読者です 読者をやめる 読者になる 読者になる

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

自然言語処理 機械学習

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

自然言語処理特論の授業で最大エントロピー法が紹介されました。言語モデルで、パープレキティが小さいモデルを作るのが目標なんですが、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つ出せば終わりだった。しかし、最大エントロピー法では素性に関する重要度がパラメータとなっていて、バイグラムとかだと求めないといけないパラメータの数が急激に多くなる。自分の経験としては、まだ数万単位の最適化問題は解いたことがないので、書けるか不安なところではある。

補足

あと、授業では証明は飛ばして、紹介程度だったが、最大エントロピーモデルの存在定理というのがある。

  • 最大エントロピーモデルは、パラメトリック形式のモデルで必ず表現でき、一意に定まる
  • パラメトリック形式で表現された最大エントロピーモデルは尤度も最大

というものである。まあ、あることを知ってればとりあえず問題はないんだけど、こういうのも大事にしていきたいなー。カーネル法もリプレゼンター定理があって、その存在意義(?)的なところもあったりすると思うので。あとでこれを読んで自分で補足しておこうと思います。

言語と計算 (4) 確率的言語モデル

言語と計算 (4) 確率的言語モデル

*1:正確にはもうちょい工夫が必要であるが