最大エントロピーモデルの導出過程、学習の更新則、素性選択についての理論的側面を述べる。記述の大部分は を参照し、一部 , も参照している。
最大エントロピーモデルは、データの特徴を 素性関数(feature function)
によって記述し、素性関数がある 制約(constraint)
を満たし、かつ、モデルを表現する確率分布のエントロピーが最大となる（最大エントロピー原理を満たす）モデルである。
エントロピーを最大にする事により、制約を満たしながら最大エントロピーモデルの確率分布が最も一様に分布する様になり、未知データに対する確率を無下に\(0\)にすることが無くなるため、高い汎用性（汎化性能）が期待できる。
まず、サンプル（事例）データのドメイン（定義域）を\(X\)、データに付与されたラベルのドメインを\(Y\)と書く。例えば、次に来る単語を予測させたい場合には、サンプル\(X\)は1つ前までの単語の並び、ラベル\(Y\)は今の単語となる。
データとラベルを組にすることで1つの学習サンプルが構成され、また、モデルに与える\(m\)個の学習サンプルの集合\(Z_{m} \subset 2^{X\times Y}\)を次で表す:
\begin{equation*}
Z_{m} = \{ (x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{m}, y_{m}) \}
\end{equation*}
このようなサンプルに対し、素性関数（素性）の集合\({\cal F}\)は次で定義される:
\begin{equation*}
{\cal F} = \{ f_{i} : X \times Y \to \{0,1\}, i \in \{1,2,\dots,n\} \}
\end{equation*}
即ち\({\cal F}\)は、データとラベルの組\((x,y) \in X \times Y\)を受け取って\(\{0,1\}\)いずれかを返す関数の集合である。ここでは\(f\)の値域は議論の簡略化のため\(\{0,1\}\)としたが、値域は\(\{0,\alpha\} (\alpha > 0)\)、即ち\(0\)と\(0\)以外の正数実数を取るようにもできる。また、素性が条件を満たし正の値を取る時は、素性が活性化しているという。
素性の例を挙げると、\(n\)個の単語列\(w_{1},\dots,w_{n}\)から、直前の\(N-1\)個の単語列\(w_{n-N+1},\dots,w_{n-1}\)のみを用いて今の単語\(w_{n}\)を予測する（\(N\)-グラムの）場合は、素性は次の様に表現出来る。
\begin{equation*}
f_{x_{1}x_{2}\dots x_{N}}(w_{1},\dots,w_{n-1},w_{n}) =
\left\{
\begin{array}{ll}
1 & w_{n-N+1} = x_{1}, w_{n-N+2} = x_{2}, \dots, w_{n-1} = x_{N-1}, w_{n} = x_{N} \\
0 & {\rm otherwise}
\end{array} \right.
\end{equation*}
ここで\(f\)のインデックス\(x_{1}\dots x_{N}\)は整数との対応を適当に取ることで、容易に実現できる。
最大エントロピーモデルの制約として与えられる条件は、素性の平均（期待値）が、モデルと経験確率で一致することである。この条件を数式で表現する事を考える。
定義域\(X\times Y\)上に定義されるモデルの確率分布を\(P(x,y)\)と書き、経験確率分布を\(\tilde{P}(x,y)\)と書く。ここで経験確率分布\(\tilde{P}\)は、頻度確率で与える。即ち、学習サンプルに現れた\((x,y)\)の組の回数を\(C(x,y)\)と書くと、
\begin{equation*}
\tilde{P}(x,y) = \frac{C(x,y)}{m}
\end{equation*}
と表せる。モデルの確率分布は後で導出する。
ある素性\(f_{i}\)の分布\(p\)による平均を\(E_{p}[f_{i}]\)と書くと、経験分布とモデルの確率分布のそれぞれの平均は
\begin{align*}
E_{\tilde{P}}[f_{i}] &= \sum_{x,y} \tilde{P}(x,y) f_{i}(x,y) \\
E_{P}[f_{i}] &= \sum_{x,y} P(x,y) f_{i}(x,y)
\end{align*}
と表せられ、従って制約を数式で表現すると,
\begin{align*}
E_{\tilde{P}}[f_{i}] &= E_{P}[f_{i}] \ \ (i=1,\dots,n) \\
\iff \sum_{x,y} \tilde{P}(x,y) f_{i}(x,y) &= \sum_{x,y} P(x,y) f_{i}(x,y) \ \ (i=1,\dots,n)
\end{align*}
となる。最大エントロピーモデルの候補となる集合\({\cal P}\)は、全ての素性に関する制約を満たすモデルの集合となる:
\begin{equation*}
{\cal P} = \{ P | E_{P}[f_{i}] = E_{\tilde{P}}[f_{i}], i = \{1,\dots,n\} \}
\end{equation*}
明らかに、2つのモデル\(P,P^{\prime} \in {\cal P}\)に対して、\(E_{P}[f_{i}] = E_{\tilde{P}}[f_{i}] = E_{P^{\prime}}[f_{i}]\ \ (i=1,\dots,n)\)（候補となるモデルの素性の平均は同一）となる。
更に考慮すべき点は、最大エントロピーモデルの名の通り、モデル（確率分布\(P\)）のエントロピーを最大にする必要がある。モデルのエントロピーを\(H(P)\)と書くと、確率分布のエントロピーの式から,
\begin{equation*}
H(P) = -\sum_{x,y}P(x,y) \log P(x,y)
\end{equation*}
と表現できる。集合\({\cal P}\)の中で最もエントロピーが高いものが得るべきモデル\(P^{\ast}\)である:
\begin{equation*}
P^{\ast} = \underset{P \in {\cal P}}{\rm argmax}\ H(P)
\end{equation*}
この式を 最大エントロピー原理(maximum entropy principle)
と呼ぶ。集合\({\cal P}\)は無限集合だが最大エントロピー原理を満たすモデルは解析的に求められ、かつ一意に存在する（後術）。
最大エントロピー原理を満たすモデルの確率分布\(P\)を求める事を考える。これは制約付き非線形最適化問題であることから、ラグランジェの未定定数法が適用できる。\(P\)が満たすべき制約を列挙すると
\begin{align*}
1:& \quad E_{P}[f_{i}] = E_{\tilde{P}}[f_{i}] \ \ (i=1,\dots,n) \\
2:& \quad P(x,y) \geq 0 \\
3:& \quad \sum_{x,y}P(x,y) = 1
\end{align*}
であり（2,3は\(P\)が確率分布となる為の条件）、\(n\)個の制約に対応する未定定数を\(\Lambda = \{\lambda_{1},\dots,\lambda_{n}\}\)と書くと、ラグランジアン（ラグランジュ関数）\({\cal L}(P,\Lambda)\)は
\begin{align*}
{\cal L}(P, \Lambda) &= H(P) + \sum_{i=1}^{n} \lambda_{i} (E_{P}[f_{i}] - E_{\tilde{P}}[f_{i}]) \\
&= -\sum_{x,y}P(x,y)\log P(x,y) + \sum_{i=1}^{n} \lambda_{i} \left\{ \sum_{x,y} P(x,y) f_{i}(x,y) - \sum_{x,y} \tilde{P}(x,y) f_{i}(x,y) \right\}
\end{align*}
と書ける。最大値を得るため、\(P(x,y)\)によって偏微分すると,
\begin{equation*}
\frac{\partial {\cal L}(P,\Lambda)}{\partial P(x,y)} = -\log P(x,y) - 1 + \sum_{i=1}^{n} \lambda_{i} f_{i}(x,y)
\end{equation*}
この式を\(0\)とおいて\(P(x,y)\)について解くと
\begin{equation*}
P(x,y) = \exp \left[ -1 + \sum_{i=1}^{n} \lambda_{i} f_{i}(x,y) \right]
\end{equation*}
を得る。確率分布が指数関数で表現される為条件2の非負条件は満たされるが、条件3の全確率が1になることが保証されていない。そこで
\(\sum_{x,y}P(x,y) = Z_{\Lambda}\)なる正規化項(normalization
factor)を導入し\(P(x,y)\)の\(x,y\)についての総和が1になるようにする。従ってモデルの確率分布は次で表される:
\begin{align*}
P(x,y) &= \frac{ \exp \left[ -1 + \sum_{i=1}^{n} \lambda_{i} f_{i}(x,y) \right] }{ \sum_{x,y} \exp \left[ -1 + \sum_{i=1}^{n} \lambda_{i} f_{i}(x,y) \right] } \\
&= \frac{1}{Z_{\Lambda}} \exp \left[ \sum_{i} \lambda_{i} f_{i}(x,y) \right] \\
Z_{\Lambda} &= \sum_{x,y} \exp \left[ \sum_{i} \lambda_{i} f_{i}(x,y) \right]
\end{align*}
（以下、\(\sum_{i=1}^{n} \equiv \sum_{i}\)とする）得られた確率分布はMRF(Markov
Random
Fields、マルコフ確率場)のクリークサイズを1とした時、即ち節点ポテンシャル（連想ポテンシャル）のみを考えた結合確率に一致する。従って最大エントロピーモデルはMRFのサブクラスとして捉えられる。
最大エントロピー原理を満たすモデルは上述の議論で求められたが、このモデルが唯一に定まる事を示す。まず、上述の議論で得られた確率分布を持つモデルの集合を\({\cal Q}\)と書く:
\begin{equation*}
{\cal Q} = \left\{ P \left| P(x,y) = \frac{1}{Z_{\Lambda}} \exp\left[ \sum_{i} \lambda_{i}f_{i}(x,y) \right] \right. \right\}
\end{equation*}
集合\({\cal Q}\)の要素に制約は陽に表れていない。そして、\({\cal P,Q}\)と最大エントロピー原理について次の定理が成り立つ:
\(P^{\ast} \in {\cal P} \cap {\cal Q}\)ならば,
\begin{equation*}
P^{\ast} = \underset{P \in {\cal P}}{\rm argmax} \ H(P)
\end{equation*}
が成り立ち、かつ\(P^{\ast}\)は唯一に定まる。
（証明）まず補助定理として、\(R, S \in {\cal P}, T \in {\cal Q}\)ならば,
\begin{equation*}
\sum_{x,y} R(x,y) \log T(x,y) = \sum_{x,y} S(x,y) \log T(x,y)
\end{equation*}
を示す。\(T \in {\cal Q}\)より\(T(x,y) = \displaystyle\frac{1}{Z_{\Lambda}} \exp\left[ \sum_{i} \lambda_{i} f_{i}(x,y) \right]\)と表せるので、
\begin{align*}
（左辺） &= \sum_{x,y} R(x,y) \left[ \sum_{i} \lambda_{i} f_{i}(x,y) - \log Z_{\Lambda} \right] = \sum_{i} \lambda_{i} \sum_{x,y} R(x,y) f_{i}(x,y) - \log Z_{\Lambda} \sum_{x,y}R(x,y) \\
&= \sum_{i} \lambda_{i} E_{R}[f_{i}] - \log Z_{\Lambda} \\
&= \sum_{i} \lambda_{i} E_{S}[f_{i}] - \log Z_{\Lambda} \ \ (\because E_{R}[f_{i}] = E_{\tilde{P}}[f_{i}] = E_{S}[f_{i}]） \\
&= \sum_{x,y} S(x,y) \left[\sum_{i} \lambda_{i} f_{i}(x,y) \right] - \sum_{x,y} S(x,y) \log Z_{\Lambda} \\
&= \sum_{x,y} S(x,y) \log T(x,y) = （右辺）
\end{align*}
補助定理を用いて、定理の証明を行う。\(P \in {\cal P}, P^{\ast} \in {\cal P} \cap {\cal Q}\)とすると,
\begin{align*}
H(P^{\ast}) - H(P) &= -\sum_{x,y} P^{\ast}(x,y) \log P^{\ast}(x,y) + \sum_{x,y} P(x,y) \log P(x,y) \\
&= -\sum_{x,y} P(x,y) \log P^{\ast}(x,y) + \sum_{x,y} P(x,y) \log P(x,y) \ \ （\because 補助定理） \\
&= \sum_{x,y} P(x,y) \log \left[ \frac{P(x,y)}{P^{\ast}(x,y)} \right] \\
&= {\rm KL}(P || P^{\ast}) \geq 0\ \ （{\rm KL}:KLダイバージェンス）
\end{align*}
よって\(H(P^{\ast}) \geq H(P)\)が成立する。また\(H(P^{\ast}) = H(P)\)ならばKLダイバージェンスの性質により\(P^{\ast} = P\)となる。以上により、定理の成立が示された。
生成モデルの学習に関連して、最大エントロピー原理を満たすモデル\(P^{\ast}\)は、経験確率分布\(\tilde{P}\)が与えられた時に最大尤度を持つ事も示されている。モデルの尤度の式を導く事を考えると、まず経験確率分布\(\tilde{P}\)に対するモデル\(P\)の経験誤差はKLダイバージェンス\({\rm KL}(\tilde{P} || P)\)で与えられる ので,
\begin{align*}
{\rm KL}(\tilde{P} || P) &= \sum_{x,y} \tilde{P}(x,y) \log \left[ \frac{\tilde{P}(x,y)}{P(x,y)} \right] \\
&= \sum_{x,y} \tilde{P}(x,y) \log \tilde{P}(x,y) - \sum_{x,y} \tilde{P}(x,y) \log P(x,y)
\end{align*}
なる。大数の弱法則より、サンプル数の極限\(m\to \infty\)を取ることにより経験確率分布は標的概念の確率分布に一致し、また経験誤差は汎化誤差に一致する。今\({\rm KL}(\tilde{P} || P) \geq 0\)であり、かつ、\(\tilde{P}\)は観測により固定されるので、経験誤差を最小にするには下段の式の第2項を最大化すれば良いことになる。そして、下段式の第2項は対数尤度（経験対数尤度）と呼ばれる。モデル\(P\)の対数尤度を\(L(P)\)と書くと、
\begin{equation*}
L(P) = \sum_{x,y} \tilde{P}(x,y) \log P(x,y)
\end{equation*}
と表すことができる。尤度との関連として、最大エントロピー原理を満たすモデル\(P^{\ast}\)は次を満たす:
\(P^{\ast} \in {\cal P} \cap {\cal Q}\)ならば、
\begin{equation*}
P^{\ast} = \underset{Q \in {\cal Q}}{\rm argmax} \ L(Q)
\end{equation*}
が成り立ち、かつ\(P^{\ast}\)は唯一に定まる。
（証明）前の定理と同様の方針と、補助定理により,
\begin{align*}
L(P^{\ast}) - L(P) &= \sum_{x,y} \tilde{P}(x,y) \log P^{\ast}(x,y) - \sum_{x,y} \tilde{P}(x,y) \log P(x,y) \\
&= \sum_{x,y} P^{\ast}(x,y) \log P^{\ast}(x,y) - \sum_{x,y} P^{\ast}(x,y) \log P(x,y) \ \ (\because 反射性 E_{\tilde{P}}[f_{i}] = E_{\tilde{P}}[f_{i}]により、\tilde{P} \in {\cal P}) \\
&= \sum_{x,y} P^{\ast}(x,y) \log \left[ \frac{P^{\ast}(x,y)}{P(x,y)} \right] \\
&= {\rm KL}(P^{\ast} || P) \geq 0
\end{align*}
よって\(L(P^{\ast}) \geq L(P)\)であり、再びKLダイバージェンスの性質により、\(L(P^{\ast}) = L(P)\)ならば\(P^{\ast} = P\)が成り立つので唯一性も示される。従って定理の成立が示された。
定理1と2により、次の性質が成り立つ:
\begin{equation*}
P^{\ast} = \underset{P \in {\cal P}}{\rm argmax} \ H(P) = \underset{Q \in {\cal Q}}{\rm argmax} \ L(Q)
\end{equation*}
即ち、モデルの最大エントロピー原理は最尤推定の枠組みで捉える事もでき、尤度を最大化したモデルが最大のエントロピーを持つ。よって、モデルの学習には通常の生成モデルの学習と同じ様に、\({\cal Q}\)の要素で表現されるモデルの尤度最大化を考えれば良いことになる。
最尤推定法に基づく最大エントロピーモデルの学習は、モデルの尤度が最大になるようにモデル\(P\)のパラメタ\(\Lambda\)を調節してやれば良い。単純なアプローチとしては、対数尤度\(L(P)\)をパラメタ\(\Lambda=\{\lambda_{1},\cdots,\lambda_{n}\}\)で偏微分し、最急上昇法によって最大値を得る方法がある。実際に計算してみると,
\begin{align*}
\frac{\partial L(P)}{\partial \lambda_{i}} &= \sum_{x,y} \tilde{P}(x,y) \frac{\partial}{\partial \lambda_{i}} \log P(x,y) \\
&= \sum_{x,y} \tilde{P}(x,y) \frac{\partial}{\partial \lambda_{i}} \left[ \sum_{j} \lambda_{j} f_{j}(x,y) - \log Z_{\Lambda} \right] \\
&= \sum_{x,y} \tilde{P}(x,y) \left[ f_{i}(x,y) - \frac{1}{Z_{\Lambda}} \sum_{x^{\prime},y^{\prime}} f_{i}(x^{\prime},y^{\prime}) \exp \left( \sum_{j} \lambda_{j} f_{j}(x^{\prime},y^{\prime}) \right) \right] \\
&= \sum_{x,y} \tilde{P}(x,y) \left( f_{i}(x,y) - E_{P}[f_{i}] \right) \\
&= E_{\tilde{P}}[f_{i}] - E_{P}[f_{i}]
\end{align*}
であり（最適時には制約が満たされることが分かる）、ステップ\(t\)におけるパラメタ\(\lambda_{i}^{t}\)の更新規則は次の様に得られる:
\begin{align*}
\lambda_{i}^{t+1} &= \lambda_{i}^{t} + \eta \frac{\partial L(P)}{\partial \lambda_{i}^{t}} \\
&= \lambda_{i}^{t} + \eta ( E_{\tilde{P}}[f_{i}] - E_{P}[f_{i}] )
\end{align*}
ここで\(\eta\)は収束の早さを決める学習率(learning
rate)であり、ヒューリスティックに決める必要がある。
この様に再急上昇法による学習は単純だが、学習（収束）が遅く、\(\eta\)を決めなければならないという問題がある。\(\eta\)を大きく設定し過ぎると勾配の谷を越えてしまい発散を招き、逆に小さく設定すると学習がいつまでたっても終わらない。現状、最大エントロピーモデルの学習では、反復スケーリング法(iterative
scaling)という学習手法が伝統的に用いられている。
反復スケーリング法の基本的な考え方は、まずパラメタ\(\Lambda\)を\(\Lambda+\Delta\)に変化させた時の対数尤度の変化量の下限\(A(\Lambda,\Delta)\)を計算し、次にこの\(A(\Lambda,\Delta)\)を最大にする\(\Delta\)を求める事で、結果増加量を最大にするようにしている。この考え方には学習率の様なヒューリスティックは介在せず、かつ毎ステップの対数尤度の増加量を最大にするようにパラメタを更新できる。
それでは反復スケーリング法の更新式を導くことを考える。各パラメタの更新量を\(\Delta=\{\delta_{1},\cdots,\delta_{n}\}\)と表すものとし、まず、パラメタ更新時の対数尤度の変化量\(L(P_{\Lambda+\Delta})-L(P_{\Lambda})\)は,
\begin{align*}
L(P_{\Lambda+\Delta})-L(P_{\Lambda}) &= \sum_{x,y} \tilde{P}(x,y) \log P_{\Lambda+\Delta}(x,y) - \sum_{x,y} \tilde{P}(x,y) \log P_{\Lambda}(x,y) \\
&= \sum_{x,y} \tilde{P}(x,y) \log \left[ \frac{P_{\Lambda+\Delta}(x,y)}{P_{\Delta}(x,y)} \right] \\
&= \sum_{x,y} \tilde{P}(x,y) \log \left[ \frac{Z_{\Lambda}}{Z_{\Lambda+\Delta}} \frac{\exp\left[ \sum_{i}(\lambda_{i} + \delta_{i}) f_{i}(x,y) \right]}{\exp\left[ \sum_{i}\lambda_{i}f_{i}(x,y) \right] } \right] \\
&= \sum_{x,y} \tilde{P}(x,y) \left[ \sum_{i} \delta_{i} f_{i}(x,y) - \log\left(\frac{Z_{\Lambda+\Delta}}{Z_{\Lambda}} \right) \right] \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) - \log \left(\frac{Z_{\Lambda+\Delta}}{Z_{\Lambda}} \right) \\
&\geq \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) + 1 - \frac{Z_{\Lambda+\Delta}}{Z_{\Lambda}} \ \ (\because -\log x \geq 1-x) \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) + 1 - \frac{\sum_{x,y}\exp\left[ \sum_{i}(\lambda_{i} + \delta_{i})f_{i}(x,y) \right]}{\sum_{x,y}\exp\left[ \sum_{i}\lambda_{i}f_{i}(x,y) \right]} \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) + 1 - \frac{Z_{\Lambda}\sum_{x,y}P_{\Lambda}(x,y)\exp\left[ \sum_{i}\delta_{i}f_{i}(x,y) \right]}{Z_{\Lambda} \sum_{x,y}P_{\Lambda}(x,y)} \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) + 1 - \sum_{x,y}P_{\Lambda}(x,y)\exp\left[ \sum_{i}\delta_{i}f_{i}(x,y) \right]
\end{align*}
素性\(f_{i}(x,y)\)の\(i\)についての和\(f^{\#}(x,y) = \sum_{i=1}^{n}f_{i}(x,y)\)を用いると、
\begin{equation*}
L(P_{\Lambda+\Delta})-L(P_{\Lambda}) = \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) + 1 - \sum_{x,y}P_{\Lambda}(x,y)\exp\left[ \sum_{i}\frac{f_{i}(x,y)}{f^{\#}(x,y)}\delta_{i}f^{\#}(x,y) \right]
\end{equation*}
と書ける。今\(f_{i}(x,y)/f^{\#}(x,y)\)は確率分布となることから、\(\sum_{i}\frac{f_{i}(x,y)}{f^{\#}(x,y)}\delta_{i}f^{\#}(x,y)\)は\(\delta_{i}f^{\#}(x,y)\)についての平均と読み取れる。更に\(\exp\)は明らかに凸関数であることから、イェンセンの不等式\(\exp(E[X]) \leq E[\exp(X)]\)を用いて最終的な下限の式を得る。
\begin{align*}
L(P_{\Lambda+\Delta})-L(P_{\Lambda}) &\geq \sum_{x,y} \tilde{P}(x,y) \sum_{i} \delta_{i} f_{i}(x,y) + 1 - \sum_{x,y}P_{\Lambda}(x,y)\sum_{i}\frac{f_{i}(x,y)}{f^{\#}(x,y)}\exp\left[ \delta_{i}f^{\#}(x,y) \right] \\
&= A(\Lambda, \Delta)
\end{align*}
次に\(A(\Lambda, \Delta)\)を\(\delta_{i}\)で偏微分することで下限の最大化を考える。
\begin{align*}
\frac{\partial A(\Lambda, \Delta)}{\partial \delta_{i}} &= \sum_{x,y} \tilde{P}(x,y) f_{i}(x,y) - \sum_{x,y} P_{\Lambda}(x,y) f_{i}(x,y) \exp \left[ \delta_{i}f^{\#}(x,y) \right] \\
&= E_{\tilde{P}}[f_{i}] - \sum_{x,y} P_{\Lambda}(x,y) f_{i}(x,y) \exp \left[ \delta_{i}f^{\#}(x,y) \right]
\end{align*}
この式を\(0\)とおき\(\delta_{i}\)について解くことで変化量を求める事ができる。この式は\(\delta_{i}\)について閉じた形をしていないので、基本的には数値解析によって極値を求める。しかし、もしも任意の\((x,y)\)に対し
\(f^{\#}(x,y) = C\)（定数）となるならば、\(\delta_{i}\)について解く事ができ、次の結果を得る。
\begin{align*}
& E_{\tilde{P}}[f_{i}] - \sum_{x,y} P_{\Lambda}(x,y) f_{i}(x,y) \exp \left[ \delta_{i}f^{\#}(x,y) \right] = 0 \\
&\implies \exp \left[C \delta_{i} \right] \sum_{x,y} P_{\Lambda}(x,y) f_{i}(x,y) = E_{\tilde{P}}[f_{i}] \iff \exp \left[C \delta_{i} \right] = \frac{E_{\tilde{P}}[f_{i}]}{E_{P}[f_{i}]} \\
&\iff \delta_{i} = \frac{1}{C} \log \left( \frac{E_{\tilde{P}}[f_{i}]}{E_{P}[f_{i}]} \right)
\end{align*}
任意の\((x,y)\)で\(f^{\#}(x,y)\)が定数にならない場合でも、実は\(C = \displaystyle\max_{x,y} f^{\#}(x,y)\)とし、新しい素性\(f_{n+1}(x,y)\)を\(f_{n+1}(x,y) = C - f^{\#}(x,y)\)とおけば、変更後の和\(f^{\#\prime}(x,y)\)は\(f^{\#\prime}(x,y)=C\)となる事が知られている。\(f^{\#\prime}(x,y)\)について検算を行ってみると,
\begin{align*}
f^{\#\prime}(x,y) &= \sum_{i=1}^{n+1} f_{i}(x,y) = \sum_{i=1}^{n} f_{i}(x,y) + f_{n+1}(x,y) \\
&= f^{\#}(x,y) + C - f^{\#}(x,y) = C
\end{align*}
となって、定数\(C\)を取ることが確かめられた。
前節までのモデルはあるパターン\((x,y)\)を生成する結合確率を表現しているが、応用上は何らかの入力\(x\)に対して出力\(y\)の結果を得たいというケースが多い。例えば、再び単語予測の例を挙げると、一つ前までの単語を\(x\)として入力として、今の単語\(y\)を予測するというタスクである。そのような場合はモデルの条件付き確率\(P(y|x)\)が用いられる。このモデルは\(y\)の識別を行うので生成識別モデルと呼ばれ、条件付き最大エントロピーモデルはCRF(Conditional
Random Fields、条件付き確率場)のサブクラスとして捉えられる。
条件付き最大エントロピーモデルの確率分布\(P_{\Lambda}(y|x)\)は、\(P_{\Lambda}(x,y)\)とベイズの定理から得られる。
\begin{align*}
P_{\Lambda}(y|x) &= \frac{P_{\Lambda}(x,y)}{P_{\Lambda}(x)} \\
&= \frac{\exp\left[ \sum_{i}\lambda_{i}f_{i}(x,y) \right]}{Z_{\Lambda}} \left( \sum_{y} \frac{\exp\left[ \sum_{i}\lambda_{i}f_{i}(x,y) \right]}{Z_{\Lambda}} \right)^{-1} \\
&= \frac{1}{Z_{\Lambda}(x)} \exp\left[ \sum_{i}\lambda_{i}f_{i}(x,y) \right] \\
Z_{\Lambda}(x) &= \sum_{y}\exp\left[\sum_{i}\lambda_{i}f_{i}(x,y)\right]
\end{align*}
このモデルを用いた素性の平均\(E_{P}[f_{i}]\)は次の様に計算できる。
\begin{align*}
E_{P}[f_{i}] &= \sum_{x,y} P(x,y) f_{i}(x,y) = \sum_{x,y} P(y|x)P(x)f_{i}(x,y) \\
&= \sum_{x} P(x) \sum_{y} P(y|x) f_{i}(x,y)
\end{align*}
外側の\(P(x)\)の和は、考えうる全ての入力\(x \in X\)についての和を取らねばならず、その計算は現実的に不可能である。従って経験確率による近似\(P(x) \approx \tilde{P}(x)\)を用いて、平均は
\begin{equation*}
E_{P}[f_{i}] \approx \sum_{x}\tilde{P}(x) \sum_{y} P(y|x) f_{i}(x,y)
\end{equation*}
とする。この近似を用いることで、\(x\)については学習データに現れるものだけの和を取ればよく、また\(y\)についても素性関数が非零の時のみ和を取れば良ため、計算の効率化が望める。
平均だけでなく、正規化項\(Z_{\Lambda}(x)\)の計算もボトルネックな部分であり、効率化が望まれる。そこで、文献 による効率的な正規化項の計算手法を見ていく。まず、素性関数の集合\({\cal F}\)を次の2つに分割する:
\begin{align*}
{\cal F}_{m} &= \{ f_{i} | \forall{w,x,y} \ f_{i}(x,y) = f_{i}(w,y) \} \ \ \text{（周辺素性(marginalized feature)の集合）} \\
{\cal F}_{c} = {\cal F}_{m}^{c} &= \{ f_{i} | \exists{w,x,y} \ f_{i}(x,y) \neq f_{i}(w,y) \} \ \ \text{（条件付き素性(conditional feature)の集合）}
\end{align*}
周辺素性は\(y\)の値のみによって決まる素性であり、\(y\)の関数として捉えられる。集合演算の性質により、\({\cal F}\_{m} \cap {\cal F}_{c} = \emptyset\)は自明に成り立つ。次に、\(y\)の値域\(Y\)についても次の分割を行う:
\begin{align*}
Y_{m} &= \{ y | \exists f_{i} \in {\cal F}_{m} \ f_{i}(y) \neq 0 \} \ \ \text{（周辺素性が活性化される$Y$の要素）} \\
Y(x) &= \{ y | \exists f_{i} \in {\cal F}_{c} \ f_{i}(x,y) \neq 0 \} \ \ \text{（$x$を固定した時に,条件付き素性が活性化される$Y$の要素）}
\end{align*}
定義より
\begin{equation*}
Y_{m}^{c} = \{ y | \forall{f_{i}} \in {\cal F}_{m} \ f_{i}(y) = 0 \}
\end{equation*}
（どの周辺素性に対しても活性化されない\(Y\)の要素）は自明に成り立つ。また、一般には\(Y_{m} \cap Y(x) \neq \emptyset\)である。即ち周辺素性と条件付き素性を同時に活性化させる\(Y\)の要素は存在する。
以上の集合分割を考慮しつつ、正規化項\(Z_{\Lambda}(x) = \sum_{y}\exp\left[\sum_{i}\lambda_{i}f_{i}(x,y)\right]\)の計算を考えていくが、表記の簡略化の為、文献と同じように次の表記を用いる:
\begin{equation*}
z(y|x) = \exp\left[ \sum_{i}\lambda_{i} f_{i}(x,y) \right] \ ,\ z(y) = \exp\left[ \sum_{f_{i} \in {\cal F}_{m}} \lambda_{i} f_{i}(y) \right]
\end{equation*}
正規化項\(Z_{\Lambda}(x)\)の計算式は次のように展開される。
\begin{align*}
Z_{\Lambda}(x) &= \sum_{y \in Y}z(y|x) \\
&= \sum_{y \in Y_{m}^{c} \cap Y(x)^{c}} z(y|x) + \sum_{y \in Y_{m} \cap Y(x)^{c}} z(y|x) + \sum_{y \in Y(x)} z(y|x) \\
\end{align*}
ここで、
\begin{align*}
y \in Y(x)^{c} &\implies z(y|x) = z(y) \\
&\because z(y|x) = \exp\left[ \sum_{f_{i} \in {\cal F}_{m}} \lambda_{i} f_{i}(y) + \sum_{f_{i} \in {\cal F}_{c}} \lambda_{i} 0 \right] = \exp \left[ \sum_{f_{i} \in {\cal F}_{m}} \lambda_{i} f_{i}(y) \right] = z(y)
\end{align*}
が成立するので、
\begin{equation*}
Z_{\Lambda}(x) = \sum_{y \in Y_{m}^{c} \cap Y(x)^{c}} z(y) + \sum_{y \in Y_{m} \cap Y(x)^{c}} z(y) +\sum_{y \in Y(x)} z(y|x)
\end{equation*}
となり、さらに集合の包含関係に注目すれば、
\begin{align*}
\sum_{y \in Y} z(y) &= \sum_{y \in Y_{m} \cap Y(x)^{c}} z(y) + \sum_{y \in Y_{m}^{c} \cap Y(x)^{c}} z(y) + \sum_{y \in Y(x)} z(y) \\
&= \sum_{y \in Y_{m}} z(y) + \sum_{y \in Y_{m}^{c}} z(y) \\
\therefore \sum_{y \in Y_{m} \cap Y(x)^{c}} z(y) + \sum_{y \in Y_{m}^{c} \cap Y(x)^{c}} z(y) &= \sum_{y \in Y_{m}} z(y) + \sum_{y \in Y_{m}^{c}} z(y) - \sum_{y \in Y(x)} z(y)
\end{align*}
が成立するので、
\begin{equation*}
Z_{\Lambda}(x) = \sum_{y \in Y_{m}^{c}} z(y) + \sum_{y \in Y_{m}} z(y) + \sum_{y \in Y(x)} \left\{ z(y|x) -z(y) \right\}
\end{equation*}
となり、更に\(Y_{m}^{c}\)の要素の性質
\begin{align*}
y \in Y_{m}^{c} &\implies z(y) = 1 \\
&\because z(y) = \exp\left[ \sum_{f_{i} \in {\cal F}_{m}} \lambda 0 \right] = 1
\end{align*}
を用いて、次の最終結果を得る。
\begin{align*}
Z_{\Lambda}(x) &= \sum_{y \in Y_{m}^{c}} 1 + \sum_{y \in Y_{m}} z(y) + \sum_{y \in Y(x)} \left\{ z(y|x) -z(y) \right\} \\
&= |Y-Y_{m}| + \sum_{y \in Y_{m}}z(y) + \sum_{y \in Y(x)} \left\{ z(y|x) -z(y) \right\}
\end{align*}
ここで\(Y-Y_{m}=Y \cap Y_{m}^{c}\)は集合演算の意味での差である。この計算式は、第1項と第2項は予め計算しておくことができ、しかも第3項については\(Y\)の部分集合\(Y(x)\)の和を考えれば良い。結果、ナイーブな計算（計算量\(O(|X||Y|)\)）を行うよりも効率的（計算量\(O(|X||Y(x)|+|X|)\)）に計算を行うことができる。
前節までは、最大エントロピーモデルの学習について考えてきたが、モデルの構成要素となる素性については触れてなかった。観測された経験確率分布\(\tilde{P}(x,y)\)に対し、素性の組み合わせによって実現可能な最大尤度が異なり、従って尤度が最大になる素性集合\({\cal F}\)を選び出さなければならない。
しかし素性の候補となる集合\({\cal F}_{0}\)は非常に大きくなる為に、網羅的に全ての素性の組み合わせを試していくのは現実的に不可能である。また、サンプルで出現頻度が高い素性を選択する手法も存在するが、これでは尤度を厳密に最大化できない。そこで、逐次的にモデルの尤度が増加する様に素性を追加する手法が基本的に用いられており、その手順の概要は以下の様になる。
- モデルの素性集合\({\cal F}\)を空集合とする:
\({\cal F} \leftarrow \emptyset\)
- （反復スケーリング法等の学習手法によって）素性集合\({\cal F}\)における最大尤度モデル\(P_{\cal F}\)を得る。
- 素性集合の候補\({\cal F}\_{0}\)の各要素\(f_{0} \in {\cal F}_{0}\)について、以下を行う。
1.
素性を加えたモデルを学習し\(P_{{\cal F} \cup f_{0}}\)を得る。
2. 対数尤度の増分\(\Delta L({\cal F}, f_{0})\)を計算する:
\(\Delta L({\cal F}, f_{0}) \leftarrow L(P_{{\cal F} \cup f_{0}}) - L(P_{\cal F})\)
- 最大の増分\(\Delta L({\cal F}, \hat{f})\)を与える\(\hat{f} = \underset{f \in {\cal F}_{0}}{\rm argmax}\ \Delta L({\cal F}, f)\)を選び出し、素性集合に加える:
\({\cal F} \leftarrow {\cal F} \cup \hat{f}\)
- 最大増分がある閾値以下になったら終了し、それ以外は2.に戻る。
逐次的に計算が行える為に手続き的に実行しやすいものの、結局手順3,4において\({\cal F}_{0}\)を走査しているので依然として膨大な計算量が必要になる。文献 では対数尤度の増分を近似的に求める手法を述べているが、それでも本質的に計算量を削減できたとは言えず、効率的な素性選択の手法については研究の対象となっていた 。
ここでは元の文献 に述べられていた、増分の近似による手法を見ていく。近似の仮定としては、元のモデル\(P_{\cal F}\)とそのパラメタ集合\(\Lambda\)に\(f \in {\cal F}\)とそれに付随するパラメタ\(\alpha\)を加えたモデル\(P_{{\cal F} \cup f}\)においても、最大尤度を与える元のパラメタ\(\Lambda\)は変化しないというものである。実際には素性を加える事で最大尤度を与えるパラメタ\(\Lambda\)は変化するが、この変化を無視することでモデル\(P_{{\cal F} \cup f}\)の最大尤度\(L(P_{{\cal F} \cup f})\)の計算を回避する。素性を追加することにより尤度は増えこそすれ減ることはないので（\(\because\)経験分布に適合しない素性に対しては学習の結果\(\alpha = 0\)となり、元のモデルと一致するので尤度増分は0）
、近似的増分を最大にする\(\alpha\)を探索する問題に帰着される。
仮定の下で、素性集合\({\cal F} \cup f\)に対するモデル\(P_{{\cal F} \cup f}^{\alpha}\)の確率分布は次の様に書ける。
\begin{align*}
P_{ {\cal F} \cup f}^{\alpha}(y|x) &= \frac{1}{Z_{\alpha}(x)} P_{\cal F} (y|x) \exp \left[ \alpha f(x,y) \right] \\
Z_{\alpha}(x) &= \sum_{y} P_{\cal F}(y|x) \exp \left[ \alpha f(x,y) \right]
\end{align*}
対数尤度の近似的増分\(G_{{\cal F} \cup f}(\alpha)\)は,
\begin{align*}
G_{{\cal F} \cup f}(\alpha) &= L(P_{{\cal F}\cup f}^{\alpha}) - L(P_{\cal F}) \\
&= \sum_{x,y} \tilde{P}(x,y) \log P_{{\cal F} \cup f}^{\alpha}(x,y) - \sum_{x,y} \tilde{P}(x,y) \log P_{\cal F}(x,y) \\
&= \sum_{x,y} \tilde{P}(x,y) \left\{ \log P_{\cal F}(x,y) + \alpha f(x,y) - \log Z_{\alpha}(x) - \log P_{\cal F}(x,y) \right\} \\
&= \alpha \sum_{x,y} \tilde{P}(x,y) f(x,y) - \sum_{x} \log Z_{\alpha}(x) \sum_{y} \tilde{P}(x,y) \\
&= \alpha E_{\tilde{P}}[f] - \sum_{x} \tilde{P}(x) \log Z_{\alpha}(x)
\end{align*}
となる、\(G_{{\cal F} \cup f}(0) = 0\)は\(Z_{0}(x) = 1\)より容易に確かめられる。増分最大化の為、偏微分\(\frac{\partial G_{{\cal F} \cup f}}{\partial \alpha} = G_{{\cal F} \cup f}^{\prime}(\alpha)\)を計算すると,
\begin{align*}
G_{{\cal F} \cup f}^{\prime}(\alpha) &= E_{\tilde{P}}[f] - \sum_{x} P(x) \frac{\partial \log Z_{\alpha}(x)}{\partial \alpha} \\
&= E_{\tilde{P}}[f] - \sum_{x} \tilde{P}(x) \frac{1}{Z_{\alpha}(x)} \sum_{y} P_{\cal F}(y|x) \exp\left[ \alpha f(x,y) \right] f(x,y) \\
&= E_{\tilde{P}}[f] - \sum_{x} \tilde{P}(x) \sum_{y} P_{ {\cal F} \cup f}^{\alpha}(y|x) f(x,y)\ \ (= E_{\tilde{P}}[f] - E_{P_{ {\cal F} \cup f}}[f]) \\
&= E_{\tilde{P}}[f] - \sum_{x} \tilde{P}(x) Q_{ {\cal F} \cup f}^{\alpha} (f|x)
\end{align*}
ここで、文献にもあるように\(Q_{ {\cal F} \cup f}^{\alpha} (h|x) = \sum_{y} P_{ {\cal F} \cup f}^{\alpha}(y|x) h(x,y)\)（分布\(P_{ {\cal F} \cup f}\)による、\(h\)の\(y\)における平均）とおいている。\(G_{{\cal F} \cup f}^{\prime}(0)\)の値は\(P_{ {\cal F} \cup f}^{0}(y|x) = P_{\cal F}(y|x)\)により\(G_{{\cal F}\cup f}^{\prime}(0) = E_{\tilde{P}}[f] - E_{P_{\cal F}}[f]\)となる。更に2階微分\(G_{{\cal F} \cup f}^{\prime \prime}(\alpha)\)を計算すると,
\begin{align*}
G_{{\cal F} \cup f}^{\prime \prime}(\alpha) &= - \sum_{x} P(x) \frac{1}{Z_{\alpha}^{2}(x)} \left[ \left\{ \sum_{y} P_{\cal F}(y|x) \exp\left[ \alpha f(x,y) \right] f^{2}(x,y) \right\} Z_{\alpha}(x) \right. \\
& \left. - \left\{ \sum_{y} P_{\cal F}(y|x)\exp\left[ \alpha f(x,y) \right] f(x,y) \right\}^{2} \right] \\
&= - \sum_{x} \tilde{P}(x) \left[ Q_{ {\cal F} \cup f}^{\alpha} (f^{2}|x) - \left\{Q_{ {\cal F} \cup f}^{\alpha}(f|x) \right\}^{2} \right] \\
&= - \sum_{x} \tilde{P}(x) Q_{ {\cal F} \cup f}^{\alpha} \left( (f - Q_{ {\cal F} \cup f}^{\alpha}(f|x))^{2} | x \right)
\end{align*}
ここで最下段の式変形には、分散と平均の関係\(E[(X-E[X])^{2}] = E[X^{2}] - \{E[X]\}^{2}\)を用いている。\((f - Q_{ {\cal F} \cup f}^{\alpha}(f|x))^{2} \geq 0\)より、\(G_{{\cal F} \cup f}^{\prime \prime}(\alpha) \leq 0\)が成立し、\(G_{{\cal F} \cup f}(\alpha)\)は上に凸な関数であり、極大値がそのまま大域的な最大値となる事が分かる。
上述の議論により、\(G_{{\cal F} \cup f}^{\prime}(\alpha^{\ast}) = 0\)を満たす\(\alpha^{\ast}\)を得れば良いことになるが、解くべき式が\(\alpha\)について閉じた形をしていない為、数値解析的な手法を用いることになる。文献 によると、\(G_{{\cal F} \cup f}^{\prime}(\alpha)\)は\(\alpha\)に対して凸関数ではないが、\(\exp(\alpha)\)に関しては下に凸の減少関数、かつ\(\exp(-\alpha)\)に関しては上に凸の増加関数となる事が示されているので、\(\exp(\alpha)、\exp(-\alpha)\)の数列に対してニュートン法を適用する事を考える。偏微分の連鎖律を用いることで,
\begin{align*}
\frac{\partial G_{{\cal F} \cup f}^{\prime}(\alpha)}{\partial \exp(\alpha)} &= \frac{\partial G_{{\cal F} \cup f}^{\prime}(\alpha)}{\partial \alpha} \frac{\partial \alpha}{\partial \exp(\alpha)} \\
&= \frac{\log t}{t} G_{{\cal F} \cup f}^{\prime \prime}(\alpha) \ \ (t = \exp(\alpha)) \\
&= \frac{1}{t} G_{{\cal F} \cup f}^{\prime \prime}(\alpha) = \exp(-\alpha) G_{{\cal F} \cup f}^{\prime \prime}(\alpha)
\end{align*}
が成り立つので、ニュートン法の更新則は、
\begin{align*}
\exp(\alpha_{n+1}) &= \exp(\alpha_{n}) - \frac{G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{\frac{\partial G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{\partial \exp(\alpha_{n})}} = \exp(\alpha_{n}) \left[ 1 - \frac{G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{G_{{\cal F} \cup f}^{\prime\prime}(\alpha_{n})} \right] \\
\iff \alpha_{n+1} &= \alpha_{n} + \log \left[ 1 - \frac{G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{G_{{\cal F} \cup f}^{\prime\prime}(\alpha_{n})} \right] \\
\exp(-\alpha_{n+1}) &= \exp(-\alpha_{n}) - \frac{G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{\frac{\partial G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{\partial \exp(-\alpha_{n})}} = \exp(-\alpha_{n}) \left[ 1 + \frac{G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{G_{{\cal F} \cup f}^{\prime\prime}(\alpha_{n})} \right] \\
\iff \alpha_{n+1} &= \alpha_{n} - \log \left[ 1 + \frac{G_{{\cal F} \cup f}^{\prime}(\alpha_{n})}{G_{{\cal F} \cup f}^{\prime\prime}(\alpha_{n})} \right]
\end{align*}
となる。最適値\(\alpha^{\ast}\)が\(\alpha^{\ast} > 0\)の場合（\(E_{\tilde{P}}[f] > E_{P_{\cal F}}[f]\) ）には上の更新式を用いれば良く、\(\alpha^{\ast} < 0\)の場合（\(E_{\tilde{P}}[f] < E_{P_{\cal F}}[f]\)）には下の更新式を用いれば良い。