放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

基于CRF序列标注的中文依存句法分析器的Java实现

目录

这是一个基于CRF的中文依存句法分析器,内部CRF模型的特征函数采用 双数组Trie树(DoubleArrayTrie)储存,解码采用特化的维特比后向算法。相较于《最大熵依存句法分析器的实现》,分析速度翻了一倍,达到了1262.8655 sent/s

开源项目

本文代码已集成到HanLP中开源:http://www.hankcs.com/nlp/hanlp.html

CRF简介

CRF是序列标注场景中常用的模型,比HMM能利用更多的特征,比MEMM更能抵抗标记偏置的问题。在生产中经常使用的训练工具是CRF++,关于CRF++的使用以及模型格式请参阅CRF++模型格式说明》。

CRF训练

语料库

最大熵依存句法分析器的实现》相同,采用清华大学语义依存网络语料的20000句作为训练集。

预处理

依存关系事实上由三个特征构成——起点、终点、关系名称。在本CRF模型中暂时忽略掉关系名称(在下文可以利用其它模型补全)。

根据依存文法理论, 我们可以知道决定两个词之间的依存关系主要有二个因素: 方向和距离。因此我们将类别标签定义为具有如下的形式:

[ + |- ] dPOS

其中, [ + | – ]表示方向, + 表示支配词在句中的位置出现在从属词的后面, – 表示支配词出现在从属词的前面; POS表示支配词具有的词性类别; d表示距离。

比如原树库:

1	很	很	d	d	_	2	程度	
2	有	有	v	vyou	_	0	核心成分	
3	必要	必要	a	a	_	2	存现体	
4	对	对	p	p	_	14	介词依存	
5	惩治	惩治	v	v	_	14	限定	
6	贪污	贪污	v	v	_	8	限定	
7	贿赂	贿赂	n	n	_	6	连接依存	
8	犯罪	犯罪	v	vn	_	5	受事	
9	的	的	u	ude1	_	5	“的”字依存	
10	一些	一些	m	mq	_	14	数量	
11	理论	理论	n	n	_	14	限定	
12	与	与	c	cc	_	11	连接依存	
13	实践	实践	v	vn	_	11	连接依存	
14	问题	问题	n	n	_	16	内容	
15	进行	进行	v	vx	_	16	评论	
16	研究	研究	v	vn	_	3	限定

转换后:

很	d	d	+1_v
有	v	vyou	-1_ROOT
必要	a	a	-1_v
对	p	p	+3_n
惩治	v	v	+3_n
贪污	v	v	+1_v
贿赂	n	n	-1_v
犯罪	v	vn	-2_v
的	u	ude1	-3_v
未##量	m	mq	+2_n
理论	n	n	+1_n
与	c	cc	-1_n
实践	v	vn	-1_n
问题	n	n	+2_v
进行	v	vx	+1_v
研究	v	vn	-1_a

特征模板

# Unigram
U01:%x[0,0]
U02:%x[0,0]/%x[0,2]
U03:%x[-1,2]/%x[0,0]
U04:%x[-1,2]/%x[0,2]/%x[0,0]
U05:%x[0,0]/%x[1,2]
U06:%x[0,0]/%x[0,2]/%x[1,2]
U07:%x[-1,2]/%x[0,2]
U08:%x[-1,1]/%x[0,2]
U09:%x[0,2]/%x[1,2]
U10:%x[0,2]/%x[1,1]
U11:%x[-2,2]/%x[-1,2]/%x[0,2]/%x[1,2]
U12:%x[-1,2]/%x[0,2]/%x[1,2]/%x[2,2]
U13:%x[-2,2]/%x[-1,2]/%x[0,2]/%x[1,2]/%x[2,2]
U14:%x[-2,1]/%x[-1,2]/%x[0,2]
U15:%x[-1,2]/%x[0,2]/%x[1,2]
U16:%x[-1,1]/%x[0,2]/%x[1,1]
U17:%x[-1,2]/%x[1,2]

# Bigram
B

训练参数

crf_learn -f 3 -c 4.0 -p 3 template.txt train.txt model -t

我的试验条件(机器性能)有限,每迭代一次要花5分钟,最后只能设定最大迭代次数为100。经过痛苦的迭代,得到了一个效果非常有限的模型,其serr高达50%,暂时只做算法测试用。

解码

标准的维特比算法假定所有标签都是合法的,但是在本CRF模型中,标签还受到句子的约束。比如最后一个词的标签不可能是+nPos,必须是负数,而且任何词的[+/-]nPos都得保证后面(或前面,当符号为负的时候)有n个词语的标签是Pos。所以我覆写了CRF的维特比tag算法,代码如下:

@Override
public void tag(Table table)
{
    int size = table.size();
    double bestScore = 0;
    int bestTag = 0;
    int tagSize = id2tag.length;
    LinkedList<double[]> scoreList = computeScoreList(table, 0);    // 0位置命中的特征函数
    for (int i = 0; i < tagSize; ++i)   // -1位置的标签遍历
    {
        for (int j = 0; j < tagSize; ++j)   // 0位置的标签遍历
        {
            if (!isLegal(j, 0, table)) continue;
            double curScore = matrix[i][j] + computeScore(scoreList, j);
            if (curScore > bestScore)
            {
                bestScore = curScore;
                bestTag = j;
            }
        }
    }
    table.setLast(0, id2tag[bestTag]);
    int preTag = bestTag;
    // 0位置打分完毕,接下来打剩下的
    for (int i = 1; i < size; ++i)
    {
        scoreList = computeScoreList(table, i);    // i位置命中的特征函数
        bestScore = Double.MIN_VALUE;
        for (int j = 0; j < tagSize; ++j)   // i位置的标签遍历
        {
            if (!isLegal(j, i, table)) continue;
            double curScore = matrix[preTag][j] + computeScore(scoreList, j);
            if (curScore > bestScore)
            {
                bestScore = curScore;
                bestTag = j;
            }
        }
        table.setLast(i, id2tag[bestTag]);
        preTag = bestTag;
    }
}

注意上面的

 if (!isLegal(j, i, table)) continue;

保证了标签的合法性。

这一步的结果:

坚决	a	ad	+1_v	
惩治	v	v	-1_ROOT	
贪污	v	v	+2_n	
贿赂	n	n	-1_v	
等	u	udeng	-1_v	
经济	n	n	+1_v	
犯罪	v	vn	-2_v

后续处理

有了依存的对象,还需要知道这条依存关系到底是哪种具体的名称。我从树库中统计了两个词的词与词性两两组合出现概率,姑且称其为2gram模型,用此模型接受依存边两端的词语,输出其最可能的关系名称。

最终结果

转换为CoNLL格式输出:

1	坚决	坚决	ad	a	_	2	方式	_	_
2	惩治	惩治	v	v	_	0	核心成分	_	_
3	贪污	贪污	v	v	_	6	限定	_	_
4	贿赂	贿赂	n	n	_	3	连接依存	_	_
5	等	等	udeng	u	_	3	连接依存	_	_
6	经济	经济	n	n	_	7	限定	_	_
7	犯罪	犯罪	vn	v	_	2	受事	_	_

评测

在封闭测试集上效果马马虎虎:

UA: 71.13%LA: 66.51%DA: 66.07%sentences: 20000speed: 1077.6443 sent/s

在测试集上则有待改进:

UA: 60.72%LA: 47.24%DA: 45.48%sentences: 2000speed: 890.4719 sent/s

2014年12月12日更新:

今天改进了特征模板,简单地去掉了B特征,进步非常显著。

封闭测试集——

UA: 78.81%LA: 73.67%DA: 72.59%sentences: 20000speed: 1262.8655 sent/s

开发集——

UA: 67.66%LA: 52.53%DA: 50.16%sentences: 2000speed: 787.40155 sent/s

我上次关于“B特征似乎没有任何用处”的猜测是正确的。

2014年12月14日更新

今天再次改进了特征模板,将前后5个词语的词和词性与其组合作为特征,训练了80个迭代,效果更好了。

封闭测试集——

UA: 91.61%LA: 85.68%DA: 84.94%sentences: 20000speed: 582.42816 sent/s

开发集——

UA: 71.22%LA: 55.02%DA: 52.69%sentences: 2000speed: 513.34705 sent/s

值得一提的是,由于条件有限,模型并没有训练到足够收敛。如果有足够的时间,应该可以得到更加精确的模型。同时模型的体积也达到了466MB,代价很大。

思考

我认为不足之处有三:

  1. 机器性能受限,没有训练到足够收敛

  2. 特征模板没有设计好,B特征似乎没有任何用处

  3. 语料库本身有错误

另外,关于将线性CRF序列标注应用于句法分析,我持反对意见。CRF的链式结构决定它的视野只有当前位置的前后n个单词构成的特征,如果依存节点恰好落在这n个范围内还好理解,如果超出该范围,利用这个n个单词的特征推测它是不合理的。也就是说,我认为利用链式CRF预测长依存是不科学的。

我不清楚论文中标称的80+%的准确率是怎么计算的,我保留意见。

Reference

基于序列标注的中文依存句法分析方法.pdf

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 基于CRF序列标注的中文依存句法分析器的Java实现

分享到:更多 ()

评论 6

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #3

    感謝分享。文中提到的性能問題,可以嘗試下:https://github.com/zhongkaifu/CRFSharp 我對其性能做了很大優化,其完全兼容crf++的模板和語料格式。另外也可以用RNN實驗下:https://github.com/zhongkaifu/RNNSharp

    另外,贊同關於鏈式CRF不適用於依存句法分析的應用。

    monkeyfu5个月前 (02-06)回复
    • 谢谢,我很早就试用过你的CRFSharp,其独有的增量训练功能令我印象很深。这些项目质量很高,我会持续关注的。

      hankcs5个月前 (02-06)回复
  2. #2

    博主你好,请问data中模型文件在哪可以下载?谢谢

    贾圣宾1年前 (2016-02-20)回复
  3. #1

    为啥所有的Reference连接都不能下载呢?

    JerryLu的早晨1年前 (2016-02-04)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机