条件随机场

目录

• 条件随机场
  • • 概率无向图模型

条件随机场 (conditional random field, CRF) 是给定一组随机变量\(\mathbf{X}\)条件下，另一组随机变量\(\mathbf{Y}\)的条件概率分布模型。并假设随机变量\(\mathbf{Y}\)构成马尔可夫随机场（稍后介绍）。一般在NLP中，特别是在标注、分词、命名实体识别等中提到的CRF，是线性链条件随机场。

在介绍CRF之前，需要先了解下其依赖的理论基础。

概率无向图模型

概率无向图模型(probabilistic undirected graphical model), 又称为马尔可夫随机场(Markov random field， MRF), 是可由无向图表示的联合概率分布。这里面涉及概率图的多个概念，我们从图(graph)开始渐进介绍。

图是由节点（node）及连接结点的（edge）组成的集合，无向图是指边没有方向的图，用无向图表示的分布，也被称为马尔可夫网(Markov network )。概率图模型（probabilistic graphical model，PGM）则是由图表示的概率分布。其中的结点表示随机变量，边表示随机变量之间的依赖关系。要让PGM成为MRF还需要满足变量之间的一些马尔可夫独立性假设(Markov independent assumptions)，具体地是成对马尔可夫性，局部马尔可夫性，全局马尔可夫性。

成对（pairwise）马尔可夫性：指在无向图（如G）上没有边连接的两个结点(如，u,v分别对应随机变量，如\(Y_u,Y_v\)，下同)在其他所有结点(如用O表示)给定的情况下，相互独立, 具体地：

\[P(Y_u,Y_v|Y_O) = P(Y_u|Y_O)P(Y_v|Y_O) \]

局部（local）马尔可夫性: 设\(v\)是无向图G中的一个结点，\(W\)表示与\(v\)有边连接的所有的结点集合，\(W\)有时也称为马尔可夫毯（Markov Blanket)，在给定W， \(v\)与无向图上其所他所有结点(如用集\(O\)表示)，条件独立:

\[P(Y_v,Y_O|Y_W) = P(Y_v|Y_W)P(Y_O|Y_W) \]

图1. 在给定图中橙色结点时，绿色结点与黄色结点条件独立。

全局(global)马尔可夫性：设结点集合A，B在无向图G中被结点集合C分开，那么：

\[P(Y_A,Y_B|Y_C) = P(Y_A|Y_C)P(Y_B|Y_C) \]

图2. 在给定图中橙色结点时，绿色结点与黄色结点条件独立。

即在给定C的情况下，A、B两集合对应的随机变量条件独立。此时称结点集C在G中分离A与B，记为\(sep_{H_G}(A;B|C)\).

设联合概率分布\(P(Y)\)，由无向图G=(V,E)表示，如果\(P(Y)\)满足成对、局部与全局马尔可夫性，那么，就称此联合概率为概率无向图模型(probabilistic undirected graphical model), 又称为马尔可夫随机场(Markov random field， MRF)。

设X与Y是随机变量，\(P(Y|X)\)是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图G=（V，E）表示的马尔可夫随机场， 即:

\[P(Y_v|X,Y_w,w\neq v) = P(Y_v|X,Y_w,w\sim v) \]

对任意结点v成立，则称条件概率分布\(P(Y|X)\)为条件随机场。其中，\(w\neq v\)表示G上除v的所有点， \(w \sim v\)表示结点v的马尔可夫毯，即与v连接的结点的集合。

上式表达，在考虑G图上任意结点v的条件概率只需要考虑与其相连的结点集合与X即可。

一般我们假定X与Y有相同的图结构，而且在一般应用上，特别是NLP当中， 目前主要常用的是线性链条件随机场。

团（clique）无向图G中的结点子集C， 若C中任意两结点间均有边连接，则称C为G的一个团，如果C不能再加G中任一结点使用其使其成为更大（“大”指结点数量多）的团，则称C为最大团(maximal clique).

将概率无向图模型的联合概率分布表示其所有最大团上的随机变量的函数（也称因子 factor)乘积的形式的操作，称为概率无向图模型的因子分解(factorization)

设C表示无向图G上的一个最大团, \(Y_C\)表示C对应的随机变量，那概率无向图模型的联合概率分布\(P(Y)\)：

\[P(Y)= \frac{1}{Z}\prod_{C}\Psi_C(Y_C) \]

此式由(Hammersley-Clifford定理)保证（此定理要求P(Y)为正分布，即随机变量的概率均大于0）。其中Z称为规范化因子（normalization factor), 或配分函数(partition function)：

\[Z = \sum_Y\prod_C\Psi_C(Y_C) \]

因子\(\Psi_C(Y_C)\) 称为也称势函数(potential function)，因C是G上的团，则也称为团势函数(clique potential function). 这里要求势函数要严格正的，即率无向图模型的联合概率分布\(P(Y)\)要满足正分布, 通常定义团势函数为指数函数:

\[\Psi_C(Y_C) = \exp{\{-E(Y_C)\}} \]

则\(P(Y)\)表示:

\[P(Y) = \frac{1}{Z}\exp\{{-\sum_{C} E(Y_C)\}} \]

条件承机场的参数化形式:

\[P(y|x) = \frac{1}{Z(x)}\exp{\Big(\sum_{t,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\Big)} \]

其中，

\[Z(x) = \sum_{y}\exp{\Big(\sum_{t,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\Big)} \]

\(t_k,s_l\)分别为边上的特征函数与结点上的特征函数，\(\lambda_k,\mu_l\)为对应的权值。注意，特征函数的中\(x\)是整个序列，而不只是第\(k\)个或第\(l\)个.