最近傍探索2011

Tag

# 大規模データ処理

# 解説

Daisuke Okanohara

Executive Vice President

こんにちは、二台目のmbaを買うのをためらっている岡野原です。

アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。

アイテムが低次元（例えば2, 3次元）の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元（数百万次元）中の点であったり、アイテム間の距離のみが定義されている場合（カーネル関数など）です。アイテム数は数万から数億ぐらいを想定しています。

最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、全てのアイテムxにそれぞれについて、それらから最も近いk個のアイテム（k近傍リスト)、kNN(x)を求めよ」

となり、近傍列挙問題では

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、距離がt以下のアイテムペアを全て列挙せよ」

といった形になります。

この問題に対する自明で最も単純な方法は、全てのアイテムについて、他のアイテム全ての距離を計算し、最小k個を求める方法です。この場合、距離計算はn^2/2回行う必要があり、アイテム数が数百〜数千ぐらいまでしかスケールしません。

この問題に対しては、アイテム一つずつ近傍探索するのではなく、全てのアイテムの近傍探索をまとめて解くことで、高速に求めることが出来る方法がいくつか存在します。今回はそのなかでも実用的で新しいアイディアに基づいているものをいくつか紹介します。

Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures

PDF
W. Dong, M. Charikar, and K. Li, WWW 2011

なぜ誰も思いつかなかったのか（ルーターのMST決定とかで見たような）というほど単純なアイディアで近傍探索を高速に求めるアルゴリズムです。
このアルゴリズムの基本アイディアは、「近傍の近傍は近傍になりやすい」ということです。それぞれのアイテムが自分の現状の近傍リストを持ち、近傍の近傍に今のリストに入っているアイテムより近いものがないかを調べて、近傍リストを逐次的に改善していきます。

各アイテムxについて、そのk個の近傍アイテムをB[x]で表すことにします。逆に、アイテムxを近傍だとしているアイテムの集合をR[x]とします。B[x]は常にk個なのに対し、R[x]はk個とは限らないことに注意してください。また、B[x]とR[x]の和集合をU[x]とします。

はじめに、各アイテムxについて、B[x]をX中のランダムなk個で適当に決めます。次に、各点xについて、その近傍の近傍、つまり、U[x]の中から一つアイテムyを選び、さらにU[y]の中の各アイテムzについて、それが自分の今持っている近傍リスト中のアイテムより近いかどうかをチェックし、近ければ近傍リストを更新します。これを収束するまで繰り返します。

この方法は近傍リストを逐次的、Greedyに更新していくので、kNNの最急降下法という説明が論文ではなされています。

基本的なアイディアはここまでなのですが、改良ポイントが四点あります。

一つ目がlocal joinです。先程のような更新方法をとる場合、近傍の近傍でループを回すとメモリアクセスに局所性がありません。例えば、a – b で aとbが近傍ということを表すと、先ほどは a – b – cの関係にある時、aを固定してループを回して、cがaの近傍に入るかというのをチェックしています。local joinでは bを固定して、bの近傍二つa, cをとってきて、それらがそれぞれ自分の近傍リストを更新できるかどうかをチェックするようにします。こうすることによって、計算量自体はかわりませんが、メモリアクセスの局所性が増し（各アイテムの近傍リストを二重ループするだけ）、高速化することができます。

二つ目がincremental searchです。近傍リストは後半になってくると収束して殆ど更新されなくなってきます。そこで、近傍リストに新しく入ったかどうかを各アイテム毎にフラグとして持っておき、local joinで調べるときには少なくとも片方が新しく入った場合だけチェックをするようにします。

三つ目がsamplingです。local joinの時に実際に全部をチェックするのではなく、適当にサンプルしたものだけをチェックするようにします。次回のサンプリングでは前回サンプリングされなかったものを選ぶようになります。近いのであれば、どれかの近傍には入っているので、全部調べるのは冗長という考えにもとづいています。

四つ目はEarly Terminationです。収束してきたら、近傍リストの改善は少なくなってくるので、適当なところでやめてしまいます。

実験では画像データや言語データなどいくつか試していますが大体傾向は同じです。iteration回数はどの場合でも4,〜5回程度で収束し、その時の再現率が9割前後（本当の近傍のうち9割程度見つかる）、データ数nに対する計算量は多くのデータでO(n^1.14)です。
このアルゴリズムでは逐次的に近傍リストを更新していくのでアイテムの追加や削除、更新についても効率的にサポートできそうです。

結果で気になるのはデータの種類や量によらず計算量のオーダーが常に同じ（小数点第2位まであう）だということです。近傍グラフの性質がスモールネットワークのように一定以上の量になると法則が現れてくるのでしょうか。

今後の改善の余地があるとすれば、理論的な解析をするのと、更新にランダム性をいれたりMCMCのような枠組みをいれることで局所最適ではなく大域最適な結果が見つかるようにできるかということです。

Scaling Up All Pairs Similarity Search

pdf
R. J. Bayardo, Y. Ma, and R. Srikant, WWW 2007

次に紹介する方法は各アイテムが疎で高次元な特徴ベクトルの場合に向けての方法です。先程の方法では結果は近似でしたが、今回の方法は正確な結果を返します。
話を簡単にするために距離がcos類似度（高ければ高いほどよい）の場合であり、各特徴ベクトルのL2ノルムが1に正規化されているとします。また、cos類似度が閾値tを超えたものだけを見つけたいとします。
＃そうでない場合については論文を参照してください。

このような特徴ベクトルが疎で、内積ベースで距離を計算する場合にまず考えられることは、情報検索のように各特徴毎に、それが発火したデータと、特徴値を保存した転置ファイルを構築し、それを利用して内積を計算する方法です。しかし、この転置ファイルを利用する方法には問題が三つあります。
一つ目は、そのまま計算してしまうと(x, y)と(y, x)の二つの類似度の計算をしてしまうという問題、二つ目は全部のデータを読み込んで、それに対して転置ファイルを構築した後でしか結果を出せないという問題、三つ目は転置ファイル自身が元のデータと同じサイズだけ必要で作業領域量が大きいことです。これらを解決していきます。

まず最初の改善では、初めに転置ファイルを作るのではなく、データを順番に調べていって、その時に一緒に転置ファイルも作っていく方法です。データをx1, x2, …, xk-1までみていった時、ここまでのデータに対する転置ファイルを構築します。そして、xkを調べるときには(x1, xk), (x2, xk), …, (xk-1, xk)の類似度が閾値より大きかどうかをチェックします。これにより、対称部分の計算の重複がなくなりますし、また、データ全体を読み込まなくても結果を返すことができます。

二つ目の改善では、転置ファイルを全て作らずに関係しそうなところだけを作る方法です。特徴毎に発火数に大きな偏りがあることをうまく利用し、転置ファイルには珍しい特徴だけが含まれるようにします。アイテムxについての転置ファイルを構築する際には、xの発火している特徴を、転置ファイル中でのエントリ数が多いものから順番に調べるようにします。次に値bに現在みてきた特徴と、他のアイテム全てのうち特徴値が一番大きいものを計算したときの内積を保存します。そして、閾値がtの時 b < tの間は転置ファイルに登録せず、元のデータに登録しておき、b >= t になった時から転置ファイルに登録するようにします。

これらの改良により、転置ファイルは、実際に閾値tを超える可能性がある場合のみ転置ファイルに入るようにあります。そして、転置ファイルにひっかかって類似度を計算するときには、転置ファイルによって計算された分にくわえ、残されたアイテムからの類似度計算部分を調べます。転置ファイルのエントリ数が大きいものから小さいものに順に調べているので、大部分の転置ファイルをつくらずにすむようになり、使用容量の大幅な削減と計算時間の削減が達成できます。

三つ目の改善では、データを、それが持つ特徴値の最大値が大きい順番に並び替えます。そして、転置ファイルを作る時と、それを利用して閾値がtを超えるものを調べる両方の時に枝刈りを行います。これにより、転置ファイルが作る量と、実際に候補が出る量の両方が大幅に減らすことができます。

またこの他にも、特徴ベクトルがbit列である場合や、距離がcos類似度ではない場合向けの最適化も紹介しています。

これらの最適化を適用することで何も最適化を施さない場合と比べて数倍から数十倍、他の手法（例えばLSHを使う場合）などと比べても数倍の高速化が達成できたと報告しています。

その他

この他にも、注目すべきトピックがいくつかありますので要点だけ述べておきます。

“Hashing with Graphs

W. Liu et. al, ICML 2011 pdf

アイテムの集合からアンカーポイントと呼ばれる少数の点を選んだ後に、各アイテムをそれから一番近いk個のアンカーポイントが張るsimplex上で表します。そして、アイテムaとアイテムbの間の近さを、aから関係する各アンカーポイント、そしてそれらのアンカーポイントからbへの近さをあわせて測るようにします。このように作られた行列はいくつも良い性質があって、例えば隣接情報は非常に疎に表せることができますし、またグラフラプラシアンなどを高速に求められるという特徴があります。この論文では、グラフラプラシアンを使った符号化に注目していましたが、アンカーグラフの方はいろいろな用途に使えそうです。

詳しく知りたい方はbeamさんによる解説や、nokunoさんによる解説をどうぞ