Отсчётный скетч

Перейти к навигацииПерейти к поиску

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

Особенности

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

,

где означает произведение Кронекера.

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

[4]

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

,

гдe и являются независимыми матрицами.

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

Примечания

  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 Almost Optimal Tensor Sketch. Researchgate (3 сентября 2019). Дата обращения: 11 июля 2020. Архивировано 14 июля 2020 года.
  3. Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.
  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.