配列データとそれに対応する隠れ状態列を明示的に\(\bar{x}=x_1,\ldots , x_T\)，
\(\bar{y}=y_1,\ldots , y_T\)と書くことにする．
Conditional Random Field (CRF)では，
(ref{eq:general-log-linear})式の\(F_j(,)\)を以下の形に制限する．
\[\begin{align}
F_j(\bar{x},\bar{y}) = \sum_{t=1}^{T}f_j(y_{t-1},y_{t},\bar{x},t)
\end{align}\]
ここで、固定された\(\bar{x}， w\)に対して\(g_t(,)\)を以下のように定義する．
\[\begin{align}
g_t(y_{t-1},y_{t})=\sum_{j=1}^{J}w_jf_j(y_{t-1},y_{t},\bar{x},t) \label{eq:def-g-crf}
\end{align} \]
すると，CRFは以下の形になる．
\[\begin{align}
p(\bar{y}|\bar{x};w) = \frac{\exp{\sum_{t=1}^{T}g_t(y_{t-1},y_t})}{Z(\bar{x},w)} \label{eq:crf}
\end{align} \]
式(ref{eq:crf})における\(\bar{y}\)の最尤推定\(\hat{y}^{MLE}\)は，以下の形に書ける．
\[\begin{align}
\hat{y}^{MLE} = argmax_{\bar{y}}\sum_{j=1}^{J}w_j\sum_{t=1}^{T}f_j(y_{t-1},y_{t},\bar{x},t)
= argmax_{\bar{y}}\sum_{t=1}^{T}g_t(y_{t-1},y_{t})
\end{align}\]

%%
%%
%% $¥bar{x}$，$w$，$t$を固定して考えると，$g_t(,)$は$m$×$m$の行列
%%（$m$は状態の種類の数）として表現できる．
%% 特徴関数$f_j(,,,)$が constant time で計算できると仮定すると，
%% $g_t(,)$を1つの$i$について計算するのには，$O(m^2J)$の計算時間がかかる．

このモデルの推定において最大化すべきスコア
\[\begin{align}
\sum_{j=1}^{J}w_j F_j(\bar{x},\bar{y}) =\sum_{t=1}^{T}g_t(y_{t-1},y_t)
\end{align}\]
を最大化する$\bar{y}$を求めるために， Viterbi変数もどき$V(k,v)$を， 位置$1$から$k$までのベストスコアで位置$k$での状態が$v$である値と定義すると、以下の漸化式が得られる．
\[\begin{eqnarray}
V(k,v) &=& \max_{y_{1}\ldots y_{k-1}}
\left[\sum_{t=1}^{k-1}g_t(y_{t-1},y_{t}) + g_k(y_{k-1},v)\right]\\
&=& \max_{u}\left[V(k-1,u) + g_k(u,v)\right] \label{eq:Viterbi-crf}
\end{eqnarray}\]
%%

演習問題

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