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

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

История[править | править код]

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

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

Тензорные проекции[править | править код]

В основе одного из вариантов тензорного скетча лежит применение торцевого произведения матриц, предложенного Слюсарем В. И.^[6] в 1996 г. (англ. face-splitting product)^{[7][8][9][10][11]}.

Торцевое произведение двух матриц с однаковым количеством строк ${\displaystyle \mathbf {C} \in \mathbb {R} ^{3\times 3}}$ и ${\displaystyle \mathbf {D} \in \mathbb {R} ^{3\times 3}}$ имеет вид^{[7][8][9][12]}: ${\displaystyle \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].}$

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

${\displaystyle (\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],}$

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

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

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

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

См. также[править | править код]

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

Примечания[править | править код]