研究に直接関係ないタイプの労働をしていると、先端の研究を追いかけるのが困難になってきます。 なんといっても論文を読む時間がとれないので有識者の記事やらスライドやら書籍やらに頼ることになるのですが、とはいえ1次ソースであるところの論文を確認し…

機械学習の本をおすすめする記事をいろいろ書いてきたけど、純粋に自分が活用している本について書いたことがなかった気がしたので書いておきます。必ずしもおすすめではないかもしれません。ベイズ1冊、DL1冊、凸2冊の計4冊。

社内の有志で機械学習や数学の勉強会をいくつかやっています（私以外の方が主催しているものもある）。とくに理系ではない方も参加されていますが、きちんと頑張ればだんだん機械学習ができるようになるということがわかってきたのでメモしておきます。 なお…

"トピックモデルによる統計的潜在意味解析"という有益な書物が発売されたので読んでみました。 それなりに高度な話題を簡潔に解説した素晴らしい本で、これを読んだことでよくわかっていなかったCollapsed Gibbs Sampling版のLDAを実装することができました。…

AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました。 実装がとても簡単で、ハイパーパラメータも論文に推奨値が書いてあるのが良いですね。 持っておかないといけないパラメータの数は(たぶん)AdaGradと同じです。https://github.com/echize…

機械学習では、データがどのクラスに属するかを識別するという問題が基本的です。 この識別問題は線形識別器というモデルを使うことで解くことができます。 この記事では、実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説を行います。AdaGrad+RDAの詳細…

AdaGrad(Adaptive Gradient)というオンライン学習のアルゴリズムを実装しました。 https://github.com/echizentm/AdaGrad 論文: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization(http://www.magicbroom.info/Papers/DuchiHaS…

最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。 この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明…

@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。 文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使っ…

「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとって…

Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。 …

一年くらい前にウェーブレット行列のrank計算を2倍高速化する方法を思いついた。 詳細はDSIRNLP発表資料(http://ja.scribd.com/doc/102636443/Wavelet-Matrix)のP.56以降。 本当にイケているのか自信がなかったのでウェーブレット行列論文のfirst authorであ…

機械学習界隈では多変量正規分布のKLダイバージェンスの導出は自明らしく、とくに説明もなく「はいこうなりますね〜簡単ですね〜ははは〜」みたいな感じで軽く流されて死にそうになる。 軽く流されると私のように死んでしまう人もいるかもしれないので導出方…

情報理論でエントロピーといえば確率変数が持つ情報量の期待値のこと。例えば P(x1) = 1/2, P(x2) = 1/4, P(x3) = 1/4という分布があったらエントロピーは 1/2 * lg2 + 1/4 * lg4 + 1/4 * lg4 = 1/2 * 1 + 1/4 * 2 + 1/4 * 2 = 3/2 = 1.5なので平均1.5ビット…

Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。 Compress data more densely with Zopfli - Google Developers Blog

ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。 とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ち…

「入門機械学習」を献本していただきました。ありがとうございました。 というわけで早速読み終わったので感想を書いておく。

「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。

DSIRNLP#03 で「ウェーブレット行列 最速攻略」の発表をしました。 詳しくは資料を見ていただけると良いです。 台風にぶつかってしまいどうなることかと思いましたが、@overlastさんの配慮で無事発表できました。ありがとうございました。 それから準備あま…

9/30(日)に開催予定のDSIRNLP#03で発表予定の「ウェーブレット行列 最速攻略」の予告編資料を作成したので公開しておきます。 ウェーブレット行列とはそもそもどんなものなのかを解説した資料です。この資料によってウェーブレット行列に関心をもつ人が増え…

9/30(日)に開催予定のDSIRNLP#03でウェーブレット木について発表しません。

ごく一部で話題沸騰中のまじぱないデータ構造、ウェーブレット行列を用いた検索アルゴリズムであるFM-Index。このFM-Indexは以前私が実装したShellinfordというライブラリから利用可能になっている。さらにここで用いたウェーブレット行列にはオリジナルには…

なんかすごい高速化できた気がする。

FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。

話題のウェーブレット行列(Wavelet Matrix)を自作のFM-Indexライブラリ、shellinfordに組み込んでみた。 ウェーブレット行列はウェーブレット木と互換性があるので、ウェーブレット木の代表的な適用例であるFM-Indexでも当然利用可能。 というわけでとりいそ…

久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能と…

ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。 簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブ…

最近サザエさんとキュアピースのじゃんけん対決が話題になっている。 じゃんけんポンで日曜日 またこれに関連して「サザエさん ジャンケン学」というサイトが注目を集めている様子。 サザエさん ジャンケン学 このサイトによるこれまでの予測的中率は44.7％…

先日公開したShellinfordという文書検索ライブラリにAutotoolsを導入してみた。 ShellinfordはFM-Indexというデータ構造を採用している。このデータ構造は文書をBurrows-Wheeler変換してウェーブレット木でインデックスすることでSuffixArrayと同等の機能を…

IME本の効果でLOUDSの認知度が高まってきた気がする。が、一方で難しいという意見もチラホラある様子。 というわけでLOUDSをどこまでわかりやすく説明できるか？ということに挑戦したくなったので記事を書いてみるよ。