機械学習コミュの質問 online algorithm & latent variable

学習用のサンプルを一回しか見ない online algorithmで、EMのように latent variable を学習できるもの、ってどんなのがあるんでしょうか? 論文や教科書を教えてもらえると嬉しいです。

コメント(12)

最初
全て
最新の40件

Nobuyukiさん＞またまた書き込ませていただきます。online algorithmは僕もかなり興味があります。もしかすると、博士論文もonline algorithmに関するものになる可能性があるんです。

やはりEMのような手法では一度、バッチ的に与えられた訓練データを用いて学習が終了した後に、追加的に与えられたデータを用いて学習すると以前に学習したパラメータは壊れてしまう
ような気がします。（表現が分かりにくくてすいません）

しかし音声の分野では、多数の話者の音声データから作成されたHMMを特定の話者を良好に認識できるように修正する技術があります。（話者適応技術）
これらの研究の中で、学習用のサンプルを一回づつ入力しながらHMMのパラメータを逐次的に修正するといったような論文を見かけたような気がします。

online algorithmとはこのようなものでしょうか？
見当違いだったらすいません。

[2] mixiユーザー 03月10日 05:57

> 学習用のサンプルを一回づつ入力しながらHMMのパラメータを
> 逐次的に修正する
...
> online algorithmとはこのようなものでしょうか？

そうです。その論文の情報が分るようでしたら、教えてもらえると嬉しいです。

例えば、winnowとかも onlineです。
http://www.cs.cmu.edu/afs/cs/usr/avrim/www/Papers/survey.ps

最近の論文で大事そうなものは、voted perceptronや、
http://www.cs.princeton.edu/~schapire/papers/FreundSc98.ps.Z
http://people.csail.mit.edu/mcollins/papers/tagperc.ps
(HMMみたいに構造がある場合の voted perceptron)

使用例
http://www.cis.upenn.edu/~feisha/pubs/shallow03.pdf
(比較対象の batchにした voted perceptronも悪くない性能)

OnlineであるにもかかわらずMax Marginができるとか、
http://jmlr.csail.mit.edu/papers/volume3/crammer03a/crammer03a.pdf
http://www.cs.huji.ac.il/~singer/papers/pa_long.pdf

使用例
http://www.seas.upenn.edu/~ryantm/papers/nonprojectiveHLT-EMNLP2005.pdf
(HMMのように、Forward-Backward のアルゴリズムがないため、これまた online learningを batchにして使う)

他にも限られた記憶容量の使い方が巧いとか、
http://books.nips.cc/papers/files/nips18/NIPS2005_0192.pdf

online algorithmを何回も走らせて作ったbatch と、そうでない batchの algorithmの理論的な違いとか (論文忘れました)、いろいろあります。さすがに同じ、と言うわけではないが、かなり良いところまで行ける感じがします。

自分としては記憶容量は今のところ問題にならないことが多い気がするんですが、サンプルの分布が分らなくても学習が出来るのがよいと思います。でも、EMみたいに、latent variable を学習できるオンラインの学習方法は見たことがなくて、今探しているところなんですよ。

[3] mixiユーザー 03月10日 08:07

どのくらい遡ればオリジナルに行き着くのかはわからないですが、on-line EMは、Googleで検索すればたくさんでてきますね。基本的に、例を一個づつ処理できる学習アルゴリズムがあるなら、
・例をひとつとって、現在のモデルで隠れ変数を推定
・その推定に基づいてモデルをアップデート
でいいんではないでしょうか。

それとも、"latent"っていうと、特定のモデル
http://citeseer.ist.psu.edu/hofmann99probabilistic.html
http://citeseer.ist.psu.edu/blei03latent.html
あたりを指していますか？

[4] mixiユーザー 03月10日 14:13

kashiさん

今、ぐーぐるで見つけたKevin Murphy のノートで勉強してたんですが、
http://www.cs.ubc.ca/~murphyk/Teaching/CS540_Fall05/LectureNotes/lec10.pdf
けっこう基本的な質問だったみたいですね。どうもありがとうございます。

> ・例をひとつとって、現在のモデルで隠れ変数を推定
> ・その推定に基づいてモデルをアップデート

おお、そういわれてみると、EMってそんな感じのアルゴリズムじゃないですか。 EMって、見たことがある証明は、KL Divergenceを使ってどうのこうのっていうのしかなくて、確率じゃない、一番ありそうな隠れ変数の値を見つけてhard assignemtするだけで大丈夫だったって知りませんでした。クラスタリングのk-meansはまさにこれ、ってことですよね。なんか、semi-suervised の self-trainingにも似ているみたいな。。

これでconvergeするって言うのが驚きです。
http://citeseer.ist.psu.edu/neal98view.html
よさげな論文みつけたので読んでみるつもりです。

> それとも、"latent"っていうと、特定のモデル

いや、普通の隠れ変数ですが、上の二つのlatentがつくモデルはどちらもインパクトが大きいので、勉強しておかないといけないなと思ってます。

[5] mixiユーザー 03月13日 22:30

そのLのつくモデル、言語処理学会のチュートリアルで紹介されていました。
資料は数日中に
http://www.milab.is.tsukuba.ac.jp/~myama/pdf/topic2006.pdf
におかれるとのことです。

[6] mixiユーザー 03月17日 16:04

kashiさん、
おお、ありがとうございます。よさそうですね。読んでみたいと思います。

[7] mixiユーザー 04月20日 18:49

Nobuyukiさん＞ものすごい遅くなりましたが、最近出たOnline EMの論文を見つけました。
http://www.umoncton.ca/greti/papers/Online%20EM%20algorithm%20for%20mixture%20with%20application.pdf

しかも最後の方にHMMのパラメータ推定法であるBaum-Welchに応用も検討していると書いてあります。よってかなり気になるところです。

Kashiさん＞素朴な質問なんですが、
・例をひとつとって、現在のモデルで隠れ変数を推定
・その推定に基づいてモデルをアップデート
していくと、その1つの例(SAMPLE)に特化したモデルが構成されてしまうのでしょうか？そうであるなら、アップデートする前に学習したテータ群に対しての識別率が落ちてしまうような気がします。以上よろしくお願いします。

[8] mixiユーザー 04月22日 01:52

＞・その推定に基づいてモデルをアップデート
の部分ですが、その1つの例のみに基づいてモデルを推定するということではなく、これまでのモデルを「ちょっとだけ」更新するという感じだと思います。
たとえばですが、毎時間tにx_tが与えられるとして、その平均を推定しましょう、という話だとすると、時刻tでの平均m_tは、
m_t := ( m_{t-1} * (t-1) + x_t )/t
によってアップデートできますよね。
あるいは、「昔のことは忘れる」タイプの更新なら
m_t := (1-a) * m_{t-1} + a * x_t
(0<a<<1)
みたいな感じでしょうか。

[9] mixiユーザー 04月23日 11:32

kashiさん＞ありがとうございます。
上の例、大変分かりやすいです。
aのような忘却パラメータを用いて、忘れる度合いを調整すればよいということですよね？

PS　Kashiさんの｢CRFとHMMについて｣講演された時のスライドを読んで、勉強させていただきました。これについてもありがとうございます。

[10] mixiユーザー 04月24日 08:24

＞最近出たOnline EMの論文を見つけました。

どうもありがとうございます。

＞忘却パラメータを用いて、忘れる度合いを調整すればよい

上の例では、忘れる度合を調整しなくても、正しいパラメータの推定がされていますが？　古いサンプルなしで、新しいサンプルだけを見たにもかかわらず（古い平均値を少し更新するだけで）全てのサンプルに対する正しい平均値がでています。

新しいサンプルを見て、古いモデルをちょっとだけ更新した結果、ひとつのサンプルだけではなく、サンプル全体に対してモデルを特化できる好例を示してくれたんだと思います。　

[11] mixiユーザー 04月25日 02:10

Nobuyukiさん＞なるほど、理解しました。online EM
(もしくはこのようなonline可能な手法)を用いてVISIONについての応用問題を考えて行きたいと思います。ありがとうございました。

[12] mixiユーザー 05月06日 09:23

online algorithm も、可能である場合には batch に直して使ったほうが性能が高いです。

batchに直したといっても、サンプルをひとつずつ見るのは変わっていませんが、voted perceptronがその好例です。　

online -> batch conversionをどうやるかについての論文を付け加えておきます。

http://www.cs.huji.ac.il/~singer/papers/o2b_nips.pdf

ログインすると、みんなのコメントがもっと見れるよ