概率模型与条件随机场

1、概率模型
机器学习中的非常多模型能够依据概率分布形式分为生成模型和判别模型，当中生成模型以输入输出的联合分布P(X,Y)为基础建模。如朴素贝叶斯、隐马尔可夫模型。判别模型以条件概率分布P(Y|X)为基础建模，如最大熵模型、条件随机场等。这几个模型之间有一定的关系，它们的关系例如以下：

当中，NB表示朴素贝叶斯。ME表示最大熵。HMM表示隐马尔科夫，CRF表示条件随机场。joint联合分布。conditional条件分布。single class输出单一类别。sequence输出序列。比如。朴素贝叶斯将输出y扩展成序列(y1,y2,...,yn)。就能够以此为基础构造HMM；在满足输入条件下的HMM能够扩展成CRF。

这里面，朴素贝叶斯如果最强 ，由于它要求全部输入特征之间条件独立。如P(y|x1,x2,...,xn)=∏i=1nP(y|xi)；这是一种为计算方便而做的近似如果。然而现实中基本不会有模型符合输入特征间的独立，因此以朴素贝叶斯建模通常会有精度损失。
隐马尔科夫模型进了一步，它考虑一定的变量相关性，如马尔科夫如果状态序列中，当前状态仅仅与其前一个状态有关。如：

P(X,Y)=∏i=0nP(yi|yi−1P(xi|yi)
可是HMM仅仅考虑了状态之间的邻接关系，没有考虑观測序列间的关系，条件随机场刚好弥补了这个缺陷。

所以条件随机场是一个相对照较完好的模型，但代价是计算复杂性的提高。

2、概率图模型
上面讲到的概率模型能够用图的形式表示出来，称为概率图模型。概率图模型用图中结点表示随机变量，结点之间的边表示变量间的概率相关关系。

在概率图中。两结点没有边相连，说明两节点是条件独立的，比方P(a,b|c)=P(a|c)⋅P(b|c)。

在概率图中，结点间全连接是不包括不论什么概率分布信息的，所以我们更关注的是哪些边是缺失的，这些缺失的边表示边连接的结点条件独立。

下图中的两个图是概率图的两种表示形式，一个是独立图，一个是因子图。通过条件独立的条件，能够将一个复杂的概率分布分解成简单的概率分布乘积，例如以下图中（a）,联合概率分布P(x1,x2,y)=P(x1)⋅P(x2)⋅P(y|x1,x2)。
若定义因子。也称势函数Ψs为概率分布的分解因子。对随意概率图G=（V,E）,有：

p(V)=∏sΨs(Vs)

当中，s表示随机变量构成的集合，Vs表示该集合中包括的变量。

则能够将P(x1,x2,y)写成P(x1,x2,y)=Ψ1⋅Ψ2⋅Ψ3。这里的Ψi分别与独立图中的概率相应。

概率图模型可大致分为两类：一类是有向图模型，表示变量间的依赖关系，也称为贝叶斯网。一类是无向图模型。表示变量间的相关关系。也称为马尔科夫网或马尔科夫随机场。
2.1 有向图模型
在有向图中，边表示了变量之间的一种依赖关系。联合分布概率能够写作是全部变量在在父节点条件下的概率乘积：

P(V)=∏i=1KP(vk|vnk)

例如以下图所看到的的隐马尔可夫有向图，联合概率能够写作：

P(x1,x2,x3,y1,y2,y3)=Ψ1(y1)⋅Ψ2(x1,y1)⋅Ψ3(x2,y2)⋅Ψ4(x3,y3)⋅Ψ5(y1,y2)⋅Ψ6(y2,y3)

2.2 无向图模型
在无向图模型中，有个团和最大团的概念。表示了变量之间的关系。团的意思是一些随机变量结点构成的子集中，两两结点都有边相连，例如以下图中(1,2)、（1,2,5）等；最大团表示结点构成的团中再加入不论什么一个新结点后都不会构成团。如（1,4,5）。在一些线性链结构的无向图。如线性链条件随机场中，最大团仅仅考虑(yj−1,yj,x)。

像有向图的分解一样，无向图也能够分解，无向图是基于最大团进行分解，例如以下：

P(V)=1Z∏C∈CΨC(VC)

当中每一个最大团相应一个势函数ΨC。是不是跟最大熵模型的形式非常类似？由于最大熵模型也是一个无向图模型。像在最大熵模型中一样。Z是一个归一化因子，例如以下：

Z=∑V∏C∈CΨC(VC)

一般，势函数要求严格非负。所以在使用中会选择指数函数作为势函数。例如以下图的一个最大熵模型，能够写作：

P(y|x)=1Zλ(x)eλ1f1⋅eλ2f2⋅eλ3f3

有向图与无向图的一个主要差别在于概率分布的分解不同，在概率有向图中，分解因子是条件概率分布。在无向图中，分解因子能够是随意函数。无向图不须要说明变量间是怎样关联的，而是将在一个团中的变量作为一个总体来看。

**3、条件随机场**
在前面，我们说能够把隐马尔科夫模型看作是对贝叶斯模型的序列化。类似地，我们能够把条件随机场看作是对最大熵模型的序列化。

条件随机场并不要求线性序列，即它能够是随意结构的，通常我们使用较多的是线性链随机场。它能够看作是有条件的HMM(即加入了观測序列x的条件)。
条件随机场属于判别模型，即它要求出在观測序列x的条件下得到可能输出序列y的概率P(y|x)。
由上面的无向图分解公式

P(V)=1Z∏C∈CΨC(VC)

条件概率P(y|x)能够写作：

p(y|x)=p(x,y)p(x)
=p(x,y)∑y′p(y′,x)
=1Z∏C∈CΨC(xC,yC)1Z∑y′∏C∈CΨC(xC,yC)
=1Z(x)∏C∈CΨC(xC,yC)

当中，

Z(x)=∑y′∏C∈CΨC(xC,yC)

以下介绍一下经常使用的线性链条件随机场。
线性链CRFs是条件随机场中的一种特殊结构，与隐马尔科夫一样，输出形成一个线性序列，例如以下图：

依据上面的公式。其条件概率能够写作。

p(y|x)=1Z(x)∏j=1nΨj(x,y)

当中，n+1表示输出状态序列长度。n为势函数个数。
由图可知。状态yj与输入x和yj−1有关，特征函数能够写作：
f(yj−1,yj,x,j)
势函数：
Ψj(x,y)=exp(∑i=1mλifi(yj−1,yj,x,j))
进而，线性链CRFs的条件概率分布能够写作。

pλ(y|x)=1Zλ(x)exp(∑nj=1∑i=1mλifi(yj−1,yj,x,j))

当中。Zλ(x)是归一化因子，

Zλ(x)=∑y∈Yexp(∑nj=1∑i=1mλifi(yj−1,yj,x,j))