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)

LSHの論文

鬱です．

ゼミ前ってホントいやですね．



Imagineも大規模アップデートでいろいろと追加・変更があったので，

そろそろやりたい．

なんだかんだであまりにもブランクあけすぎた（あれｗもしかして，一ヶ月オーバー？）ので，

さっさと復帰したい．

でも，ゼミ終わるまでは無理．

というかゼミが無理ｗ

打ち合わせがもっと無理ｗ





さて，研究の話．

論文の内容の概略．

Approximate Nearest Neighbors: Towards Removing the Cures of Dimensionality

この論文で初めてLSHが提案された．たぶん．

でも，LSH主体な訳ではなく，

あくまでε-NNS(ε-approximate Nearest Neighbor Search)

を解く提案手法の一部として紹介されている．



この論文では，ε-NNSを解くために，

ring-cover treesという新しいデータ構造を用いることで高速化を可能としている．

詳細は・・・しょーじきよくわかりません（ぉぃ

まあ，でも実際これは概略さえ知ってればいいか思う．



しかしながら，ring-cover treesを構成する上でpoint location問題

を解く必要がある．

ここで，point location問題とは，queryの点が含まれている領域を探索すること．

http://www.cs.sunysb.edu/~algorith/files/point-location.shtml


で，論文では，point location問題の解法として，2つの手法を挙げており，

そのうちの片方がLSHというわけ．



あと，どうやらこの手法には次元の削減にramdom projection(ランダム射影)

を用いているらしい．

最初，ただランダムに次元を選ぶようなので，

まあ，そういうもんか

と思っていたら，きちんとした理論展開があるらしい・・・．

「Johnson-Lindenstrauss補題」というらしいけど，

どうやらこれも使ってるみたい．

一応，確認しておくか．

LSHアルゴリズム

基本的な考え方

対象となる特徴ベクトルp=(x1, ..., xd) (d：次元数)
↓
二進数のベクトルv(p)に変換
v(p)=UnaryC(x1) ... UnaryC(xd)
C：ベクトルの要素の最大値
UnaryC(x)：1がx個の列に0がC-x個の列をつなげた0,1で構成される値．
↓
ハッシュ関数：gI(p)
{1, 2, ... , Cd}の部分集合Iによって選ばれたビットの値を並べた値がハッシュ値．

Step1:

{1, 2, ..., Cd}の部分集合Ii (i = 1, ..., L)について，
のハッシュテーブルを作成．

(つまり，ひとつの特徴ベクトルにつきL回ハッシュ値を計算してテーブルに格納．)

全部でL個のハッシュテーブルTiができる．

このとき，競合(collision)する場合は，同じエントリに格納する．

ここ重要！ｍ9っ｀Д´) ﾋﾞｼｯ!!

Step2:

最近接点探索．

クエリqに対してすべてのハッシュ関数でハッシュ値を求める．

得られたハッシュと同じキーを持つエントリに含まれる特長ベクトルをすべて取り出す．（同じキーを持つエントリの和集合）→　最近接点候補

候補の中から最近接点を距離計算により発見．

Locality-Sensitive Hashing

Locality-Sensitive Hashing [1] (以降、LSH)は，Indykらによって提案された最近接点探索の確率的な近似アルゴリズム．

LSHはハッシュテーブルを用いることで高次元のデータセットでも最近接点探索を高速に実行する．

・ハッシュテーブル(hash table)

キーと値の組（エントリと呼ぶ）を複数個格納し，キーに対応する値をすばやく参照するためのデータ構造．

・ハッシュ関数(hash function)

あるデータが与えられた場合にそのデータを代表する数値を得る操作．または，その様な数値を得るための関数のこと．

ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという．

LSHの重要なポイントは，類似しているデータ間のハッシュ値は一致し，類似していいないデータ間のハッシュ値は異なるようなハッシュ関数を用いることにある．

これにより，ハッシュテーブルを用いた探索が可能となり，ハッシュテーブルの特徴であるデータ参照の速さをいかした探索が可能となる．

参考文献

[1] A. Gionis, P. Indyk and R. Motwani, "Similarity Search in High Dimensions via Hashing," Proc. of the 25th VLDB Conference, pp. 518-528, 1999.