初めての最大エントロピー法

なぜ最大エントロピー法が必要か

自然言語処理特論の授業で最大エントロピー法が紹介されました。言語モデルで、パープレキティが小さいモデルを作るのが目標なんですが、EMアルゴリズムでは、小さくできるパープレキシティにちょっと限界がありました。まあ、パラメータ数がせいぜい3つとかの最適化問題しか解いてないですからね。実際、簡単に実装もできたし。

ということで、さらに精度をよくするべく取り上げられた枠組みの一つとして最大エントロピー法。(何度も書いてるけど、)言語モデルでいつも問題になるのはデータスパースネス。データがないところをいかに推定するか、というところで色んなモデルで工夫してやってるし、やった(EMアルゴリズムのところは線形補完法で、低次のngramを使ったり)。

一様性の観点から

例えば、aとbという文字があったときにp(a)とp(b)の確率は分かっているんだけど、p(a,b)とかp(a,a)の確率が分からない、というのが最大エントロピー法が想定しているようなシチュエーション(まあ、本当は条件付き確率のほうなんだけど、ここではおいておく)。p(a, b)とかは分からないので、この条件のもとでなるべく「ばらばら」になるようにしたい。もう少しちゃんというとモデルの分布を一様にしたい、ということである。情報理論のほうで、一様性の議論というのがあり、一様性の定義の一つとして「エントロピー最大化」があった。

言語モデルの文脈でこれをあてめてあげると

低次のngramは密な感じなので、信頼できるだろう
高次のngramだとスパースで、すかすかである
すかすかの部分をなるべく一様になるように分配してあげよう
- ただし、低次のngramのところを制約としてね

という感じである。つまり、制約付き最適化問題に帰着するわけである。しかし、この問題を解析的に解くというのはかなり困難である。。。

定式化

ここで、ラグランジュ関数の形にして考える。目的としているパラメータのほうで偏微分してあげると、ラグランジュの未定乗数が入った形ではあるけど、次のような形で書き表わすことができる。
$P_{\mathbf{\Lambda}}(x, y) = \frac{1}{Z_{\mathbf{\Lambda}}} \exp\{\sum_{i=1}^n \lambda_i f_i(x, y)\}$
ここで、 $f_i(x, y)$ は素性関数、 $Z_{\mathbf{\Lambda}} = \sum_{x, y} \exp\{\sum_{i=1}^n \lambda_i f_i(x, y)\}$ である。このような流れで、最大エントロピー法はこのラグランジュの未定乗数 $\mathbf{\Lambda}$ を決定する問題に帰着された。

最適化

さて、ここでEMアルゴリズムで考えたときと同じようなことをやる。つまり、パラメータを更新したときの対数尤度関数の差分を考え、その差分の下界になっているような関数を探す。ステップごとにその下界を大きくしていくことができれば、尤度も大きくしていけるだろう、という思考の流れである。その下界をどうやって探すかという問題は(EMアルゴリズムのときもお世話になった)Jensenの不等式から出てくる。expが凸関数であるという性質を使って、これにあてはめてやり、下界の最大化問題を解く。これなら解ける*1。

とまあ、流れとしてはこんな感じである。ぱっと見た感じEMアルゴリズムよりずいぶん難しい感じである。線形補完法でのEMアルゴリズムなんかは重みをせいぜい3つ出せば終わりだった。しかし、最大エントロピー法では素性に関する重要度がパラメータとなっていて、バイグラムとかだと求めないといけないパラメータの数が急激に多くなる。自分の経験としては、まだ数万単位の最適化問題は解いたことがないので、書けるか不安なところではある。