Rubyで近似最近傍探索ライブラリを作った話

はじめに

Rubyで動く近似最近傍探索（Approximate Nearest Neighbor search, ANN）ライブラリが欲しくなって作成した。

hanny | RubyGems.org | your community gem host

FLANNのRuby バインディングがあり検討したが、FLANN自体の開発が止まっているので、勉強の意味でもゼロから作ることにした。手法は様々なものがあるが、シンプルな実装・データ構造になるものが良いと思い、ハッシュ型ANNを選択した。

ハッシュ型ANN

ハッシュ型ANNでは、ベクトルデータ（特徴ベクトル）をバイナリコードに変換し、それをキーとしてハッシュテーブルを作成する。このとき、もとのベクトルデータが類似しているもの同士は、同じバイナリコードになるような変換にする。検索クエリが与えられると、ハッシュテーブルを作成したときと同様にしてバイナリコードに変換し、ハッシュテーブルを探索する。

再訪 Locality Sensitive Hashing

ハッシュ型ANNは、バイナリコードを計算する処理が重要となる。この処理に関して、たくさんの、xxx Hashingが提案されている（もちろん深層学習を使ったDeep Hashingもある、ハッシュ型ANNの黎明期？にSemantic HashingというDeep Belief Networkをベースにしてた手法もあった）。そのなかで、Locality Sensitive Hashing（LSH）は、ハッシュ型ANNの研究の発端となった最初期の手法である。多くの研究ではベースラインとして使われているが、これを見直した論文がある。

Deng Cai, “A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search,” CoRR abs/1612.07545, 2016.

多くの xxx Hashingでは、コード長が短い場合で実験していて、128-bitを超えるコード長も含めて実験してみたら、ランダム射影ベースのLSH（LSHは近似するメトリックで複数種あるが、実験で使われたのはコサイン類似度を近似したもの）は良い感じで、過小評価されてるんじゃないか？という内容になっている。

論文では、複数のハッシュテーブルを用意する探索手法と、バイナリコードのハミング距離をもとに探索する手法との比較も行われており、コード長が32-bitを超える場合は、ハミング距離をもとにする手法が良いらしい（もともとは複数のハッシュテーブルを用意する探索手法があって、空間計算量の節約のためには、ハッシュテーブル上で近接するバケツも探索するのが良いよという話が出て、元のベクトルデータの類似関係がバイナリコードの類似関係に反映されてたほうが良いよねとなって、xxx hashingがたくさん出てきたと記憶している。現在は多くの研究でハミング距離をもとに探索する手法が主流なはず。）

実装のちょっとしたところ

そういったわけで、LSHでハミング距離による探索を実装した。線形代数を必要とするのでNumo::NArrayを用いて実装した。Numo::NArrayにはバイナリコードを表現できるBitクラスがあるので、ハミング距離の計算が簡潔に書けることもある。irbで試すとすれば以下のような感じになる。

> require 'numo/narray'
> a = Numo::Bit[0, 1, 0, 1]
> b = Numo::Bit[0, 1, 1, 0]
> (a ^ b).count # ^ がxorで、countメソッドは1を数える
=> 2

使い方は、READMEのUsageの節が全てです。

おわりに

READMEにExperimentの節を用意して掲載したが、MNISTで簡単にテストしたところ、brute-forceな方法よりも20倍はやく検索できた（もちろん元のベクトルデータの次元数やクエリ数とかで変わってくる）。

今後、xxx hashingを追加していくかは未定で（たくさん手法が提案されていて、どれがベストかはベクトルデータにも寄るので、実装するなら代表的なモノ全てを実装した方が良さそうで、面白いだろうけど大変そう）、LSHのようなdata independentなアプローチで発展があれば、ちょこちょこと実装しても良いかな〜ぐらいに思ってます。

つまらないものですが、よろしくお願い致します。