Conditional Random Field (CRF)では， 対数線形モデル
\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}
の\(\phi(x,h)\)を以下の形に制限する．
\[ \begin{align}
\phi_j(x,h) = \sum_{t=1}^{T}f_j(h_{t-1},h_{t},x,t)
\end{align} \]
ここで、固定された\(x， \theta\)に対して\(g_t(,)\)を以下のように定義する．
\[ \begin{align}
g_t(h_{t-1},h_{t})=\sum_{j=1}^{J}\theta_j f_j(h_{t-1},h_{t},x,t) \label{eq:def-g-crf}
\end{align} \]
すると，
\[ \begin{align}
\theta\cdot\phi(x,h)
= \sum_j^J \theta_j \sum_t^T f_j(h_{t-1},h_t,x,t)
= \sum_t^T \sum_j^J \theta_j f_j(h_{t-1},h_t,x,t)
= \sum_t^T g_t(h_{t-1},h_t)
\end{align} \]
となるから、CRFは以下の形になる．
\[ \begin{align}
p(h|x,\theta) = \frac{1}{Z(x,\theta)}\exp{\sum_{t=1}^{T}g_t(h_{t-1},h_t}) \hspace{3cm} \mbox{(2)}
\end{align} \]
式(2)における\(h\)の最尤推定\(\hat{h}^{MLE}\)は，以下の形に書ける．
\[\newcommand{\argmax}{\mathop{\rm argmax}\limits}
\begin{align}
\hat{h}^{MLE} = \argmax_{h}\sum_{j=1}^{J}\theta_j\sum_{t=1}^{T}f_j(h_{t-1},h_{t},x,t)
= \argmax_{h}\sum_{t=1}^{T}g_t(h_{t-1},h_{t})
\end{align} \]

このモデルの推定において最大化すべきスコア
\[ \begin{align}
\theta\cdot\phi(x,h)
=\sum_{t=1}^{T}g_t(h_{t-1},h_t)
\end{align} \]
を最大化する\(h\)を求めるために， Viterbi変数もどき\(V(k,v)\)を， 位置\(1\)から\(k\)までのベストスコアで位置\(k\)での状態が\(v\)である値と定義する．
\[\begin{align}
V(k,v) = \max_{h,h_k=v} \sum_t^k g_t(h_{t-1},h_t)
\end{align}\]
以下の漸化式が得られる．
\[ \begin{eqnarray}
V(k,v) &=& \max_{h_{1}\ldots h_{k-1}}
\left[\sum_{t=1}^{k-1}g_t(h_{t-1},h_{t}) + g_k(h_{k-1},v)\right]\
&=& \max_{u}\left[V(k-1,u) + g_k(u,v)\right] \hspace{3cm} \mbox{(3)}
\end{eqnarray} \]

演習問題１

\(V(k,v)\)のViterbiアルゴリズムもどきを書き下すために、
式(3)に対応する\(V(k,v)\)の初期値を求めよ．