Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph - todo314 @ ウィキ

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

• Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang
• In IJCAI 2011

メモ

• hatenaから引っ張ってきたのだからアレ

概要

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

問題

• 最近傍探索。d次元空間上の点集合Dと距離尺度ρが与えられる。各クエリQに対して、次を求める
• $$ X^{*} = ￥arg \min_{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-近傍を探すことを考える（大文字と小文字が混ざって分かりにくい…）

1. k-近傍グラフから初期点Y_0を選ぶ
2. 以下の貪欲法をT回繰り返す
   • 一言でいうと、今いるノードのE-近傍の内で最もクエリに近い点に遷移する
   1. $$ Y_t = \mathrm{argmin}_{Y \in N(Y_{t-1},E,G)}\rho(Y,Q) $$
3. 終了したら、今まで探索したノードでクエリ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-近傍グラフが明らかにネックになるので、次は高速な近似構築手法に関する論文を読む予定。

IJCAI nearest neighbor

2013-10-07 16:24:07 (Mon)