numpy复现马尔科夫链算法内含数据集

## 目录 - [1. 马尔可夫网络、马尔可夫模型、马尔可夫过程、贝叶斯网络的区别](#1-马尔可夫网络马尔可夫模型马尔可夫过程贝叶斯网络的区别) - [2. 马尔可夫模型](#2-马尔可夫模型) - [2.1 马尔可夫过程](#21-马尔可夫过程) - [3. 隐马尔可夫模型(HMM)](#3-隐马尔可夫模型hmm) - [3.1 隐马尔可夫三大问题](#31-隐马尔可夫三大问题) - [4. 马尔可夫网络](#4-马尔可夫网络) - [4.1 因子图](#41-因子图) - [4.2 马尔可夫网络](#42-马尔可夫网络) - [5. 条件随机场(CRF)](#5-条件随机场crf) - [6. EM算法、HMM、CRF的比较](#6-em算法hmmcrf的比较) - [7. 参考文献](#7-参考文献) - [8. 词性标注代码实现](https://github.com/NLP-LOVE/ML-NLP/blob/master/Machine%20Learning/5.2%20Markov/5.2%20HMM.ipynb) ## 1. 马尔可夫网络、马尔可夫模型、马尔可夫过程、贝叶斯网络的区别 相信大家都看过上一节我讲得贝叶斯网络，都明白了概率图模型是怎样构造的，如果现在还没明白，请看我上一节的总结：[贝叶斯网络](https://github.com/NLP-LOVE/ML-NLP/blob/master/Machine%20Learning/5.1%20Bayes%20Network/5.1%20Bayes%20Network.md) 这一节我们重点来讲一下马尔可夫，正如题目所示，看了会一脸蒙蔽，好在我们会一点一点的来解释上面的概念，请大家按照顺序往下看就会完全弄明白了，这里我给一个通俗易懂的定义，后面我们再来一个个详解。 以下共分六点说明这些概念，分成条目只是方便边阅读边思考，这6点是依次递进的，不要跳跃着看。 1. 将随机变量作为结点，若两个随机变量相关或者不独立，则将二者连接一条边；若给定若干随机变量，则形成一个有向图，即构成一个**网络**。 2. 如果该网络是有向无环图，则这个网络称为**贝叶斯网络。** 3. 如果这个图退化成线性链的方式，则得到**马尔可夫模型**；因为每个结点都是随机变量，将其看成各个时刻(或空间)的相关变化，以随机过程的视角，则可以看成是**马尔可夫过程**。 4. 若上述网络是无向的，则是无向图模型，又称**马尔可夫随机场或者马尔可夫网络**。 5. 如果在给定某些条件的前提下，研究这个马尔可夫随机场，则得到**条件随机场**。 6. 如果使用条件随机场解决标注问题，并且进一步将条件随机场中的网络拓扑变成线性的，则得到**线性链条件随机场**。 ## 2. 马尔可夫模型 ### 2.1 马尔可夫过程 马尔可夫过程（Markov process）是一类随机过程。它的原始模型马尔可夫链，由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性：在已知目前状态（现在）的条件下，它未来的演变（将来）不依赖于它以往的演变 (过去 )。例如森林中动物头数的变化构成——马尔可夫过程。在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。 每个状态的转移只依赖于之前的n个状态，这个过程被称为1个n阶的模型，其中n是影响转移状态的数目。最简单的马尔可夫过程就是一阶过程，**每一个状态的转移只依赖于其之前的那一个状态**，这个也叫作**马尔可夫性质**。用数学表达式表示就是下面的样子： 假设这个模型的每个状态都只依赖于之前的状态，这个假设被称为**马尔科夫假设**，这个假设可以大大的简化这个问题。显然，这个假设可能是一个非常糟糕的假设，导致很多重要的信息都丢失了。 =P(X_{n+1}=x|X_n=x_n)) 假设天气服从**马尔可夫链**：  从上面这幅图可以看出： - 假如今天是晴天，明天变成阴天的概率是0.1 - 假如今天是晴天，明天任然是晴天的概率是0.9，和上一条概率之和为1，这也符合真实生活的情况。 | | 晴 | 阴 | | ------ | ---- | ---- | | **晴** | 0.9 | 0,1 | | **阴** | 0.5 | 0.5 | 由上表我们可以得到马尔可夫链的**状态转移矩阵**：  因此，一阶马尔可夫过程定义了以下三个部分： - **状态**：晴天和阴天 - **初始向量**：定义系统在时间为0的时候的状态的概率 - **状态转移矩阵**：每种天气转换的概率 马尔可夫模型（Markov Model）是一种统计模型，广泛应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理等应用领域。经过长期发展，尤其是在语音识别中的成功应用，使它成为一种通用的统计工具。到目前为止，它一直被认为是实现快速精确的语音识别系统的最成功的方法。 ## 3. 隐马尔可夫模型(HMM) 在某些情况下马尔科夫过程不足以描述我们希望发现的模式。回到之前那个天气的例子，一个隐居的人可能不能直观的观察到天气的情况，但是有一些海藻。民间的传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合，一个可以观察到的状态集合（海藻的状态）和一个隐藏的状态（天气的状况）。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。 而这个算法就叫做**隐马尔可夫模型(HMM)**。  隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。**它是结构最简单的动态贝叶斯网，这是一种著名的有向图模型**，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。 ### 3.1 隐马尔可夫三大问题 1. 给定模型，如何有效计算产生观测序列的概率？换言之，如何评估模型与观测序列之间的匹配程度？ 2. 给定模型和观测序列，如何找到与此观测序列最匹配的状态序列？换言之，如何根据观测序列推断出隐藏的模型状态？ 3. 给定观测序列，如何调整模型参数使得该序列出现的概率最大？换言之，如何训练模型使其能最好地描述观测数据？ 前两个问题是模式识别的问题：1) 根据隐马尔科夫模型得到一个可观察状态序列的概率(**评价**)；2) 找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大(**解码**)。第三个问题就是根据一个可以观察到的状态序列集产生一个隐马尔科夫模型（**学习**）。 对应的三大问题解法： 1. 向前算法(Forward Algorithm)、向后算法(Backward Algorithm) 2. 维特比算法(Viterbi Algorithm) 3. 鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法) 下面我们以一个场景来说明这些问题的解法到底是什么？ 小明现在有三天的假期，他为了打发时间，可以在每一天中选择三件事情来做，这三件事情分别是散步、购物、打扫卫生(**对应着可观测序列**)，可是在生活中我们所做的决定一般都受到天气的影响，可能晴天的时候想要去购物或者散步，可能下雨天的时候不想出门，留在家里打扫卫生。而天气(晴天、下雨天)就属于隐藏状态，用一幅概率图来表示这一马尔可夫过程：  那么，我们提出三个问题，分别对应马尔可夫的三大问题： 1. 已知整个模型，我观测到连续三天做�