Created by potrace 1.13, written by Peter Selinger 2001-2015

隐马尔可夫模型

马尔科夫链

在理解隐马尔科夫模型之前,必须先要弄懂马尔科夫链这个概念,这里举个例子来说明.

我们村智商为0的王二狗，人傻不拉几的，见人就傻笑，当然,人家也是有梦想滴,分别是发财,娶媳妇,当官.

心中的梦想，仨状态发财,娶媳妇,当官。这就是传说中的梦想分布。

你想知道他n天后梦想是什么？想着发财,想着娶媳妇,还是想着当官？这些状态发生的概率分别都是多少？

先看个假设，他每个状态的转移都是有概率的:

image

这个矩阵就是转移概率矩阵P，并且它是保持不变的，就是说第一天到第二天的转移概率矩阵跟第二天到第三天的转移概率矩阵是一样的。

有了这个矩阵，再加上已知的第一天的梦想分布，就可以计算出第N天的梦想分布了。

image

S_1 是4月1号中午12点的的梦想分布矩阵 [0.6, 0.2, 0.2] ，里面的数字分别代表发财的概率，娶媳妇的概率，当官的概率。那么:

隐马尔科夫模型

根据他每天的梦想,王二狗做出了实际行动,他们之间也有一定的概率关系:

image

这个概率关系矩阵被称为观测矩阵B.

有了观测矩阵,就可以根据王二狗的行为来推测王二狗心中的梦想,假设王二狗这几天的行为分布为: O_1 , O_2 , O_3 ,..., O_n ,于是有:

image

由于我们只能观测到王二狗每天的行为,不能观测到他心中的梦想,所以称行为是观测状态,梦想是隐状态,隐马尔科夫模型就是在马尔科夫链的基础上加了个隐状态.

隐马尔可夫模型能解决现实生活中什么问题?

在现实生活中什么地方需要用到马尔科夫模型呢?语音识别是最典型的一个例子,事实上隐马尔可夫模型设计之初就是为了解决语音识别和自然语言处理的问题.

在语音识别中我们接受的是一段声音的波形,我们需要将它还原成文字.这里声音的波形就是观测量,声音背后对应的文字就是状态量.

令一个例子是中文的分词也用到了隐马尔可夫模型,我在另一篇文章jieba分词的原理中有介绍分词对隐马尔可夫模型的使用.分词时文字为观测量,对应的状态为BMES,分别代表词头,词中,词尾和单字词.

隐马尔可夫模型的定义

首先我们假设Q是所有可能的隐藏状态的集合，V是所有可能的观测状态的集合，即：

Q = \{q_1,q_2,...,q_N\}, \; V =\{v_1,v_2,...v_M\}

其中，N是可能的隐藏状态数，M是所有的可能的观察状态数。

对于一个长度为T的序列，I对应的状态序列, O是对应的观察序列，即：

I = \{i_1,i_2,...,i_T\}, \; O =\{o_1,o_2,...o_T\}

其中，任意一个隐藏状态 i_t \in Q ,任意一个观察状态 o_t \in V

A为状态转移矩阵:

A=\Big [a_{ij}\Big ]_{N \times N}

其中

a_{ij} = P(i_{t+1} = q_j | i_t= q_i)

B为观测概率矩阵(有的文章中称之为发射矩阵):

B = \Big [b_j(k) \Big ]_{N \times M}

其中

b_j(k) = P(o_t = v_k | i_t= q_j)

值的一提的是,如果观测变量为连续的，则发射概率可以是高斯或混合高斯模型，甚至是神经网络模型。

\pi 是初始状态概率:

\pi = \Big [ \pi_{i}\Big ]_N

其中

\pi_{i} = P(s_1 = q_i)

这样的话,马尔科夫模型可用一个三元组表示:

\lambda = (A, B, \pi)

隐马尔可夫模型做了两个假设:
(1) 齐次马尔科夫假设,即假设t时刻的状态仅依赖于前一刻的状态,与其他时刻的观察及状态无关:

P(i_t|i_1,o_1,i_2,o_2,i_3,o_3,...,i_{t-1},o_{t-1}) = P(i_t | i_{t-1})

(2) 观测独立假设,即假设任意时刻的观测只依赖于该时刻的状态,与其他观测及状态无关.

P(o_t|i_1,o_1,i_2,o_2,i_3,o_3,...,i_{t},o_{t}) = P(o_t | i_{t})

隐马尔科夫模型的3个基本问题

隐马尔科夫模型有3个基本问题:

  1. 概率计算问题.给定模型 \lambda = ( A , B , \pi ) 和观测序列 O = \left( o _ { 1 } ,o _ { 2 } , \cdots , o _ { T } \right) ,计算在模型 \lambda 下观测序列 O 出现的概率 P(O|\lambda) ,该概率会在下个问题使用极大似然估计的方法估计参数的时候被用到.
  2. 学习问题.已知观测序列 O = \left( o _ { 1 } ,o _ { 2 } , \cdots , o _ { T } \right) ,估计模型参数 \lambda = ( A , B , \pi ) ,使得在该模型下观测序列概率 P(O|\lambda) 最大,即使用极大似然估计的方法估计参数.
  3. 预测问题,也称解码问题.已知模型 \lambda = ( A , B , \pi ) 和观测序列 O = \left( o _ { 1 } ,o _ { 2 } , \cdots , o _ { T } \right) ,求对给定观测序列条件概率 P(I|O) 最大的状态序列 I = (i_1,i_2,...,i_T) .即给定观测序列求最优可能的对应状态序列.

如果我们没有标记数据,就要解决模型参数的学习问题.但是如果我们有大量的标记数据,也就是说我们知道数据观测序列对应的状态序列,这时完全可以通过统计现有数据的转移概率计算出模型参数 A , B , \pi .

前向算法与后向算法求观测序列概率

先来看一下直接计算求观测序列的概率是否可行.当我们已知HMM模型的参数 \lambda = (A, B, \Pi) ,要求观测序列O在模型 \lambda 下出现的条件概率 P(O|\lambda) 。
因为:

P ( I | \lambda ) = \pi _ { i _ { 1 } } a _ { i _ { 1 } i _ { 2 } } a _ { i _ { 2 } i _ { 3 } } \cdots a _ { i _ { r - 1 } i _ { T } }

P ( O | I , \lambda ) = b _ { i _ { 1 } } \left( o _ { 1 } \right) b _ { i _ { 2 } } \left( o _ { 2 } \right) \cdots b _ { i _ { T } } \left( o _ { T } \right)

所以有：

P(O,I|\lambda) = P(I|\lambda)P(O|I, \lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}\;\;i_T}b_{i_T}(o_T)

然后对所有可能的状态序列I求和可的 P(O|\lambda) ，即：

P(O|\lambda) = \sum\limits_{I}P(O,I|\lambda) = \sum\limits_{i_1,i_2,...i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}\;\;i_T}b_{i_T}(o_T)

假设状态有N种取值，状态序列长度为T，则状态序列的可能取值有 N^T 种可能。再加上里面的连乘长度与T的长度相关，所以此公式的复杂度为 O(TN^T) 。此法不可行。下面我们介绍前向算法与后向算法来解决此问题。

前向算法可以递推出观察序列概率：

  1. 初值

\alpha_1(i) = \pi_ib_i(o_1),\; i=1,2,...N

  1. 递推 对t=1,2,3,...T-1

\alpha_{t+1}(i) = \Big[\sum\limits_{j=1}^N\alpha_t(j)a_{ji}\Big]b_i(o_{t+1}),\; i=1,2,...N

  1. 因为 \alpha_T(i) = P(o_1,o_2,...o_T, i_T =q_i | \lambda) ,所以有

P(O|\lambda)= \sum\limits_{i=1}^N\alpha_T(i)

从递推公式可以看出，我们的算法时间复杂度是 O(TN^2) 。

我们可以这样来理解前向算法,把 \alpha 当成是一个矩阵,行从 1,2,...N 表示隐状态,所以 \alpha_1,\alpha_2,\alpha_3,... 就代表t=1,2,3,...时刻的所有隐状态,先来写出几个时序的 \alpha 看看:

\alpha_1 = \begin{bmatrix}\pi_1b_1(o_1)\\\pi_2b_2(o_1)\\\pi_3b_3(o_1)\\...\end{bmatrix}

\alpha_2 = \begin{bmatrix}\pi_1b_1(o_1)a_{11}b_1(o_2)\\\pi_2b_2(o_1)a_{12}b_2(o_2)\\\pi_3b_3(o_1)a_{13}b_3(o_2)\\...\end{bmatrix}

\alpha_3 = \begin{bmatrix}\pi_1b_1(o_1)a_{11}b_1(o_2)a_{21}b_1(o_3)\\\pi_2b_2(o_1)a_{12}b_2(o_2)a_{22}b_2(o_3)\\ \pi_3b_3(o_1)a_{13}b_3(o_2)a_{23}b_3(o_3)\\ ...\end{bmatrix}

定义中的累加相当于将每行的数据相加,递推会继续乘 a_{ji}b_i(o_t) ,可以想象最终结果与直接推导中的 P(O|\lambda) 相吻合.

后向算法与前向算法原理相同，只不过一个从前向后计算，而另一个从后向前计算。因为后面Baum-Welch算法中需要用到后向算法,所以这里列举一下算法流程：

  1. 初始化时刻T的各个隐藏状态后向概率：

\beta_T(i) = 1,\; i=1,2,...N

  1. 递推时刻T−1,T−2,...1时刻的后向概率：

\beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\; i=1,2,...N

  1. 计算最终结果：

P(O|\lambda) = \sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i)

后向算法时间复杂度是 O(TN^2) 。

Baum-Welch算法

Baum-Welch算法实际上就是使用EM算法求解隐马尔科夫模型的算法.

观测序列 O ,状态序列 I 为隐变量,学习隐马尔可夫模型 \lambda= (A,B,\pi) .

(1) E步：求Q函数:

Q (\lambda,\hat \lambda) = \sum_I P(I|O,\hat \lambda)\log P(O,I|\lambda)

由于:

P(I|O,\overline{\lambda}) = \frac{P(I,O|\overline{\lambda})}{P(O|\overline{\lambda})}

这里的 P(O|\overline{\lambda}) 相当于常数,所以Q函数可以写为

Q (\lambda,\hat \lambda) = \sum_I P(O,I|\hat \lambda)\log P(O,I|\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 (\lambda,\hat \lambda) =\sum_I \log\pi_{i_1}P(O,I|\hat\lambda)+\sum_I(\sum_{t=1}^{T-1} \log a_{i_ti_t{t+1}})P(O,I|\hat\lambda)+\sum_I(\sum_{t=1}^{T} \log b_{i_t}(o_t))P(O,I|\hat\lambda)

(2) M步：极大化Q函数 Q (\lambda,\hat \lambda) 求模型参数 A,B,\pi

使用拉格朗日求Q函数的极值可得：

\pi_i =\frac {P(O,i_1=i|\hat\lambda)}{P(O|\hat\lambda)}

a_{ij}=\frac {\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1} =j|\hat\lambda)}{\sum_{t=1}^{T-1}P(O,i_t=i|\hat\lambda)}

b_j(k) =\frac {\sum_{t=1}^T P(O,i_t =j|\hat\lambda)I(o_t =v_k)}{\sum_{t=1}^T P(O,i_t =j|\hat\lambda)}

Baum-Welch模型参数估计公式

1）给定模型 \lambda 和观测序列O,在时刻t处于状态 q_i 的概率记为:

\gamma_t(i) = P(i_t = q_i | O,\lambda) = \frac{P(i_t = q_i ,O|\lambda)}{P(O|\lambda)}

利用前向概率和后向概率的定义可知：

P(i_t = q_i ,O|\lambda) = \alpha_t(i)\beta_t(i)

于是我们得到：

\gamma_t(i) = \frac{ \alpha_t(i)\beta_t(i)}{\sum\limits_{j=1}^N \alpha_t(j)\beta_t(j)}

2）给定模型 \lambda 和观测序列O,在时刻t处于状态 q_i ，且时刻t+1处于状态 q_j 的概率记为:

\xi_t(i,j) = P(i_t = q_i, i_{t+1}=q_j | O,\lambda) = \frac{ P(i_t = q_i, i_{t+1}=q_j , O|\lambda)}{P(O|\lambda)}

而 P(i_t = q_i, i_{t+1}=q_j , O|\lambda) 可以由前向后向概率来表示为:

P(i_t = q_i, i_{t+1}=q_j , O|\lambda) = \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)

从而最终我们得到 \xi_t(i,j) 的表达式如下：

\xi_t(i,j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum\limits_{r=1}^N\sum\limits_{s=1}^N\alpha_t(r)a_{rs}b_s(o_{t+1})\beta_{t+1}(s)}

由以上公式可将Baum-Welch算法M步中的参数改写为：

\pi_i = \frac{\sum\limits_{d=1}^D\gamma_1^{(d)}(i)}{D}

a_{ij} = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\xi_t^{(d)}(i,j)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\gamma_t^{(d)}(i)}

b_{j}(k) = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1, o_t^{(d)}=v_k}^{T}\gamma_t^{(d)}(i)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}\gamma_t^{(d)}(i)}

维特比算法

维特比算法就是将动态规划的一个特例,用来解决上述篱笆网络最优路径问题.现在每个时刻有3种隐状态,我们每个时刻要取1种状态,有很多种取法:

image

篱笆网络中每个节点的概率可以根据模型计算出来,现在的问题是如何找出概率最大的那条路径,显然不能用贪心算法,而枚举所有路径复杂度太高,这个问题可以用动态规划算法来解决.

假设我们知道了最优路径,那么最优路径一定会经过第i层的节点,如果求出到第i层所有节点的最优路径,那么全局最优路径一定在这些局部最优路径中.

所以动态规划的求解过程:

隐马尔科夫模型的维特比算法如下:

  1. 初始化局部状态：

\delta_1(i) = \pi_ib_i(o_1),\;i=1,2...N

\Psi_1(i)=0,\;i=1,2...N

  1. 进行动态规划递推时刻 t=2,3,...T 时刻的局部状态：

\delta_{t}(i) = \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]b_i(o_{t}),\;i=1,2...N

\Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}],\;i=1,2...N

  1. 计算时刻T最大的 \delta_{T}(i) ,即为最可能隐藏状态序列出现的概率。计算时刻T最大的 \Psi_t(i) ,即为时刻T最可能的隐藏状态。

P* = \max_{1 \leq j \leq N}\delta_{T}(i)

i_T^* = arg \; \max_{1 \leq j \leq N}\;[\delta_{T}(i)]

  1. 利用局部状态 \Psi(i) 开始回溯。对于 t=T-1,T-2,...,1 ：

i_t^* = \Psi_{t+1}(i_{t+1}^*)

最终得到最有可能的隐藏状态序列 I^*= \{i_1^*,i_2^*,...i_T^*\}

参考:
李航《统计学习方法》

posted @ 2018-07-18 14:12:16
评论加载中...
发表评论