« tx bepの内部技術の発表 | Main | マルコフ情報源上で次の文字を予測する »

2007.11.05

L1正則化付LLMの双対化

タイトルの内容で現在開催中のIBIS 2007で発表してきました。論文[pdf] 発表パワポ [ppt]

タイトルからしてよくわからない人もいると思うので”タイトル”を簡単に説明します。

まず LLM (Log Linear Model)というのは指数型分布族と一般に呼ばれるのですが、p(x; w) = exp(wx - Z'(w)) x∈R^m, w ∈R^mの形をしている確率分布です。自然言語処理などでは最大エントロピーモデルとかCRFとかいろいろ名前を変えて使われているモデルです。いろいろな確率分布(例えば正規分布)がこの形に属します.Log-linearというのはこの確率分布の対数をとると、log p(x) = wx - Z'(w) と線形の式がでてくるところからそう呼ばれています。

次は、L1正則化です。やりたいことは訓練データを利用して確率分布を決定するパラメータを推定することです.指数型分布族の場合はwを求めることになるのですが、オーバーフィットの問題が常につきまといます。例えば高次の多項式で二次元中のn点を通る関数を求めようとすると,がたがた振動するようなことがおきますが、今回推定する場合もwを推定するのに十分データがないので同様の問題が発生します。あまりフィットしないで滑らかで単純なモデルを選ぶように指定する部分が正則化になります。正則化の中でもL1正則化は最近注目されています。というのは、この正則化を適用すると多くの重みが0に潰されるといういい性質があるからです。自然言語処理タスクの場合はmが数百万にもなりwが数百万次元のベクトルとなるのですが、L1正則化を使うと、wの成分の殆どが0になってくれて、結果が分かりやすい、速い、省メモリといいところだらけです。

で、最後が双対化。今回の確率分布の推定問題は最適化問題を解くことによって得られます。最適化問題とはf(x)という関数があってこの関数の値を最大(最小)にするxを探す問題です。一般に最適化問題は難しい問題なのですが、今回解くのは、その中でも解きやすい凸最適化問題になっています。双対化は、この問題を直接解かずに、それと同じ解にたどり着くような解きやすい問題に変換するものです。今回も最終的に解く問題はパーセプトロンのような非常な単純な式になりました。数値最適化とかの手法とかは必要いらずで実装も簡単です。

ずいぶん適当にかいてみましたが、これで少しはタイトルが分かっていただけましたでしょうか。ppt, pdfをみていただける人が増えたら幸いです。いたらすごい。この論文で作った実装も将来的には公開する予定です。

ちょこちょこ修正してすいません。
 

|

« tx bepの内部技術の発表 | Main | マルコフ情報源上で次の文字を予測する »

Comments

お疲れさま。素晴らしいですね。
ぜひ読みたかったのですが、IBISには行く時間がなかったので助かりました。
Log Linearなのに、各訓練事例にまるでEMのような確率分布がつく(解き方は全然違いますが)というのが興味深かったです。
色々と拡張していけそうですね。

Posted by: daichi | 2007.11.06 02:25 PM

確率分布がつくのはきれいなのですが,これがどういった意味を持っているのか。これを確率分布を擬似頻度だと思って最尤推定しても同じ結果が得られることになります。

Dirichlet分布をpriorで使うとDiscountingスムージングしていることになるんですが、ME+l2もしくはL1の場合も対応するスムージングが存在するんでしょね。何に対応するのかなぁ

Posted by: oka | 2007.11.06 07:52 PM

確かに、どんな意味なんでしょうね。
MEのような対数線形モデルは大まかにはカウントをロジスティック変換していることになる気がしますが、その場合には指数分布族にはならないので、Dirichletのような綺麗なpriorは作れないかもしれない、と思いました。でも何か、方法はあるかもしれません。

Posted by: daichi | 2007.11.06 10:47 PM

Yes! Finally something about backup live mail.

Posted by: Maximo | 2014.05.19 10:56 AM

What's up, everything is going fine here and ofcourse every one is sharing information, that's really fine, keep up writing.

Posted by: สมัครแทงบอล | 2014.10.14 11:26 AM

Post your opinions of this super great Moshlings under!

Posted by: moshi monsters cheats | 2014.10.26 05:44 AM

Hey there, You have done an excellent job. I'll definitely digg it and personally recommend to my friends. I am sure they'll be benefited from this web site.

Posted by: match.com | 2015.04.06 02:17 AM

Post a comment



(Not displayed with comment.)




TrackBack


Listed below are links to weblogs that reference L1正則化付LLMの双対化:

« tx bepの内部技術の発表 | Main | マルコフ情報源上で次の文字を予測する »