机器学习 | 条件随机场（一）

Posted on 2021-06-30

机器学习 | 条件随机场（一）

今天，我们开始条件随机场的学习。

首先我们要知道条件随机场（conditional random field, CRF）是干嘛的。它可以用于构造在给定一组输入随机变量的条件下,另一组输出随机变量的条件概率分布模型。

再开始之前，我们首先要了解一些概念。

概率无向图

即马尔可夫随机场,是一个用无向图表示的联合概率分布.

定义: 图(graph) 是由 节点(node) 与 边(edge) 组成的集合,我们记节点为$v$,记边为$e$,将节点和边所处的集合分别置为$V$与$E$,相应的,我们把该图记作$G=(V,E)$,设由$G$表示联合概率分布$P(Y)$,在图 $G$ 中,每一个节点$v∈V$都表示一个随机变量$Y_v$,$Y=(Y_v)_{v∈V}$,而与之对应的,$e∈E$则表示了随机变量之间的概率依赖关系.

三个性质:

成对马尔可夫性:

$$
P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)
$$
局部马尔可夫性:

$$
P(Y_u,Y_W|Y_O)=P(Y_u|Y_O)P(Y_W|Y_O)
$$
全局马尔可夫性:

$$
P(Y_M,Y_W|Y_O)=P(Y_M|Y_O)P(Y_W|Y_O)
$$

显然成对,局部,全局马尔可夫性质都是等价的。

我们可以说:

如果联合概率分布图$P(Y)$满足成对、局部或全局马尔可夫性,则我们可以称此联合概率分布为概率无向图模型或者马尔可夫随机场.

概率无向图因子分解:

无向图模型实例

最大团: 如上图${Y_1,Y_2,Y_3}$构成一个最大团,该最大团的特点是,从图上的各个其他节点当中,任选一个节点,都不可能同时存在与$Y_1,Y_2,Y_3$的关系,这样的团(clique)我们称之为最大团(maximal clique).

无向图会满足如下性质:

$$
P(Y)=\frac {1} {Z}\prod_C \Psi_C(Y_C)
$$

其中,C代表一个最大团,$Y_C$表示C对应的随机变量.

$$
Z=\sum_Y \prod_C\Psi_C(Y_C)
$$

我们通常称$\Psi_C(Y_C)$为势函数,我们这里要求势函数$\Psi_C(Y_C)$是严格正项.

$$
\Psi_C(Y_C)=exp{-E(Y_C)}
$$

这里我们用指数的形式来表达是因为指数函数良好的性质.

Hammersley-Clifford 定理

概率无向图模型的联合概率分布$P(Y)$可以表示为如下形式:
$$
P(Y)=\frac{1}{Z} \prod_C \Psi_C(Y_C)
$$

$$
Z=\sum_Y \prod_C \Psi_C (Y_C)
$$

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

条件随机场的基础表达

条件随机场(conditional random field)是给定随机变量$X$条件下,随机变量$Y$的马尔可夫随机场.这里我们主要介绍定义在线性链上的特殊条件随机场,我们称之为线性链马尔可夫随机场(linear chain conditional random field).在该条件概率模型$P(Y|X)$中,$Y$是输出变量,表示标记序列,即状态序列,$X$是输入变量,也就是我们得到的需要标注的观测序列.研究学习问题时,我们利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型$\hat P(Y|X)$,在研究预测问题时,我们根据给定的输入序列$x$,求出条件概率$\hat P(y|x)$最大的输出序列$\hat y$.

条件随机场的成立条件: 设$X$与$Y$是随机变量,$P(Y|X)$是在给定的条件$X$下的条件概$Y$率分布.若随机变量$Y$构成一个由无向图$G=(V,E)$表示的马尔可夫随机场,即
$$
P(Y_v|X,Y_w,w \ne v)=P(Y_v|X,Y_w,wv)
$$
对任意结点$v$成立,则称条件概率分布为$P(Y|X)$条件随机场,式中$wv$表示在图$G=(V,E)$中与结点$v$有边链接的所有结点$w$表示结点$v$以外的所有节点,$Y_v,Y_u,Y_w$为结点$v,u,w$分别对应的随机变量.

线性链条件随机场

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

$$
P(Y_i|X,Y_1,…,Y_{i-1},Y_{i+1},…,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})
$$
其中$i=1,2,…,n$，(在$i=1$和$n$时只考虑单边)
则称$P(Y|X)$为线性链条件随机场,在标注问题中,$X$表示输入观测序列,$Y$表示对应的输出标记序列,或者我们可以称之为状态序列.

线性链条件随机场

X和Y具有相同图结构的线性链条件随机场

条件随机场的参数化形式:
$$
P(y|x)=\frac {1} {Z(x)} exp(\sum _{i,k} \lambda k t_k(y{i-1},y_i,x,i)+\sum _{i,l}\mu _ls_l(y_i,x,i))
$$
其中,$t_k,s_l$是特征函数,$\lambda_k,\mu_l$是对应的权值,而$Z(x)$是规范化因子.
$$
Z(x)=\sum _y exp(\sum _{i,k} \lambda k t_k(y{i-1},y_i,x,i)+\sum _{i,l}\mu _ls_l(y_i,x,i)
$$
其中$t_k$是定义在边上的特征函数,我们称之为转移特征,它同时依赖于当前位置和上一个位置。而$s_t$是定义在节点上的特征函数,我们称之为状态特征,它仅仅依赖于当前位置。以上两个变量都依赖于位置属于局部特征,在满足条件时它们的取值为1,不满足条件时,它们的取值为0.

条件随机场的简化形式:

为了方便记录起见,我们将转移特征和状态特征及其权值用统一的符号来表示.设有$K_1$个转移特征,$K_2$个状态特征,$K=K_1+K_2$,记: