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

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

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

История

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

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

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

В основе одного из вариантов тензорного скетча лежит применение торцевого произведения матриц, предложенного Слюсарем В. И. в 1996 г. (Шаблон:Lang-en).

Торцевое произведение двух матриц с однаковым количеством строк $𝐂\in {ℝ}^{3\times 3}$ и $𝐃\in {ℝ}^{3\times 3}$ имеет вид: $𝐂\bullet 𝐃=\left[\begin{array}{c}{𝐂}_1\otimes {𝐃}_1\\ {𝐂}_2\otimes {𝐃}_2\\ {𝐂}_3\otimes {𝐃}_3\end{array}\right]=\left[\begin{array}{ccccccccc}{𝐂}_{1,1}{𝐃}_{1,1}& {𝐂}_{1,1}{𝐃}_{1,2}& {𝐂}_{1,1}{𝐃}_{1,3}& {𝐂}_{1,2}{𝐃}_{1,1}& {𝐂}_{1,2}{𝐃}_{1,2}& {𝐂}_{1,2}{𝐃}_{1,3}& {𝐂}_{1,3}{𝐃}_{1,1}& {𝐂}_{1,3}{𝐃}_{1,2}& {𝐂}_{1,3}{𝐃}_{1,3}\\ {𝐂}_{2,1}{𝐃}_{2,1}& {𝐂}_{2,1}{𝐃}_{2,2}& {𝐂}_{2,1}{𝐃}_{2,3}& {𝐂}_{2,2}{𝐃}_{2,1}& {𝐂}_{2,2}{𝐃}_{2,2}& {𝐂}_{2,2}{𝐃}_{2,3}& {𝐂}_{2,3}{𝐃}_{2,1}& {𝐂}_{2,3}{𝐃}_{2,2}& {𝐂}_{2,3}{𝐃}_{2,3}\\ {𝐂}_{3,1}{𝐃}_{3,1}& {𝐂}_{3,1}{𝐃}_{3,2}& {𝐂}_{3,1}{𝐃}_{3,3}& {𝐂}_{3,2}{𝐃}_{3,1}& {𝐂}_{3,2}{𝐃}_{3,2}& {𝐂}_{3,2}{𝐃}_{3,3}& {𝐂}_{3,3}{𝐃}_{3,1}& {𝐂}_{3,3}{𝐃}_{3,2}& {𝐂}_{3,3}{𝐃}_{3,3}\end{array}\right].$

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

$(𝐂\bullet 𝐃)(x\otimes y)=𝐂x\circ 𝐃y=\left[\begin{array}{c}(𝐂x{)}_1(𝐃y{)}_1\\ (𝐂x{)}_2(𝐃y{)}_2\\ ⋮\end{array}\right],$

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

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

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

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

См. также

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