# Marginalized Count Kernel on HMM

### 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を求めるプログラムを作れ