最近傍グラフを用いた類似文字列検索の実験に失敗した話

アルゴリズム

前々から、LSHとか最近傍探索に興味があったので、下記の論文をちょっと実装してみた。 面倒なので、ちゃんとした評価はしていない。

  1. Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures (WWW 2011)
  2. Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph (IJCAI 2011)

1の論文は、最近傍グラフを近似的に計算するもの。2の論文は、最近傍グラフを元に、クエリと一番近傍の点を近似的に探索するというもの。 1の論文については、PFI Research blogに解説があるので、詳しくはそちらを参照されたい。 2の論文については、既に構築済みの最近傍グラフから、ランダムに１点抽出し、その近傍の中で一番類似度が高いものを調べ、そのさらに近傍を調べ・・・というのを繰り返すというシンプルなもの。すごく簡単なアイディアなので、この論文がIJCAIに通ったのは、手法の理論的な分析がよくできてたからなんだろうなーと思う。

 

これらの論文の面白いところは、類似度関数に任意のものを利用できるという点。 そこで、cosine類似度や、Jaccard係数のように集合をベースとした類似度計算ではなく、編集距離を用いて計算してみた。個人的にはtree kernelの最近傍探索とかが面白いかな？とか思ってた。

実装上は、類似度関数を簡単に切り替えられるようにしてあるので、もともとは類似文字列検索ではなく適当なリコメンドエンジンにしようかと思ったんだけど、ちょっと試すのに楽なように文字列を対象にした。

 

で、結果だけど、類似文字列検索をやるのであれば、SimStringやapporoを使った方がいい。

レコメンドエンジンとしてはどうなのかなー。 たまに一番近いアイテムを取り逃すことがあるので、それはビジネス的に嬉しくなさそうだとは思った。

もちろん、素直にO(n2)使って最近傍グラフを作るよりは、ずっと高速に近傍グラフの作成及び検索が可能だけど、精度がやっぱり近似ということもあって少し残念。 (もちろん、構築&検索速度を落とせば精度は高くなるが、それだとあまり意味がない)

 

具体的にソースコードと実行結果は以下のような感じ。

ソースコード(github)

# コンパイル
$ g++ -O2 nng_builder.cc -o nng_builder
$ g++ -O2 nns.cc -o nns  

# 最近傍グラフの構築 (対象のファイル名 linux.words)
$ ./nng_builder linux.words > /dev/null

# 最近傍グラフの探索
$ ./nns linux.words "test"
test,100000 west,99999 vest,99999 text,99999 tent,99999 rest,99999 pest,99999 nest,99999 lest,99999 jest,99999 

$ ./nns linux.words "ARPA"
Anne,99997 Agee,99997 trap,99996 tool,99996 tons,99996 sulk,99996 step,99996 spot,99996 scan,99996 ring,99996

まぁ、とりとめもないエントリでしたが、成功した話でもないしただの記録ということで。