计算语言学之隐马尔可夫模型
1 引言
隐马尔可夫模型到现在我才敢写是因为到现在才明白一点。如果有写的不对的地方还请指正。
2 隐马尔可夫模型概要
2.1 介绍
隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。
事实上,隐马尔可夫模型是一个比较巧妙的模型,它在形式上是一个概率图模型,但是它比普通的概率图模型更为复杂的地方在于,它有隐含层的存在。
2.2 系统构成
这样,整个系统就会被分为2个部分,隐藏状态和观察状态。而连接这两个部分和时间序列的,则是三个部分:
1.
2. 状态转移矩阵,从一个隐藏状态转移到另一个隐藏状态的概率分布。
3. 混淆矩阵,即给定一个隐藏状态,给出各个观察状态的概率。
2.3 HMM模型需要解决的3个问题
这里我们讲解HMM模型需要解决的3个问题:
1. 给定HMM模型,求一个观察序列概率(评估)
2. 给定HMM模型,搜索最有可能生成一个观察序列的隐藏状态序列(解码)
3. 给定观察序列,生成一个HMM模型(学习)
2.4 HMM模型实例
通常来讲,如果HMM模型给出了,那么前两个问题就解决了。而第三个问题,才是机器学习的核心所在。但是这里我们只讲解前两项,第三项太过复杂,可能需要另开一篇来介绍。
这样说,可能比较抽象,这里我们用一个例子来简单说明,下面还有它的详细介绍:
给定一个自动贩卖机,但是这个贩卖机比较特殊,它有2个出口,分别对应着机子内两个存储箱,而且你不知道你要的饮料会从哪里出现,但是它应该有一定的规律才对。另外,它出来的饮料有3种口味,更奇怪的是这三种口味也是随机的,不过也有一定的规律。
这个故事实在是太过奇特了,当然只是为了说明我们的HMM模型而构造出来的特殊实例。在这实例中,两个出口表示的就是隐含状态,而出来的饮料的口味,则是观察状态。凭直觉,你也认为这其中一定有什么规律和联系所在。没错你猜对了,现在我们给出其中的规律。
当然这个图看起来和我们说的不太一致,我们暂且认为Cola和IcedTea是两个出口,分别为CP和IP。而三种口味为cola,it,lem。这样我们就可以继续我们的讲解了。
3 给定HMM求一个观察序列概率(评估)
正如上面例题所说,我们有这样一个系统,隐藏状态之间的转换如同图的上半部分,其隐藏状态和观察状态的转换概率在图的下半部分。现在给出一个观察序列{it,col,lem},问这个观察序列的概率。初始时,系统始终从IP开始。
其实要解决这个问题,需要算法,例如,使用前向算法,还可以使用后向算法来解决。
具体的算法大家可以参考这两个,我们这里就题论题,一步一步手动解决上面那个题。
根据题目,我们只需要找到3个部分,
|
CP | IP |
---|---|---|
Value | 0 | 1 |
下面给出A:
A | CP | IP |
---|---|---|
CP | 0.7 | 0.5 |
IP | 0.3 | 0.5 |
下面给出B:
B | col | it | lem |
---|---|---|---|
CP | 0.6 | 0.1 | 0.3 |
IP | 0.1 | 0.7 | 0.2 |
再给出一个整齐一点的图
这样就可以看到在t=1,2,3时刻的状态转换了。这也是非常熟悉的转换,而我们要做的就是把所有的这种可能的都加起来:
t=1时
当t=2时
当t=3时
最后求和即可。
4 搜索最有可能生成一个观察序列的隐藏状态序列(解码)
承接上文的所有数据,我们只需要在合并的时候,使用前一时刻的最大值代替前一时刻的和即可。
t=1时
当t=2时
当t=3时
找到最大的那个即可,而且我们肉眼是可以回溯路径的。
事实上,它也可以展示成下面这种形式,然后找到一个概率最大的路径即可。应该是后向算法的表现形式:
5 给定观察序列,生成一个HMM(学习)
最难的部分在这, 这才是机器学习的关键,因为通常来讲,上面那些概率值我们是不知道的,需要通过观察统计才能够获得。在这里用的是向前向后算法,再配合极大似然估计和最大期望算法,最终才能够获得准确的参数。因此这里我们不再赘述。等有机会专门开一章讲解。