一种改进Viterbi算法的应用研究

No.3

计算机工程与设计

ComputerEngineeringandDesign

2007年2月Feb.2007

一种改进Viterbi算法的应用研究

李

摘

荣1，郑家恒2

(1.忻州师范学院计算机系，山西忻州034000；2.山西大学计算机与信息技术学院，山西太原030006)

要：为降低现代汉语句法分析的难度，以北大和哈工大语料为基础，利用改进的Viterbi算法对汉语真实文本进行了短语识别研究。提出了在隐马尔可夫模型(HMM)框架下，训练阶段依据统计概率信息，以极大似然法获取HMM参数，识别阶段用一种改进的Viterbi算法进行动态规划，识别同层短语；在此基础上，运用逐层扫描算法和改进Viterbi算法相结合的方法来识别汉语嵌套短语。实验结果表明，识别正确率在封闭测试中可达93.52%，在开放测试中达到77.529%，证明该算法对短语识别问题具有良好的适应性和实用性。关键词：隐马尔可夫模型;中图法分类号：TP391

Viterbi算法;层次分析;短语识别;句法分析

文献标识码：文章编号：A1000-7024(2007)03-0530-02

Applicationstudyofimprovedviterbialgorithm

LIRong1,

ZHENGJia-heng2

(1.DepartmentofComputer,XinzhouTeacher'sUniversity,Xinzhou034000,China;

2.SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006,China)

Abstract：Todecreasethedifficultyofsyntaxparsing,animprovedViterbialgorithmtorecognizephrasesinChinesetextsbasedonthecorpusfromPekinguniversityandHarbininstituteoftechnologyisadopted.AnefficientschemeforChinesephraserecognitionispro-posedintheframeworkofhiddenMarkovmodel.Inthetaggingsystem,statisticsprobabilityinformationandmaximumlikelihoodes-timationareusedtogetHMMparametersfortrainingphase.AnimprovedViterbialgorithmfordynamicprogrammingispresentedtoidentifythesamehierarchyphraseforidentifyingphase.ThenthecombinationmethodofhierarchicalsyntaxparsingandViterbialgorithmisbroughtforwardtoidentifythoserecursivephrases.Theexperimentalresultsshowthattheprecisionratesofthephraserecognitionintheclosedtestandtheopentestare93.52%and77.529%respectively,whichprovesthatthealgorithmhasabetteradaptabilityandpracticabilityforphraseidentification.

Keywords：hiddenmarkovmodel;viterbialgorithm;hierarchicalanalysis;phraserecognition;syntaxparsing

性标注的文本

=

/

/

0引言

12

Viterbi算法[1]作为隐马尔可夫模型[2~4]中的一个经典算法，能解决其第二个问题，序列问题，即给定一个观察

=、

=

12

|能最好地说明文本T的短语2

构成情况，这正是HMM的第二个问题：解码问题。该模型中可观察序列是一对对词性标记对，隐藏状态是词性标记对两词性间的边界状态。所以，短语识别的目标就是由词性对序列反推出最合理的边界状态序列。用于短语识别的HMM模型如下：

(1)N为模型状态数：6个可能的短语边界标记(chunk_tag))和短语的嵌套(如如果不考虑空短语(即“[]”“[[”，“]]”等)，则在一个词性对间有6种情况：①“[”，短语开始；②“]”，短语结束；③“][”，两个短语相邻；④“I”，不是短语左右边界，且在短语内部；⑤“O”，不是短语左右边界，且在短语外部。⑥“N”，一种不存在的状态，引入的目的是为了使别用

(2)ͬµÄ¡£

2

,…使

得在某种意义下它能最好地说明观察序列O，即求可能性最大的状态序列。该算法一般应用在任何与线性序列相关的现象上。如：语音识别、脱机手写汉字的识别[5]、词性标注[6,7]及基因分析等。而汉语短语的识别同样体现了这样的线性特点，在深入研究短语结构和Viterbi算法的基础上，认为Viterbi算法同样可以在短语定界问题上发挥优势。

1短语识别的HMM

短语识别[8]的HMM模型可描述为：对给定经过分词和词

=1和分=1。ÊDz»

、

4

、

6

表示。

1.1HMM模型的建立

收稿日期：2006-01-09

E-mail：lirong_1217@126.com

基金项目：山西省忻州师范学院科研基金项目(200623)。

作者简介：李荣(1974－)，女，山西原平人，硕士，讲师，研究方向为中文信息处理、人工智能；郑家恒，女，教授，研究方向为中文信息处理。

－530－

(3)初始分布和第一种随机过程：初始分布为

=max

1

]+log[

]+4

1

计算到各时

刻最佳路径的概率权值；

｝，用极大似然法来确定：

(b)用

６[

+log

训练语料中出现的总次数(4)第二种随机过程：观察值输出矩阵

｝

*=max

1

计算所选最佳路径上最后一词性对

的累计最大概率权值；

在边界标记状态输出第

训练语料中出现的总次数

(5)独立性：边界状态转移和各词性串构成的不同边界状态都是相对独立，不相互影响的。

上述模型可用图1来表示短语识别中6种边界状态的转移情况。

1

(b)用

６

*＋１

*，

1.21.2.1

态符

非嵌套短语的Viterbi应用问题描述

短语的识别过程可转化为在词性对之间插入不同边界状

,最大的

・令

1

=0)then

=

1

=0=0)or

1=0)

thenthen

=0

(

+log

・if(max

)=0)or

=1；

(2)确定当前观察值矩阵行

＝

=,

=2

*(最佳边界标记状态序列)

(1)初始化，计算句首词性对的

(5)=log0.5+log[

=

2

,

＄

＄＄

1

的值；]+4；

(3)=

npnvfnp*fnp*n*n**

uv#uv#uv#u

v###

(a)句首词性对的6种可能边界状态概率值：

1

1

1

1

(6)=0；

(b)句首词性对前无词性对，其前一状态记为0，即

＄

＄＄

－531－

时，若实际模拟值偏离rate_的程度可以忍受，此时可以近似认为rate_与

ooooo

oo

ooo

oo

oo

I

最终识别结果：[计算机/n[[在/p[[企业/n管理/v]中/f]]的/u应用/v]]

2实验结果及分析

在实验中利用训练参数

、

－571－