locality sensitive hashing(LSH)

LSH[0][6]とは、ハッシュ関数を使ってデータを次元圧縮をしたり、データ同士の比較を高速で行えるようにするための手法である。使用するハッシュ関数の代表例は、下記の安定分布とハミング距離、Jaccard指数がある。ハミング距離を使って、データの比較する例は[6]がわかりやすい。

安定分布

[1][2]によると、確率変数 ${X_i}$ が独立同時分布(i.i.d)Xに従う時、
$S_n = \frac{1}{a_n} \sum^n_{i=1} X_i - b_n$
が元のi.i.dと同一の分布である場合、Xは安定分布であるという。なお[3]では条件式が別形式で記載されているが、
$aX_1 + bX_2 = cX + d \Leftrightarrow \frac{a}{c}X_1 + \frac{b}{c}x_2 = X + \frac{d}{c} \Leftrightarrow X = \frac{a}{c}X_1 + \frac{b}{c}X_2 - \frac{d}{c}$
となり、XからサンプルSを取り出した時に ${X_1, X_2}$ の係数と ${\frac{d}{c}}$ を変化させれば上式と同様のことが言える。

安定分布の中の代表格が、ガウス分布やコーシー分布である。

ハミング距離[4]

2つの変数a, bがある時、
f:id:graziegrazie:20190316061929p:plain
で求める。例えばa = [1, 0, 0, 1]、b = [1, 1, 0, 0]とすると、ハミング距離は(0+1+0+1)=2となる。

Jaccard指数[5]

f:id:graziegrazie:20190316062819p:plain
a={abc, def, ghi}, b={abc, efg, hij}とすると、 ${a \cup b = 3 + 3 - 1}$ (１つ重複する要素があるため）かつ ${a \cup b = 1}$ なので、 ${J(a, b) = \frac{1}{5} = 0.2}$ となる。