LSHまとめ(1)

ここ10日間研究室にとまったおかげで，
LSHとその周辺についていろいろとわかった．
ネットサーフィンならぬ文献サーフィンをしていたので，
一度ここで整理しておく．

Locality-Sensitive Hashing

LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ．

近似最近傍探索とは，簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること．
つまり，半径(1+ε)の点のうち，どれか1つでも探索できればおｋ．
言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる．
（実は，特徴ベクトルの次元がd=2の場合なら，ボロノイ図を使えば近似最近傍探索ができる）

LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く．
そう，実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある．（これが自分にとってはかなりやっかいな問題）
LSHでは，クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く，
クエリqと遠い位置にある点ではハッシュ値が一致する確率が低くなるようなハッシュ関数を定める．
各点の特徴ベクトルを入力として，ハッシュ関数から得られたハッシュ値に対し，
ハッシュ値が等しいものを同じバケットに格納する．
これにより，近傍にある（可能性の高い）データ同士の集合が生成される．
クエリqが含まれるバケットを探索することで，近似最近傍探索が実現される．

以上よりLSHメリット・デメリットは以下のようになる．
メリット：
・2点間の距離を算出をしない　→　高速な探索が可能
・クエリの数，つーかクエリの有無に関係なく近傍探索のコストは同じ．

デメリット：
・確率的探索　→　精度に問題
・精度に限界がある

2つ目のメリットはでかい．
バケット=クラスタと考えれば，ある意味LSH自体がクラスタリングをしているといっても過言ではない．
でも，実際にはバケット=クラスタとすることができない．
それは，バケットがあくまでも確率的に可能性が高いとしか言えないから．
うーん，なんとも歯がゆい感じ．

そもそも，なぜ確率に頼るのか．
それは，ハッシュを使っているから．
この考え方だと，ハッシュ値が一致したものしか同じバケットに格納されない．
だから，確率的に変動させておかないと，まったく同じ特徴ベクトルのものしか格納されないことになる．

最初に提案されたのは，
"Approximate Nearest Neighbors : Towards Removing the Curse of Dimensionality"(P.Indyk et al, 1998)
でも，LSHは全体の手法の一部としか紹介されおらず，
具体的なハッシュ関数の定義が書いていない．
というか，実験すらしてないΣ(ﾟдﾟ)
なので，理論だけ．
ときどき，(A.Gionis et al, 1999)をrefしてる文献があったけど，
それは正確ではない．
そっちは，具体的にハッシュ関数を定めたやつ．(最初，どっちがどっちだかわからずこまった)

LSHのハッシュ関数

LSHでは特徴ベクトルをどんな距離空間で比較するかによってハッシュ関数を定める．
自分が確認したの以下のようなもの．
・L1距離(Hamming Space)
定義・証明：
"Similarity Search in High Dimensions via Hashing"(A.Gionis et al, 1999)

・Lp距離
安定分布を用いることでLp空間に対応．
定義・証明：
"Locality-Sensitive Hashing Scheme Based on p-Stable Distributions"(M.Datar et al, 2005)

・Jaccard係数
Min-wise Independent Family(最小値独立変換族)に属する順列(Permutation)を用いることでJaccard係数に対応．
のちにMinHashと呼ばれたりする．
理論の元：
"Syntactic clustering of the Web"(A.Z.Border et al, 1997)
Min-wise Independent Familyの定義等：
"Min-wise Independent Permutations"(A.Z.Border et al, 1998)
Min-wise Independent Familyからハッシュ関数への証明：
"A small approximately min-wise independent family of hash functions"(P.Indyk, 1999)

・Cosine尺度(Earth Mover Distance:EMD)
定義・証明：
"Similarity Estimation Techniques from Rounding Algorithms"(M.S.Charikar, 2002)