Locality-sensitive hashing

Goal: Find documents with Jaccard similarity at least t

LSHの一般概念は、もし2文書の署名を入力したら、その2文書が候補ペアになるかどうか、つまりそれらの類似性が閾値tより大きくなったかを伝えるアルゴリズムを見つけることである。 ここでは、署名の類似度を、元の文書間のJaccard類似度の代理としていることに注意。

特にmin-hash署名行列の場合：

• 複数のハッシュ関数を用いて署名行列Mの列をハッシュする
• もし2文書が少なくとも一つのハッシュ関数で同じバケットにハッシュすれば、2文書を候補ペアとする

さて問題は異なるハッシュ関数にどうするかということである。 これにはバンドパーティションを行う。

Band partition

これがそのアルゴリズムである。

• 署名行列をbバンドに分割し、各バンドはr行を持つ
• 各バンドについて。 k個のバケットを持つハッシュテーブルに各列の一部をハッシュする
• 候補となる列のペアは、少なくとも1バンドで同じバケットにハッシュするもの
• bとrは、最も似ているが非類似ペアは少ないペアを捕まえるように調整する

ここでいくつか考慮すべき点がある。 理想的には、各バンドにおいて、kはバンド内で列が取り得る値のすべての可能な組み合わせに等しくなるようにしたいものです。 これは同一性マッチングと同等になります。 しかし、この方法ではkは膨大な数になり、計算上実行不可能である。 例えば、あるバンドに5つの行があるとする。 署名の要素が32ビット整数である場合、この場合のkは(2³²)⁵ ~ 1.4615016e+48となる。 何が問題かはおわかりいただけると思います。

このアイデアは、2つの文書が類似していれば、少なくとも1つのバンドで候補ペアとして表示されるというものです。

bの選択 & r

bを大きく、すなわちハッシュ関数数を多くすると、b*rが定数となりrが小さくなります（署名行列の列の数）。 直感的には、候補ペアが見つかる確率が高くなることを意味します。 この場合、t（類似度閾値）を小さくすることと等価である

署名行列が100行あるとする。

b1 = 10 → r = 10

b2 = 20 → r = 5

2番目のケースでは、より多くの機会があり（20対10）、比較される署名の要素が少ない（5対10）ため、少なくとも一度は同じバケットに2文書が現れる確率が高くなります。

b が高いほど類似度閾値が低く（偽陽性が高い）、b が低いほど類似度閾値が高い（偽陰性が高い）。

セットアップ：

• 100k documents stored as signature of length 100
• Signature matrix: 100*100000
• 署名をブルートフォースで比較すると、100C2比較=50億回（かなり多い！）
• b=20とする→r=5

類似度閾値（t） : 80%

20バンドのうち少なくとも1バンドで類似度80%の2文書（D1 & D2）が同一バケットにハッシュされればいいのです。

P(D1 & D2 identical in a particular band) = (0.8)⁵ = 0.328

P(D1 & D2 are not similar in all 20 bands) = (1-0.328)^20 = 0.00035

つまりこのシナリオで我々は〜.となるわけです。035% の確率で 80% の類似文書が偽陰性となります。

また、類似度 30% の 2 つの文書 (D3 & D4) が、20 のバンドのいずれでも同じバケットにハッシュされないようにします（閾値 = 80%）。

P (D3 & D4 同一バンドで) = (0.3)⁵ = 0.00243

P(D3 & D4 are similar in at least one of the 20 bands) = 1 – (1-0.00243)^20 = 0.0474

このシナリオでは、類似文書30％で偽陽性になる可能性は4.74％ということになります。 これらの割合は、bとrの選択によって変化します。

ここで欲しいのは、以下のようなものです。 もし、閾値以上の類似性を持つ2つの文書があれば、少なくとも1つのバンドで同じバケットを共有する確率は1でなければ0になるはずです。

最悪のケースは、以下のようにb = signature matrixの行数としている場合である。

任意のbとrについて一般化すると、以下のようになります。

最高のSカーブを得るためにbとrを選択する。e minimum false negative and false positive rate

LSH summary

• Tune M、b, rは、類似した署名を持つほぼすべてのドキュメントペアを取得するが、類似した署名を持たないペアのほとんどを削除する
• メインメモリで候補ペアが本当に類似した署名を持っているかチェックする

。