CRF 条件随机场 概述


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

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

  • 我们用CRF来做什么?

    可以用于构造在给定一组输入随机变量的条件下,另一组输出随机变量的条件概率分布模型.


在开始之前

  • 概率无向图

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

    • 定义: 图(graph) 是由 节点(node)边(edge) 组成的集合,我们记节点为v,记边为e,将节点和边所处的集合分别置为
      VE,相应的,我们把该图记作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_CC的节点对应的随机变量,\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.
  • 条件随机场的成立条件: 设XY是随机变量,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=1n时只考虑单边)
    则称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)表示全局特征向量:

    我们可以对应地把条件随机场写成向量wF(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=starty_{n+1}=stop表示开始状态与结束状态,规范化因子是这期间所有的概率矩阵的乘积.


CRF的概率计算问题

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

    递推公式为:

    终结项为:

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

    递推公式:

    终结项:

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

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

    其中:

  • 期望值计算:

    其中:

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

    其中:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念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

推荐阅读更多精彩内容