Bloom filter の気持ち - アスペ日記

Bloom filter について書いてみる。
実装例についてはBloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー等があるので、ここでは「気持ち」中心に。

前提:ハッシュ関数と key-value store の知識
注意:途中、説明のために実際の Bloom filter とは違う実装を導入している。

次の 4点はお互いに関連しているため、適当に混ぜながら書く。

1. Bloom filter でできることはどういうことか
2. Bloom filter はどのように実装されているのか
3. Bloom filter はどのような計算量的特性を持っているか
4. Bloom filter を使うと、どういう時にうれしいか

まず、「Bloom filter でできることはどういうことか」について、key-value store (KVS) , set との違いという観点から。

KVS では、キーと関連付けて、「値」を記録する。
Bloom filter では、キーと関連付けて、値の「存在」を記録する。
KVS では "cat":"neko", "dog":"inu" というキー・値ペアを保存できるのに対し、Bloom filter では "cat", "dog" というキーが存在することしか記録しない。
つまり、集合のようなもの。

しかし、Bloom filter にクエリを投げても、その結果は信用できるとは限らない。
存在するキーでクエリを投げると必ず Yes と返ってくる。
存在しないキーの場合、No が返ってきたり Yes が返ってきたりする。
つまり、"No" が返ってきたら存在しないことが確定だが、"Yes" が返ってきても存在するとは限らない。

さて、このように癖のあるデータ構造となると、「どういう時にうれしいか」という問題になる。
それは「どのような計算量的特性を持っているか」に関わってくる。
また、その理解には「どのように実装されているのか」から入るのがいい。

Bloom filter の基礎となるような実装を例に挙げる。
英単語 50個について、その「存在」を記録したいとする。
ハッシュテーブルであれば、適当なポインタ配列を用意し、それぞれの単語についてハッシュ値を求め、それに対応する場所に値をセットし、重複があればリストでつないで…とするところ。
ここではその代わりに、適当なビットフィールドを用意し、それぞれの単語についてハッシュ値を求め、そのハッシュ値に対応するビットを立てるだけ、という方法を考える。
重複は無視。元々のビットが 1であった場合、この操作は何の効果ももたらさない。
ビットフィールドのサイズは、全部の要素に対してビットを立てた時にだいたい半分のビットが立っているぐらいにする。
要素が 50個なら 70ビットぐらい（重複を考えると、70個のビットに対して適当に 50回ぐらいビットを立てた時にだいたい 35ビットぐらい立っている状態になる）。
クエリ時には、クエリ文字列のハッシュ値を求め、ビットフィールドの中でそのハッシュ値に対応するビットを返す。
こうすると、70ビット(9バイト)の領域で、50個の単語に対して、単語が存在する時は必ず 1を・存在しない時は 0か 1を半々ぐらいの確率で返すようなデータ構造ができる。

この例ではあまりにも規模が小さすぎて、ありがたみが伝わりにくいと思う。
そこで、もっと大規模なタスクを考える。

例えば、日本語のかな漢字変換の場合、共起情報というものを調べたいということがある。
「きかんとのこうしょう」というような文を変換する時、「機関」と「交渉」に共起関係があるということが分かれば、それらのペアが有利になるようにしたいというのは自然なこと。
それを実現するのは簡単で、文書の中で出てきたペアについて、二つの単語を文字コードの若い順にデリミタでつなげたものをキーとして、出現回数を値とするような KVS を使えばいい。
この時、例えば単語数が 100万であれば、可能なペアはその 2乗の 1兆ペアということになるのだが、実際にはその中のごくわずかしか記録しないことになる。
出現頻度の偏りや文書数の問題でそもそも共起情報が取れるペアが少ないということもあるし、適当な基準で足切りしたりもする。
結局、可能なペア 1兆に対し、共起情報を記録するペアは 1万であったり 10万であったりするが、いずれにせよとてもスパースなものになる。
ここでは 10万ペアとする。

ここで再び「きかんとのこうしょう」という文を変換するというタスクに戻り、共起情報の辞書を参照することを考える。
問題となるのが同音異義語。
「きかん」といっても機関・期間・帰還・器官・旗艦…と数十個の候補があり、「こうしょう」といっても交渉・考証・公称・公証・校章…と数十個の候補がある。
これら同士のペアについて共起関係を調べるとなると、数十×数十ということで、千ぐらいのオーダーになってしまう。
しかし、それらのほとんどは、上記のスパースネスにより、共起辞書には載っていない無駄なクエリ（以下「駄クエリ」）になる。

さらに、切り方の問題もある。
「きかんとのこうしょう」は、「きかん/と/の/こうしょう」と切れば、助詞以外の単語は 2つしか出てこないが、「き/かん/と/の/こう/しょう」といった切り方も考えられる。
そうすると、調べるペアは一気に増える。
また、ここでは短い文を例に出しているが、実際の文はもちろんずっと長いものもありうる。
例えば、20単語の文であれば、単語同士の組み合わせは 200ぐらいになる。
上の同音異義語の問題、切り方の問題と合わせると、クエリ回数は平気で 100万といったオーダーになる。
それらのほとんどは共起辞書に載っていない駄クエリなのに。
KVS さんかわいそうです。

ここで出てくるのが、さっきのビットフィールド。
例えば、記録する共起が 10万ペアであれば、15万ビットぐらいのビットフィールドを用意して、それぞれのペアに対してハッシュ値を出してビットを立てれば、半分ぐらいのビットが立つことになる。
単語ペアに対して共起辞書を参照する前に、まずこちらのビットフィールドにビットが立っているかどうかを確認することにする。
こうすると、共起辞書にある場合には必ずビットが立っているが、共起辞書にないペアの場合は、半分ぐらいの確率で 0が返ってくる。
0 が返ってきたら KVS を見に行かないでいいということ。

このビットフィールドに必要な領域は、15万ビット≒2万バイト≒20KB=ただ同然。
クエリごとの CPU 時間は、ハッシュ値計算+ビットフィールド参照=ただ同然。
ただ同然のコストで、駄クエリを半分に減らせた！
うれしい！

しかし、半分ではいかにも手ぬるい。
全ての駄クエリを消し去りたい。

「全ての」とはいかないが、フィルタリング性能を上げるのには非常に単純な方法がある。
同じ大きさのビットフィールドをもう一つ用意して、そちらには別のハッシュ関数でビットを立てることにする。
そうすると、辞書にあるクエリは必ず両方のフィルタを通過するが、駄クエリはそれぞれのフィルタを 1/2 の確率でしか通れない。
駄クエリは 1/4 になる。

あとは単純で、駄クエリをどれだけ減らしたいかに応じて、ビットフィールドとハッシュ関数を増やせばいい。
例えば、1/65536 に減らしたければ、ビットフィールド 16個、ハッシュ関数 16個。
必要な領域は、15万ビット×16≒300KB=ただ同然。
クエリごとの CPU 時間は、(ハッシュ値計算+ビットフィールド参照)×16=ただ同然。
ただ同然のコストで、駄クエリが 1/65536 に減らせた！
うれしい！

ここで、「全ての駄クエリを消し去りたい」というところに戻ってみる。
考えてみると、そこまでする必要はない。
理由は二つある。

一つ目は、トレードオフの問題。
フィルタを一つ追加するたびに、その分ハッシュ計算とビットフィールド参照のコストが増える。
それによって減らせる KVS 検索よりも、フィルタリングのコストが上回っては意味がない。

二つ目は、ボトルネックがどこかということ。
クエリの中には、結果が返ってくる、無駄じゃないクエリもある（当たり前）。
100万回のクエリの中に、例えば 10回ぐらい無駄じゃないクエリがあるとしたら、駄クエリの回数を 10回よりずっと少なくすることにはあまり意味がない。

これらを考慮に入れて、必要なフィルタリング精度を見積もる必要がある。

また、例を見ればわかるように、フィルタリング精度を上げようと思うとフィルタを増やさなければいけないのだが、一つ一つのフィルタを 1/2 よりもスパースにすることで、メモリ効率と引き換えにフィルタリングの回数を少し節約できる。
この辺りの調整もさじ加減で。

ここまで、説明のために本物の Bloom filter とはちょっと違う実装を使った。
上では、例えば駄クエリ通過確率を 1/4　にしたい時に、ビットフィールドとそれにマップするハッシュ関数を 2セット用意するということにしている。
しかし、実際の Bloom filter では、2倍のサイズのビットフィールドを 1個用意して、ハッシュ関数はその大きなビットフィールド全体にマップするものを 2個用意するというようにする。
ビットフィールドの密度はどちらでも近似的には同じなのだが、ビットフィールドが 1つにまとまっているほうが取り回しが楽。
Bloom filter の具体的な計算量・フィルタリング効率等は Wikipedia に載っているはずなので、パラメータを決める際にはその式を参考にしてください。

Bloom filter を使うとうれしいのは、上の例のように "KVS に駄クエリを投げまくらないといけない時"。
KVS を駄クエリから守ってくれます。

http://d.hatena.ne.jp/nokuno/20110327/1301179927で紹介されているように、Google 日本語入力のオープンソース版 mozc では共起情報を利用していて、その中で Bloom filter を使っている（ここでは KVS との組み合わせではなく、低コストの set として）。
ソースは http://code.google.com/p/mozc/source/browse/trunk/src/storage/existence_filter.cc　のあたり。

ちなみに、ビットフィールドを複数用意するというナイーブな実装は、以前の会社で IME を開発していた時、似たような必要に迫られて自分で考えたもの。
結果的には、Bloom filter という、より洗練されたものが存在していたので車輪の再発明だったけど、友達に教える時に途中段階として使ったら好評だったので、ここでも活用してみた。