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

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

Історія

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

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

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

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

Торцевий добуток двох матриць з однаковою кількістю рядків $𝐂\in {ℝ}^{3\times 2}$ та $𝐃\in {ℝ}^{3\times 2}$ позначається $𝐂\bullet 𝐃$ і має вид: $𝐂\bullet 𝐃=\left[\begin{array}{c}{𝐂}_1\otimes {𝐃}_1\\ {𝐂}_2\otimes {𝐃}_2\\ {𝐂}_3\otimes {𝐃}_3\end{array}\right]=\left[\begin{array}{cccccc}{𝐂}_{1,1}{𝐃}_{1,1}& {𝐂}_{1,1}{𝐃}_{1,2}& {𝐂}_{1,2}{𝐃}_{1,1}& {𝐂}_{1,2}{𝐃}_{1,2}& {𝐂}_{1,3}{𝐃}_{1,1}& {𝐂}_{1,3}{𝐃}_{1,2}\\ {𝐂}_{2,1}{𝐃}_{2,1}& {𝐂}_{2,1}{𝐃}_{2,2}& {𝐂}_{2,2}{𝐃}_{2,1}& {𝐂}_{2,2}{𝐃}_{2,2}& {𝐂}_{2,3}{𝐃}_{2,1}& {𝐂}_{2,3}{𝐃}_{2,2}\\ {𝐂}_{3,1}{𝐃}_{3,1}& {𝐂}_{3,1}{𝐃}_{3,2}& {𝐂}_{3,2}{𝐃}_{3,1}& {𝐂}_{3,2}{𝐃}_{3,2}& {𝐂}_{3,3}{𝐃}_{3,1}& {𝐂}_{3,3}{𝐃}_{3,2}\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$, економія буде ще більш значною.

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

Див. також

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