Участник:Warmte — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
==Точность==
 
==Точность==
  
При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{2^r}}</tex>. Также этот алгоритм способен оценивать значения, превышающие 10<sup>9</sup>, используя 1.5 kB памяти для получения ответа с точностью 2%.  
+
При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{m}}</tex>. Также этот алгоритм способен оценивать значения, превышающие 10<sup>9</sup>, используя 1.5 kB памяти для получения ответа с точностью 2%.  
  
 
Предыдущий алгоритм '''LogLog''', использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.
 
Предыдущий алгоритм '''LogLog''', использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.
  
 
==Идея алгоритма==
 
==Идея алгоритма==
В основе алгоритма '''HyperLogLog''' лежит наблюдение, что мощность набора равномерно распределенных случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>.
+
{{Определение
 +
|definition=
 +
Обозначим за '''мощность''' набора количество различных элементов в нём.
 +
}}
  
Суть алгоритма заключается в следующем: к каждому элемента исходного набора применяется хеш-функция для получения набора равномерно распределенных случайных чисел с той же мощностью, что и исходный набор. Затем мощность этого случайно распределенного набора оценивается с помощью описанного выше алгоритма.
+
В основе алгоритма '''HyperLogLog''' лежит наблюдение, что мощность набора [[wikipedia:ru:Равномерное_распределение|равномерно распределенных]] случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>.
  
Но при таком подходе могут возникать различные проблемы за счёт большой дисперсии получаемой величины, а также некоторых крайних случаев: к примеру, если хэш некоторого элемента будет равен <tex>0</tex>, то максимальное количество ведущих нулей сразу станет равным <tex>log_2{m}</tex>, где <tex>m</tex> {{---}} максимальное значение выбранной хэш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на <tex>2^r</tex> корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.  
+
Суть алгоритма заключается в следующем: к каждому элементу исходного набора применяется [[wikipedia:ru:Хеш-функция|хеш-функция]] для получения набора равномерно распределенных случайных чисел с той же мощностью, что и исходный набор. Затем мощность этого случайно распределенного набора оценивается с помощью описанного выше алгоритма.
 +
 
 +
Но при таком подходе могут возникать различные проблемы за счёт большой [[wikipedia:ru:Дисперсия_случайной_величины|дисперсии]] получаемой величины, а также некоторых крайних случаев: к примеру, если хэш некоторого элемента будет равен <tex>0</tex>, то максимальное количество ведущих нулей сразу станет равным <tex>log_2{m}</tex>, где <tex>m</tex> {{---}} максимальное значение выбранной хэш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на <tex>2^r</tex> корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.  
  
 
==Описание алгоритма==
 
==Описание алгоритма==
 
* <tex>\mathcal{M}</tex> {{---}} исходный набор элементов <tex>a_1 ... a_n</tex>.
 
* <tex>\mathcal{M}</tex> {{---}} исходный набор элементов <tex>a_1 ... a_n</tex>.
  
* <tex>h : \mathcal{U} \to {0, 1 ... 2^k - 1}</tex> {{---}} выбранная хэш-функция с возможными значениями от <tex>0</tex> до <tex>m - 1</tex>, <tex>k = log_2{m}</tex>.
+
* <tex>h : \mathcal{U} \to {0, 1 ... 2^k-1}</tex> {{---}} выбранная хэш-функция с возможными значениями от <tex>0</tex> до <tex>m-1</tex>, <tex>k = log_2{m}</tex>.
  
 
* <tex>r</tex> {{---}} количество бит исходного хэша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.
 
* <tex>r</tex> {{---}} количество бит исходного хэша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.
Строка 31: Строка 36:
 
Для каждой корзины вычислим соответствующее <tex>z_j</tex>, равное максимальному количеству ведущих нулей среди элементов этой корзины. Тогда оценкой для числа различных элементов в корзине будет <tex>2^{z_j}</tex>.
 
Для каждой корзины вычислим соответствующее <tex>z_j</tex>, равное максимальному количеству ведущих нулей среди элементов этой корзины. Тогда оценкой для числа различных элементов в корзине будет <tex>2^{z_j}</tex>.
  
Логично было бы предположить, что в таком случае итоговым ответом на задачу будет <tex> \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} </tex>, но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок:
+
Логично было бы предположить, что в таком случае итоговым ответом на задачу будет <tex> \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} </tex>, но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок: <tex>E \approx \alpha \cdot (2^r)^2 \cdot I</tex>
  
<tex>E \approx \alpha \cdot (2^r)^2 \cdot I</tex>
+
<tex>I</tex> {{---}} это индикатор, вычисляемый по формуле <tex>I = (\sum\limits_{j=0}^{2^{r - 1}} \frac{1}{2^{z_j}})^{-1} </tex>
  
* <tex>I</tex> {{---}} это индикатор, вычисляемый по формуле <tex>I = (\sum\limits_{j=0}^{2^{r - 1}} \frac{1}{2^{z_j}})^{-1} </tex>
+
<tex>\alpha</tex> {{---}} корректирующий множитель, вычисляемый по формуле <tex>\alpha = (2^r  \int\limits_{0}^{\infty} (log_2{\frac{2 + u}{1 + u}})^{2^r} \,du )^{-1}</tex>.
  
* <tex>\alpha</tex> {{---}} корректирующий множитель, вычисляемый по формуле <tex>\alpha = (2^r \int\limits_{0}^{\infty} (log_2{\frac{2 + u}{1 + u}})^{2^r} \,du )^{-1}</tex>.
+
Поскольку множитель <tex>\alpha</tex> может быть достаточно сложным для вычисления, можно подобрать его примерное значение в зависимости от <tex>r</tex>:
  
Поскольку множитель <tex>\alpha</tex> может быть достаточно сложным для вычисления, можно подобрать его примерное значение в зависимости от <tex>r</tex>:
+
<tex>
 +
\alpha_{r}\approx\begin{cases}
 +
r=4 & 0.673\\
 +
r=5 & 0.697\\
 +
r=6 & 0.709\\
 +
r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}}
 +
\end{cases}
 +
</tex>
  
:<tex>
+
Число <tex>E</tex> и будет итоговой оценкой мощности данного набора.
\alpha_{r}\approx\begin{cases}
 
r=4 & 0.673\\
 
r=5 & 0.697\\
 
r=6 & 0.709\\
 
r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}}
 
\end{cases}
 
</tex>
 
  
==Доказательство==
+
==План доказательства==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Идеальным мультимножеством''' с количеством различных элементов <tex>n</tex> называется последовательность, полученная произвольными повторениями и перестановками, применяемыми к <tex>n</tex> равномерно распределенным случайным величинам на действительном интервале [0, 1].
+
'''Идеальным мультимножеством''' мощностью <tex>n</tex> называется последовательность, полученная произвольными повторениями и перестановками, применяемыми к <tex>n</tex> равномерно распределенным случайным величинам на действительном интервале [0, 1].
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть алгоритм '''HyperLogLog''' применяется к идеальному мультимножеству, содержащему <tex>n</tex> различных элементов (число <tex>n</tex> нам неизвестно), используя <tex>reg = 2^r</tex> корзин, и пусть <tex>E</tex> {{---}} полученная результирующая оценка количества различных элементов в этом мультимножестве.
+
Пусть алгоритм '''HyperLogLog''' применяется к идеальному мультимножеству мощностью <tex>n</tex> (число <tex>n</tex> нам неизвестно), используя <tex>reg = 2^r</tex> корзин, и пусть <tex>E</tex> {{---}} полученная результирующая оценка количества различных элементов в этом мультимножестве.
  
 
# Оценка величины E в таком случае асимптотически почти несмещенная, а именно: <br /> <tex> \frac{1}{n} \mathbb{E}(E) \overset{n \to \infty}{=} 1 + \delta_1(n) + o(1)</tex>, где <tex>|\delta_1(n)| < 5 \cdot 10^{-5}</tex> при <tex>reg \geq 16</tex>
 
# Оценка величины E в таком случае асимптотически почти несмещенная, а именно: <br /> <tex> \frac{1}{n} \mathbb{E}(E) \overset{n \to \infty}{=} 1 + \delta_1(n) + o(1)</tex>, где <tex>|\delta_1(n)| < 5 \cdot 10^{-5}</tex> при <tex>reg \geq 16</tex>
 
 
# Стандартная ошибка, равная <tex>\frac{1}{n}\sqrt{\mathbb{D}_n(E)}</tex>, вычисляется следующим образом: <br /> <tex>\frac{1}{n}\sqrt{\mathbb{D}_n(E)} \overset{n \to \infty}{=} \frac{\beta_{reg}}{\sqrt{r}} + \delta_2(n) + o(1)</tex>, где <tex>|\delta_2(n)| < 5 \cdot 10^{-4}</tex> при <tex>reg \geq 16</tex>
 
# Стандартная ошибка, равная <tex>\frac{1}{n}\sqrt{\mathbb{D}_n(E)}</tex>, вычисляется следующим образом: <br /> <tex>\frac{1}{n}\sqrt{\mathbb{D}_n(E)} \overset{n \to \infty}{=} \frac{\beta_{reg}}{\sqrt{r}} + \delta_2(n) + o(1)</tex>, где <tex>|\delta_2(n)| < 5 \cdot 10^{-4}</tex> при <tex>reg \geq 16</tex>
  
Строка 91: Строка 95:
 
Оценка времени работы: <tex>\mathcal{O}(n)</tex>, где <tex>n</tex> {{---}} количество элементов в исходном наборе.
 
Оценка времени работы: <tex>\mathcal{O}(n)</tex>, где <tex>n</tex> {{---}} количество элементов в исходном наборе.
  
Оценка дополнительной памяти: <tex>2^r \cdot log_2(k) = 2^r \cdot log_2 log_2 m </tex>, где <tex>m</tex> {{---}} количество возможных значений хэш-функции.
+
Оценка дополнительной памяти: <tex>\mathcal{O}(2^r \cdot log_2 log_2 n) </tex>.
  
 
==Практические оптимизации==
 
==Практические оптимизации==
Полученное при помощи алгоритма HyperLogLog значение <tex>E</tex> может оказаться неточным и нуждается в корректировке:
+
Полученное при помощи алгоритма '''HyperLogLog''' значение <tex>E</tex> может оказаться неточным и нуждается в корректировке:
* При <tex>E \leq \frac{5}{2}2^r</tex> в оценке могут появляться нелинейные искажения, которые необходимо скорректировать. Вычислим количество <tex>z_j</tex> равных <tex>0</tex>, обозначим эту величину за <tex>V</tex>. Если <tex>V = 0</tex>, то уже полученное алгоритмом значение <tex>E</tex> в корректировке не нуждается, иначе оно должно быть вычислено по формуле <tex>E_{result} = 2^r \frac{2^r}{V}</tex>.
+
* При <tex>E \leq \frac{5}{2}2^r</tex> в оценке могут появляться нелинейные искажения, которые необходимо скорректировать. Вычислим количество <tex>z_j</tex> равных <tex>0</tex>, обозначим эту величину за <tex>V</tex>. Если <tex>V = 0</tex>, то уже полученное алгоритмом значение <tex>E</tex> в корректировке не нуждается, иначе оно должно быть вычислено по формуле <tex>E_{result} = 2^r log(\frac{2^r}{V})</tex>.
* В том случае, если значение <tex>E</tex> превосходит ограничение на размер <tex>z_j</tex>, итоговая оценка также должна быть скорректирована. Рассмотрим 32-битный случай: при <tex>E > \frac{2^{32}}{30}</tex> итоговое значение можно вычислить как <tex>E_{result} = -2^{32} log(1 - \frac{E}{2^{32}})</tex>. Это может быть полезным при больших <tex>n</tex>, близких к (в нашем примере) 2^{32}, когда вероятность коллизии при хешировании становится довольно высокой.
+
* В том случае, если значение <tex>E</tex> превосходит ограничение на размер <tex>z_j</tex>, возрастает вероятность коллизии при хешировании и итоговая оценка также должна быть скорректирована. Рассмотрим 32-битный случай: при <tex>E > \frac{2^{32}}{30}</tex> итоговое значение можно вычислить как <tex>E_{result} = -2^{32} log(1 - \frac{E}{2^{32}})</tex>.
 
* В остальных случаях итоговая оценка <tex>E</tex> в корректировке не нуждается.
 
* В остальных случаях итоговая оценка <tex>E</tex> в корректировке не нуждается.
  

Версия 21:53, 18 января 2022

HyperLogLog — это вероятностный алгоритм, оценивающий количество различных элементов в больших потоках данных. Является стриминговым алгоритмом (англ. streaming algorithm), то есть обрабатывает последовательно поступающие данные в один проход.

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

Точность

При использовании [math]m[/math] единиц дополнительной памяти алгоритм HyperLogLog оценивает количество различных элементов со стандартной ошибкой около [math]\frac{1.04}{\sqrt{m}}[/math]. Также этот алгоритм способен оценивать значения, превышающие 109, используя 1.5 kB памяти для получения ответа с точностью 2%.

Предыдущий алгоритм LogLog, использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.

Идея алгоритма

Определение:
Обозначим за мощность набора количество различных элементов в нём.


В основе алгоритма HyperLogLog лежит наблюдение, что мощность набора равномерно распределенных случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно [math]n[/math], то оценка количества различных элементов в наборе будет [math]2^n[/math].

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

Но при таком подходе могут возникать различные проблемы за счёт большой дисперсии получаемой величины, а также некоторых крайних случаев: к примеру, если хэш некоторого элемента будет равен [math]0[/math], то максимальное количество ведущих нулей сразу станет равным [math]log_2{m}[/math], где [math]m[/math] — максимальное значение выбранной хэш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на [math]2^r[/math] корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.

Описание алгоритма

  • [math]\mathcal{M}[/math] — исходный набор элементов [math]a_1 ... a_n[/math].
  • [math]h : \mathcal{U} \to {0, 1 ... 2^k-1}[/math] — выбранная хэш-функция с возможными значениями от [math]0[/math] до [math]m-1[/math], [math]k = log_2{m}[/math].
  • [math]r[/math] — количество бит исходного хэша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.
  • [math]z_j[/math] — максимальное наблюдаемое количество начальных нулей в корзине под номером [math]j[/math].

Разобьём исходный набор [math]\mathcal{M}[/math] на наборы [math]\mathcal{M}_0..\mathcal{M}_{2^r - 1}[/math] следующим образом: для каждого поступающего элемента [math]a_i[/math] вычислим его хэш [math]h(a_i)[/math] и представим его в двоичном виде. Тогда первые [math]r[/math] бит этого двоичного представления будут характеризовать номер корзины [math]j[/math], а оставшиеся биты сформируют остаточный хэш [math]h'(a_i)[/math], который и будет использоваться для поиска максимального количества начальных нулей в корзине [math]\mathcal{M}_j[/math].

Hll bins.jpg

Для каждой корзины вычислим соответствующее [math]z_j[/math], равное максимальному количеству ведущих нулей среди элементов этой корзины. Тогда оценкой для числа различных элементов в корзине будет [math]2^{z_j}[/math].

Логично было бы предположить, что в таком случае итоговым ответом на задачу будет [math] \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} [/math], но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок: [math]E \approx \alpha \cdot (2^r)^2 \cdot I[/math]

[math]I[/math] — это индикатор, вычисляемый по формуле [math]I = (\sum\limits_{j=0}^{2^{r - 1}} \frac{1}{2^{z_j}})^{-1} [/math]
[math]\alpha[/math] — корректирующий множитель, вычисляемый по формуле [math]\alpha = (2^r  \int\limits_{0}^{\infty} (log_2{\frac{2 + u}{1 + u}})^{2^r} \,du )^{-1}[/math].

Поскольку множитель [math]\alpha[/math] может быть достаточно сложным для вычисления, можно подобрать его примерное значение в зависимости от [math]r[/math]:

[math]
 \alpha_{r}\approx\begin{cases}
 r=4 & 0.673\\
 r=5 & 0.697\\
 r=6 & 0.709\\
 r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}}
 \end{cases}
 [/math]

Число [math]E[/math] и будет итоговой оценкой мощности данного набора.

План доказательства

Определение:
Идеальным мультимножеством мощностью [math]n[/math] называется последовательность, полученная произвольными повторениями и перестановками, применяемыми к [math]n[/math] равномерно распределенным случайным величинам на действительном интервале [0, 1].


Теорема:
Пусть алгоритм HyperLogLog применяется к идеальному мультимножеству мощностью [math]n[/math] (число [math]n[/math] нам неизвестно), используя [math]reg = 2^r[/math] корзин, и пусть [math]E[/math] — полученная результирующая оценка количества различных элементов в этом мультимножестве.
  1. Оценка величины E в таком случае асимптотически почти несмещенная, а именно:
    [math] \frac{1}{n} \mathbb{E}(E) \overset{n \to \infty}{=} 1 + \delta_1(n) + o(1)[/math], где [math]|\delta_1(n)| \lt 5 \cdot 10^{-5}[/math] при [math]reg \geq 16[/math]
  2. Стандартная ошибка, равная [math]\frac{1}{n}\sqrt{\mathbb{D}_n(E)}[/math], вычисляется следующим образом:
    [math]\frac{1}{n}\sqrt{\mathbb{D}_n(E)} \overset{n \to \infty}{=} \frac{\beta_{reg}}{\sqrt{r}} + \delta_2(n) + o(1)[/math], где [math]|\delta_2(n)| \lt 5 \cdot 10^{-4}[/math] при [math]reg \geq 16[/math]

[math]\delta_1(n)[/math], [math]\delta_2(n)[/math] представляют собой осциллирующие функции с маленькой амплитудой, поддающиеся вычислению. Хотя их влияние в теории может быть компенсировано только частично, ими можно безопасно пренебречь для всех практических целей. Константа [math]\beta_{reg}[/math], в свою очередь, вычисляется следующим образом:

[math] \beta_{reg}=\begin{cases} reg=16 & 1.106\\ reg=32 & 1.070\\ reg=64 & 1.054\\ reg=126 & 1.046\\ reg\to\infty & \sqrt{3 log(2) - 1} = 1.03896 \end{cases} [/math]

Основная задача представляет оценку асимптотической зависимости величин [math]\mathbb{E}_n[/math] и [math]\mathbb{D}_n[/math] от индикатора [math]Z = \frac{1}{2^{-z_j}}[/math].

Краткий план доказательства имеет следующий вид:

  1. Сначала выводятся значение величины [math]\alpha_r[/math], которая и делает оценку [math]E[/math] асимптотически почти несмещенной, и величина стандартной ошибки.
  2. Затем производится непосредственная оценка величин [math]\mathbb{E}_n(Z)[/math] и [math]\mathbb{D}_n(Z)[/math].
  3. Поскольку значение [math]\mathbb{E}_n(Z)[/math] достаточно сложно вычислить, сначала исследуется величина [math]\mathbb{E}_{\mathcal{P}(\lambda)}(Z)[/math], то есть ситуация, когда ожидаемое значение величины [math]Z[/math] не фиксировано, а удовлетворяет закону Пуассона с некоторым параметром [math]\lambda[/math].
  4. После этого остаётся доказать, что при [math]\lambda := n[/math] поведение [math]\mathbb{E}_n(Z)[/math] и [math]\mathbb{E}_{\mathcal{P}(\lambda)}(Z)[/math] асимптотически близко.

С полным доказательством этой теоремы можно ознакомиться в оригинальной статье.

Асимптотика

Оценка времени работы: [math]\mathcal{O}(n)[/math], где [math]n[/math] — количество элементов в исходном наборе.

Оценка дополнительной памяти: [math]\mathcal{O}(2^r \cdot log_2 log_2 n) [/math].

Практические оптимизации

Полученное при помощи алгоритма HyperLogLog значение [math]E[/math] может оказаться неточным и нуждается в корректировке:

  • При [math]E \leq \frac{5}{2}2^r[/math] в оценке могут появляться нелинейные искажения, которые необходимо скорректировать. Вычислим количество [math]z_j[/math] равных [math]0[/math], обозначим эту величину за [math]V[/math]. Если [math]V = 0[/math], то уже полученное алгоритмом значение [math]E[/math] в корректировке не нуждается, иначе оно должно быть вычислено по формуле [math]E_{result} = 2^r log(\frac{2^r}{V})[/math].
  • В том случае, если значение [math]E[/math] превосходит ограничение на размер [math]z_j[/math], возрастает вероятность коллизии при хешировании и итоговая оценка также должна быть скорректирована. Рассмотрим 32-битный случай: при [math]E \gt \frac{2^{32}}{30}[/math] итоговое значение можно вычислить как [math]E_{result} = -2^{32} log(1 - \frac{E}{2^{32}})[/math].
  • В остальных случаях итоговая оценка [math]E[/math] в корректировке не нуждается.

Литература