Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph

K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang, Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. ;In Proceedings of IJCAI. 2011, 1312-1317.

k近傍グラフ上での山登り方による近似最近傍探索．
Locality Sensitive Hashing，KD-木よりも速くて高速．

問題

最近傍探索．d次元空間上の点集合Dと距離尺度ρが与えられる．各クエリQに対して，
$X^{*} = \mathrm{argmin}_{X \in D} \rho(X, Q)$
を求める．線形探索のオーダーはO(nd)．

提案手法 The Graph Nearest Neighbor Search (GNNS)

k-近傍グラフ

ノードが各点の有向グラフ．辺(u, v)は，vがuのk-近傍だった時に繋がれる．単純な構築オーダーはO(dn^2)．ただ，もっと速い手法が既に提案されている．

近似k-近傍探索

滅茶苦茶簡単な最良優先探索．k-近傍グラフ上で，K-近傍を探すことを考える（大文字と小文字が混ざって分かりにくい…）．

k-近傍グラフから初期点 $Y_0$ を選ぶ．
以下の貪欲法をT回繰り返す．一言でいうと，今いるノードのE-近傍の内で最もクエリに近い点に遷移する．

$Y_t = \mathrm{argmin}_{Y \in N(Y_{t-1},E,G)}\rho(Y,Q)$

終了したら，今まで探索したノードでクエリQに近いノードK個を出力する．
Tは反復回数．無くても，局所解に入ったら終了とかで大丈夫らしい．Eは適当に決める．

計算量

時間計算量は， $\min\{nd, 2^dn^{2/d}\}$
精度は，距離尺度がL1ノルムかつ，終了条件を極小値とした時，点集合が超立方体上に一様分布していれば，真の最近傍を返す確率が高い（論文にはちゃんと書いてある）．

実験

比較対象

乱択KD-木
Locality Sensitive Hashing

評価基準

線形探索との速度比（実装依存）
距離尺度の計算回数（非実装依存）

データセット

中身：SIFT（Scale-Invariant Feature Transform，画像の特徴量）
データセット数：5
点数：17000, 50000, 118000, 204000
次元数：128
クエリ数：500
K（求める近傍の数）の値：1, 30, 300

合成データセット

次元dの点をいっぱい作る
点の生成法：[0,1]^d 上で一様ランダム
点数：50000
クエリ数：500

実験設定

距離尺度：L2ノルム
k-近傍グラフ：k=1000のグラフを作って使いまわす
パラメータ：(精度, 速度・計算回数)の関係を見るため，EとTを色々変えた

実験結果

速度も計算回数もKD-木，LSHより良い（同じ精度の時の速度・計算回数が少ない）
データセットのサイズが大きい方が線形探索に比べた性能が顕著

戯言

時間計算量が良く分からない．2^dが入っている時点でその項は意味無いように思える（読み落としたのかも）．
アルゴリズムは単純で自分でも思いついていた位だった（元々k-近傍グラフを先に知った）．
実験は，色々設定を変えているので良いのかなと思ったが，距離尺度をL1ノルムとかコサイン類似度とかに変えてやってみて欲しかった（データセットも変えて）．
速度が比較手法より遥かに優れているのに対して，計算回数はそれ程でも無かったので，実装によっては変わるのかもなあと思った．グラフの見せ方の問題か，あるいは，アルゴリズムが単純だから定数が小さいのかもしれない．
オフラインでのk-近傍グラフが明らかにネックになるので，次は高速な近似構築手法に関する論文を読む予定．