摘要：最大熵方法，特别是最大熵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.

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