最大エントロピーモデルについて（CRF への前振り）

最大エントロピーモデルについての解説。

既存の資料としては、A Simple Introduction to Maximum Entropy Models for Natural Language Processing や「言語処理のための機械学習入門」（通称高村本）が詳しい。

記事中でもその用語を適宜使ったり、内容を引用したりする。

ここでは、できるだけ直感的に理解できるような説明を目指す。

まず、最大エントロピーモデルとは何か。

最大エントロピーモデルは、分類を行う時に使われる。

たとえば、あるレビューに出てきた単語（good とか bad とか）から、そのレビューがポジティブなのかネガティブなのか分類する、というようなもの。

この分類先のことをクラスと呼ぶ。

最大エントロピーモデルは識別モデルの一種。

識別モデルの他には生成モデルというものもある。

これらの違いは、レビューの例で言うと、どういうレビュー（出てくる単語を含め）が次に出てくるかという予測をするかどうかということ。するのが生成モデルで、しないのが識別モデル。

識別モデルでは、あるレビューが与えられた時、それに出てくる単語などから、それがポジティブかネガティブかを判別できるようにモデルを最適化させる。

具体的に、最大エントロピーモデルとはどういうモデルか。

まず、起こりうるすべてのクラスと起こりうるすべての文脈を組み合わせた事象空間というものを考える。

起こりうるすべてのクラスというのは、ここでの例では次の二つとする。

ポジティブ
ネガティブ

起こりうるすべての文脈というのは、少し複雑になる。

たとえば、判別に使う単語が good, bad の二つだけだとすると、起こりうるすべての文脈というのは、

どちらも出てこない
good だけ出てくる
bad だけ出てくる
good も bad も出てくる

という 4つになる。

これらを組み合わせると、

ポジティブなレビューで、どちらも出てこない
ポジティブなレビューで、good だけ出てくる
ポジティブなレビューで、bad だけ出てくる
ポジティブなレビューで、good と bad の両方が出てくる
ネガティブなレビューで、どちらも出てこない
ネガティブなレビューで、good だけ出てくる
ネガティブなレビューで、bad だけ出てくる
ネガティブなレビューで、good と bad の両方が出てくる

というのが全事象になる。

そして、訓練データの中でそれぞれの事象が起こった回数が次の表のようになっているとする。

	-	good	bad	good, bad
ポジティブ	3	3	0	2
ネガティブ	2	1	2	1

表の見方は、訓練データの中にあるレビューが、

「ポジティブなレビューで、どちらも出てこない」ものが 3個
「ポジティブなレビューで、good だけ出てくる」ものが 3個

…

「ネガティブなレビューで、good も bad も出てくる」ものが 1個

というようになっていたということ。

この事象空間のそれぞれの事象に対して、モデルによって確率を割り当てることを考える*1。

一番簡単なのは、次の表のように、その事象が起きた回数に比例して確率を割り振るというもの。

	-	good	bad	good, bad
ポジティブ	3/14	3/14	0/14	2/14
ネガティブ	2/14	1/14	2/14	1/14

つまり、good が出てきて bad が出てこなかったら、ポジティブなものである確率は (3/14)/(3/14+1/14)=3/4 となる。

わかりやすい。

だが、これではうまくいかない。

何が問題か。

パラメータが多すぎる。

8 個の事象すべてに確率を割り振るということは、変数を 8 個（合計が 1 になることを考えても 7個）も持つということだ。

そのせいで、汎化能力（訓練データに出てこなかったものに対応する能力）に欠ける。

この例では単語の数が少ないので、全事象にそのまま起こった回数の確率を割り当ててもいいように見えるが、実際には単語の数はもっと多く、全事象の数はそれに対して指数的に増えるので、もっとずっとまばらになる。
高村本の例を引用する。単語は good, bad, exciting, boring の 4つで、文書は次の 4つ*2。

ポジティブなレビューで、good と bad が出てくる

ポジティブなレビューで、exciting が出てくる

ネガティブなレビューで、bad と boring が出てくる

ネガティブなレビューで、bad と exciting が出てくる

この場合、すべての事象を表にすると次のようになる。

- go ba go, ba ex ex, go ex, ba ex, go, ba bo bo, go bo, ba bo, go, ba bo, ex bo, ex, go bo, ex, ba bo, ex, go, ba

P 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0

N 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0

欄の多くが 0 になる。
たとえば、「exciting と good と bad が出てくるレビュー」があったとすると、それは表では次の位置になる。

- go ba go, ba ex ex, go ex, ba ex, go, ba bo bo, go bo, ba bo, go, ba bo, ex bo, ex, go bo, ex, ba bo, ex, go, ba

P 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0

N 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0

訓練データには、ポジティブなものもネガティブなものもない。
判別しようがないということになってしまう。
また、実際の判別に使う単語は 4 つどころではなく、ずっと多くなる。そのため、訓練データと同じ単語の組み合わせが出てくることはほとんどありえない。
そういうわけで、単語の組み合わせに対してではなく、個々の単語に対して、何らかのパラメータを割り当てる必要がある。

以降、繁雑さを避けるために good, bad の 2単語の例に戻る。

ここで、素性（そせい）というものを考える。

素性というのは、分野によっては特徴量とも呼ぶ。この素性というのをわかりやすく定義するのは難しいが、ここではとりあえず、「判別に使えそうな特徴」ということにしておく。

ここでの例では、

レビューに good が出てきたか
レビューに bad が出てきたか

の二つを考える。

さらに、最大エントロピーモデルでは、これに判別結果のクラスも組み合わせる。つまり、「レビューにどういう単語が出てきたか」という文脈に関するものと、「レビューがポジティブだったか、それともネガティブだったか」というクラスの組み合わせにする。

すると、素性は

レビューはポジティブで、文中に good が出てきた
レビューはポジティブで、文中に bad が出てきた
レビューはネガティブで、文中に good が出てきた
レビューはネガティブで、文中に bad が出てきた

の 4 つになる。

そして、それぞれの素性に対して、それが満たされた時に 1 になる素性関数というものを考える。つまり、次のようになる。
f₁(レビュー, クラス)=1 if "good" in レビュー and クラス == ポジティブ else 0
f₂(レビュー, クラス)=1 if "bad" in レビュー and クラス == ポジティブ else 0
f₃(レビュー, クラス)=1 if "good" in レビュー and クラス == ネガティブ else 0
f₄(レビュー, クラス)=1 if "bad" in レビュー and クラス == ネガティブ else 0
f₁..f₄ は、レビューとクラスを与えたら 0 か 1 かを返す二値関数（以降、「二値関数」というときは、0 か 1 かの二値関数とする）。

例えば、f₁ はレビューに good が含まれ、そのクラスがポジティブである時に限って 1 になり、それ以外では 0 になる。

最大エントロピーモデルでは、訓練データに対してモデルによって所属するクラス（ポジティブ・ネガティブ）の確率を計算した時に、これらの素性関数の期待値が、実際の訓練データでの合計値と一致するようにする。

「そもそもどうして素性関数の期待値を訓練データでの合計値に合わせるのか」という疑問があるかもしれないけれど、とりあえずは「そのようにするといろいろうまくいく」ということでお茶を濁しておく。

ここは非常にわかりにくいところなので、詳しく説明する。

最初に挙げた訓練データを再掲する。

	-	good	bad	good, bad
ポジティブ	3	3	0	2
ネガティブ	2	1	2	1

これを、文脈だけで分けると次のようになる。

-	good	bad	good, bad
5	4	2	3

表の見方は、「good も bad も出てこなかったレビュー」が 5 個、「good だけ出てきた」レビューが 4個…というもの。

これをモデルによってポジティブ・ネガティブに分類した時に、そこで出てくる素性関数の期待値が、訓練データ中に出てきた素性関数の合計値と同じになるようにする。

まず、訓練データ中に出てきた素性関数の合計値というのは、どういうものか。

もう一度訓練データを見直す。

	-	good	bad	good, bad
ポジティブ	3	3	0	2
ネガティブ	2	1	2	1

この 8 パターンのそれぞれについて、値が 1 になる素性関数を書くと、次のようになる。

	-	good	bad	good, bad
ポジティブ	-	f₁	f₂	f₁, f₂
ネガティブ	-	f₃	f₄	f₃, f₄

訓練データと合わせて考えると、それぞれの素性関数の合計値は次のようになる。

f₁: 3 + 2 = 5
f₂: 0 + 2 = 2
f₃: 1 + 1 = 2
f₄: 2 + 1 = 3

これが、訓練データ中での素性関数の合計値。

モデルによって確率を設定する時には、それぞれの素性関数の期待値がこの合計値に一致するという条件にする。

モデルによる確率を、次のように変数でおく。

	-	good	bad	good, bad
ポジティブ	p₁	p₂	p₃	p₄
ネガティブ	p₅	p₆	p₇	p₈

訓練データを文脈だけで分けたものの表を再掲する。

-	good	bad	good, bad
5	4	2	3

これらのデータをモデルによって分類すると、それぞれの事象の期待値は次のようになる。

	-	good	bad	good, bad
ポジティブ	5*(p₁/(p₁+p₅))	4*(p₂/(p₂+p₆))	2*(p₃/(p₃+p₇))	3*(p₄/(p₄+p₈))
ネガティブ	5*(p₅/(p₁+p₅))	4*(p₆/(p₂+p₆))	2*(p₇/(p₃+p₇))	3*(p₈/(p₄+p₈))

そして、それぞれの事象で 1 になる素性関数を再掲する。

	-	good	bad	good, bad
ポジティブ	-	f₁	f₂	f₁, f₂
ネガティブ	-	f₃	f₄	f₃, f₄

そうすると、それぞれの素性関数の期待値は次のようになる。

E[f₁]=4*(p₂/(p₂+p₆))+3*(p₄/(p₄+p₈))
E[f₂]=2*(p₃/(p₃+p₇))+3*(p₄/(p₄+p₈))
E[f₃]=4*(p₆/(p₂+p₆))+3*(p₈/(p₄+p₈))
E[f₄]=2*(p₇/(p₃+p₇))+3*(p₈/(p₄+p₈))

訓練データでの素性関数の合計値を再掲する。

f₁: 5
f₂: 2
f₃: 2
f₄: 3

それぞれの素性関数の期待値が訓練データでの合計値に一致するという条件なので、次のような式になる。

4*(p₂/(p₂+p₆))+3*(p₄/(p₄+p₈))=5
2*(p₃/(p₃+p₇))+3*(p₄/(p₄+p₈))=2
4*(p₆/(p₂+p₆))+3*(p₈/(p₄+p₈))=2
2*(p₇/(p₃+p₇))+3*(p₈/(p₄+p₈))=3

ここで、変数が 8 個あるのに制約条件が 4 個（合計が 1 になるという制約を加えても 5個）しかないため、値は一通りには決まらない。

たとえば、次のように p1..p8 を適当に決めたものはこの条件を満たす。

	-	good	bad	good, bad
ポジティブ	0/12	2/12	1/12	2/12
ネガティブ	5/12	0/12	2/12	3/12

これを使って訓練データの判別を行ってそれぞれの素性関数の期待値を求めると、訓練データでの素性関数の合計値と一致することがわかる。

しかし、この分布には不自然なところがある。

たとえば、good も bad も出てこないレビューに対しては、根拠なくポジティブ 0/12、ネガティブ 5/12 としている。

最大エントロピーモデルでは、このような不自然さを避けることを目指す。

たとえば、何も判断材料がない二つの選択肢に確率を割り振るとしたら、それぞれに同じだけ確率を分配するというのが、偏りがなく自然だ。

その自然さ（偏りのなさ）を測るのには、エントロピーという尺度がある。

エントロピーの式というのは、次のようなもの。

$}\displaystyle H(p)=-\sum_{x\in\mathcal{E}}p(x)\log p(x)$
たとえば上の確率分布についてエントロピーを求めると、-(2/12 * log(2/12) + 1/12 * log(1/12) + ... 3/12 * log(3/12)) = 1.8 程度になる。

このエントロピーが大きければ大きいほど、より偏りがない分布ということになる。

ここでは、期待値が条件を満たすような分布の中で、エントロピーを最大にするようなものを探すことにする。

すると、期待値についての条件を満たすものような分布の中では、それぞれの確率が次のような形で表されるものがエントロピーを最大にするものだということが導かれる。

$}\displaystyle p_{d,y}=\pi\prod_{j=1}^k{W_j}^{f_j(d,y)}(0<W_j<\infty)$

この式が導出される過程は、A Simple Introduction to Maximum Entropy Models for Natural Language Processing に詳しく載っている。ここでは割愛する。

そして、この式の意味について。
まず、「レビューにどういう単語が出てきたか」という文脈を d、「レビューがポジティブだったか、それともネガティブだったか」というクラスを y とおいている。これらのを組み合わせたものが事象ということになる。
そして、f_j(d, y) というのは、それぞれの事象に対して、0 または 1 になる。

たとえば、事象として「good だけがレビューに出てきて、かつレビューはポジティブなもの」というものを考える。
上の表でおいた p₁..p₈ の中では、p₂ にあたる。
また、この事象で 1 になる素性関数は f₁ で、f₂ と f₃ と f₄ は 0 になる。
そして、掛け算の記号Πを展開すると、上の式は次のようになる。
$}\displaystyle p_2=\pi*{W_1}^1*{W_2}^0*{W_3}^0*{W_4}^0=\pi*W_1*1*1*1=\pi*W_1$
まず、π というのは合計値が 1 になるようにするための定数で、ここではいったん置いておく。
そして、素性関数が 0 になるところは W_n の 0 乗、つまり 1 を掛けるということになる。要は「何もしない」ということ。
素性関数が 1 になるところ、つまり f₁ に対応する W₁ だけが残る。

これは二値変数 a_iが 1 になるところだけについて、それに対応する値 b_i を掛け合わせたい時に、 $}\textstyle \prod_{i}{b_i}^{a_i}$ と表すパターン。

他の例も挙げる。
「bad だけがレビューに出てきて、かつレビューはポジティブなもの」という事象では、f₂ だけが 1 になるため、以下のようになる。
$}\displaystyle p_3=\pi*{W_1}^0*{W_2}^1*{W_3}^0*{W_4}^0=\pi*W_2$
「good と bad の両方がレビューに出てきて、かつレビューはポジティブなもの」という事象では、1 になる素性関数は f₁ と f₂ の 2 つ。
$}\displaystyle p_4=\pi*{W_1}^1*{W_2}^1*{W_3}^0*{W_4}^0=\pi*W1*W_2$
まとめると、次のようになる。
まず、

素性関数ごとに倍率を設定する。

そして、それぞれの事象について、

その事象で 1 になる素性関数それぞれに対応する倍率を掛け合わせ、ある定数を掛けたものを、その事象の確率とする。

ということになる。
こうすると、上で p₁..p₈ とおいた変数同士は独立でなくなり、お互いの関係が設定されることになる。

すべての事象についての確率をこの形で表してみる。

それぞれの事象で 1 になる素性関数の表を再掲。

	-	good	bad	good, bad
ポジティブ	-	f₁	f₂	f₁, f₂
ネガティブ	-	f₃	f₄	f₃, f₄

それぞれの素性関数が 1 になるところには W₁..W₄ のような倍率を掛ける。

	-	good	bad	good, bad
ポジティブ	1	W₁	W₂	W₁*W₂
ネガティブ	1	W₃	W₄	W₃*W₄

そして、合計を 1 に調整するために、すべてを合計したもの（1+W₁+W₂+W₁*W₂+1+W₃+W₄+W₃*W₄）の逆数をπとおき、それをすべてに掛ける。すると、確率分布は次のようになる。

	-	good	bad	good, bad
ポジティブ	π	π*W₁	π*W₂	πW₁W₂
ネガティブ	π	π*W₃	π*W₄	πW₃W₄

たとえば、次のように適当においてみる。

W₁=2
W₂=1/3
W₃=1/2
W₄=5

すると、
W₁*W₂=2/3, W₃*W₄=5/2 となり、すべての合計（1+W₁+W₂+W₁*W₂+1+W₃+W₄+W₃*W₄）は 13 となるので、確率分布は次のようなものになる。

	-	good	bad	good, bad
ポジティブ	1/13	2/13	1/39	2/39
ネガティブ	1/13	1/26	5/13	5/26

しかし、これは変数同士の関係を満たすことだけを考えて適当に決めたものなので、素性関数の期待値についての条件は満たさない。試しに計算してみると、次のようになる。右は訓練データでの合計値。

E[f₁]≒3.8≠5
E[f₂]≒0.76≠2
E[f₃]≒3.2≠2
E[f₄]≒4.2≠3

上の式を再掲する。

$}\displaystyle p_{d,y}=\pi\prod_{j=1}^k{W_j}^{f_j(d,y)}(0<W_j<\infty)$
実際に求めるパラメータは、この条件と、素性関数の期待値に関する条件を同時に満たすもの。

それによる分布は、素性関数の期待値に関する条件を満たすものの中でもっともエントロピーが高くなる。

また、そのようなパラメータは一意に定まる。

導出過程は、やはり A Simple Introduction to Maximum Entropy Models for Natural Language Processing を参照。

ところで、この解をすぐに求めることはできない。

ここからは、その計算方法に移る。

まず、それぞれの重みの対数をとったものを w_i = log W_i とおく。0 < W_i < ∞ なので、-∞ < w_i < +∞ となる。

そして、それらをひとつのベクトルとして表す。w=(w₁, w₂, w₃, w₄) となる。

さらに、あるレビューと評価に対してどの素性関数がどういう値になるかというのもベクトルにする。

たとえば、good と bad を含むネガティブなレビューの場合、f₃ と f₄ だけが 1 になるので、(0, 0, 1, 1)^T というベクトルになる（後で掛け算をする都合上、列ベクトルにする）。

これを、φ(d, y) のように表す。d はこの場合はそれぞれのレビューで、y はポジティブかネガティブかという判別クラス。上の例では、φ(good と bad を含むレビュー, ネガティブ) = (0, 0, 1, 1)^T ということになる。

このようにすると、上で挙げた式

$}\displaystyle p_{d,y}=\pi\prod_{j=1}^k{W_j}^{f_j(d,y)}$

は、次のように書き換えられる。

$}\displaystyle p_{d,y}=\pi\exp({\bf w}\cdot\phi(d,y))$

上で出てきた式の中の重みを対数で置き換え、足し算をベクトルの掛け算に置き換え、それを指数関数で元に戻している。

ここも慣れが必要なところ。

実例として、「レビューに good と bad が両方含まれ、評価がネガティブである場合」を考える。
これは、表の中では p₈ とおいている。
この時、1 になる素性関数は f₃ と f₄ なので、 $}\textstyle \phi(d,y)=(0,0,1,1)^T$ となる。
つまり、式は次のようになる。
$}\displaystyle p_8=\pi\exp<a href=$

この exp の中身は、二値変数 aiが 1 になるところだけについて、それに対応する値 bi を足し合わせたい時に、それぞれをベクトルとして、a・b のようにベクトルの掛け算として表すパターン。
そして、指数関数なので足し算を掛け算にして、wi = log Wi であることを考えると、結局次のようになる。

これは、
$}\displaystyle p_{d,y}=\pi\exp({\bf w}\cdot\phi(d,y$ *3">
が
$}\displaystyle p_{d,y}=\pi\prod_{j=1}^k{W_j}^{f_j(d,y)}$
と同じ意味であるということの直感的な説明。
上のように書き換えたのは計算の都合によるもの。

あるレビューが与えられた時に、それがポジティブ（もしくはネガティブ）である確率は、次のように推定される。

$}\displaystyle P(y|d)=\exp({\bf w}\cdot\phi(d,y))/\sum_{y'}\exp({\bf w}\cdot\phi(d,y'))$

言い換えると、あるレビューがポジティブである確率は、そのレビューがポジティブである場合に対応する表内の値を、（そのレビューがポジティブである場合に対応する表内の値とそのレビューがネガティブである場合に対応する表内の値の合計）で割ったものにするということ。

ここは、言葉では伝わりにくいところなので、表で見てみる。

たとえば、good と bad が出てきたレビューがポジティブである確率は、good と bad が出てきて、かつポジティブであるところに割り振った確率

	-	good	bad	good, bad
ポジティブ	π	π*W₁	π*W₂	πW₁W₂
ネガティブ	π	π*W₃	π*W₄	πW₃W₄

を、すべてのクラスにわたって good と bad が出てくるものに割り振った確率の合計

	-	good	bad	good, bad
ポジティブ	π	π*W₁	π*W₂	πW₁W₂
ネガティブ	π	π*W₃	π*W₄	πW₃W₄

で割ったものとする、ということ。

結局、W₁*W₂/(W₁*W₂+W₃*W₄)、つまり $}\textstyle \exp(w1+w2)/(\exp(w1+w2)+\exp(w3+w4))$ になる（πは分母と分子で相殺される）。

ここで、ある文脈とあるクラスに対して、その事象で 1 になる素性関数に対応する重みを掛け合わせたものを、その事象に対するスコアとすると、ある文脈がそのクラスになる確率は、その事象に対するスコアを、その文脈とすべてのクラスを組み合わせたすべての事象に対するスコアを合計したもので割ったもの、ということになる。

上の式を再掲する。

$}\displaystyle P(y|d)=\exp({\bf w}\cdot\phi(d,y))/\sum_{y'}\exp({\bf w}\cdot\phi(d,y'))$

これによって、今のパラメータによる訓練データの尤度が求められる。

尤度というのは、ここでは「今のモデルで訓練データを判別して、うまく判別できる確率」のようなもの。

そして、最大エントロピーモデルでは、「エントロピーを最大にするパラメータ」は「訓練データの尤度を最大にするパラメータ」でもあり、一意に定まる。

これも、詳しくは A Simple Introduction to Maximum Entropy Models for Natural Language Processing を参照。

「エントロピーを最大にする」ことと「訓練データの尤度を最大化する」ことは同値なので、ここから先は後者について考える。

訓練データ全部の尤度は、訓練データを D とおき、それぞれのレビューとその評価をそれぞれ d_i, y_i とおくと、次のように表せる。

$}\displaystyle P_{cond}(D)=\prod_{(d_i,y_i)\in D}P(y_i|d_i)$
これを最大化するパラメータを求めるということは、これの対数をとったものを最大化するパラメータを求めるのと同じこと。

自明かもしれないけれど一応。正の数について、a > b なら log(a) > log(b) となるので、値域が正のある関数を最大化するパラメータと、その関数の対数を最大化するパラメータは同じことになる。ここでは、対数をとったほうが都合がいいのでそうしている。

対数をとると、次のようになる。

$}\displaystyle \log P_{cond}(D)=\sum_{(d_i,y_i)\in D}\log P(y_i|d_i)$

ここで、これを素直に最大化すると、「あるクラスだけに出現した素性に対する重みが無限大になる」という問題があるので、正則化項というものを付加する。ここでは、L2 ノルム というものを使う。そして、 $}\textstyle \log P_{cond}(D)$ から正則化項を引いたものを w の関数 L(w) とおくと、次のような形になる。

$}\displaystyle L({\bf w})=\sum_{(d_i,y_i)\in D}\log P(y_i|d_i)-\frac{C}{2}|{\bf w}|^2$
最後に引いているのが正則化項。

正則化項について突っ込むと面倒なことになるので、とりあえずこういうものだということで軽く流しておく。大雑把には「w があんまり極端な値にならないように調整する」というイメージ。

これを最大化するのだが、これでも答えはすぐには出ない。

しかし幸いなことに、これを w について微分することができたら、それを使って w を更新して、L(w) を最大化する w に近づけることができる。

そのあたりの数学的なところは、やはり上で挙げた資料などを参照。

で、要するに

$}\displaystyle L({\bf w})=\sum_{(d_i,y_i)\in D}\log P(y_i|d_i)-\frac{C}{2}|{\bf w}|^2$
を w について微分できたらいいということになる。

ここで、

$}\displaystyle P(y|d)=\exp({\bf w}\cdot\phi(d,y))/\sum_{y'}\exp({\bf w}\cdot\phi(d,y'))$

であることを考えて微分すると、次のようになる（過程は高村本を参照）。

$}\displaystyle \nabla_{\bf w}L({\bf w})=\sum_{(d_i,y_i)\in D}\left(\phi(d_i,y_i)-\sum_{y}P(y|d_i)\phi(d_i,y)\right)-C_{\bf w}$
この中で、 $}\textstyle \phi(d_i,y_i)$ は一つの訓練データの中でのそれぞれの素性関数の合計値で、 $}\textstyle \sum_{y}P(y|d_i)\phi(d_i,y)$ は、今のパラメータによって一つの訓練データの確率を推定した時の、それぞれの素性関数の期待値。

つまり、訓練データの中での素性関数の合計値と、今のパラメータによって訓練データを判別した時のそれぞれの素性関数の期待値との差分が求められれば、パラメータの更新ができることになる。

その差分は、それぞれの訓練データについて求めたものを全訓練データにわたって合計すればいい。

つまり、訓練データの尤度を最大にするような w を求めるには、まず w を適当な値（0 でいい）で初期化して、次の 2 つのステップを繰り返せばいい。

今の w を使って訓練データの確率を推定した時のそれぞれの素性関数の期待値を計算する。
訓練データ中での素性関数の合計値とそれとの差分を使って、w を更新する。

繰り返すうちに、 w が収束して、対数尤度の変化も少なくなってくるので、それを検知して適当なところで打ち切る。

試しに、(w₁, w₂, w₃, w₄)=(0, 0, 0, 0) の時を考えてみる。

w_i = log W_i という設定なので、(W₁, W₂, W₃, W₄) = (1, 1, 1, 1) となる。

確率の比は次の表のように表されるが、これらがすべて 1 になる。

	-	good	bad	good, bad
ポジティブ	1	W₁	W₂	W₁*W₂
ネガティブ	1	W₃	W₄	W₃*W₄

このパラメータで訓練データを判別すると、ポジティブの確率・ネガティブの確率ともに 0.5 になる。

訓練データを文脈によって分けたものを再掲する。

-	good	bad	good, bad
5	4	2	3

これらがすべて確率 0.5 でポジティブ・確率 0.5 でネガティブと判別されることになる。

それぞれの事象で 1 になる素性関数を再掲する。

	-	good	bad	good, bad
ポジティブ	-	f₁	f₂	f₁, f₂
ネガティブ	-	f₃	f₄	f₃, f₄

それぞれの素性関数の期待値は次のようになる。

E[f₁]=4*(1/2)+3*(1/2)=3.5
E[f₂]=2*(1/2)+3*(1/2)=2.5
E[f₃]=4*(1/2)+3*(1/2)=3.5
E[f₄]=2*(1/2)+3*(1/2)=2.5

訓練データでの素性関数の合計値を再掲。

f₁: 5
f₂: 2
f₃: 2
f₄: 3

これから、今のパラメータによる素性関数の期待値を引くと、(1.5, -0.5, -1.5, 0.5) となる。

あとは、これ（と正則化項）を計算ルーチンに渡すと、少し最適解に近づいた新しい w を返してもらえる。

ここでの例では、事象空間が小さいので、全事象について計算をしても問題ないが、普通は事象空間はもっと大きくなる。実際に素性関数の期待値を求めるにあたっては、訓練データひとつひとつに対して、各クラスに分類される確率を求め、それに基づいて計算する。

以下、計算方法についてのまとめ。

最大エントロピーモデルでパラメータを求めるには:

最初にパラメータを適当に設定して、それを最適解に近づけるために更新していく。

パラメータを更新するには:

訓練データ中での素性関数の合計値から、今のパラメータによる素性関数の期待値を引いたものを求める。

今のパラメータによる素性関数の期待値を求めるには:

ある訓練データについて、それが持つ文脈によって、今のパラメータで各クラスに配分する確率を求める。そして、各クラスについて、その時に 1 になる素性関数それぞれに対して、その確率を足していくと、その訓練データに対する素性関数の期待値が求められる。それを、すべての訓練データにわたって足し合わせる。

あるデータが持つ文脈によって、それが今のパラメータであるクラスになる確率を求めるには、ある文脈とあるクラスに対して、その事象で 1 になる素性関数に対応する重みを掛け合わせたものを、その事象に対するスコアとすると、

その事象に対するスコアを、その文脈とすべてのクラスを組み合わせたすべての事象に対するスコアを合計したもので割ったものを求める。

結局のところ、スコア、つまり、ある文脈とあるクラスに対して、その事象で 1 になる素性関数に対応する重みを掛け合わせたものが求められればいいということになる。

これらは基本的に CRF*4 でも同じ。

CRF というのは最大エントロピーモデルの特殊な場合で、系列に対して適用するというのがその特徴。

次の記事では CRF について書く。

*1:ここでちょっとトリッキーなのは、判別モデルであるのに全事象に対する確率を考えるということ。なぜかは置いといて、そういうものだということで。

*2:重複は考慮しないので削除。

*3:w1,w2,w3,w4)%5ccdot(0,0,1,1)^T)"> $}\displaystyle =\pi\exp(w3+w4)$ この exp の中身は、二値変数 a_iが 1 になるところだけについて、それに対応する値 b_i を足し合わせたい時に、それぞれをベクトルとして、a・b のようにベクトルの掛け算として表すパターン。そして、指数関数なので足し算を掛け算にして、w_i = log W_i であることを考えると、結局次のようになる。 $}\displaystyle \pi\exp(w3+w4)$ $}\displaystyle =\pi\exp(w3)\cdot\exp(w4)$ $}\displaystyle =\pi\cdot W3\cdot W4$ これは、

*4:ここで CRF という時、Linear-Chain CRFs のことを指すものとする。

	-	go	ba	go, ba	ex	ex, go	ex, ba	ex, go, ba	bo	bo, go	bo, ba	bo, go, ba	bo, ex	bo, ex, go	bo, ex, ba	bo, ex, go, ba
P	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0
N	0	0	0	0	0	0	1	0	0	0	1	0	0	0	0	0