Bayes 网络学习及其在文本检测中的应用研究

《Bayes 网络学习及其在文本检测中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第43卷　第5期复旦学报(自然科学版)Vol.43No.52004年10月JournalofFudanUniversity(NaturalScience)Oct.2004　　文章编号:042727104(2004)0520733204XBayes网络学习及其在文本检测中的应用研究汪荣贵,张佑生,高　隽,彭青松,胡良梅(合肥工业大学计算机与信息学院,合肥　230009)摘　要:针对大规模Bayes网络的条件概率赋值问题,提出一种学习方法.首先使用类层次结构定义一种新的层次Bayes网络模型,用于表示大规模Bayes网络.然后将训练数据集由单个数据表的形式转化成多表

2、数据库,其中每个数据库表对应1个Bayes网络模块.在此基础上导出条件概率计算公式,从每个数据库表中算出相应的Bayes网络模块的条件概率表,由此实现对整个层次Bayes网络的概率赋值.可通过适当增加数据库表的数目来控制每个表中属性的个数,保证计算的可行性.最后将本层次Bayes网络及计算公式用于解决图像中文本的自动检测与定位问题,实验结果表明了它们的有效性.关键词:Bayes网络;类层次结构;层次Bayes网络;机器学习中图分类号:TP181文献标识码:A为使Bayes网络具有机器学习能力,人们提出了许多有效的学习算法.它们可大致分为两类:①基于经典的统计学的

3、学习算法,如适合处理完备数据的极大似然算法、适合处理不完备数据的EM算法和梯度上升算法等;②基于Bayes统计学的学习算法,如适合处理完备数据的Bayes预测(条件期望估计法)算法、1～3适合处理不完备数据的Gibbs算法等.Bayes网络学习的计算复杂度依赖于网络结构,最坏情况下是4NP2hard问题.变量较多时,难以对网络结构的进行合理地评判,现有的学习算法不可行.本文针对大规模Bayes网络的概率赋值问题,提出一种学习方法.首先定义一种新的基于层次的Bayes网络模型,来表示大规模Bayes网络.然后在此基础上提出条件概率表的学习算法,实现概率赋值.最后将

4、层次Bayes网络及其学习算法用于解决图像中文本的自动检测与定位问题,验证它们的有效性.1Bayes网络及类层次结构概率论使用概率分布处理不确定性问题.对于n元随机向量U={x1,x2,⋯,xn},若每个分量最多n有r个可能的取值,则要确定r-1个概率.这是一个NP2hard问题.因此,通过直接对每个基本事件计算或指派概率的方法来确定联合概率分布P(U)是不现实的.需要建立适当的概率模型,借助模型的结构和数量特征来确定P(U).Bayes网络就是一种这样的概率图模型.定义1n元离散随机向量U={x1,x2,⋯,xn}的Bayes网络是一个二元组B=(Bs,BP)

5、.其中:Bs=(U,V)是有向无环图,称为网络结构,U为节点集,V是有向边的集合,每条边表示两节点间直接的依赖关系,依赖程度决定于条件概率.BP={P(xi

6、par(xi)):xi∈U}是一组条件概率分布的集合.par(xi)表示在Bs中xi所有父节点的集合(若没有父节点则par(xi)=ª);P(xi

7、par(xi))表示节点xi在其父节点某一取值状态下的条件概率分布.Bayes网络模型由网络结构和条件概率分布两部分组成.网络结构用于定性描述变量间概率依赖关X收稿日期:2004203205基金项目:国家自然科学基金资助项目(60175011,60375011)

8、;安徽省自然科学基金(03042207);安徽省优秀青年科技基金(04042044)作者简介:汪荣贵(1966—),男,副教授,在职博士;张佑生(1941—),男,教授,博导.734复旦学报(自然科学版)　　　　　　　　　　　　　　　　第43卷系.它是一个有向无环图,图中每个节点表示问题领域中某一随机变量,每条边表示节点间可能存在直接的概率依赖关系,两节点间没有边连结则表示两节点间没有直接的概率依赖关系.条件概率分布定量描述节点对其父节点的概率依赖程度.Bayes网络的结构特征与变量间的条件独立性之间满足马尔可夫条件,即任一变量在已知其父节点取值状态的条件下,独

9、立于它的所有非子孙节点.由链式法则,有nnP(U)=7P(XiX1,X2,⋯,Xi-1)=7P(Xipar(Xi1)).(1)i=1i=1　　机器学习是构造Bayes网络的重要途经,然而对于大规模Bayes网络,还没有有效的学习方法.事实上,大规模Bayes网络难以学习根本原因在于它没有充分使用问题域中的结构信息.它只使用了系统中变量之间的独立、依赖等结构信息,忽视了系统中各个子系统或对象实体之间的结构信息.本文利用层次关系中所蕴含的条件独立性,降低Bayes网络学习的复杂度.首先定义一种层次结构,称之为类层次结构.定义2　称四元组为类层次结构

10、,记为H.其中各要素定义