监督学习_CRF

[TOC]

一文理解条件随机场CRF
如何用简单易懂的例子解释条件随机场（CRF）模型？它和HMM有什么区别？
机器学习-白板推导系列(十七)-条件随机场CRF（Conditional Random Field）
机器学习之CRF条件随机场
【NLP】从隐马尔科夫到条件随机场
13张动图，彻底看懂马尔科夫链、PCA和条件概率

背景

系列相关

分类问题根据是否引入概率分为了硬分类和软分类
SVM(几何间隔)、PLA(感知机)、LDA(类间大, 类内小)
概率判别模型
Logistic Regression (对 $p(y|x)$ 建模，二分类)(多分类的话就是softmax) -> 都是最大熵模型(给定均值和方差，Gaussian Dist熵最大，做分类时可以看成对数线性模型)
MEMM(打破了HMM的观测独立假设，但会引起Label bias Problem，原因是局部归一化引起的)
CRF的提出就是为了解决MEMM的标注偏差问题(变成了无向图, 也就是全局归一化 )
概率生成模型
Naive Bayesian(朴素贝叶斯二分类转序列的时候就是HMM，对 $p(x,y)$ 建模)
$p(x|y=1/0)=\sum_{i=1}^{p}{p(x_i|y=0/1)}$
Gaussian Mixture Model(加入时间的话就是HMM)
Hidden Markor Model
1)齐次Markor 2)观测独立

HMM

$\lambda = (\pi,A,B)$
1)齐次Markor(链条的长度为1 给定3的时候 4和2条件独立)
齐次是1-4的的转移概率是相同的
$p(y_t|y_{1:t-1},x_{1:t-1})=p(y_t|y_{t-1})$
2)观测独立假设
$p(x_t|y_{1:t},x_{1:t-1})=p(x_t|y_t)$
建模对象: $P(X,Y|\lambda)$
$P(X,Y|\lambda)=\prod_{t=1}^{T}{P(x_t,y_t|\lambda)}=\prod_{t=1}^{T}{P(y_t|y_{t-1},\lambda)}P(x_t|y_t,\lambda)$
NB->HMM(观测独立假设不合理，例子垃圾邮件分类，应该和每个单词都有关系)

MEMM

建模对象 $P(Y|X,\lambda)$
$P(Y|X,\lambda)=\prod_{t=1}^{T}p(y_t|t_{t-1},x_{1:t},\lambda)$
打破了观测独立假设

CRF

马尔科夫性

无向图随机变量之间满足三种性质
成对马尔科夫性
设 $u$ 和 $v$ 是无向图 $G$ 中任意两个没有边连接的节点，节点 $u$ 和 $v$ 分别对应随机变量 $Y_u$ 和 $Y_v$ 。其他所有节点为 $O$ ，对应的随机变量是 $Y_o$ 。成对马尔可夫性是指给定随机变量组 $Y_o$ 的条件下随机变量 $Y_u$ 和 $Y_v$ 是条件独立的，即
$P(Y_u,Y_v|Y_o)=P(Y_u|Y_o)P(Y_v|Y_o)$
局部马尔科夫性
设 $v \in V$ 是无向图 $G$ 中任意一个节点， $W$ 是与 $v$ 有边连接的所有节点， $O$ 是 $v$ 、 $W$ 以外的其他所有节点。 $v$ 表示随机变量是 $Y_v$ ， $W$ 表示的随机变量组是 $Y_W$ ， $O$ 表示的随机变量组是 $Y_o$ 。局部马尔可夫性是指在给定随机变量组 $Y_W$ 的条件下随机变量 $Y_v$ 与随机变量组 $Y_o$ 是独立的，即
$P(Y_v,Y_o|Y_W)=P(Y_v|Y_W)P(Y_o|Y_W)$
全局成对马尔科夫性
设结点集 $A$ ， $B$ 在无向图 $G$ 中被结点集合 $C$ 分开的任意结点的集合，具体如下图所示
则在给定了集合C的条件下结点集合A和B之间是相互独立的，具体表达式如下
$P(Y_A,Y_B|Y_C)=P(Y_A|Y_C)P(Y_B|Y_C)$
仔细观察发现这三种性质实质上是等价的，成对马尔科夫性和局部马尔科夫性都可以看作是全局马尔科夫性的特殊形式。
那这三种性质提出来有什么用呢？
首先满足这三种性质的联合概率分布 $P(Y)$ 可以称为马尔科夫随机场或者概率无向图模型。
而对于马尔科夫随机场，可以将联合概率分布 $P(Y)$ 拆分成多个因子的乘积，这样就便于计算 $P(Y)$ 。

团和最大团

团、极大团、最大团

团(clique)就是一个无向图的完全子图，既然是完全图，当然每对顶点之间都必须要有边相连。
团：无向图的完全子图。完全图：完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
比如这里的{0、5}就是一个团，它就是原图的一个完全子图，并且结点之间连接，当然{0、4、5}，{1、2、4}同样也是团，团里面的结点都必须是互相连接的。还有许多的团并没有全部列举出来，比如{0、4}，{1、2}，{4、3}等等。
最大团就是就是结点数最多的极大团