高速に類似度計算をしたい場合、典型的に使われるのは Locality sensitive hashing (LSH)という技術であり、元々距離が近いインスタンス同士はハッシュ値が近くなるようにハッシュ関数を作ることで高速に類似度を計算したりできるというお話なのだが、最近 Semantic hashing や Spectral hashing、また Kernelized LSH という手法が登場して盛り上がりつつあるところ、同じグループの人がもっといいのを出しました、ということらしい。ちなみに情報推薦とか画像検索とか大規模クラスタリングとか、いろいろな分野で高速な類似度計算の応用例がある。
そういうわけで、今日は manab-ki くんが
- Brian Kulis and Trevor Darrell. "Learning to Hash with Binary Reconstructive Embeddings." NIPS-2009 (to appear)
を紹介していた。
Spectral hashing はハッシュ関数の設計に元のデータの情報を用いることで高い性能を達成していたが、カーネルが使えないという問題とデータの分布に一様分布の仮定があったりするという問題があり、提案手法 BRE はカーネルも使えるしデータの分布にも仮定がないという利点があるそうだ。
勉強会の最中はよく分からなかったが、終わったあと manab-ki くんが「今日の内容分かった？」と確認に来てくれたので、いろいろ話してみてようやく分かった。ポイントは
- s 個のランダムサンプリングした点から greedy に目的関数を最適化してハッシュ関数を作る(b 個のハッシュ関数を得るためにはランダムサンプリングを b 回する)。具体的にはハッシュ関数で使う重みを学習する。
- ランダムサンプリングされたインスタンスとそれに対する重みを保存しておき、テストインスタンスは記憶されているインスタンスとテストインスタンスの重みつきカーネル和(の符号)でハッシュ計算
というところか。
実験設定とグラフを見ると、どうも前処理や後処理(Spectral hashing と使っているデータは同じなのに見せているグラフの設定が違う)をいろいろしているようで、なんだか恣意的な印象を受ける。計算の手間を考えると Spectral hashing のほうがいいんじゃないか、と思うのだが……。(一応カーネルを使えるのが利点なので、性能が同じでも提案手法のほうが上かもしれないが、何個のサンプルを用いたかも書いていないし、どのカーネル使ったのかも書いていないし、謎が多い)。自分の印象としては「Spectral hashing でいいんじゃないの？」というものだったが、本文があまりうまく書かれていないないので、よく分からない……。
タスクによるのだろうけど、しましまさんも昔 LSH は推薦アルゴリズムの実用的には精度悪いのではと書いていたし、Spectral hashing のような最近のアルゴリズム使わないと使い物にならないのかもなぁ。
