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

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

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

ИсторияПравить

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

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

Тензорные проекцииПравить

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

Торцевое произведение двух матриц с однаковым количеством строк $\mathbf{C}\in <!--\; \in \; -->{\mathbb{R}}^{3\times <!--\; \times \; -->3}$$\mathbf {C} \in \mathbb {R} ^{3\times 3}$  и $\mathbf{D}\in <!--\; \in \; -->{\mathbb{R}}^{3\times <!--\; \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 <!--\; \bullet \; -->\mathbf{D})(x\otimes <!--\; \otimes \; -->y)=\mathbf{C}x\circ <!--\; \circ \; -->\mathbf{D}y=\left[\begin{array}{c}(\mathbf{C}x{)}_1(\mathbf{D}y{)}_1\\ (\mathbf{C}x{)}_2(\mathbf{D}y{)}_2\\ ⋮<!--\; ⋮\; -->\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 <!--\; \circ \; -->$$\circ$  — поэлементное произведение Адамара.

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

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

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

См. такжеПравить

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