Approximate Nearest Neighbor Search

　今回は近似近傍探索です。昨日の記事では厳密に距離を計算し、その結果をもとに最も近いN個/距離がR以下のサンプルを抽出していました。近似近傍探索では、距離を簡易的に計算したり、近傍の候補を効率的に抽出することで高速化を目指します。加えて、一部のアルゴリズムではデータを圧縮して保持することもできます。

　高次元(20次元以上？)では、総当たり探索とKDTreeなどの厳密に近傍を探索するアルゴリズムはほぼ違いがなくなってしまいます。高次元では球面集中現象が発生します。クエリからすべてのサンプルのほぼ同距離にあるため、必要のない領域の判定がうまくいきません。例えば１００次元の０～１の一様乱数を生成したとします。KDTreeでは分割平面とクエリが保持するサンプルが形成する球が交われば探索を行いますが、この時全サンプルの距離行列を計算し平均を見てみると４程度でした。つまり、分割平面（軸に平行）とクエリまでの距離は最大でも１しかないにもかかわらず、近傍サンプルまでの距離は４程度ということは、まず間違いなく兄弟ノードの探索が必要になりということです。このような状況が発生するので、むしろKDTreeのように全サンプルを細かい集団で距離を計算するよりは、総当たり探索のように一気に距離を計算したほうが無駄がなくなり、結果として速くなります。

　今日は実装ができているLocallity Sensitive Hashing、Product Quantizationのみについて解説します。近似近傍探索の分類としてはTree、Hash、Graphがあるようですが、ここではHashのみ見てみます。Treeは比較的簡単に実装できそうですがしていません。Graphはどのようにデータを保持すればいいかというか、Graphをどう扱うのかが理解できていないため実装していません。とはいえ、近似近傍探索の性能のトップ付近にも位置しているため実装してみたいと思っています。最速はProduct Quantization ベースのようです。以前調べたときにはGraphベースのものが最速だったような気がしたのですが...

　この記事を読んでいただくよりは、松井勇佑さんのサーベイ資料のほうを読んでいただいた方が良いです。

Locallity Sensitive Hashing

　局所鋭敏性ハッシュとも言います。非常に大雑把にいうと、近いベクトルは同じ値に割り振られる確率の高いハッシュ関数を用意し、クエリと同じハッシュ値を持つサンプルのみを対象として距離計算を行い、近傍抽出を行うアルゴリズムです。とりあえず実装しては見たのですが、どこに原因があるのか精度も速度もかなり悪い実装になってしまっています。

構築

　ハッシュ関数の候補としては、

バイナリへの変換
ランダムな軸上への射影

などがあげられます。これらは一つのベクトルを一つの値へ変換するものです。実際は、これらの少しずつ異なるハッシュ関数K個ペアをLセット用意します。一つのベクトルをK次元のベクトルに変換する関数をL個持っているわけです。あまりいろいろなハッシュ関数を試していないため、どんな場合にうまくいくのかわかっていません。
　サンプルに対してL個のハッシュ関数を適用することで、いくつかのユニークなベクトルに割り振られるはずです。そのユニーク数はサンプル数より少なく、同じハッシュ値（すべてのベクトルの値が同じ）をもつサンプルは近傍に属しています。Kを増やせば増やすほど当然同じ値をもつサンプルは少なくなります。つまり誤検知が減るわけですが、本当にとらなければならないサンプルを取り落とす可能性も同時に高まります。そのため、Lセット用意することで取りこぼしを防ぎます。KとLが増えるほど精度という面では向上しますが、当然処理時間がトレードオフで増大していってしまうため、要件によって調整が必要になります。また、ハッシュ値に対してはそれぞれのサンプルへのポインタのみを保持していればよいのですが、結局元のデータはすべて保持しておかなければなりません。

探索

　探索時はクエリに対してもハッシュ関数を適用します。そしてL個のハッシュ関数のうち同じハッシュ値をもつサンプルのみを距離計算対象とします。ここら辺はそのまま実装したのみです。ほかにも効率化手法はあるようですが、特に調査を実施してはいません。ANN Benchmarを見ていてもLSH系の手法が取り上げられているようには見えなかったためです。

短いですが、LSHは以上です。

Product Quantization：PQ

　直積量子化とも呼びます。こちらも（多分）ハッシュベースのアルゴリズムの1種です。ハッシュ値が同じサンプルのみを距離計算の対象とするのは同じですが、LSHは距離計算は厳密に行われます。一方PQは、距離計算自体も簡略化・高速化されています。非常に簡単なコードで実装していただいているので、こちらのURLもぜひご覧ください。

構築

　LSHのハッシュ関数の候補の一つとしてもあがっているKmeansでハッシュ化を行います。ただ、LSHのようにKペアLセット用意するのは探索時に少し時間がかかるのではないかと思います。そこで、ベクトルをM個の部分空間ごとにKmeansを適用し、その部分空間ごとにクラスタラベルに置換します。例えば256クラスタに分割するKmeansを適用したとします。そうすると原理的には256^Mのパターンを形成することができるほど分解能が高くなります。これと同レベルの分解能を一つのKmeansで達成しようと思うと、すさまじい数のクラスタ数を設定しなければなりません。もちろん現実的な数のクラスタ数では今度は思ったような性能がでないという状態になってしまいます。

　また、ベクトルをクラスタラベル（一つの数値）へ変換することでデータの圧縮することもできます。例えば128次元のFloatが格納されたベクトルを8個の部分空間に分割し、256クラスタのKmeansで変換することを考えてみましょう。もともとのデータは4096bitを消費します。各部分ベクトルは、4096/8=512bit消費しています。この部分ベクトルを256クラスタの一つに割り当てる、つまり0-255の8bitに置換することができます。8/512で1/64となって64分の1にまでデータを圧縮することができます。100万単位であれば個人用のPCでも特に問題ないと思いますが、1億単位では現実的ではありません。128dim x 32bit x 1億 ~ 51GBが64分の1となれば800MBと余裕ができるくらいまで圧縮できます。しかも元のデータを保持する必要がありません。

　実際はもう一段階前にKmeansを適用します。Coarse-Quantizerと呼んで、こちらは部分空間ごとではなく全特徴量を用います。これはCoarse(粗い)の名前の通り、大雑把にサンプルを分割することで探索時に距離計算の必要のないサンプルを削ることができます。これを適用後、すべてのサンプルからそれぞれの属するクラスタとの差分を計算します。つまり、すべてのサンプルを原点付近にシフトさせます。その後部分空間ごとのKmeans、Product-Quantizerを適用します。CoarseQuantizerの各クラスタごとにKmeansを適用すべきかもしれませんが、そうなると構築に非常に時間がかかってしまいます。実際にこのままでも性能が十分以上に出ている状態なので、問題はないようです。

　構築の全体の手順としては以下です。

Corase Quantizerを適用。セントロイドと差分をとる。サンプルごとにクラスタラベルは保存しておく
差分のベクトルに対して部分空間ごとにKmeansを実施。各部分空間をクラスタラベルに置換したベータを保存

上記は前処理です。したがって全サンプルではなく、数千サンプル程度で実施します。その後、学習済みのCoarseQuantizer、Product-Quantizerを全サンプルに適用します。

検索

　検索はまず上述のようにCoarseQuantizerを適用し、該当したクラスタとの差分を計算します。ここからがいろいろ調べていて非常に面白かった点です。前処理でそれぞれの部分空間ごとにクラスタラベルにすべて変換してしまいました。これが高速化に寄与します。そのままCoarseQuantizerの同じクラスタに属するサンプルと距離を計算するのではなく、クエリの各部分ベクトルとその部分空間のクラスタとの間の距離行列を計算します。量子化したあるサンプルの部分空間とクエリの対応する部分空間の間の距離は、この距離行列を参照するだけで計算ができます。全部分空間の和をとってしまえば、それをクエリとサンプルの距離として代用することができます。

以上