Відліковий скетч

Відліковий скетч (англ. 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)}$ є незалежними матрицями.

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

Див. також

• Лема Джонсона-Лінденштрауса
• Тензорний скетч