Algorithm 版 (精华区)

发信人: AA (积极的人生、美好的人生), 信区: Algorithm
标  题: 虚节点HMM 汉语文本后处理模型(zz)
发信站: 哈工大紫丁香 (2002年05月23日10:36:23 星期四), 站内信件


虚节点HMM 汉语文本后处理模型
[摘要]  研究一种基于HMM的汉语文本上下文相关后处理新模型。通过引入虚节点，改进
Viterbi动态规划算法，简化了搜索操作，提高了搜索效率。文中还给出了对手写体汉字
识别系统的后处理实验测试，其结果令人满意，表明本算法的有效性和实用性。
[关键词] 文本后处理，HMM模型 ，Viterbi算法，虚节点
1.引言
随着模式识别和人工智能学科的发展，中文信息处理的研究不断前进，近十年来，关于
汉语的自动识别处理技术也取得了很大的成就。许多商品系统已经成功的推入市场，并
且取得了巨大的社会效益和经济效益。它们包括印刷汉字OCR系统、版面及文档自动录入
、脱机手写文稿识别、联机手写汉字笔输入、连续汉语语音识别系统等。
国内学者对后处理方法作了广泛和深入的研究。对加入联想、词组信息作了有益的探索
，取得了较好的结果。苗兰芳[1]等提出了一种利用N联字（N字词组）进行识别后处理纠
正的方法。张彩录[2]等提出了关于二字词的前向和后向相关识别的模型。夏莹[3]等提
出一种基于语料库统计的方法，通过建立Markov模型、统计二元同现概率和三元同现概
率进行决策。
隐马尔可夫模型（HMM）有严格的数学推导和成熟的实现算法，而且在连续语音识别上取
得了很大的成功，在文字识别系统也有很好的应用前景[4][5]。本文以下部分，将以手
写汉字识别系统为例，介绍一种基于HMM的汉语文本上下文相关处理新算法，通过引入虚
节点，大大简化了搜索操作，提高了处理速度。
2·文本Markov模型
2. 1  汉语文本后处理的HMM模型
我们的目的是首先用单字识别器根据输入文本L的特征，获得较为可靠的候选字阵列C（
其中每个字符都对应多个特征相似的候选字）。再由文本后处理模块从候选字阵列C中选
出最符合语言模型的候选字序列S*。
用符号描述整个过程如下：
设输入文本序列L =（L 1，L 2，…L T）,其中T为文本序列数目，Li为单个OCR字符；候
选字阵列 ( ＝ {(i }，( i ＝{ C1i , C2i , ?, Cni },  1( i( T，其中N为候选字数
目；候选字序列 S ＝ (C i1， C j2，…，C fT)，其中C lm ( ( m , 1( m ( T，1( l
 ( N；所有的候选字序列S构成(；P（S ( L）表示输入样本序列L，结果为S的概率。
显然，如果P（S*| L） ＝ P(S| L），则S*就是识别结果。
由Bayes公式得：P（S*| L）＝ P(S | L）
＝{ P(S）×P（L| S）/ P(L）}       (1)
由于输入样本序列L已经确定，故P（L）不影响最终结果，可以不考虑。 所有在以后的
推导中均忽略。P（L | S）项一般由单字识别器的置信度确定。P（S）由语言模型确定
。现在我们把注意点放在P（S）的求取上。
从汉语文本的实际情况考虑，可以认为在汉字文本中，只存在单词（一字词、二字词…
n字词），也就是说，在后处理中，不考虑单字的影响，认为单词是文本的最小单元。基
于如上假设，单词内部的状态转移概率认为为1，而单词间的状态转移概率与单词的词频
有关和组成该单词的单字识别置信度有关。
我们认为汉语语句后处理过程符合HMM，符合左－右Markov模型（即状态转移是顺序的）
。在后处理过程中，状态之间的转移是按一定的概率发生的，但是，在HMM中，状态是不
可直接观测的，要通过单词来体现的，而该单词的出现有一定的概率。因此作为观测者
，只能观测到单词，虽然无法直接知道状态，但是可以通过单词产生的概率去了解单词
背后隐藏的状态。
由此，当计算出各个候选字状态之间的转移概率后，就可以使用下节介绍的虚节点Vite
rbi动态规划算法求取最优结果序列。
3.虚节点HMM的Viterbi搜索算法
3.1  Viterbi文本后处理算法
传统的HMM搜索是采用Viterbi概率动态规划算法。其基本思想是分解问题，把原来的整
体最优解归结为各个子问题的局部最优解。它的目的在于解决给定一个观测值序列O＝
O1，O2，...，OT以及一个模型( = ((，A，B) 情况下，在最佳的意义上确定一个状态序
列Q* = q 1*，q 2*，...，q T*。在这里，所谓“最佳”的定义是使 P(O/()最大。
应用到汉字文本后处理中，可用HMM建立语言模型（词法的或语义的）。识别时每个字符
得到多个候选结果，将这些候选字送入语言模型进行后处理。语言模型用词性的转移概
率表示。处理过程是先由候选字建立一个多阶转移图，然后用动态规划法寻找最大可能
的句子。
但是对汉语识别来说，直接运用上述原始算法存在较大困难。主要原因在于汉语语言，
不象西文语言那样存在确定的词边界（日文单词也有较严格的词界），难以做到准确的
分词。因此必须考虑多种情况，包括单字词、二字词、三字词、四字词等，分别要建立
一元、二元、三元、四元文法模型等。这样以来不仅因状态的数目多所要求的存储量太
大，搜索时间过长，而且由于每一条路径上的状态数目不固定，存在跨越性路径，非常
不利于搜索。
3.2  虚节点的引入与计算
上一节中我们看到，原始Viterbi搜索时会带来许多困难。本节介绍我们提出的一种巧妙
的解决方案，称为虚节点法。
所谓“虚节点”，就是人为的加入一些复制节点，对于这类节点，它们的进入路径和出
口路径都是确定的。引入虚节点之后，搜索就相对容易多了。以“浙江大学电机系”为
例，如图-1所示，虚节点的引入，使我们只须专心考虑二元文法。并且，由于搜索路径
长度一致，简化了算法的设计实现过程。
图-1   虚节点在搜索中应用示例
在讲述算法之前，首先定义一些符号：
t            ：时间量，1 ( t ( T;
(t（C i）    ：到达节点C it最大似然概率，1≤t ≤ N， 1≤i≤S;
(t（C i）    ：产生(t（C i） 的进入状态，1≤t ≤ N，1≤i≤S;
(i j           ：节点C i, t－1至节点C jt的转移概率，包含虚节点;
b t（C i）    ：节点C it的OCR识别概率，即前面的单字置信度P COR（C it）;
由于节点既可以是普通节点，又可以是虚节点，故根据所组成的词组情况不同，( i j的
定义分别如下：
a) 如果状态C i, t－1和状态C j t无法构成词组，则
(i j  =  PW(C j t)
b) 如果节点C i, t－1和节点C j t构成二字词组，则
(i j  = P W(C i,t-1C j t) / PW(C j t)
c) 如果节点C i, t－1、节点C j t 和C m, t＋1构成三字词组，
则复制节点C j t，产生虚节点C k t，
(i k  = P W(C i,t-1C k t C m,t+1) / PW(C i,t-1)
(km  = 1
d) 如果节点C i, t－1、节点C j t、节点C m, t＋1和节点C p ,t＋2构成四字词组
则复制节点C j t和C m ,t＋1，产生虚节点C k t 和C o ,t＋1
(i k   = P W(C i,t-1C k t C o,t+1C p ,t＋2) / PW(C i,t-1)
(k o  = 1
(op   =1
4. 实验结果与结论
4.1 实验结果
用本文提出的基于虚节点的Viterbi算法对研制的手写体汉字识别系统[7]进行后处理测
试。选择五篇文章，分属科技、政治、经济等不同领域，各约1000字左右，由三位书写
者较认真写成，经单字识别器识别，获得前十位候选字集，送入后处理模块测试。表-1
是实测的结果，其中ER = (RR-R1) /（R10-R1） 。
%
文章1
文章2
文章3
文章4
文章5
 首选正确率R1
87.1
84.0
92.5
88.5
81.2
 十选正确率R10
97.2
95.0
99.2
99.0
99.5
后处理正确率RR
95.3
93.0
98.0
95.7
96.0
错识校正率  ER
81.2
81.8
82.1
68.6
80.9
表-1  五篇文章的后处理结果统计
可以看出，采用后处理校正平均能校正约80 % 的错识，提高识别率达10 %  。
图-2上边示出了某份书写样张，中间和下边分别是校正前和校正后的文本。从阅读来看
，文章通顺了不少。
---->识别结果:
目世界上弟一台数学计算机间世以来随着计算机技术的发展和成热计算机的应用范围木
从纯数值计算扩展到国彤图象信息处理领成形成了数学图象处理这一新的学升远年来随
着结大规模集成由路技术与计算机结抱算法的发展数字图象处理枝术取得了叔人的迸步
。
----->校对结果:
目世界上第一台数学计算机问世以来随着计算机技术的发展和成熟计算机的应用范围木
从纯数值计算扩展到图形图象信息处理领域形成了数学图象处理这一新的学科近年来随
着超大规模集成电路技术与计算机结构算法的发展数字图象处理技术取得了惊人的进步
。
图-2 某篇文章的识别校正结果
4.2 结 论
本文根据上下文相关性，提出了一种基于HMM的、词组一级的汉语文本后处理方法，并创
新的提出虚节点的概念，大大简化了Viterbi算法的搜索复杂性，从试验结果看，无论是
后处理正确率还是处理速度都是令人满意的。
研究表明，从提高正确率上看，今后的研究方向在于：研究词和词之间的更高阶的关系
对后处理的作用，例如数词和量词之间的关系；研究识别候选置信度分布模型的学习训
练机制。 
--
                人世间的事谁也无法掌握
                  该执著的  永不怨悔
                  改舍去的  不在牵挂
                  改珍惜的  好好把握

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: NLPCenter.hit.edu.cn]