Отсчётный скетч ( англ. Count sketch ) — метод уменьшения размерности, используемый в статистике, машинном обучении и алгоритмах обработки больших данных . Может быть использован для ускорения ядерного метода и билинейного пулинга в нейронных сетях , а также в численных алгоритмах линейной алгебры .

Особенности

В отличие от тензорного скетча отсчётный скетч оперирует так называемым внешним произведением векторов:

${\displaystyle \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}}}$ ,

где ${\displaystyle \otimes }$ означает произведение Кронекера .

Существенно, что отсчётный скетч от такого произведения двух векторов

${\displaystyle C(x\otimes x^{T})}$

эквивалентен векторной свёртке

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

гдe ${\displaystyle C^{(1)}}$ и ${\displaystyle C^{(2)}}$ являются независимыми матрицами.

Для сокращения вычислительных затрат на реализацию свёртки нескольких отсчётных скетчей может быть использовано быстрое преобразование Фурье .

Примечания