最近のバイナリハッシングをいくつかJavaで実装してみた

ml java hashing

去年の終わりから、バイナリハッシングを使った近似近傍検索をいろいろ調べていたのですが、ぼちぼち一段落したので、ひと通りまとめておきます。

バイナリハッシングとは。

n 個の D 次元の点からなるデータセット X = [x_{1} \, , \, ... \, , \, x_{n}] \in R^{D\times n} で、元空間での近傍点を、類似したバイナリコードに関連づける技術。


要するに、実数ベクトルの検索をマトモにやるには、最近のデータは膨大すぎるのでお手上げ。なので、元空間での距離をなるべく保ったまま、バイナリコードに落としましょう。
そうすると、バイナリ一致か、1ビット違うか、2ビット違うか...と、捜索していくにしても、元空間のデータでやるより高速で、しかもストレージ容量を削減できるというわけです。


その K ビットのバイナリコード Y = [y_{1} \, , \, ... \, , \, y_{n}] \in B^{K\times n} を作るために、K 個のハッシュ関数が使われる。
ハッシュ関数は h_{k}({\small X}) = sgn( f( {\small W} ^T_k {\small X} + b_{k}) ) と定義される。ここで、{\small X} はデータセット。{\small W}_k は射影ベクトル。b_k は閾値。


線形写像ベースのハッシングはシンプルで効果的です。上の式は要するに、データに、

  1. 行列 {\small W} を掛けて
  2. ごにょごにょして
  3. 二値化

しているだけです。ごにょごにょで複雑なことをしなければ十分に高速なはずで、実際に、テストの速度は手法ごとにそれほど差はありません。
一方で、{\small W} を求めるための訓練では、手法ごとに速度差があります。用途によっては、選ぶポイントになるかもしれません。

異なる {\small W} と f(\cdot ) を選べば、異なるハッシングのアプローチが得られる。

LSH
f(\cdot ) 恒等関数
{\small W} p-stable分布からランダムに選ぶ
SpectralHashing
f(\cdot ) コサイン関数
{\small W} データの主軸方向
USPLH
f(\cdot ) 恒等関数
{\small W} 以下のように抽出する

入力： データX, ハッシュコード長K
X^0_{\ MC} = \phi , S^0_{\ MC} = \phi として初期化する
for k = 1 to K do
　　補正された共分散行列を求める
　　 　　M_k = \sum_{i=0}^{k-1}{ \ { \lambda^{k-1} \ X^i_{MC} \ S^i_{MC} \ X^i_{MC} }^T + \eta XX^T }
　　Mkの最初の固有ベクトル e を抽出する
　　　　 W_k = e
　　{\small W}_k での射影から仮のラベルを生成する
　　　　 X^k_{ \ MC} をサンプルし、S^k_{ \ MC} を構築する
　　残差を求める
　　　　 X = X - w_k { w_k } ^T X
end for


もちろん他にもいろいろ手法がありますが、最初の二つは有名ですね。
LSHが2004年、SpectralHashingが2008年、USPLHが2010年と、全体に新しい分野みたいです。

実装

LSH

まずこれを実装しました。
ランダムなベクトルをテストデータに掛けて二値化するだけ。簡単高速です。
が、やはり言われているように精度が悪い。いっぱいハッシュを作って精度を上げていくことも可能なのですが、そうするとデータベースが肥大化して、なんだかなーという事になります。もちろん、そのデメリットが呑めるようなシーンではアリです。
コード https://bitbucket.org/rubyu/hashing/src/4488f99834a0/java/Hashing/src/hashing/hashing/LSH.java

SpectralHashing

次にこれを実装しました。
LSHではランダムに生成していた射影ベクトルを、主成分分析で得るのがポイント。
LSHとは違って、データに依存した手法なので精度がよいです。ただし、LSHのように、並列化して精度を上げていくようなことはできません。
LSHより訓練、テスト共に複雑なことをやっているので遅いです。このうち、テストの遅さがやや気になったので、即決で採用はしませんでした。
コード https://bitbucket.org/rubyu/hashing/src/4488f99834a0/java/Hashing/src/hashing/hashing/SpectralHashing.java
ペーパーの著者がmatlabコードを公開してくれていたのでそれを参考にしています。（ライセンスは不明）

USPLH

SpectralHashingのアレンジです。
平均が0になるようにデータを前処理しておいて、固有ベクトルを求め、データを射影して、0で閾値化します。
このとき、0に近いマイナスの点と、プラスの点は、距離が近いのに、違うハッシュ値に割り当てられます。
また、同じ符号で、0に近い点と、０から遠い点は、距離が遠いのに、同じハッシュ値に割り当てられます。
この両方のエラーを、ビットを求めるごとに補正していくというのがUSPLHの手法です。
性能はだいたいSpectralHashingと同じぐらいでした。
訓練は非常に遅いですが、テストはLSH並に高速です。
訓練時間がデメリットにならない用途であることと、パフォーマンスとテスト時間のバランスから、今回はこれを採用することにしました。
コード https://bitbucket.org/rubyu/hashing/src/4488f99834a0/java/Hashing/src/hashing/hashing/USPLH.java
ペーパーてきとう訳 https://bitbucket.org/rubyu/hashing/src/4488f99834a0/paper/UPSLH.txt

テスト

訓練セット：１万件の画像から抽出した566839の64bit SURF特徴点。
テストセット： 150件の画像から抽出した9126の64bit SURF特徴点。
実際の用途で使われるような、ハッシュに対するクエリで、ハッシュ法の性能について調べる。
クエリ点からのユークリッド距離が、2パーセンタイル以内のものを正解とする。

Precision


だいたいペーパーと同じグラフ。ペーパーでは長いビットは切れてるけど、たぶんこんな感じに伸びてるはず。
PHよりUSPLHのほうがやや優れている。
LSHのグラフがギザギザなのは、一発の値（複数回取って平均していない）なので。

Recall curves


これもペーパーとだいたい同じ。

Training time


LSHと比べればSH、USPLH共に、ものすごく時間を食う。
LSHの4bitが跳ねてるのは、Javaのヒープ拡張のせい。（多分）

Test time


USPLHのテストはLSHと同じぐらい高速。

以上、グラフを見比べると、実装に大きな間違いはないかなーということが確認できました。

ペーパーとにらめっこで、昨年の終わりから、旅行やら骨折やらを挟んで約一月半ぐらいかかりましたが、そのかいはあったかなと。これを使ってぜひ何か新しいことをしたいと思います。

References

　　M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni,
　　　"Locality-sensitive hashing scheme based on p-stable distributions",
　　　in Proc. Symposium on Computational Geometry, 2004, pp.253-262.


　　Y. Weiss, A. Torralba, and R. Fergus, "Spectral hashing," in NIPS, 2008.
　　pdf: http://people.csail.mit.edu/torralba/publications/spectralhashing.pdf
　　matlab code: http://www.cs.huji.ac.il/~yweiss/SpectralHashing/sh.zip


　　Jun Wang, Sanjiv Kumar, Shih-Fu Chang,
　　　Sequential Projection Learning for Hashing with Compact Codes,
　　　InProc. of the 27th International Conference on Machine Learning (ICML), 2010.
　　pdf: http://www.sanjivk.com/SPLH_ICML10.pdf