1 定義と背景
1.1 類似性の定量化と次元の呪い
高次元空間におけるデータ間の類似性を定量化することは、情報検索や機械学習の基本的な課題である。しかし、次元が増加するにつれて、データ点間の距離が均一化する「次元の呪い」が発生し、効率的な探索が困難になる。LSHはこの問題に対処するための確率的アプローチを提供する。
1.2 ハッシュ関数の局所鋭敏性
従来のハッシュ関数は異なる入力に対して均一にバケットを割り当てることを目的とする。これに対しLSHでは、類似した入力が同じバケットに高い確率で割り当てられるようなハッシュ関数群を設計する。この性質を「局所鋭敏性」と呼ぶ。
1.3 近似最近傍探索への応用
LSHは厳密な最近傍探索を犠牲にすることで、大規模データセットにおける近似最近傍探索を実現する。計算時間を大幅に削減しつつ、高い精度を維持できる点が実用的価値を持つ。
2 数学的定式化
2.1 確率的性質とハッシュファミリー
LSHはハッシュ関数の族（ファミリー）として定義される。集合Hが(R, cR, P1, P2)-敏感であるとは、以下の条件を満たすことを意味する：
- 距離がR以下の点同士は少なくとも確率P1で衝突
- 距離がcR以上の点同士は高々確率P2で衝突
ここでP1 > P2が成立する必要がある。
2.2 距離尺度の種類
2.2.1 ユークリッド距離
ユークリッド空間では、p-安定分布を用いたハッシュ関数が典型的に使用される。各データ点に対してランダムな射影を行い、その値を量子化することでハッシュ値を生成する。
2.2.2 コサイン類似度
コサイン類似度はベクトル間の角度に基づく類似度尺度である。ランダム超平面による符号化を用いて、コサイン類似度を近似的に保存するハッシュが可能である。
2.2.3 ジャカード係数
集合間の類似度を測るジャカード係数に対しては、MinHashが効果的である。要素の最小ハッシュ値の一致確率が、元のジャカード係数と一致する性質を利用する。
2.3 パラメータ (R, c, P1, P2) の定義
Rは閾値距離、cは近似比（c>1）、P1は真陽性確率、P2は偽陽性確率を表す。適切なパラメータ選択により、探索の感度と特異度を調整する。
3 主要なLSHファミリー
3.1 MinHash
3.1.1 原理とシグネチャ生成
MinHashは集合の要素に対してランダムな順列を適用し、各順列における最小要素を抽出する。複数の独立な順列を用いて生成された最小ハッシュ値のベクトルがシグネチャとなる。
3.1.2 バンド化手法
シグネチャを複数のバンドに分割し、各バンド内で完全一致する集合を候補とする。バンド数とバンドサイズの調整により、類似度の閾値を制御できる。
3.2 E2LSH（Exact Euclidean LSH）
3.2.1 p-安定分布に基づくハッシュ
ユークリッド距離に対するLSHとして、p-安定分布（特にコーシー分布や正規分布）を用いた射影ベースの手法が代表的である。ハッシュ関数はh(x) = floor((a·x + b)/w)の形で表される。
3.2.2 複数ハッシュテーブルの併用
単一のハッシュテーブルでは十分な再現率が得られないため、複数の独立なハッシュテーブルを並列に構築し、クエリ時に全テーブルから候補を収集する。
3.3 ランダム射影法（Random Projection）
3.3.1 符号化によるコサイン類似度近似
ランダムな超平面の法線ベクトルとの内積の符号を用いて、データ点をバイナリコードに変換する。この符号化により、ハミング距離がコサイン類似度を近似する。
3.3.2 超平面分割
各ランダム超平面でデータ空間を二分し、1ビットのハッシュを生成する。複数の超平面を組み合わせることで、多ビットのハッシュコードを得る。
3.4 他の変種
3.4.1 データ依存型LSH
データ分布に基づいてハッシュ関数を学習する手法。静的なランダム射影よりも高精度な近似が可能だが、学習コストが増加する。
3.4.2 学習ベースLSH（Neural LSH）
ニューラルネットワークを用いてハッシュ関数を学習する手法。深層学習の表現力を活用し、タスクに特化したハッシュコードを生成する。
4 実装とアルゴリズム
4.1 ハッシュテーブル構築手順
- L個の独立なハッシュ関数を選択
- 各データ点に対してL個のハッシュ値を計算
- 各ハッシュ関数に対応するL個のハッシュテーブルを構築
- 各データ点を対応するバケットに格納
4.2 クエリ実行と候補照合
クエリ点に対して同様にL個のハッシュ値を計算し、各テーブルから該当バケット内のデータ点を候補として収集する。収集された候補に対して実際の距離計算を行い、最近傍を特定する。
4.3 メモリ使用量と時間計算量のトレードオフ
ハッシュテーブル数Lを増やすと再現率は向上するが、メモリ消費と候補照合のコストが増加する。バケットサイズやハッシュ関数のパラメータ調整により、精度と効率のバランスを最適化する。
5 応用例
5.1 類似文書検出（重複排除）
MinHashはWebページの重複排除や盗作検出に広く利用される。シャフリングによる文書の特徴抽出とバンド化手法により、大量の文書間の類似性を効率的に検出できる。
5.2 画像検索と類似画像発見
画像特徴量（SIFT、CNN特徴など）に対するLSHを適用することで、大規模画像データベースからの類似画像検索を実現する。近似最近傍探索により、実時間での応答が可能となる。
5.3 レコメンデーションシステム
ユーザーとアイテムの相互作用行列に対する類似度計算にLSHを応用する。協調フィルタリングにおける近傍探索を高速化し、大規模なレコメンデーションを実現する。
5.4 ゲノム配列の類似照合
生物情報学では、DNAやタンパク質の配列比較にLSHが利用される。長い配列データに対する正確なアライメントの前処理として、近似検索が効果を発揮する。
5.5 コミュニティ検出とソーシャルネットワーク分析
ソーシャルネットワークグラフにおける近接ノードの検出にLSHを適用する。大規模グラフデータでのコミュニティ抽出やリンク予測に貢献する。
6 短所と限界
6.1 近似精度とパラメータ調整の難しさ
良好な近似精度を得るためには、ハッシュ関数のパラメータやテーブル数を適切に調整する必要がある。データ分布や要求される精度に応じて試行錯誤が必要となる。
6.2 高次元データでの性能劣化
次元が非常に高い場合、ランダム射影の有効性が低下し、ハッシュの衝突確率の差が小さくなる。極端な高次元では近似精度が著しく劣化する可能性がある。
6.3 メモリ消費の問題
複数のハッシュテーブルを保持するため、メモリ消費が大きくなる。特に大規模データセットでは、ハッシュテーブルの管理に要するメモリが問題となる場合がある。
7 発展と関連技術
7.1 バイナリコード学習（Deep Hashing）
深層学習を用いて、データの特徴を直接バイナリコードに変換する手法。エンドツーエンドの学習により、タスクに特化したハッシュコードを生成し、従来のLSHを凌駕する性能を示す。
7.2 マルチプローブLSH
単一のハッシュテーブルにおいて、クエリ近傍の複数のバケットを探索する手法。複数テーブルを用いずに再現率を向上できるため、メモリ消費を抑えつつ精度を高める。
7.3 ハイブリッド手法（HNSWとの組み合わせ）
階層的ナビゲーション可能スモールワールドグラフ（HNSW）とLSHを組み合わせたハイブリッド手法。グラフベースの探索とハッシュベースの近似を融合し、大規模データにおける高速な近似最近傍探索を実現する。