HMM 简单的入门例子
霍金曾经说过，你多写一个公式，就会少一半的读者。
所以时间简史这本关于物理的书和麦当娜关于性的书卖的一样好。
我会效仿这一做法，写最通俗易懂的答案。
掷骰子
还是用最经典的例子，掷骰子。
假设我手里有三个不同的骰子。
第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。
第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。
第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。
假设我们开始掷骰子，我们先从三个骰子里挑一个，挑到每一个骰子的概率都是1/3。
然后我们掷骰子，得到一个数字，1，2，3，4，5，6，7，8中的一个。
不停的重复上述过程，我们会得到一串数字，每个数字都是1，2，3，4，5，6，7，8中的一个。
例如我们可能得到这么一串数字（掷骰子10次）：1 6 3 5 2 7 3 5 2 4 这串数字叫做可见状态链。
但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。
在这个例子里，这串隐含状态链就是你用的骰子的序列。
比如，隐含状态链有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8
隐含状态链
一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transition probability）。
在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换概率也都一样是1/3。
这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。
比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。
这样就是一个新的HMM。
同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。
就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。
比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。
其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。
但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；
有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。
如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。
这些算法我会在下面详细讲。
答主的碎碎念
说两句废话，答主认为呢，要了解一个算法，要做到以下两点：会其意，知其形。
答主回答的，其实主要是第一点。但是这一点呢，恰恰是最重要，而且很多书上不会讲的。
正如你在追一个姑娘，姑娘对你说“你什么都没做错！”你要是只看姑娘的表达形式呢，认为自己什么都没做错，显然就理解错了。你要理会姑娘的意思，“你赶紧给我道歉！”这样当你看到对应的表达形式呢，赶紧认错，跪地求饶就对了。
数学也是一样，你要是不理解意思，光看公式，往往一头雾水。
不过呢，数学的表达顶多也就是晦涩了点，姑娘的表达呢，有的时候就完全和本意相反。所以答主一直认为理解姑娘比理解数学难多了。
三种问题
隐含状态链
知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。
这个问题呢，在语音识别领域呢，叫做解码问题。
这个问题其实有两种解法，会给出两个不同的答案。每个答案都对，只不过这些答案的意义不一样。
第一种解法求最大似然状态路径，说通俗点呢，就是我求一串骰子序列，这串骰子序列产生观测结果的概率最大。
第二种解法呢，就不是求一组骰子序列了，而是求每次掷出的骰子分别是某种骰子的概率。
比如说我看到结果后，我可以求得第一次掷骰子是D4的概率是0.5，D6的概率是0.3，D8的概率是0.2.第一种解法我会在下面说到，但是第二种解法我就不写在这里了，如果大家有兴趣，我们另开一个问题继续写吧。
骰子是否被换了？
还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率。
看似这个问题意义不大，因为你掷出来的结果很多时候都对应了一个比较大的概率。
问这个问题的目的呢，其实是检测观察到的结果和已知的模型是否吻合。
如果很多次结果都对应了比较小的概率，那么就说明我们已知的模型很有可能是错的，有人偷偷把我们的骰子給换了。
转换概率
知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）。
这个问题很重要，因为这是最常见的情况。
很多时候我们只有可见结果，不知道HMM模型里的参数，我们需要从可见结果估计出这些参数，这是建模的一个必要步骤。
零号问题
问题阐述完了，下面就开始说解法。
（0号问题在上面没有提，只是作为解决上述问题的一个辅助）
0. 一个简单问题
其实这个问题实用价值不高。
由于对下面较难的问题有帮助，所以先在这里提一下。
知道骰子有几种，每种骰子是什么，每次掷的都是什么骰子，根据掷骰子掷出的结果，求产生这个结果的概率。
解法无非就是概率相乘：
1. 看见不可见的，破解骰子序列
最大似然路径问题
这里我说的是第一种解法，解最大似然路径问题。
举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。
我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。
其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照第零个问题的解法把每个序列对应的概率算出来。
然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。
Viterbi algorithm
另外一种很有名的算法叫做 Viterbi algorithm.
要理解这个算法，我们先看几个简单的列子。
（1）首先，如果我们只掷一次骰子：=> 1
看到结果为1.对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6和1/8.
（2）把这个情况拓展，我们掷两次骰子：=> 1 => 6
结果为1，6.这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。
显然，要取到最大概率，第一个骰子必须为D4。
这时，第二个骰子取到D6的最大概率是
第一次选D4 => 选D4且抛出 1 => 第二次选择 D6 => 选 D6 且抛出 6
同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第二个骰子取到D6的概率最大。
而使这个概率最大时，第一个骰子为D4。所以最大概率骰子序列就是D4 D6。
（3）继续拓展，我们掷三次骰子：1 => 6 => 3
同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。
我们再次发现，要取到最大概率，第二个骰子必须为D6。
这时，第三个骰子取到D4的最大概率是
同上，我们可以计算第三个骰子是D6或D8时的最大概率。
我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。
写到这里，大家应该看出点规律了。
既然掷骰子一二三次可以算，掷多少次都可以以此类推。
我们发现，我们要求最大概率骰子序列时要做这么几件事情。
首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。
然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。
因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。
当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。
然后，我们要把对应这个最大概率的序列从后往前推出来。
这里我们其实可以看到 动态规划算法 的思想，参见 Viterbi 算法
2. 谁动了我的骰子？
比如说你怀疑自己的六面骰被赌场动过手脚了，有可能被换成另一种六面骰，这种六面骰掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。
你怎么办么？
答案很简单，算一算正常的三个骰子掷出一段序列的概率，再算一算不正常的六面骰和另外两个正常骰子掷出这段序列的概率。
如果前者比后者小，你就要小心了。
- 例子
比如掷骰子的结果为：1=>6=>3
要算用正常的三个骰子掷出这个结果的概率，其实就是将所有可能情况的概率进行加和计算。
同样，简单而暴力的方法就是把穷举所有的骰子序列，还是计算每个骰子序列对应的概率，但是这回，我们不挑最大值了，而是把所有算出来的概率相加，得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列（马尔可夫链）。
我们会应用一个和前一个问题类似的解法，只不过前一个问题关心的是概率最大值，这个问题关心的是概率之和。
解决这个问题的算法叫做前向算法（forward algorithm）。
（1）首先，如果我们只掷一次骰子：=> 1
看到结果为1.产生这个结果的总概率可以按照如下计算，总概率为0.18：
（2）把这个情况拓展，我们掷两次骰子：=> 1 => 6
看到结果为1，6.产生这个结果的总概率可以按照如下计算，总概率为0.05：
（3）继续拓展，我们掷三次骰子：=> 1 => 6 => 3
看到结果为1，6，3.产生这个结果的总概率可以按照如下计算，总概率为0.03：
3.掷一串骰子出来，让我猜猜你是谁
（答主很懒，还没写，会写一下EM这个号称算法的方法）
参考 EM 最大期望算法
上述算法呢，其实用到了递归，逆向推导，循环这些方法，我只不过用很直白的语言写出来了。
如果你们去看专业书籍呢，会发现更加严谨和专业的描述。
毕竟，我只做了会其意，要知其形，还是要看书的。
HMM(隐马尔科夫模型）
隐马尔科夫模型是统计模型在机器学习中的典型应用，即使在目前神经网络飞速发展的当下，也被认为是NLP领域相当有效的方法。
转移概率，发射概率
现实生活中，我们可以观察到很可见状态，这些可见状态是已发生的，确定的。
这些可见状态会依赖于一些隐藏状态，隐藏状态之间会存在转移概率（transition probality), 而从隐藏状态到可见状态则存在发射概率（emission probality）
HMM 模型
如上图所示，白色那一行描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列，蓝紫色那一行是各个状态生成可观测的随机序列
话说，上面也是个贝叶斯网络，而贝叶斯网络中有这么一种，如下图：
代表：c确定时a和b独立。(c为实心圆代表：c已经被确定)
这时，如果把z1看成a，x1看成b，z2看成c的话，则因为第一个图的z1是不可观测的(所以z1是空心圆)，也就是没确定，则x1和z2就一定有联系。
进一步，如果把z2、x2合在一起看成c的话，则x1和z2、x2就一定有联系，则x1和x2有联系(不独立)。
推广之后：x2和x3不独立，x1和x3也不独立，于是xn们互相不独立。
LDA 假定文章中的词与词之间互相独立，而HMM中是所有的观测互相均不独立。
所以，对于一篇Machine Learn的文章，LDA会吧“机器”和“学习”分成两个词，而HMM会将其视为一个词。
ps: 个人理解词语之间是不独立的。
HMM 确定
初始概率分布
z1可能是状态1，状态2 … 状态n，于是z1就有个N点分布：
即：Z1对应个n维的向量。
上面这个n维的向量就是初始概率分布，记做π。
状态转移矩阵
但Z2就不能简单的“同上”完事了，因为Z2和Z1不独立，所以Z2是状态1的概率有：Z1是状态1时Z2是状态1，Z1是状态2时Z2是状态1,…, Z1是状态n时Z2是状态1，于是就是下面的表
即：Z1->Z2对应个n*n的矩阵。
同理：Zi -> Zi+1对应个n*n的矩阵。
上面这些 n*n 的矩阵被称为状态转移矩阵，用 An*n 表示。
当然了，真要说的话，Zi -> Zi+1的状态转移矩阵一定都不一样，但在实际应用中一般将这些状态转移矩阵定为同一个，即：
只有一个状态转移矩阵。
图1的第一行就搞定了，下面是第二行。
观测矩阵
如果对于zi有：状态1, 状态2, …, 状态n，那zi的每一个状态都会从下面的m个观测中产生一个：观测1, 观测2, …, 观测m，所以有如下矩阵：
这可以用一个 n*m 的矩阵表示，也就是观测矩阵，记做 Bn*m。
由于HMM用上面的π，A，B就可以描述了，于是我们就可以说：HMM由初始概率分布π、状态转移概率分布A以及观测概率分布B确定，为了方便表达，把A, B, π 用 λ 表示，即：
λ = (A, B, π)
HMM 的性质与常见问题
性质
齐次假设
当前状态之和上一个状态有关系，用公式表示的话就是：
P(zt|zt-1,xt-1, zt-2, xt-2, ..., z1, x1)= P(zt | zt-1)
参见 马尔科夫链
观测独立性假设
所有的观测之间是互相独立的，某个观测之和生成它的状态有关系，即：
P(xt|zt,xt, zt-1, xt-1, zt-2, xt-2,..., z1, x1) = P(xt | zt)
PS：在一开始时说x1和z2、x2不独立，怎么在这里又说x1和x2独立呢？
其实真严格追究的话x1和x2的确不互相独立，因为x1是被z1生成的，x2是被z2生成的， 但z2的形成受z1影响，所以x1和x2一定也会有联系。
但是为了研究和应用的方便，就假设：生成x1的z1和生成x2的z2不独立，但x1和x2独立。
中文分词的例子
假设我们相对如下这行话进行分词：欢迎来到我的博客
再假设我们是这样分的：找到“终止字”，然后根据终止字来分词。
即：对于这行字，“迎、到、我、的、客”是终止字，于是最终这么分词：欢迎/来到/我/的/博客
下面用上面的知识对这个例子建立HMM的A, B, π：
初始概率分布的确定：
1，对于每个样本，我们的目标是确定其是不是“终止字”，因此对于每个样本，其状态只有n=2个：状态1 – 是、状态2 – 不是。
2，因此初始概率分布π为：
π = {p1，p2}
P1：整个句子中第一个字是非终止字的概率
P2：整个句子中第一个字是终止字的概率
状态转移矩阵的确定：
刚才已经知道状态有n=2个，于是状态转移矩阵就立马得出了，即状态转移矩阵是个n*n的矩阵，如下：
A=
p11：非终止字 -> 非终止字的概率。
p12：非终止字 -> 终止字的概率。
p21：终止字 -> 非终止字的概率。
p22：终止字 -> 终止字的概率。
观测矩阵的确定：
如果我们的目标文字使用Unicode编码，那么上面的任何一个字都是0~65535中的一个数，于是我们的观测就会有m=65536个，于是观测矩阵就是个n*m的矩阵，如下：
B=
p1,0：Unicode编码中0对应的汉字是非终止字的概率
p1,65535：Unicode编码中65535对应的汉字是非终止字的概率
p2,0：Unicode编码中0对应的汉字是终止字的概率
p2,65535：Unicode编码中65535对应的汉字是终止字的概率
PS：为什么x会有65535个观测啊？“欢迎来到我的博客”这个明明只有8个字。
原因是因为真正的HMM面临的情况，即：现有了 Z1=“非终止字”这个状态，然后根据这个状态从65535个字中选出x1=“欢”这个字，然后根据状态转移矩阵，下一次转移到了Z2 =“终止字”，然后根据Z2从65535个字中选出了x2=“迎”这个字，这样，最终生成了这句话。
HMM 常见问题
问题
现在有几个问题：
1，知道HMM的参数 λ = (A, B, π) 和观测序列O = {o1,o2, …, oT} ，如何计算模型 λ 下观测序列O出现的概率 P(O | λ)。
2，HMM的参数如何确定？
比如：对于刚才的中文分词的小例子。
初始概率分布π好确定：是不是终结词的概率各是0.5。
观测矩阵B也好确定：1/65535嘛
但状态转移矩阵怎么确定？我怎么知道下个词是终结词的概率是多少？
3，知道HMM的参数 λ = (A, B, π) 和观测序列O = {o1,o2, …, oT}，如何计算给定观测序列条件概率 P(I|O, λ)最大的状态序列I，即：
对于中文分词，我想到底如何分的词。
解法
上面三个问题：
第一个问题被称为：概率计算问题。
解决办法：
-
前向-后向算法(一种动态规划算法)。
第二个问题被称为：学习问题。
解决办法：如果状态序列已知，那用最大似然估计就好了，但HMM的状态序列未知，即含有隐变量，所以要使用Baum-welch算法
(其实其本质就是EM 最大期望算法)。
第三个问题被称为：预测问题/解码问题。
解决办法：Viterbi 算法(一种动态规划算法)。
概率计算问题
解决办法
该问题有两种解决办法：
1，直接/暴力算法。
2，前向算法/后向算法。
而上面两个算法中的“暴力方法”是实际应用中绝不会被使用的。
Q：那为什么还说这玩意！
A：理解了直接/暴力算法可以帮助你推导Baum-welch算法。
暴力穷举法
问题
已知HMM的参数 λ，和观测序列O = {o1, o2, …,oT}，求 P(O|λ)
思想核心
大力出奇迹。
思路
1，列举所有可能的长度为T的状态序列I = {i1, i2, …, iT}；
2，求各个状态序列I与观测序列的联合概率 P(O,I|λ)；
3，所有可能的状态序列求和∑_I P(O,I|λ)得到P(O|λ)。
步骤
1，最终目标是求O和I同时出现的联合概率，即：
P(O,I|λ)= P(O|I, λ)P(I|λ)
那就需要求出P(O|I, λ) 和 P(I|λ)。
2，求P(I|λ) ，即状态序列 I = {i1,i2, …, iT} 的概率：
P(I|λ) = P(i1,i2, ..., iT |λ)
=P(i1 |λ)P(i2, i3, ..., iT |λ)
=P(i1 |λ)P(i2 | i1, λ)P(i3, i4, ..., iT |λ)
=......
=P(i1 |λ)P(i2 | i1, λ)P(i3 | i2, λ)...P(iT | iT-1, λ)
而上面的 P(i1 |λ) 是初始为状态i1的概率，P(i2 | i1, λ) 是从状态i1转移到i2的概率，其他同理，于是分别使用初始概率分布 π 和状态转移矩A，就得到结果：
上面的ai1i2代表A的第i1行第i2列。
3，P(O|I, λ)，即对固定的状态序列I，观测序列O的概率是：
4，代入第一步求出 P(O,I|λ)。
5，对所有可能的状态序列I求和得到观测序列O的概率 P(O|λ)：
时间复杂度：
每个时刻有n个状态，一共有t个时刻，而根据上面的第5步可以知道每个时刻需要乘2T-1次，所以时间复杂度是：O((2T-1)n^T)
拓展阅读
参考资料
《统计学习方法》，李航
《机器学习》，Tom M.Mitchell
《统计学自然语言处理》
隐马尔可夫(HMM)、前/后向算法、Viterbi算法 再次总结
http://www.360doc.com/content/18/0911/08/17157244_785582242.shtml
