Граф эскиз - Count sketch

Граф эскиз это тип уменьшение размерности это особенно эффективно в статистика, машинное обучение и алгоритмы.^[1][2]Его изобрели Мозес Чарикар, Кевин Чен и Мартин Фарач-Колтон.^[3] в попытке ускорить Эскиз AMS Алон, Матиас и Сегеди за аппроксимацию частотных моментов потоков.^[4]

Эскиз почти идентичен Хеширование функций алгоритм Джона Муди,^[5] но отличается использованием хэш-функций с низкой зависимостью, что делает его более практичным. Чтобы по-прежнему иметь высокую вероятность успеха, средний трюк используется для объединения нескольких скетчей, а не среднего.

Эти свойства позволяют использовать явные методы ядра, билинейный объединение в нейронные сети и является краеугольным камнем многих алгоритмов численной линейной алгебры.^[6]

Математическое определение

1. Для констант ${\displaystyle w}$ и ${\displaystyle d}$ (будет определено позже) самостоятельно выбрать ${\displaystyle 2d}$ случайные хеш-функции${\displaystyle h_{1},\dots ,h_{d}}$ и ${\displaystyle s_{1},\dots ,s_{d}}$ такой, что${\displaystyle h_{i}:[n]\to [w]}$ и${\displaystyle s_{i}:[n]\to \{\pm 1\}}$. Необходимо, чтобы хеш-семейства, из которых ${\displaystyle h_{i}}$ и ${\displaystyle s_{i}}$ выбраны попарно независимыми.

2. По каждому пункту ${\displaystyle q_{i}}$ в потоке добавьте ${\displaystyle s_{j}(q_{i})}$ к ${\displaystyle h_{j}(q_{i})}$ое ведро ${\displaystyle j}$й хеш.

В конце этого процесса ${\displaystyle wd}$ суммы ${\displaystyle (C_{ij})}$ куда

${\displaystyle C_{ij}=\sum _{h_{i}(k)=j}s_{i}(k).}$

Чтобы оценить количество ${\displaystyle q}$s вычисляет следующее значение:

${\displaystyle {\text{median}}_{i}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.}$

Связь с тензорным скетчем

Счетная эскизная проекция внешний продукт двух векторов эквивалентно свертка двухкомпонентных графических эскизов.

Эскиз счетчика вычисляет вектор свертка

${\displaystyle C^{(1)}x\ast C^{(2)}x^{T}}$, куда ${\displaystyle C^{(1)}}$ и ${\displaystyle C^{(2)}}$ являются независимыми скетч-матрицами подсчета.

Фам и Паг^[7] показать, что это равно ${\displaystyle C(x\otimes x^{T})}$ - графическая зарисовка ${\displaystyle C}$ из внешний продукт векторов, где ${\displaystyle \otimes }$ обозначает Кронекер продукт.

Для быстрой свертки счетных эскизов можно использовать быстрое преобразование Фурье. С помощью продукт, расщепляющий лицо^[8][9][10] такая структура вычисляется намного быстрее, чем обычные матрицы.

Смотрите также

• Счетчик мин. Эскиз
• Тензорский эскиз

Рекомендации

1. Фейсал М. Алгашам; Киен Нгуен; Мохамед Алканхал; Винод Чандран; Wageeh Boles. «Мультиспектральная периокулярная классификация с мультимодальным компактным мультилинейным объединением» [1]. Доступ IEEE, Vol. 5. 2017.
2. Ахле, Томас; Кнудсен, Якоб (2019-09-03). «Почти оптимальный тензорный набросок». Researchgate. Получено 2020-07-11.
3. Чарикар, Моисей, Кевин Чен и Мартин Фарач-Колтон. «Обнаружение частых элементов в потоках данных». Международный коллоквиум по автоматам, языкам и программированию. Шпрингер, Берлин, Гейдельберг, 2002.
4. Алон, Нога, Йоси Матиас и Марио Сегеди. «Пространственная сложность аппроксимации частотных моментов». Журнал компьютерных и системных наук 58.1 (1999): 137-147.
5. Муди, Джон. «Быстрое обучение в иерархиях с несколькими разрешениями». Достижения в области нейронных систем обработки информации. 1989 г.
6. Вудрафф, Дэвид П. «Создание эскизов как инструмент численной линейной алгебры». Теоретическая информатика 10.1-2 (2014): 1–157.
7. Нинь, Фам; Расмус, Паг (2013). Быстрые и масштабируемые полиномиальные ядра с помощью явных карт функций. Международная конференция SIGKDD по обнаружению знаний и интеллектуальному анализу данных. Ассоциация вычислительной техники. Дои:10.1145/2487575.2487591.
8. Слюсарь В. И. (1998). «Конечные продукты в матрицах в радиолокационных приложениях» (PDF). Радиоэлектроника и системы связи. 41 (3): 50–53.
9. Слюсарь, В. И. (20.05.1997). «Аналитическая модель цифровой антенной решетки на основе матричных продуктов расщепления граней» (PDF). Proc. ICATT-97, Киев: 108–109.
10. Слюсарь В. И. (13 марта 1998 г.). «Семейство граней произведений матриц и его свойства» (PDF). Кибернетика и системный анализ К / К Кибернетика и Системный анализ.- 1999.. 35 (3): 379–384. Дои:10.1007 / BF02733426.

дальнейшее чтение

• Фейсал М. Алгашам; Киен Нгуен; Мохамед Алканхал; Винод Чандран; Wageeh Boles. «Мультиспектральная периокулярная классификация с мультимодальным компактным мультилинейным объединением» [1]. Доступ IEEE, Vol. 5. 2017.
• Ахле, Томас; Кнудсен, Якоб (2019-09-03). «Почти оптимальный тензорный набросок». Researchgate. Получено 2020-07-11.