摘要本文利用隐马尔可夫模型( Hidden Markov Model,简称.pdf

《摘要本文利用隐马尔可夫模型( Hidden Markov Model,简称.pdf》由会员分享，可在线阅读，更多相关《摘要本文利用隐马尔可夫模型( Hidden Markov Model,简称.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 基于隐马尔可夫模型和候选排序的汉语基本名词短语识别基于隐马尔可夫模型和候选排序的汉语基本名词短语识别*马艳军 刘 颖 清华大学中文系计算语言学研究室 北京 100084 E-mail:yj- 摘 要：本文利用隐马尔可夫模型（Hidden Markov Model，简称HMM），并利用A*启发式搜索算法得出N-Best最优路径作为汉语基本名词短语标注的候选集。利用边界匹配和基本名词短语模板对候选集进行过滤，并利用基本名词短语模板的可信度信息对候选集进行重新排序，取得了不错的标注效果。本文的实验模型有较强的鲁棒性和可扩展性，能够通过不断添加不同领域的知识来提高性能。关键词：汉语基本名词短语，隐马

2、尔可夫模型，基本名词短语模板，短语模板的可信度，过滤规则 Base Noun Phrase Identification Based on HMM and Candidates Sorting by Weighted Templates Ma Yanjun Liu Ying Computational Linguistics Laboratory,Department of Chinese Language and Literature,Tsinghua University,Beijing,100084 E-mail:yj- Abstract:This paper uses HMM appr

3、oach and heuristic decoder to get candidates of Chinese base noun phrase tagging.We filter the noisy candidates by applying boundary match rule and phrase template match rule.Furthermore,the candidates are sorted according to the reliability of the base noun phrase templates they matched.This is a r

4、obust model.The performance is expected to be further improved by adding new features.Key words:Chinese base noun phrase;HMM;base noun phrase template;the reliability of phrase template;filter rules 1 引言 基本名词短语是自然语言的重要结构单位，也是信息传递的基本单位。在自然语言处理领域，基本名词短语的识别和分析是自然语言浅层句法分析的重要任务之一，其分析结果可以简化句子的结构，从而降低句法分析的

5、复杂度；同时，基本名词短语的识别对于信息检索、*清华大学亚洲研究中心 2005 年度青年项目。自动问答和机器翻译等都有重要的意义。自然语言学习国际会议（CoNLL-2000）提出了语块共享任务，定义了英语中11种基本语块：NP，VP，ADJP，ADVP，PP，SBAR，CONJP，PRT，INTJ，LST，UCP4。语块的特点是语块之间不相交而且无嵌套1，即句子中的每个词能且只能属于一个语块而且每个语块的内部都不能包含其他的语块。英语基本名词短语的识别5已经得到了广泛的研究，在英语基本名词短语定义的问题上也有着比较一致的看法。而汉语基本名词短语的研究还相对滞后，并且针对不同的研究目标，对基本名

6、词短语的界定也不尽相同。比较有代表性的是从限定性定语的角度出发对基本名词短语下的定义7。本文的基本名词短语也与该定义基本一致。目前，基本名词短语识别的主要方法之一就是将其转化为与词性标注同构的问题2。对句子中的每个词，标注它在短语中所处的位置。从语言模型的角度看，基本名词短语识别的方法主要有三种：一是生成模型，以隐马尔可夫模型（HMM）为代表；另一种是最大熵模型，综合利用各种名词短语的特征3；还有基于相似度计算的模型，有代表性的如MBL（Memory-Based Learning）方法5。当然这些方法都有内在的联系并且有融合的趋势。国内学者也尝试利用上面的方法进行汉语短语识别。678 2 本文

7、基本名词短语的界定 结合汉语自身的特点和当前对英语名词短语、汉语基本名词短语的定义，我们将汉语基本名词短语（简称BaseNP）作如下界定：BaseNP?BaseNP+BaseNP BaseNP?BaseNP+名词 BaseNP?限定性定语+BaseNP BaseNP?限定性定语+名词 限定性定语?形容词|区别词|动词|名词|处所词|西文字串 在对句子中的基本名词短语进行识别时，对每个词而言，它只有四种可能的标注：名词短语外部（NNP）、名词短语左边界（LNP）、名词短语内部（INP）、名词短语右边界（RNP）。这样基本名词短语的识别问题就转化为对每个词进行标注的问题。例如对于汉语句子：迈向/v

8、 充满/v 希望/n 的/u 新/a 世纪/n/wp 一九九八年/nt 新年/nt 讲话/n 正确的标注为：NNP NNP NNP NNP LNP RNP NNP NNP LNP RNP 隐马尔可夫模型已经在词性标注方面取得了令人满意的结果，本文尝试利用隐马尔可夫模型进行基本名词短语的识别。3 基本名词短语模板的获取与可信度估计 本文利用词性信息和依存库*中词的依存信息抽取基本名词短语，并以所抽取的基本名词 *本文利用哈尔滨工业大学提供的 10000 句汉语依存树库获取基本名词短语模板，特此致谢！短语的词性序列作为基本名词短语的模板。利用获取的模板对测试语料进行标注，S为能够匹配当前基本名词短

9、语模板的词串集合，B是S中构成基本名词短语的词串集合。我们采用最大似然估计可以计算每条短语模板的可信度（Reliability）。对于每条基本名词短语模板PT，其可信度为：Reliability=|BS，|B|和|S|分别表示集合B和S中元素个数。基本名词短语模板PT|S|B|Reliability a n 2446 1451 59.32%a n n 374 175 46.79%v ns n n 141 11 7.80%表一：基本名词短语模板的可信度示例 由表一看出，能够与模板“a n”相匹配的词串在语料中出现了2446次，而其中是基本名词短语的为1451次，故其可信度为59.32。同时，我们

10、发现很多短语模板的可信度比较低，如何构造可信度较高的短语模板需要进一步研究。4 基于隐马尔可夫模型的基本名词短语标注实验 隐马尔可夫模型是由转移连接的状态集合，其中每个转移上都有两组概率：转移概率（transition probability）给出执行某个转移的概率；发射概率（emission probability）是当前状态输出有限字母表中某个符号的概率。给定带词性标注的句子S=w1w2wi.wn，其中wi(1 i n)代表句子中的第i个词；句子S的词性标记串为pos1pos2posiposn，其中posi(1 i n)代表句子中第i个词wi的词性。对S进行基本名词短语的标注，T=t1t2

11、titn（tiNNP,LNP,INP,RNP）是句子S对应的基本名词短语标注串。句子S标注为T的概率为：()(|)(|)()P T P S TP T SP S=（4.1）公式（4.1）的分子代表了词性标注的统计模型，对于分子的第二项，可以简化认为每个词的标注只与这个词的词性有关，即HMM中的发射概率：1(|)(|)niiiP S Tp pos t=（4.2）对于分子中的第一项，即HMM中的转移概率，我们采用三元语言模型，：121123()()(|)(|)niiiiP Tp t p ttp t t t=（4.3）正确标注串的概率为：1211122123*(|)argmax(|)argmax()(

12、|)argmax()(|)(|)(|)(|)(|)TTniiiiiiPT SP T SP T P S Tp tp ttp w tp wtp tt tp pos t=（4.4）利用A*启发式搜索算法进行解码，得到N条最优路径（N-Best）。这N条路径构成一个按照路径评分（P(T|S)的估计值）高低排序的有序集合。对于测试语料S（从现有的一万句语料中随机抽取200句作为测试语料，其余作为训练语料）中的样本s，利用上面的方法对其进行基本名词短语标注，得到包含N-Best路径的候选集合Ts，令正确的标注为t*，t*有可能在候选集合Ts中也有可能不在Ts中。我们定义一个二值函数(Ts)：1 *0 *(

13、)ssiftTsiftTT=（4.5）对于测试样本s，候选标记集合Ts大小的确定，也即在启发式搜索中路径数N值的设置对于最终能否得到正确的标注t*有较大影响。随着候选标记集合的扩大，正确的标注t*被包含在候选路径中的概率也不断增加。如果t*Ts，我们称当前的候选集合覆盖了正确标注，那么在测试语料S上，当取N条最优路径，也即候选数|Ts|=N时，覆盖率()|sSTS，其中|S|表示测试集S中的句子数。（4.6）图一反映了候选集大小的确定与覆盖率之间的关系。0%20%40%60%80%100%120%501002005001000 2000候选数覆盖率不考虑句长句长小于20句长大于20 图一：候选

14、数与覆盖率的关系表 由图一不难看出，随着候选数量的增加，覆盖率也不断上升。同时，发现覆盖率与句长（句子中的词数）有密切关系。这是因为句长与启发式搜索中的解码复杂度密切相关，随着句子长度的增加，候选中出现正确标注的可能性降低。当候选取集定为2000时，总体覆盖率达到81，仍有19的实例正确标注未在候选集中，在这些实例90词数大于20；在词数小于20的实例集中，覆盖率能达到97左右。也就是说句长对于基于隐马尔可夫模型的基本名词短语识别有较大的影响。5 候选集的过滤和重新排序 在利用隐马尔可夫模型的解码器得到N-Best候选之后，面临的任务就是如何通过各种手段，从大量的候选中将正确的标注选取出来。我

15、们首先利用一些边界规则过滤掉一些不符合条件的候选，然后利用上文提到的带有可信度信息的短语模板（以短语模板的可信度作为当前短语模板的权重）对剩下的候选进行重新评分，得分最高的作为最终的标注结果。5.1 基于短语结构规则的候选集过滤 规则一：边界匹配过滤规则：LNP与RNP必须满足括号匹配原则，并且INP必须在匹配的LNP和RNP之间。基本名词短语是一个相对稳定和封闭的语言单位，反映在基本名词短语的识别中就是其左右边界的划定。利用隐马尔可夫模型得出的候选结果不能保证其符合边界匹配的要求。比如得出的结果可能出现如下情况：LNP*NNP，即找不到名词短语的右边界；甚至会出现RNP*LNP的情况。这样我

16、们需要利用边界匹配规则对得出的候选结果进行第一步过滤，得出那些符合边界匹配原则的候选。规则二：基本名词短语模板匹配规则：检查当前的候选是否能够与现有的某个名词短语模板匹配，当不能与任何模板匹配时，如果候选中不包含基本名词短语标记，则认为当前实例不包含任何名词短语；否则将该实例从候选集中去除。此规则以基本名词短语模板集合有较高的召回率为前提。实验表明，边界匹配规则和基本名词短语模板匹配规则能够过滤掉大量不符合边界匹配条件的候选，从而为重新排序提供了条件。图二为候选数与过滤比率的关系表，基本名词短语模板匹配规则是在边界匹配规则过滤结果的基础上应用的，两条规则都过滤掉了80以上的无效候选，大大减小了

17、候选规模。候选数与规则过滤率关系表70%75%80%85%90%95%501002005001000 2000候选数过滤比率边界匹配规则模板规则 图二：候选数与过滤率关系 5.2 基于加权短语模板的重新排序 上面的过滤规则，都是对不符合规则要求的候选进行简单的删除。基本名词短语模板匹配规则仅仅考虑当前候选有没有匹配上特定的短语模板，而不考虑所匹配短语模板的可信度问题，所以对于同样匹配了短语模板的候选无法进行进一步的比较和排序。事实上，同样能与短语模板相匹配的两个候选，其匹配的模板在数量和可信度上都有较大的差别。我们把匹配短语模板的数量和可信度的问题考虑进来。利用所匹配的短语模板的可信度，对候选

18、进行评分，得分最高的作为最终标注结果。对于测试语料集合S中的样本s，Ts表示对样本s进行标注得到的有序候选集合，Ts表示经过规则过滤后的候选集合。Ts中的元素是对s进行基本名词短语标注后带有评分的N-Best标注路径。用Index(t*,Ts)标记正确标注t*在有序候选集Ts中的位置，Index(t*,Ts)标记正确标注t*在经过规则过滤后得到的有序候选集合Ts中的位置。对于候选集Ts中的候选t，其匹配的短语模板的集合为M(matched templates)，M中的每个元素用m表示，weight(m)表示模板m的权重也就是它的可信度。那么候选t的评分：()()|m Mweight mScor

19、e tM=，其中|M|表示候选t匹配的短语模板数。（5.2.1）Index(t*,Ts)=1 =5 =10 =20 重新排序前 48.05%89.61%96.10%100%重新排序后 62.34 88.31 92.20 100%表二：利用加权短语模板重新排序后Index(t*,Ts)分布情况 实验表明，基于加权短语模板的重新排序，对于基本名词短语的识别是有效的（见表二）。但从整体来看，正确率不高，可以考虑进一步加入多种特征进行排序。6 结论 本文首先对基本名词短语做了比较清晰的界定，在此基础上提出利用隐马尔可夫模型进行基本名词短语的标注；为了提高标注的准确度，我们利用启发式搜索得出N-Best

20、路径，利用语言知识和规则对候选进行过滤，并短语模板的可信度信息对候选路径进行重新排序。实验结果表明这种方法是有效的。但是，由于在词性标注阶段仅进行了一级标注，获取短语模板颗粒度较大。如果能够获取更为细致的短语模板，则在后期的排序阶段会有更好的效果。同时，获取其他的基本名词短语识别特征并加入到后期的排序模型中来也需要进一步探索。参 考 文 献 1 Steven Abney.1991.Parsing by Chunks.In Principal-Based Parsing.Kluwer Academic Publishers.Dordrecht.2 K.Church.1988.A Stochast

21、ic Parts Program and Noun Phrase Parser for Unrestricted Text.In Proceedings of Second Conference on Applied Natural Language Processing.3 Rob Koeling.2000.Chunking with Maximum Entropy Models.In Proceedings of CoNLL-2000 and LLL-2000.Lisbon,Portugal.4 Eric F.Tjong Kim Sang and Sabin Buchholz.2000.I

22、ntroduction to the CoNLL-2000 Shared Task:Chunking.In Proceedings of CoNLL-2000 and LLL-2000,pages 127-132,Lisbon,Portugal,2000.5 Jorn Veenstra and Sabine Buchholz.1998.Fast NP Chunking Using Memory-Based Learning Techniques.In Proceedings of BENELEARN98,Pages 71-78,Wageningen,the Netherlands.6 赵军，1998，汉语基本名词短语识别及结构分析研究。清华大学博士研究生学位论文。7 张昱琪，周强，2002，汉语基本短语的自动识别。中文信息学报，第 16 卷第 6 期。8 周雅等，2003，基于最大熵方法的中英文基本名词短语识别。计算机研究与发展，2003 年第 3 期。