Min-Max類似度のためのSketchSortの実装 (SketchSort-MinMax)を公開しました

SketchSortとは全ペアー類似度検索(与えられたデータセットからすべての類似するデータペアーを発見する問題)を高速に解くためのソフトウェアーで、以前に論文とソフトウェアーを公開しました。

論文: Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML), Tokyo, Japan, 2010.

ソフトウェアー: https://code.google.com/archive/p/sketchsort

ブロブ記事: http://d.hatena.ne.jp/tb_yasu/20100911/1284207891

以前のこれらのバージョンでは、コサイン類似度、Jaccard(Tanimoto)類似度、ユーグリッド距離を類似度の尺度としてつかっていました。


今回の新しいバージョンではMinMax類似度を類似度の尺度として用いています。 ではなぜ今SketchSortなのかといいますと、今携わっているプロジェクトで全ペアー類似度検索を解く場面がありまして、類似度としてはminmax類似度を使いたいという要望がありました。SketchSortでは内部でデータのランダムプロジェクションを行っているのですが、ちょうど今年のKDD'17でMin-Max類似度用のランダムプロジェクションを提案した論文が発表され、MinMax類似度を用いたSketchSortを実現できることがわかったので実装を行いました。因みにMinMax類似度のためのランダムプロジェクションはgeneralized consistent weighted samplingと呼ばれ、手法を解説した論文は以下となります。ご興味がある方は読んでみてください

Ping Li: Linearized GMM Kernels and Normalized Random Fourier Features, KDD'17
http://www.kdd.org/kdd2017/papers/view/linearized-gmm-kernels-and-normalized-random-fourier-features

MinMax類似度を用いたSketchSort-minmaxはgithubからダウンロードできます。
https://github.com/tb-yasu/sketchsort-minmax

化合物グラフのアライメントソフトウェア (PACHA: Pairwise Chemical Aligner)を公開しました。

Githubからダウンロードできます。

https://github.com/tb-yasu/pacha

PACHAは、2つの化合物を入力として、それらの間のアライメント出力します。アルゴリズムは去年のISMB'15のプロシーディングスにて発表した内容です。

Yoshihiro Yamanishi*, Yasuo Tabei*, Masaaki Kotera: Metabolome-scale de novo pathway reconstruction using regioisomer-sensitive graph alignments, ISMB/ECCB, 2015. (*joint first author) 論文へのリンク

化合物のアライメントや化合物のアライメントから化合物ペアーの特徴ベクトルの作成して機械学習の入力として使うことができます。応用として、代謝ネットワークの再構築やバーチャルスクリーニングに用いることができます。

KDD'16に参加しました

8月13日から17日にサンフランシスコで開催されたKDD'16に参加しました。

  • よくも悪くもTutorialの日とWorkshopの日が分かれて2日になりました。
  • Research Trackはオーラル+ポスターとポスターのみの採択に分かれていて、採択数はそれぞれ70と72で採択率18%(=142/784)ととても競争激しい。僕も運良く採択された印象。
  • 今年はResearch Trackのトピックを12に絞ったそうです。セッション内容もデータマイニングの代表的な分野に絞られていました。
  • ポスターセッションが夜19時から24時の間の5時間になり、どこかの機械学習の国際会議のポスター発表形式に近くなった。
  • 私のポスター発表はおかげさまで盛況でした。いかんせん時間が長く一人で発表していたせいか、何話したか覚えていない。名刺渡したしよしとする。
  • セッションがResearch TrackとApplied Data Science Trackに分かれているのですが、Research Trackが2セッション並列、Applied Data Science Trackも2セッション並列で、昨年よりApplied Data Science Trackのセッションの並列数が1つ増えて、プレゼンスも上がりました。
  • 全体的にグラフ処理に関する話が多い。時系列データ処理や異常検知のセッションに出ていたはずが、時系列に変化するグラフのデータ使っていつの間にかグラフ処理の話題になっていたり。
  • 昨年、面白い発表をしていた研究者がアカデミアから企業に移った研究者が多いせいか、好みの発表が減ってしまった印象。例えば、昨年のKDDではb-bit MinHashのLiとSmolaが同じセッションで発表していて、面白い発表の多いセッションだったのですが、今年はこのようなセッションがなかった。
  • 今年は動画による論文紹介がのせられるようになりました。優勝したのは論文“Why Should I Trust you?” Explaining the Predictions of Any Classifier"の紹介動画でプロが作ったCM並にすごい。https://t.co/kkt0iDLo4G 実際の発表も上手でした。
  • Discussion Forumを作って各論文の内容に関して議論できるようになっていました。
  • keynote speakerはアカデミアの人が例年より多い印象。たとえば、初日のkeynote speakerは数学者でいきなり理論の話をするのでみんな引き気味だった。
  • NECが企業ブースを出していたせいか日本人参加者が多かったです。
  • 全体的に発表レベルが高いことや参加者に有名人が多いので参加していて楽しい国際会議でした。

ERATO感謝祭SeasonIIIで発表しました

8月9日と10日に国立情報学研究所で開催されたERATO感謝祭SeasonIIIで発表してきました。
感謝祭のURLは、https://bigdata.nii.ac.jp/eratokansyasai3/ です。

ERATO感謝祭は様々なコンピュータサイエンス分野の有名国際会議に今年採択された論文の講演からなるワークショップです。ERATO内部の研究者の講演者が殆どですが、今年はERATO外で関連分野の研究者の講演も多くありました。私も今年KDDに採択されたということで講演者として呼んでいただきました。内容は以前ブログで紹介した文法圧縮されたデータ行列上PLS回帰モデルを学習するというものです。発表資料をslideshareに置きました。

ワークショップはどの講演も有名国際会議に採択された内容だけあってレベルが高く、様々な分野の話が聴けてとても良い刺激を受けました。

KDD'16に文法圧縮されたデータ行列上でのPLS回帰のモデル学習に関する論文が採択

データマイニング分野のトップの国際会議KDD’16に以下の論文が採択されました.

Y.Tabei, H.Saigo, Y.Yamanishi, S.J.Puglisi: Scalable partial least squares regression on grammar-compressed data matrices, accepted to KDD’16

内容は, PLS回帰モデルの入力となるデータ行列を文法圧縮してその上でスケーラブルにモデル学習するというものです.
機械学習法の殆の入力はデータ行列とそのラベル列です. 機械学習には, データ行列がメモリーの大半を占める機械学習アルゴリズムが存在して, もし, データ行列を圧縮して学習することができれば, 入力が巨大な行列でもメモリー効率良くモデル学習を行なうことができます.PLS回帰モデルにはそのような学習アルゴリズムが存在して, 圧縮されたデータ行列上でモデル学習を行なうことができます. しかし, モデル学習を行なうためにはナイーブには圧縮されたデータ行列をいったん解凍して学習を行わなければならず, そのようにするともとのデータ行列を保存するのと同じメモリーを消費してしまいます. よって, 省メモリーでモデル学習を行なうためには, 圧縮したデータ行列上で行列の要素にアクセスする手法が必要です. 本研究では, データ行列を文法圧縮して, 行列全体を復元することなく行列の要素にアクセスする手法を開発しています. これにより, PLS回帰モデルのメモリー効率の良い学習を可能にしています.

文法圧縮を用いる利点は, 多くのデータ行列に対して高い圧縮率を達成することができることに加えて, 可逆データ圧縮であることが挙げられます. データ行列を圧縮してモデル学習を行なう先行研究に, Liらが提案したb-bit minhashを用いる方法があります. しかし, b-bit minhashは不可逆データ圧縮であり, 元のデータ行列を復元することが不可能で, 学習後のモデルの解釈(どの特徴が予測に寄与しているか)ができません. 一方, 文法圧縮は可逆圧縮なので, モデルの解釈を行なうことができます.
実データを用いた実験と大規模データ向けの学習法(b-bit minhash, SGDなど)などの比較により, 圧縮率, 予測精度, モデルの解釈可能性の観点から文法圧縮の有効性を示しています.

2016/6/20更新
arXivに論文を置きました. http://arxiv.org/abs/1606.05031

ESA2015に論文採択しました

文法圧縮上でのaccess、rank、select操作に関する論文が、アルゴリズム分野のトップ会議ESA2015に採択されました。

Djamal Belazzougui, Patrick Cording, Simon J. Puglisi, Yasuo Tabei: Access, rank, and select in grammar-compressed strings, 23rd European Symposium on Algorithms (ESA), 2015.

内容は、以前このブログで紹介した論文です。
文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。

%6月20追加
早くもaccepted paper listが出ているようです。
http://algo2015.upatras.gr/esa/accepted.html

様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。

様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。本論文はデータ圧縮に関する国際会議 Data Compression Conference (DCC2015)に採択された論文でarXivから入手出来ます。

Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Alberto Ordóñez, Simon J. Puglisi, Yasuo Tabei: Queries on LZ-Bounded Encodings, Data Compression Conference (DCC), 2015. 論文へのリンク(arXiv)

提案法はLempel-Ziv(LZ)法に類似性がありその簡易版になっています。LZ法では各テキスト上の位置より前に出現する部分文字列の最長一致文字をテキスト上の位置と一致した部分文字列の長さで表現することに圧縮を行います。一方、提案法では入力テキストを固定長の部分文字列にチャンク分割したあとで、各チャンクに対して一致する部分列を探して、その位置を記録することにより圧縮を行います。このようにすると圧縮率は低下してしまいますが、提案手法では一致する部分列が見つからなかったチャンクに対して、チャンクをさらに短いチャンクに分割して一致する部分列を発見します。これをチャンクの最小単位まで再帰的に繰り返すことにより圧縮率の低下を抑えます。大きいチャンクからより小さいチャンクに一致文字列が見つからなかったチャンクを再帰的に分割することを繰り返すので、最終的には各ノードがチャンクをもつ木構造が出来上がり、これを保存します。木が持つノード数に対する圧縮率の上限を保証することもできます。

圧縮率に対する保証を持たせることができることの利点に加えて、提案法ではrank/select/access/LCAなどのFM-indexやcompressed suffix tree(CST)などの圧縮データ構造を実装するのに欠かせない操作を定数時間でサポートします。文法圧縮でも、これらの操作をサポートする方法が最近提案されていいますが、構文木の高さ(バランスされている場合、高さlog n, n : テキスト長)の時間がかかってしまうことを考えると、定数時間でこれらの操作をサポートしていることは、提案法のメリットと言えます。

提案法はチャンクをノードにもつ木ですので実装は比較的簡単で、ベンチマークデータ上でも実際に有用性が確認されています。ソースコード整理の都合上、実装の公開はもう少し後になりそうです。