隐马尔可夫模型

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

隐马尔可夫模型是可用于标注问题的统计学习模型,描述有隐藏的马尔科夫链随机生成观测序列的过程,属于生成模型。本文将学习隐马尔可夫模型,着重介绍掌握HMM的模型、应用、及理论推导过程。

来源:李航的《统计学习方法》

基本概念

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

背景

机器学习中的步骤优化:

  1. 确定模型
  2. 确定策略 即准则(损失函数)
  3. 算法:GN

概率图模型

概率图模型( probabilistic graphical model)是一类用图来表达变量相关关系的概率模型。它以图为表示工具,最常见的是用一个结点表示一个或一组随机变量,结点之间的边表示变量间的概率相关关系,即“变量关系图”.根据边的性质不同,概率图模型可大致分为两类:

第一类是使用有向无环图表示变量间的依赖关系,称为有向图模型或贝叶斯网( Bayesian network);

第二类是使用无向图表示变量间的相关关系,称为无向图模型或马尔可夫网( Markov network);

概率图模型可以分为有向图(贝叶斯网络)、无向图(马尔可夫随机场);

概率图模型+时间序列=动态模型;

动态模型主要有:HMM、卡尔曼滤波器、粒子滤波器;

  1. HMM:系统状态离散
  2. Kalman滤波器:系统状态连续且线性分布
  3. Particle滤波器:系统状态连续且非线性分布

HMM定义

​ 隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。形式定义如下:

设Q是所有可能的状态集合,V是所有可能的观测的集合。
$$
Q = {q_1,q_2,…,q_N},V={v_1,v_2,…v_M}
$$
其中,N是可能的状态数,M是可能的观测数。

I是长度为T的状态序列,O是对应的观测序列
$$
I={i_1,i_2,…,i_N},O={v_1,v_2,…,v_M}
$$
A是状态转移概率矩阵:
$$
A=[a_ij]{N\times N}
$$
其中,
$$
a
{ij}=P(i_{t+1}=i_t|q_j),i=1,2,..N;j=1,2,…,N
$$
表示在时刻t处于状态$q_i$的条件下在时刻t+1转移到状态$q_j$的概率。

B是观测概率矩阵:
$$
B=[b_j(k)]_{N\times M}
$$
其中,
$$
b_j(k)=P(o_t=v_k|i_t=q_j),i=1,2,…N;j=1,2,…,N
$$
是在时刻t处于状态$q_j$的条件下生成观测$v_k$的概率。

$\pi$是初始状态概率向量:
$$
\pi=(\pi_i)
$$
其中,
$$
\pi=P(i_1=q_i),i=1,2,…N
$$
是时刻t=1处于状态$t=1$处于状态$q_i$的概率。

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

​ 状态转移概率矩阵A与初始状态概率向量π确定了隐藏的马尔可夫链,生成不可观测的状态序列。观测概率矩阵B确定了如何从状态生成观测,与状态序列综合确定了如何产生观测序列

两个基本假设

  1. 齐次马尔可夫性假设,即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一其前一时刻的状态,于其它时刻的状态及观测无关,也与时刻t无关。
    $$
    P(i_t|i_t-1,o_{t-1},…,i_1,o_1)=P(i_t|i_t-1),t=1,2,…,T
    $$

  2. 观测独立性假设,即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关。
    $$
    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)
    $$

观测序列的生成过程

根据HMM模型定义,可以将一个长度为T的观测序列$O=(o_1,o_2,…o_T)$的生成过程描述如下:

算法:观测序列的生成

输入:隐马尔可夫模型$\lambda=(A,B,\pi)$,观测序列长度;

输出:观测序列$O=(o_1,o_2,…,o_T)$

  1. 按照初始状态分布$\pi$产生状态$i_1$
  2. 令t=1
  3. 按照状态$i_t$的观测概率分布$b_{i_t(k)}$生成$o_t$
  4. 按照状态$i_t$的状态转移概率分布${a_{i_ti_{t+1}}}$产生状态$i_{t+1},i_{t+2}=1,2,…N$
  5. 令t=t+1,如果t<T,转步(3),否则,终止

算法推导

隐马尔可夫模型有三个基本问题

  1. 概率计算问题。给的模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$,计算在模型$\lambda$下观测序列O出现的概率$P(O|\lambda)$。
  2. 学习问题。阈值观测序列$O=(o_1,o_2,…,o_T)$,估计模型参数$\lambda=(A,B,\pi)$参数,使得在该模型下观测序列序列概率$P(O|\lambda)$最大,即用极大似然估计的方法估计参数
  3. 预测问题,(解码(decoding)问题)。一致模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$,求对给定观测序列条件概率$P(I|O)$最大的状态序列$I=(i_1,i_2,…,i_T)$,即给定观测序列,求最有可能的对应的状态序列。

本节将介绍HMM模型的概率计算算法、学习算法以及预测算法

概率计算算法

目的:给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$,计算在模型$\lambda$下观测序列O出现的概率$P(O|\lambda)$。

直接计算法

最直接的方法是按照概率公式直接计算。通过列举所有可能的长度为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_1i_2}a_{i_2i_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)$,
$$
P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)…b_{i_T}(o_T)
$$
O和I同时出现的概率为:
$$
P(O,I|\lambda)=P(O|I,\lambda)P(I,\lambda)=\pi_{i_i}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)…a_{i_{T-1}i_T}b(o_T)
$$
对所有可能的状态序列I球壳,得到观测序列O的概率$P(P|\lambda)$,即
$$
P(O|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)=\sum_{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)
$$
这种方法很容易理解,但是计算量很大,是$O(TN^T)$阶的。不可行

前向算法(forward-backward algorithm)

前向概率 给定隐马尔可夫模型$\lambda$,定义时刻t部分观测序列为$O=(o_1,o_2,…,o_T)$且状态为$q_i$的概率为前向概率,记作
$$
\alpha_t(i)=P(o_1,o_2,…,o_t,i_t=q_i|\lambda)
$$
观测序列概率的前向算法

输入:隐马尔可夫模型$\lambda$,观测序列O;

输出:观测序列概率$P(O|\lambda)$

  1. 初值
    $$
    \alpha_1(i)=\pi_ib_i(o_1),i=1,2,…N
    $$

  2. 递推 对 $t=1,2,..,T-1$
    $$
    \alpha_{t+1}(i)=[\sum^N_{j=1}\alpha_t(j)a_{ji}]b_t(o_{t+1}),i=1,2,…N
    $$

  3. 终止
    $$
    P(O|\lambda)=\sum^N_{j=1}\alpha_T(i)
    $$

算法解读,步骤(1)初始化前向概率是初始时刻状态和观测的联合概率,步骤(2)是前向概率的递推公式,计算到时刻t+1部分观测序列在时刻t+1且初始状态$q_i$的的前向概率。

所以:
$$
P(O|\lambda)=\sum^N_{j=1}\alpha_T(i)
$$
下图表示了前向概率的递推公式:

递推公式

后向算法

后向概率:给定隐马尔可夫模型$\lambda$ ,定义在时刻t状态为$q_i$的条件下,从t+1到T的部分观测序列为$o_{t+1},o_{t+2},…o_T$的概率为后向概率,记作:
$$
\beta_t(i)=P(o_{t+1},o_{t+2},…,o_T|i_t=q_i,\lambda)
$$
可以也递推的方法求得后向概率$\beta_t(i)$及观测序列概率$P(O|\lambda)$.

算法步骤

输入:隐马尔可夫模型$\lambda$,观测序列O;

输出:观测序列$P(O|\lambda)$;

  1. $\beta_T(i)=1,i=1,2,…N$

  2. 对$t=T-1,T-2,…1$
    $$
    \beta_t(i)=\sum^N_{j=1}a_{ij}b_j(a_{t+1})\beta_{t+1}(j),i=1,2,…,N
    $$

算法(1)初始化后向概率,对最终时刻的所有状态$q_i$规定$\beta_T(i)=1$ ;步骤(2)是后向概率的递推公式。

后向概率的递推公式

学习算法

监督学习方法

Baum-welch算法

预测算法(Decoding算法)

近似算法

维特比算法

应用

隐马尔可夫模型在语音识别、自然语言处理、生物信息、模式识别等领域有着广泛的应用。

HMM的主要应用是解码

两种解码方法:

  1. Viterbi算法解码
  2. 前向后向算法+贝叶斯后验概率

语音识别

自然语言处理

词性标注

词性是隐藏状态,词出现时观察序列。

首先我们要知道模型的参数,如果又标注数据,直接用比例代替概率,如果没有用前向后向算法求除

知道模型参数吧,使用Viterbi算法来计算某个标注序列(隐含状态)的概率

实际建模过程

  • 根据实际问题确定状态个数及观察序列
  • 用若干已知序列,采用B-W算法估计参数(转移概率和输出概率的值)
  • 输入位置序列用Viterbi算法或者贝叶斯概率解码
  • © 2019-2022 guoben
  • PV: UV:

微信