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をみていただける人が増えたら幸いです。いたらすごい。この論文で作った実装も将来的には公開する予定です。

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