隐马尔科夫模型笔记

1.前言

隐马尔科夫模型有些不同,不论感知机、逻辑回归还是SVM,它们都是用数学公式来建模,但HMM却是采用了图的方式来建模,而且这个图很有想象力。它可以想象成在看似没有关系的现实世界背后,隐藏着一个存在关系的规律世界。在因果律的基础上,增加了概率表现的想法。

它的模型可以描述为(这个网络也被成为贝叶斯网络):

zi代表着规律世界,在这里称为状态量,xi代表着现实世界,这里称为观测量。

把它抽象成数学语言,状态量之间的转换矩阵定义为A,状态量表现为观测量的转换矩阵定义为B,初始时刻状态量的概率分布定义为π,这样模型表述为:

λ = (A, B, π)

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

  1. 概率计算问题

    给定模型 λ和观测序列X = (x1, x2...xT),计算该观测序列出现的概率P(X | λ)

    这个问题其实是为下两个问题服务的

  2. 参数估计

    给定观测序列X = (x1, x2...xT),估算模型λ的参数。其实就是训练模型。

  3. 预测问题

    给定模型 λ和观测序列X = (x1, x2...xT),估计状态序列Z。这个是已知模型的标注。

下边分别来看看它们。

2. 概率计算

2.1 直接求解

对状态量的所有可能性求表现出观测量的概率求和,如下:

这个复杂度是O(TNT)随着序列的上升,成指数增长

2.2 前、后向概率算法

  • 定义:

    前向概率,t时刻,1-t时刻的观测值以及qt的联合概率;

    后向概率,给定qt下,后边t+1到T时刻观测量的概率;

  • 前向算法

    第二步中,将 t 步所有的取值转换到 t+1 中制定qi的概率,再乘以qi表达出yt的概率

    第三步中,再将所有的前向概率求和。整个算法的复杂读O(T*N^2),有了极大的进步,这个过程用图像表示如下:

  • 后向算法

    后箱算法是从T往1来递推的过程,第二步中的过程可以如下图所示:

    第三步中前两项正式第1向的概率

2.3 前后向概率之间的关系

  • 互补关系

    既然前后向概率是互补的,那怎样互补的呢?

    以上概率是给定模型λ下,出现观测序列O以及第i项状态是qi状态的概率。

  • γ概率

    定义:给定模型λ和观测O下,在时刻t处于状态qi的概率

  • ξ概率

    定义:给定模型λ和观测O下,在t处于状态qi并且时刻t+1处于状态qj的状态

    这两个概率很直观,也是后边能用到的两个概率。

3. 参数估计

书中介绍了2种算法,监督学习算法,与无监督学习的算法,监督学习给定了观测序列与对应的状态序列,无监督学习只给定了观测序列,状态序列是隐变量,采用EM算法求解。

3.1 监督学习方式

监督学习是计数问题,如下:

3.2 无监督学习方式

无监督学习是用EM算法

E步:

M步:

由于极大化的参数单独在3个项中,只需对各分项求极大值,结果如下:

4. 预测问题

预测问题是给定模型λ与观测序列O,预测最有可能的状态序列I的问题。书中介绍了两种算法,分别来看看。

4.1 近似算法

前边我们看过γt(i)的定义:给定马尔科夫模型λ与观测序列O,在时刻t处于状态qi的概率,它的表达式是:

从这里只要每个时刻γt(i)的取得最大值,那对应的序列就是可以是状态的估计。

这种方法有点比较简单,缺点不能保证准确。

4.2 维特比算法

这个算法使用动态规划的方法解隐马尔科夫预测问题。这个过程与前向概率算法(也是动态规划)很像,下边来看看。

定义两个变量δ与ψ。

δ定义在时刻 t 状态为 i 的所有单个路径(i1, i2, ....it)中概率最大值:

ψ定义为取得最大值时所取得的第t-1时刻的状态

有了递推公式,真算法表述如下:

这个算法的图,与前向概率的图类似,这不过前向概率取得是和,这里取得是max:

5. 实践

HMM的观测值可以是连续的,但隐状态必须是离散的;

如果隐状态也是连续的,那就是卡尔曼滤波了;

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×