隐马尔可夫链之基本原理
由ypyu创建，最终由ypyu 被浏览 17 用户
在本讲中，我会给大家介绍隐马尔可夫模型（HMM）的基本原理。HMM是一种非常重要的机器学习算法，在自然语言处理和语音识别中有着极其广泛的应用。HMM涉及到的内容非常的多，本次讲解无法面面俱到，希望大家能抽出时间更加系统地学习这个模型。
一个进入HMM世界的简单例子是：在赌场内有一个赌徒玩得一手好骰子，战无不胜，赌场老板怀疑赌徒偷换了骰子（不均匀的），于是通过摄像头把每次骰子出现的点数都记录了下来，现在问题是通过这一串点数你能判断赌徒是否偷换了骰子吗？如果偷换了那么用了几个作弊的骰子？这几个作弊的骰子每个点数出现的概率是多大？（该例子来源于小小鸟小小 - 博客频道 - CSDN.NET）
在讲HMM之前我们先谈谈马尔可夫链，马尔可夫链是一种非常特殊的随机过程。假设一个系统有多个状态可以切换，每个时刻都会处于某一个状态，现在知道了它在0,1,2,..,T时刻的状态后我们想推断其在T+1时刻的状态。马尔可夫链做了一个简单的假设，第T+1时刻的状态仅由第T时刻的状态决定，因此如果知道了状态两两之间切换的概率以及T时刻的状态就可以得到第T+1时刻的状态分布了。
从上面的讨论可以知道马尔可夫链由三部分组成：可以枚举的状态，状态之间的转移概率矩阵，系统初始的状态。相比于马尔可夫链，隐马尔可夫链有两种类型的状态，一种是可以观察到的状态，另一种则是无法被观测的隐含状态。隐含状态是一条马尔科夫链，而可观察状态由隐含状态决定。如果要描述这样的一个模型，显然需要两个转移概率矩阵：隐含状态之间的转移概率，隐含状态到可观察的转移概率。
结合骰子的例子，HMM模型由这样几个组成部分：
- 隐含状态H：骰子1，骰子2，...
- 可观察状态O：1,2,3,4,5,6六个点数
- 隐含状态之间的转移概率A：赌徒在几个骰子切换的概率
- 隐含状态到可观察的转移概率B：骰子i撒出各点数的概率
- 开始的隐含状态pi：赌徒最开始拿的是第i个骰子的概率分布P(H=i)
好了，以上就完整地构建了一个HMM模型，那么如何利用该模型和算法解决问题呢？我们由浅入深一个个来说明这些问题是如何被解决的，背景仍然是赌徒撒筛子的故事。
问题0
假设我们知道了HMM模型的一切（知道骰子有几种，每种骰子是什么，每次掷的都是什么骰子），如何计算某一个可观察状态序列出现的概率？
这个问题非常简单，概率相乘即可。
问题1
假设现在我们知道了初始的隐含状态，如果赌徒的套路全被摸清了（H、A、B、pi已知），如何计算某一个可观察状态序列出现的概率？（predict 问题）
首先，根据简单的概率计算第一次掷k点的概率是非常容易的。假设有N种隐含状态，那么经过N次概率计算并求和即可得到第一次掷k点的概率：sum(P(H=i)*P(H=i to O=k))。
第二次掷k点的概率怎么算呢？同理有sum(P(H=i)*P(H=i to H=j)*P(H=j to O=k))，其中i和j可以任取N种隐含状态中的一个，可以看到现在需要进行N^2次概率计算。依此类推，如果要计算第L次掷k点的概率，需要进行N^L次方次运算。
根据上面的讨论，这个问题理论上是可以解决的，但是需要的计算复杂度非常高。上面的计算方法，我们很容易发现一个问题，每次计算第n次掷k点的概率时都是重新计算并没有用到前面的计算结果，如何用递归的方式去简化计算呢？
第一次掷k1点时的概率可以分解为N份，每份是P(H=i|第一次O=k1)=P(H=i)*P(H=i to O=k1)，现在我们递归地计算P(H=i|第一次O=k2)。
显然P(H=i|第一次O=k2)=sum(P(H=i|第一次O=k1)*P(H=i to H=j)*P(H=j to O=k2)。在每次递归中，P(H=i to H=j)*P(H=j to O=k2)对于特定的i和j是始终不变的，不用额外计算。这种算法叫做前向算法（forward algorithm）。
同样地，我们可以将向前算法的方向变换一下，从最后的观察状态开始递归推导到最前面，这种算法叫做后向算法。
问题2
假设现在知道了一串点数（每个时刻的可观察状态序列{O}）和pi、H、A、B，我们想了解可观察状态序列{O}背后最可能对应的隐含状态序列{H}。（encode问题）
这里有个笨办法，我把所有可能的隐含状态排列方式全部列出来，然后就转化成了问题0，分别计算在已知隐含状态序列{H}的情况下可观察状态序列{O}出现的概率，概率最大的{H}就是最可能的隐含状态序列。然而这样做的开销是非常大的，计算复杂度是O(N^L)。
基于问题1的解决方法，我们需考虑是否有递归的方法，注意到问题1是求sum而这里是求max，两个问题的本质其实是一样的。从问题一的解答我们可以知道第一天隐藏状态H为i、掷k1点时的概率P(H=i)*P(H=i to O=k1)，在这里取概率最大的i作为第一天最可能的隐藏状态。第二天隐藏状态H为j、掷k1点时的概率是P(H=i|第一次O=k1)*P(H=i to H=j)*P(H=j to O=k2)，同样取概率最大的j作为第二天最可能的隐藏状态，依次类推即可解决该问题。这种算法叫做维特比算法（Viterbi Algorithm）。
这里有一个算法动态图大家可以有一个直观的认识：https://en.wikipedia.org/wiki/File:Viterbi_animated_demo.gif#file
问题3
现在我们只知道O、H（有几个骰子)，pi、A和B都不知道，如何通过可观察状态序列{O}去估计概率转移矩阵A和B。（learning问题）
要解决这个问题是非常不容易的，下面我来向大家重点介绍前向后向（Baum-Welch）算法，该算法是EM算法的一个特例。
初看这个问题似乎很难入手，最简单的一个想法是先随便假设(pi、A、B)的值看看。
现在回到我们的问题，学习问题实质上是要找到一个最佳的参数使得观察状态序列和隐含状态序列出现的概率最大。根据EM算法中的E步有：
以上Q函数的构造需要大家先去熟悉EM算法，在此不做过多说明。上面这个式子中上划线lambda是我们假设的参数值，现在需要求得真实的参数值替换我们的假设值，这样不断的迭代逼近直至收敛就可以估计出模型的参数。EM算法的E步实际上是构造了一个最优化目标函数，最大化Q即可求得本次迭代中真实参数值lambda。
可以将Q式进一步变换一下：
分别对pi、a、b分别求偏导，即可求得模型中每个参数值。
HMM在语音识别和文本挖掘中有着大量的应用，在量化投资中它也有着用武之地，在HMM时序应用篇中会详细介绍HMM如何应用于金融时序模型中。