（计算机科学与技术专业论文）基于迭代神经网络的复杂结构模式的分类方法研究.pdf

西北工业大学硕士学位论文摘要 摘要 随着模式识别、人工智能和机器学习等领域研究的不断深入，传统的基于模式 特征向量和距离、类似度等测量的统计分类和识别方法已经不能有效解决一些复 杂问题的分类和识别。研究表明，越来越多的模式分类和机器学习处理的对象由 无结构域中的高维特征向量向结构域中的树型或图型结构特征向量转变。结构域 中研究的主体是具有复杂数据关系的子模式数据，通过对子模式的分类和识别， 达到对整个复杂模式分类和识别的目的。 本文对能够处理结构数据的有监督的迭代神经网络和无监督的迭代神经网络 进行了较深入的研究。迭代神经网络的研究以普通神经网络的研究为基础，在研 究顺序上，一般先研究普通神经网络，再把研究深入到迭代神经网络上来，在本 文的叙述上，也按照同样的顺序。在前向神经网络上，分别对b p 算法、l m b p 算 法和粒子群算法的学习性能进行了对比：以此为基础，在有监督的迭代神经网络 上，讨论了b p t s 训练算法及其改进算法，同时将在前向神经网络调练中表现最好 的粒子群算法应用于有监督的迭代神经网络训练，得出了一些有益的结论；在自 组织映射神经网络上，分别讨论了生长自组织映射和无参数自组织映射，在此基 础上，提出了无参数生长白组织映射：在无监督的迭代神经网络上，把基本自组 织映射、生长自组织映射、无参数自组织映射和无参数生长自组织映射推广到结 构域，并进行了实验对比。 本文的主要贡献概括如下： 1 提出了基于“g l o b a lb e s t ”算予的粒子群算法，在训练前向神经网络时，相 比于现有的粒子群算法，该类算法拥有最快的收敛速度。结合粒子群算法在进行 函数优化时的经验，提出了广义粒子群算法，广义粒子群算法对于如何把粒子群 算法应用于其它领域做出了理论性的建议。将在前向神经网络训练中表现最好的 粒子群算法应用于有监督的迭代神经网络训练，提出了一种基于粒子群算法的有 监督的迭代神经网络快速学习算法。 2 传统自组织映射模型网络结构固定，训练过程中退火参数的确定是个麻烦 的过程。在前人研究的基础上，本文提出了无参数生长自组织映射融合模型，该 模型很好的解决了上述两个问题，同时也给出了无参数自组织映射中参数声的确 定方法。把该模型应用于无监督的迭代网络框架，得到了比较满意的结果。 关键词：结构数据，有监督的迭代神经网络，无监督的迭代神经网络 西北工业大学硕士学位论文a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fp a t t e mr e c o g n i t i o n ，a r t i f i c i a li n t e l l i g e n c ea n dm a c h i n e l e a r n i n g ，t r a d i t i o n a ls t a t i s t i c a lc l a s s i f i c a t i o na n dr e c o g n i t i o nm e t h o d sc a n tc l a s s i f ya n d r e c o g n i z es o m ec o m p l e xp r o b l e m se f f e c t i v e l y i t i sr e p o r t e dt h a t ，m o r ea n dm o r e r e s e a r c h o b j e c t s h a v eb e e nt r a n s f o r m e df r o m h i g h d i m e n s i o n v e c t o r si nt h e n o n s t r u c t u r e dd o m a i n st ot r e e so rd o a g ss t r u c t u r e dv e c t o r si nt h es t r u c t u r e dd o m a i n s t h em a i nr e s e a r c ho b j e c ti ss t r u c t u r e dd a t a ，a n dc l a s s i f y i n ga n dr e c o g n i z i n gt h ew h o l e p a t t e r nb yc l a s s i l y i n ga n dr e c o g n i z i n gi t ss u bp a t t e r n s t h i sa r t i c l ed o e sl o t so fr e s e a r c ho ns u p e r v i s e dr e c u r s i v en e u r a ln e t w o r k sa n d u n s u p e r v i s e dr e c u r s i v en e u r a l n e t w o r k sw h i c hc a nd e a lw i t hs t r u c t u r e dd a t a t h e r e s e a r c ho fr e c u r s i v en e u r a ln e t w o r k si sb a s e do nt h er e s e a r c ho fn o r m a ln e u r a l n e t w o r k s t h i sa r t i c l ef i r s td e s c r i b e sn o r m a ln e u r a ln e t w o r k sa n dt h e ng e n e r a l i z e st h e m t ot h es t r u c t u r e dd o m a i n sj u s ta st h eo r d e ro fr e s e a r c h w h e nd e a l i n gw i t hf o r w a r d n e u r a ln e t w o r k s ，t h i sa r t i c l ec a r r i e se x p e r i m e n t so nb p , l m b pa n dp s ot r a i n i n g a l g o r i t h m s w h e nd e a l i n gw i t hs u p e r v i s e dr e c u r s i v en e u r a ln e t w o r k s ，t h i s a r t i c l e d e s c r i b e st h eb p t st r a i n i n ga l g o r i t h ma sw e l la si t si m p r o v e da l g o r i t h m sa n dt h eb e s t p s oa l g o r i t h mi nt r a i n i n gf o r w a r dn e u r a ln e t w o r ki sa l s ou s e dt ot r a i nr e c u r s i v en e u r a l n e t w o r k s w h e nd e a l i n gw i t hs o m ，t h i sa r t i c l ed i s c u s s e sg r o w i n gs o ma n d p a r a m e t e r l e s ss o mr e s p e c t i v e l nt h e np r o p o s e sp a r a m e t e r l e s sg r o w i n gs o m b a s e do n t h e s e w h e n d e a l i n g w i t h u n s u p e r v i s e d r e c u r s i v en e u r a ln e t w o r k s ，t h i sa r t i c l e g e n e r a l i z e st h eb a s i cs o m ，g r o w i n gs o m ，p a r a m e t e r l e s ss o ma n dp a r a m e t e r l e s s g r o w i n gs o m t ot h es t r u c t u r e dd o m a i n s t h em a i nc o n t r i b u t i o n sa r el i s t e di nt h ef o l l o w i n gc o n t e n t s ： 1t h i sa r t i c l ep r o p o s e sf l e wp s oa l g o r i t h m sb a s e do n “g l o b a lb e s t f a c t o rw h i c h c a ns p e e du pt h ec o n v e r g e n c eg r e a t l yw h e nt r a i n i n gn e u r a ln e t w o r k sc o m p a r e dw i t hb p a n do t h e r p a r t i c l e s w a r l t i a l g o r i t h m s f u r t h e r m o r e ，w i t ht h ee x p e r i e n c e so fp s o a l g o r i t h m si nt h ea p p l i c a t i o no ff u n c t i o no p t i m i z a t i o n ，t h i sa r t i c l ec o n c l u d e sam o r e g e n e r a l i z e dp a r t i c l es w a r ma l g o r i t h mb ym e r g i n gt h ep r o p o s e da l g o r i t h m sa n dt h e a l g o r i t h m s e x i s t e dt o g e t h e r t h eg e n e r a l i z e dp a r t i c l es w a r ma l g o r i t h mg i v e sa s u g g e s t i o no fh o wt oa p p l yp a r t i c l es w a r ma l g o r i t h mi n t oo t h e rd o m a i n s t h i sa r t i c l e p r o p o s e saq u i c kt r a i n i n ga l g o r i t h mo ns u p e r v i s e dr e c u r s i v en e u r a ln e t w o r k sb a s e do n p s oa l g o r i t h m sb ya p p l y i n gt h ep s oa l g o r i t h mw h i c hp e r f o r m sb e s ti nt r a i n i n gn e u r a l f l 西北工业大学硕士学位论文 a b s t r a c t n e t w o r k si nt r a i n i n gr e c u r s l v en e u r a in e t w o r k s 2 t h eb a s i cs o mm o d e lh a st w od r a w b a c k s ：i th a saf i xn e t w o r ks t r u c t u r ea n di t i sn o te a s yt oa s c e r t a i nt h et w oa n n e a lp a r a m e t e r s t h i sa r t i c l ep r o p o s e sp a r a m e t e r l e s s g r o w i n gs o mm o d e lw h i c hc a ns o l v et h e s et w op r o b l e m s m e a n w h i l e ，t h ep r o p o s e d m o d e lg i v e sam e t h o dt oa s c e r t a i nt h ep a r a m e t e r $ i np a r a m e t e r l e s ss o m g o o d r e s u l t sa r eg o t t e nb ya p p l y i n gt h i sm o d e li nt h ef r a m e w o r ko fu n s u p e r v i s e dr e c u r s i v e n e u a r a ln e t w o r k s k e y w o r d s ：s t r u c t u r e d d a t a ，s u p e r v i s e d r e c u r s i v en e u r a ln e t w o r k s ， u n s u p e r v i s e dr e c u r s i v e n e u r a ln e t w o r k s i i 西北工业大学学位论文知识产权声明书 西北工业大学业 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西北工业大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位 论文研究课题再撰写的文章一律注明作者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名：鱼翌函 ? 刁年弓月岁目 指导教师签名： 棚年；月；7f 1 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位 论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文 中已经注明引用的内容和致谢的地方外，本论文不包含任何其他个人或集体 已经公开发表或撰写过的研究成果，不包含本人或其他已申请学位或其他用 途使用过的成果。对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式表明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：监 功。7 年3 月可日 西北工业大学硕士学位论文第一章绪论 1 1 课题来源 第一章绪论 本研究依托的科研项目是国家自然科学基金“基于迭代神经网络的复杂结构 模式的表示与分类方法研究”f 6 0 4 0 3 0 0 8 ) 。 1 2 研究的内容和意义 随着模式识别、人工智能和机器学习等领域研究的不断深入，传统的基于模 式特征向量和距离、类似度等测度的统计分类和识别方法已经不能有效解决一些 复杂问题的分类和识别。复杂的模式需要高维的特征向量来描述，这本身就需要 较大的开销，并且，高维特征向量的描述方法无法保持复杂模式内在的一些结构 关系。从某些方面来说，人类对复杂物体的分类和识别能力相当完美，如果能够 借鉴人类迸行分类和识别活动的机理，对我们的研究工作将具有非常大的推动作 用。通过分析人类的视觉感知机理，我们发现人类是以结构的方式认知现实世界 的，受此启发，越来越多的模式分类和机器学习问题处理的对象从无结构域 n s d ( n o n s t r u c t u r e dd o m a i n s ) 中的高维向量表示转变为结构域s d ( s t m c t u r e d d o m a i n s ) 的多层次树型或图型结构表示。在模式识别的研究中，人们提出了结 构模式识别的方法，即把一个复杂模式划分为若干个较简单子模式的组合，而子 模式又分为若干个基元，然后通过对基元的识别，进而识别子模式，最终识别该 复杂模式。为了表示每一模式的层次结构，可以把模式描述的结构法类比于语言 的语法，通过用小而简单的基元与语法规则描述大而复杂的模式。 概括的来说，整个基金项目的研究内容可以分成三个部分： 1 构造基于迭代神经网络的能够处理树型和图型结构数据的框架性分类方 法。 2 研究复杂结构模式的多层次树型和图型语法表示规则。 3 将理论成果推广到典型的应用领域，全面验证提出的模型和方法的正确 性。 在本文中，对“构造基于迭代神经网络的能够处理树型和图型结构数据的框 架性分类方法”这一内容做了大量的研究。 西北工业大学硕士学位论文第一章绪论 1 3 国内外研究现状 根据国际权威机构的统计以及我们的查新，有关该领域的工作在国际上有一 些报道，而国内的相关研究还没有见到。最早提出神经网络可以学习有向无环图 结构数据的是意大利学者s p e r d u t i 和f r a s c o n i ，在他们的报告【1 2 】中研究了用迭代神 经网络表示和处理结构数据的方法，通过结构的反传算法b p t s ( b a c k p r o p a g a t i o n t h r o u g hs t r u c t u r e ) 对树型和图型结构数据进行学习和分类。t s o i l 3 1 在他的文章中讨 论了自适应处理结构数据的一般框架。这些方法的提出，一方面解决了一类树型 和图型结构数据的分类表示问题，另一方面也存在着下面的问题： 1 有关这种网络的收敛性证明以及学习的复杂度这一非常重要的理论问题 仍然没有解决，使得目前的研究成果大都是经验结果的总结i i 捌。 2 基于结构反传的算法训练和学习收敛的速度特别慢，在某些特定的情况 下，有向无环图( 或者有向树) 的深度很大，导致误差从底层结点向顶层结点反 向传递的非常小，非常有必要提出一些快速学习算法【4 l 。 3 有向无环图的拓扑结构和迭代神经网络计算的复杂度之间的相关性还没 有研究。同时，如何选择误差函数使得网络学习的复杂度最小，也是一个关键的 问题f 5 j a 4 有监督的学习方法在一定程度上很难适合有些问题的研究，诸如数据挖 掘、知识搜索等，需要使用无监督的神经网络结构和学习算法，目前国际上已经 开始进行这方面的研究【6 , 7 1 。 2 0 0 1 年i e e e 知识和数据工程会刊( i e e et r a n s a c t i o no nk n o w l e d g ea n dd a t a e n g i n e e r i n g ) 出版了一个专辑，全面介绍了连接主义模型在结构域数据的表示和学 习方面的相关研究。其中，最具代表性的是如下的四个专题： 1 c a r r a s o 和f o r c a d a 提出了用迭代神经网络表示结构模式以及迭代神经网络 计算的一种树型自动机实现【s 】。 2 c h a n 结合r a a m 模型以及层次聚类模型，提出了用于自然语言处理的上 下文相关文法的表示机制吼 3 h o d g e 和a u s t i n 研究了传统统计特征向量表示的模式的一种结构化模拟方 法，提出了基于生长单元结构g c s ( g r o w i n gc e l ls t m c t u r e s ) 的分层聚类算法1 1 0 】，通 过自组织的映射网络将高维统计向量映射到二维层次图。 4 h a m m e r 对迭代神经网络模型的学习能力和泛化能力进行了系统的理论分 析，提出了循环神经网络和迭代神经网络的v c 维( v a p n i k - c h e r v o n e n k i sd i m e n s i o n ) 以及伪v c 维( p s e u d o v cd i m e n s i o n ) 的上界j 。 以上的研究搭建了自适应处理结构数据的框架，在最近的研究中，一些研究 人员尝试把该框架推广到一些应用领域。z w a n g 把基于自组织映射的迭代神经网 西北工业大学硕士学位论文第一章绪论 络用于植物和景色分类6 1 ，m a r k u sh a g e n b u c h n e r 提出了一种基于有监督自组织映 射的迭代神经网络模型，并把该模型应用于公司商标分类【1 2 i 。所有这些研究表明， 复杂结构模式的表示和分类问题不仅是一个基础性的研究问题，还有着广泛的应 用前景。 1 4 本文的主要工作 现有的迭代神经网络模型主要包括基于前向神经网络的有监督的迭代神经网 络和基于自组织映射的无监督的迭代神经网络。我们的研究目标是对于各种网络 模型，找到在给定的条件下最合适的训练算法。迭代神经网络训练算法的研究以 普通神经网络训练算法的研究为基础，为了构造性能良好的迭代神经网络训练算 法，必须先对普通神经网络的训练算法进行研究。因此，本文在对普通神经网络 训练算法进行深入研究的基础上，构造了相应的迭代神经网络训练算法，通过实 验，找到了在给定的条件下最合适的训练算法。本文的主要工作概括如下： 1 有监督的神经网络和迭代神经网络训练算法性能研究。 2 无监督的神经网络和迭代神经网络训练算法性能研究。 全文的贡献表现在以下几点： i 提出了一类新的基于“g l o b a lb e s t 算子的粒子群算法，成功的应用于有监 督的神经网络和迭代神经网络训练。在研究了现有的基于不同邻域拓扑结构和邻 域影响方式的粒子群算法的基础上，将一个新的影响因素“g l o b a lb e s t ”算子加入到 现有的粒子群算法中，通过与现有的粒子群算法和b p 算法在训练前向神经网络上 的性能对比实验，发现提出的算法具有较大的性能优势，从中选择了性能表现最 好的粒子群算法，将其应用于迭代神经网络训练，同样得到了较好的结果。 2 提出了广义粒子群算法。将现有的粒子群算法和提出的基于“g l o b a lb e s t ” 算子的粒子群算法分别应用于函数优化和前向神经网络训练，通过实验，分别找 到了最适合于两种应用的粒子群算法，在此基础上，将现有的粒子群算法和基于 “g l o b a lb e s t 算子的粒子群算法统一在一个框架下，提出了广义粒子群算法，广义 粒子群算法对于如何把粒子群算法应用于其它领域做出了理论性的建议。 3 提出了无参数的生长自组织映射网络训练算法，并将其成功的推广到无监 督的迭代网络模型。传统的自组织映射网络训练算法使用了退火机制，相关参数 不容易确定：确定的网格结构也使得它不能很好的模拟输入模式的分布情况。为 了克服这两个缺陷，在前人工作的基础上，我们提出了无参数的生长自组织映射 网络训练算法，同时应用于迭代网络模型，得到了比较满意的结果。 西北工业大学硕士学位论文第一章绪论 1 5 文章的组织结构 第一章，阐述论文的研究背景、研究意义以及研究现状，并概括介绍研究内 容和成果。 第二章，介绍了结构数据的表示模型和几个应用实例。 第三章和第四章，分别对有监督的神经网络和迭代神经网络训练算法进行研 究。 第五章和第六章，分别对无监督的神经网络和迭代神经网络训练算法进行研 究。 在最后章，做了总结并提出了未来的工作目标。 4 西北工业大学硕士学位论文第二章结构数据表示模型及应用实例 2 1 引言 第二章结构数据表示模型及应用实例 许多自然的或人造的系统能够用结构数据来进行适当的表示和建模。举个例 子，存储一幅l 0 0 0 x1 0 0 0 的灰度图像大约需要8 m 的空间。但是，如果有效的利 用该图像的内容和结构信息，将大大减少存储空间。假设图像中有一个房子，存 储这个房子的结构信息比起简单地存储灰度象素要节省很多空间。 现在的问题是：机器怎样识别出图像中有一个房子。要想将所给图像的内容 表示为一个房子，机器必先“识别”出这是一个房子。一旦“识别”出房子，就 可以只存储一个房子而不必再存储每个象素。 这个例子说明了在用结构数据表示实体时的一些特性： 1 如果对一个实体没有任何先验知识，就需要用更多的特征来描述它。比如 上面的例子，如果没有图像的先验知识，就需要8 m 的存储空间。 2 如果有实体的先验知识( 如通过预处理可以得到) ，就会减少所需要的特 征。先验信息越多，或是对实体的预处理越多，那么就可以更多的减少表示实体 所需要的特征。 对实体的特征提取和预处理过程非常重要，它们是提取实体内容信息这个过 程的一个完整部分。然而，特征提取和预处理方法都是领域依赖的，在一个领域 适用的提取特征的方法在另一个领域不能直接使用。例如，语音识别中一般从语 音中用线性预测编码器提取信息，该方法的最初模型就是通过线性模型处理一个 小段说话，这是基于我们对耳朵如何处理信息的理解，用一系列定义的非线性传 递函数，包括对数转换等，将非线性信号转变为线性模型的系数。然而，这种特 征提取方法在图像处理中却不适用。从根本上说，人类的视觉感知系统相比于听 觉感知系统使用了不同的技术提取特征。因此，视觉信息的特征提取需要不同类 型的预处理技术。 通过预处理，得到富含实体结构信息的特征。这样，不仅使得存储实体的空 间花费大大减小，还减少了表示实体所需要的特征，方便了进一步的处理。更重 要的是，包含结构信息的特征具有较高的分类作用，同时，结构数据在处理和分 析时，具有更有效和抵抗噪声的特点。 西北工业大学硕士学位论文第二章结构数据表示模型及应用实例 2 2 结构数据表示模型 在本节中，给出结构数据的表示模型。 迭代神经网络的研究发展到现在，已经能处理多种树型和图型数据。考虑有 m 个结点的树( 图) ，假设其最大出度为c ，树( 图) 的每个结点有，个自身的信 息，我们称这些信息为该结点的属性( a t t r i b u t e ) 或标志( l a b e l ) 。由于我们假设每个 结点有最大的出度c ，有些结点就没有达到最大的孩子个数，另外，在终端叶子结 点，根本没有孩子，这些都将作为特殊情况来考虑。对于每个结点v ，在经过迭代 神经网络时其输入向量都可以表示如下： v = ”，c v 】，c h 2 t v l , 础 ，1 】 ( 2 1 ) 其中，m ，表示结点v 本身的属性信息，其维数是，c 。表示结点p 的第f 个孩子 对结点v 的输入信息，一般取第i 个孩子的输入向量经过迭代网络的输出，假设网 络的输出维数是p ，那么然。的维数就是p ，从而得到了每个结点输入向量的维数 是l + c x p 。由于某些结点没有达到最大的孩子个数，其缺失的孩子结点的输入信 息统一用预先定义好的向量疗疗( 同样是p 维) 来表示。 图2 - i 编码网络示意图 在图2 - 1 所示的编码网络中，按照自底向上的顺序处理结构数据，该结构的最 大出度为2 。首先处理结点c ，因为它是叶子结点，所以它的输入向量为【，”f f ，h f f 】， 经过迭代神经网络其输出设为o u t ，同样的过程，得到结点b 的输入向量 【，h 订，疗川和输出向量o u t b ，现在开始处理结点d ，其输入向量为阻d ，o u t n ，o u t c 】， 经过网络得到输出o u t d ，最后处理根结点a ，输入向量为【”。，o u t o ，o u t c 】，根结点 的输出为o l a f a 。 上面介绍了迭代网络对结构数据的处理流程，可以看到，这是个自底向上、 从叶子结点到根结点的处理过程。我们的目的是对结构数据进行分类，经过对结 构数据的处理，期望得到一个输出，以此来决定该结构所属的类别，经过分析迭 6 西北工业大学硕士学位论文 第二章结构数据表示模型及应用实例 代神经网络模型，有三种可能的处理模式： 1 以任意结点的输出为最终输出： 2 以根结点的输出为最终输出； 3 最终输出可以在根结点，也可以在任意结点。 以非根结点的输出为最终输出会造成信息的丢失，所以在大多数情况下，以 根结点的输出为最终输出；在结构数据的表示过程中，越接近根结点的结点越多 的表达了全局的信息，在部分结点内容缺失的情况下，可以用能够得到的最接近 根结点的结点的输出作为最终输出，在部分内容缺失的情况下，仍然能够得到近 似全局的信息，是结构数据表示的另一优势。 2 3 应用实例 2 3 1 图像处理 在图像处理中，一个非常重要的问题就是怎样理解一个给定的场景。就像前 面所提到的那样，如果用象素表示一幅图像，将会有很大的存储开销。例如，处 理一幅1 0 0 0 x1 0 0 0 的灰度图像需要大约8 m 的存储空间，并且，这种存储方式没 有考虑图像中对象之间的相互关系。如果通过预处理从图像提取一些对象，那么 这幅图像就可以占用较小的存储空间，同时，对象之间的关系也将更加明晰。 d 图2 - 2 一个包含房屋的场景的例子 我们可以参考图2 2 所示的场景，这个场景已经用边缘检测预处理过，所以大 多数的细节内容，如阴影、纹理等信息都被忽略了。这样一个场景可以通过图2 3 中的树型结构来表示。在这个树中，有一个被标记为“s c e n e ”的根结点，它是分析 的起始点。这个结点和有许多表示基本场景的叶子结点以及表示局部结构的非叶 子结点相连。例如，标号为“c ”的叶子结点表示屋顶，标号为“a ”的结点代表这个 房子的侧面。另外，一个非叶子结点“b ”代表房子的另一面。房屋的每一个面都有 它们的细节信息。如a 面包含四个窗户，即a ，b ，“c ”和d 。因此，用一个树 型结构表示一幅图像从存储空间上来说有大大改观。其次，这种表示可以清楚地 西北工业大学硕士学位论文第二章结构数据表示模型及应用实例 描述出单个对象之间的相互关系。例如，b 面包括两个对象( 窗户和门) ，即“e ” 和“f ，。 可以想象在进行适当的预处理后，一幅场景可以被表示成多种形式的树型结 构。这就带来了一个问题，给定了许多场景，怎么识别这些场景以及如何区别不 同场景之间的差别。如果用树型结构表示场景，这个问题就转化成怎样区分一类 树型结构与另一类树型结构的问题。如果有许多树型结构，就必须研究一种方法， 能够把这些树型结构按类别分类。 趾e n 8 2 3 2 文档处理 ，瓜。 朱八 8 bcd ef 图2 3 包含房犀场景的树犁结构表示 随着计算机技术和办公自动化的发展，一个大的企业每天会产生很多文档， 这些文档需要得到及时的处理和管理。例如，一家大的保险公司，每天有许多表 单，这些表单包含了很多对公司有用的信息。另外，许多文档内部都包含表格， 如帐目清单、交易细节、权益细节和付款细节等。根据不同公司的业务需求，这 些表单以纸张或电子版的形式存储。如果是纸张的形式，从表格中检索信息将会 花很多时间；如果以电子表格形式存储，通常又很难寻找和检索到特定描述内容 的文档，尤其是描述的内容很“模糊”。例如，用户并不太确定文档的确切内容。 因此，需要研究一种通用文档的表示模型。 另外一个文档处理的例子是机器通过自动识别邮件封面的内容来自动分类邮 件。自动识别信封这一应用的关键技术在于识别信封的表格并且定位地址栏所在 的区域。图2 - 4 描述了一个典型的信封识别的例子，其中有许多的分割块，如标志 块、地址块和邮票块等。这些分割块和信封之间的关系可以表示成一个树型结构， 如图2 - 5 。从这个结构中，可以非常清楚地描述这些不同块之间的联系。 当采用了这种文档表示的结构化模型后，一个具体的问题就是如何对这种树 型结构进行分类。 西北工业大学硕士学位论文 第二章结构数据表示模型及应用实例 图2 - 4 一个典型的手写信封 s t a m p 7 s t a m p s t a m p m a r k 2 3 3i n t e r n e t 行为 w a v e h k e瓜h 蛔“剐毗 l m 8 i l m 。2i i 3 图2 - 5 手写信封的树型结构表示 前面讨论和分析的例子都是静态的，在某种意义上这类问题并不随时间的改 变而改变。例如在文档处理应用中，一旦信封上地址写完，识别问题也不会改变。 图2 - 6i n t c m e t 用户行为图 9 西北工业大学硕士学位论文 第二章结构数据表示模型及应用实例 但是，有一些问题是随着时间的变化而改变的，也就是用户的一些行为是随 着时间而变化的，这类问题主要表现在i n t e m e t 上的用户。当一个人在i n t e m e t 上 寻找信息时，通常会循着一个又一个的链接寻找相关的信息。如果这个人今天寻 找某个信息，在晚些时候寻找同样信息的时候并不能保证会沿着相同的路径。一 个典型的i n t e m e t 用户行为表示在图2 - 6 中，用户首先访问文档1 ，然后点击一个 链接到第2 页，随后又连到第3 页和第4 页，第3 页和第4 页可能又有各自的联 接，而用户也有可能直接从第1 页跳转到第7 页。 这个图说明了随时间变化的用户行为。上面的一种情况就是用户通过第2 页 到第4 页再到第7 页。其他情况可能是可能直接从第1 页跳转到第7 页。因此， 用户的行为依赖于在一个特定的时间内用户所寻找的主题和内容。 显而易见，树型结构非常适合表示描述用户行为的信息。 2 4 小结 在本章中，首先讨论了使用结构数据的优点。通过提取实体的结构信息，不 仅使得存储实体的空间花费大大减小，减少了表示实体所需要的特征，方便了进 一步的处理，更重要的是，包含结构信息的特征具有较高的分类作用，同时，结 构数据在处理和分析时，具有更有效和抵抗噪声的特点；然后给出了结构数据表 示模型，通过对表示模型的分析，发现用结构数据表示实体时，在部分内容缺失 的情况下，仍然能够得到近似全局的信息；最后，给出了结构数据表示模型的一 些应用实例。 1 0 西北工业大学硕士学位论文第三章有监督的前向神经网络模型和训练算法 第三章有监督的前向神经网络模型和训练算法 3 1 引言 第二章引入了结构数据的表示模型并介绍了该模型的几种应用实例，从这些 例子可以看出，用结构数据来表示实体具有很多优点，有很大的研究价值和应用 前景。 本文的主要工作是研究结构数据的分类方法。处理结构数据的迭代神经网络 的研究以普通神经网络的研究为基础。本章中，给出了有监督的前向神经网络模 型，并对其训练算法进行了系统的研究。首先描述了前向神经网络的基本模型， 然后介绍了b p ( b a c k p r o p a g a t i o n ) 训练算法和l m b p ( l e v e n b e r g m a r q u a r d t b a c k p r o p a g a t i o n ) _ j i i 练算法，并在标准样本集上对其性能进行了对比，最近有研究 人员尝试用智能计算方法对神经网络进行训练，本章在粒子群算法训练神经网络 上做了比较深入的研究。 3 2 基本网络模型 理论上已经证明：隐层采用s i g m o i d 激励函数的三层前向网络可以以任意精度 逼近任何连续映射，所以以下的讨论主要集中在三层前向神经网络模型上。图3 1 给出了三层前向神经网络模型，三层分别是输入层、隐层和输出层。 p ( 1 ) p ( 2 ) p ( s o ) 图3 - 1 前向神经网络模型 训练样本给出了一组输入输出对： ( ；。，。t 一) ，( ；：，一t ：) ，( _ 口，乃) ) ，共有q 个训练 西北工业大学硕士学位论文第三章有监督的前向神经网络模型和训练算法 样本。s 0 ，s l ，s 2 分别为输入层、隐层和输出层的神经元的个数。前向神经网 络的训练过程，实际上就是调整网络权值和闽值，对于所有的训练样本，使碍它 们的理想输出和实际输出之间的误差v 最小，见式( 3 1 ) ，应用于分类任务时，将 测试样本经过训练好的网络，根据其实际输出决定样本所属的类别。 矿= 导兰( 乙咱- - 2 ) 7 函一z ) ：丢羔亳( 3 - 1 ) - 口= l q = l 其中口；是第口个样本的实际网络输出。这实际上是一个无约束非线性最优化问题， 当前对于此类问题的解法，大体上分为两大类： 数值解法：包括最速下降法、共轭梯度法和牛顿法等。研究比较多的b p 算法 ( b a c k - p r o p a g a t i o n ) 基于最速下降法，而l m b p 算法【1 3 】( l e v e n b e r g - m a r q u a r d t b a c k p r o p a g a t i o n ) 是牛顿法的一种近似。 智能计算算法：分别包括遗传算法和粒子群算法。 在下面的内容里，分别用b p 算法、l m b p 算法和粒子群算法对前向神经网络 进行训练，由于b p 算法是一种比较成熟的算法，所以把l m b p 算法和粒子群算 法的结果与b p 算法进行对比。 3 3 训练样本介绍 在实验中，采用了一组b e n c h m a r k 样本：i r i s 样本集。该样本集包含1 5 0 个样 本，分3 类：i r i s s e t o s a 、i r i s - v e r s i c o l o r 和i r i s - v i r g i n i c a ，每类5 0 个样本。每个样本 具有4 个特征，分别是：萼片长度和宽度，花瓣长度和宽度。在我们的实验中， 用其中的1 0 0 个样本进行训练，5 0 个样本进行测试。 3 4b p 与l m b p 算法 前向神经网络的训练问题可以归结为式( 3 一1 ) 中v 的最小化问题。目前研究较 多的是数值解法，下面介绍的b p 算法与l m b p 算法都属于该类方法。 3 4 ib p 算法 下面给出b p 算法的推导。该推导适合于肘层网络。 在图3 - i 所示的网络模型中，不难得出下列的运算关系 雎 ”“。( o = w “( f ，) 口( _ ，) + ( f ) = l a k + l ( f ) = f “1 0 “1 ( f ) ) ( 3 2 ) ( 3 - 3 ) 西北工业大学硕士学位论文第三章有监督的前向神经网络模型和训练算法 其中，七表不第k 层嘲络，黜表不第k 层神经兀的个数。嘲络的层数从0 开始，对 于三层网络，输入层是第0 层，隐层是第1 层，输出层是第2 层。 在标准b p 算法中，使用了近似最速下降法，性能函数( 3 1 ) 被式( 3 4 ) 所代替： 矿：昙哥己(3-4) 也就是误差平方和被单个样本的误差平方所代替。权值和阈值调整如下： w 伽) = 一口砥o v 历 ( 3 5 ) 蛳) = - 口羔 ( 3 - 6 ) 这里的口表示学习率，k 表示第k 层网络。定义敏感度： 趴泸蒜 ( 3 - 7 ) 由式( 3 2 ) ( 3 7 ) ，并对式( 3 5 ) ( 3 6 ) 使用链法则，得到： 而o v = 羔若川弋d ( 3 - s ) 蒜= 羔鬻 p 9 ， 敏感度满足下面的迭代式，( 由( 3 7 ) 利用链法则得出) ： 萨：寥( ) “7 矿“( 3 - 1 0 ) 其中 i t ( ) ： ，( 矿( 1 ) ) 0 0 0 f ( ”( 2 ) ) 00 厂( ( & ) ) 并且 歹t ( 。) ：掣 a n 敏感度的初始化在网络的最后一层 ( 3 1 1 ) ( 3 - 1 2 ) 西北工业大学硕士学位论文第三章有监督的前向神经网络模型和训练算法 矿：一声( ) ( 7 7 )( 3 1 3 ) 由式( 3 1 3 ) ( 3 8 ) ( 3 9 ) ( 3 一l o ) 可以得到网络的反传过程。 处理过程中，存在下面的特殊情况： a = p( 3 1 4 ) b p 算法收敛缓慢、容易陷入局部极小；在训练中权值有可能变得很大，这会 使神经元的网络输入变得很大，从而又使得其激励函数的导函数在此点上的取值 很小，根据前面的推导过程，此时的训练步长会变得非常小，进而导致训练速度 降得非常低，最终导致网络停止收敛，引起网络瘫痪。现在对b p 算法的改进主要 集中在加入动量项和动态调整学习步长方面。 3 4 2l m b p 算法 为了便于理解，以下的详细推导具体到3 层网络结构上。l e v e n b e r g - m a r q u a r d t 是牛顿法的一种近似。下面的部分直接介绍算法流程，期间进行算法的详细推导。 s t e p l ： 对于所有的训练样本，计算目标输出与实际输出之间的平均累积误差平方和： ds 2 ( ，( f ，) 一c 1 2 ( f ，) ) 2 v = 卫旦石_ 一 ( 3 一1 5 ) q + s 2 、7 其中q 是训练样本个数，s 2 是输出层维数。 这里为了对于所有的样本取一个比较平均的结果，累积求和的结果除了样本 数和输出层维数。 s t e p 2 ： 对于我们的网络模型，实际上是为了使矿( 工) 达到最小，其中v ( x ) 是网络的平 均累积误差平方和，向量x 表示网络权值和闽值。利用牛顿法，有 a x = 一i v 2 矿( x ) - i v v ( x ) ( 3 1 6 ) 其中v v ( x ) 是梯度，v 2 矿乜) 是海森( h e s s i a n ) 矩阵，并且 v v ( x ) = j 7 ( x ) e ( z )( 3 1 7 ) v 2 v ( x ) = j7 ( 工) ，( j ) + s ( x ) ( 3 1 8 ) j ( x ) 是j a c o b i a n 矩阵。在高斯一牛顿方法中假设s ( x ) 为0 ，这样式( 3 1 6 ) 就变成 了： = - j 7 ( ；) ，西】- i j 7 ( ；) ；( ；) 1 4 ( 3 1 9 ) 西北工业大学硕士学位论文第三章有监督的前向神经网络模型和训练算法 l e v e