Marginalized Kernel

\[
K_M(x,x’) = E_{h}\left[\phi(x,h)\right]^T \cdot E_{h’}\left[\phi(x’,h’)\right]　= \phi_M(x)^T \cdot \phi_M(x’)
\]

HMM as a log linear model

\[ \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_{i,d}(x,h) \log{e_{i,d}}
\end{align} \]
where
\[N^a_{i,j}(h) \mbox{ : the number of times } i \mbox{ to } j \mbox{ transition occured }\]
\[N^e_{i,d}(x,h) \mbox{ : the number of times } d \mbox{ was emitted from state } i\]

Marginalized Count Kernel on HMM

Count feature on HMM

\[
\phi(x,h) = \{N^a, N^e\}
\]

Joint Count Kernel on HMM

\[
K_J((x,h),(x’,h’)) = \{N^a, N^e\}^T \cdot \{N’^a, N’^e\}
\]

Marginalized Count Kernel on HMM

\[
K_M(x,x’) = E_h \left[ \{N^a, N^e\} \right] ^T \cdot E_{h’}\left[ \{N’^a, N’^e\} \right]
\]

Calculation by forward-backward algorithm

\[
E_h \left[ N^a_{i,j} \right] = \frac{1}{p(x|\theta)}\sum_{t=1}^T f_{t-1,i} a_{i,j}e_{j,x_t} b_{t,j} \\
E_h \left[ N^e_{i,d} \right] = \frac{1}{p(x|\theta)}\sum_{t \in \{x_t = d\}}^T f_{t,i} b_{t,i}
\]

演習問題

HMMのforward-backwardアルゴリズムを実装して、
（１）　Baum-Welchアルゴリズムによるパラメータ学習を行うプログラムを作れ
（２）　2本の配列に対するmarginalized count kernelを求めるプログラムを作れ