一起走进条件随机场4(NLP重点理论)

1 统计学习角度谈CRF

引言

条件随机场(CRF):是给定一组输入随机变量条件下,另一组输出随机变量的条件概率分布模型,其特点是假设输出随机变量构成马尔科夫随机场,条件随机场可用于不同预测问题,由输入序列对输出序列预测的判别式模型,形式为对数线性模型,其学习方法通常是极大似然估计。

条件随机场定义和形式

简单的说,条件随机场(CRF)类似于MRF,只不过CRF比MRF多了一个观察集合,或者说,CRF本质上就是给定了观察值集合的MRF。

条件随机场:设G=(V,E)是一个无向图,Y={Yv|v∈V}是以G中节点v为索引的随机变量Yv构成的集合。在给定X的条件下,如果每个随机变量Yv服从马尔可夫性,即

,则条件概率分布P(Y|X)就是一个条件随机场。上式中的w ~ v表示在图G=(V, E)中与节点v有边连接的所有节点,w≠v表示v以外的所有节点,Yv,Yu, Yw为w对节点v,u,w对应的随机变量。

线性链条件随机场

设X = (X1, X2,..., Xn), Y = (Y1, Y2, ..., Yn)均为线性链表示的随机变量序列,若在给定随机变量序列X的条件下,随机变量序列Y的条件概率分布P(Y|X)构成条件随机场,即满足马尔可夫性(见本文最开始的“模型定义”部分): P(Yi| X, Y1, ..., Yi-1, Yi+1, ...., Yn)= P(Yi | X, Yi-1, Yi+1) i= 1, 2, ..., n (在i=1和n时只考虑单边),则称P(Y|X)为线性链条件随机场。

注意:在标注问题中,X表示输入观测序列,Y表示对应的输出标记序列或状态序列。

2 CRF参数化形式

参数化形式化

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

式中,tk和sl是特征函数,λk和μl是对应的权值。Z(x)是规范化因子,求和时在所有可能的输出序列上进行的。

通常:特征函数t和s取值是1或0,当满足特征条件取值1,反之取值0,条件随机场完全由特征函数t,s和对应的数值λ,μ确定。

注意:线性CRF也是对数性模型。

实例理解条件随机场

设有一个天气预测问题:输入观察序列(连续三天的天气情况)为X = (X1, X2, X3),输出标记序列(每天对应天气热冷的预测)为 Y = (Y1, Y2, Y3), Y1, Y2, Y3 的取值于y= {H, C},其中H表示天热,C表示天冷。假设特征tk,sl和对应的权值λk,μl如下:

其中,上式代表着特征值为H的条件,即:yi-1= H, yi=C, x, i = 2, 3 时特征值取1。而特征值取0的条件被省略了。

PS:如果写全的话是这样:

于是对给定的观测序列x,求标记序列为y =(y1, y2, y3) = (H, C, C),即第一天热,第二天第三天连续冷的非规范化条件概率(即没有除以规范化因子的条件概率)

案例分析

由以上问题可知,观察序列是天数的集合,标记序列是对应天气热冷的集合,由此分析显然是随机条件场的编码问题,基于随机条件场,可以将上述情形转换为图形化形式分析,然后进行模型构建,算法实现,算法优化和结果分析即可。本节重点实现分析,图形表示,模型构建。

天气预测问题转化为图形表示如下:

如图所示,横坐标x1,x2,x3分别对应天,是观察序列具备时序性,纵坐标是标记序列即可能隐藏的所有标记情况,start和end表示开始和结束状态(这点参照笔者Viterbi算法一节的介绍),其中t表示转移概率,t=0.5有具体权值的,标注转移概率是50%机会。X对应的s表示发射概率或者生产概率,显然,如上满足条件随机场,回顾下条件随机场模型,线性链条件随机场模型为:

于是对给定的观测序列x,标记序列y=(H,C,C)的非规范化条件概率为

上式数值计算,参照已知条件和图形分析,很容易计算,这里具体计算过程省略。

3 条件随机场简化形式

将局部特征转化为一个全局特征函数,可将CRF写成权值向量和特征向量的内积形式即是条件随机场的简化形式,具体参见如下笔记:

① 将转移特征和状态特征以及其数值用统一符号表示,设有K1个转移贴纸,K2个状态特征,K=K1+K2,记:

② 对转移状态各个位置i求和,记作:

③ 用wk表示特征fk(y,x)的权值,即:

④ 于是,条件随机场可表示为

⑤ 以w表示权值向量,即

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

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

4 条件随机场预测算法

形式化描述

条件随机场的预测问题是给定义条件随机场P(Y|X)和输入序列(观测序列)x,求条件概率最大的输出序列(标记序列)y*,即对观测序列进行标注。 条件随机场的预测算法是著名的维特比算法。

维特比算法

你对维特比算法是什么就有概念了吧,下面来看看其数学描述。维特比算法不做深入讲解,如果读者还不清楚,参考本人系列文章之揭秘马尔科夫模型系统文章,有专门章节详细介绍viterbi算法。

这里,路径表示标记序列,其中

注意,这时只需计算非规范化概率,而不必计算概论,可以大大提高效率。

为了求解最优路径,将式写成如下形式:

其中

就是局部特征向量。下面叙述维特比算法。

实例解析

用维特比算法求给定的输入序列(观测序列)x对应的输出序列(标记序列)y* = (y1*, y2*, y3*);

  1. 第一步初始化:因为y1=1和y1=2是最初,所以就不用考虑转移的情况了(实际上也没有“表达从y0转移到y1的情况”的t函数(转移函数)),直接从状态函数(s函数中找),发现,s1和s2分别对应y1=1和y1=2,说明y1=1和y1=2这个状态都是存在的,而s1和s2的权值分别是1和0.5,且上面列出的s函数们和t函数们值都为1,所以y1=1和y2=1的可能性分别是1和0.5。所以,到达y1的非规范化概率最大值为:δ1(1) = 1,δ1(2) = 0.5。
  2. 第二步递推:i=2(达第二处目的地集合{y2=1, y2=2}):首先是路线(仅说明到达y2=1的情况):上图可知,到达y2=1的路线有如下几条: 路线1:从y1=1出发 ----(经过t2)---->到达y2=1; 路线2:从y1=2出发 ----(经过t4)---->到达y2=1; 接着是状态(仅说明到达y2=1的情况):根据题目可知:i=2时的状态函数只有s2和s3,而y2=1对应的函数是s3。所以到达y2=1的非规范化概率最大值为:δ2(1) = max{1+λ2t2 + u3s3,0.5 + λ4t4 + u3s3}= 2.4 非规范化概率最大值的路径为: ψ2(1) = 1。δ2(2)同理。i=3也一样(只不过对于δ3(1)中的u5s5,我认为应该是u3s3,先不说s3对应的是y3=1的情况,而且原题中根本没有s5函数)。
  3. 第三步终止:这步就简单了,在δ3(l)中δ3(1) = 4.3最大,所以y3中取1的可能性最大,即y3*=1。
  4. 第四步返回:然后反着推:从y2的哪个值到y3可能性最大呢?在第二部已经解出:ψ3(1) = 2,即y2到达y3=1的路线中权值最大的是y2=2,即y2*=2。同理,从y1=1到y2=2的可能性最大,即y1*=1。
  5. 就得到标记序列:*= (y1*, y2*, y3*)= (1, 2, 1)6

5 参考文献

  1. 数学之美 吴军 著
  2. 机器学习 周志华 著
  3. 统计自然语言处理 宗成庆 著(第二版)
  4. 统计学习方法(191---208) 李航
  5. 知乎 网络资源

文末:文章来源机器学习和自然语言处理(ID:datathinks),作者:机器学习和自然语言处理。本公众号旨在技术传播与分享,未经授权不能转载发布。

原文发布于微信公众号 - 机器学习和自然语言处理(datathinks)

原文发表时间:2017-09-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

塔说 |盘点人工智能从业者必备的10个深度学习方法

导读:近日,软件工程师 James Le 在 Medium 上发表了一篇题为《The 10 Deep Learning Methods AI Practitio...

3484
来自专栏AI科技评论

学界 | 美图云联合中科院提出基于交互感知注意力机制神经网络的行为分类技术 | ECCV 2018

以往注意机制模型通过加权所有局部特征计算和提取关键特征,忽略了各局部特征间的强相关性,特征间存在较强的信息冗余。为解决此问题,来自美图云视觉技术部门和中科院自动...

1162
来自专栏大数据文摘

超实用总结:AI实践者需要用到的10个深度学习方法

1164
来自专栏IT派

改变你对世界看法的五大计算机视觉技术!

计算机视觉是当前最热门的研究之一,是一门多学科交叉的研究,涵盖计算机科学(图形学、算法、理论研究等)、数学(信息检索、机器学习)、工程(机器人、NLP等)、生物...

1760
来自专栏机器之心

资源 | 从反向传播到迁移学习,盘点人工智能从业者必备的10个深度学习方法

3267
来自专栏数据科学与人工智能

【机器学习】特征工程

作者:JasonDing1354 引言 在之前学习机器学习技术中,很少关注特征工程(Feature Engineering),然而,单纯学习机器学习的算法流程,...

4765
来自专栏目标检测和深度学习

MIT 6.S094· 深度学习 | 学霸的课程笔记,我们都替你整理好了

计算机视觉,到目前为止都是深度学习。并且大部分成功理解图片含义的案例都是使用神经网络。

1215
来自专栏Python数据科学

【算法面经】:机器学习面试算法梳理

机器学习算法面试一直是大家比较苦恼的事情,各种算法经常弄混,或者无法透彻理解。分享一篇非常好的机器学习算法面试干货总结,梳理算法原理,优缺点。

1042
来自专栏AI科技大本营的专栏

机器学习101:我们天天都在说的机器学习,究竟该怎么入门?

为了使大家对机器学习有一个基本的认识,在这篇文章中,我们将对以下四个主题做简要的介绍: 什么是机器学习? 机器学习模型的训练。 模型参数的优化。 神经网络。 即...

2985
来自专栏新智元

【重磅】计算机视觉和 CNN 发展十一座里程碑(附论文下载)

【新智元导读】从AlexNet到ResNet,计算机视觉领域和卷积神经网络(CNN)每一次发展,都伴随着代表性架构取得历史性的成绩。作者回顾计算机视觉和CNN过...

3744

扫码关注云+社区