相信大家都看过上一节我讲得贝叶斯网络,都明白了概率图模型是怎样构造的,如果现在还没明白,请看我上一节的总结:贝叶斯网络
这一节我们重点来讲一下马尔可夫,正如题目所示,看了会一脸蒙蔽,好在我们会一点一点的来解释上面的概念,请大家按照顺序往下看就会完全弄明白了,这里我给一个通俗易懂的定义,后面我们再来一个个详解。
以下共分六点说明这些概念,分成条目只是方便边阅读边思考,这6点是依次递进的,不要跳跃着看。
马尔可夫过程(Markov process)是一类随机过程。它的原始模型马尔可夫链,由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性:在已知目前状态(现在)的条件下,它未来的演变(将来)不依赖于它以往的演变 (过去 )。例如森林中动物头数的变化构成——马尔可夫过程。在现实世界中,有很多过程都是马尔可夫过程,如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等,都可视为马尔可夫过程。
每个状态的转移只依赖于之前的n个状态,这个过程被称为1个n阶的模型,其中n是影响转移状态的数目。最简单的马尔可夫过程就是一阶过程,每一个状态的转移只依赖于其之前的那一个状态,这个也叫作马尔可夫性质。用数学表达式表示就是下面的样子:
假设这个模型的每个状态都只依赖于之前的状态,这个假设被称为马尔科夫假设,这个假设可以大大的简化这个问题。显然,这个假设可能是一个非常糟糕的假设,导致很多重要的信息都丢失了。
P(Xn+1∣X1=x1,X2=x2,...,Xn=xn)=P(Xn+1=x∣Xn=xn)P(X_{n+1}|X_1=x_1,X_2=x_2,...,X_n=x_n)=P(X_{n+1}=x|X_n=x_n)P(Xn+1∣X1=x1,X2=x2,...,Xn=xn)=P(Xn+1=x∣Xn=xn)
假设天气服从马尔可夫链:
从上面这幅图可以看出:
晴 | 阴 | |
---|---|---|
晴 | 0.9 | 0,1 |
阴 | 0.5 | 0.5 |
由上表我们可以得到马尔可夫链的状态转移矩阵:
因此,一阶马尔可夫过程定义了以下三个部分:
马尔可夫模型(Markov Model)是一种统计模型,广泛应用在语音识别,词性自动标注,音字转换,概率文法等各个自然语言处理等应用领域。经过长期发展,尤其是在语音识别中的成功应用,使它成为一种通用的统计工具。到目前为止,它一直被认为是实现快速精确的语音识别系统的最成功的方法。
在某些情况下马尔科夫过程不足以描述我们希望发现的模式。回到之前那个天气的例子,一个隐居的人可能不能直观的观察到天气的情况,但是有一些海藻。民间的传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合,一个可以观察到的状态集合(海藻的状态)和一个隐藏的状态(天气的状况)。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。
而这个算法就叫做隐马尔可夫模型(HMM)。
隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型,用来描述一个含有隐含未知参数的马尔可夫过程。它是结构最简单的动态贝叶斯网,这是一种著名的有向图模型,主要用于时序数据建模,在语音识别、自然语言处理等领域有广泛应用。
前两个问题是模式识别的问题:1) 根据隐马尔科夫模型得到一个可观察状态序列的概率(评价);2) 找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大(解码)。第三个问题就是根据一个可以观察到的状态序列集产生一个隐马尔科夫模型(学习)。
对应的三大问题解法:
下面我们以一个场景来说明这些问题的解法到底是什么?
小明现在有三天的假期,他为了打发时间,可以在每一天中选择三件事情来做,这三件事情分别是散步、购物、打扫卫生(对应着可观测序列),可是在生活中我们所做的决定一般都受到天气的影响,可能晴天的时候想要去购物或者散步,可能下雨天的时候不想出门,留在家里打扫卫生。而天气(晴天、下雨天)就属于隐藏状态,用一幅概率图来表示这一马尔可夫过程:
那么,我们提出三个问题,分别对应马尔可夫的三大问题:
下面我们就依据这个场景来一一解答这些问题。
遍历算法:
这个是最简单的算法了,假设第一天(T=1 时刻)是晴天,想要购物,那么就把图上的对应概率相乘就能够得到了。
第二天(T=2 时刻)要做的事情,在第一天的概率基础上乘上第二天的概率,依次类推,最终得到这三天(T=3 时刻)所要做的事情的概率值,这就是遍历算法,简单而又粗暴。但问题是用遍历算法的复杂度会随着观测序列和隐藏状态的增加而成指数级增长。
复杂度为:2TNT2TN^T2TNT
于是就有了第二种算法
前向算法:
细心的读者已经发现了,第二步中要求的概率可以在第一步的基础上进行,同样的,第三步也会依赖于第二步的计算结果。那么这样做就能够节省很多计算环节,类似于动态规划。
这种算法的复杂度为:N2TN^2TN2T
后向算法
跟前向算法相反,我们知道总的概率肯定是1,那么B_t=1,也就是最后一个时刻的概率合为1,先计算前三天的各种可能的概率,在计算前两天、前一天的数据,跟前向算法相反的计算路径。
维特比算法(Viterbi)
说起安德鲁·维特比(Andrew Viterbi),通信行业之外的人可能知道他的并不多,不过通信行业的从业者大多知道以他的名字命名的维特比算法(ViterbiAlgorithm)。维特比算法是现代数字通信中最常用的算法,同时也是很多自然语言处理采用的解码算法。可以毫不夸张地讲,维特比是对我们今天的生活影响力最大的科学家之一,因为基于CDMA的3G移动通信标准主要就是他和厄文·雅各布(Irwin Mark Jacobs)创办的高通公司(Qualcomm)制定的,并且高通公司在4G时代依然引领移动通信的发展。
维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图—篱笆网络(Lattice)的有向图最短路径问题而提出的。它之所以重要,是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码,包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
维特比算法一般用于模式识别,通过观测数据来反推出隐藏状态,下面一步步讲解这个算法。
因为是要根据观测数据来反推,所以这里要进行一个假设,**假设这三天所做的行为分别是:散步、购物、打扫卫生,**那么我们要求的是这三天的天气(路径)分别是什么。
对应路径为:
对应路径为:
以上是比较通俗易懂的维特比算法,如果需要严谨表述,可以查看《数学之美》这本书的第26章,讲的就是维特比算法,很详细。附:《数学之美》下载地址,点击下载
鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法),详细讲解请见:监督学习方法与Baum-Welch算法
wikipedia上是这样定义因子图的:将一个具有多变量的全局函数因子分解,得到几个局部函数的乘积,以此为基础得到的一个双向图叫做因子图(Factor Graph)。
通俗来讲,所谓因子图就是对函数进行因子分解得到的一种概率图。一般内含两种节点:变量节点和函数节点。我们知道,一个全局函数通过因式分解能够分解为多个局部函数的乘积,这些局部函数和对应的变量关系就体现在因子图上。
举个例子,现在有一个全局函数,其因式分解方程为:
g(x1,x2,x3,x4,x5)=fA(x1)fB(x2)fC(x1,x2,x3)fD(x3,x4)fE(x3,x5)g(x_1,x_2,x_3,x_4,x_5)=f_A(x_1)f_B(x_2)f_C(x1,x2,x3)f_D(x_3,x_4)f_E(x_3,x_5)g(x1,x2,x3,x4,x5)=fA(x1)fB(x2)fC(x1,x2,x3)fD(x3,x4)fE(x3,x5)
其中fA,fB,fC,fD,fE为各函数,表示变量之间的关系,可以是条件概率也可以是其他关系。其对应的因子图为:
我们已经知道,有向图模型,又称作贝叶斯网络,但在有些情况下,强制对某些结点之间的边增加方向是不合适的。使用没有方向的无向边,形成了无向图模型(Undirected Graphical Model,UGM), 又被称为马尔可夫随机场或者马尔可夫网络(Markov Random Field, MRF or Markov network)。
设X=(X1,X2…Xn)和Y=(Y1,Y2…Ym)都是联合随机变量,若随机变量Y构成一个无向图 G=(V,E)表示的马尔可夫随机场(MRF),则条件概率分布P(Y|X)称为条件随机场(Conditional Random Field, 简称CRF,后续新的博客中可能会阐述CRF)。如下图所示,便是一个线性链条件随机场的无向图模型:
在概率图中,求某个变量的边缘分布是常见的问题。这问题有很多求解方法,其中之一就是把贝叶斯网络或马尔可夫随机场转换成因子图,然后用sum-product算法求解。换言之,基于因子图可以用sum-product 算法高效的求各个变量的边缘分布。
详细的sum-product算法过程,请查看博文:从贝叶斯方法谈到贝叶斯网络
一个通俗的例子
假设你有许多小明同学一天内不同时段的照片,从小明提裤子起床到脱裤子睡觉各个时间段都有(小明是照片控!)。现在的任务是对这些照片进行分类。比如有的照片是吃饭,那就给它打上吃饭的标签;有的照片是跑步时拍的,那就打上跑步的标签;有的照片是开会时拍的,那就打上开会的标签。问题来了,你准备怎么干?
一个简单直观的办法就是,不管这些照片之间的时间顺序,想办法训练出一个多元分类器。就是用一些打好标签的照片作为训练数据,训练出一个模型,直接根据照片的特征来分类。例如,如果照片是早上6:00拍的,且画面是黑暗的,那就给它打上睡觉的标签;如果照片上有车,那就给它打上开车的标签。
乍一看可以!但实际上,由于我们忽略了这些照片之间的时间顺序这一重要信息,我们的分类器会有缺陷的。举个例子,假如有一张小明闭着嘴的照片,怎么分类?显然难以直接判断,需要参考闭嘴之前的照片,如果之前的照片显示小明在吃饭,那这个闭嘴的照片很可能是小明在咀嚼食物准备下咽,可以给它打上吃饭的标签;如果之前的照片显示小明在唱歌,那这个闭嘴的照片很可能是小明唱歌瞬间的抓拍,可以给它打上唱歌的标签。
所以,为了让我们的分类器能够有更好的表现,在为一张照片分类时,我们必须将与它**相邻的照片的标签信息考虑进来。这——就是条件随机场(CRF)大显身手的地方!**这就有点类似于词性标注了,只不过把照片换成了句子而已,本质上是一样的。
如同马尔可夫随机场,条件随机场为具有无向的图模型,图中的顶点代表随机变量,顶点间的连线代表随机变量间的相依关系,在条件随机场中,随机变量Y 的分布为条件机率,给定的观察值则为随机变量 X。下图就是一个线性连条件随机场。
条件概率分布P(Y|X)称为条件随机场。
HMM词性标注,GitHub:点击进入
作者:@mantchs GitHub:https://github.com/NLP-LOVE/ML-NLP 欢迎大家加入讨论!共同完善此项目!群号:【541954936】