隐马尔可夫模型（HMM）

HMM: Hidden Markov Model

由隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程
状态序列（state sequence）:隐藏的马尔科夫链随机生成的状态序列
观测序列（observation sequence）：每个状态生成的观测产生的随机序列
$Q$ ：所有可能的状态集合， $V$ ：所有可能的观测集合 $Q = \{q_1, q_2, …, q_N\},V= \{v_1, v_2, …, v_M\}$
$I$ :长度为 $T$ 的状态序列，O是对应的观测序列 $I = \{i_1, i_2, …, i_T\} O = \{o_1, o2, …, oT\}$
$A$ : 状态转移概率矩阵 $A = [a_{ij}]_{N*N}$ , $a_{ij}$ 指的是在 $t$ 时刻处于状态 $q_i$ 在 $t+1$ 转移到 $q_j$ 的概率
$B$ ：观测概率矩阵 $B = [b_j(k)]_{N*M}$ , $b_j(k)$ 在t时刻处于状态 $q_j$ 的条件下生成观测 $v_k$ 的概率
$\pi$ 是初始状态概率向量 $\pi = (π_i)$ ，时刻 $t=1$ 处于 $q_i$ 的概率
$\lambda = \{ A, B, \pi \}$
$A$ 和 $\pi$ 确定了隐藏的马尔科夫链，生成不可观测的状态序列
$B$ 确定了如何从状态序列生成观测序列
两个基本假设
- 齐次马尔可夫性：隐藏马尔科夫链在任意时刻的状态只依赖于前一时刻状态，且与t无关
- 观测独立性假设：任意时刻的观测只依赖于该时刻的隐马尔可夫链状态

计算所有可能长度为 $T$ 的状态序列 $I$ ，求各个观测序列的联合概率，然后对所有可能的状态序列求和，得到 $P(O|\lambda)$ 。复杂度 $O(TN^T)$ ，计算量大。

前向概率：给定隐马尔科夫模型 $\lambda$ ，定义到时刻 $t$ 部分观测序列，其状态 $q_i$ 的概率， $\alpha_t(i) = P(o_1, o_2, ..., o_t, i_t=q_t|\lambda)$
观测序列概率的前向算法

初值： $\alpha_1(i)=\pi_i b_i (o_1), i=1,2,...,N$
递推：对 $t=1,2,...,T-1$ ， $\alpha_{t+1}(i)=\left [\sum_{j=1}^N \alpha_t(j) \alpha_{ji}\right ] b_i(o_{t+1}), i = 1,2,...,N$
终止： $P(O|\lambda)=\sum_{i=1}^N \alpha_T(i)$

计算量: $O(N^2T)$

后向概率：给定HMM模型 $\lambda$ ，定义在时刻 $t$ 状态为 $q_i$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的概率为后向概率， $\beta_t(i) = P(o_{t+1},o_{t+2},...,o_T|i_t=q_i,\lambda)$
算法：观测序列概率的后向算法

$\beta_T(i) = 1, i = 1,2,...,N$
对 $t=T-1,T-2,...,1$ , $\beta_t(i) = \sum_{j=1}^N a_{ij}b_j(a_{t+1})\beta_{t+1}(j), i = 1,2,...,N$
$P(O|\lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i)$