条件随机场

《统计学习方法》笔记 第11章

Posted by Cheereus on February 24, 2020

第11章 条件随机场

条件随机场(conditional random filed, CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型,其特点是假设输出随机变量构成马尔可夫随机场。

11.1 概率无向图模型

11.1.1 模型定义

设有联合概率分布 $Y(Y)$,由无向图 $G=(V,E)$ 表示,在图 $G$ 中,节点表示随机变量,边表示随机变量之间的依赖关系。如果联合概率分布 $Y(Y)$ 满足成对、局部或全局马尔可夫性,就称此联合概率分布为概率无向图模型(probabilistic undirected graphical model),或马尔可夫随机场。

11.1.2 概率无向图模型的因子分解

无向图 $G$ 中任何两个节点均有连接的节点子集称为团(clique)。若 $C$ 是无向图 $G$ 的一个团,并且不能再加进任何一个 $G$ 的节点使其称为一个更大的团,则称此 $C$ 为最大团(maximal clique)。

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

(Hammersley-Clifford 定理)概率无向图模型的联合概率分布 $P(Y)$ 可以表示为如下形式:

其中,$C$ 是无向图的最大团,$Y_C$ 是 $C$ 的节点对应的随机变量,$\Psi_C(Y_C)$ 是 $C$ 上定义的严格正函数,乘积是在无向图所有的最大团上进行的。

$Z$ 是规范化因子(normalization factor),保证 $P(Y)$ 构成一个概率分布。函数 $\Psi_C(Y_C)$ 称为势函数(potential function),通常定义为指数函数:

11.2 条件随机场的定义与形式

11.2.1 条件随机场的定义

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

对任意节点 $v$ 成立,则称条件概率分布 $P(Y\vert X)$ 为条件随机场。式中 $w\sim v$ 表示在图 $G=(V,E)$ 中与节点 $v$ 有边连接的所有节点 $w$,$w\neq v$ 表示节点 $v$ 以外的所有节点,$Y_v,Y_u,Y_w$ 为节点 $v,u,w$ 对应的随机变量。

(线性链条件随机场) 设 $X=(X_1,X_2,\cdots,X_n),Y=(Y_1,Y_2,\cdots,Y_n)$ 均为线性链表示的随机变量序列,若在给定随机变量序列 $X$ 的条件下,随机变量序列 $Y$ 的条件概率分布 $P(Y\vert X)$ 构成条件随机场,即满足马尔可夫性

在 $i=1$ 和 $n$ 时只考虑单边。则称 $P(Y\vert X)$ 为线性链条件随机场。在标注问题中,$X$ 表示输入观测序列,$Y$ 表示对应的输出标记序列或状态序列。

11.2.2 条件随机场的参数化形式

设 $P(Y\vert X)$ 为线性链条件随机场,则在随机变量 $X$ 取值为 $x$ 的条件下,随机变量 $Y$ 取值为 $y$ 的条件概率具有如下形式:

其中

式中 $t_k$ 和 $s_l$ 是特征函数,$\lambda_k$ 和 $\mu_l$ 是对应的权值。$Z(x)$ 是规范化因子,求和是在所有可能的输出序列上进行的。

11.2.3 条件随机场的简化形式

若以 $w$ 表示权值向量,即

以 $F(y,x)$ 表示全局特征向量,即

则条件随机场可以写成向量 $w$ 与 $F(y,x)$ 的内积的形式:

其中

11.2.4 条件随机场的矩阵形式

11.3 条件随机场的概率计算问题

11.3.1 前向-后向算法

11.3.2 概率计算

11.3.3 期望值的计算

11.4 条件随机场的学习算法

11.4.1 改进的迭代尺度法

11.4.2 拟牛顿法

11.5 条件随机场的预测算法