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