Граф эскиз

Эскиз подсчета — это тип уменьшения размерности , который особенно эффективен в статистике , машинном обучении и алгоритмах . Его изобрели Моисей Чарикар, Кевин Чен и Мартин Фарах-Колтон. в попытке ускорить работу AMS Sketch Алона, Матиаса и Сегеди для аппроксимации частотных моментов потоков (эти вычисления требуют подсчета количества вхождений отдельных элементов потока).

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

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

Интуитивное объяснение

Изобретатели этой структуры данных предлагают следующее итеративное объяснение ее работы:

• На простейшем уровне выходные данные одной хеш-функции , отображающей элементы потока q подаются на один счетчик прямого/обратного преобразования C. в {+1, -1} , После одного прохода по данным частота $n(q)$ элемента потока q может быть, хотя и крайне плохо, аппроксимировано ожидаемым значением ${\mathbf {E}}[C\cdot s(q)]$;
• простой способ улучшить дисперсию предыдущей оценки — использовать массив различных хеш-функций $s_{i}$, каждый из которых подключен к своему счетчику $C_{i}$. Для каждого q элемента ${\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)$ по-прежнему сохраняется, поэтому усреднение по диапазону i приведет к ужесточению аппроксимации;
• предыдущая конструкция по-прежнему имеет серьезный недостаток: если низкочастотный, но все же важный выходной элемент a демонстрирует хеш-коллизию с высокочастотным элементом, $n(a)$ оценка может существенно измениться. Чтобы избежать этого, необходимо уменьшить частоту обновления счетчика коллизий между любыми двумя отдельными элементами. Это достигается за счет замены каждого $C_{i}$ в предыдущей конструкции с массивом из m счетчиков (преобразование счетчика в двумерную матрицу $C_{i,j}$), с индексом j конкретного счетчика, который нужно увеличить/уменьшить, выбранным с помощью другого набора хэш-функций $h_{i}$ это отображает элемент q в диапазон {1.. m }. С ${\mathbf {E}}[C_{i,h_{i}(q)}\cdot s_{i}(q)]=n(q)$, будет работать усреднение по всем значениям i .

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

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

2. Для каждого предмета $q_{i}$ в потоке добавьте $s_{j}(q_{i})$ к $h_{j}(q_{i})$ведро $j$этот хеш.

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

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

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

$r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.$

Ценности $s_{i}(q)\cdot C_{i,h_{i}(q)}$ являются несмещенными оценками того, во сколько раз $q$ появился в потоке.

Оценка $r_{q}$ имеет дисперсию $O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})$, где $m_{1}$ длина потока и $m_{2}^{2}$ является $\sum _{q}(\sum _{i}[q_{i}=q])^{2}$.

Более того, $r_{q}$ гарантированно никогда не будет больше, чем $2m_{2}/{\sqrt {w}}$ от истинного значения с вероятностью $1-e^{-O(t)}$.

формулировка

В качестве альтернативы Count-Sketch можно рассматривать как линейное отображение с функцией нелинейной реконструкции.Позволять $M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}$, быть совокупностью $d=2t+1$ матрицы, определяемые

$M_{h_{i}(j),j}^{(i)}=s_{i}(j)$

для $j\in [w]$ и 0 везде.

Тогда вектор $v\in \mathbb {R} ^{n}$ набросан $C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}$.Реконструировать $v$ мы берем $v_{j}^{*}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)$.Это дает те же гарантии, что и указано выше, если принять $m_{1}=\|v\|_{1}$ и $m_{2}=\|v\|_{2}$.

Связь с эскизом Tensor

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

Эскиз подсчета вычисляет векторную свертку

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

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

Быстрое преобразование Фурье можно использовать для быстрой свертки эскизов подсчета.Используя продукт для разделения лица такие структуры можно вычислить намного быстрее, чем обычные матрицы.

См. также

• Скетч Count-min — это версия алгоритма с меньшими требованиями к памяти (и более слабыми гарантиями ошибок в качестве компромисса).
• Тензорскетч

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

• Чарикар, Моисей; Чен, Кевин; Фарах-Колтон, Мартин (2004). «Поиск часто встречающихся элементов в потоках данных» (PDF) . Теоретическая информатика . 312 (1). Эльзевир Б.В.: 3–15. дои : 10.1016/s0304-3975(03)00400-6 . ISSN   0304-3975 .
• Фейсал М. Альгашаам; Киен Нгуен; Мохамед Алканхал; Винод Чандран; Ваги Болес. «Мультиспектральная периокулярная классификация с мультимодальным компактным многолинейным объединением» [1] . Доступ IEEE , Том. 5. 2017.
• Але, Томас; Кнудсен, Якоб (3 сентября 2019 г.). «Почти оптимальный тензорный эскиз» . Исследовательские ворота . Проверено 11 июля 2020 г.