局所性鋭敏型ハッシュ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

局所性鋭敏型ハッシュ: locality sensitive hashing)とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。

定義[編集]

局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間\mathcal M =(M,d)と閾値R>0、近似因子c>1によって定義される。LSH族[1][2]は2点p,q\in {\mathcal M}について次の2つの性質、

  • d(p,q) \le Rならばh(p)=h(q)となる確率はP_1 \,以上である。
  • d(p,q) \ge cRならばh(p)=h(q)となる確率はP_2 \,以下である。

を満たす関数h:{\mathcal M}\to Sにより与えられるであり,h\mathcal Fから一様乱数にしたがって選択される。このときd(p,q)は2点p, qの距離を表す関数であり、c \le 1P_1 < P_2である。このような族\mathcal F(R,cR,P_1,P_2)に鋭敏であるという。

これに準ずる定義として、領域Uにおける類似度関数\phi : U \times U \to [0,1]によるものがある[3]。局所性鋭敏型ハッシュの性質は、ハッシュ関数の集合Hと確率分布Dにより与えられる。あるハッシュ関数hは集合Hから確率分布Dにより選ばれるが、Dとは領域Uに存在する2点a, bについて、

Pr_{h \in H} [h(a) = h(b)] = \phi(a,b)

を満たすような確率分布である。

手法[編集]

ハミング距離に基づく標本化[編集]

LSH族を構築するためのもっとも単純な手法はハミング距離に基づくものである。これはd次元のベクトル\{0,1\}^dに対して適応できる。この手法はd次元のベクトルについてi番目の座標値をハッシュ値として与えるような族\mathcal Fにより定義され、\mathcal Fとは例えば{\mathcal F}=\{h:\{0,1\}^d\to \{0,1\}\mid h(x)=x_i,i =1 ... d\}のように与えられる。ここで\mathcal Fからhを任意に選ぶということは、入力点から任意にビットを選択するということに他ならない。この時、族は次の性質を持つ。

P_1=1-R/d \,, P_2=1-cR/d \,

安定分布に基づく手法[編集]

ハッシュ関数h_{\mathbf{a},b} (\boldsymbol{\upsilon}) : 
\mathcal{R}^d
\to \mathcal{N} d次元のベクトルvを整数の集合に移すような関数であると定義する[4]。ハッシュ関数hは2つの乱数a, bによって定義される。ここでaとは安定分布から独立に選ばれる乱数であり、bとは[0, r]から一様に選ばれる実乱数である。aおよびbが選ばれたとき、ハッシュ関数h_{\mathbf{a},b}

h_{\mathbf{a},b} (\boldsymbol{\upsilon}) = \left \lfloor \frac{\mathbf{a}\cdot \boldsymbol{\upsilon}+b}{r} \right \rfloor

のように与えられる。

この他にもデータをより適切に対応させるハッシュ関数が提案されている[5]。例えばk-平均法に基づくハッシュ関数などは大域的最適解を与えることが保証されていないものの実用的なハッシュ関数として知られている。

参考文献[編集]

  1. ^ Gionis, A.; Indyk, P., Motwani, R. (1999). , “Similarity Search in High Dimensions via Hashing”. Proceedings of the 25th Very Large Database (VLDB) Conference. http://people.csail.mit.edu/indyk/vldb99.ps ,. 
  2. ^ Indyk, Piotr.; Motwani, Rajeev. (1998). , “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.”. Proceedings of 30th Symposium on Theory of Computing. http://people.csail.mit.edu/indyk/nndraft.ps ,. 
  3. ^ Charikar, Moses S.. (2002). “Similarity Estimation Techniques from Rounding Algorithms”. Proceedings of the 34th Annual ACM Symposium on Theory of Computing 2002: (ACM 1–58113–495–9/02/0005)…. doi:10.1145/509907.509965. http://portal.acm.org/citation.cfm?id=509965 2007年12月21日閲覧。. 
  4. ^ Datar, M.; Immorlica, N., Indyk, P., Mirrokni, V.S. (2004). “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions”. Proceedings of the Symposium on Computational Geometry. http://theory.csail.mit.edu/~mirrokni/pstable.ps. 
  5. ^ Pauleve, L.; Jegou, H., Amsaleg, L. (2010). “Locality sensitive hashing: A comparison of hash function types and querying mechanisms”. Pattern recognition Letters. http://hal.inria.fr/inria-00567191/en/. 

関連項目[編集]