サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
都知事選
tb-yasu.hatenadiary.org
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/1284207
8月9日と10日に国立情報学研究所で開催されたERATO感謝祭SeasonIIIで発表してきました。 感謝祭のURLは、https://bigdata.nii.ac.jp/eratokansyasai3/ です。 ERATO感謝祭は様々なコンピュータサイエンス分野の有名国際会議に今年採択された論文の講演からなるワークショップです。ERATO内部の研究者の講演者が殆どですが、今年はERATO外で関連分野の研究者の講演も多くありました。私も今年KDDに採択されたということで講演者として呼んでいただきました。内容は以前ブログで紹介した文法圧縮されたデータ行列上PLS回帰モデルを学習するというものです。発表資料をslideshareに置きました。 Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrice
様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。本論文はデータ圧縮に関する国際会議 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に関する論文を公開しました。ヘルシンキ大のDjamal BelazzouguiさんとSimon J. Puglisiさんとの共著論文です。arXivからダウンロードできます。 Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei: Rank, select and access in grammar-compressed strings 論文へのリンク(arXiv) 内容はタイトルが示す通り文法圧縮されたテキスト上のrank/select/accessに関するものです。一般の文字列上のrank/select/access操作はFM-indexを代表とするさまざまなデータ構造を実装する際の重要なデータ構造であることは良く知られています。これらの操作を実現する代表的なデータ構造にWav
今年の実験的アルゴリズムに関する国際会議SEA2014に採択された論文をarxivにて公開しました。内容は文法圧縮の索引化に基づく高速クエリー検索です。 Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto: Improved ESP-index: a practical self-index for highly repetitive texts, 13th International Symposium on Experimental Algorithms (SEA), 2014. 論文へのリンク
東大で開催されたNIPS2013読み会で発表させていただきました. http://connpass.com/event/4728/ 参加者60人と大盛況で, 機械学習の人気の高さを再確認しました. 僕は, Scalable graph kernels for continuous attributesというタイトルの論文を発表しました. 要点は ノードに実数値ベクトルをもつグラフに対するGraphHopper Kernelを提案 類似度は2つのグラフに存在する同じ長さの最短路上のノードの類似度の和で定義 式変形により最短路におけるノードを通過する回数に関するforward-backward計算に帰着 実際のグラフに対しては, ノードの数の2乗で計算可能 高速かつ高精度 です. 下は発表スライドです. NIPS2013読み会: Scalable kernels for graphs with
年が明けて2014年の1月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。 はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます. 文法圧縮には2つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズム
暑い日々が続きますが、いかがお過ごしでしょうか? 早いもので2013年もう8月ということでだいぶ遅いですが2013年の前半の成果を振り返ってみたいと思います。幸いにも2013年の前半に4本論文を出す事ができました。内分けは、データマイニング・機械学習1本、バイオインフォマティクス1本、 文字列処理2本となります。以下では1つ1つ論文の内容を簡単に紹介していきたいと思います。 Yasuo Tabei, Akihiro Kishimoto, Masaaki Kotera, Yoshihiro Yamanishi: Succinct Interval Splitting Tree for Scalable Similarity Search of Compound-Protein Pairs with Property Constraints, 19th ACM SIGKDD Conferenc
以前のブログで紹介した簡潔マルチビット木のc++による実装 (Succinct Multibit Tree (SMBT)) を公開致しました。ソフトウェアーはgoogle codeからダウンロードすることができます。 http://code.google.com/p/smbt/ SMBTは去年のWABIで発表した内容にもとづいています。 簡潔マルチビット木に関するブログ記事 : http://d.hatena.ne.jp/tb_yasu/20120808/1344415559 論文 : Yasuo Tabei: Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches, Workshop
SPIRE2012で発表したメモリー効率の良い文法圧縮のための可変長コードに関する論文を公開しました。 Y.Takabatake, Y.Tabei, H.Sakamoto: Variable-Length Codes for Space-Efficient Grammar-Based Compression, Symposium on String Processing and Information Retrieval (SPIRE), Cartagena, Colombia, 2012. Link to the PDF 上記の論文に基づくオンライ文法圧縮(online LCA)のC++による実装(olca++)を公開しました。 下のサイトからダウンロードできます。 https://code.google.com/p/olca-plus-plus/ 文法圧縮のアルゴリズムは@marugo
大規模グラフ類似度検索のためのソフトウェアーgwtの内部で使われているwavelet木の実装をwavelet行列に変更しました。 下のサイトからgwt-wm-3.0.0.tar.bz2をダウンロードできます。 http://code.google.com/p/gwt/ gwtに関する説明は以前のブログ記事を参照してください。 gwtについての解説記事 wavelet行列に関する説明は論文とechizen_tmさんの記事を参照して下さい。 http://d.hatena.ne.jp/echizen_tm/20120801 Francisco Claude and Gonzalo Navarro.The Wavelet Matrix.Proc. SPIRE'12, pages 167-179. LNCS 7608
8月6日,7日に北海道大学で開催された、機械学習とバイオインフォマティクスのワークショップMLAB2012にて研究発表を行いました。 http://www.cris.hokudai.ac.jp/takigawa/mlab2012/ 発表内容は大規模化合物フィンガープリントデータベースのための新しい簡潔データ構造を提案するというものです。フィンガープリントとは、化合物の部分構造や性質をバイナリーのベクトルとして表現したのもで、自然言語処理におけるbag-of-words (BOF)と同じデータ表現です。化合物類似度検索分野ではフィンガープリントの類似度として、Jaccard (Tanimoto)類似度が標準として使われています。 2009年にKristensenらが高速な類似度検索を可能にするマルチビット木(Multibit Tree)というデータ構造を提案しました。マルチビット木とは、近年
2012-02-04の記事 http://d.hatena.ne.jp/tb_yasu/20120204 のESPによる文法圧縮の実装に関して問い合わせが数件ありましたのでソースコードを公開しました。 今後のアップデートのしやすさを考慮してgithubにアップロードしました。 https://github.com/tb-yasu/GrammarCompression 現在のところ、文章から文法を構築する機能と、文法から文章を復元する機能をサポートしています。 esp-0.0.1.tar.bz2をダウンロードしましたら、tarで解凍してください。 tar -xzvf esp-0.0.1.tar.bz2 解凍出来ましたらmakeでコンパイルできます。 cd esp-0.0.1/src make 文章から文法を構築する際は、esp-compressコマンドを使用します。 ./esp-compre
ALSIPの時に聴いて気になっていた文法圧縮法Edit Sensitive Parsing (ESP)を実装しました。 文法圧縮とは、与えられた文章から曖昧でない文脈自由文法*1をもとめることにより圧縮する手法です。文脈自由文法のサイズは、導出規則の右辺の終端記号と非終端記号の個数の総和として求められますが、サイズ最小の文脈自由文法を求める問題はNP-Hardとして知られています。これまで近似解を求める手法が提案されてきましたが、文書長 n に線形なメモリが必要で実用的ではありませんでした。例えば、有名な文法圧縮法の一つであるRePairはおおよそ5nのメモリが必要です[1]。2002年にCormodeら[2]が、文書長に依存しないメモリーで文脈自由文法を求める手法(Edit Sensitive Parsing (ESP))を提案しました。必要なメモリーは、文脈自由文法のサイズをgとしたと
人工知能学会誌の私のブックマークに簡潔データ構造という題で記事を書きました。私のブックマークは研究者が自らの研究をする中で普段使っているWeb上のリソースを公開するための記事です。今までいろいろな研究者が記事を書かれています。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/ 幸いにも今回は、私が執筆の機会を頂くことができたので情報検索などでよく使われている簡潔データ構造のリソースについてまとめてみました。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/26-6.html 記事を書いてみて思ったことは、ライブラリの充実により実際の場面で使いやすくなっていることと、多くのエンジニアや研究者がブログなどをつうじて記事を公開してくださっているおかげでこの分野が日本語で勉強しやすくなってい
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距離に基づく手法に拡張しました。このため、以前は与えられた任意の2点間のCosine距離をハミング距離で保存したままバイナリ文字列へとハッ
5月24日から27日に中国深センで開催されたPAKDD2011で、以前のブログで紹介した線形グラフのマイニングアルゴリズム(LGM: Linear Graph Miner)について発表しました。 下はexcursionの写真. 発表スライドをアップしました。 Lgm pakdd2011 public View more presentations from Yasuo Tabei
昨日のブログで紹介した大規模グラフの類似度検索のC++による実装(gWT:graph-indexing wavelet tree*1 )を公開しました。googlecodeよりダウンロードすることができます。 初めに、gWTはgwt-buildによりグラフデータベースの索引付けを行います。以下にサンプルを示します。 ./gwt-build -iteration 2 ../dat/mutagen.gsp index この例では、mutagen.gspが入力のグラフデータベースファイルで、indexが索引の出力ファイルです。-iterationオプションでは、Weisfeiler-Lehman手続きのイテレーション回数を指定します。ここでは2回に指定しています。入力ファイルの形式は、各行がノードラベルまたはエッジラベルとノードとの接続関係を表現します。各行の意味は以下を参照してください。 "t
4月28日から4月30日に開催されたデーターマイニングの国際会議 SIAM Conference on Data Mining (SDM2011)にてwavelet木を用いた大規模グラフデータベースの高速類似度検索手法について発表してきました。 Yasuo Tabei and Koji Tsuda: Kernel-based Similarity Search in Massive Graph Databases with Wavelet Trees, Eleventh SIAM International Conference on Data Mining (SDM), Arizona, USA, 2011. Link to the paper 本研究では大規模グラフデーターの索引による高速な類似度検索手法を提案しました。近年、グラフデータベースに登録されているグラフの数は大規模化してい
データマイニングの国際会議 PAKDD2011に線形グラフのマイニングアルゴリズムに関する論文がアクセプトされました。本研究は、PFIの岡野原さん(@hillbig)、産総研の廣瀬さん、津田さん(@kojitsuda)との共同研究です。 論文をarxiv.orgにアップしました。 LGM: Mining Frequent Subgraphs from Linear Graphs, Yasuo Tabei, Daisuke Okanohara, Shuichi Hirose, Koji Tsuda, The 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD2011), link to the paper 線形グラフ(Linear Graph)とは、通常のグラフの頂点に順序がついたグラフです(下
FM-indexのC++による実装 FM-index++を公開しました。 http://code.google.com/p/fmindex-plus-plus/ FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばかりでなくゲノム検索[5]など、いろいろなところで応用されています。今回は、クエリーに対する検索操作の内、exact検索、ハミング距離による検索、編集距離による検索の3つを実装しました。それぞれの計算時間は、qがクエリーの長さとすると、exact検索がO(q)時間、 ハミング距離による検索がO(q^σ)時間、編集距離による検索がO((q \times q)^σ)時間です。よって、4文字種のDNAや20文字種のタンパク質など、文字種類数が少ない対象にはハミング距離
東京工業大学の杉山研究室でSketchSort法に関する講演をさせていただきました。杉山研はいろいろな国からの留学生が多くゼミでの公用語は英語だそうです。企業と同様に大学の研究室単位でもグローバル化しているようです。ツッコミも激しかった。杉山研での発表のためにスライドを少し修正したので再アップしました。またまた英語で発表したので英語のスライドになっております。 Sketch sort sugiyamalab-20101026 - publicView more presentations from tbyasu. 今後の予定 11月4日〜6日に行われるibis2010にて以下のタイトルでポスター発表します。 「大規模化合物のスケッチ表現によるクラスタリング」 http://ibis-workshop.org/2010/index.html SketchSort法を2千5百万からなる化合物デ
お茶の水女子大学にてSketchSort法に関する講演をさせていただきました。 スライドをアップしました。英語で講演したので英語のスライドになっています。 Sketch sort ochadai20101015-publicView more presentations from tbyasu. 下はお昼に頂いた仕出しハンバーガー。
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法は、データー点の集合が与えられたら、集合中の2点間の距離がある閾値以内のペアー(近傍ペアー)を全て求める問題(全点間類似度検索)を高速
Locality Sensitive Hashing(LSH)とは、ベクトルとして表現されたデーターの集合を入力として、それらの2点間の距離を保存したまま、ハミング距離に基づく文字列の集合に射影する技術です。コサイン距離[1]、ユーグリッド距離[2]に基づくものや、機械学習法を応用した、semantic hashing[3], spectral hashing[4], kernelized LSH[5], その他[6][7][8]、現在までに多くの手法が提案されています。この背景には、Googleが、昔に提案されたLSHが、ニュース記事の推薦システムで使えることを示した[9]のきっかけに、現在、推薦システム、画像検索、文章のクラスタリング[10]など、色々なシステムや研究の場面で利用されています。 理論的な収束の保証があるという意味で、オリジナルのコサイン距離ベース[1]の手法が良いのです
SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。 アルゴリズムは、マルチソーティングという手法に基づきます。 詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ
8月と9月の二ヶ月間, Preferred Infrastructure(略してPFI)のインターンに参加してきました。 PFIは、主に情報検索やレコメンデーションソフトウェアーを開発しているベンチャー企業です。PFIについては、http://preferred.jp/index.htmlを参照してください。 7月の終わりにインターンの募集があります。インターンに応募すると、まず書類選考があり、それに通過すると面接があります。面接時間は約30分で、2つの問題が出題されます。今年は、以下の問題が出題されました。 1.現在の情報検索のランキングについて調べて、その利点と欠点を述べよ。 2. 整数の集合を格納するデーター構造、及び、検索アルゴリズムを記述せよ。 1に関しては、事前に出題(といっても5日ぐらい前)されます。2に関しては、その場で出題しその場で解きます。問題からわかるとおり、面接では
このページを最初にブックマークしてみませんか?
『Yasuo Tabeiの日記』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く