[解決済み] Locality Sensitive Hashingを理解するには？[クローズド］

質問

LSHは、高次元の特性を持つ類似項目を見つけるのに適しているようですね。

論文を読んで http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf とはいえ、これらの数式にはまだ戸惑いがありますね。

どなたか、それを簡単に説明しているブログや記事をご存じないでしょうか？

どのように解決するのですか？

LSHのチュートリアルは、私が見た中では、この本が一番です。Mining of Massive Datasetsにあります。 第3章 - 類似アイテムの検索をチェック http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

また、以下のスライドもおすすめです。 http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . このスライドの例は、コサイン類似度に対するハッシュを理解する上でとても役に立ちました。

から2枚のスライドを拝借しています。 Benjamin Van Durme & Ashwin Lall, ACL2010 と、コサイン距離のLSH Familiesの直感を少し説明してみます。

• 図の中に、2つの円w/があります。 赤 と 黄色 の色で、2つの2次元のデータ点を表しています。私たちは、その コサイン類似度 をLSHで使用しています。
• 灰色の線は、一様にランダムに選ばれたいくつかの平面である。
• データ点が灰色の線の上にあるか下にあるかによって、この関係を0/1とマークする。
• 左上には白と黒の正方形が2列並んでおり、それぞれ2つのデータ点の署名を表している。それぞれの正方形はビット0（白）または1（黒）に対応している。
• つまり、プレーンのプールがあれば、そのプレーンに対応する位置でデータポイントをエンコードすることができるのです。プールのプレーン数が多いほど、シグネチャにエンコードされる角度差は実際の差に近くなると想像してください。なぜなら、2つの点の間に存在する平面だけが、2つのデータに異なるビット値を与えるからです。

• ここで、2つのデータ点のシグネチャを見てみましょう。例と同じく、6ビット（四角）のみで各データを表現しています。これが手持ちの元データのLSHハッシュです。
• 2つのハッシュ値のハミング距離は、署名が1ビットしか違わないので、1である。
• 署名の長さを考慮すると、グラフのように両者の角度の類似性を計算することができます。

pythonでcosine similarityを使ったサンプルコード(50行だけ)があります。 https://gist.github.com/94a3d425009be0f94751