马尔科夫链

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

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

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

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

先看个假设,他每个状态的转移都是有概率的:
image.png

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

有了这个矩阵,再加上已知的第一天的梦想分布,就可以计算出第N天的梦想分布了。
image.png
S_1是4月1号中午12点的的梦想分布矩阵[0.6, 0.2, 0.2],里面的数字分别代表发财的概率,娶媳妇的概率,当官的概率。那么:

  • 4月2号的梦想分布矩阵S_2 = S_1 \times A (俩矩阵相乘)。
  • 4月3号的梦想分布矩阵S_3 = S_2 \times A (看见没,跟S_1无关,只跟S_2有关)。
  • 4月4号的梦想分布矩阵S_4 = S_3 \times A (看见没,跟S_1,S_2无关,只跟S_3有关)。
  • 4月n号的梦想分布矩阵S_n = S_{n-1} \times P (看见没,只跟它前面一个梦想S_{n-1}有关)。

隐马尔科夫模型

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

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

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

  • 4月2号的行为分布矩阵O_1= S_1 \times B
  • 4月3号的行为分布矩阵O_3 = S_2 \times B
  • 4月4号的行为分布矩阵O_4 = S_3 \times B
  • 4月n号的行为分布矩阵O_n = S_{n-1} \times B

image.png

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

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

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

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

令一个例子是中文的分词也用到了隐马尔可夫模型,我在另一篇文章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.png
篱笆网络中每个节点的概率可以根据模型计算出来,现在的问题是如何找出概率最大的那条路径,显然不能用贪心算法,而枚举所有路径复杂度太高,这个问题可以用动态规划算法来解决.

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

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

  • 计算到第2层的所有最优路径
  • 在前面的基础上,计算到第3层的所有最优路径
  • 在前面的基础上,计算到第4层的所有最优路径
  • 在前面的基础上,计算出到第n层的所有最优路径

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

  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
评论加载中...

发表评论