基于统计机器学习的序列标注模型算法与应用
毕业论文关键词：中文分词，感知器算法，文特比算法
Title The Algorithm and Application of Sequence Tagging ModelBased on Statistical Machine LearningAbstractChinese word segmentation (CWS) is basic tasks in natural language process (NLP) .Character-based approaches is now the main method in CWS task. In the currentcharacter-based segmentation tools, most of them are based on Conditional RandomFiled (CRF) model, Hidden Markov Model (HMM) , and Maximum-entropy Markov Model(MEMM). In this paper, a new method based on Perceptron algorithm is introducedfor CWS task.First, in this paper, we used the traditional feature templates to do somestatistical work on the corpus. After that, we obtained the corpus statisticalinformation and corpus feature vectors. The corpus statistical informationinclude,for the n-tag system, the initial probability of each tag and transferprobability of each tag to another. Secondly, we use the corpus feature vectorsto train a multi-class perceptron as a classification problem. In CWS task, thecharacter-based tagging method reformulate CWS task to a sequence tagging task.So, in the third part, we use the perceptron we trained before, combine with theViterbi algorithm to solve the best tag sequence for given sentence.Experimental results show that, our sequence tagging method based on perceptronis able to give a good performance on CWS task.keywords Chinese Word Segmentation, Perceptron Algorithm, Viterbi Algorithm
目 次
1 引言 1
1.1 课题背景.. 1
1.2 国内外研究现状.. 1
1.3 本文结构.. 2
1.4 本章小结.. 2
2 相关理论介绍.. 3
2.1 基于字标注的分词方法.. 3
2.2 特征模板.. 4
2.3 感知器算法及多类感知器算法.. 6
2.4 数据集 8
2.5 性能评价.. 9
2.6 本章小结.. 9
3 语料处理及感知器训练.. 10
3.1 字标注系统与感知器. 10
3.2 语料预处理工作 10
3.3 训练感知器.. 12
3.4 感知器输出.. 15
3.5 本章小结 15
4 基于文特比算法的分词算法 16
4.1 文特比算法.. 16
4.2 文特比算法与感知器的结合. 19
4.3 利用文特比算法寻找最佳分词结果. 20
4.4 本章小结 21
5 算法实现.. 22
5.1 语料预处理算法实现. 22
5.2 感知器训练算法实现. 24
5.3 文特比算法实现 25
5.4 分词算法实现. 26
5.5 小结.. 27
6 实验. 29
6.1 实验结果 29
6.2 不同参数设置的影响. 30
结论. 32
致谢. 33
参考文献.. 34
1 引言1.1 课题背景伴随信息化技术的发展，互联网上的信息量呈指数增长，我们对海量文本信息的处理需求变得愈发迫切。单纯依靠人工处理的速度早已不能跟上信息的产生速度，于是越来越多的研究人员着手于利用计算机进行快速、准确的文本信息处理。与英语等西方语言的文本资料不同，中文文本资料的词与词之间是没有天然的分割标志的，因此中文分词是中文自然语言处理任务中必要的基础步骤。近年来有关机器学习理论的不断发展，使得机器学习算法渐渐有能力处理复杂的任务。在监督学习(supervised learning)方面，算法的能力也不再局限于简单的分类问题。序列标注问题长期倍受关注，因此进入了机器学习研究者的视线。序列标注模型中，如隐马尔可夫模型（HMM）、条件随机场（CRF），在自然语言处理、语音识别、生物信息、模式识别等领域有着广泛的应用。本课题应达到的目的，是理解和掌握基本的序列标注模型（如 HMM、CRF），基于 Python 或 C/C++设计实现一种基本的序列标注模型，并将之应用到汉语分词等应用中。1.2 国内外研究现状过去的十余年间，特别是在 2003 年国际中文分词评测活动Bakeoff 开展之后，中文自动分词技术取得了可喜的进步。[4]在 2002 年之前，中文的自动分词方法是基于词或词典的，以此为基础又可以分成基于规则和基于统计的两大类方法。[4]在此之后，基于字标注的分词方法渐渐崭露头角，并逐渐成为主流方法。在 Bakeoff-2005 上，Low的系统采用最大熵模型，在四项开放测试中夺得三项冠军(AS, CityU, PKU)和一项亚军(MSRA)。 Tseng 的系统采用条件随机场模型，在四项封闭测试中取得两项冠军(CityU, MSRA)、一项亚军(PKU)和一项季军(AS)。到了Bakeoff-2006，基于字标注的分词系统已遍地开花。[4]然而现有的基于字标注的方法在跨领域中文分词中不具有健壮性，因为它们在模型中采用的表面特征经常对不同领域中的同一个字符建立不同的标注分布。为了达到更高的精度，有研究者提出使用字典信息辅助字标注系统，提升系统表现。[5]该研究者在论文中推荐了一种新的抽象聚合候选特征，该特征可以指示分配的标注是否符合对应最长字典匹配词中对应字符的位置标注。使用这种新型的具有领域不变性的特征，他们之后推导出一种用于多领域中文分词的新型增强生成式模型来解决这一问题。实验结果证明该方法确实可以提高系统的精度，并使系统在处理未登录词时表现更佳，推荐模型在不同 OOV 覆盖率下的健壮性并且优于 5 个语料中 3 个的最佳系统。因为互补性，推荐模型进一步整合了增强判别式方法。在公共外部字典的帮助下，在 SIGHAN-2005 和 CIPS-SIGHAN-2010 上的实验表明整合模型优于开发测试中的其他所有系统，并在5 个不同的领域上取得最佳F 值。[5]在现有的基于字标注模型的分词工具中，大多数基于条件随机场(CRF)、隐马尔可夫模型(HMM)或最大熵马尔可夫模型(MEMM)开发。这些工具都有大致类似的训练、使用的过程。然而这些模型都是概率模型，是对标注(tag)概率分布建模的。模型训练完毕后便再不可更改，不具备在线学习的能力。当前自然语言处理发展有一个特点，那就是统计数学方法越来越受到重视。[15]基于字标注的方法主要使用的是序列标注模型，如隐马尔可夫模型(HMM)、条件随机场(CRF)等，为了实现课题要求中可实现在线更新学习(online update)的算法，感知器算法是很好的选择。1.3 本文结构本文的结构采用逐层深入的方式展开，从理论到设计再到实验。第二章对相关理论和指标进行详细的介绍，为本文设计作理论性解释；第三、四章简要介绍分词算法的设计，展示算法设计中某些值得注意的细节，；第五章将具体介绍算法实现，对核心代码进行介绍；第优尔章展示实验结果，对结果进行简要分析。最后对全文作了总结并感谢了在此过程中提供帮助的人。1.4 本章小结本章课题的研究背景作了简单的分析，让读者对课题有了一个浅层次的概念。同时，对课题的研究意义做了阐述，增加我们探索的动力。信息化加速了中文分词技术的提高，也为我们带来了无限激情去钻研。2 相关理论介绍2.1 基于字标注的分词方法在 2002年之前，中文的自动分词方法大多数都是基于词或词典的，以此为基础又可以分成基于规则的或基于统计的方法。[4]第一篇基于字标注(Character-Based Tagging)的分词论文发表在 2002年第一届 SIGHAN 研讨会上， 遗憾的是当时并未引起学术界的重视。 [4]一年之后，Xue 基于最大熵模型(ME)实现的基于字标注的分词系统参加 Bakeoff-2003 评测，取得了不错的成绩，并且该方法其 OOV 召回率位居榜首。由于未登录词对分词精度的影响比分词歧义至少大 5 倍以上[4]，人们自然很看好基于字标注的分词方法。这一预测在 Bakeoff-2005 上得到了印证。在此之后， 基于字标注的分词方法渐渐崭露头角， 并逐渐成为了主流方法。 在Bakeoff-2005上，Low的系统采用最大熵模型，在四项开放测试中夺得三项冠军(AS, CityU, PKU)和一项亚军(MSRA)。Tseng 的系统采用条件随机场模型，在四项封闭测试中取得两项冠军(CityU,MSRA)、一项亚军(PKU)和一项季军(AS)。到了 Bakeoff-2006，基于字标注的分词系统已遍地开花。[4]以往的分词方法，无论是基于规则还是基于统计的，都依赖于一个实现编制好的词典(Dictionary)或词表(Vocabulary)。中文自动分词的过程就是反复查询词典或词表以及相关信息对当前字串做出是否切分的决策。实际上基于字标注的分词方法是一种构词方法，即将分词过程中原来的分割、切分的思想转化为了由字组词的序列标注问题。[6]换句话说，这将原有的切分问题转化为序列标注问题，而这一关键步骤是通过使用标注系统来完成的。在众多的标注系统中，4-tag 系统，也称为 BMES 标注系统获得了最广泛的应用。以下我们将以这种标注系统为例，介绍具体的标注方法。4-tag 标注系统下，句子中每个字依据其出现的位置，都有一个不同的标注。B(begin)代表词的开始，M(middle)代表词的中部，E(end)代表词的结尾，S(single)代表单字词。如下面这个例子：分词结果：我 爱 北京 天安门 。标注结果：S S B E BME S首先需要说明的是，基于字标注的分词算法中提到的“字”不仅指汉字。考虑到真实中文文本中不可避免地会出现非汉字字符，“字”因此也包括外文字母、阿拉伯数字和标点符号等。所有这些字符都是构造词的基本单元(unit)。[4]使用以上这样的标注系统，我们就可以把中文分词这一原本为切分的问题转化为序列标注问题。[17]对于一个未分词的句子，如果能够对每个字分配一个标注，就等同于知道了分词结果。通过这样的问题转化，很多机器学习方法在分词领域得到了应用。此外，因为汉语本身的某些性质，有的字会以很大的概率出现在词的固定位置上，例如“我们”中的“们”，一般出现在词的结尾，而“花”则可能出现在词的头部或尾部，如“花瓣”，“樱花”等。使用序列标注算法，可以用相对固定的字的位置信息来推断相对不固定的字的位置信息。同时，在本文的工作中，我们把转换后的标注系统看成是 4 个类别，而把序列标注看成是一个分类问题，句子中的每个字被分为B、M、E、S 四类。此外，把分词过程转换成序列标注问题的重要优势是：它平等的对待登录词(IV)和未登录词(OOV)的识别问题。在这种分词技术中，登录词和未登录词的识别都用统一的字标注过程，不必强调登录词信息，也不用专门设计未登录词识别模块。总而言之，基于字标注的分词方法将分词从一个切分过程转化为字重组的简单过程，然而这一简单处理带来的性能提升却是令人满意的。