問題タブ [locality-sensitive-hash]

min-hashを使用してLSH（局所性鋭敏型ハッシュ）を実装する多くのチュートリアル、ドキュメント、およびコードを読みました。

LSHは、ランダムなサブセットをハッシュし、それらを集計することにより、2つのセットのJaccard係数を見つけようとします。code.google.comで実装を見てきましたが、その方法も理解できませんでした。私は紙のGoogleニュースのパーソナライズ：スケーラブルなオンライン協調フィルタリングを理解していますが、そこにある実装のいずれも理解できていません。

MinHashでLSHを実装する方法を簡単な言葉で説明してもらえますか？

互いに独立した 2 つの異なるシステムによって生成された 2 つの配列があります。配列から生成されたいくつかの数値のみを比較して、それらの類似性を比較したいと考えています。

現在、配列の最小値、最大値、および合計のみを比較していますが、より良いアルゴリズムがあるかどうか疑問に思っていましたか? どのタイプのハッシュ アルゴリズムも、配列間の浮動小数点数のわずかな違いに影響されないようにする必要があります。

編集:私がやろうとしているのは、データを直接比較することなく、2 つのアルゴリズムが同じデータを生成することを確認することです。そのため、アルゴリズムはデータの変化に敏感で、各要素間の小さな違いには比較的鈍感である必要があります。

約 1,000 万件のクエリのクエリ ログがある場合、ユーザーにクエリを要求し、入力クエリに最も類似した 10 個のクエリを出力として表示するプログラムを作成する必要があります。また、スペル ミスの場合は、正しいスペルを提案する場合があります。

このコンテキストでは、ローカリティ センシティブ ハッシュに関するいくつかのチュートリアルを調べましたが、この問題にどのように適用できるか理解できません。最初に、ログを辞書順にソートすることを考えていました。しかし、ログ全体をメモリにロードするのは効率的ではない可能性があるため、ログのサイズに関する限り、ログをソートすることはお勧めできません。

だから、誰でも私に問題に取り組むためのアイデアを提案してください。ありがとうございました。

私はこの質問を読んでいました：

Locality Sensitive Hashing を理解する方法は?

しかし、コサイン類似度を計算する式は次のとおりであることがわかりました: Cos(v1, v2) = Cos(theta) = (ハミング距離/署名の長さ) * pi = ((h/b) * pi )

つまり、ベクトルが完全に類似している場合、ハミング距離はゼロになり、コサイン値は 1 になります。しかし、ベクトルが完全に類似していない場合、ハミング距離はシグネチャの長さに等しくなるため、cos( pi) -1 になります。類似度は常に 0 と 1 の間であるべきではありませんか?

現在、Locality-sensitive ハッシュを使用して最近傍を見つける方法を研究しています。ただし、論文を読んだり Web を検索したりしているときに、これを行うための 2 つのアルゴリズムを見つけました。

1- L 個のランダム LSH 関数で L 個のハッシュ テーブルを使用すると、類似した 2 つのドキュメントが同じ署名を取得する可能性が高くなります。たとえば、2 つのドキュメントが 80% 類似している場合、1 つの LSH 関数から同じ署名を取得する可能性は 80% です。ただし、複数の LSH 関数を使用すると、LSH 関数の 1 つからドキュメントに対して同じ署名を取得する可能性が高くなります。この方法はウィキペディアで説明されており、私の理解が正しいことを願っています:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- もう 1 つのアルゴリズムは、Moses S. Charikar による Rounding Algorithms からの類似性推定手法と呼ばれる論文 (セクション 5) の方法を使用します。これは、1 つの LSH 関数を使用して署名を生成し、それに P 順列を適用してリストを並べ替えることに基づいています。実は私はその方法をよく理解していないので、誰かがそれを明確にしてくれることを願っています.

私の主な質問は、なぜ最初の方法ではなく 2 番目の方法を使用するのでしょうか? 私が見つけたように、それはより簡単で高速です。

誰かが助けてくれることを本当に願っています!!!

EDIT：実際には、@ Raff.Edwardが「最初」と「2番目」を混ぜていたかどうかはわかりません。2 番目の方法のみが半径を使用し、最初の方法はハッシュ ファミリ F で構成される新しいハッシュ ファミリ g を使用するためです。ウィキペディアのリンクを確認してください。多くの g 関数を使用してさまざまな署名を生成し、各 g 関数に対応するハッシュ テーブルを持っています。ポイントの最近傍を見つけるには、ポイントに g 関数を通過させ、対応するハッシュ テーブルの衝突をチェックするだけです。したがって、私はそれをより多くの機能として理解しました...衝突の可能性が増えました。

最初の方法の半径についての言及は見つかりませんでした。

2 番目の方法では、特徴ベクトルごとに 1 つの署名のみを生成し、それらに P 順列を適用します。これで、それぞれが n 個の署名を含む順列の P 個のリストができました。次に、P から各リストを並べ替えます。その後、クエリ ポイント q が与えられると、その署名を生成し、それに P 順列を適用してから、順列および並べ替えられた各 P リストで二分探索を使用して、最も類似した署名を見つけます。クエリq。私はそれについて多くの論文を読んだ後にこれを結論付けましたが、ハミング距離を見つけるのが速くないように見えるので、なぜ誰かがそのような方法を使用するのかまだわかりません!!!!

私にとっては、次のようにして、クエリ ポイント q の最近傍を見つけるだけです。署名のリスト N が与えられた場合、クエリ ポイント q の署名を生成し、リスト N をスキャンして、N の各要素と q の署名の間のハミング距離を計算します。したがって、q の最近傍が得られます。そして、それはO（N）かかります!!!