プロジェクトの中で、Mastering Bitcoin の読書会を進めていまして、ぼくはこの本を読むのは 3 周目になります。ただ、読み直す度に新しい発見があるのがこの本であり Bitcoin の技術でして、その中で Bloom Filter についての話題がありました。

Bloom Filter というのは一般的な確率的データ構造であり、アルゴリズムの一つですが、Bitcoin ではそのアルゴリズムの欠点をプライバシー問題を緩和するための一つとして使用していて、そのあたりの話をしたい。でも、そのためには Bloom Filter 自体に言及する必要があるかなと思いまして、このエントリは Bloom Filter とはどういうものか、そしてその数理はどうなるのかを記述したいと思います。

Bloom Filter の特徴
- Bloom Filter の欠点
Bloom Filter の仕組み
false positive の発生確率は?
false positive を最小にするハッシュ関数の数 k は?
最適な数のハッシュ関数を用意したときの false positive の発生確率は?
結論:実はパラメータ m, n, k は false positive の発生確率 p で決定できる
参考文献

Bloom Filter の特徴

まず Bloom Filter というのは確率的なデータ構造の一つでして、「ある要素が、データ集合の中に含まれているか否か」という命題に答えるために使用されます。

この命題を解くための一番直感的な方法は、 $n$ 個のデータからなる集合を作った後に要素 $e$ がその集合に入っているかどうかを先頭から見に行くという方法だと思います。この方法の時間計算量 $O(n)$ ということになるでしょう。もちろん要素を予めソートしておくことで、ソートを含まず判定だけ見ると $O(\log{n})$ になりますが、どうやってもオーダーに $n$ という数がでてくる、つまりは、集合内のデータ数に依存してしまうことは避けられません。

しかし、Bloom Filter を使うと、命題に回答するための時間計算量は $O(k)$ になります。 $k$ ってなんだ? なんと $k$ は定数です。つまり、データ集合の中に含まれるデータ数 $n$ に依らず、定数オーダーで判定が可能になるという夢のアルゴリズム、データ構造が Bloom Filter ということです!

また、いわゆる空間計算量、つまりはそのデータ構造が必要とするデータ容量もメリットです。先に述べた「直感的な方法」だと、集合の中に実データを格納することになります。たとえば、「"apple"、"banana" からなる集合に "orange" が含まれるか否か」という命題であれば、集合に "apple"、"banana" という実データを含むことになります。

しかし、Bloom Filter はデータ集合をフラグの配列で持てば良い構造になっており、空間計算量についても格段のメリットがあります。

Bloom Filter の欠点

もちろん、このようなメリットがノーリスクで得られるはずはありません。 Bloom Filter の弱点、それは false positive で間違える可能性があることです。もうすこし詳しく言うと、

Bloom Filter が「その要素は集合に含まれていない」と判断するとき、それは 100 % 間違わない (false negative は起こらない)
Bloom Filter が「その要素は集合に含まれている」と判断するとき、それは間違ってしまう可能性がある (false positive が起こり得る)
- つまりは、「その要素が集合に含まれている」と判断したとき、実際にはその要素が含まれていない可能性がある

ということです。ただし、その false positive の発生確率はパラメータで制御可能であり、実はそのパラメータはシステムが許容できる false positive 発生確率からも導出できるというのが本エントリの主題です。

Bloom Filter の仕組み

この資料がすごくわかりやすいので、それを見れば良いです。

speakerdeck.com

要するに、

準備
1. $k$ 個のハッシュ関数 $h_1, h_2, \cdots, h_k$ と $m$ 個の要素を持つ配列を用意する。配列の要素はすべて $0$ に初期化しておく。
2. 集合に含めるデータ $e_i$ について各ハッシュ値 $h_1(e_i), h_2(e_i), \cdots, h_k(e_i)$ に該当する配列の要素を $1$ にする
判定
1. 判定対象のデータ $d$ について各ハッシュ値 $h_1(d), h_2(d), \cdots, h_k(d)$ を計算し、その値に該当する配列の要素全てが $1$ だった場合にのみ、「 $d$ は集合に含まれている」と回答する。それ以外は「 $d$ は集合に含まれていない」と回答する。

というデータ構造・アルゴリズムになっています。

false positive の発生確率は?

任意の配列要素が 1 になっている確率

この節の内容 (false positive の発生確率の導出)については wikipedia:ブルームフィルタを読めば良いんですが、一応ここでも記載しておきます。

長さ $m$ を持つ配列の任意の要素 $i$ を考えたとき、1 個のデータを集合に格納するときに当該の要素 $i$ が 0 の確率は、 $\left(1-\frac{1}{m}\right)^{k}$ になります。なんでかっていうと、1 個のハッシュ関数によって 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}$ ですから、先の式は $\left(1-e^{-\frac{n}{m}k}\right)^{k}$ と近似できます。ずいぶん扱いやすい式になりました。

ここまでが wikipedia:ブルームフィルタで解説されている内容です。

false positive を最小にするハッシュ関数の数 k は?

ここからは wikipedia:en: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$ を最小にするためには $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{n}{m}\ln\left(y\right)$ になります。この $k$ の式を先の式に代入すると、 $\ln(1-y)=-\frac{y \ln\left(y\right)}{1-y}$ 、もうちょっと分かりやすくすると、 $(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$ の数だけハッシュ関数を用意するのが、Bloom Filter にとって一番 false positive が小さくなるということになります。

最適な数のハッシュ関数を用意したときの 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}$ となります。つまり、 $\frac{m}{n}$ もハッシュ関数の数も false positive の確率 $p$ にのみ依存することが分かります。すごくおもしろい特性ですね。