Тензорный скетч

Тензорный скетч может использоваться для уменьшения количества переменных, необходимых для реализации билинейного пулинга в нейронной сети

Тензорный скетч (англ. tensor sketch) — метод уменьшения размерности, используемый в статистике, машинном обучении и алгоритмах обработки больших данных. Он особенно эффективен применительно к векторам, имеющим тензорную структуру. Такой скетч может быть использован для ускорения билинейного объединения в нейронных сетях и является краеугольным камнем во многих алгоритмах числовой линейной алгебры.

История

Термин тензорный скетч (эскиз) был придуман в 2013 г. и в том же году описан как метод Расмусом Пегом.

Сначала соответствующий метод базировался на использовании быстрого преобразования Фурье, чтобы реализовать быструю свёртку аналогично отсчётному скетчу. В результате дальнейших исследований его обобщили на значительно больший класс методов уменьшения размерности с помощью случайных тензорных проекций.

Тензорные проекции

В основе одного из вариантов тензорного скетча лежит применение торцевого произведения матриц, предложенного Слюсарем В. И. в 1996 г. (англ. face-splitting product).

Торцевое произведение двух матриц с однаковым количеством строк $\mathbf {C} \in \mathbb {R} ^{3\times 3}$ и $\mathbf {D} \in \mathbb {R} ^{3\times 3}$ имеет вид: $\mathbf {C} \bullet \mathbf {D} =\left[{\begin{array}{c }\mathbf {C} _{1}\otimes \mathbf {D} _{1}\\\hline \mathbf {C} _{2}\otimes \mathbf {D} _{2}\\\hline \mathbf {C} _{3}\otimes \mathbf {D} _{3}\\\end{array}}\right]=\left[{\begin{array}{c c c c c c c c c }\mathbf {C} _{1,1}\mathbf {D} _{1,1}&\mathbf {C} _{1,1}\mathbf {D} _{1,2}&\mathbf {C} _{1,1}\mathbf {D} _{1,3}&\mathbf {C} _{1,2}\mathbf {D} _{1,1}&\mathbf {C} _{1,2}\mathbf {D} _{1,2}&\mathbf {C} _{1,2}\mathbf {D} _{1,3}&\mathbf {C} _{1,3}\mathbf {D} _{1,1}&\mathbf {C} _{1,3}\mathbf {D} _{1,2}&\mathbf {C} _{1,3}\mathbf {D} _{1,3}\\\hline \mathbf {C} _{2,1}\mathbf {D} _{2,1}&\mathbf {C} _{2,1}\mathbf {D} _{2,2}&\mathbf {C} _{2,1}\mathbf {D} _{2,3}&\mathbf {C} _{2,2}\mathbf {D} _{2,1}&\mathbf {C} _{2,2}\mathbf {D} _{2,2}&\mathbf {C} _{2,2}\mathbf {D} _{2,3}&\mathbf {C} _{2,3}\mathbf {D} _{2,1}&\mathbf {C} _{2,3}\mathbf {D} _{2,2}&\mathbf {C} _{2,3}\mathbf {D} _{2,3}\\\hline \mathbf {C} _{3,1}\mathbf {D} _{3,1}&\mathbf {C} _{3,1}\mathbf {D} _{3,2}&\mathbf {C} _{3,1}\mathbf {D} _{3,3}&\mathbf {C} _{3,2}\mathbf {D} _{3,1}&\mathbf {C} _{3,2}\mathbf {D} _{3,2}&\mathbf {C} _{3,2}\mathbf {D} _{3,3}&\mathbf {C} _{3,3}\mathbf {D} _{3,1}&\mathbf {C} _{3,3}\mathbf {D} _{3,2}&\mathbf {C} _{3,3}\mathbf {D} _{3,3}\end{array}}\right].$

Целесообразность использования этого произведения заключается в его свойстве:

$(\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right],$

где $\circ$ — поэлементное произведение Адамара.

На этой основе произвольный тензорный скетч вида $\mathbf {M} (y\otimes z)$ можно представить как $\mathbf {M'} y\circ \mathbf {M''} z$, где матрицы $\mathbf {M'}$ и $\mathbf {M''}$ имеют меньшую размерность, и $\mathbf {M'} \bullet \mathbf {M''} =\mathbf {M}$. Поскольку операции $\mathbf {M'} y$ и $\mathbf {M''} z$ выполнимы за линейное время $kd_{1}$ и $kd_{2}$ соответственно, переход к представлению $\mathbf {M'} \bullet \mathbf {M''}$ позволяет выполнить умножение на векторы с тензорной структурой намного быстрее, чем формируется исходное выражение $\mathbf {M} (y\otimes z)$, а именно за время $kd=kd_{1}d_{2}$.

Для тензоров более высокого порядка, например, $x=y\otimes z\otimes t$, экономия будет ещё более значимой.

Подобное преобразование удовлетворяет лемме о малых искажениях исходных данных большой размерности.

См. также

• Торцевое произведение
• Лемма о малом искажении