Technical Note - ブルームフィルタ
概要
あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる確率的データ構造。
空間効率が非常に良いが、以下のデメリットがある。
- 偽陽性（= 実際には含まれていないのに含まれていると判定）を示す可能性がある
- データの存在判定には使えるが、元のデータを取り出すことはできない
- そのためには本体を保存する別のデータ構造と組み合わせる必要がある
仕組み
以下の図をもとに解説する。
1. 準備（フィルタの作成・初期化）
- 全ての値がゼロで初期化された、長さ $m$ のビット配列
- データ $d$ を入力として、0以上 $m-1$ 以下のハッシュ値を出力する $h$ 個のハッシュ関数 $H_1(d), H_2(d), \cdots, H_h(d)$
を用意する。図は $m=20,\ h=2$ の場合。
2. データの追加 (add)
- 追加したいデータ $d$ のハッシュ値 $H_1(d), H_2(d), \cdots, H_k(d)$ を計算
- ビット配列の $H_1(d), H_2(d), \cdots, H_k(d)$ 番目の値を0→1に変更
- 元々1だった場合は何も変えない
図の上半分は data 1〜3（$d_1, d_2, d_3$）を追加する例。
計算されたハッシュ値が
- $H_1(d_1)=6,\ H_2(d_1)=9$
- $H_1(d_2)=16,\ H_2(d_2)=2$
- $H_1(d_3)=6,\ H_2(d_3)=13$
だったので、配列の $2,6,9,13,16$ 番目の値を1に変えている。
3. データの検索 (search)
- 検索したいデータ $d$ のハッシュ値 $H_1(d), H_2(d), \cdots, H_k(d)$ を計算
- ビット配列の $H_1(d), H_2(d), \cdots, H_k(d)$ 番目の値が「全て1」だったら「存在する」と判定
図の下半分は、data 1〜3 を追加した後、data 1,4,5（$d_1, d_4, d_5$）が存在するかどうか検索する例。
- data 1：真陽性, True Positive
- 実際に存在するデータを「存在する」と判定できる
- data 4：真陰性, True Negative
- 実際に存在しないデータを「存在しない」と判定できる
- data 5：偽陽性, False Positive
- 実際には存在しないデータを「存在する」と判定してしまう
偽陽性を示す原因は、ハッシュ値の衝突（別データなのに同じハッシュ値を出力）。
しかも複数のハッシュ関数で1つの配列を共有するため、別データに対する別ハッシュ関数の値が衝突しただけでも偽陽性を示す可能性がある。
data 5 はまさにその例であり、$H_1(d_5) = H_2(d_3) = 9,\ H_2(d_5) = H_1(d_2) = 16$ という衝突が起こっている。
【NOTE】配列サイズと偽陽性
Bloom Filter の配列が密（値に1が多い）だと偽陽性の可能性が高くなるので、扱いたいデータ量に応じて、十分に疎となるような配列サイズを確保することが望ましい。
【NOTE】疑問：なぜ複数のハッシュ関数で共通の1つの配列を使うのか？
- 無駄にハッシュ値の衝突確率が上がるし、仕組みの理解が複雑にならないか？
- $h$ 個のハッシュ関数それぞれに対応する長さ $m$ の別の配列を作って、$m \times h$ 行列でフラグを立てれば良いのでは？
- 何なら、ハッシュ関数ごとに配列の長さが違っても良い
- 多少衝突確率が上がっても可能な限り空間計算量を少なくしたい、というモチベーション？
→ Appendix の $(2.4)$ までで議論している通り、フィルタに追加済みのデータ数を $n$ として $nh \ll m$ が成り立てば、偽陽性は十分小さいため問題にならない。
ただ、ハッシュ関数ごとに独立した配列を使っても、気にするほど大きな問題にはならない気がする。空間計算量的には少し非効率になるけど。
用途
前述の通り、Bloom Filter は偽陽性を示す可能性がある。
そのため、「集合内に 確実に データが存在する」という判定ではなく、「集合内にデータが存在する 可能性がある（高い）」という判定で十分に役立つようなシステムに利用される。
- Cassandra など分散 DB
- DB 内の全レコードに関する存在判定用の Bloom Filter を各サーバが持つ
- 全レコードそのものを1つのサーバが持つことは無理でも、そのハッシュ値をインデックスとする配列であれば非常にサイズを小さくでき、1つのサーバでも持てる
- 分散 DB なので、あるサーバ A がデータ $d$ について検索リクエストを受けたとき、DB 全体で見れば $d$ が存在していても、リクエストを受けた A 自身は $d$ を持っていない可能性がある
- 他のサーバ B, C, D, … に「データ $d$ を持っていますか？」という確認通信をすれば良いが、通信コストがかかる
- なのでまずは A 自身が持つ Bloom Filter を参照し、「データが存在する可能性がある」ときだけ他サーバに問い合わせて「本当に存在するかどうか？」を確認
- DB 内の全レコードに関する存在判定用の Bloom Filter を各サーバが持つ
実装
空間効率を考えるとフィルタには純粋な $m$ ビット整数を使うのが良いが、ここでは動作を理解しやすくするため $m$ 次元配列を使う。
実験
BloomFilter に登録済みの検索単語の数を変える
- 確率的にハッシュ関数の衝突が起こり、偽陽性（BloomFilter に登録されたことがない単語に対して「存在する」と判定）を示す
- 登録済み単語が非常に少ない時：BloomFIlter は疎であり、ハッシュ値の衝突が起こる頻度が非常に少ないため偽陽性率は低い
- 登録済み単語が非常に多い時：BloomFIlter が密になってしまい、未登録単語で検索しても、ハッシュ値が衝突して偽陽性を示す頻度が高い
実験コード：
フィルタのサイズを変える
- フィルタのサイズが大きいほど、ハッシュ値がとりうる値が多いので、ハッシュ値の衝突が発生しにくくなって偽陽性率が下がる
実験コード：
ハッシュ関数の個数を変える
後述の Appendix で議論する通り、フィルタサイズ $m$ と追加データ件数 $n$ を固定した場合、最も偽陽性が小さくなる最適なハッシュ値の個数 $h_\mathrm{opt}$ とそのときの偽陽性確率 $P_\mathrm{fp}(h_\mathrm{opt})$ は
\[\begin{eqnarray} h_\mathrm{opt} = \cfrac{m}{n} \log 2 \simeq 0.7 \cfrac{m}{n} \tag{3.7} \\ P_\mathrm{fp} \simeq \left( 1 - e^{-nh/m} \right)^h \tag{3.4} \end{eqnarray}\]で表される。
$m=30000,\ n=7000$ を代入すれば、
\[h_\mathrm{opt} \simeq 3,\quad P_\mathrm{fp}(h_\mathrm{opt}) \simeq \left( 1-\cfrac{1}{2} \right)^3 = 0.125\]これをシミュレーション実験で確かめてみる。
→ 理論通り、ハッシュ関数が3個のときに偽陽性率が最小となり、その値が理論値0.125に近いことが確かめられた。
実験コード：
Appendix: 偽陽性に関する議論
ハッシュ関数を1つだけ用いる場合
以下のような Bloom Filter を想定する。
- 用いるハッシュ関数の個数：$h=1$
- ビット配列の長さ（= ハッシュ値が取りうる値の個数）：$m$
- ビット配列の各要素は0で初期化し、その後 $n$ 件のデータ $d_1, \cdots, d_n$ を追加
このフィルタに対し、未追加の データ $d_{n+1}$ で検索をかける。
$d_{n+1}$ は Bloom Filter に未追加なので、「存在しない」と判定されることが望ましい。
データ1件が追加される時、$d_{n+1}$ に対応するビットが0のままである確率は
\[1 - \cfrac{1}{m} \tag{1.1}\]データ $n$ 件が追加された後、このビットが0のままである確率は
\[\left( 1 - \cfrac{1}{m} \right)^n \tag{1.2}\]検索結果が偽陽性を示す確率 $P_{\mathrm{fp}}$ は、データ $n$ 件が追加された後、このビットが1となっている確率であるから、$(1.2)$ の余事象を取って、
\[P_{\mathrm{fp}} = 1 - \left( 1 - \cfrac{1}{m} \right)^n \tag{1.3}\]ハッシュ関数を複数用いる場合
1個ではなく $h$ 個のハッシュ関数を用いる場合、$n$ 件のデータそれぞれについて $h$ 個ハッシュ値が計算される。
よって、$n$ 件のデータ $d_1, \cdots, d_n$ が Bloom Filter に追加された後、未追加のデータ $d_{n+1}$ に対してハッシュ関数の1つを適用するとき、対応するビットが1になっている確率は
$d_{n+1}$ の検索結果が偽陽性を示すのは、$h$ 個のハッシュ関数全ての計算結果に対応するビットが1になっているとき。
よってその確率 $P_\mathrm{fp}$ は
式より明らかに
- フィルタの大きさ $m$ が大きいほど偽陽性確率が小さくなる
- 追加済みデータ件数 $n$ が大きいほど偽陽性確率が大きくなる
ということがわかり、直感的な理解とも合う。
また、実用的には $\frac{1}{m} \ll 1$ であるから、テイラー展開による近似式を用いて
\[P_\mathrm{fp} \simeq \left\{ 1 - \left( 1 - \cfrac{nh}{m} \right) \right\}^h = \left(\cfrac{nh}{m}\right)^h \tag{2.3}\]したがって、$nh/m$ が十分小さい、すなわち
\[nh \ll m \tag{2.4}\]であるようなときは、偽陽性は十分小さい。
最適なハッシュ関数の個数
使用するハッシュ関数の個数 $h$ は、多ければ良いというものではない。
- $h$ が小さすぎるとき：別のデータ同士でハッシュ値が衝突する可能性が高くなる
- $h$ が大きすぎるとき：BloomFilter のビット配列が密になってしまい、何を検索てもヒットするようになる
ビット長 $m$、追加済みデータ件数 $n$ は固定として、偽陽性確率 $P_{\mathrm{fp}}$ を最小にするような最適なハッシュ関数の個数 $h_{\mathrm{opt}}$ を求めたい（opt = optimized）。
そのためには \(\cfrac{\partial P_{fp}}{\partial h} = 0 \tag{3.1}\)
を解けば良い。
$(2.2)$ を真面目に微分するのは大変なので、近似式を用いる。
ネイピア数（自然対数の底） $e$ の定義式の1つである
より、ビット配列の大きさ $m$ が1に比べて十分大きければ、
\[\left( 1 - \cfrac{1}{m} \right)^{nh} = \left\{ \left( 1 + \cfrac{1}{-m} \right)^{(-m)} \right\}^{-nh/m} \simeq e^{-nh/m} \tag{3.3}\]よって
\[P_\mathrm{fp} \simeq \left( 1 - e^{-nh/m} \right)^h \tag{3.4}\]両辺で対数を取って、
\[\log P_\mathrm{fp} \simeq h \log \left( 1 - e^{-nh/m} \right)\]これを $h$ で微分すれば、
\[\cfrac{1}{P_\mathrm{fp}} \cfrac{\partial P_{fp}}{\partial h} \simeq \log \left( 1 - e^{-nh/m} \right) + h \cfrac{n}{m} e^{-nh/m} \cfrac{1}{1 - e^{-nh/m}} \tag{3.5}\]$(2.2)$ から明らかに $P_\mathrm{fp} \ne 0$ なので、$(3.5)$ に $(3.1)$ を代入して式変形すると、
\[-\cfrac{nh}{m} e^{-nh/m} = \left( 1 - e^{-nh/m} \right) \log \left( 1 - e^{-nh/m} \right)\]$x := e^{-nh/m}$ とおけば、
\[x \log x = (1-x) \log (1-x) \tag{3.6}\]$m,n,h \ge 1$ より $0 \lt x \lt 1$ であり、この範囲における $(3.6)$ の明らかな解は $x = 1/2$。
以下のグラフより他の解は存在しない（数学的に厳密な証明は省略）
import numpy as np
from matplotlib import pyplot as plt
x = np.linspace(0.001, 0.999, 999)
y1 = x * np.log(x)
y2 = (1-x) * np.log(1-x)
plt.xlabel('$x$')
plt.ylabel('$y$')
plt.plot(x, y1, label=r'$y=x\log x$')
plt.plot(x, y2, label=r'$y=(1-x)\log (1-x)$')
plt.grid()
plt.legend()
plt.show()
よって $h = h_\mathrm{opt}$ においては
\[x = e^{-nh/m} = \cfrac{1}{2}\]となり、これを解くと
\[h_\mathrm{opt} = \cfrac{m}{n} \log 2 \simeq 0.7 \cfrac{m}{n} \tag{3.7}\]が求まる。
$m,n$ 個別の値ではなく、それらの比 $m/n$ によって最適な $h$ が一意に定まる ことが分かる。
【NOTE】
正確に言うと、$h_\mathrm{opt}$ はハッシュ値の個数であるから整数。
→ $(3.7)$ を計算して最も近い整数を $h_\mathrm{opt}$ とすれば良い。
【NOTE】(2.3) の厳密解
$(2.2)$ の対数を取った式
\[\log P_\mathrm{fp} = h \log \left\{ 1 - \left( 1 - \cfrac{1}{m} \right)^{nh} \right\}\]の両辺を $h$ で微分して、
\[\cfrac{1}{P_\mathrm{fp}} \cfrac{\partial P_{fp}}{\partial h} = \log \left\{ 1 - \left( 1 - \cfrac{1}{m} \right)^{nh} \right\} - h \cfrac{1}{1 - \left( 1 - \frac{1}{m} \right)^{nh}} \cdot \left( 1 - \cfrac{1}{m} \right)^{nh} \log \left( 1 - \cfrac{1}{m} \right)^n\]左辺をゼロとおいて変形すると、
\[\left( 1 - \cfrac{1}{m} \right)^{nh} \log \left( 1 - \cfrac{1}{m} \right)^{nh} = \left\{ 1 - \left( 1 - \cfrac{1}{m} \right)^{nh} \right\} \log \left\{ 1 - \left( 1 - \cfrac{1}{m} \right)^{nh} \right\}\]ここで
\[x' := \left( 1 - \cfrac{1}{m} \right)^{nh}\]とおけば、
\[x' \log x' = (1-x') \log (1-x')\]近似したときと同様に、$m,n,h \ge 1$ より $0 \lt x’ \lt 1$ であり、この範囲における明らかな解は $x’ = 1/2$。
\[x' = \left( 1 - \cfrac{1}{m} \right)^{nh} = \cfrac{1}{2}\]これを解けば、
\[h_\mathrm{opt} = \cfrac{1}{n} \cfrac{\log(1/2)}{\log{(1 - \frac{1}{m})}} \tag{3.8}\]これが求める厳密解となる。
\[\log \left( 1 + x \right) \simeq \log (1+0) + \cfrac{1}{1!} \cfrac{1}{1+0} x = x \qquad \mathrm{if}\quad |x| \ll 1\]
ここで初めて、$\frac{1}{m} \ll 1$ として分母にテイラー展開による近似を適用すると、
\[h_\mathrm{opt} \simeq \cfrac{1}{n} \cfrac{\log(1/2)}{-1/m} = \cfrac{m}{n} \log 2\]となり、$(3.7)$ に一致する。