MinHashを用いたSketchSort

機械学習

MinHashを用いたSketchSortの論文がMolecular Informaticsに採択されました。
論文は下のサイトからダウンロードすることができます。

Yasuo Tabei and Koji Tsuda: SketchSort: Fast All Pairs Similarity Search for Large Databases of Molecular Fingerprints, Molecular Informatics, 2011. Link

ソフトウェアをgoogle codeにて公開しています。

本論文では、以前紹介したCosine距離に基づく高速な全点間類似度検索法(SketchSort)をJaccard-Tanimoto距離に基づく手法に拡張しました。このため、以前は与えられた任意の２点間のCosine距離をハミング距離で保存したままバイナリ文字列へとハッシュするLocality Sensitive Hashingの代わりに、Jaccard-Tanimo距離を保存するMinHash[1,2]を用いています。
MinHashの解説はPFI Research Blog - MinHashによる高速な類似検索とNIPS読む会の瀬々先生の資料に詳しいのでそちらに譲り、ここでは本論文で工夫した点を述べます。MinHashは、入力のバイナリベクトルのJaccard-Tanimoto距離をハミング距離で保ちつつ文字列へハッシュする手法でした。元々のMinHashではハッシュされた文字列の各文字は入力ベクトルの次元種類数分の値を取り、入力ベクトルの次元が高い場合(Webページなどは数万から数億次元)は、入力ベクトルの次元数×ハッシュした文字列長のメモリを消費してしまい実用的ではありませんでした。そこで、Liら[1,2]は本来のMinHashの性能を保ちつつメモリを削減する手法(b-bit MinHash)を提案しました。本来のMinHashが持っている衝突確率(2つのベクトルのJaccard-Tanimoto距離がある閾値以内の時、２つのハッシュされた文字が同じ文字である確率)も近似的に彼らの論文中[1,2]では導出されています。しかし、衝突確率の証明の中で、入力のベクトルの次元がとても高いとき(文章など)を仮定していて、それ以外の対象(化合物など)にはこの仮定はかならずしも当てはまらないので、衝突確率を次元の低い対象に使うことができませんでした。この衝突確率はSketchSortを構成する上でとても重要で、これがあるおかげでデータ中の距離の近い２点を見逃す確率(False Negative率)の上限をバウンドすることができます。そこで提案法では入力ベクトルの次元が高くない場合でも使える衝突確率を導出しています。このおかげでFalse Negative率をバウンドしつつ高速にデータ中からJaccard-Tanimoto距離がある閾値以内の２点をもとめることができます。

参考文献
[1] b-Bit Minwise Hashing”, Ping Li, Arnd Christian Konig, WWW 2010
[2] b-Bit Minwise Hashing for Estimating Three-Way Similarities, Ping Li, Arnd Christian Konig and Wenhao Gui, NIPS 2010