定义

系统中有若干个状态S1, S2, …, Sn. 随着时间推移，系统会从一个状态转移到另一个状态，马尔可夫模型认为后一个状态和前面若干个状态有关系。

例如天气和前面若干天的天气之间有关系，假如近两天天晴明天天晴的可能性就比较大。

形式化描述：

马尔可夫模型可以表示为一个五元组$\lambda = (S, O, A, B, \pi)$

状态集合S: S = {S1, S2, S3} 描述了模型所有可能的状态，例如上例中{下雨，天晴，刮风…}或{N, V, A, D, P, T, Y}
输出符号集合O: 所有状态输出的集合。例如上面不同颜色的小球
状态转移矩阵A = $a_{ij}$ 。它决定下一个状态。
可观察符号的概率分布矩阵B = $b_j (k)$: 表示在状态j输出符号为k的概率。它决定在当前状态输出什么符号
初始状态概率分布$\pi$: 最开始可能位于什么状态.

两个假设

齐次马尔可夫假设

也就是说当前状态只和前一个状态有关,和其他状态和观测无关，形式化描述为：

$P(s_t | s_{t-1} o_{t-1} ... s_1 o_1 ) = P(s_t | s_{t-1})$

观测独立假设

当前观测只依赖于当前状态，和其他观测及状态无关：

$P(o_t | s_{T} o_{T} ... s_t ... s_1 o_1 ) = P(o_t | s_t )$

评估问题

评估问题是给出一个序列$O = O_1 O_2 … O_n$ 和模型$\lambda$,计算在该模型下观察到O的概率P(O | $\lambda$)

假设模型在时间t的输出序列为$O_1 O_2 … O_t$, 并且位于状态i的概率为

$\alpha_t (i) = P(O_1 O_2 ... O_t , q_t = S_i | \lambda)$

则

$\begin{aligned} \alpha_1 (i) = P(O_1 q_1 = S_i | \lambda) = \pi_i b_i (O_1)\\ \alpha_t (i) = P(O_1 O_2 ... O_t , q_t = S_i | \lambda) = P(), q_t = S_i | \lambda)\\ P(O | \lambda) = \sum_{i=1}{N} a_T (i) (a_T 是最终状态) \end{aligned}$

由上面的公式可以推得一个递推过程，从$a_1 a_2$到$a_T$，然后得出最终结果

算法过程为：

初始化: $\alpha_1 (i) = \pi_I b_i (O_1 ) , 1 \le i \le N$
递归：

$\begin{aligned} \alpha_{t+1}(j) =& P(O_1 O_2 ... O_{t+1}, q_{t+1} = S_j | \lambda)\\ &令O_{t+1} = A \quad O_1 O_2 ... O_t q_{t+1} = S_j | \lambda = B 根据P(AB) = P(A | B) P(B)\\ =& P(O_{t+1} | O_1 O_2 ... O_t q_{t+1} = S_j, \lambda) P(O_1 O_2 ... O_t q_{t+1} = S_j | \lambda) 由观测独立假设可得\\ =& P(O_{t+1} | q_{t+1} = S_j) P(O_1 O_2 ... O_t q_{t+1} = S_j | \lambda)\\ =& b_j (O_{t+1}) \sum_{i=1}^{N} P(O_1 O_2 ... O_t q_{t}=S_i q_{t+1}=S_j | \lambda)(全概率公式)\\ =& b_j (O_{t+1}) \sum_{i=1}^{N} ( P(q_{t+1} = S_j | O_1 O_2 ... O_t q_{t} = S_i, \lambda) P(O_1 O_2 ... O_t q_{t} = S_i | \lambda)\\ =& b_j (O_{t+1}) \sum_{i=1}^{N} (P(q_{t+1} = S_j | q_{t} = S_i) P(O_1 O_2 ... O_t q_{t} = S_i | \lambda)(齐次马尔可夫假设)\\ =& b_j (O_{t+1}) \sum_{i=1}^{N} (a_{ij} \alpha_t (i))\\ 即& \alpha_{t+1}(j) = b_j (O_{t+1}) \sum_{i=1}^{N} (a_{ij} \alpha_t (i)) \end{aligned}$

从结果上看$a{t+1}(j)$就是从上一个状态跳转到j状态的可能性乘上j状态得到O{t+1}的可能性