专栏首页NewBeeNLP概率图模型笔记(PART III)条件随机场简介

概率图模型笔记(PART III)条件随机场简介

前情提要: 概率图模型笔记(PART I) & 概率图模型笔记(PART II)隐马尔科夫模型

条件随机场CRF笔记

写在前面

前面写完了HMM,比较重点的就是HMM的三个问题,需要好好消化。这篇博客主要介绍条件随机场,相比于HMM,CRF的应用可能会更广。从刚接触CRF开始也很久了,但是由于书上公式非常晦涩难懂,而且网上也有超级多的开源代码实现,所以对CRF的认识也就停留在非常表层的理解。但是就这样的程度让人觉得非常虚,那就拿起小蓝书跟条件随机场来个了断吧~

条件随机场定义

首先给出来自小蓝书的CRF定义:

条件随机场是给定从输入随机变量X条件下,输出随机变量Y的马尔科夫随机场。

那么在这个定义里面,有几个需要我们提前了解的概念:

  1. 「随机场」:随机场是由若干个位置组成的整体,当给每一个位置中按照某种分布随机赋予一个值之后,其全体就叫做随机场。
  2. 「马尔科夫随机场」:马尔科夫随机场是随机场的特例,它及假设随机场中某个位置的赋值仅仅与和它相邻的位置的赋值有关,与其不相邻的位置的值无关。
  3. 「条件随机场」:CRF是马尔科夫随机场的特例,它假设马尔科夫随机场中只有X和Y两种变量,且X一般是给定的输入变量,而Y是我们需要输出的变量(在给定X的条件下)。这样一个马尔科夫随机长就形成了CRF。
线性链条件随机场

在CRF的定义中,并没有要求X和Y具有相同的结构。但是在现实中,我们一般假设X和Y有相同的结构,,如下:

X=\left(X_{1}, X_{2}, \ldots X_{n}\right), Y=\left(Y_{1}, Y_{2}, \ldots Y_{n}\right)

「linear-CRF」定义:

P\left(Y_{i} | X, Y_{1}, \ldots, Y_{i-1}, Y_{i+1}, \ldots, Y_{n}\right)=P\left(Y_{i} | X, Y_{i-1}, Y_{i+1}\right), \quad i=1, \ldots, n

其中当i取1或者n时只考虑单边。 例如,在标注问题中,X表示输入观测序列,Y表示对应的输出标记序列。

linear-CRF参数化形式

那么对于linear-crf,我们如何将其转换成可以学习的机器学习模型呢?这主要是通过「特征函数」和对应的「权重」来进行的。

特征函数

  1. 第一类是状态特征,定义在Y节点上的特征函数,这类特征函数只和当前节点有关,记为:
s_{l}\left(y_{i}, x, i\right), l=1,2, \ldots L

其中L是定义在该节点的节点特征函数的总个数,i是当前节点在序列的位置。2. 第二类是转移特征,定义在边上(Y上下文)的局特征函数,这类特征函数之和当前节点和上一个节点有关,记为:

t_{k}\left(y_{i-1}, y_{i}, x, i\right), \quad k=1,2, \ldots K

其中K是定义在该节点的局部特征函数的总个数,i是当前节点在序列的位置。

注意, 无论是状态特征函数还是转移特征函数,它们的取值只能是0或者1,即满足特征条件或者不满足特征条件。

权重

对于上面说描述的每一个特征函数,我们都为其设置一个权重,用以表达我们对这个特征函数的信任度。 假设tk的权重系数是λk,sl的权重系数是μl,则linear-CRF由我们所有的tk,λk,sl,μl共同决定。

综上,我们可以得出线性链条件随机场的表达式:

P(y | x)=\frac{1}{Z(x)} \exp \left(\sum_{i, k} \lambda_{k} t_{k}\left(y_{i-1}, y_{i}, x, i\right)+\sum_{i, l} \mu_{l} s_{l}\left(y_{i}, x, i\right)\right)

其中,Z是规范化因子,

Z(x)=\sum_{y} \exp \left(\sum_{i, k} \lambda_{k} t_{k}\left(y_{i-1}, y_{i}, x, i\right)+\sum_{i, l} \mu_{l} s_{l}\left(y_{i}, x, i\right)\right)

举个栗子

可以参考小蓝书给出的简单示例,加权求和即可。

CRF简化形式

上一节给出的CRF公式特征函数和权重的参数有点多,显得非常复杂,这里我们可以对其进行整理简化。

假设我们在某一节点我们有K1个转移特征函数和K2个状态特征函数,总共有K=K1+K2个特征函数。我们用一个特征函数fk(yi−1,yi,x,i)来统一表示如下:

f_{k}\left(y_{i-1}, y_{i}, x, i\right)=\left\{\begin{array}{ll}{t_{k}\left(y_{i-1}, y_{i}, x, i\right)} & {k=1,2, \ldots K_{1}} \\ {s_{l}\left(y_{i}, x, i\right)} & {k=K_{1}+l, l=1,2 \ldots, K_{2}}\end{array}\right.

接着我们对特征函数在各个位置i求和,可得:

f_{k}(y, x)=\sum_{i=1}^{n} f_{k}\left(y_{i-1}, y_{i}, x, i\right)

同时我们也将对应的权重进行相同的处理,

w_{k}=\left\{\begin{array}{ll}{\lambda_{k}} & {k=1,2, \ldots K_{1}} \\ {\mu_{l}} & {k=K_{1}+l, l=1,2 \ldots, K_{2}}\end{array}\right.

这样我们之前那个复杂多参数的公式就可以简写为,

P(y | x)=\frac{1}{Z(x)} \exp \sum_{k=1}^{K} w_{k} f_{k}(y, x)

其中Z为规范化参数

Z(x)=\sum_{y} \exp \sum_{k=1}^{K} w_{k} f_{k}(y, x)

CRF矩阵形式

条件随机场也有矩阵形式,是一种模型按时序展开分步计算的形式。对输入观测序列X中的每一个

x_{t}

  1. 计算出所有的可能情况(根据不同假设y组合情况,计算激活的特征函数与权值乘积的和), 按照一定的顺序组成矩阵;
  2. 在所有矩阵计算完成之后,利用这些矩阵可以完成最优序列的求解,Z(x)的计算。

为此我们定义一个m x m的矩阵M,m为y所有可能的状态的取值个数:

M_i(x) = \Big[ M_i(y_{i-1},y_i |x)\Big] = \Big[ exp(W_i(y_{i-1},y_i |x))\Big] = \Big[ exp(\sum\limits_{k=1}^Kw_kf_k(y_{i-1},y_i, x,i))\Big]

同时引入起点和终点标记

y_0 =start, y_{n+1} = stop

,这样标记序列y的非规范化概率可以通过n+1个矩阵元素的乘积得到:

P_{w}(y | x)=\frac{1}{Z_{w}(x)} \prod_{i=1}^{n+1} M_{i}\left(y_{i-1}, y_{i} | x\right)

其中Z(x)为规范化因子。

CRF的三个问题

与HMM类似,CRF也有三个基本问题:

  • 计算问题:

给定条件随机场 P(Y|X),输入序列x和输出序列y,计算条件概率

P\left(y_{i} | x\right)

P\left(y_{i-1},y_{i} | x\right)

以及对应的期望 前向后向算法

  • 解码问题

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

  • 学习问题

给定训练数据集X和对应的标记序列Y,K个特征函数fk(x,y),需要学习linear-CRF的模型参数wk和条件概率Pw(y|x) 梯度下降法,牛顿法,拟牛顿法,迭代尺度法

其中前两个问题属于inference,第三个问题属于learning。 三个问题的具体解法就放在下篇文章里写吧~ 以上~

本文分享自微信公众号 - NewBeeNLP(NewBeeNLP),作者:kaiyuan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Kick Algorithm】十大排序算法及其Python实现

    看到好像春招都已经陆续都开始了,最近抽空打算把自己和朋友的经验整理一下分享出来。作为一个刚刚经历秋招打击的自闭儿童,可以非常负责任地说手撕算法是面试中必考的点,...

    kaiyuan
  • 详解ERNIE-Baidu进化史及应用场景

    ERNIE: Enhanced Representation through Knowledge Integration[1] 是百度在2019年4月的时候,基...

    kaiyuan
  • Transformers Assemble(PART V)

    上一期魔改Transformer好像是两周之前了哈哈,今天继续!最近刚关注的同学感兴趣可以翻翻历史记录补补课

    kaiyuan
  • [白话解析] 用水浒传为例学习条件随机场

    本文将尽量使用易懂的方式,尽可能不涉及数学公式,而是从整体的思路上来看,运用感性直觉的思考来解释条件随机场。并且用水浒传为例学习。并且从名著中找了具体应用场景来...

    罗西的思考
  • 今日 Paper | 梯度剪切;命名实体识别;自然语言处理;免强度函数学习等

    论文名称:Why Gradient Clipping Accelerates Training: A Theoretical Justification for...

    AI科技评论
  • 聊聊rocketmq-client-go的api.go

    rocketmq-client-go的api.go定义了Producer、TransactionProducer、PushConsumer、PullConsum...

    codecraft
  • 聊聊rocketmq-client-go的api.go

    rocketmq-client-go的api.go定义了Producer、TransactionProducer、PushConsumer、PullConsum...

    codecraft
  • Java selenuim用执行js模拟鼠标滚动的方式

    我使用的方法是利用如下js代码来完成页面的滚动,每次滚动多少可以根据不同情况自行调整。

    heasy3
  • 南航戴振东:仿生学研究需要与生物学家跨界交流,目前最缺的是人才

    谈到仿生学,可以一直追溯到古代的「木牛流马」、渔船摇撸、鲁班发明木锯。研究难点在于从研究生物到理解生物再到工程实现,周期太长,很多人难以坚持。

    AI科技评论
  • JavaScript文件加载优化

    在js引擎部分,我们可以了解到,当渲染引擎解析到script标签时,会将控制权给JS引擎,如果script加载的是外部资源,则需要等待下载完后才能执行。 所以,...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券