HMM隐马尔可夫模型

1.概率图模型：HMM（隐马）,MEMM（最大熵）,CRF（条件随机场）

概率：既然是一个图那么就是一个有圈有边的结构，圈代表随机向量，随机变量之间有边，边上有概率

既然是模型肯定可以求解：

有向图求解方式：p(Y)=p(x1)*p(x2|x1)....

无向图求解方式：

z(x)：代表归一化因子，作用就是为了把最终结果，缩放成一个概率

累乘：图中有几个最大团，就累乘多少次

势函数：指数函数：e的多少次方：特征函数

图模型：

1.有向图：有箭头，表示单向依赖关系

2.无向图：没有箭头，表示双向依赖关系

有向图：

1.静态贝叶斯网络

2.动态贝叶斯网络

无向图：

马尔可夫网络

团的概念：由几个节点所构成的闭环。（且节点之间相互连接）

最大团：最多有几个元素构成一个闭环并且相互连接（节点之间相互连接）

两个最大团：

x1,x3,x4;x2,x3,x4

2.齐次马尔可夫假设：

当前这个状态只依赖于前一个状态。相当于学习过的n-gram的n=2

3.生成式模型和判别式模型

学习的过程不一样

如何体现学习方式不同：建模不同，那么学习方式就不同。

生成式模型：可以直接生成模型来判别

生成式模型求得联合概率分布P(Y,X)，对于没有见过的X，你要求出X与不同标记之间的联合概率分布

判别式模型：只有规律，通过某些特征进行判别

1.对条件概率分布P(Y|X)建模

2.对所有的样本只构建一个模型，确认总体判别边界

3.观测到输入什么特征，就预测最可能的label

4.另外，判别式的优点是：对数据量要求没生成式的严格，速度也会快，小数据量下准确率也会好些。

4.序列标注：词性标注、命名实体识别、搜狗输入法

之前的学习解决四大类问题：回归,分类,聚类,降维

序列标注问题和分类问题的区别和联系

序列标注是一类特殊的分类任务，分类问题就不用细说了，标注问题相当于是分类问题的一个拓展，

分类是输入一个序列得到一个分类结果，而标注问题，输入的是一个序列，输出的也是一个序列，

标注问题输出的是一个向量，分类问题输出的是一个标签。

1.HMM（隐马尔可夫模型）：生成式 有向图模型

HMM:HMM是一个生成式有向图模型，该模型依赖于齐次马尔可夫假设和观测独立假设。

      齐 次马尔可夫性假设 ，即假设隐藏的马尔可夫链在任意时刻 t的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻t无关。

     观测独立性假设 ，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

HMM是机器学习算法

注意：机器学习的模型是做具体任务的。

        深度学习的模型是为机器学习服务的。（特征提取）

2.马尔可夫模型：

        描述一段时间，状态的转移变化。

        红灯-黄灯-绿灯-黄灯

        描述出来一段时间内，路口红绿邓状态变换

3.序列标注：词性标注、命名实体识别、搜狗输入法

4.n-v-adj-adv（马尔可夫链）（马尔可夫过程）

        描述一个句子词性的变换过程。

5.隐马尔可夫模型相比较马尔可夫模型多了些哪些东西？

        隐：隐含状态链

        

6.隐马结构：

    1.初始概率

    2.状态转移概率

    3.输出概率

    4.可观测序列

    5.隐含状态链

7.隐马要学习的参数：

    1.初始概率：[ 1/3，1/3，1/3]

    2.状态转移概率：

            [[1/3,1/3,1/3],

            [1/3,1/3,1/3],

            [1/3,1/3,1/3]]

    3.输出概率:

            [[1/4,1/4,1/4,1/4,0,0,0,0],

             [1/6,1/6,1/6,1/6,1/6,1/6,0,0],

             [1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8]]

8.隐马解决的三种问题：

    1.解码问题：给定观测序列（x）,给定模型参数（1，2，3），求最有可能的隐藏序列 max

    2.评估问题：给定观测序列（x）,给定模型参数（1，2，3），求观测序列x发生的概率 sum 

    3.参数学习问题：1.通过统计。如果数据有标签2.通过EM算法，数据没有标签。

    词性标注：属于解码问题

        用HMM，用HMM，用MEMM，用CRF都是使用解码问题。

思考题：

    1.评估问题（按照正常计算过于复杂），动态规划思想

    2.解码问题

HMM（隐马尔可夫模型）：

马尔可夫模型

在某段时间内，交通信号灯的颜色变化序列是：红色 - 绿色 - 红色。

在某个星期天气的变化状态序列：晴朗 - 多云 - 雨天。

像交通信号灯一样，某一个状态只由前一个状态决定，这就是一个一阶马尔可夫模型。而像天气这样，天气状态间的转移仅依赖于前 n 天天气的状态，即状态间的转移仅依赖于前 n 个状态的过程。这个过程就称为n 阶马尔科夫模型。

马尔可夫模型（Markovmodel）描述了一类重要的随机过程，随机过程又称随机函数，是随时间而随机变化的过程。

马尔可夫模型定义

存在一类重要的随机过程：如果一个系统有 N 个状态,,..,,.. 随着时间的推移，该系统从某一状态转移到另一状态。如果用表示系统在时间 t 的状态变量，那么 t 时刻的状态取值为(1<=j<=N)的概率取决于前 t-1 个时刻(1, 2, …, t-1)的状态，该概率为：

 

假设：如果在特定情况下，系统在时间 t 的状态只与其在时间 t-1 的状态相关，则该系统构成一个离散的一阶马尔可夫链：

 

隐马尔可夫模型(Hidden Markov model, 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中的一个。例如我们可能得到这么一串数字（掷骰子9次）：1 6 3 5 2 7 3 5 2

这串数字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：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。

 

A、B和C也被称为隐马尔科夫模型的三要素（参数）。

状态转移概率矩阵A与初始状态概率向量C确定了隐藏的马尔可夫链，生成不可观测的状态序列，观测概率矩阵B确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。

总结：此时在HMM中出现了：可观测状态链，隐含状态链，初始概率矩阵，转移概率和输出概率

HMM的流程：

隐马尔可夫模型由初始的概率分布、状态转移概率分布以及观测概率分布确定。具体的形式如下，这里设Q是所有可能的状态的集合，V是所有可能的观测的集合

其中，N是可能的状态数，M是可能观测的数。另外设I是长度为T的状态序列，O是对应的观测序列：

 

在马尔可夫链中，有几个矩阵变量，分别是状态转移概率矩阵A，观测概率矩阵B，以及初始状态概率向量C，其中状态转移概率矩阵A为：

 

是在时刻t处于状态qi的条件下在时刻t+1转移到状态qj的概率。

观测概率矩阵为：

是在时刻t处于状态qj的条件下生成观测vk的概率。

初始状态概率向量为：

 

Ci为时刻t=1处于状态qi的概率。

隐马尔可夫模型由初始状态概率向量C，状态转移概率矩阵A和观测概率矩阵B决定，C和A决定状态序列，B决定观测序列，因此隐马尔可夫模型可以用三元符号表示为：

A、B和C也被称为隐马尔科夫模型的三要素。

状态转移概率矩阵A与初始状态概率向量C确定了隐藏的马尔可夫链，生成不可观测的状态序列，观测概率矩阵B确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。

从定义中，可以发现隐马尔可夫模型作了两个基本假设：

(1) 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻t无关，

 

1.  观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

 

隐马尔可夫模型可以用于标注，这时状态对应着标记，标注问题是给定观测的序列预测其对应的标记序列。可以假设标注问题的数据是由隐马尔可夫模型生成的，这样可以利用该模型的学习与预测算法进行标注。

其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。

隐马尔科夫模型的三个基本问题：

(1) 评估观测序列概率：给定模型λ=(A,B,C)和观测序列O=(o1,o2,...,oT)，计算在该模型下观测序列O出现的概率P(O|λ)，这个问题求解需要用到前向后向算法，这个问题求解最简单。

(2) 模型参数学习问题：一直观测序列O=(o1,o2,...,oT)，估计模型λ=(A,B,C)参数，使得在该模型下观测序列概率P(O|λ)最大，即用极大似然估计的方法估计参数，这个问题求解极其困难。

(3) 预测问题，也称为解码的问题，已知模型λ=(A,B,C)也观测序列O=(o1,o2,...,oT)，求对给定观测序列条件概率P(I|O)最大的状态序列 I = (i1,i2,...,iT)，即给定观测序列，求最有可能的对应的状态序列，这个问题的求解需要用到基于动态规划的维特比算法，这个问题居中。

第一个问题求解：

注意上述的C = Π

这个问题是这样的。我们已知HMM模型的参数λ=(A,B,C)。其中A是隐藏状态转移概率的矩阵，B是观测状态生成概率的矩阵， C是隐藏状态的初始概率分布。同时我们也已经得到了观测序列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}出现的概率是：

 

对于固定的状态序列I={i1,i2,...,iT}，我们要求的观察序列O={o1,o2,...oT}出现的概率是：

 

则O和I联合出现的概率是：

 

然后求边缘概率分布，即可得到观测序列O在模型λ下出现的条件概率P(O|λ)：

 

虽然上述方法有效，但是如果我们的隐藏状态数N非常多的那就麻烦了，此时我们预测状态有NT种组合，算法的时间复杂度是阶的。因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。

 

前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。

2. 用前向算法求HMM观测序列的概率

前向后向算法是前向算法和后向算法的统称，这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。

前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。

在前向算法中，通过加入一个定义“前向概率”来定义动态规划的这个局部状态。什么是前向概率呢, 其实定义很简单：定义时刻t时隐藏状态为qi, 观测状态的序列为o1,o2,...ot的概率为前向概率。记为：

αt(i)=P(o1,o2,...ot,qi=si | λ)既然是动态规划，我们就要递推了，现在我们假设我们已经找到了在时刻t时各个隐藏状态的前向概率，现在我们需要递推出时刻t+1时各个隐藏状态的前向概率。

注意：充分理解了αt(i)表示的含义就可以很轻松的理解前向算法。

我们把原来全局的所有的情况一一列出来计算，转变成了现在的一个一个的输出：

α1(i) 表示在第一时刻，隐藏状态为qt = Si，观测序列为O1的概率

α2(i) 表示在第二时刻，隐藏状态为qt = Si，观测序列为O2的概率

α3(i) 表示在第三时刻，隐藏状态为qt = Si，观测序列为O3的概率

...........

最终我们求解的就变成了：

P(O|λ) = α1(i) + α2(i) + α3(i) + 。。。。。。

如果我们可以高效的求解αt(i)，那么是不是也就意味着高效的求解了隐马的第一个问题，我们想一想α1(i)到α2(i)中间只乘以了一个aij的转移概率，也就是说t时刻有N种状态，而t+1时刻也有N种状态，同时序列长度为T，这个时候时间复杂度是不是就变成了

O（TN²）。

 

 

从上图可以看出，我们可以基于时刻t时各个隐藏状态的前向概率，再乘以对应的状态转移概率，即αt(j)aji就是在时刻t观测到o1,o2,...ot，并且时刻t隐藏状态qj,时刻t+1隐藏状态qi的概率。如果将想下面所有的线对应的概率求和，即就是在时刻t观测到o1,o2,...ot，并且时刻t+1隐藏状态qi的概率。继续一步，由于观测状态ot+1只依赖于t+1时刻隐藏状态qi, 这样就是在在时刻t+1观测到o1,o2,...ot，ot+1，并且时刻t+1隐藏状态qi的概率。而这个概率，恰恰就是时刻t+1对应的隐藏状态i的前向概率，这样我们得到了前向概率的递推关系式如下：

我们的动态规划从时刻1开始，到时刻T结束，由于αT(i)表示在时刻T观测序列为o1,o2,...oT，并且时刻T隐藏状态qi的概率，我们只要将所有隐藏状态对应的概率相加，即 就得到了在时刻T观测序列为o1,o2,...oT的概率。

下面总结下前向算法。

输入：HMM模型λ=(A,B,Π)，观测序列O=(o1,o2,...oT)

输出：观测序列概率P(O|λ)

（1) 计算时刻1的各个隐藏状态前向概率：

（2) 递推时刻2,3,...T时刻的前向概率：

 

计算最终结果：

 

从递推公式可以看出，我们的算法时间复杂度是，比暴力解法的时间复杂度少了几个数量级。

隐马尔可夫的第三类问题：求最优的隐藏序列

1. 也可以列出来所有的情况，然后找到概率最大的，但是问题仍然是时间复杂度太高
2. 使用维特比算法（Viterbi）

维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法

维特比算法之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。

下面通过一个例子来解释讲解一下维特比算法！

词性标注问题

dog chase mouse

我们就可以进行词性标注为：

 

其中nn为名词，vv为动词。通过上面例子，我们就很容易看出词性标注的任务。

那么我们来了一句话之后，比如我们的词性字典中有nn,vv,prp(代词)，我们怎么能够找到dog

chase mouse 所对应的词性标注呢，如果每一个单词有nn，vv，prp三种可能，那么将会有3*3*3=27种可能，我们如何去挑选呢？

如下图：

 

我们总共有27条路径，那么如何得到我们Dog chase mouse的最优路径呢？

我们至少可以遍历每一条路径，求出各自的概率值，然后挑选最大的即可，比如我们求第一条路径的时候，可以这么表示：

 

所求的路径对应如下图红色线条所示：

 

求第27条路径的时候，我们可以这么表示：

所求的路径对应如下图红色线条所示：

 

那么我们从上面可以知道，要求一个句子的最优词性标注，我们至少可以遍历所有的路径，然后挑选概率值最大的那条路径即可！

但是问题来了！

给定模型，求给定长度为T的观测序列(这里指的就是Dog Chase Mouse)的概率，直接计算法的思路是枚举所有的长度T（例子中是三个，Dog，Chase，Mouse总共三个单词）的状态序列，计算该状态序列与观测序列的联合概率（隐状态发射到观测），对所有的枚举项求和即可。

在状态种类为N(例子中就是三个，NN，VV, PRP)的情况下，一共有  种排列组合，每种组合计算联合概率的计算量为T，总的复杂度为  ，这并不可取。

 

维特比算法

好了，到现在为止，我们假定我们已经训练好了一个隐马尔可夫模型了（训练好的意思，也就是单词到词性的发射概率，词性与词性的转移概率都已经在训练数据中学习得到了），来了一句话，Dog Chase Mouse，我如何得到它的词性标注序列？

首先先上一个维特比算法流程图：