隐马尔可夫模型
文章目录
-
隐马尔可夫模型简介
-
- 隐马尔可夫模型的定义
-
隐马尔可夫模型的三个核心问题
-
概率推算方法
-
- 直接求解方式
- 正向推导过程
- 反向推导过程
-
学习算法
-
- 监督学习方法
- Baum-Welch算法(非监督)
-
预测算法
-
隐马尔可夫模型简介
隐式马尔科夫模型(HM, HMM)是一种用于标注任务的统计学习方法。它通过隐式马尔科夫链来随机生成观测序列的过程进行建模，并归类于生成模型的一种。在序列中每个位置被视为一个时间点。
隐马尔可夫模型的定义
定义 (隐马尔可夫模型)
设Q是所有可能的状态的集合，V是所有可能的观测的集合.
Q={q_1,q_2,\dots q_N},\ \ V={v_1,v_2,\dots v_M}
其中，N是可能的状态数，M是可能的观测数.
I是长度维T的状态序列，O是对应的观测序列.
I={i_1,i_2,\dots i_T},\ \ O={_1,o_2,\dots o_T}
A是状态转移概率矩阵:
\begin{aligned} A = \Big[a_{ij}\Big]_{N\times N}\tag{1.1} \end{aligned}
其中，
a_{ij} = P(i_{t+1}=q_j|i_t=q_i),\ \ \ \ \ i=1,2,\dots N \tag{1.2}
是在时刻t处于状态q_i的条件下在时刻t+1转移到状态q_j的概率.
B是观测概率矩阵:
\begin{aligned} B = \Big[b_j(k)\Big]_{N\times M}\tag{1.3} \end{aligned}
其中，
b_j = P(o_t=v_k|i_t=q_j),\ \ \ \ \ k=1,2,\dots M,j=1,2,\dots N \tag{1.4}
是在时刻t处于状态q_j的条件下生成观测v_k的概率.
\pi被定义为初始状态的概率分布向量：
隐马尔科夫模型通过初始状态概率向量\pi, 状态转移概率矩阵A以及观测概率矩阵B来确定其行为模式。
其中的状态序列由A和π共同决定，
而观测序列则由B单独生成。
该模型λ可采用三元素符号来表示：
\lambda = (A, B, \pi) \quad (1.5)
\pi、B、A称为隐马尔可夫模型的三要素.
隐马尔科夫模型的两个基本假设：
齐次马尔可夫性假设即基于隐藏的马尔可夫链在任意时刻t的状态受限于其前一时刻的状态，并不受其他时间点状态及观测的影响也与当前时刻t无关.
在马尔可夫链模型中
隐马尔可夫模型可以用于标注，这是2状态对应着标记.
隐马尔可夫模型的三个基本问题
概率计算问题.
基于模型\lambda=(A,B,\pi)以及观测序列O=\{o_1,o_2,\dots,o_T\}的概率分布研究中，我们关注的是观测序列O在模型\lambda下的发生概率P(O|\lambda)。
学习问题
给定观测序列O=\{o_1,o_2,\dots,o_t\}, 我们需要对模型\lambda=(A,B,\pi)进行参数估计, 以使该模型能够最大化地解释观测序列的概率P(O|\lambda), 即我们采用极大似然估计方法来求解这些参数.
预测问题，也称为解码问题.
假设给定一个隐马尔可夫模型\lambda=(A,B,\pi)以及一个观测序列O=\{o_1, o_2, \dots, o_t\}。寻求在给定观测序下的最大后验状态子序列I=(i_1,i_2,\dots,i_T)使得对应的条件几率P(I|O)达到最大值。亦即，在已知观测数据的情况下寻求最可能的状态轨迹。
概率计算算法
直接计算法
基于模型参数(A,B,\pi)以及观测序列为O=(o_1, o_2, \dots, o_t)的一组观察数据，估计其发生的概率P(O|\lambda).最直观的方式是通过概率公式直接求解.具体而言，在马尔可夫链框架下遍历所有可能的状态转移路径I=(i_1,i_2,\dots i_T) ，并分别计算每条路径及其对应观察数据的条件概率值p(o|I;\lambda) p(I;\lambda).随后将这些条件概率按照各条路径的可能性加权相乘后累加起来得到总的概率值
状态序列I=(i_1,i_2,\dots i_T)的概率是
P(I|\lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}\cdots a_{i_{T-1}i_T} \tag{2.1}
对于固定的长度为T的状态序列I=(i₁,i₂,…,i_T)及其相应的观测序列O=\{o₁,o₂,…,o_T\}的概率为P(O|I,λ)，
P(O|I,λ)=b_{i₁}(o₁)b_{i₂}(o₂)\cdots b_{i_T}(o_T) \tag{2.2}
O和I同时发生所对应的联合概率等于
\begin{aligned} P(O,I;\lambda)&=\sum_I P(O|I;\lambda)P(I;\lambda)\\ &=\sum_{t=1}^{T}\prod^t p(i_t|x_t)\prod^{t-1}_{s=1}\prod^K Q(z_s|i_s,x_s)} \end{aligned}
但是利用公式(2.3)计算量很大，是O(TN^T)阶的，这种算法不可行.
前向算法
定义 (前向概率)
给定一个隐马尔科夫模型λ，在时刻t的部分观测序列为o₁,o₂,…,o_t且状态为q_i的情况下，其概率称为前向概率，并用符号α_t(i)表示
α_t(i) = P(o₁,o₂,…,o_t,i_t=q_i|\lambda) \tag{2.4}
具体步骤
输入信息 ：隐马尔科夫模型\lambda描述了状态转移和发射概率的参数集；观测序列O为长度为T的符号序列. 输出结果 ：通过递推计算得到观测序列的概率值P(O|\lambda).
具体步骤
输入信息 ：隐马尔科夫模型\lambda = (A,B,\pi)包含状态转移概率矩阵A、发射概率矩阵B以及初始状态概率向量π；观测序列为O = o₁,o₂,…,o_T. 计算结果 ：通过动态规划方法依次计算各时刻的状态概率α_t(i)及其相关的观测序列联合概率P(O|λ).
（1）初值\alpha_1(i) = \pi_ib_i(o_1), i=1,2,\cdots,N
（2）递推
针对每一个t=1,2,\dots,T-1，
\begin{aligned} \alpha_{t+1}(i) \text{的值被定义为}\Big[\sum_{j=1}^N \alpha_t(j)a_{ji}\Big]b_i(o_{t+1})\text{的结果}\tag{2.5} \end{aligned}
（3）终止
P(O|\lambda) = \sum_{i=1}^N \alpha_T(i) \tag{2.6}
\alpha_t(j)代表观测序列在时间点t\时的状态为q_j\的概率。因此，在时间点t\时将当前状态为q_j\并下一状态为q_i的可能性表示为\alpha_t(j)a_{ji}这一乘积，则表示从所有可能的时间点j\转换到i\的同时观察到一连串的数据o_1, o_2, \cdots, o_t$的可能性。将这些可能性相加即得到从初始状态经过一系列转移，在时间点t+1\$达到状态i$的同时观察到全部数据o_1, o_2, \cdots, o_t, o_{t+1}\的可能性。因此，在时间点t+1$时的状态i\$的概率可以通过将方括号内的值与b_i(o_{t+1})$相乘来计算。
前向算法本质上是基于对状态序列路径结构进行递推运算的方法。其核心优势在于通过局部状态的概率估计并结合路径结构逐步推导至全局状态以获得观测序列的整体概率值P(O|\lambda)。为了降低重复计算量，在每一步迭代中只需要关注当前状态与其可能转移的状态之间的关系即可完成更新过程。这使得其总运算复杂度显著低于直接方法。
后向算法
下面阐述的是关于隐马尔科夫模型λ中后向概率的定义：基于给定的隐马尔科夫模型λ，在状态qt=qi的情况下（其中i=1,2,…N），后续从t+1到T的所有观测数据序列的概率密度函数定义为：
\beta_t(i) = P(o_{t+1},o_{t+2},\cdots,o_T|q_t=q_i,\lambda) \tag{3.1}
可以用递推的方法求得后向概率\beta_t(i)及观测序列概率P(O|\lambda).
算法
输入 ：隐马尔可夫模型\lambda，观测序列O.
输出 ：观测序列P(O|\lambda).
（1）
\begin{aligned} \beta_T(i)=1, i=1,2,\cdots,N\tag{3.2} \end{aligned}
（2）对t=T-1,T-2,\cdots,1，
\beta_t(i) = \sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j), i=1,2,\cdots,N\tag{3.3}
（3）
P(O|\lambda) = \sum_{i=1}^N \pi_i b_j(o_1)\beta_1(i) \tag{3.4}
基于前向概率与后向概率的定义，观测序列的概率P(O|\lambda)能够表达为以下形式：
P(O|\lambda) = \sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\quad t=1,2,\dots,T-1 \tag{3.5}
当t=1和t=T-1时分别为式(2.6)和(3.5).
学习算法
监督学习方法
假设我们拥有训练数据集S个长度相同的观测序列与对应的状态序列集合\{(O_1, I_1), (O_2, I_2), \dots, (O_S, I_S)\}；基于此我们可以运用最大似然估计的方法来推断隐马尔可夫模型的具体参数；具体步骤如下
转移概率\hat{a}_{ij}的估计
设样本在时刻t处于状态i且在下一个时刻t+1转移到状态j的频数为n_{t(i,j)}^{(t)} = A_{ij}, 则其相应的转移概率\hat{a}_{ij}即为：
\hat{a}_{ij} = \frac{n_{t(i,j)}^{(t)}}{\sum_{j=1}^N n_{t(i,j)}^{(t)}},\quad i=1,2,\dots,N \tag{4.1}
- 观测概率\hat{b}_j(k)的估计
在样本中，当状态为j且观测结果为k时（即状态j被观测到结果k的情况），频数统计得到的状态j对应观测k的频率计数值为B_{jk}。根据该频数数据，则可得出状态j观测k的概率估计\hat{b}_j(k)为：
\hat{b}_j(k) = \frac{B_{jk}}{\sum_{k=1}^M B_{jk}}, \quad j=1,2,\cdots,N;\,k=1,2,\cdots,M \tag{4.2}
- 初始状态概率\pi_i的估计\hat{\pi}_i为S个样本中初始状态为q_i的频率.
Baum-Welch算法(非监督)
基于训练数据仅包含了S个长度为T的观测序列{O_1,O_2,\cdots,O_S}而无相应的状态序列的情况下，我们的目标是估计该隐马尔科夫模型\lambda=(A,B,\pi)的相关参数。我们将这些状态序列视为不可观测的隐变量，并由此可知该类概率模型本质上就是一个含有不可观测性状的概率系统。
参数学习可以由EM算法实现.
确定完全数据的对数似然函数.
\log P(O,I|\lambda)
EM算法的E步：求Q函数Q(\lambda,\bar{\lambda})
\begin{aligned} Q(\lambda.\bar{\lambda}) &= \sum_I \log P(O,I|\lambda)P(I|O,\hat{\lambda}) \end{aligned}
P(O|\bar{\lambda})是对于固定的模型参数来说，是一个常量，因此我们乘上它，以方便后面计算.
\begin{aligned} Q(\lambda.\bar{\lambda}) &= \sum_I \log P(O,I|\lambda)P(I|O,\hat{\lambda})\\ & = \sum_I \log P(O,I|\lambda)P(I|O,\hat{\lambda})P(O|\bar{\lambda})\\ & = \sum_I \log P(O,I|\lambda)P(O,I|\hat{\lambda}) \tag{4.4} \end{aligned}
其中，\bar{\lambda}是隐马尔可夫模型参数的当前估计值，\lambda是要极大化的隐马尔可夫模型参数.
P(O,I|\lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T)
于是，Q函数可以写成:
\begin{aligned} Q(\lambda.\bar{\lambda}) &= \sum_I \log \pi_{i_1}P(O,I|\bar{\lambda}) + \sum_I\Big(\sum_{t=1}^{T-1}\log a_{i_t,i_{t+1}}\Big)P(O,I|\bar{\lambda})+\sum_I\Big(\sum_{t=1}^T\log b_{i_t}(o_t)\Big)P(O,I|\bar{\lambda}) \tag{4.5} \end{aligned}
EM算法的M步：最大化Q函数Q(λ,̄λ)，用于估计模型的参数包括A、B以及λ。
因为(4.5)式中的参数以单独的形式分别出现在三个项中，因此，在最大化过程中仅需对每个项分别进行处理。
（1） 第一项可以写成
\sum_I \log \pi_{i_1}P(O,I|\bar{\lambda}) = \sum_{i=1}^N \log \pi_iP(O,i_1=i|\bar{\lambda})
注意到\sum_{i=1}^N\pi_i = 1，利用拉格朗日乘子法，写出拉格朗日函数：
\sum_{i=1}^N \log \pi_iP(O,i_1=i|\bar{\lambda}) + \gamma\Big(\sum_{i=1}^N\pi_i-1\Big)
对其求偏导数并令结果为零
\frac{\partial}{\partial \pi_i}\Big[\sum_{i=1}^N\log \pi_i P(O,i_1=i|\bar{\lambda})+ \gamma\Big(\sum_{i=1}^N\pi_i-1\Big)\Big] = 0 \tag{4.6}
得P(O,i_1=i|\bar{\lambda}) + \gamma\pi_i=0
对i进行累加运算得到\gamma = - P(O|\bar{\lambda})，并将其结果代入式（4.6）后可得以下表达式：其中分子为条件概率P(O,i_1=i|\bar{\lambda})而分母则为归一化因子P(O|\bar{\lambda})
（2）这一部分可以表示为
\sum_I\left(\sum_{t=2}^{T}\ln a(i_t,i)\right)P(O,I|\lambda) = \sum_i^n\sum_j^n\left[\ln a(i,j)\right]P(O,i_t=i,t+1=j|\lambda)
在满足约束条件\forall i,\,\sum_j^n a(i,j)= 的前提下，则可以通过拉格朗日乘子法求解得到：
a(i,j) = \frac{\displaystyle\sum_t P(O, i_t=i, t+ 1=j|\lambda)}{\displaystyle\sum_t P(O, i_t=i|\lambda)} \quad (4.8)
（3）第三项的表达式为
\sum_I\Big(\sum_{t=1}^T\log b_{i_t}(o_t)\Big)P(O,I|\bar{\lambda}) = \sum_{j=1}^N\sum_{t=1}^T\log b_j(o_t) P(O,i_t=j|\bar{\lambda})
满足约束条件：
\sum_{k=1}^M b_j(k) = 1
采用拉格朗日乘数法求解，在以下条件下偏导数不为零：仅当 o_t=v_k 时， b_j(o_t) 对 b_j(k) 的偏导数才不等于零。通过上述推导可得：
b_j(k) = \frac{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda})I(o_t=v_k)}{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda})}
其中I(o_t=v_k)表示指示函数
由(4.7)(4.8)(4.9)三个参数公式逐次进行递推，最终得到模型参数\lambda^{(n+1)} = (B^(n+1),b^{(n+1)}, C^{(n+1)})
上述三项的最大值都是基于概率之和等于1的限制条件. 通过拉格朗日乘子法求解参数值.
预测算法
- 近似算法
根据每个时刻t的观测结果，在该时刻最可能发生的隐马尔科夫模型状态下选择对应的状态i_t^*。
通过这种方法得到的状态序列I^*=(i_1^*,i_2^*,\cdots,i_T^*)被用作预测结果。
基于隐马尔科夫模型以及观测序列，在时刻t处于状态q_i的概率\gamma_t(i)是
\gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)} = \frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_j(t)} \tag{5.1}
对于每一个时间点t所对应的最可能的状态i_t^*等于
从而得到状态序列I^*=(i_1^*,i_2^*,\dotsi_T^*).
近似算法的优势在于其运算过程较为简便。
然而存在一个缺陷：预测的状态序列未必全局最优。
这一缺陷源于预测过程中可能出现未被实际观察到的状态转移。
- 维特比算法
其核心在于通过动态规划来解决隐马尔科夫模型的预测问题，并基于动态规划方法寻找具有最高概率的状态转移序列。每个路径对应着一组完整的状态序列。
当最优路径在时间t经过节点i_t^*时，在该节点至终点之间的部分路径必须被视为当前所求解的最佳路线
过程：起始时刻t=1时启动递推算法，在每个时间步t的状态i处评估所有可能路径的最大累积概率值。最终达到终止时刻t=T时所获得的最大累积概率即为最优路径的概率值P*. 为了确定最优路径的关键节点位置, 采用逆向推导的方法, 通过逐步反向追踪每个关键节点的位置信息, 最终获得完整表达的最优路径序列I^*
定义在时刻t状态为i的所有单个路径(i_1,i_2,\dots,i_t)中概率最大值为：
\delta_t(i) = \max_{i_1,i_2,\dots,i_{t-1}}P(i_t=i, i_{t-1},\dots,i_1,o_t,\dots,o_1|\lambda),\ i=1,2,\dots,N
由定义可得变量\Delta的递推公式：
\begin{aligned} \delta_{t+1}(i) &= \max_{i_1,i_2,\dots,i_{t-1}}P(i_{t+1}=i, i_t,\dots,i_1,o_{t+1},\dots,o_1|\lambda)\\ & = \max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1}),\ i=1,2,\dots,N;t=1,2,\dots,T-1 \end{aligned}
定义在时刻t状态为i的所有单个路径(i_1,i_2,\dotsi_{t-1},i)中概率最大的路径的第t-1个结点为
\psi_t(i) = arg \max_{1\le j\leq N}[\delta_{t-1}(j)a_{ji}],\ i=1,2,\dots,N
维特比算法
输入 ：模型\lambda=(A,B,\pi)和观测序列O=(o_1,o_2,\dots,o_T)
输出 ：最优路径I^*=(i_1^*，i_2^*,\dots,i_T^*)
（1）初始化
\delta_1(i) = \pi_ib_i(o_1),\ i=1,2,\dots, N\\ \psi_1(i) = 0 ,\ i=1,2,\dots,N
（2）递推关系中，在t=2,3,\dots,T时，
\delta_t(i)的值由以下等式确定：
\delta_t(i)=\max_{1\leq j\leq N}\left[\delta_{t-1}(j)\cdot a_{ji}\right]\cdot b_i(o_t)，其中i=1,2,\dots,N
同时，
\psi_1(i)= \arg\max_{1\leq j\leq N}\left[\delta_{t-1}(j)\cdot a_{ji}\right] ，其中i=1,2,\dots,N
（3）终止
P^* = \max_{1\leq i \leq N}\delta_T(i)\\ i_T^* = arg \max_{1\leq i \leq N}[\delta_T(i)]
（4）最优路径回溯
对t=T-1,T-2,\dots,1
i_t^* = \psi_{t+1}(i_{t+1}^*)
求得最优路径I^*。