PROFILPELAJAR.COM

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

Історія

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

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

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

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

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

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

Див. також

Примітки

↑ Low-rank Tucker decomposition of large tensors using: Tensor Sketch (PDF). amath.colorado.edu. Boulder, Colorado: University of Colorado Boulder. Архів оригіналу (PDF) за 14 лютого 2019. Процитовано 30 липня 2020. [Архівовано 2019-02-14 у Wayback Machine.]
↑ Ahle, Thomas; Knudsen, Jakob (3 вересня 2019). Almost Optimal Tensor Sketch. Researchgate. Процитовано 11 липня 2020.
↑ Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1–157.
↑ Ninh, Pham; Rasmus, Pagh (2013). Fast and scalable polynomial kernels via explicit feature maps. SIGKDD international conference on Knowledge discovery and data mining. Association for Computing Machinery. doi:10.1145/2487575.2487591.
↑ Rasmus, Pagh (2013). Compressed matrix multiplication. ACM Transactions on Computation Theory, August 2013 Article No.: 9. Association for Computing Machinery. doi:10.1145/2493252.2493254.
↑ Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics — Theory and Methods, 38:19, P. 3501 [1]
↑ ^а ^б Slyusar, V. I. (27 грудня 1996). End products in matrices in radar applications (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53.
↑ ^а ^б Slyusar, V. I. Analytical model of the digital antenna array on a basis of face-splitting matrix products : [англ.] // Proc. ICATT- 97, Kyiv : journal. — 1997. — 20 травня. — С. 108—109.
↑ ^а ^б Slyusar, V. I. A Family of Face Products of Matrices and its Properties : [англ.] // Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz : journal. — 1999. — Vol. 35, № 3. — С. 379—384. — DOI:10.1007/BF02733426.
↑ Slyusar, V. I. Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels : [англ.] // Radioelectronics and Communications Systems : journal. — 2003. — Vol. 46, № 10. — С. 9—17.
↑ Миночкин А.И., Рудаков В.И., Слюсар В.И. (2012). Основы военно-технических исследований. Теория и приложения. Том. 2. Синтез средств информационного обеспечения вооружения и военной техники//Под ред. А.П. Ковтуненко. - Киев: «Гранмна». – 2012 (PDF). с. C. 7 - 98, 354—521.
↑ Slyusar, V. I. (15 вересня 1997). New operations of matrices product for applications of radars (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74.