Hidden Markov Model
这篇只是个人为了加深对Markov Model的理解而做的学习笔记，基本是以易于理解的目的进行组织，所以可能有很多地方不太严禁。如有错误，还请不吝指出。
Markov Process
一个
Markov Process是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为n阶马尔科夫模型，其中n是影响下一个状态选择的（前）n个状态。最简单的
Markov Process是一阶模型，它的状态选择仅与前一个状态有关。Markov Process有两个假设：
Hidden Markov Model
Basics
HMM有 5 个元素：隐藏状态集合，一个系统的（真实）状态，可以由一个
Markov Process进行描述。观察状态集合：在这个过程中‘可视’的状态。
状态转移矩阵（
transition matrix）：隐藏状态间的转移概率。
混淆矩阵（
confusion matrix）：隐藏状态到输出状态的概率。
初始概率分布：隐藏状态的初始概率分布。
注意：其中，后 3 个经常用
X = (pi, A, B)表示，称为HMM的参数。给定一个X，也就决定了一个HMM。HMM解决 3 种不同类型的问题（前两个是模式识别的问题）：评估：给定
HMM（也就是X = (pi, A, B)已知），求产生某个观察序列的概率（前向算法：对所有能够产生观察序列的概率取sum，DP）。“评估”有时也指代筛选
HMM。也就是在给定的一系列的HMM中，求出最有可能产生这个观察序列的HMM。解码：给定
HMM（也就是X = (pi, A, B)已知），搜索最有可能生成一个观察序列的隐藏状态序列（维特比算法：对所有能够产生观察序列的概率取max，DP）。学习：
X = (pi, A, B)未知，此时要做的是：对于给定的观察序列，调整HMM的参数（X = (pi, A, B)），使观察序列出现的概率最大（前向-后向算法）。注意：“评估”是从一些已知的
HMM中，筛选出一个求出最有可能产生这个观察序列的HMM。但对于“学习”这个过程，根本就没有现成的HMM，而是要以 from scratch 的方式求解一个HMM（也就是求解出一个X = (pi, A, B)） 。关于这 3 个问题的 concept/definition 可以参考这个，更为详细。
问题 1
下面的算法主要用于：计算观察序列的概率（Finding the probability of an observed sequence），也就是问题 1（评估）。
Brute Force
解决问题 1 的最直观的办法：求出每一种可能产生这个观察序列的隐藏状态序列，然后计算对应情况下的概率，最后把它们加起来就是最终的。
但是这种求解概率的方式的时间复杂度是非常高的，如果观察序列的长度是n，隐藏状态的个数是m（这里考虑最简单的情况：任意时刻t，每个隐藏状态都有可能发生），所有可能的情况就有m^n种。
比如下面的图：
按照Brute Force算法，需要计算出所有的27种情况：
所以，自然就会想有没有更为高效的算法？有，就是前向算法（Forward Algorithm）。
前向算法（Forward Algorithm）
正如上面所说，由于Brute Force算法时间复杂度太大，无法在实际生产中使用，所以有了前向算法。
前向算法的实现方法是动态规划（Dynamic Programming）（这里有道OJ题目就是利用DP求解概率，当时没写出来 -_- ），使用DP可以暂存从开始到中间某个状态的概率(局部概率）。
本质上前向算法就是对Brute Force算法的一种变换，怎么变换？非常简单：数学公式的结合律：a * c + b * c = (a + b) * c。利用这个就可以把Brute Force转化为前向算法。记住这个，再去看前向算法，就会发现前向算法非常容易理解，详细看下面。（对于问题2的维特比算法也是利用这种变换，只是把求和换成了取max）
->->->->->->->->->->->->->->->->
前向算法示意图如下图，为了方便，定义（i，j）指代图中的第 i 行第 j 列（下标都从1开始计数）所代表的隐藏状态：
重点：结合律。一直说结合律，那到底是怎么用到结合律的？和上面的图 3 对比着看。
因为图中（2,2）的隐藏状态可以由前一时刻的任何一种隐藏状态转换而来， 按照Brute Force有：
P(O=damp|t=2,S=Cloudy) = P(O=dry|t=1,S=Sunny) × P((1,1)–>(2,2)) × P((2,2)–>damp) + P(O=dry|t=1,S=Cloudy) × P((1,2)–>(2,2)) × P((2,2)–>damp) + P(O=dry|t=1,S=Rainy) × P((1,3)–>(2,2)) × P((2,2)–>damp) 。
那如果现在要计算：在时刻 t=2（第2列）时的隐藏状态是 Cloudy，时刻 t=3（最后一列）时的隐藏状态是 Sunny 的前提下，观察序列是(dry,damp,soggy)的概率，怎么算？（有点绕，注意这里固定住了 t=2（第2列）与 t=3（最后一列）时的隐藏状态）
按照Brute Force：
P(O=soggy|t=3,S=Sunny && t=2,S=Cloudy) = P(O=dry|t=1,S=Sunny) × P((1,1)–>(2,2)) × P((2,2)–>damp) × P((2,2)–>(3,1)) × P((3,1)–>soggy) + P(O=dry|t=1,S=Cloudy) × P((1,2)–>(2,2)) × P((2,2)–>damp) × P((2,2)–>(3,1)) × P((3,1)–>soggy) + P(O=dry|t=1,S=Rainy) × P((1,3)–>(2,2)) × P((2,2)–>damp) × P((2,2)–>(3,1)) × P((3,1)–>soggy) = P(O=damp|t=2,S=Cloudy) × P((2,2)–>(3,1)) × P((3,1)–>soggy)。
看到了吧，结合律就是这样被用到的。这里提取出了共有的 P((2,2)–>(3,1)) × P((3,1)–>soggy)，同时也证明了前向算法就是对Brute Force的一种变换，自然也证明了前向算法的正确性。
上面就是前向算法的整个过程，对于任意观察序列的出现概率都可以用这种方式计算。
问题 2
下面的算法主要用于：根据一个给定的HMM模型，根据观察状态序列找到产生这一序列的潜在的隐含状态序列，也就是问题 2（解码）。
Brute Force
解决问题 2 的最直观的办法：列出所有可能的情况，从所有可能的情况中选取最有可能产生这个观察状态序列的隐藏状态序列（问题 1 是把它们加起来）。
对于图中，找出能够以最大概率产生这个观察状态序列的隐藏状态序列，需要从下面的概率中取最大的一个。
和问题 1 的 Brute Force 一样，时间复杂度太大，无法应用到实际情况。不过，这个也是有更为高效的算法的，就是：维特比算法（Viterbi Algorithm）。
维特比算法（Viterbi Algorithm）
部分概率和部分最优路径
对于网格中的每一个中间及终止状态，都有一个到达该状态的最可能路径。举例来说，在t=3时刻的3个状态中的每一个都有一个到达此状态的最可能路径，或许是这样的：
这些路径被称为局部最佳路径(partial best paths)。其中每个局部最佳路径都有一个相关联的概率，即局部概率（注意局部概率就说明对应的路径是最佳的）。不过这里不是前向算法中对之前的概率取和，而是对之前的概率取最大值。
比如上图，最终要选择其中能够以最大概率产生观察状态序列的隐藏状态序列。
在整个计算过程中，同样要使用动态规划算法：计算中间状态的局部概率，最后就能得到正确的隐藏状态序列。
计算过程
对应的分为t=1时刻和t>1时刻的局部概率的计算，看这个博客：HMM学习最佳范例六：维特比算法2
优点
说的是计算的是总体的概率，考虑到了全局的信息，这是当然的，因为计算据局部概率时算的就是考虑到了之前观察状态序列最大化概率（联合概率）。
教程（看这里）中说的另外一个不好的计算方式，使用的是贪心算法：只考虑某个特定的时刻，从它前一个时刻的状态转换到当前状态的概率 × 状态输出概率。这明显是不对的，当前这一步最好不能使全局最好（没有贪心选择性质）。
总结
关于维特比算法，需要着重强调的一点是它不是简单的对于某个给定的时间点选择最可能的隐藏状态，而是基于全局序列做决策——因此，如果在观察序列中有一个“非寻常”的事件发生，对于维特比算法的结果也影响不大。
这在语音处理中是特别有价值的，譬如当某个单词发音的一个中间音素出现失真或丢失的情况时，该单词也可以被识别出来。
问题 3
这里需要用到前向-后向算法(Forward-backward algorithm)，由于目前还没有需要用到这个算法，所以本人并没有去学习这个算法，等到以后再来补充。
想自己学习的可以看这里：HMM学习最佳范例七：前向-后向算法1 | 我爱自然语言处理
其实，前两部分的概率计算都是算的联合概率：转移概率 × 状态输出概率，所以这也说明了HMM是生成模型（Generative Model），CRF是判别模型（determistic model）。