数理輪講で Anchor Graph Hashing の紹介をしてきました

今日、大学の数理情報学輪講で発表してきました。

rinko2011-agh

View more presentations from beam2d

今回は来週開催される ICML 2011 の論文 Hashing with Graphs の紹介です。Anchor Graph Hashing (AGH) という近傍探索のための最新のハッシング手法を提案しています (なんでアルゴリズム名をタイトルにしなかったんだろう……)。一応スライドを読めばなんとなくわかるんじゃないかと思います。

AGH は Spectral Hashing (SH) と同じ最適化問題を考えていて、それを解いてから out-of-sample extension の話に持っていくという流れも同じです。違うのは最適化問題を低ランク近似して解くところと、そのおかげで Nyström method という手法が使えて、SH みたいに分布に変な仮定を置いて固有関数問題をガリガリ解かなくて済むところ。データの次元、データ数のそれぞれについて線形時間のアルゴリズムになっています。

低ランク近似は、第一著者の Liu が ICML2010 提案している Anchor Graph に基づいています。この Anchor Graph が良い性質をたくさん持っていて、アンカーを用いたマルコフ連鎖的な解釈もあって、ハッシング以外にもいろいろ使えるんじゃないかと思います。

スライドでは論文の後半で述べられている階層的手法 (2-AGH) を紹介できませんでしたが、これは半分のビットは AGH で作って、残りは前半の各ビットに対して、うまく分けられなかった・分けるべきでなかった部分を補正するようなビットを入れる、という手法です。AGH は SH と同じく PCA みたいな手法なので、ビット数を増やすと固有値の低い (ノイズの多い) 主成分まで使うことになり、結果として MAP 精度が低下してしまう問題があります。階層的ハッシングでは半分のビットだけ AGH にして、後半はアドホックに作ることで、この問題をある程度回避しようとしています。が、半分は AGH で作るので、実験では 2-AGH でも下がったりしてます。

SH と同じ問題なので、多様体学習的な要素が入ってきています。なので与えられた距離関数についての最近傍探索ではないです。実際、実験結果では単純に全比較をした場合よりも精度が高いです。面白いのは、Spectral Embedding したあとに単純な全比較をする方法 (SE l_2 Scan) よりも階層的ハッシング (2-AGH) の方が精度が良いということ。近傍探索については、遠い点同士の類似度はざっくりゼロに落としちゃう方が精度が上がるということなんでしょうか。

Nyström method のあたりはちょっと難しいですが、SH に出てくる Laplace-Beltrami 作用素の固有関数問題のあたりに比べればだいぶわかりやすいと思います。[Bengio+, 04] をパラパラ読めば結構分かるんではないかと。固有ベクトルから固有関数を近似する方法として、結構使われている？みたいです。

ともかく Anchor Graph Hashing は面白いので、気になる方はぜひ論文も読むといいと思います。