机器学习之概率图模型浅析
根据《机器学习》、《统计学习方法》、《统计自然语言处理》，关于HMM，CRF等演算法实现先跳过，等用到再补。
其中的一些内容，例如HMM，CRF在其他的文章中都有拓展，在专栏里找一下就能找到。
机器学习最重要的任务，是根据一些己观察到的证据(例如训练样本)来对感兴趣的未知变数(例如类别标记)进行估计和推测。
概率图模型就是概率图模型(probabilisticgraphicalmodel)是一类用图来表达变数相关关系的概率模型.它以图为表示工具，最常见的是用一个结点表示一个或一组随机变数，结点之间的边表示变数间的概率相关关系，即"变数关系图"。
第一类是使用有向无环图表示变数间的依赖关系，称为有向图模型或贝叶斯网(Bayesiannetwork);第二类是使用无向图表示变数间的相关关系，称为无向图模型或马尔可夫网(Markovnetwork)
生成式模型与称判别式模型
判别式模型（DiscriminativeModel）是直接学习决策函数f(x)或者直接求得条件概率分布p(y|x;θ)。常见的判别式模型有线性回归模型、支持向量机SVM等。
对条件分布进行建模。
生成式模型（GenerativeModel）由数据学习联合概率分布p(x,y)，然后通过贝叶斯公式来求得p(yi|x)，然后选取使得p(yi|x)最大的yi。例如朴素贝叶斯模型和隐马尔科夫模型。
对联合分布进行建模。
自然语言处理中概率图模型的演变
横向：由点到线（序列结构）、到面（图结构）。
纵向：在一定条件下生成式模型（genmodel）转变为判别式模型（discriminativemodel）
贝叶斯网路
形式上，一个贝叶斯网路就是一个有向无环图（directedacyclicgraph,DAG），结点表示随机变数。结点之间的有向边表示条件依存关系，箭头指向的结点
依存于箭头发出的结点（父结点）。
三个事件的联合概率函数为：
P（H，S，N）＝P（H|S，N）×P（S|N）×P（N）马尔可夫模型
一个交通信号灯的颜色转换，灯的颜色变化序列依次是红色-黄色-绿色-红色，这就是一个确定性模式下的状态序列。例如天气的变化，晴朗-多云-雨天的状态序列是非确定性模式下的一个状态序列。
像交通信号灯一样，某一个状态只由前一个状态决定，这就是一个一阶马尔可夫模型。像天气这样，天气状态间的转移仅依赖于前n天天气的状态，即状态间的转移仅依赖于前n个状态的过程。这个过程就称为n阶马尔科夫模型。
不通俗的讲，马尔可夫模型（Markovmodel）描述了一类重要的随机过程，随机过程又称随机函数，是随时间而随机变化的过程。
如果在特定条件下，系统在时间t的状态只与其在时间t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链（Markovchain）。
系统在时间t-1的状态为si的情况下，时间t的状态为sj的概率：P（qt＝sj|qt－1＝si）=aij，且：
则该随机过程就是马尔可夫模型。
有N个状态的一阶马尔可夫过程有N^2次状态转移，其N^2个状态转移概率可以表示成一个状态转移矩阵。
根据状态转移方程，可以计算得到该状态序列的概率，例如天气的状态转移矩阵：
那么以天气为例，确定一个一阶马尔可夫模型需要：
1. pi向量：定义系统初始化时每一个状态的概率
2. 状态转移矩阵：给定前一天天气情况下的当前天气概率。
隐马尔可夫模型
在马尔可夫模型中，每个状态代表了一个可观察的事件，所以，马尔可夫模型有时又称作可视马尔可夫模型（visibleMarkovmodel，VMM），这在某种程度上限制了模型的适应性。
对于盲人来说也许不能够直接获取到天气的观察情况，但是他可以通过触摸树叶通过树叶的干燥程度判断天气的状态。于是天气就是一个隐藏的状态，树叶的干燥程度是一个可观察的状态，于是我们就有了两组状态，一个是不可观察、隐藏的状态（天气），一个是可观察的状态（树叶），我们希望设计一种演算法，在不能够直接观察天气的情况下，通过树叶和马尔可夫假设来预测天气。
以此为例，一个一阶的马尔可夫过程描述：
在隐马尔可夫模型（HMM）中，我们不知道模型所经过的状态序列，只知道观察到的事件在某状态下的概率函数。因此，该模型是一个双重的随机过程，包括模型的状态转换和特定状态下可观察事件的随机。
上图中，Xi表示观测变数，yi表示状态变数。Xi是由yi决定的，并且t时刻的yt仅仅由t-n至t-1时刻的y决定。
一个隐马尔可夫模型需要确定以下三方面内容：λ=[π,A，B]
1. 初始状态概率π:模型在初始时刻各状态出现的概率，通常记为π=(π1，π2，...，πN)，πi表示模型的初始状态为Sí的概率.
2. 状态转移概率A:模型在各个状态间转换的概率，通常记为矩阵A[αij]N*N，其中αij=P(Yt+l=Sj|Yt=Si),
表示在任意时刻t，若状态为Si，则在下一时刻状态为Sj的概率.3. 输出观测概率B:模型根据当前状态获得各个观测值的概率通常记为矩阵
B=[bij]N*M，。其中，N是状态数量，M是观测值的数量，bij=P(Xt=Oj|Yt=Si),表示在任意时刻t，若状态为Si.，则观测值Oj被获取的概率.相对于马尔可夫模型，隐马尔可夫只是多了一个各状态的观测概率
给定隐马尔可夫模型λ=[A，B，π]，它按如下过程产生观测序列{X1,X2，...,Xn}:
(1) 设置t=1，并根据初始状态概率π选择初始状态Yl;
(2) 根据状态值和输出观测概率B选择观测变数取值Xt;
(3) 根据状态值和状态转移矩阵A转移模型状态，即确定Yt+1;
一旦一个系统可以作为HMM被描述，就可以用来解决三个基本问题。
1. 评估（Evaluation）
给定HMM，即λ=[π,A，B]，求某个观察序列的概率。
例如，给定一个天气的隐马尔可夫模型，包括第一天的天气，天气转移概率矩阵，特定天气下树叶的湿度概率分布。求第一天湿度为1，第二天湿度为2，第三天湿度为3的概率。
2. 解码（ Decoding）
给定HMM，即λ=[π,A，B]，以及某个观察序列，求得天气的序列。
例如，给定一个天气的隐马尔可夫模型，包括第一天的天气，天气转移概率矩阵，特定天气下树叶的湿度概率分布。并且已知第一天湿度为1，第二天湿度为2，第三天湿度为3。求得这三天的天气情况。
3. 学习（Learning）
给定一个观察序列，得到一个隐马尔可夫模型。
已知第一天湿度为1，第二天湿度为2，第三天湿度为3。求得一个天气的隐马尔可夫模型，包括第一天的天气，天气转移概率矩阵，特定天气下树叶的湿度概率分布。
可夫随机场MRF
马尔可夫随机场是典型的马尔可夫网，即一个无向图模型。
图中的节点表示变数，结点之间的边表示两个变数之间的依赖关系.马尔可夫随机场有一组势函数(potentialfunctions)，亦称"因子"(factor)，这是定义在变数子集上的非负实函数，主要用于定义概率分布函数。
若其中任意两结点间都有边连接，则称该结点子集为一个"团"(clique)（类似于一个全连通图）。「极大团」类似于一个属于全连通图的图的最大的子集。
在马尔可夫随机场中，多个变数之间的联合概率分布能基于团分解为多个因子的乘积?每个因子仅与一个团相关.具体米说，对于n个变数X={Xl，x2，...，xn}，所有团构成的集合为C，与团Q(shuyu)C对应的变数集合记为XQ，则联合概率P(X)定义为:
势函数的累乘相加得到Z，Z为规范化因子，是为了确保P（X）是被正确定义的概率。
条件随机场CRF
条件随机场(ConditionalRandomField，简称CRF)是一种判别式无向图模型.生成式模型是直接对联合分布进行建模，丽判别式模型则是对条件分布进行建模.前面介绍的隐马尔可夫模型和马尔可夫随机场都是生成式模型，而条件随机场则是判别式模型.
CRF的特点是假设输出随机变数构成马尔可夫随机场。
条件随机场试图对多个变数在给定观测值后的条件概率进行建模.具体来
说，若令X={Xl,X2,…,Xn}为观测序列，y={y1，y2，...,Yn}为与之相应的标记序列，则条件随机场的目标是构建条件概率模型P(y|X).马尔可夫性（pairwiseMarkovproperty）
成对马尔可夫性
设无向图G中的任意两个没有边连接的节点u、v，其他所有节点为O，成对马尔可夫性指：给定YO的条件下，Yu和Yv条件独立
局部马尔可夫性
全局马尔可夫性
令G=(V，E)表示结点与标记变数Y中元素一一对应的无向图，Yv表示与结点v对应的标记变数，n(v)表示结点v的邻接结点，若图G的每个变数Yv都满足马尔可夫性（即给定变数Yv,两个其他变数不是邻接变数，且他们各自独立），即
则(y，x)构成一个条件随机场.
推荐阅读：
