HMM(隐马尔可夫模型)总结
2011-12-02 16:35阅读：
通过前几时断续的学习，发现自己对HMM模型的了解还只停留在皮毛，导致在学习CRF模型并将其与最大熵模型、HMM、MEMM做比较时感觉很吃力，所以又花了两天时间使劲看了遍HMM，发现了解得确实深刻了很多，现小结一下，争取把看过的知识变成自己的，特别感谢52nlp网站http://www.52nlp.cn/和崔晓源翻译的HMM相关资料，英文学习网站http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html，中文神马的都是浮云。
每次要学习一点新的东西时，总是想迫切地知道学它是用来干嘛的，然后就是想知道它该怎么用，我觉得这是接触并接受新知识的两个最起码的原则。HMM
来源于现实社会的需求，它是为人们服务的，我们通常都习惯于寻找一个事物在一段时间内的变化规律，并能在特定情况下预测下一变化，比如预测天气等。当然
HMM还有一些其他的应用，后面还会提到。
既然HMM用处是具有实际意义的，那么下面我们来学习它。
实际生活中，有的时候状态的转变是固定的，如红绿灯的变化规律，下一状态是已知的，这种模式叫确定性的生成模式，而在大多数情况下状态的改变却是不确定的，如根据今天的天气推测明天的天气，这个状态的变化是不明确的，这种模式叫非确定的生成模式，通常我们更倾向于研究非确定性生成模式，所以我们用到了HMM。这里明确一个概念，n阶HMM，意思是说当前的状态只与前n个状态有关，我们通常研究的是1阶HMM，意思是当前状态只与前一状态有关，显然这是不符合现实的一个假设，但它却非常适于分析，同时要注意HMM是与时间无关的一个模型，这也是一个与现实不符的假设。（从此可看出HMM有待改进）
HMM的核心在于思想，算法与两个矩阵。
HMM的两个矩阵为状态转移矩阵（表征状态之间的转移概率）、混淆矩阵（表征特定状态下发射符号（观察值）的概率）。
根据HMM不同的应用，有不同的算法来解决。
主要是三类问题。
①
根据已知的HMM找出一个观察序列的概率—评估
这类问题是假设有若干HMM模型，对应每个模型找出给定观察序列的概率，最大概率对应的模型则是最可能生成该序列的系统。
应用：根据观察序列判断季节，语音识别。
算法——
穷举搜索举例：
对于水藻和天气的关系，我们可以用穷举搜索方法得到下面的状态转移图（trellis）： 
图中，sunny,cloudy,rainy表示三个状态，dry,damp,soggy表示观察值，每一列与相邻列的连线由状态转移概率决定，而观察状态和每一列的隐状态则由混淆矩阵（处于某一状态，发射某一观察值的概率）决定。如果用穷举的方法的到某一观察状态序列的概率，就要求所有可能的天气状态序列下的概率之和，这个trellis中共有3*3=27个可能的序列。
Pr(dry,damp,soggy | HMM) =
Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy |
sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + .
. . . Pr(dry,damp,soggy | rainy,rainy ,rainy)
可见计算复杂度是很大，特别是当状态空间很大，观察序列很长时。我们可以利用概率的时间不变性解决复杂度。
递归方法（Forward
Algorithm）举例：
首先定义部分概率为到达trellis中某一中间状态的概率。把长度为T的观察状态序列表示为：
在计算trellis中某一中间状态的概率时，用所有可能到达该状态的路径之和表示。
比如在t=2时间，状态为cloudy的概率可以用下面的路径计算：
用Pt (
j ) 表示在时间t时 状态j的部分概率。计算方法如下：
Pt ( j )= Pr( observation |
hidden state is j ) * Pr(all paths to state j at time
t)
最后的观察状态的部分概率表示，这些状态所经过的所有可能路径的概率。比如： 
这表示最后的部分概率的和即为trellis中所有可能路径的和，也就是当前HMM下观察序列的概率。
我们计算部分概率的公式为:
Pt ( j )= Pr( observation |
hidden state is j ) x Pr(all paths to state j at time
t)
但是在初始状态，没有路径到达这些状态。那么我们就用probability乘以associated observation
probability计算：
这样初始时刻的状态的部分概率就只与其自身的概率和该时刻观察状态的概率有关。
这一算法最后需要的是概率的和。
对于观察序列长度T，穷举法的复杂度为T的指数级；而Forward Algorithm的复杂度为T的线性。
手动计算过程：观察序列为Damp,Soggy,Dry，计算该模型的概率，不同的模型概率不同，概率最大的对应的则是能产生该序列的最可能模型。
状态转移矩阵A：
|
Sunny
|
Cloudy
|
Rainy
|
Sunny
|
0.5
|
0.25
|
0.25
|
Cloudy
|
0.375
|
0.125
|
0.375
|
Rainy
|
0.125
|
0.675
|
0.375
|
混淆矩阵B：
|
Damp
|
Soggy
|
Dry
|
Dryish
|
Sunny
|
0.15
|
0.05
|
0.6
|
0.20
|
Cloudy
|
0.25
|
0.25
|
0.25
|
0.25
|
Rainy
|
0.35
|
0.5
|
0.05
|
0.10
|
