Mastering Bitcoin の読書会をやっていました。読み直す度に新しい発見があるのがこの本であり Bitcoin の技術でして、その中で Bloom Filter についての話題があります。
Bloom Filter というのは確率的アルゴリズムの一つです。このエントリでは、 Bloom Filter とはどういうものか、そしてその数理はどうなるのかを記述したいと思います。
Bloom Filter の特徴
まず Bloom Filter というのは確率的アルゴリズムの一つでして、「ある要素 $e$ が、$n$ 個からなるデータ集合の中に含まれているか否か」という命題に答えるために使われます。
この命題を解くための一番直感的な方法は、$n$ 個のデータからなる集合を作った後で、要素 $e$ がその集合に入っているかどうかを先頭から見に行くという方法だと思います。この方法の時間計算量は $O(n)$ ということになるでしょう。
もちろん要素を予めソートできれば、二分探索を用いて $O(\log{n})$ にすることができます。しかし、どうやってもオーダーに $n$ という数がでてくる、つまりは、集合内のデータ数 $n$ に依存してしまうことは避けられません。
しかし、Bloom Filter を使うと、命題に回答するための時間計算量は $O(k)$ になります。 $k$ ってなんだ?
なんと $k$ は定数です。つまり、データ数 $n$ に依らず、定数オーダーで判定が可能になるという夢のアルゴリズムが Bloom Filter ということです。
Bloom Filter の欠点
もちろん、このようなメリットがノーリスクで得られるはずはありません。
Bloom Filter の弱点、それは false positive が発生する可能性があることです。もうすこし詳しく言うと、
- Bloom Filter が「その要素は集合に含まれていない」と判断するとき、それは 100 % 間違わない (false negative は起こらない)
- Bloom Filter が「その要素は集合に含まれている」と判断するとき、それは間違ってしまう可能性がある (false positive が起こり得る)
つまり、「その要素が集合に含まれている」と判断したとき、実際にはその判断が間違っている可能性があるということです。
ただし、その false positive の発生確率はパラメータで制御可能であるというのが本エントリの主題です。
Bloom Filter の仕組み
この資料が非常にわかりやすいので、それを見ていただくのが一番かなと思います。
要するに、
- 準備
- $k$ 個のハッシュ関数 $h_1, h_2, \cdots, h_k$、および、$m$ 個の要素を持つ配列を用意する。配列の要素はすべて $0$ に初期化しておく。
- 集合に含めるデータ $e_i$ について、各ハッシュ値 $h_1(e_i), h_2(e_i), \cdots, h_k(e_i)$ に該当する配列の要素を $1$ にする
- 判定
3. 判定対象のデータ $d$ について各ハッシュ値 $h_1(d), h_2(d), \cdots, h_k(d)$ を計算し、その値に該当する配列の要素全てが $1$ だった場合にのみ、「$d$ は集合に含まれている」と回答する。それ以外は「 $d$ は集合に含まれていない」と回答する。
というデータ構造・アルゴリズムになっています。
false positive の発生確率は?
false positive の発生確率の導出)については ブルームフィルタ を読めば良いんですが、一応ここでも記載しておきます。
1. 任意の配列要素が 1 になっている確率
長さ $m$ の配列の任意の要素 $ｍ[i]$ を考えます。
1 個のデータを集合に格納するときに当該の要素 $m[i]$ が 0 のままの確率は、$\left(1-\frac{1}{m}\right)^{k}$ になります。なんでかっていうと、1 個のハッシュ関数によって 1 に更新される確率は $\frac{1}{m}$ であり、ハッシュ関数は $k$ 個あるわけだからですね。
このため、$n$ 個の要素を集合に格納した状態で任意の要素 $i$ が 0 のままの確率は $\left(1-\frac{1}{m}\right)^{kn}$ であり、1 になっている確率はこの背反事象ですから $1-\left(1-\frac{1}{m}\right)^{kn}$ ということになります。
false positive の確率
Bloom Filter でいう false positive は、「データ集合に含まれないデータ $d$ であるにも関わらず、$k$ 個のハッシュ値 $h_1(d), h_2(d), \cdots, h_k(d)$ に対応する配列の要素がすべて $1$ になっている」ということを意味します。false positive の確率は、このような事象が発生する確率を求めれば良い。
先の議論で、配列の任意の要素が $1$ になっている確率は $1-\left(1-\frac{1}{m}\right)^{kn}$ ですから、これが $k$ 回発生すれば false positive のできあがりです。この発生確率は $\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^{k}$ になります。
false positive の近似式
ちょっと扱いづらい数式ですから、近似しましょう。
指数関数のテイラー展開を思い出すと、$e^{x} \approx 1+x$ です。この指数関数のテイラー展開を利用すると、$e^{-\frac{1}{m}}\approx 1-\frac{1}{m}$ ですから、先の式は $p=\left(1-e^{-\frac{n}{m}k}\right)^{k}$ と近似できます。ずいぶん扱いやすい式になりました。
ここまでが ブルームフィルタ で解説されている内容です。
false positive を最小にするハッシュ関数の数 k は?
ここからは Bloom Filter の内容です。
false positive の発生確率は制御可能と書きましたが、まずは false positive の発生確率を最小にするハッシュ関数の数 $k$ を求めてみましょう。
false positive の発生確率を $p$ とすると、その式は $p=\left(1-e^{-\frac{n}{m}k}\right)^{k}$ でした。これを対数関数の知識で変形すると $p=\exp \left( \ln\left( 1-e^{-\frac{n}{m}k} \right)^{k} \right)=\exp\left(k \ln\left( 1-e^{-\frac{n}{m}k} \right)\right)$ になります。この指数関数のとる値を最小にするためには、肩に乗っている指数部 $f=k \ln\left( 1-e^{-\frac{n}{m}k} \right)$ を最小にすれば良い。そして $f$ を最小にするための $k$ を求めるには、偏微分 $\frac{\partial f}{\partial k}=0$ を $k$ について解けば良いということになります。
ここまで来て、解くべき式は、$\frac{\partial f}{\partial k}=\ln\left( 1-e^{-\frac{n}{m}k} \right)+\frac{n}{m}k\frac{e^{-\frac{n}{m}k}}{1-e^{-\frac{n}{m}k}}=0$ となりました。
ここで、変数置換を行います。 $y=e^{-\frac{n}{m}k}$ と置くと、 $k=-\frac{m}{n}\ln\left(y\right)$ になります。この $k$ の式を先の式に代入すると、
$\ln(1-y)-\frac{y \ln\left(y\right)}{1-y} = 0$、もうちょっと分かりやすくすると、$(1-y)\ln(1-y)=y\ln y$ です。
この式を成立させるためには、$y=e^{-\frac{n}{m}k}=\frac{1}{2}$ でなければならないのは自明でしょう。これを $k$ について解くと、$k=\frac{m}{n}\ln 2$ であることが導けます。つまりは、この ハッシュ関数を $k=\frac{m}{n}\ln 2$ 個だけ用意するのが、Bloom Filter にとって一番誤りが少なくなるということになります。 $n$ は格納したデータの個数、 $m$ は配列の長さですから、これらを事前に見繕っておけば誤る確率の最小化が可能ということになります。
最適な数のハッシュ関数を用意したときの false positive の発生確率は?
$p=\left(1-e^{-\frac{n}{m}k}\right)^{k}$ の式に、先ほど求めた $k=\frac{m}{n}\ln 2$ を代入してみれば、最適な false positive の発生確率が求められます。この結果は、$p=\left(\frac{1}{2}\right)^{\frac{m}{n}\ln 2}$ になります。
実はパラメータ m, n, k は false positive の発生確率 p で決定できる
$k=\frac{m}{n}\ln 2$ のとき、$p=\left(\frac{1}{2}\right)^{\frac{m}{n}\ln 2}$ が得られることが分かりました。
ここで、この式を $\frac{m}{n}$ について解くと、おもしろいことに $\frac{m}{n}=-\frac{\ln p}{\left(\ln 2\right)^{2}}=-\frac{\log_{2}p}{\ln 2}$ が導けます。
さらに、これを $k=\frac{m}{n}\ln 2$ の式に代入すると、最適なハッシュ関数の数は $k=-\log_2{p}$ とも表現できます。
つまりハッシュ関数の数が、false positive の確率 $p$ にのみ依存することが分かります。すごくおもしろい特性ですね。