観測変数\(x\)と隠れ変数\(h\)の同時確率分布が
\[ p(x,h|\theta) = e^{\theta\cdot\phi(x,h)} = \exp[\theta\cdot\phi(x,h)] \]
の下で、\(x\)が与えられた時の\(h\)の条件付き確率は、以下のように与えられる。
\begin{align}
p(h|x,\theta) = \frac{p(x,h|\theta)}{p(x|\theta)} = \frac{1}{Z(x,\theta)}\exp{[\theta\cdot\phi(x,h)]}
\end{align}
ここで分母は、以下のような分配関数である．
\begin{align}
Z(x,\theta) = \sum_{h’}\exp{[\theta\cdot\phi(x,h’)]}
\end{align}
与えられたデータ\(x\)に対して最尤推定\(\hat{h}^{MLE}\)を求める場合は，分母は\(h\)には依存せず共通だから，
\[\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\begin{align}
\hat{h}^{MLE} = \argmax_{h}p(h|x,\theta) = \argmax_{h}\theta\cdot\phi(x,h)
\end{align}
\]

対数線形モデルのパラメータ学習

学習データ（\(x\)と\(h\)のセット）から，以下の式の対数条件付き尤度（LCL; Log Conditional Likelihood）を最大化する\(\theta\)を求めることが目的．
\begin{align}
\log{p(h|x,\theta)} = \theta\cdot\phi(x,h) – \log{Z(x,\theta)}
\end{align}
LCLのパラメータ\(\theta\)による偏微分\(\frac{\partial}{\partial \theta}\log p(h|x;\theta)\)を求めることができれば
\begin{align}
\theta^{new} = \theta^{old} + \epsilon \frac{\partial}{\partial \theta}\log p(h|x;\theta^{old})
\end{align}
LCLのパラメータ\(\theta\)による偏微分は以下のようになる．
\begin{eqnarray}
\frac{\partial}{\partial \theta_j}\log p(h|x;\theta)
&=& \phi_j(x,h) – \frac{\partial}{\partial \theta_j}\log{Z(x,\theta)}\\
&=& \phi_j(x,h) – \frac{1}{Z(x,\theta)}\sum_{h’}\frac{\partial}{\partial \theta_j}Z(x,\theta)
\end{eqnarray}
分配関数\(Z(x,\theta)\)の偏微分は以下のようになる．
\begin{eqnarray}
\frac{\partial}{\partial \theta_j}Z(x,\theta)
&=& \frac{\partial}{\partial \theta_j}\sum_{h’}\left[\exp\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)\right]\\
&=& \sum_{h’}\frac{\partial}{\partial \theta_j}\left[\exp\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)\right]\\
&=& \sum_{h’}\left[\exp\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)\right]
\frac{\partial}{\partial \theta_j}\left[\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)\right]\\
&=& \sum_{h’}\left[\exp\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)\right]\phi_{j}(x,h’)
\end{eqnarray}
したがって，結局LCLの偏微分は以下のようになる．
\begin{eqnarray}
\frac{\partial}{\partial \theta_j}\log p(h|x;\theta)
&=& \phi_j(x,h) – \frac{1}{Z(x,\theta)}\sum_{h’}\phi_{j}(x,h’)\left[\exp\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)\right]\\
&=& \phi_j(x,h) – \sum_{h’}\phi_{j’}(x,h’)\left[\frac{\exp\sum_{j’}\theta_{j’}\phi_{j’}(x,h’)}{Z(x,\theta)}\right]\\
&=& \phi_j(x,h) – \sum_{h’}\phi_j(x,h’)p(h’|x;\theta)\\
&=& \phi_j(x,h) – E_{h’\sim p(h’|x;\theta)}\left[\phi_j(x,h’)\right]
\end{eqnarray}

つまり，学習データ\((x,h)\)にに対する対数条件付き尤度の\(j\)番目の重み\(\theta_j\)による偏微分は，特徴関数の\(x\)、\(h\)に対する値（\(\phi(x,h)\)）から特徴関数の\(h’\)に関する平均値を引いたものとなる．
学習データのセット\(D_T =\{(x^i,h^i)\}\)が与えられた時、大域的な最大値においてはGradientはゼロとなるから，
\begin{align}
\sum_{(x,h)}\phi_j(x,h)=\sum_{x}E_{h\sim p(h|x;\theta)}[\phi_j(x,h)]
\end{align}

演習問題

（１）以上を踏まえて、学習データのセット\(D_T =\{(x^i,h^i)\}\)が与えられた時に判別モデルとしての対数線形モデルのパラメータ学習をどのように行うか、説明せよ。
（２）以下の隠れマルコフモデル、確率文脈自由文法では、学習データのセット\(D_T =\{(x^i,h^i)\}\)が与えられた時のパラメータ学習は、上記のような微分を行うことなく、簡単に行うことができる。その方法と、なぜ簡単になるのかを説明せよ。
（３）学習データとして隠れ状態のわからない\(D_T’ =\{x^i\}\)が与えられた時に用いられる
EMアルゴリズム
と上記の最急降下法を比較してその意味を論ぜよ。

隠れマルコフモデル (HMM)

\[
\begin{align}
\log{p(x,h|A,E)}
&=\sum_{t=1}^T \log{a_{h_t,h_{t-1}}} + \sum_{t=1}^T \log{e_{x_t,h_t}} \\
&=\sum_{i=1}^m \sum_{j=1}^m N^a_{i,j}(h) \log{a_{i,j}}
+\sum_{i=1}^m \sum_{d=1}^D N^e(x,h) \log{e_{i,d}} \\
&= \theta \cdot \phi(x,h) = \log{p(\phi(x,h)|\theta)}
\end{align}
\]

確率文脈自由文法 (SCFG)

\[\begin{align}
\log{p(x,\sigma|\theta)}
&=\sum_{v,y,z\in S} N^t_{v,y,z}(\sigma) \log{t_{v,y,z}}
+\sum_{v\in S,a\in \Sigma} N^e(x,\sigma) \log{e_{v,a}} \\
&= \theta \cdot \phi(x,\sigma) = \log{p(\phi(x,\sigma)|\theta)}
\tag{B.2}\label{eq:scfg_log_linear}
\end{align}\]