1. 马尔可夫模型
在介绍隐马尔可夫模型之前，先来介绍马尔可夫模型。
我们知道，随机过程又称随机函数，是随时间而随机变化的过程。马尔可夫模型（Markov model）描述了一类重要的随机过程。我们常常需要考察一个随机变量序列，这些随机变量并不是相互独立的，每个随机变量的值依赖于这个序列前面的状态。如果一个系统有 N N N 个有限状态 Q = { q 1 , q 2 , … , q N } Q=\{q_1,q_2,\dots,q_N\} Q={q1,q2,…,qN}，那么随着时间的推移，该系统将从某一状态转移到另一状态。 S = { s 1 , s 2 , … , s T } S=\{s_1,s_2,\dots,s_T\} S={s1,s2,…,sT} 为一个随机变量序列，随机变量的取值为状态集 Q Q Q 中的某个状态，假定在时刻 t t t 的状态记为 s t s_t st。对该系统的描述通常需要给出当前时刻 t t t 的状态和其前面所有时刻状态的关系：系统在时刻 t t t 的状态 q j q_j qj 的概率取决于其在时刻 1 , 2 , … , t − 1 1,2,\dots,t-1 1,2,…,t−1 的状态，该概率为
P ( s t = q j ∣ s t − 1 = q i , s t − 2 = q k , … ) P(s_t = q_j\mid s_{t-1} = q_i,s_{t-2}=q_k,\dots) P(st=qj∣st−1=qi,st−2=qk,…)
如果在特定条件下，系统在时刻 t t t 的状态只与其在时刻 t − 1 t-1 t−1 的状态相关，即
P ( s t = q j ∣ s t − 1 = q i , s t − 2 = q k , … ) = P ( s t = q j ∣ s t − 1 = q i ) P(s_t = q_j\mid s_{t-1} = q_i,s_{t-2}=q_k,\dots)=P(s_t = q_j\mid s_{t-1} = q_i) P(st=qj∣st−1=qi,st−2=qk,…)=P(st=qj∣st−1=qi)
则该系统构成一个离散的一阶马尔可夫链（Markov chain）。进一步，如果只考虑上式独立于时刻 t t t 的随机过程：
P ( s t = q j ∣ s t − 1 = q i ) = a i j , 1 ≤ i , j ≤ N P(s_t = q_j\mid s_{t-1} = q_i)=a_{ij},\space\space\space\space 1\le i,j\le N P(st=qj∣st−1=qi)=aij, 1≤i,j≤N
该随机过程为马尔可夫模型。其中，状态转移概率 a i j a_{ij} aij 必须满足以下条件：
a i j ≥ 0 ∑ j = 1 N a i j = 1 a_{ij}\ge 0 \\ \sum_{j=1}^N a_{ij}=1 aij≥0j=1∑Naij=1
显然，有 N N N 个状态的一阶马尔可夫过程有 N 2 N^2 N2 次状态转移，其 N 2 N^2 N2 个状态转移概率可以表示成一个状态转移矩阵。例如，一段文字中名词、动词、形容词三类词性出现的情况可由三个状态的马尔可夫模型描述：
状态 q 1 q_1 q1 表示名词，状态 q 2 q_2 q2 表示动词，状态 q 3 q_3 q3 表示形容词。假设状态之间的转移矩阵如下：
A = [ a i j ] = q 1 q 2 q 3 q 1 q 2 q 3 [ 0.3 0.5 0.2 0.5 0.3 0.2 0.4 0.2 0.4 ] A = [a_{ij}]=\space\space \begin{matrix} \begin{matrix} & q_1&\space\space q_2\space\space & q_3 \end{matrix} \\ \begin{matrix} q_1\\q_2\\q_3 \end{matrix} \left[\begin{matrix} 0.3 & 0.5 & 0.2 \\ 0.5 & 0.3 & 0.2 \\ 0.4 & 0.2 & 0.4 \\ \end{matrix} \right] \end{matrix} A=[aij]= q1 q2 q3q1q2q3⎣⎡0.30.50.40.50.30.20.20.20.4⎦⎤
如果在该段文字中某一句子的第一个词为名词，那么根据这一模型 M M M，在该句子中这三类词的出现顺序为 O = O= O=“名动形名” 的概率为
P ( O ∣ M ) = P ( q 1 , q 2 , q 3 , q 1 ∣ M ) = P ( q 1 ) ⋅ P ( q 2 ∣ q 1 ) ⋅ P ( q 3 ∣ q 2 ) ⋅ P ( q 1 ∣ q 3 ) = 1 × a 12 × a 23 × a 31 = 0.5 × 0.2 × 0.4 = 0.04 \begin{aligned} P(O\mid M) &= P(q_1,q_2,q_3,q_1\mid M)\\ &=P(q_1)·P(q_2\mid q_1)·P(q_3\mid q_2) ·P(q_1\mid q_3) \\ &= 1\times a_{12} \times a_{23} \times a_{31} \\ &= 0.5\times 0.2\times 0.4\\ &= 0.04 \end{aligned} P(O∣M)=P(q1,q2,q3,q1∣M)=P(q1)⋅P(q2∣q1)⋅P(q3∣q2)⋅P(q1∣q3)=1×a12×a23×a31=0.5×0.2×0.4=0.04
另外， m m m 阶马尔可夫假设为当前时刻状态仅依赖于其前 m m m 个时刻的状态，满足 m m m 阶马尔可夫假设的模型为 m m m 阶马尔可夫模型。