8

現在、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）かかります!!!

4

1 に答える 1

8

最初のものに対するあなたの理解は少しずれています。衝突が発生する確率は、類似度に比例するのではなく、事前に定義された半径よりも小さいかどうかに関係ありません。目標は、半径内にあるものは衝突する可能性が高く、半径 * (1+eps) の外側にあるものは衝突する可能性が低くなります (その間の領域は少し暗くなります)。

最初のアルゴリズムは、実際にはうまく実装するのがかなり難しいですが、良い結果を得ることができます。特に、最初のアルゴリズムは、L1 および L2 (および技術的にはさらにいくつか) メトリック用です。

2 番目のアルゴリズムは実装が非常に簡単ですが、問題のサイズによっては、素朴な実装ではメモリを使いすぎて役に立たない場合があります。この場合、衝突の確率は入力の類似性に比例します。ただし、コサイン類似度 (または類似度の変換に基づく距離メトリック) に対してのみ機能します。

したがって、どちらを使用するかは、主に、最近傍 (またはその他のアプリケーション) に使用している距離メトリックに基づいています。

2 番目のものは、実際には最初のものよりも理解しやすく、実装するのがはるかに簡単です。論文は非常に冗長です。

短いバージョン: ランダム ベクトル V を取り、各インデックスに独立したランダム ユニットの正規値を与えます。署名の長さが必要な数のベクトルを作成します。シグネチャは、Matrix Vector 積を実行するときの各インデックスの符号です。これで、任意の 2 つのシグネチャ間のハミング距離は、それぞれのデータ ポイント間のコサイン類似度に関連付けられます。

署名を int 配列にエンコードし、ビット カウント命令で XOR を使用してハミング距離を非常に迅速に取得できるため、おおよそのコサイン類似度スコアを非常に迅速に取得できます。

LSH アルゴリズムには多くの標準化がなく、2 つの論文 (およびその他) は異なる定義を使用しているため、少し混乱することがあります。これらのアルゴリズムをJSATに実装したのはつい最近のことですが、まだ両方を完全に理解するために取り組んでいます。

編集: あなたの編集に返信します。ウィキペディアの記事は LSH には適していません。元の論文を読んだ場合、あなたが話している最初の方法は固定半径でのみ機能します。次に、その半径に基づいてハッシュ関数が作成され、連結されて、衝突でポイントに近づく可能性が高くなります。次に、k の最大値を決定することにより、これに加えて k-NN を実行するためのシステムを構築し、k 番目の最近傍を見つけることができる最大の妥当な距離を見つけます。このようにして、半径検索k-NNのセットを返す可能性が非常に高いです。これを高速化するために、密度が均一でないことが多いため、いくつかの非常に小さな半径も作成します。使用する半径が小さいほど、結果が速くなります。

リンクしたウィキペディアのセクションは、半径r = 1の検索のハッシュ関数を示す「安定した分布」セクションの論文の説明から取られています。

2番目の論文では、あなたが説明する「ソート」はハッシュの一部ではなく、ハミング空間をより迅速に検索するための1つのスキームの一部です。私が述べたように、私は最近これを実装しました。ブルートフォース検索を使用して行った簡単なベンチマークは、NN の単純な方法よりもはるかに高速であることがわかります。繰り返しになりますが、L2 または L1 距離でのコサイン類似度が必要な場合も、この方法を選択します。署名によって作成されたハミング空間を検索するためのさまざまなスキームを提案している他の多くの論文を見つけることができます。

助けが必要な場合は、ブルート フォースを行っていたとしても、より速くフィットする可能性があります。次のように見てください。平均的なまばらなドキュメントには、別のドキュメントと共通する 40 の単語があるとしましょう (私の経験では非常に保守的な数です)。比較するドキュメントが n 個あります。力ずくのコサインの類似性には、約 40*n の浮動小数点乗算 (および追加の作業) が含まれます。1024 ビットの署名がある場合、それは 32 の整数のみです。つまり、32*n 整数演算でブルート フォース LSH 検索を実行でき、浮動小数点演算よりもかなり高速です。

ここには他の要因もあります。スパース データ セットの場合、非ゼロ インデックスを表すために倍精度インデックスと整数インデックスの両方を保持する必要があるため、スパース ドット積は、どのインデックスが共通しているかを確認するために多くの追加の整数演算を実行します。LSH を使用すると、メモリを節約することもできます。これは、ベクトルごとにこれらの整数と double をすべて格納する必要がないためです。代わりに、そのハッシュを保持するだけで済みます。これはわずか数バイトです。メモリ使用量を減らすと、CPU キャッシュをより有効に活用できます。

あなたの O(n) は、私がブログ投稿で使用した単純な方法です。そしてそれは速いです。ただし、事前にビットをソートすると、O(log(n)) でバイナリ検索を実行できます。これらのリストが L 個ある場合でも、L << n であるため、より高速になるはずです。唯一の問題は、すでに余弦類似度を近似しているハミング NN を近似するため、結果が少し悪化する可能性があることです。必要なものによって異なります。

于 2013-06-23T19:46:41.807 に答える