学习目标：
在机器学习算法中，马尔可夫链(Markov chain)是个很重要的概念。马尔可夫链（Markov chain），又称离散时间马尔可夫链（discrete-time Markov chain），因俄国数学家安德烈·马尔可夫（俄语：Андрей Андреевич Марков）得名。
马尔科夫链即为状态空间中从一个状态到另一个状态转换的随机过程。
该过程要求具备“无记忆”的性质：
马尔科夫链作为实际过程的统计模型具有许多应用。
在马尔可夫链的每一步，系统根据概率分布，可以从个状态变到另一个状态，也可以保持当前状一态。
状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。
马尔可夫链的数学表示为：
既然某一时刻状态转移的概率只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，这个马尔科夫链的模型就定了。
下图中的马尔科夫链是用来表示股市模型，共有三种状态：牛市（Bull market）, 熊市（Bear market）和横盘 （Stagnant market）。
每一个状态都以一定的概率转化到下一个状态。如，牛市以0.025的概率转化到横盘的状态。
当这个状态转移矩阵P确定以后，整个股市模型就已经确定！
隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。
其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。
下面我们一起用一个简单的例子来阐述：
假设我手里有三个不同的骰子
但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。
在这个例子里，这串隐含状态链就是你用的骰子的序列。
一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transition probability）。
在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换
概率也都一样是1/3。
这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。
同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。
其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的。
如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。这些算法我会在后面详细讲。
2.2.1 问题阐述
和HMM模型相关的算法主要分为三类，分别解决三种问题：
1）知道骰子有一种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想
知道每次掷出来的都是哪种骰子（隐含状态链）。
第一种解法求最大似然状态路径，说通俗点呢，就是我求一串骰子序列，这串骰子序列产生观测结果的概率最大。
第二种解法呢，就不是求一组骰子序列了，而是求每次掷出的骰子分别是某种骰子的概率。比如说我看到结果
后，我可以求得第一次掷骰子是D4的概率是0.5，D6的概率是0.3，D8的概率是0.2。
2）还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰⼦掷出的结果（可见状态链）。
3）知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）。
2.2.2 问题解决
一个简单问题【对应问题二】
其实这个问题实用价值不高。由于对下面较难的问题有帮助，所以先在这里提一下。
解法无非就是概率相乘：
看见不可见的，破解骰子序列【对应问题一】
这里我说的是第一种解法，解最大似然路径问题。
举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果
（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。
其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照上一个问题的解法把每个序列对应的概率算出来。然
后我们从里面把对应最大概率的序列挑出来就行了。
如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。
另外一种很有名的算法叫做维特比算法（Viterbi algorithm）. 要理解这个算法，我们先看几个简单的列子。 首先，如果我们只掷一次骰子：
看到结果为1.对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6和1/8.
把这个情况拓展，我们掷两次骰子：
结果为1，6.这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。显然，要取到
最大概率，第一个骰子必须为D4。这时，第二个骰子取到D6的最大概率是：
同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第个骰二取到D6的概率最大。而使这个概率最大时，第一个骰⼦为D4。所以最大概率骰子序列就是D4 D6。 继续拓展，我们掷三次骰子：
同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。我们再次发现，要取到最大概率，第二个骰子必须为D6。
这时，第三个骰子取到D4的最大概率是：
同上，我们可以计算第三个骰子是D6或D8时的最大概率。我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。
写到这里，大家应该看出点规律了。既然掷骰子一、二、三次可以算，掷多少次都可以以此类推。
我们发现，我们要求最大概率骰子序列时要做这么几件事情。
谁动了我的骰子？【对应问题三】
比如说你怀疑自己的六面骰被赌场动过手脚了，有可能被换成另一种六面骰，这种六面骰掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。你怎么办么？
答案很简单，算一算正常的三个骰子掷出一段序列的概率，再算一算不正常的六面骰和另外两个正常骰子掷出这段
序列的概率。如果前者比后者小，你就要小心了。
比如说掷骰子的结果是：
要算用正常的三个骰子掷出这个结果的概率，其实就是将所有可能情况的概率进行加和计算。
同样，简单而暴力的方法就是把穷举所有的骰子序列，还是计算每个骰子序列对应的概率，但是这回，我们不挑最大值了，而是把所有算出来的概率相加，得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列（马尔可夫链）。 我们会应应用个和前一个问题类似的解法，只不过前一个问题关心的是概率最大值，这个问题关心的是概率之和。解决这个问题的算法叫做前向算法（forward algorithm）。
首先，如果我们只掷一次骰子：
看到结果为1.产生这个结果的总概率可以按照如下计算，总概率为0.18：
把这个情况拓展，我们掷两次骰子：
看到结果为1，6.产生这个结果的总概率可以按照如下计算，总概率为0.05：
继续拓展，我们掷三次骰子：
看到结果为1，6，3.产生这个结果的总概率可以按照如下计算，总概率为0.03：
同样的，我们一步一步的算，有多长算多长，再长的马尔可夫链总能算出来的。
同同样的方法，也可以算出不正常的六面骰和另外两个正常骰子掷出这段序列的概率，然后我们比较一下这两个概率大小，就能知道你的骰子是不是被人换了。
首先我们来看看什么样的问题解决可以用HMM模型。使用HMM模型时我们的问题一般有这两个特征：
１）我们的问题是基于序列的，比如时间序列，或者状态序列。
２）我们的问题中有两类数据，
一类序列数据是可以观测到的，即观测序列；
而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。
有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。
从这些例子中，我们可以发现，HMM模型可以无处不在。但是上面的描述还不精确，下面我们用精确的数学符号来表述我们的HMM模型。
对于HMM模型，首先我们假设Q是所有可能的隐藏状态的集合，V是所有可能的观测状态的集合，即：
其中，N是可能的隐藏状态数，M是所有的可能的观察状态数。
对于一个长度为T的序列，i是对应的状态序列, O是对应的观察序列，即：
其中，任意一个隐藏状态it ∈ Q, 任意一个观察状态ot ∈ V
HMM模型做了两个很重要的假设如下：
1） 其次马尔科夫链假设
即任意时刻的隐藏状态只依赖于它前一个隐藏状态。
当然这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个
或者是前三个。
但是这样假设的好处就是模型简单，便于求解。
如果在时刻t的隐藏状态是i = q ,在时刻t + 1的隐藏状态是i = q , 则从时刻t到时刻t+1的HMM状态转移概率
a = P(i = q ∣i = q )
这样a 可以组成⻢尔科夫链的状态转移矩阵A:
A=[aij]N×N
2） 观测独立性假设。
即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。
b (k) = P(o = v ∣i = q )
这样b (k)可以组成观测状态生成的概率矩阵B:
B = [b (k)N×M
除此之外，我们需要一组在时刻t=1的隐藏状态概率分布Π :
Π = [Π ]N
其中Π = P(i = q )
一个HMM模型，可以由隐藏状态初始概率分布Π , 状态转移概率矩阵A和观测状态概率矩阵B决定。
Π ,A决定状态序列，B决定观测序列。
因此，HMM模型可以由一个三元组λ 表示如下：
λ = (A, B, Π) = (状态序列，观测序列，初始状态概率分布)
下面我们用一个简单的实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型。
例子来源于李航的《统计学习方法》。
假设我们有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里球的数量分别是：
按照下面的方法从盒子里抽球，开始的时候，
以这个概率抽一次球后，将球放回。
然后从当前盒子转移到下面个盒子进行抽球。规则是：
如此下去，直到重复三次，得到一个球的颜色的观测序列:
O={红，⽩，红}
注意在这个过程中，观察者只能看到球的颜色序列，却不能看到球是从哪个盒子里取出的。
那么按照我们前面HMM模型的定义，我们的观察状态集合是:
我们的隐藏状态集合是：
Q={盒⼦1，盒⼦2，盒⼦3}，N=3
而观察序列和状态序列的长度为3. 初始状态分布Π为：
状态转移概率分布A矩阵为：
观测状态概率B矩阵为：
从上面的例子，我们也可以抽象出HMM观测序列生成的过程。
生成的过程如下：
1）根据初始状态概率分布Π生隐藏状态i
2) for t from 1 to T
所有的o 一起形成观测序列O = o , o , ...or
HMM模型一共有三个经典的问题需要解决：
1）评估观察序列概率 —— 前向后向的概率计算
2）预测问题，也称为解码问题 ——维特比（Viterbi）算法
3）模型参数学习问题 —— 鲍姆-韦尔奇（Baum-Welch）算法(状态未知) ，这是一个学习问题
接下来的三节，我们将基于这个三个问题展开讨论
首先我们回顾下HMM模型的问题一。这个问题是这样的。
我们已知HMM模型的参数λ = (A, B, Π)。
其中A是隐藏状态转移概率的矩阵，
B是观测状态生成概率的矩阵，
Π 是隐藏状态的初始概率分布。
同时我们也已经得到了观测序列O = {o1, o2, ...oT },
现在我们要求观测序列O在模型λ 下出现的条件概率P(O∣λ)。
乍一看，这个问题很简单。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。
我们可以列举出所有可能出现的长度为T的隐藏序列i = {i1,i2, ...,iT },分别求出这些隐藏序列与观测序列
O = {o1, o2, ...oT }的联合概率分布P(O,i∣λ)，这样我们就可以很容易的求出边缘分布P(O∣λ)了。
具体暴力求解的求解法是这样的：
首先，任意隐藏序列i = i1,i2, ...,iT出现的概率是：
P(i∣λ) = Πi1ai1,i2ai2,i3...aiT−1,iT
对于固定的状态序列i = i1,i2, ...,iT，我们要求的观察序列O = o1, o2, ...oT 出现的概率是：
P(O∣i, λ) = bi1(o1)bi2(o2)...biT (oT )
则O和i联合出现的概率是：
然后求边缘概率分布，即可得到观测序列O在模型λ 下出现的条件概率P(O|λ )P(O|λ )：
虽然上述方法有效，但是如果我们的隐藏状态数N非常多的那就麻烦了，此时我们预测状态有N 种组合，算法的时间复杂度是O(T N )阶的。
因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。
前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。
前向后向算法是前向算法和后向算法的统称，这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。
4.2.1 流程梳理
前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。
4.2.2 算法总结
1) 计算时刻1的各个隐藏状态前向概率
2) 递推时刻2,3,... ...T时刻的前向概率：
从递推公式可以看出，我们的算法时间复杂度是O(T N2)，比暴力解法的时间复杂度O(T NT)少了几个数量级。
这里我们用前面盒子与球的例子来显示前向概率的计算。 我们的观察集合是：
我们的状态集合是：
而观察序列和状态序列的长度为3.
初始状态分布为：
状态转移概率分布矩阵为：
观测状态概率矩阵为：
球的颜色的观测序列:
按照我们上一节的前向算法。首先计算时刻1三个状态的前向概率：
时刻1是红色球，
隐藏状态是盒子1的概率为：
隐藏状态是盒子2的概率为：
隐藏状态是盒子3的概率为：
现在我们可以开始递推了，首先递推时刻2三个状态的前向概率：
时刻2是白色球，
隐藏状态是盒子1的概率为：
隐藏状态是盒子2的概率为：
隐藏状态是盒子3的概率为：
继续递推，现在我们递推时刻3三个状态的前向概率：
时刻3是红色球，
隐藏状态是盒子1的概率为：
隐藏状态是盒子2的概率为：
隐藏状态是盒子3的概率为：
最终我们求出观测序列:O=红，白，红的概率为：
4.4.1 流程梳理
熟悉了用前向算法求HMM观测序列的概率，现在我们再来看看怎么用后向算法求HMM观测序列的概率。
后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”。
4.4.2 后向算法流程
以下是后向算法的流程,注意下和前向算法的相同点和不同点：
初始化时刻T的各个隐藏状态后向概率：
递推时刻T−1,T−2,...1时刻的后向概率：
此时我们的算法时间复杂度仍然是O(T N 2 )
在本篇我们会讨论维特比算法解码隐藏状态序列，即给定模型和观测序列，求给定观测序列条件下，最可能出现的对应的隐藏状态序列。
HMM模型的解码问题最常用的算法是维特比算法，当然也有其他的算法可以求解这个问题。
同时维特比算法是一个通用的求序列最短路径的动态规划算法，也可以用于很多其他问题。
近似算法很简单，但是却不能保证预测的状态序列整体是最可能的状态序列，因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。
而维特比算法可以将HMM的状态序列作为一个整体来考虑，避免近似算法的问题，下面我们来看看维特比算法进行HMM解码的方法。
维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法。
既然是动态规划算法，那么就需要找到合适的局部状态，以及局部状态的递推公式。在HMM中，维特比算法定义了两个局部状态用于递推。
1) 第1个局部状态是在时刻t隐藏状态为i所有可能的状态转移路径i ,i , ...i 中的概率最大值。
2) 第二个局部状态由第一个局部状态递推得到。
有了这两个局部状态，我们就可以从时刻0一直递推到时刻T，然后利用ψ (i)记录的前一个最可能的状态节点回溯，直到找到最优的隐藏状态序列。
现在我们来总结下维特比算法的流程：
流程如下：
1）初始化局部状态：
2) 进行动态规划递推时刻t = 2, 3, ...T时刻的局部状态：
3) 计算时刻T最大的δ (i),即为最可能隐藏状态序列出现的概率。计算时刻T最大的ψ (i),即为时刻T最可能的隐藏状态。
4) 利用局部状态ψ (i)开始回溯。对于t = T − 1, T − 2, ..., 1:
最终得到最有可能的隐藏状态序列I = i ,i , ...i
下面我们仍然用盒子与球的例子来看看HMM维特比算法求解。 我们的观察集合是：
我们的状态集合是：
而观察序列和状态序列的长度为3.
初始状态分布为：
状态转移概率分布矩阵为：
观测状态概率矩阵为：
球的颜色的观测序列:
按照我们前面的维特比算法，首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态，此时观测状态为1：
现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态，此时观测状态为2：
δ (1) = max [δ (j)a ]b (o ) = max [0.1 × 0.5, 0.16 × 0.3, 0.28 × 0.2] × 0.5 = 0.028
Ψ (1) = 3
δ (2) = max [δ (j)a ]b (o ) = max [0.1 × 0.2, 0.16 × 0.5, 0.28 × 0.3] × 0.6 = 0.0504
Ψ (2) = 3
δ (3) = max [δ (j)a ]b (o ) = max [0.1 × 0.3, 0.16 × 0.2, 0.28 × 0.5] × 0.3 = 0.042
Ψ (3) = 3
继续递推三个隐藏状态在时刻3时对应的各自两个局部状态，此时观测状态为1：
δ (1) = max [δ (j)a ]b (o ) = max [0.028 × 0.5, 0.0504 × 0.3, 0.042 × 0.2] × 0.5 = 0.00756
Ψ (1) = 2
δ (2) = max [δ (j)a ]b (o ) = max [0.028 × 0.2, 0.0504 × 0.5, 0.042 × 0.3] × 0.4 = 0.01008
Ψ (2) = 2
δ (3) = max [δ (j)a ]b (o ) = max [0.028 × 0.3, 0.0504 × 0.2, 0.042 × 0.5] × 0.7 = 0.0147
Ψ (3) = 3
此时已经到最后的时刻，我们开始准备回溯。此时最大概率为δ (3),从而得到i = 3
由于ψ (3) = 3,所以i = 3, 而又由于ψ (3) = 3,所以i = 3。从而得到最终的最可能的隐藏状态序列为：(3,3,3)。
模型参数学习问题 —— 鲍姆-韦尔奇（Baum-Welch）算法(状态未知)
鲍姆-韦尔奇算法原理既然使用的就是EM算法的原理，
接着不停的进行EM迭代，直到模型参数的值收敛为止。
首先来看看E步，当前模型参数为λ, 联合分布P(O, I∣λ)基于条件概率P(I∣O,λ)的期望表达式为：
L(λ, λ) = ∑P(I∣O, λ)logP(O, I∣λ)
在M步，我们极大化上式，然后得到更新后的模型参数如下：
λ = arg maxλ ∑P(I∣O, λ)logP(O, I∣λ)
通过不断的E步和M步的迭代，直到λ收敛。
官网链接：hmmlearn 0.2.8.post18+g29072a4 documentation
pip3 install hmmlearnhmmlearn实现了三种HMM模型类，按照观测状态是连续状态还是离散状态，可以分为两类。
GaussianHMM和GMMHMM是连续观测状态的HMM模型，而MultinomialHMM是离散观测状态的模型，也是我们在HMM原理系列篇里面使用的模型。
在这里主要介绍我们前面一直讲的关于离散状态的MultinomialHMM模型。
对于MultinomialHMM的模型，使用比较简单，里面有几个常用的参数：
下面我们用我们在前面讲的关于球的那个例子使用MultinomialHMM跑一遍。
import numpy as np
from hmmlearn import hmm# 设定隐藏状态的集合
states = ["box 1", "box 2", "box3"]
n_states = len(states)
# 设定观察状态的集合
observations = ["red", "white"]
n_observations = len(observations)
# 设定初始状态分布
start_probability = np.array([0.2, 0.4, 0.4])
# 设定状态转移概率分布矩阵
transition_probability = np.array([
[0.5, 0.2, 0.3],
[0.3, 0.5, 0.2],
[0.2, 0.3, 0.5]
])
# 设定观测状态概率矩阵
emission_probability = np.array([
[0.5, 0.5],
[0.4, 0.6],
[0.7, 0.3]
])# 设定模型参数
model = hmm.MultinomialHMM(n_components=n_states)
model.startprob_=start_probability # 初始状态分布
model.transmat_=transition_probability # 状态转移概率分布矩阵
model.emissionprob_=emission_probability # 观测状态概率矩阵现在我们来跑一跑HMM问题三维特比算法的解码过程，使用和之前一样的观测序列来解码，代码如下：
seen = np.array([[0,1,0]]).T # 设定观测序列
box = model.predict(seen)
print("球的观测顺序为：\n", ", ".join(map(lambda x: observations[x], seen.flatten())))
# 注意：需要使⽤flatten⽅法，把seen从⼆维变成⼀维
print("最可能的隐藏状态序列为:\n"， ", ".join(map(lambda x: states[x], box)))我们再来看看求HMM问题一的观测序列的概率的问题，代码如下：
print(model.score(seen))
# 输出结果是：-2.03854530992要注意的是score函数返回的是以自然对数为底的对数概率值，我们在HMM问题一中手动计算的结果是未取对数的原始概率是0.13022。对比一下：
import math
math.exp(-2.038545309915233)
# ln0.13022≈−2.0385
# 输出结果是：0.13021800000000003