隐马模型

机器学习

---

Basic Concepts

Let $Q = \left\{ q_1, q_2, \dots, q_N \right\}$ denote state set, $V = \left\{ v_1, v_2, \dots, v_M \right\}$ denote observation set, $I = (i_1, i_2, \dots, i_N)$ denote state sequence, and $O = (o_1, o_2, \dots, o_N)$ denote corresponding observation sequence.

$A = \left[ a_{ij} \right]_{N \times N}$ is state transfer matrix, where

$$a_{ij} = P(i_{i+1} = q_j \mid i_t = q_i), i = 1, 2, \dots, N; j = 1, 2, \dots, N$$

$B = \left[ b_{ij} \right]_{N \times M}$ is observation probability matrix, where

$$b_j(k) = P(o_t = v_k \mid i_t = q_j), k = 1, \dots, M; j = 1, \dots, N$$

$\pi$ is initial state probability vector, where $\pi_i = P(i_1 = q_i)$.

Calculalate Probability

Given $\lambda = (A, B, \pi)$ and $O$, find $P(O \mid \lambda)$.

By force

$$P(O \mid \lambda) = \sum_I P(O \mid I, \lambda) P(I \mid \lambda)$$

Forward

Define forward probability as

$$\alpha_t(i) = P(o_1, o_2, \dots, o_t, i_t = q_i \mid \lambda)$$

Input: Hidden markov model $\lambda$ and observation sequance $O$;
Output: Observation sequence probability $P(O \mid \lambda)$.

1. Initialize:
   $$\alpha_1(i) = \pi_i b_i(o_1)$$
2. Deduct:
   $$\alpha_{t+1}(i) = \left[ \sum_{j=1}^N \alpha_t(j) a_{ji} \right] b_i(o_{t+1})$$
3. Terminate
   $$P(O \mid \lambda) = \sum_{i=1}^N \alpha_T(i)$$

Backward

Define backward probability as

$$\beta_t(i) = P(o_{t+1}, \dots, o_T \mid i_t = q_i, \lambda)$$

Input: Hidden markov model $\lambda$ and observation sequance $O$;
Output: Observation sequence probability $P(O \mid \lambda)$.

1. Initialize:
   $$\beta_1(i) = 1$$
2. Deduct:
   $$\alpha_{t}(i) = \left[ \sum_{j=1}^N a_{ij} b_j(o_{t+1})\beta_{t+1}(j) \right]$$
3. Terminate
   $$P(O \mid \lambda) = \sum_{i=1}^N \pi_i b_i(o_1) \beta_1(i)$$

Some probabilities and expectations

Let $\gamma_t(i)$ denote probabity at state $q_i$ at time $t$

$$\gamma_t(i) = P(i_t = q_i \mid O, \lambda) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(i) \beta_t(i)}$$

Learning Algorithm

TODO: Solve it with EM.

Predication Algorithm

Approximation

Most likely state $i_t^*$ at time $t$ is

$$i_t^* = \mathrm{argmax}_{1 \le i \le N} \left[ \gamma_t(i) \right]$$

It's not necessary the most likely state sequence, but it's still quite useful.

Viterbi algorithm

1. Init
   

   $$\delta_1(i) = \pi_ib_i(o_1), i = 1, 2, \dots, N$$
   $$\psi_i(i) = 0, i = 1, 2, \dots, N$$

2. Deduct, for $t = 2, \dots, T$
   

   $$\begin{align} \delta_t(i) = & \max_{1\le j\lt N} \left[ \delta_{t-1}(j) a_{ji} \right] b_i(o_t), & i = 1, 2, \dots, N \\ \phi_t(i) = & \mathrm{argmax}_{1\le j\lt N}(i) \left[ \delta_{t-1}(j) a_{ji} \right], & i = 1, 2, \dots, N \end{align}$$

3. Terminate
   

   $$P^* = \max_{1\le j\lt N} \delta_T(i)$$
   $$i_T^* = \mathrm{argmax}_{1\le j\lt N} \left[ \delta_T(i) \right]$$