CRF 条件随机场概述

哈哈哈没错就是我,我我我又跑过来开新坑了,今天来和大家唠唠CRF的那点事儿.

条件随机场(conditional random field, CRF)

我们用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)$
  显然成对,局部,全局马尔可夫性质都是等价的ww
- 我们可以说:
  - 如果联合概率分布图 $P(Y)$ 满足成对、局部或全局马尔可夫性,则我们可以称此联合概率分布为概率无向图模型或者马尔可夫随机场.
- 概率无向图因子分解:
  
  无向图模型实例.jpg
  - 最大团: 如上图 ${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,w~v)$
对任意结点 $v$ 成立,则称条件概率分布 $P(Y|X)$ 为条件随机场,式中 $w~v$ 表示在图 $G=(V,E)$ 中与结点 $v$ 有边链接的所有结点 $w$ , $w \ne v$ 表示结点 $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$ 表示对应的输出标记序列,或者我们可以称之为状态序列.

线性链条件随机场.png

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

条件随机场的参数化形式:
$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$ ,记:

相应的我们把和写为如下格式:

权值对应的统一符号:

条件随机场对应的概率表达:

w表示权值向量:

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

我们可以对应地把条件随机场写成向量 $w$ 与 $F(y,x)$ 的内积的形式:

与之对应的归一化参数 $Z_w(x)$
条件随机场的矩阵形式:
对于观测序列 $x$ 的每一个位置我们都定义一个 $m$ 阶矩阵( $m$ 是标记 $y_i$ 的取值的个数):

矩阵化表示

这样一来,对于给定的观测序列 $x$ ,标记序列 $y$ 的非规范化概率可以通过 $n+1$ 个矩阵的乘积 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 来表示,于是,条件概率 $P_w(y|x)$ 就是:

其中 $Z_w(x)$ 为规范化因子,是 $n+1$ 个矩阵的乘积的 $( start,stop )$ 元素:

$y_0=start$ 与 $y_{n+1}=stop$ 表示开始状态与结束状态,规范化因子是这期间所有的概率矩阵的乘积.

CRF的概率计算问题

前向-后向算法:对于每个指标 $i=0,1,...,n+1$ ,定义前向向量 $\alpha_i(x)$ :

递推公式为:

终结项为:

同理可知我们的后向向量 $\beta_i(x)$ :

递推公式:

终结项:

由此我们可得出如下关系:

在已知前向后向序列时的条件概率运算:

其中:
期望值计算:

其中:

特征函数 $f_k$ 关于联合分布 $P(X,Y)$ 的数学期望是:

其中:

最后编辑于：2018.08.25 00:15:13

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 201,468评论 5赞 473
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,620评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,427评论 0赞 334
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,160评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,197评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,334评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,775评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,444评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,628评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,459评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,508评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,210评论 3赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,767评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,850评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,076评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,627评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,196评论 2赞 341

CRF 条件随机场 概述

条件随机场(conditional random field, CRF)

在开始之前

概率无向图

条件随机场的基础表达

CRF的概率计算问题

推荐阅读更多精彩内容

CRF 条件随机场概述