不知道从上个月哪天开始，conll08评测的结果公布栏开始接受赛后结果。上面说好，这个不影响正式排名，有了更好的结果可以发给组织者，然后他们把分数放到公布栏中，如同往届那样。
地址 http://www.yr-bcn.es/dokuwiki/doku.php?id=conll2008:results
最开始的时候日内瓦大学提交了一个更新的结果，大大更新了在句法依存上的分数，从原来的第4追到第2。没两天，第一名的lund大学的大大更新了他们的语义依存的成绩，让他们的成绩更加遥不可及。又过了没几天，加泰罗尼亚理工的lluis大大更新了他们的句法依存成绩——他们往届conll成绩一直靠前，可惜这次被句法依存拖了后腿，总分屈居倒数第二，而这此赛后更新猛赶8个名次，算是挽回了点面子。
昨天早上我看不下去了，把我几天前轻微改进的句法依存结果提交了上去（语义依存的性能提升是连带性的，其实我没有改进这部分），傍晚的时候mihai回信，说加上去了。现在我的总分排在第三了，句法部分的分数排在第二。我打开页面，开心了没几分钟，无意刷新了下，发现yahoo的ciaramita也更新了他们的结果。太巧了。他们也是改进了句法依存，但是他们的语义部分很强悍，所以我的总分第三只是维持了几分钟。好在暂时没有人撼动我的句法第二的位置。
不过现在哈工大的结果后有追兵,前有堵截。这游戏越来越好玩了。

昨天提到我怀疑conll08的open test任务提供的maltparser性能不佳, 今天想起来顺便跑了下打分程序. 果然证实了我的猜测.

下面是open feature所提供的maltparser在4个测试和开发集上的成绩
data        LAS    UAS  label-acc.
===========================================
devel      84.10  87.66  89.18
wsj        85.50  88.41  90.41
brown      77.06  82.67  83.60
wsj+brown  84.56  87.77  89.66

下面是所提供的maltparser在所有closed test参加者的句法依存序列中的LAS排名,总计20个closed结果.
maltparser输出排在17位.由于太低(<80%),我认为最后三位的句法依存结果不能算作正常的成绩.
LAS         wst+brown  wsj    brown
===================================
1 st         89.32     90.13    82.81
16 th        84.82     85.69    77.83
maltparser   84.56     85.50    77.06
17 th        84.47     85.20    78.58

不知道这个maltparser在哪里训练的,如果是在去年的数据上训练的,应该是情有可原的,因为去年的english句法分析的训练语料是一个大杂烩,训练规模也仅为今年的一半. 这样所给出的maltparser性能其实并不能算太差, 可能只是不太拟合今年的数据吧.
但总的来说,以这样的一个分析器来做open test的句法依存输入不是一个成功的做法.

继而想到,如果我利用这个open test的句法依存输入作为基础,仅运行我提交的那个srl模块会怎样?
我想这会是一个有趣的对比, 下面是结果.

总分 macro-f1:
            wst+brown  wsj    brown    devel
==============================================
mine        80.08     81.29   70.26    79.55
best-open   79.61     80.61   71.45    -

best-open是open test总分第一的选手.

句法依存 LAS of syntactic parsing:
                wst+brown  wsj    brown    devel
==============================================
mine(maltparsr) 84.56      85.50  77.06    84.10
best-open       87.32      88.14  80.8     -
这部分比较其实是open test的maltparser输出和参赛者的结果比较, 和我没关系.

语义依存 labeled-f1 of semantic parsing:
              wst+brown  wsj    brown    devel
==============================================
mine          75.55     77.02   63.39    74.90
best-open-srl 76.17     77.38   66.23    -
best-open     71.89     73.08   62.11    -

best-open-srl是仅仅单独参加了srl部分的open test的最优选手.
结果说明,我的系统比best-open更加平衡, 他的句法部分做得相当好, 很大程度上克服了不佳的maltparser输入(考虑到他的open句法性能和closed句法性能一模一样,我猜测他早就发现了问题因而完全抛弃了open test给的这个句法输入,而自己单独搞了一套),但是他的语义依存部分脱了太大的后腿. 至于best-open-srl,他只做srl,虽然大致在一个水平线上, 他的系统性能的确轻微的好于我的srl子系统.


关于srl子模块的评估问题，我想起来前几天给mihai写了封信，建议他加入一个新的rank list，使用一个比值semantic-F1/syntactic-LAS来评估单独的SRL子系统的性能，我的理由是SRL部分过于依赖syntactic parsing部分的性能，因而不是像句法依存部分那样独立。mihai热情的回信说，他喜欢这个主意，但是还要考虑下怎么做。我猜测他一定在苦恼，如果真的列出一个这样的表格的话，那么那个排在最后一位的不正常的结果要跳到第一位了，这个动静也太大了。：）

没有更新blog已近两个多月，都是conll-2008招惹的，事情起源于去年年底kit转发的一封newsletter，说今年要办一个输入很少，输出很多的自然语言学习任务：基于依存的句法和语义结构的联合推导（当然实际的要求比这个说法要更加复杂，我在4月中旬给主办者Mihai写了封弱弱的信问了些初级问题，才知道本次任务还包含一个语义消岐问题），问我有无兴趣。那时候我还不知道什么是dp和srl，只好笼统地回答说，如果那个跑crf的机器允许的话，可以试下。但1月2月在南亚和中东各奔波了一半的时间，浪费了大好时间去深入学习理解dp/srl。好在总算利用春节的几天把最大熵写了一个出来。考虑到效率因素，决定以后的机器学习就用这个跑了。虽然种种迹象表明现在的计算语言学界中svm更加时髦，但是svm天文般的训练时间自从读博士以来就已经把我吓怕了好多年。至于将来能否用svm要看 intel,amd以及nvidia的表现了（记得某次开会我曾经建议买台ps3来跑crf的，自然是被鄙视）。随后，我用自己写的最大熵先跑了下传统的分词ner，继而用词性标注作了下验证，结果在bakeoff-4的成绩单中很靠前，至少前三名之列，恩，考虑到第一名事实上用了一个双向最大熵，这个结果至少说明我的最大熵实现没什么大毛病，可以放心的拿它用于后面的任务了。

下面我的教训说明，仔细阅读任务说明是多么重要的事情：从2月下旬开始，我在conll-2004的数据上跑了一个月，一直到3月中旬发现单个训练时间以星期为单位的时候，我才觉得应该利用这个空挡看看怎么做依存句法分析（dependency parsing,DP）——这时候我其实还没有发现我的错误。无从下手之下，给dp前辈陈文亮（他参加了去年的关于dp的conll）写了封email，请教了很多初级的问题，总算知道dp是要做什么的了。然后又花了一个星期的时间，在最大熵上面（不顾nivre在论文中的反复警告：使用最大熵跑它的算法，性能不会高），对照nivre那些拗口的论文写了一个移进规约算法（昨天才知道nivre在2月份就公布了一份java版本的maltparser源代码，ft）。调试，让它能够正常工作，给出了些正常的结果，不知不觉时间到了4月中旬。在一个被nivre认为没有前途的分类算法上，我只用一个model所作出的性能看来也就这样了。于是随意看了看早就发布了的训练数据的格式，才惊讶的发现SRL部分的标记似乎都只有一个词，慌张地写了封email问mihai，弱弱的问是不是今年的srl只用标出argument的开头，另外，predicate标记的那些末尾数字是什么意思，名词述语和动词述语的区别又不太像。虽然回信显得很富有耐心，我还是猜想mihai一定是以郁闷的心情写他的回信的：那个srl标记不是argument的开头，是中心词（head），至于末尾的数字，那是sense的编号。看了回信，急急忙忙去看官方网站的任务描述，dependencies这个词在文中到处都是，顿时想起很多年前考试，经常题目没有看清楚就匆忙答题的窘境，暴汗中。。。

好在这个时候dp已经不准备做改进了，可以专心作srl。结果鬼使神差居然用nivre算法作了大半个月的依存srl。浪费了最最宝贵的一段时间后，5月初才发现名词述语predicate和argument是同一个词的情形依然无法有效识别，而且这种情形所在比例还不小，因而不能忽略。这个不幸的原因也很简单，我实现的nivre算法只能对root标注缺省label。推倒重来后，使用直接的词对分类，这样返璞归真反而作下来了。然而所剩时间也不多了，好在5月9日发布测试数据，5月16日才需要提交测试结果，而我居然在利用这段时间做特征工程。

提交结果前，心里很没底，因为这种复合任务是第一次提出，根本没有往届的数据作指示，不知道什么范围的f-score是正常的。通过同事的关系，和哈工大的同行交换了下结果，才知道应该没事，所谓没事，就是不会垫底。我计划跑三个最终的model。第一个model在开发集上的系统总分和哈工大的结果差2个多百分点，好在他们友好的指出，我用的评估程序的版本过时了，因此实际差距没那么大。我的第二个model的差距已经在1%以下了，这也是我最终提交的model。第三个model很遗憾没有及时跑出来，它是在结果出来的那天才出来的，虽然其差距已经在0.5%以下。

周五提交的测试结果，周一晚上系统排名就出来了，不得不佩服组织者的效率。结果很意外，以微弱的差距低于第三名的srl老将ciaramita（目前在yahoo，等待微软收购中？）而排名第四，和哈工大的结果的测试集总分差距是1.2%，基本上全部是由于srl导致的，可见他们在这个领域的确有一手。但在句法依存上，综合开发集上的成绩，我的结果实际上要好些。导致我的句法依存的正式成绩拖后的是那个out-of-domain的brown测试语料。不过，这是不是恰好说我的系统有点overfitting ?

观察结果，发现了些有趣的现象。

0. 50个人报名，最后仅有23个研究小组提交结果。其中18个提交closed, 2个提交open+closed,1个提交open，2个仅提交open的srl。很佩服那两个同时提交open+closed的队伍，至少我很羡慕他们的计算服务器。他们的共同点是：提交者都是中国人。

1．关于句法依存分析：第一名的瑞典人的wsj结果总分的LAS高达90%，第二名及其之后的结果均小于88%，考虑到今年的数据需要标注复合词内部的依存，这导致句子的平均长度加大，90%这个结果很不容易。去年conll评估的英语上的最高成绩为89%（训练数据为今年的一半）。我猜测瑞典人的结果要么用了复杂的nivre组合模型，要么用到了二阶mcdonald特征，要么作了一个完美的syntactic+semantic的joint learning。无论哪种，惊人的计算量是不可少的。

2．关于句法依存分析的20个closed结果中，有7个结果，包括我，LAS在86.60-86.69%之间（浮动范围为0.1%）。如果考虑浮动范围86.0-86.9%的LAS(1.0%的浮动范围)，那么能覆盖10个也就是一半的结果！这强烈说明，当然属于我的继续猜测，86.5%左右的LAS代表了某种依存句法的性能瓶颈。

3．如果我没有记错，本次的conll是首次成功引入open test的SRL，之所以是首次，是因为往届的SRL评测从未得到过响应。：（ 不过，虽然理论上open性能应该高于closed性能,  本次open test的结果普遍差于closed test的结果，最好的open总分 的成绩排在closed第7名的位置，最好的单独的open的srl的成绩排在closed的srl第4名的位置(比我的closed srl的成绩恰好高0.01%, :-)) 。而且，完整的open test,包括dp+srl只有三个参与者，另外有两个参与者仅仅参加了srl部分的open test（可能他们无力开发依存句法分析器）。Open测试的语料和closed 不同的地方在于，它额外提供了命名实体标记，ciaramita的supersense标记，以及nivre的maltparser的依存句法输出。有两位选手，同时参与了open 和closed测试，其中dfki的open总分轻微好于closed总分,另外一个则是open总分<closed总分。有意思的是,他们的open dp成绩和closed dp成绩都是一样的, 不管是增长还是减少, open和closed总分差距均来自srl部分. 虽然组织者声称他们在用一个state-of-the-art的parser，考虑到srl的效果非常依赖于句法依存的输出，这个关于open test的负面结果让我怀疑这个用于open测试的maltparser其实不会好于大多数参赛者自己开发的依存句法分析器, 还有一个因素就是, 目前句法语义分析的联合学习还处于比较低的水平, 参加者普遍不能有效的综合两者的输出。

4．前所未有地，这次有6个国内研究团队（包括我）参与了本次conll评估，如果我没记错，即使加上港澳台，最近4届参与的国内队伍从未超过3个。这次参加的国内队伍包括：哈工大、哈工大深圳研究院、北大，中科大，苏州大学，以及我。苏州大学参加的是open test，哈工大深圳研究院同时参加了open+closed，其他的都是只参加closed test。

摘要：最大熵方法，特别是最大熵Markov模型，很大程度上启发了流行的串标注框架CRF。然而在一个一致的环境中比较这两种方法的性能差异还是一个有趣的工作。特别是在中文标注语料学习中，这种比较还未见报道。在两个领域，分词和命名实体识别上，本文的经验比较说明在适当的解码条件下，最大熵方法可以取得和crf接近的性能。

1。背景
在字标注的中文语料学习中, 最大熵和CRF获得了广泛的应用. 由于追求更高的性能的需求, 最近有利用CRF取代MaxEnt的趋势. 然而, MaxEnt方法在训练效能上的优势始终存在. 因此,标注学习领域依然有MaxEnt方法存在的空间.本文考察并比较了最大熵及其变体以及CRF在字标注学习上的性能.

最大熵（maxent）是一个分类器。原则上说，不适合结构化学习。因此，一般要用两个技巧来使其适应结构化学习的需要。以串标注为例。
1.1规则空间解码
考虑maxent对于一个未知串中的第k个样本c_k给出分类预测的概率分布p_ki, i=1,2,...,n，分别对应于标记L_i。且
\sum_i{p_ki}=1
同时，我们考虑两类规则约束。
第一类是词典约束，例如，对于c_k，{L_i}的某个子集才是可以考虑的标记空间。在这种情形，对于c_k的标注，我们选取L_i，其p_ki在可选的标记空间是最大的。在这种约束下的解码本质上还是分类问题，因为没有考虑上下文。
第二类约束是状态转移约束。这种约束，可以表达为c_{k-n},c_{k-n+1},...,c_{k-1}标注为L_{k-n},...,L_{k-1},则c_k必须标注为L_k。因此这种类型的解码是要寻求
max_{状态转移约束}\pi_k p_{ki}
通常这个最大联合概率可以通过标准的viterbi解码算法获得解码序列。

这两类约束条件均可通过搜集训练语料中的信息获得。

1.2 最大熵Markov模型(MEMM)[1]
将最大熵和HMM结合起来是一个直观的想法。MEMM在训练和MaxEnt一致，区别仅仅在于解码的时候需要考虑激活特征所包含的状态转移条件约束。解码算法也类似于状态转移约束下的MaxEnt解码。

2。实验
2.1 语料
分词:bakeoff-4的CTB切分语料
     Bakeoff-1和Bakeoff-2的CityU切分语料
选择bakeoff-4的CTB语料的原因是Xue Nianwen在[2]中用的也是ctb语料进行评估.我们假定同样来源的语料保持一致的统计机器学习特性.选择两个CityU语料的原因是它们是唯一一种在bakeoff-1,2上都出现,并且训练集发生改变的语料.此外,Xue在CityU-2003上报告了结果[3]. Low et al.在CityU-2005上报告了结果[4].
NER: Bakeoff-3的MSRA语料

2.2实验设置
实验表明,抽取自训练语料的词典约束对于性能没有帮助.因此不在这个设置下进行比较.
对于状态转移规则,只考虑一阶状态转移.同时额外考虑两种串开始和结束约束.第一种,串起始限制,包含所有那些出现在串头的标记.第二种,串结束限制,包含所有那些出现在串尾的标记.所有这些规则均自动地收集自相应的训练语料.

标注集
分词,分别使用4词位和6词位标注集
     ngram特征模板
     5字窗口模板:C_i,i=-2,-1,0,1,2; C_iC_{i+1},i=-2,-1,0,1,以及C_{-1}C_1
     3字窗口模板:C_i,i=-1,0,1; C_iC_{i+1},i=-1,0,以及C_{-1}C_1
NER 6词位标注集
     ngram特征模板仅使用3字窗口模板
在MEMM中,状态转移特征将分别考虑1阶和2阶特征,即,t_{-1}和t_{-2}t_{-1}.

性能评估一律为f-score.

2.3实验结果

================================================================================================
分词:
------------------------------------------------------------------------------------------------
CTB4
MaxEnt
4-tag+5字窗口 0.9386(字分类) 0.9496(状态转移约束下解码)
4-tag+3字窗口 0.9288(字分类) 0.9507(状态转移约束下解码)
6-tag+5字窗口 0.9396(字分类) 0.9496(状态转移约束下解码)
6-tag+3字窗口 0.9291(字分类) 0.9505(状态转移约束下解码)

MEMM
4-tag+5字窗口 0.9386(+1阶状态转移特征) 0.9391(+2阶状态转移特征)
4-tag+3字窗口 0.9231(+1阶状态转移特征) 0.9241(+2阶状态转移特征)
6-tag+5字窗口 0.9384(+1阶状态转移特征) 0.9384(+2阶状态转移特征)
6-tag+3字窗口 0.9236(+1阶状态转移特征) 0.9235(+2阶状态转移特征)

MEMM 下面附加状态转移约束解码不会导致性能发生改变.

使用CRF,6-tag+3字窗口,1阶状态转移特征,性能0.953.MaxEnt下面给出的最优结果大致差0.002

------------------------------------------------------------------------------------------------
CityU-2003
4-tag+5字窗口 0.9278(MaxEnt字分类) 0.9423(MaxEnt字分类+状态转移约束下解码)
              0.9255(MEMM,order-1) 0.9263(MEMM,order-2)
6-tag+3字窗口 0.9189(MaxEnt字分类) 0.9456(MaxEnt字分类+状态转移约束下解码)
              0.9147(MEMM,order-1) 0.9143(MEMM,order-2)

Xue在[3]中使用 4-tag+5字窗口的order-2 MEMM给出的结果0.9143.需要说明的是,[3]中Xue使用了两个MEMM分别完成正向和逆向的串解码.同时他使用一个TBL方法来校正非法的标注序列。和CRF一样，MEMM其实不会给出非法的标记串序列，除非训练集本身包含错误。至于Xue的结果比我差的原因，我认为可能是他的训练参数未达到最优。
使用CRF,6-tag+3字窗口,1阶状态转移特征,性能0.9473.MaxEnt下面给出的最优结果大致差0.002.


------------------------------------------------------------------------------------------------
CityU-2005
4-tag+5字窗口 0.9318(MaxEnt字分类)
              0.9466(MaxEnt字分类+状态转移约束下解码)
              0.9333(MEMM,order-1) 0.9322(MEMM,order-2)
              +字符类别特征            
                   0.9422(MaxEnt字分类)
                   0.9550(MaxEnt字分类+状态转移约束下解码)
             
6-tag+3字窗口 0.9168(MaxEnt字分类)
              0.9469(MaxEnt字分类+状态转移约束下解码)
              0.9132(MEMM,order-1) 0.9154(MEMM,order-2)
              +字符类别特征
                   0.9281(MaxEnt字分类)
                   0.9520(MaxEnt字分类+状态转移约束下解码)
             
Low et al.在[4]中使用 4-tag+5字窗口的(MaxEnt字分类+状态转移约束下解码+字符类别特征)给出的结果0.950.
使用CRF,6-tag+3字窗口,1阶状态转移特征,性能0.9476，加入字符类别特征后，0.9563。


================================================================================================
NER

MSRA-2005
6-tag+3字窗口 0.6617(MaxEnt字分类) 0.8313(MaxEnt字分类+状态转移约束下解码)
              0.7170(MEMM,order-1) 0.7186(MEMM,order-1,+状态转移约束下解码)
              0.7234(MEMM,order-2)
使用CRF,6-tag+3字窗口,1阶状态转移特征,性能0.8528.   

================================================================================================

3.结论
3.1
和期望的一样,MEMM优于完全基于分类器思想的MaxEnt,高阶的MEMM由于较低阶的MEMM. 然而,在字标注学习中(我谨慎的把下面的结论放在这个前提下),MEMM不敌MaxEnt+状态转移约束解码. MaxEnt+状态转移约束解码相比纯粹的MaxEnt算法, 性能上带来戏剧性的增长. 注意到由于2阶MEMM有时候轻微的好于1阶MEMM. Xue最开始可能被2阶MEMM的性能所误导. 这导致他虽然第一个吃到苹果,但不是吃得最多的人.
3.2
MaxEnt+状态转移约束解码轻微的弱于CRF(f-score性能差在分词上是0.002,在NER上0.02).但是,通常,前者的训练时间是后者的1/5-1/10.


参考文献
[1] Andrew Mccallum, Dayne Freitag, Fernando Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, In Proceedings of the 7th International Conference on Machine Learning (ICML 2000): 591--598.
[2] Nianwen Xue. 2003. Chinese Word Segmentation as Character Tagging. International Journal of Computational Linguistics and Chinese Language Processing, 8(1):29-48.
[3] Nianwen Xue and Libin Shen. 2003. Chinese Word Segmentation as LMR Tagging, In  Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing, in conjunction with ACL'03. Sapporo, Japan.
[4] Low, Jin Kiat, & Ng, Hwee Tou, & Guo, Wenyuan (2005). A Maximum Entropy Approach to Chinese Word Segmentation. Proceedings of the Fourth SIGHAN Workshop on Chinese Language Processing. (pp. 161-164). Jeju Island, Korea.

本文的增强版本已经投杂志.