隐马尔可夫是可用于标准问题的统计学习模型, 描述由隐藏的马尔可夫链随机生成观测序列的过程, 属于生成模型^[1]。其难点是从可观察的参数中确定该过程的隐含参数, 然后利用这些参数来作进一步的分析, 例如模式识别。藏于物理世界中的往往是表象, 而真正的隐藏状态是不可见的, 需要通过观察大量的表象来总结规律, 从而确定事物的隐含状态, 认识事物的本质。事物的隐含状态与事物的表象存在着一定的关联关系, 可以通过统计的方法来确立它们之间的关联。

在隐马尔可夫模型的定义中, Q={q₁, q₂, q₃, …, q_N}是所有可能的状态集合, V={v₁, v₂, v₃, …, v_M}是所有可能的观测集合, I={i₁, i₂, i₃, …, i_T}是长度为T的状态序列, O={o₁, o₂, o₃, …, o_T}是对应的观测序列。

本文通过观察海藻湿度的状态, 确定是雨天还是晴天的例子来推导隐马尔可夫模型的计算推理过程。海藻的湿度为可见状态, 而天气状况为隐藏状态(假设盲人能够感知海藻湿度, 却无法观察天气)。在海藻模型中, 观测概率矩阵为

$ \boldsymbol{B}=\left[b_{j}(k)\right]_{N \times M} $

(1)

式中: b_j(k)——在时刻t处于状态q_j的条件下生成观测v_k的概率, b_j(k)=P(o_t=v_k|i_t=q_j), k=1, 2, 3, …, M; j=1, 2, 3, …, N;

M——观测状态总数;

N——隐藏状态总数。

观测概率矩阵的定义考虑了时间t的因素, 但在分析实际问题时做了简化, 即在任何时刻, 观测概率矩阵都不随时间变化, 因此在理解观测概率矩阵时, 可以把t去掉^[2]。

通过观察海藻的湿度来确定隐含状态, 定义海藻湿度为“dry(干燥)”“dryish(稍干)”“damp(微湿)”“soggy(潮湿)”4个等级。不同的天气状况下观测到的海藻湿度的概率是不同的, 观测数据如表 1所示。

根据b_j(k)的定义, 表 1所列出的概率其实就是观测概率矩阵。因此, b_j(k)中的变量可以理解为: j表示不同的天气状态, k表示不同的海藻湿度等级。条件概率就是定义了在t时刻某个q_j状态下, 某个v_k状态出现的概率。

由于观测概率矩阵不考虑时间因素, 所以b_j(k)也不会随着时间发生变化, 写成矩阵的形式为

$ \boldsymbol{B}=\left[\begin{array}{llll} 0.60 & 0.20 & 0.15 & 0.05 \\ 0.25 & 0.25 & 0.25 & 0.25 \\ 0.05 & 0.10 & 0.35 & 0.50 \end{array}\right] $

隐马尔可夫模型中还定义了状态转换概率矩阵为

$ \boldsymbol{A}=\left[a_{i j}\right]_{N \times N} $

(2)

其中, a_ij=P(i_t+1=q_j|i_t=q_i)(i=1, 2, 3, …, N; j=1, 2, 3, …, N)是在时刻t处于状态q_i的条件下, 在时刻t+1转移到状态q_j的概率。

马尔可夫链是随机变量X₁, X₂, X₃, …, X_N的一个数列。这些变量的范围, 即它们所有可能取值的集合, 被称为“状态空间”, 而X_n的值则是在时间n的状态。如果X_n+1对于过去状态的条件概率分布仅是X_n的一个函数, 则

$ \begin{gathered} P\left(X_{n+1} \mid X_{0}, \cdots, X_{n}\right)=P\left(X_{n+1} \mid X_{n}\right) \cdot \\ P\left(X_{n} \mid X_{n-1}\right) \cdots P\left(X_{1} \mid X_{0}\right) \end{gathered} $

(3)

该式在理论上是完美的, 但在实际运用过程中存在两个问题: 第一, 假设要计算某个连续序列的概率, 而这一概率会随着序列长度的增加不断减小, 最后概率值将小到毫无意义; 第二, 每次计算都要记录前n次的状态, 当序列长度增大时, 数据量将明显增大, 计算量也会变得相当大。因此, 隐马尔可夫模型做了最基本的假设: 当前状态只与前一个状态有关, 即

$ P\left(X_{n+1} \mid X_{0}, \cdots, X_{n}\right)=P\left(X_{n+1} \mid X_{n}\right) $

(4)

针对本文案例来说, 今天的天气状态只受昨天天气状态的影响。但还需考虑时间段不同状态转移矩阵是否相同的问题。

按实际情况来说, 万年前晴天转雨天的概率显然与如今晴天转雨天的概率是不同的, 因此隐马尔可夫模型又做了一个不动性假设(状态概率转移矩阵与时间无关), 即

$ P\left(X_{i+1} \mid X_{i}\right)=P\left(X_{j+1} \mid X_{j}\right), \forall i, j $

(5)

此处的i和j在海藻模型中分别表示地球时间第i天和第j天。

基于时间不动性假设, 就可以统计状态转移的概率。假设历史上只出现了“sunny”“cloudy”“rainy”3种天气状态, 那么就可以统计出某个时间段内, 从一个状态转移至另一状态的频率(这里的频率可以理解为概率), 如表 2所示。

a_ij的定义正好与表 2中从行到列的概率相对应。因此, 状态转换概率矩阵为

$ \boldsymbol{A}=\left[\begin{array}{lll} 0.500 & 0.375 & 0.125 \\ 0.250 & 0.125 & 0.625 \\ 0.250 & 0.375 & 0.375 \end{array}\right] $

设置一个初始状态概率向量π为

$ \boldsymbol{\pi}=\left(\pi_{i}\right) \quad i=1,2,3, \cdots, N $

(6)

其中, π_i=P(i₁=q_i)是时刻t=1时状态q_i出现的概率。

在海藻模型中, 本文给出π=(0.6, 0.2, 0.2)。

一个完整的隐马尔可夫模型是由初始状态概率向量π、状态转移概率矩阵A和观测概率矩阵B所决定的, π和A决定状态序列, B决定观测序列。因此, 隐马尔可夫模型λ可以用三元符号表示, 即λ=(A, B, π), A, B, π称为隐马尔可夫模型的三要素。

隐马尔可夫模型是关于时序的概率模型, 描述由一个隐藏的马尔可夫链随机生成不可观测的状态序列, 再由各个状态生成一个观测结果而产生观测序列的过程。序列的每一个位置可以看作是一个时刻。

在海藻模型中, 盲人每天第一件事情便是感知海藻的湿度, 即每天记录海藻的状态。假设盲人连续记录了3天, 海藻的观测序列为O=(dry, damp, soggy), 则由隐马尔可夫模型可知, 第1天海藻状态为dry, 可能最佳隐藏状态为sunny; 第2天海藻状态为damp, 可能最佳隐藏状态为cloudy; 第3天海藻状态为soggy可能最佳隐藏状态为rainy。由此得到天气的隐藏状态序列为I=(sunny, cloudy, rainy)。

海藻模型中提出了在已知模型λ=(A, B, π)中求解P(O|λ)的问题。

在海藻模型中, 根据观察序列寻找到一个隐藏序列, 该概率可以表示为P(O|I, λ)。显然I序列的个数不只一个, 3种天气状态对应3个序列, I的总数为3×3×3=27个, 假设有N种状态, 对应T个观察序列, 那么I的总数为NT个。

将27个序列一一列举出来, 分别进行计算。对固定的状态序列I={i₁, i₂, i₃, …, i_T}, 观测序列O={o₁, o₂, o₃, …, o_T}的概率为

$ \begin{gathered} P(O \mid I, \lambda)=b_{i 1}\left(o_{1}\right) b_{i 2}\left(o_{2}\right) \cdot \\ b_{i 3}\left(o_{3}\right) \cdots b_{i T}\left(o_{T}\right) \end{gathered} $

(7)

由于上述概率P(O|I, λ)是条件概率, 即假定每个隐藏序列是已知的, 故观测到的海藻状态与状态转移矩阵没有关系, 只与其观测概率分布有关。如, 已知3天的天气状态均为sunny, 那么P(O={dry, damp, soggy}|I={sunny, sunny, sunny}, λ)=b₁(1)b₁(3)b₁(4)=0.60×0.15×0.05=0.004 5。

在状态转移矩阵中, 只要知道初始状态概率向量π, 就能够从某个时刻推断一连串隐藏状态序列的概率

$ P(I \mid \lambda)=\pi_{i_{1}} a_{i_{1} i_{2}} a_{i_{2} i_{3}} \cdots a_{i_{T-1} i_{T}} $

(8)

式(8)对马尔可夫链的一阶假设进行了很好的简化。比如, 第1天天气状态为sunny的概率为初始概率, 已知; 第2天为sunny的概率只与第1天的状态有关, 也就是状态转移矩阵中sunny→sunny的概率; 第3天仍为sunny的概率也只与前一天相关, 即sunny→sunny的概率。因此, 隐藏状态从一个状态转移至另一个状态, 每次只要乘以状态转移矩阵中的某个值即可。

根据I出现的概率, 以及在I出现的条件下O出现的概率, 可以求得联合概率为

$ \begin{aligned} &P(O, I \mid \lambda)=P(O \mid I, \lambda) P(I \mid \lambda)= \\ &\pi_{i} b_{i 1}\left(o_{1}\right) a_{i 1 i_{2}} b_{i_{2}}\left(o_{2}\right) \cdots a_{i_{T-1} i_{T}} b_{i_{T}}\left(o_{T}\right) \end{aligned} $

(9)

然后, 对所有可能的状态序列I求和, 得到观测序列O的概率P(O|λ), 即

$ \begin{gathered} P(O \mid \lambda)=\sum I P(O \mid I, \lambda) P(I \mid \lambda)= \\ \sum i_{1}, i_{2} \cdots i_{T} \pi_{i} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \cdots \\ a_{i_{T-1} i_{T}} b_{i_{T}}\left(o_{T}\right) \end{gathered} $

(10)

上述算法不记忆先前的计算结果, 算法传播到第3个状态后, 一切推倒, 重新计算。因此, 这种算法在数据量大的情况下是不可行的。

在程序中有用空间换时间的思想, 其实在数学公式中也是通用的。采用中间变量来记录结果, 并利用该中间变量来计算后续节点, 那么很明显可以极大地简化计算次数^[3], 减少计算量。

根据给定的模型参数λ计算出P(O|λ)的值, 给定一连串输入序列。对每个单词进行标注, 从而使得整个隐藏序列对于观测序列来说概率最大^[4], 即P(I|O)最大。维特比算法是用动态规划解隐马尔可夫模型预测问题, 即用动态规划求解概率最大路径(最优路径), 这时一条路径对应着一个状态序列。

动态规划的原理是: 如果最优路径在时刻t通过节点i_t^*, 那么从节点i_t^*到终点i_T^*的部分路径, 对于从i_t^*到i_T^*所有可能的部分路径来说, 必须是最优的。

在t=1时刻, 对于每一个状态i(i=1, 2, 3), 求状态i下观测o₁是sunny的概率δ₁(i)为

$ \begin{gathered} \delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right)=\pi_{i} b_{i}(\text { sunny }), \\ i=1,2,3 \end{gathered} $

(11)

代入实际数据后, 可得δ₁(1)=0.10, δ₁(2)=0.16, δ₁(3)=0.28。

对于t=1时刻, 每个隐藏状态i可能出现sunny的概率与初始状态有关, 与转移概率无关。在t=2时刻, 对于不同的隐藏状态, 有3条路径同时到达, 此时不再计算3条路径的概率和, 而是取其中概率最大的1条, 代表从t时刻转移至t+1时刻, 某一隐藏状态序列i_t, i_t+1出现o_t, o_t+1的概率最大。用公式表示为

$ \delta_{2}(i)=\max \limits_{1 \leqslant j \leqslant 3}\left[\delta_{1}(j) a_{j i}\right] b_{i}\left(o_{2}\right) $

(12)

计算可得: δ₂(1)=0.028, δ₂(2)=0.050 4, δ₂(3)=0.042。同理, 在t=3时刻, 有

$ \delta_{3}(i)=\max \limits_{1 \leqslant j \leqslant 3}\left[\delta_{2}(j) a_{j i}\right] b_{i}\left(o_{3}\right) $

(13)

可得, δ₃(1)=0.007 56, δ₃(2)=0.010 08, δ₃(3)=0.014 7。

用P^*表示最优路径的概率, 则

$ P^{*}=\max \limits_{1 \leqslant j \leqslant 3} \delta_{3}(i)=0.014\ 7 $

(14)

那么最优路径的终点

$ i_{3}{ }^{*}=\max \limits_{i}\left[\delta_{3}(i)\right]=3 $

(15)

记录路径经过节点的变量定义为

$ \begin{aligned} \psi_{t}(i) &=\arg \max \limits_{i}\left[\delta_{t-1} a_{j i}\right] \\ i &=1,2,3, \cdots, N \end{aligned} $

(16)

根据该函数的定义, 就可以根据最大概率路径找回所有的节点, 即t=2时, i₂^*=ψ₃(i₃^*)=ψ₃(3)=3;t=1时, i₁^*=ψ₂(i₂^*)=ψ₂(3)=3。

于是求得最优路径, 即最优状态序列I^*=(i₁^*, i₂^*, i₃^*)=(3, 3, 3)。

隐马尔可夫模型参数的估计问题是一个隐藏变量的极大似然估计。对隐马尔可夫预测模型求偏导, 得到极大似然函数的极值, 再计算联合概率, 而联合概率的计算巧妙地使用了节点图的各种性质, 用中间变量降低了节点计算的复杂度, 导出了对计算有帮助的定义, 方便了参数求解。