研究紹介 - SketchSort（スケッチソート）法

機械学習

SketchSort(スケッチソート)法の論文が ACML2010にアクセプトされました。今年も採択率30%の難関でした。

http://sugiyama-www.cs.titech.ac.jp/ACML2010/
Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML2010), Tokyo, Japan, 2010. Link to the paper

SketchSort法は、データー点の集合が与えられたら、集合中の２点間の距離がある閾値以内のペアー(近傍ペアー)を全て求める問題(全点間類似度検索)を高速に解くための方法です。この全点間近傍検索問題には、コピー発見、クラスタリング[1]、画像中の特徴的な領域発見[2]、半教師あり学習[3]、生物学的配列データーからのモチーフ発見[4]など、さまざま応用があります。ウェブや計測技術の発展にともなって、データーが大規模化してきていますが、SketchSort法は入力データー点の数が数百万または数億でさえも高速に近傍ペアーを求めることができます。計算量は入力データー点と出力データー数の線形です。

手法の概要

基本的なアイディアは、Locality Sensitive Hashing(LSH)(http://d.hatena.ne.jp/tb_yasu/20100513/1273754177)とmultiple sorting method(MSM)(http://d.hatena.ne.jp/tb_yasu/20091107/1257593519)の組み合わせです。まず、入力のデーター点をLocality Sensitive Hashingにて、２点間のハミング距離で保つように固定長のバイナリーの文字列(sketch)に射影します。その後、射影したバイナリーの文字列から以前このブログにて解説したMSM(http://d.hatena.ne.jp/tb_yasu/20091107/1257593519)にて近傍ペアーを全列挙しています。実際には、重複したペアーを出力しないよう、重複除去などの工夫も手法の中に取り入れています。このアルゴリズムは近似アルゴリズムなので、本当のペアーを見逃す可能性（False Negative）があるのですが、そのようなペアーの期待値を理論的に見積もっています。これにより見逃すペアーの期待値をある閾値以下に抑えて手法を動作させることができます。

SketchSortの簡単な使い方
ソースコードをgoogle codeにて公開しています。

http://code.google.com/p/sketchsort/

簡単な使い方は、ソースをダウンロードして解凍した後、

tar -xvzf sketchsort-0.0.6.tar.gz
cd sketchsort-0.0.6/src
./sketchsort -auto -centering -cosdist 0.01 -missingratio 0.00001 sample.txt outputfile

で動作させることができます。sample.txtは入力ファイルで、outputfileは出力ファイルです。
オプションの意味は、

  • auto: 指定したcosine距離の閾値とmissing edge ratioから、それら以外のパラメーター(ハミング距離の閾値、ブロック数、チャンク数)を自動的にチューニングします。
  • centering: データー点を0を中心に移動します。（手法の動作のために必要）
  • cosdist: コサイン距離の閾値を指定します(0〜2を指定)。（ここでは、コサイン距離が0.01以下のすべてのペアーを求めます。）
  • missingratio: false negativeの期待値の上限をしています)。（０以下の値を指定。ここでは、0.00001以下に抑えています。）

cosdistが小さいほど、missingratioが大きいほど、動作は高速です。

参考文献
[1]M. Hein, J.-Y. Audibert, and U. von Luxburg. Graph Laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 8:1325-1368, 2007.
[2]G. Kim and A. Torralba. Unsupervised Detection of Regions of Interest Using Iterative Link Analysis. In Adavances in Neural Information Processing Systems, 2010
[3]D. Zhou, O. Bousquet, J. Weston, and B. Scholkopf. Learning with Local and global consistency. In Advances in Neural Information Processing Systems. pages 321-328. MIT Press, 2004
[4]J.Weston, A. Elisseeff, D. Zhou, C. Leslie, and W.S. Noble. Protein ranking: from local to global structure in the protein similarity network. Proceedings of the National Academy of Sciences of USA, 101(17):6559-6563, 2004.