2. 隐马尔可夫模型
2.1. 模型定义
在马尔可夫模型中，每个状态代表了一个可观察的事件，所以，马尔可夫模型有时又称作可视马尔可夫模型（visible Markov model，VMM），这在某种程度上限制了模型的适应性。隐马尔可夫模型（hidden Markov model，HMM）是概率图模型中的一种有向图模型。隐马尔科夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列（state sequence）；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列（observation sequence）。序列的每一个位置又可以看作是一个时刻。图 1 1 1 说明隐马尔可夫模型的基本原理。
图 1 HMM 图解
我们可以通过如下例子来说明 HMM 的含义。假定一暗室中有 N N N 个盒子，每个盒子中有 M M M 种不同颜色的球。一个实验员根据某一概率分布随机地选取一个初始盒子，从中根据不同颜色的球的概率分布，随机地取出一个球，并向室外的人报告该球的颜色。将球放回原盒子中，再根据盒子的概率分布选择另一个盒子，根据不同颜色的球的概率分布从中随机选择另外一个球。重复进行这个过程。对于暗室外边的人来说，可观察的过程只是不同颜色的球的序列，而盒子的序列是不可观察的。在这个过程中，每个盒子对应于 HMM 中的（隐）状态，球的颜色对应于 HMM 中状态的输出符号，从一个盒子转向另一个盒子对应于状态转换，从盒子中取出球的颜色对应于从一个状态输出的观测符号。
通过上例可以看出，隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定，这三部分中隐含了模型中可能的状态数和可能的观测数。隐马尔可夫模型的形式定义如下：
设 Q Q Q 是所有可能的状态的集合， V V V 是所有可能的观测的集合：
Q = { q 1 , q 2 , … , q N } , V = { v 1 , v 2 , … , v M } Q = \{q_1,q_2,\dots,q_N\},\space\space\space\space V = \{v_1,v_2,\dots, v_M\} Q={q1,q2,…,qN}, V={v1,v2,…,vM}
其中， N N N 是可能的状态数， M M M 是可能的观测数。
S S S 是长度为 T T T 的状态序列， O O O 是对应的观测序列：
S = ( s 1 , s 2 , … , s T ) , O = ( o 1 , o 2 , … , o T ) S = (s_1,s_2,\dots, s_T),\space\space\space\space O = (o_1,o_2,\dots,o_T) S=(s1,s2,…,sT), O=(o1,o2,…,oT)
A A A 是状态转移概率矩阵：
A = [ a i j ] N × N A = [a_{ij}]_{N\times N} A=[aij]N×N
其中，
a i j = P ( s t + 1 = q j ∣ s t = q i ) , 1 ≤ i , j ≤ N a i j ≥ 0 ∑ j = 1 N a i j = 1 \begin{array}{l} a_{ij} = P(s_{t+1} = q_j\mid s_t = q_i),\space\space\space\space 1\le i,j \le N\\ a_{ij} \ge0\\ \sum\limits_{j=1}^N a_{ij} = 1 \end{array} aij=P(st+1=qj∣st=qi), 1≤i,j≤Naij≥0j=1∑Naij=1
表示在时刻 t t t 处于状态 q i q_i qi 的条件下在时刻 t + 1 t+1 t+1 转移到状态 q j q_j qj 的概率。
B B B 是观测概率矩阵：
B = [ b j ( k ) ] N × M B = [b_j(k)]_{N\times M} B=[bj(k)]N×M
其中，
b j ( k ) = P ( o t = v k ∣ s t = q j ) , 1 ≤ k ≤ M ; 1 ≤ j ≤ N b j ( k ) ≥ 0 ∑ k = 1 M b j ( k ) = 1 \begin{array}{l} b_j(k) = P(o_t = v_k\mid s_t = q_j),\space\space\space\space 1\le k \le M;1\le j \le N \\ b_j(k) \ge 0 \\ \sum \limits_{k=1}^M b_j(k) = 1 \end{array} bj(k)=P(ot=vk∣st=qj), 1≤k≤M;1≤j≤Nbj(k)≥0k=1∑Mbj(k)=1
是在时刻 t t t 处于状态 q j q_j qj 的条件下生成观测 v k v_k vk 的概率。
π \pi π 是初始状态概率向量：
π = ( π i ) \pi = (\pi_i) π=(πi)
其中，
π i = P ( s 1 = q i ) , 1 ≤ i ≤ N π i ≥ 0 ∑ i = 1 N π i = 1 \begin{array}{l} \pi_i = P(s_1 = q_i),\space\space\space\space 1\le i\le N \\ \pi_i \ge 0\\ \sum \limits_{i=1}^N\pi_i = 1 \end{array} πi=P(s1=qi), 1≤i≤Nπi≥0i=1∑Nπi=1
是时刻 t = 1 t =1 t=1 处于状态 q i q_i qi 的概率。
隐马尔可夫模型由初始状态概率向量 π \pi π、状态转移概率矩阵 A A A 和观测概率矩阵 B B B 决定。 π \pi π 和 A A A 决定状态序列， B B B 决定观测序列。因此，隐马尔可夫模型入可以用三元符号表示，即
λ = ( A , B , π ) \lambda = (A,B,\pi) λ=(A,B,π)
状态转移概率矩阵 A A A 与初始状态概率向量 π \pi π 确定了隐藏的马尔可夫链，生成不可观测的状态序列。观测概率矩阵 B B B 确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。
从定义可知，隐马尔可夫模型作了两个基本假设：
- 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻 t t t 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 t t t 无关：
P ( s t ∣ o t − 1 , o t − 2 , … , o 1 , s t − 1 , s t − 2 , … , s 1 ) = P ( s t ∣ s t − 1 ) , 1 ≤ t ≤ T P(s_t\mid o_{t-1},o_{t-2},\dots,o_1,s_{t-1},s_{t-2},\dots,s_1) = P(s_t\mid s_{t-1}),\space\space\space\space 1\le t \le T P(st∣ot−1,ot−2,…,o1,st−1,st−2,…,s1)=P(st∣st−1), 1≤t≤T - 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关：
P ( o t ∣ o T , o T − 1 , … , o t + 1 , o t − 1 , … , o 1 , s T , s T − 1 , … , s 1 ) = P ( o t ∣ s t ) P(o_t\mid o_T,o_{T-1},\dots, o_{t+1},o_{t-1},\dots, o_1,s_T,s_{T-1},\dots, s_1) = P(o_t\mid s_t) P(ot∣oT,oT−1,…,ot+1,ot−1,…,o1,sT,sT−1,…,s1)=P(ot∣st)
隐马尔可夫模型可以用于标注，这时状态对应着标记。标注问题是给定观测的序列预测其对应的标记序列。可以假设标注问题的数据是由隐马尔可夫模型生成的。这样我们可以利用隐马尔可夫模型的学习与预测算法进行标注。
依然是以上面提到的“盒子与球模型”为例，理解一下具体的 HMM。
假设有 4 4 4 个盒子，每个盒子里都装有红、白两种颜色的球，盒子里的红、白球数由下表列出。
按照下面的方法抽球，产生一个球的颜色的观测序列：
- 开始，从 4 4 4 个盒子里以等概率随机选取 1 1 1 个盒子，从这个盒子里随机抽出 1 1 1 个球，记录其颜色后，放回；
- 然后，从当前盒子随机转移到下一个盒子，规则是：如果当前盒子是盒子 1 1 1，那么下一盒子一定是盒子 2 2 2；如果当前是盒子 2 2 2 或 3 3 3，那么分别以概率 0.4 0.4 0.4 和 0.6 0.6 0.6 转移到左边或右边的盒子；如果当前是盒子 4 4 4，那么各以 0.5 0.5 0.5 的概率停留在盒子 4 4 4 或转移到盒子 3 3 3；
- 确定转移的盒子后，再从这个盒子里随机抽出 1 1 1 个球，记录其颜色，放回；
- 如此下去，重复进行 5 5 5 次，得到一个球的颜色的观测序列： O = ( O=( O=(红 , , , 红 , , , 白 , , , 白 , , , 红 ) ) )。
在这个过程中，观察者只能观测到球的颜色的序列，观测不到球是从哪个盒子取出的，即观测不到盒子的序列。
在这个例子中有两个随机序列，一个是盒子的序列（状态序列），一个是球的颜色的观测序列（观测序列）。前者是隐藏的，只有后者是可观测的。这是一个隐马尔可夫模型的例子。根据所给条件，可以明确状态集合、观测集合、序列长度以及模型的三要素。
盒子对应状态，状态的集合是：
Q = { 盒 子 1 , 盒 子 2 , 盒 子 3 , 盒 子 4 } , N = 4 Q = \{盒子\space1,盒子\space2,盒子\space3,盒子\space4\},\space\space\space\space N=4 Q={盒子 1,盒子 2,盒子 3,盒子 4}, N=4
球的颜色对应观测，观测的集合是：
V = { 红 , 白 } , M = 2 V = \{红,白\},\space\space\space\space M=2 V={红,白}, M=2
状态序列和观测序列长度 T = 5 T=5 T=5。
初始概率分布为
π = ( 0.25 , 0.25 , 0.25 , 0.25 ) T \pi = (0.25,0.25,0.25,0.25)^T π=(0.25,0.25,0.25,0.25)T
状态转移概率分布为
A = [ 0 1 0 0 0.4 0 0.6 0 0 0.4 0 0.6 0 0 0.5 0.5 ] A = \left[\begin{matrix} 0 & 1 & 0 & 0 \\ 0.4 & 0 & 0.6 & 0 \\ 0 & 0.4 & 0 & 0.6 \\ 0 & 0 & 0.5 & 0.5 \\ \end{matrix}\right] A=⎣⎢⎢⎡00.400100.4000.600.5000.60.5⎦⎥⎥⎤
观测概分布为
B = [ 0.5 0.5 0.3 0.7 0.6 0.4 0.8 0.2 ] B = \left[\begin{matrix} 0.5 & 0.5 \\ 0.3 & 0.7 \\ 0.6 & 0.4 \\ 0.8 & 0.2 \\ \end{matrix}\right] B=⎣⎢⎢⎡0.50.30.60.80.50.70.40.2⎦⎥⎥⎤
2.2. 三个基本问题
- 估计（Evaluation）问题。给定模型 λ = ( A , B , π ) \lambda= (A,B,\pi) λ=(A,B,π) 和观测序列 O = ( o 1 , o 2 , … , o T ) O = (o_1,o_2,\dots,o_T) O=(o1,o2,…,oT)，计算在模型参数 λ \lambda λ 下观测序列 O O O 出现的概率 P ( O ∣ λ ) P(O\mid \lambda) P(O∣λ)。换言之，如何评估模型与观测序列之间的匹配程度？
- 学习（learning）问题。已知观测序列 O = ( o 1 , o 2 , … , o T ) O=(o_1,o_2,\dots,o_T) O=(o1,o2,…,oT)，估计模型 λ = ( A , B , π ) \lambda = (A,B,\pi) λ=(A,B,π) 参数，使得在该模型下观测序列概率 P ( O ∣ λ ) P(O\mid \lambda) P(O∣λ) 最大。换言之，如何训练模型使其能最好地描述观测序列？即用极大似然估计的方法估计参数。
- 解码（decoding）问题。已知模型 λ = ( A , B , π ) \lambda=(A,B,\pi) λ=(A,B,π) 和观测序列 O = ( o 1 , o 2 , … , o T ) O=(o_1,o_2,\dots,o_T) O=(o1,o2,…,oT)，求对给定观测序列条件概率 P ( S ∣ O ) P(S\mid O) P(S∣O) 最大的状态序列 S = ( s 1 , s 2 , … , s T ) S = (s_1,s_2,\dots,s_T) S=(s1,s2,…,sT)。换言之，如何根据给定的观测序列推断出最有可能对应的状态序列？
这三个问题的解决是隐马尔可夫模型得以广泛使用的前提。问题一和问题二本质上都是在讨论模型训练，问题一的解决为问题二中的极大似然估计提供了计算上的支持，无法计算出 P ( O ∣ λ ) P(O\mid \lambda) P(O∣λ) 就无法进行极大似然估计。另外，观察问题一和问题二，问题一中需要已知模型参数 λ \lambda λ，问题二的输出结果为模型参数 λ \lambda λ，这显然要通过迭代的方式优化模型参数。问题三则将模型推向应用，在分词标注、机器翻译等具体问题上，问题三输出的状态序列就是我们想要的结果。