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

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

Історія

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

Спочатку відповідний метод спирався на використання швидкого перетворення Фур'є, щоб зробити швидку згортку. Пізніші науково-дослідні роботи узагальнили його до значно більшого класу методів зменшення розмірності за допомогою випадкових тензорних проєкцій.

Тензорні проєкції

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

Торцевий добуток двох матриць з однаковою кількістю рядків $\mathbf {C} \in \mathbb {R} ^{3\times 2}$ та $\mathbf {D} \in \mathbb {R} ^{3\times 2}$ позначається $\mathbf {C} \bullet \mathbf {D}$ і має вид: $\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}\mathbf {C} _{1,1}\mathbf {D} _{1,1}&\mathbf {C} _{1,1}\mathbf {D} _{1,2}&\mathbf {C} _{1,2}\mathbf {D} _{1,1}&\mathbf {C} _{1,2}\mathbf {D} _{1,2}&\mathbf {C} _{1,3}\mathbf {D} _{1,1}&\mathbf {C} _{1,3}\mathbf {D} _{1,2}\\\mathbf {C} _{2,1}\mathbf {D} _{2,1}&\mathbf {C} _{2,1}\mathbf {D} _{2,2}&\mathbf {C} _{2,2}\mathbf {D} _{2,1}&\mathbf {C} _{2,2}\mathbf {D} _{2,2}&\mathbf {C} _{2,3}\mathbf {D} _{2,1}&\mathbf {C} _{2,3}\mathbf {D} _{2,2}\\\mathbf {C} _{3,1}\mathbf {D} _{3,1}&\mathbf {C} _{3,1}\mathbf {D} _{3,2}&\mathbf {C} _{3,2}\mathbf {D} _{3,1}&\mathbf {C} _{3,2}\mathbf {D} _{3,2}&\mathbf {C} _{3,3}\mathbf {D} _{3,1}&\mathbf {C} _{3,3}\mathbf {D} _{3,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$ — поелементний добуток Адамара.

На цій основі довільний тензорний скетч виду $\mathbf {M} (y\otimes z)$ можливо подати як $\mathbf {M'} y\circ \mathbf {M''} z$, де матриці $\mathbf {M'}$ та $\mathbf {M''}$ мають менший розмір, і $\mathbf {M} =\mathbf {M'} \bullet \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$, економія буде ще більш значною.

Подібне перетворення задовольняє лемі Джонсона-Лінденштрауса про малі викривлення вихідних даних великої розмірності.

Див. також

• Лема Джонсона-Лінденштрауса
• Торцевий добуток
• Відліковий скетч