放牧代码和思想
专注自然语言处理、机器学习算法

序列标注模型算法比较

目录

偶然浏览到一篇挺有实际参考价值的论文Nguyen and Guo(2007)。该文比较了一些模型和算法在词性标注和OCR任务上的性能,包括HMM、CRF、AP、Structured SVM、M3N、SEARN算法以及SLE算法,对算法选型很有指导意义。这篇博客随手记录一些要点。屏幕快照 2016-09-14 下午5.31.38.png

结构化学习模型

多分类SVM

在论文中用做基线模型,大意是把序列标注问题退化成多个分类问题。

屏幕快照 2016-09-14 下午4.25.36.png

这里的phi是特征函数。

结构化SVM

相较于多分类SVM,唯一的变化是在函数间隔的约束条件中引入损失函数delta:

屏幕快照 2016-09-14 下午4.37.27.png

作者这个目标函数是不是贴错了啊,少了一个分母n,难道不应该是下面这样的吗?

屏幕快照 2016-09-14 下午4.39.26.png

上式引用自《结构化支持向量机学习方法及应用研究》。

Maximum Margin Markov Networks

中文名叫最大间隔马尔可夫网,大意就是定义一个序列标注y上的完全图。给每条边定义一个势函数:

屏幕快照 2016-09-14 下午4.56.02.png

其中phi_k为第k个特征函数。由于边的数量是固定的,所以定义在整个实例上的特征函数:

屏幕快照 2016-09-14 下午5.01.46.png

马尔科夫网模型最大化如下联合条件概率分布:

屏幕快照 2016-09-14 下午5.08.22.png

M3N通过间隔最大化原则求解权值向量w,思想跟SVM的结构风险最小化是一样的,于是就具有SVM的优点。

国内有《基于最大间隔马尔可夫网模型的汉语分词方法.pdf》可供参考。

平均感知机

最近的新欢,请参考:

感知机

200行Python代码实现感知机词性标注器

基于结构化平均感知机的分词器Java实现

SEARN

从搜索的角度看待序列标注,用多分类标注器做序列标注。还没仔细看论文,感觉像是拍脑袋拍出来的算法。

CRF

大家都爱的CRF:

条件随机场

CRF++代码分析

HMM

隐马尔可夫模型

SLE

一种融合多个多类别分类器为结构化预测的算法。加了个转移矩阵,乘以对每个类别的表决票数,用viterbi搜一遍。

粗略看了看公式,大概就是这样了,实验室产物,我发明不了新模型,但我可以融合多个旧模型美其名曰SLE、stacked learning之类刷分数水论文啊。

试验

做了两组试验,一组词性标注,一组手写字母OCR。

调参

每个模型能调的参数调到最优:

屏幕快照 2016-09-14 下午5.30.27.png

词性标注试验结果

在不同的训练规模下的误差率,越低越好。

屏幕快照 2016-09-14 下午5.31.38.png

表格形式:

屏幕快照 2016-09-14 下午5.33.00.png

大出意料啊,你一个基线多分类SVM误差那么低让人情何以堪!这验证了200行Python代码实现感知机词性标注器作者“对词性标注而言不必操心搜索算法”的论点,如果一个分类器每次预测的误差都很小,那么转移矩阵的作用就可以忽略不计了。

还有训练时间:

SVMmulticlass 1.8m, SVMstruct 6.8m, M3N 12h, Perceptron 6.4m, SEARN 2.1m, CRF 0.53h, HMM 0.23s.

也体现了SVM的优势。

OCR结果

屏幕快照 2016-09-14 下午5.38.43.png

结论是类似的,除了论文作者的亲儿子,SVM的性能最好。

结论

忽略论文作者亲儿子后,结构化SVM是最棒的。

结构化SVM实现

康奈尔大学的C实现:https://www.cs.cornell.edu/people/tj/svm_light/svm_struct.html

有空看看,验证一下。

Reference

Comparisons of Sequence Labeling Algorithms and Extensions.pdf

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 序列标注模型算法比较

分享到:更多 ()

评论 5

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

    只要特征够多,svm类算法效果肯定不会太差。直观感觉应该类别越多,crf效果越好,比如{B,M,E,S}*100类这种情况下搜索算法还是能起一些作用的。 还没实验过。

    赵耀diego11个月前 (11-03)回复
  2. #3

    博主,词性标注用的是什么语料,能分享吗

    Break_jiang12个月前 (10-09)回复
  3. #2

    你好,一直想勾搭几个同是信仰技术的小伙伴一起做一个充分发挥个人价值的小团队,做一个能带来社会价值的,并且用心的产品。
    我找到你,是因为你的博客 feed 早早地就被我列为了关注对象(https://github.com/t-k-/tkfeedr/tree/master/list)。至于为什么,是因为我发现了你具备了能自己管理好自己的主动、优秀的素质(比如有自己的独立而漂亮的博客、Github上活跃参与)。你可以不是名校毕业,但发自兴趣的热爱技术比什么都重要。在这诚邀你加我的微信:https://approach0.xyz/tkblog/wechat.jpg
    我将会组建一个充满和你同样对技术有热情的人的微信群。我们一起畅谈理想和技术。

    钟 威1年前 (2016-09-27)回复
    • 好的,已发你邮件。

      钟 威12个月前 (10-05)回复
  4. #1

    MARK

    ReidHolmes1年前 (2016-09-15)回复

我的开源项目

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