« April 2009 | Main | June 2009 »

2009.05.25

貪欲な変数選択による最適化

最適化問題において、最適化対象の変数を最初は空に初期化して、関数値にもっとも効きそうな変数から順に最適化対象にGreedyに加えていく方法は変数の数が非常に多い場合(全ての部分文字列に特徴が対応するなど、そもそも列挙できないくらい多い場合など)に有効です。

詳細な中身は違いますが、grafting, column generation, cutting planeとかがこの枠組みに当てはまルと思います。

ここでのポイントは「効きそうな変数」を効率的に求めることができたら、圧倒的に速く最適化できるようになることです。別分野でデータマイニングの手法だとか、上限/下限だとかデータ構造とか何か技を持っている人は、ぜひチャレンジしてみてください。

で、私もやってます。という宣伝

・特徴(変数)が文書中の全ての部分文字列に対応する場合
"Text Categorization with All Substring Features", SDM 2009, D. Okanohara, J. Tsujii [poster(ppt)]

・特徴が基本素性の全ての組み合わせの場合
"Learning Combination Features with L1 Regularization", NAACL HLT 2009, D. Okanohara T. Tsujii. to appear

あといくつかできそうなのですが、実装が追い付かない。

とりあえず上の二つは今のライブラリに組み込む形などで公開したいとおもいます

| | Comments (56) | TrackBack (0)

2009.05.19

ohmm(オンラインEMによるHMM学習)をリリースしました

Ohmm-0.01をリリースしました

[Ohmm 日本語] [Ohmm English]

これは、以前のブログで書いた、オンラインEM法をそのまま素直に隠れマルコフモデル(HMM)に対し適用したライブラリです。

使う場合は、単語(アクセス履歴とかなんでもよい)に分けられているテキストを入力として与えれば、HMMによる学習を行い、結果を出力します。他で利用できるように、パラメータを出力したり、単語のクラスタリング結果を出力します。

HMM自体は、言語情報やアクセス履歴、生物情報(DNA)といったシーケンス情報において、前後の情報を用いて各要素をクラスタリングしたい場合に用います。

本ライブラリの特徴はオンラインEMの特徴通り、従来のEMよりも速く収束します。一応標準的な最適化手法(スケーリング、スパースな期待値情報の管理)もいれているので、そこそこ高速に動きます

速度的には100万語、隠れ状態数が40ぐらいで1回のループが10秒程度です。正式な実験ではないですが1億語ぐらいまでが一台で1~2時間ぐらいで収束します。

歴史のある隠れマルコフモデルはいろいろな変種があるので、それらも暇なときに実装しようかなと思います

| | Comments (1069) | TrackBack (0)

« April 2009 | Main | June 2009 »