Відліковий скетч англ Count sketch метод зменшення розмірності що використовується у статистиці машинному навчанні та ал

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

Відліковий скетч може використовуватися для зменшення обочислень при реалізації білінійного пулінгу в нейронній мережі

Особливості

На відміну від тензорного скетчу відліковий скетч оперує так званим зовнішнім добутком векторів:

\mathbf {a} \otimes \mathbf {b^{T}} \rightarrow {\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\a_{4}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&b_{3}\end{bmatrix}}={\begin{bmatrix}a_{1}b_{1}&a_{1}b_{2}&a_{1}b_{3}\\a_{2}b_{1}&a_{2}b_{2}&a_{2}b_{3}\\a_{3}b_{1}&a_{3}b_{2}&a_{3}b_{3}\\a_{4}b_{1}&a_{4}b_{2}&a_{4}b_{3}\end{bmatrix}}

,

де $\otimes$ означає добуток Кронекера.

Суттєво, що відліковий скетч від зовнішнього добутку двох векторів

C(x\otimes x^{T})

еквівалентний векторній згортці

C^{(1)}x\ast C^{(2)}x^{T}

,

де $C^{(1)}$ і $C^{(2)}$ є незалежними матрицями.

Для прискореного обчислення згортки відлікових скетчів може бути задіяне швидке перетворення Фур'є. У цьому випадку завдяки використанню (торцевого добутку) матриць для факторизації матриці скетчу відповідні структури можуть бути розраховані значно швидше.

Див. також

Примітки

Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles.Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling [1]. — IEEE Access, Vol. 5. 2017.
Ahle, Thomas; Knudsen, Jakob (3 вересня 2019). . Researchgate. Архів оригіналу за 14 липня 2020. Процитовано 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.
Slyusar, V. I. (27 грудня 1996). (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 2 серпня 2020.
Slyusar, V. I. (20 травня 1997). (PDF). Proc. ICATT-97, Kyiv: 108—109. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 2 серпня 2020.
Slyusar, V. I. (13 березня 1998). (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379—384. doi:10.1007/BF02733426. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 2 серпня 2020.

[1] Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles.Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling [1]. — IEEE Access, Vol. 5. 2017.

[2] Ahle, Thomas; Knudsen, Jakob (3 вересня 2019). . Researchgate. Архів оригіналу за 14 липня 2020. Процитовано 11 липня 2020.

[woodruff-3] Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1–157.

[ninh-4] 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.

[5] Slyusar, V. I. (27 грудня 1996). (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 2 серпня 2020.

[6] Slyusar, V. I. (20 травня 1997). (PDF). Proc. ICATT-97, Kyiv: 108—109. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 2 серпня 2020.

[7] Slyusar, V. I. (13 березня 1998). (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379—384. doi:10.1007/BF02733426. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 2 серпня 2020.