我们通常都习惯寻找一个事物在一段时间里的变化模式（规律）。这些模式发生在很多领域，比如计算机中的指令序列，句子中的词语顺序和口语单词中的音素序列等等，事实上任何领域中的一系列事件都有可能产生有用的模式。马尔科夫模型（以下简称HMM）是对不确定状态的一种描述，也是贝叶斯网络的一种特殊情况，它不同于确定状态（如现实生活中的交通十字路口的红绿灯的交替变化，这是一个确定状态序列），HMM是为了根据观测结果来推理其背后的隐藏状态链。





图1 红绿灯的确定模式


    通常情况下，HMM分为n阶HMM，即t时刻的状态与前n个时刻的状态均相关，但是本文只考虑一阶HMM，这样计算起来很方便。

我们先看一个HMM的例子，有人试图通过一片海藻推断天气。民间传说告诉我们“湿透的”海藻意味着潮湿阴雨，而“干燥的”海藻则意味着阳光灿烂。如果它处于一个中间状态（‘有湿气’），我们就无法确定天气如何。然而，天气的状态并没有受限于海藻的状态，所以我们可以在观察的基础上预测天气是雨天或晴天的可能性。另一个有用的线索是前一天的天气状态（或者，至少是它的可能状态），通过综合昨天的天气及相应观察到的海藻状态，我们有可能更好的预测今天的天气。


    现在，我们规定，我们观察到的海藻的状态称为观察结果，而天气的情况我们称为隐藏状态，隐藏状态与观测结果是具有一定联系的。一般隐藏状态之间具有一定的转移概率，即如果今天是晴天，明天是晴天阴天或雨天的概率分别是多少；同时，给定隐藏状态产生观测结果的概率称为生成概率，即给定今天是晴天，那么海藻的状态为干燥的概率是多少。若一个HMM系统具有M个隐藏状态，那么状态转移概率矩阵的大小为M*M，若系统具有N种观测结果，则生产概率矩阵的大小为M*N。同时，我们还需要确定系统的初始状态分布，即在t=0时刻的各个状态的分布概率。


    我们来正式确定一下这个HMM系统的相关要素：

-----隐藏状态个数M；

-----可观测结果种类N；

-----序列长度T；

-----初始概率分布pi；

-----状态转移概率矩阵A;

-----结果生成矩阵B；



    例如我们可以自定义以下一个实际问题，假如现在天气有三个状态，分别是多云、阴天、大雨；而海藻的观测结果可能有四种情况，分别是干燥、稍干、湿润、潮湿；并且我们具有以下系统的信息：

*****一、状态转移概率矩阵






*****二、结果生成概率矩阵






*****三、初始状态概率分布






这样我们就组建好了一个HMM的基本要素。



    一个更实际的问题是语音识别，我们听到的声音是来自于声带、喉咙大小、舌头位置以及其他一些东西的组合结果。所有这些因素相互作用产生一个单词的声音，一套语音识别系统检测的声音就是来自于个人发音时身体内部物理变化所引起的不断改变的声音。


    一些语音识别装置工作的原理是将内部的语音产出看作是隐藏的状态，而将声音结果作为一系列观察的状态，这些由语音过程生成并且最好的近似了实际（隐藏）的状态。在这两个例子中，需要着重指出的是，隐藏状态的数目与观察状态的数目可以是不同的。一个包含三个状态的天气系统（晴天、多云、雨天）中，可以观察到4个等级的海藻湿润情况（干、稍干、潮湿、湿润）；纯粹的语音可以由80个音素描述，而身体的发音系统会产生出不同数目的声音，或者比80多，或者比80少。


    那么，HMM模型主要有以下三个作用：

【评估（前向算法）】：有一些HMM集合及一个观测序列，确定哪一个HMM最有可能生成这个观测序列。例如语音识别中，每一个单词都看做一个HMM。

【解码（维特比算法）】：给定序列，去找寻最有可能的隐藏状态序列。即已知观察序列和HMM来确定最有可能的隐藏状态序列。

【学习（BW算法，又称前向-后向算法）】：根据观察序列来生成一个HMM的所有要素。


本文接下来将重点介绍这三种算法的原理，以及如何使用C语言来实现它们。



HMM 的三个算法

前向算法

前向算法要解决的问题是，给定一组观测序列（Observations，简称O），我们如何确定一个HMM生成该观测序列的概率，即求出P(O|HMM)。


首先，我们第一个想到的想法一定是根据初始状态概率分布pi、状态转移矩阵A、结果生产概率矩阵B来枚举所有的状态序列，然后把这些状态生成给定观测序列的概率均求出来，最后累加求和即可得到所有隐藏状态生成此观测结果的总概率。用公式表示出来如下所示：

P(observations|HMM)=P(observations|states sequence1)+P(observations|states sequence2)+...

可以看到，上面的计算量非常巨大，若一共有N个状态，T个时刻，则所有可能的状态序列个数为N^T个，计算复杂度为T*N^T。



为了减少每一步的重复计算，我们可以使用前向算法。首先，定义一个局部概率alpha_t(j)，它表示t时刻位于状态j的局部概率。那么，对于不同时刻，我们可以分两步讨论：






其中a代表状态转移概率，b代表结果生成概率。前向算法计算复杂度为T*N^2。


最后，所有状态生成结果的总概率为对T时刻所有状态进行相加，故

P(observations|HMM)=SUM_i{alpha_T(i)}


实际应用中，我们先使用前向算法评估每一个HMM，然后选用概率最高的那一个HMM。




维特比算法


维特比算法要解决的问题是给定HMM下，找到一组最合适的隐藏状态序列来生成给定的观测序列。这里我们首先定义一个局部概率delta_t(i)，它表示t时刻达到状态i的所有状态序列中概率最大的概率。

那么，同样，我们可以分两步写出delta_t(i)的表达式：






上面的表达式表明delta_t(i)即遍历上一时刻的所有序列，找到使得概率最大的那个概率。


但是，问题是我们要找到一组概率最大的状态序列，如果我们仅仅按照上面的表达式来计算的话，最后只能得到t=T时刻的最大概率，即所有状态序列的最大概率被求出来了，但是这个最大概率的序列到底是什么，我们还无法得知。因此，这时候我们需要定义一个方向指针，用于回溯上一时刻的最佳状态：






它表示t时刻为i的状态的最有可能的上一个时刻的状态为多少。注意这里求最大时并没有乘以结果概率。回溯可以确定每一时刻最可能状态。维特比算法具有全局性，它不受某一时刻噪声的影响。



前向后向算法


前向-后向算法用于训练一个HMM模型，即给定观测序列，建立一个HMM模型以及确定其参数。这个算法相对要麻烦一点，也是实际中首先要做的一步。

首先，我们定义一个前向局部概率alpha_t(i)，它的表达式如下：






即已知HMM以及t时刻位于状态i，从初始时刻到t时刻的局部观察序列的概率。

定义一个后向变量beta_t(j)，其表达式如下：






即已知HMM以及t时刻位于状态i，从t+1时刻到终止时刻的局部观察序列的概率。



接下来，我们对beta进行初始化：






这样，我们就可以使用EM算法来估计HMM的参数了。给定观测序列O以及HMM，定义t时刻位于状态i的概率为






分母的作用是确保归一化，定义t时刻位于状态i以及t+1时刻位于状态j的概率为






下面我们进行参数估计：





 
 
 
 
 
 
 
来源：深度学习每日摘要
智造家 查看全部