CRF++代码分析

本文按照调用顺序抽丝剥茧地分析了CRF++的代码,详细注释了主要函数,并指出了代码与理论公式的对应关系。内容包括拟牛顿法的目标函数、梯度、L2正则化、L-BFGS优化、概率图构建、前向后向算法、维特比算法等。背景知识请参考《条件随机场》。

训练

先从训练开始说起吧

该函数解析命令行之后调用:

该函数会调用:

该函数先读取特征模板和训练文件

这个open方法并没有构建训练实例,而是简单地解析特征模板和统计标注集:

回到learn方法中来,做完了这些诸如IO和参数解析之后,learn方法会根据算法参数的不同而调用不同的训练算法。取最常用的说明如下:

计算梯度

创建多个CRFEncoderThread,平均地将句子分给每个线程。每个线程的工作其实只是计算梯度:

梯度计算时,先构建网格:

由于CRF是概率图模型,所以有一些图的特有概念,如顶点和边:

buildLattice方法调用rebuildFeatures对每个时刻的每个状态分别构造边和顶点:

这也就是大家经常看到的类似如下的图:

然后计算每个节点和每条边的代价(也就是特征函数乘以相应的权值,简称代价):

其中fvector是当前命中特征函数的起始id集合,对于每个起始id,都有连续标签个数种y值;n->y是当前时刻的标签,由于每个特征函数都必须同时接受x和y才能决定输出1或0,所以要把两者加起来才能确定最终特征函数的id。用此id就能在alpha向量中取到最终的权值,将权值累加起来,乘以一个倍率(也就是所谓的代价参数cost_factor),得到最终的代价cost。

对于边来说,也是类似的,只不过对每个起始id,都有连续标签个数平方种y值组合。

这部分对应

前向后向算法

网格建完了,就可以在这个图上面跑前向后向算法了:

该方法依次计算前后向概率:

计算前向概率的具体实现是:

其中cost是我们刚刚计算的当前节点的M_i(x),而alpha则是当前节点的前向概率。lpath是入边,如代码和图片所示,一个顶点可能有多个入边。

对应:

后向概率同理略过。

前后向概率都有了之后,计算规范化因子:

对应着

关于函数logsumexp的意义,请参考《计算指数函数的和的对数》。

于是完成整个前后向概率的计算。

期望值的计算

节点期望值

所谓的节点期望值指的是节点对应的特征函数关于条件分布

的数学期望。

calcExpectation具体实现是:

第一个for对应下式的求和

概率求和意味着得到期望。

第二个for对应边的期望值。

边的期望值

对应下式的求和

这样就得到了条件分布的数学期望:

梯度计算

–expected表示模型期望(条件分布)减去观测期望,得到目标函数的梯度:

有人可能要问了,expected的确存的是条件分布的期望,但观测期望还没计算呢,把条件分布的期望减一是干什么?

这是因为对观测数据(训练数据)来讲,它一定是对的,也就是在y!=answer_[i]的时候概率为0,在y=answer_[i]的时候概率为1,乘以特征函数的输出1,就等于1,这就是观测期望。

维特比算法

紧接着gradient函数还顺便调了一下TaggerImpl::viterbi:

void TaggerImpl::viterbi(){    for (size_t i = 0; i < x_.size(); ++i)    {        for (size_t j = 0; j < ysize_; ++j)        {            double bestc = -1e37;            Node *best = 0;            const std::vector<Path *> &lpath = node_[i][j]->lpath;            for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it)            {                double cost = (*it)->lnode->bestCost + (*it)->cost + node_[i][j]->cost;                if (cost > bestc)                {                    bestc = cost;                    best = (*it)->lnode;                }            }            node_[i][j]->prev = best;            node_[i][j]->bestCost = best ? bestc : node_[i][j]->cost;        }    }     double bestc = -1e37;    Node *best = 0;    size_t s = x_.size() - 1;    for (size_t j = 0; j < ysize_; ++j)    {        if (bestc < node_[s][j]->bestCost)        {            best = node_[s][j];            bestc = node_[s][j]->bestCost;        }    }     for (Node *n = best; n; n = n->prev)    {        result_[n->x] = n->y;    }     cost_ = -node_[x_.size() - 1][result_[x_.size() - 1]]->bestCost;}

其中prev构成一个前驱数组,在动态规划结束后通过prev回溯最优路径的标签y,存放于result数组中。

跑viterbi算法的目的是为了评估当前模型的准确度,以辅助决定是否终止训练。

正则化

为了防止过拟合,CRF++采用了L1或L2正则化:

if (orthant){   // L1    for (size_t k = 0; k < feature_index->size(); ++k)    {        thread[0].obj += std::abs(alpha[k] / C);        if (alpha[k] != 0.0)        {            ++num_nonzero;        }    }}else{    num_nonzero = feature_index->size();    for (size_t k = 0; k < feature_index->size(); ++k)    {        thread[0].obj += (alpha[k] * alpha[k] / (2.0 * C));        thread[0].expected[k] += alpha[k] / C;    }}

以L2正则为例,L2正则在目标函数上加了一个正则项:

+

其中,

是一个常数,在CRF++中其平方被称作cost-factor,

控制着惩罚因子的强度。可见要最小化目标函数,正则化项

也必须尽量小才行。模型参数的平方和小,其复杂度就低,于是就不容易过拟合。关于L1、L2正则化推荐看Andrew Ng的ML公开课

目标函数加了一项

之后,梯度顺理成章地也应加上

的导数:

+

这也就是代码中为什么要自加这两项的原因了:

        thread[0].obj += (alpha[k] * alpha[k] / (2.0 * C));        thread[0].expected[k] += alpha[k] / C;

L-BFGS优化

梯度和损失函数有了,之后就是通用的凸函数LBFGS优化了。CRF++直接将这些参数送入一个LBFGS模块中:

if (lbfgs.optimize(feature_index->size(), &alpha[0], thread[0].obj, &thread[0].expected[0], orthant, C) <=    0){    return false;}

据说这个模块是用一个叫f2c的工具从FORTRAN代码转成的C代码,可读性并不好,也就不再深入了。

//   lbfgs.c was ported from the FORTRAN code of lbfgs.m to C//   using f2c converter////   http://www.ece.northwestern.edu/~nocedal/lbfgs.html

有兴趣的话看看《数值优化:理解L-BFGS算法》即可。

预测

预测就简单多了,主要对应下列方法:

bool TaggerImpl::parse(){    CHECK_FALSE(feature_index_->buildFeatures(this)) << feature_index_->what();     if (x_.empty())    {        return true;    }    buildLattice();    if (nbest_ || vlevel_ >= 1)    {        forwardbackward();    }    viterbi();    if (nbest_)    {        initNbest();    }     return true;}

主要的方法也就是建立网格和维特比这两个,由于前面训练的时候已经分析过,这里就不再赘述了。

Reference

crf-tutorial.pdf
条件随机场理论综述.pdf

http://mi.eng.cam.ac.uk/~cz277/doc/Slides-CRFASR-CSLT.pdf

http://blog.sina.com.cn/s/blog_a6962c6401016gob.html

原文发布于微信公众号 - CreateAMind(createamind)

原文发表时间:2016-08-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杂七杂八

xgboost初识

XGBoost使用 原始数据 数据介绍 鸢尾花数据集是由杰出的统计学家R.A.Fisher在20世纪30年代中期创建的,它被公认为用于数据挖掘的最著名的数据集。...

34240
来自专栏Coding迪斯尼

深度学习项目实践,使用神经网络分析电影评论的正能量与负能量

14510
来自专栏自学笔记

聚类算法

p=2时就说平时计算的几何距离,当p趋向于正无穷的时候,其实求的就不是x,y的距离了,而是求x y中最长的一个了。因为如果x大于y,在指数增长下x回远大于y,所...

34720
来自专栏AI研习社

自定义损失函数Gradient Boosting

互联网上有很多关于梯度提升的很好的解释(我们在参考资料中分享了一些选择的链接),但是我们注意到很少有人提起自定义损失函数的信息:为什么要自定义损失函数,何时需要...

2.6K30
来自专栏机器学习算法与Python学习

教程 | 一步一步,看图理解长短期记忆网络与门控循环网络

大家好,欢迎来到 LSTM 和 GRU 的图解指南。在本文中,Michael 将从 LSTM 和 GRU 的背后的原理开始,然后解释令 LSTM 和 GRU 具...

12130
来自专栏AI研习社

教你从零开始在 TensorFlow 上搭建 RNN(完整代码)!

RNN 是什么? 递归神经网络,或者说 RNN,在数据能被按次序处理、数据点的不同排列亦会产生影响时就可以使用它。更重要的是,该次序可以是任意长度。 最直接...

39360
来自专栏人工智能头条

LSTM实现详解

23430
来自专栏量子位

如何用TensorFlow构建RNN?这里有一份极简的教程

王小新 编译自 KDnuggets 量子位 出品 | 公众号 QbitAI 本文作者Erik Hallström是一名深度学习研究工程师,他的这份教程以Echo...

49760
来自专栏小詹同学

深度学习入门笔记系列 ( 五 )

本系列将分为 8 篇 。本次为第 5 篇 ,结合上一篇的应用实例 ,将前边学到一些基础知识用到手写数字的识别分类上 。

8420
来自专栏谭正中的专栏

TensorFlow入门(1):求N元一次方程

今年以来,人工智能成为一个时代热点,同时 TensorFlow 1.0 的发布后,我也想蹭蹭时代的热点,初步学习一下神经网络和机器学习,在这里把成果以初学者的方...

3.9K10

扫码关注云+社区

领取腾讯云代金券