1. No category

情報システム基礎論２：第 8 回 (担当： 古賀)
高次元データに対する類似検索の難しさ/ハッシュベースの類似検索
2014 年 6 月 10 日
バケット法 (Bucketing Algorithm)
1
バケット法は d 次元空間での類似検索を行う手法である。kd-tree と同様に、空間分割を行うが kd-tree
よりも単純なデータ構造を使用する。
d 次元ユークリッド空間を一辺 l の超直方体で規則的に区切る。1 個の超直方体をバケットと呼ぶ。
1.1
類似検索アルゴリズム
Step 1: クエリ q が入るバケット bq を決定。これは q の座標から容易にできる。
Step 2: bq 内で q に最も近い点 p(bq ) を求める。max dist = D(p(bq ), q) とする。
Step 3: q を中心として半径 max dist の超球と重なるバケットを q に近い順に調べる。より近い点が見付
かった場合は max dist を更新し探索範囲を狭める。
図 1 の例では、max dist が 1 回更新され、超球と重なるバケット数が 6 個から 2 個に減少。
1.2
1.2.1
性質
超直方体の一辺 l の長さ
バケット法では l の大きさが検索性能に大きな影響を与える。
• 大きすぎる → 1 個のバケット b に入る点数増加。b 内で q に最も近い点を決定するための距離計算
回数増加。
• 小さすぎる → q と同じバケットに入る点が 1 点もない。調べるバケット数増加
1 バケツに点がちょうど 1 個含まれるのが理想。
bq
q
l
図 1: バケット法
1
q
l
図 2: 最悪ケース
1.2.2
次元数 d との関係
バケット法は高次元データの類似検索には向かない。図 2 を使って確認する。
図 2 では q と p(bq ) との距離がバケットの対角線の長さにほぼ等しい。調べなければならないバケット
数は 12。これは、「bq 内に S の点が存在する」という条件下では最悪の場合である。
√
• 2 次元の場合：12 = 半径 2l の球と重なる一辺 l の正方形の数
√
• d 次元の場合：半径 dl の d 次元超球と重なる一辺 l の超直方体の数 = 2d + 2dα(d)
α(d) は d に対して単調増加となる係数。α(1) = 0. α(d) ≥ 2d−1 if d ≥ 2。
よって、探索しなければならないバケット数は d に指数的に依存する。
次元の呪い (Curse of Dimensionality)
2
高次元空間になるに連れて類似検索の難しさは増加する。この現象を次元の呪いと呼ぶ。
• 高次元空間では検索すべき方向が d に関して指数的に増加し、アルゴリズムの計算量も爆発。
• 球面集中現象：データ数 n が固定されている場合、点密度は高次元空間ほど減少する。この結果、す
べての点が互いに離れていく。
どちらもデータの数と較べて、高次元空間では空間容積が大きくなることが根本原因。
2.1
球面集中現象
d 次元空間上で、クエリ q を中心とする半径 r の超球 C1 内に n 個の点が一様分布している状況を想定
する。q の NN 探索を考える。
q を中心とする半径 αr (α は定数で 0 < α < 1) の超球を C2 とすると、C1 と C2 の間の隙間の体積
d
d
(= V (C1 ) − V (C2 )) と C1 の体積 V (C1 ) との比は r −(αr)
= 1 − αd 。従って、
rd
V (C1 ) − V (C2 )
= 1.
d→∞
V (C1 )
lim
2
(1)
C1
r
q αr
C2
α を 1 に十分近い値とする。式 (1) は d が大きい時、C1 内に一様に分布する n 個の点は、ほとんどが
C1 と C2 の隙間、すなわち C1 の表面付近に存在することを意味する → すべての点が q から等しく離れ、
NN-探索が困難になる。
近似 NN 探索
3
高次元空間において最近点を厳密に求めるのは難しい。そこで、最近点の近似点を求めることにする。
この問題を近似 NN 探索 (approximate nearest neighbor search) と呼ぶ。
Definition 1 ( 近似 NN 探索)
return p ∈ S such that D(p, q) ≤ (1 + )D(p0 , q) for any other p0 ∈ S
p から q ヘの距離は、q の最近点と比べて (1 + ) 倍以下である。
ハッシュを利用した近似 NN 検索
4
4.1
ハッシュ(Hash) とは
ハッシュは、元々、クエリと同一のデータを高速検索するための技術である。ハッシュテーブルを使っ
て探索すべきデータを絞り込んで高速化を実現する。データ集合を S とする。h をハッシュ関数とする。
∀p ∈ S についてハッシュ値 h(p) を計算し、h(p) の値をインデックスとしてハッシュテーブルに登録。
ハッシュテーブルの各エントリーをバケツと呼ぶ。インデックス値が i であるバケツを b(i) と記述する。
データ x の検索
1. x のハッシュ値 h(x) を計算。
2. ハッシュテーブルにおいてバケツ b(h(x)) を調べ、x が存在するかを確認。
探索範囲をバケツ b(h(x)) 内に絞り込んで、検索スピードを速める。アクセス性能はバケツ b(h(x)) 内
の点数で決まる。h(x) をうまく設計すれば、実用上 O(1) のアクセス時間を達成。
3
hashtable
index
0
1
2
3
bucket
a list of points p such that h(p)=2
.
.
.
.
図 3: ハッシュテーブル
4.2
Locality Sensitive Hashing (LSH)
ハッシュを使った類似検索手法 Locality Sensitive Hashing を紹介する。
アイデア: 類似したデータ同士が同じハッシュ値となるようなハッシュ関数を用意すればよい。
Definition 2 2 点 p, q 間の距離が近いほどハッシュ値が同じ値を取る確率が高くなるようなハッシュ関
数を Locality Sensitive Hashing と呼ぶ。
とくに、ハッシュ関数 h が次の性質を満たす時、h は (r, r(1 + ), p1 , p2 )-sensitive であると呼ぶ。但し、
p1 > p 2 。
• if D(p, q) ≤ r, P [h(p) = h(q)] ≥ p1
• if D(p, q) ≥ r(1 + ), P [h(p) = h(q)] ≤ p2
5
M 次元ハミング空間での LSH
M 次元ハミング空間では、データは M bit のビット列である。2 個のビット列 p, q 間のハミング距離
D(p, q)=値が異なる bit 数。
q = 10101
p1 = 10001
p2 = 00111
ハミング距離は D(p1 , q) = 1, D(p2 , q) = 2。
以下のハッシュ関数 h は LSH。
Step 1. 1 から M までの範囲の整数をランダムに選択。選択された整数を i とする。
Step 2. M bit のビット列 p に対するハッシュ値 h(p) = (p の i 桁目のビット値)。
4
この時、2 個のビット列 p, q のハッシュ値が等しい確率は、
P [h(p) = h(q)] = 1 −
M − D(p, q)
D(p, q)
=
.
M
M
これは、D(p, q) が小さいほど、p, q が同じハッシュ値となる確率が大きいので LSH。具体例では、
1
5
2
P [h(p2 ) = h(q)] = 1 −
5
P [h(p1 ) = h(q)] = 1 −
= 0.8.
= 0.6.
M 次元ハミング空間における LSH による類似検索
6
クエリ q に対する類似検索を考える。
• p1 : q の最近点。r = D(q, p1 )。
• p2 : q から距離 r(1 + ) 離れた点。D(q, p2 ) = r(1 + )
q と p1 は同じハッシュ値だが、q と p2 が異なるハッシュ値となれば 近似 NN 探索を実現できる。
6.1
複数 bit の使用
M bit のビット列 p から、k 個のビット位置をランダムに選択して出力するハッシュ関数を g とする
例： q = 10101。k = 3 とし、第 5bit, 第 1bit, 第 2bit がランダムに選択されたとすると、g(q) = 110。
P [g(q) = g(p)] = (k bit すべてが一致する確率)
M −Dp =
=
k
M
k
M − Dp M − Dp − 1 M − Dp − 2
M − Dp − k + 1
·
·
··· ·
M
M −1
M −2
M −k+1
具体例では、k = 3 とすると
従って、
P [g(p1 ) = g(q)] =
4 3 2
2
· · = = 0.4.
5 4 3
5
P [g(p2 ) = g(q)] =
1
3 2 1
· · =
= 0.1.
5 4 3
10
M − Dp1 M − 1 − Dp1
M − k + 1 − Dp1
P [g(q) = g(p1 )]
=
·
···
.
P [g(q) = g(p2 )]
M − Dp2 M − 1 − Dp2
M − k + 1 − Dp2
よって、k < M − Dp2 + 1 であれば、
k が増加すると、
最近点 p1 と q が同じバケツに入る確率 P [g(q) = g(p1 )] と
遠い点 p2 と q が同じバケツに入る確率 P [g(q) = g(p2 )] との比が増幅する
5
しかし、P [g(q) = g(p1 )] の値そのものは小さくなった。
そこで、さらに複数個のハッシュ関数 g1 , g2 , · · · , gl を用意する。各ハッシュ関数はランダムに選択され
るビット位置が異なる。
そして、g1 から gl までのどれかのハッシュ関数に対してハッシュ値が一致するかどうかで、ハッシュ値
の一致判定をする。
• if ∀i gi (p) 6= gi (q) → p と q のハッシュ値が一致しない。
• if ∃i gi (p) = gi (q) → p と q のハッシュ値は一致する。
• Ej : g1 から gl までのどれかのハッシュ関数に対して、pj と q のハッシュ値が一致する事象 (j = 1 or 2)
P [E1 ] = 1 − P [for 1 ≤ i ≤ l, gi (p1 ) 6= gi (q)]
= 1 − P [g(p1 ) 6= g(q)]l
= 1 − (1 − P [g(p1 ) = g(q)])l
≈ 1 − (1 − l · P [g(p1 ) = g(q)])
(...P [g(p1 ) = g(q)] が十分小さい)
= l · P [g(p1 ) = g(q)].
同様に P [E2 ] ≈ l ·P [g(q) = g(p2 )]。すわなち、l 個のハッシュ関数を使用して、P [g(q) = g(p1 )], P [g(q) =
g(p2 )] を比を保ちつつ l 倍にできる。
k と l をうまく選択すると、
P [E1 ] ≈ 1, P [E2 ] ≈ 0.
とできる。
6.2
まとめ
k と l をうまく選択して、q と p1 を同じハッシュ値に、q と p2 を異なるハッシュ値にできる。しかし、
適切な k, l は r と に依存。→ 現実的にはサンプリングなどヒューリスティックな学習が必要。
6