nlp基础—7.隐马尔可夫模型(HMM算法)

引言

HMM算法的知识体系如下：

可以总结为两个基本假设，两个集合(序列)，三个参数，三个基本问题。

一、隐马尔可夫模型的定义

隐马尔科夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不
可观测的随机状态序列，再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态序列，称为状态序列(state sequence);每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列(observationsequence)。序列的每一个位置又可以看做是一个时刻。

1. 两个集合(序列)

设Q是所有可能的状态的集合，V是所有可能的观测集合；状态集合、观测集合定义如下：
$$Q=\{q_1,q_2,...,q_N\}$$
$$V=\{v_1,v_2,...,v_N\}$$

设I是长度为T的状态序列，O是长度为T的观测序列：
$$I=(i_1,i_2,...,i_T)$$
$$O=(o_1,o_2,...,o_T)$$

2. 两个基本假设

• 齐次马尔科夫性假设
  假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关
  $$\begin{gathered} P(i_t|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t|i_{t-1}), \\ t=1,2,...,T \end{gathered}$$
• 观测独立性假设
  假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关
  $$P(o_t|i_T,o_T,i_{T-1},o_{T-1},...,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},i_1,o_1)=P(o_t|i_t)$$

3. 三个参数

隐马尔科夫模型由初始状态概率向量$\pi$、状态转移概率矩阵$A$以及观测概率矩阵$B$决定。$\pi$和$A$决定状态序列，$B$决定观测序列。因此，隐马尔可夫模型$\lambda$可以用三元符号
$$\lambda =(A,B,\pi )$$表示。

• $A$是状态转移概率矩阵
  $$A=[a_{ij}{]}_{N\times N}$$
  其中，
  $$\begin{gathered} a_{ij}=P(i_{t+1}=q_j|i_t=q_i) \\ i=1,2,...,N \\ j=1,2,...,N \end{gathered}$$
  $a_{ij}$是在时刻$t$处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率。
  
• $B$是观测概率矩阵
  $$B=[b_j(k){]}_{N\times M}$$
  其中，
  $$\begin{gathered} b_j(k)=P(o_t=v_k|i_t=q_j) \\ k=1,2,...,M \\ j=1,2,...,N \end{gathered}$$
  $b_j(k)$是在时刻$t$处于状态$q_j$的条件下生成观测$v_k$的概率。
  
• $\pi$是初始状态概率向量
  $$\pi =({\pi }_i)$$
  其中，
  $$\begin{gathered} {\pi }_i=P(i_1=q_i) \\ i=1,2,...,N \end{gathered}$$
  ${\pi }_i$是时刻$t=1$处于状态$q_i$的概率。
  

初始状态概率向量$\pi$、状态转移概率矩阵$A$确定了隐藏的马尔科夫链，生成不可观测的状态序列。观测概率矩阵$B$确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。隐马尔科夫模型可以用于标注，这时状态对应着标记，标注问题是给定观测的序列预测其对应的标记序列。可以假设标注问题的数据是由隐马尔科夫模型生成的。这样我们可以利用隐马尔可夫模型的学习与预测算法进行标注。

二、隐马尔科夫模型的三个基本问题

1. 概率计算问题

已知信息:模型$\lambda =[A,B,\pi ]$,观测序列$O=(o_1,o_2,...,o_T)$;
求解目标:计算在给定模型$\lambda$下，已知观测序列$О$出现的概率:$P(O|\lambda )$。也就是说，给定观测序列，求它和评估模型之间的匹配度。

1.1 直接计算法

直接计算法是按概率公式直接计算。通过列举所有可能的长度为$T$的状态序列$I=(i_1,i_2,...,i_t)$，求各个状态序列$I$与观测序列$O=(o_1,o_2,...,o_T)$的联合概率$P(O,I|\lambda )$,然后对所有可能的状态序列求和，得到$P(O|\lambda )$。
状态序列$I=(i_1,i_2,...,i_t)$的概率是：
$$P(I|\lambda )={\pi }_{i_1}{a}_{i_1{i}_2}{a}_{i_2{i}_3}...a_{i_{T-1}{i}_T}$$
对固定的状态序列$I=(i_1,i_2,...,i_t)$,观测序列$O=(o_1,o_2,...,o_T)$的概率是
$$P(O|I,\lambda )=b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)$$
对联合概率求和，得到观测序列$O$的概率$P(O|\lambda )$,即
$$\begin{gathered} P(O|\lambda )=\sum _{I}P(O|I,\lambda )P(I|\lambda ) \\ =\sum _{i_1,i_2,...,i_t}{\pi }_{i_1}{b}_{i_1}(o_1)a_{i_1{i}_2}{b}_{i_2}(o_2)...a_{i_{T-1}{i}_T}{b}_{i_T}(o_T) \end{gathered}$$
直接计算法的计算量非常大，是$O(T{N}^T)$阶的，时间复杂度过高，这种算法不可行。

1.2 前向算法

定义前向概率：给定隐马尔可夫模型$\lambda$，定义到时刻$t$部分观测序列为$o_1,o_2,...,o_t,$且状态为$q_i$的概率为前向概率，记做:
$${\alpha }_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda )$$可以递推地求得前向概率${\alpha }_t(i)$及观测序列概率$P(O|\lambda )$。

观测序列概率的前向算法如下：
输入:隐马尔可夫模型$\lambda$，观测序列$O$;
输出:观测序列概率$P(O|\lambda )$

• 步骤1是初始化前向概率，是初始时刻的状态$i_1=q_i$,和观测$o_1$的联合概率。
• 计算到时刻$t+1$部分观测序列为$o_1,o_2,...,o_{t-1},$且在时刻$t+1$处于状态$q_i$的前向概率。

前向算法相比于直接计算法来说，大大减小了计算量。减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果，避免重复计算。利用前向概率计算$P(O|\lambda )$的计算量是$O(N^{2}T)$阶的。

1.3 后向算法

• 步骤1初始化后向概率，对最终时刻的所有状态$q_i$规定${\beta }_T(i)=1$
• 步骤2：为了计算在时刻$t$状态为$q_i$条件下时刻$t+1$之后的观测序列为$o_{t+1},o_{t+2},...,o_T$的后向概率${\beta }_t(i)$，只需考虑在时刻t+1所有可能的$N$个状态$q_j$的转移概率，以及在此状态下的观测$o_{t+1}$的观测概率，然后考虑状态$q_j$之后的观测序列的后向概率即${\beta }_{T+1}(j)$
  

2. HMM的学习问题

已知信息:观测序列$O=(o_1,o_2,...,o_T)$，
或许也会给定与之对应的状态序列: $S=(s_1,s_2,...,s_T)$
求解目标︰估计模型$\lambda =[A,B,\pi ]$参数，使得该模型下观测序列概率$P(O|\lambda )$最大。也就是训练模型，使其最好地描述观测数据。
隐马尔科夫模型的学习，根据训练数据是包括观测序列和对应的状态序列还是只有观测序列，可以分为由监督学习与无监督学习实现。

2.1 监督学习算法

假设已给训练数据包含$S$个长度相同的观测序列和对应的状态序列$(O_1,I_1),(O_2,I_2),...,(O_S,I_S)$


用的最多的还是监督学习的方法。

2.2 非监督学习算法—Baum-Welch算法

假设给定训练数据只包含$S$个长度为$T$的观测序列$O_1,O_2,...,O_s$而没有对应的状态序列，目标是学习隐马尔科夫模型$\lambda =(A,B,\pi )$的参数。隐马尔科夫模型是一个含有隐变量的概率模型，
$$P(O|\lambda )=\sum _{I}P(O|I,\lambda )P(I|\lambda )$$它的参数学习完全可以由EM算法实现。
Baum-Welch算法如下：

3. HMM的预测问题

已知信息:模型$\lambda =[A,B,\pi ]$，观测序列$O=(o_1,o_2,...,o_T)$
求解目标:计算在给定模型$\lambda$下，使已知观测序列$О$的条件概率$P(O|S)$最大的状态序列$S=(s_1,s_2...,s_T)$。即给定观测序列，求最有可能与之对应的状态序列。
这个算法是在分词过程中实际使用的算法。

3.1 近似算法

近似算法的想法是：在每个时刻$t$选择在该时刻最有可能出现的状态$i_t^{\ast }$，从而得到一个状态序列$I^{\ast }=(i_1^{\ast },i_2^{\ast },...,i_T^{\ast })$，将它作为预测的结果。
给定隐马尔可夫模型$\lambda$和观测序列$O$，在时刻$t$处于状态$q_i$的概率为${\gamma }_t(i)$是

在每一个时刻$t$最有可能的状态$i_t^{\ast }$是
$$\begin{gathered} i_t^{\ast }=argma{x}_{1<=i<=N}[{\gamma }_t(i)] \\ t=1,2,...,T \end{gathered}$$从而得到状态序列$I^{\ast }=(i_1^{\ast },i_2^{\ast },...,i_T^{\ast })$。
近似算法的优点是计算简单，缺点是不能保证预测的状态序列整体上是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分。

3.2 维特比算法

维特比算法实际上是用动态规划解隐马尔科夫模型预测问题，即用动态规划求概率最大路径。这时一条路径对应着一个状态序列。依据这一原理，我们只需从时刻$t=1$开始,递推地计算在时刻$t$状态为$i$的各条部分路径的最大概率,直至得到时刻$t=T$状态为$i$的各条路径的最大概率。时刻$t=T$的最大概率即为最优路径的概率$P^{\ast }$,最优路径的终结点$i_T^{\ast }$也同时得到。之后，为了找出最优路径的各个结点，从终结点$i_T^{\ast }$开始，由后向前逐步求得结点$i_{T-1}^{\ast },...,i_1^{\ast }$，得到最优路径$I^{\ast }=(i_1^{\ast },i_2^{\ast },...,i_T^{\ast })$。

下面给出两个变量$\delta$和$\Psi$的定义：
定义在时刻$t$状态为$i$的所有单个路径$(i_1,i_2,..,i_t)$中概率的最大值为
$$\begin{gathered} {\delta }_t(i)=ma{x}_{i_1,i_2,..,i_{t-1}}P(i_t=i,i_{t-1},...,i_1,o_t,...,o_1|\lambda ) \\ i=1,2,..,N \end{gathered}$$

由定义可得$\delta$的递推公式：
$$\begin{gathered} {\delta }_{t+1}(i)=ma{x}_{i_1,i_2,..,i_t}P(i_{t+1}=i,i_t,i_{t-1},...,i_1,o_{t+1}{o}_t,...,o_1|\lambda ) \\ =ma{x}_{1<=j<=N}[{\delta }_t(j)a_{ji}]b_i(o_{t+1}) \\ t=1,2,...,T-1 \\ i=1,2,..,N \end{gathered}$$
定义在时刻$t$状态为$i$的所有单个路径$(i_1,i_2,..,i_{t-1},i)$中概率最大的路径的第$t-1$个节点为
$$\begin{gathered} {\Psi }_t(i)=argma{x}_{1<=j<=N}[{\delta }_{t-1}(j)a_{ji}], \\ i=1,2,...,N \end{gathered}$$用于存储路径。

下面介绍维特比算法

如果对您有帮助，麻烦点赞关注，这真的对我很重要！！！如果需要互关，请评论或者私信！