（计算数学专业论文）基于分布估计算法的bp神经网络优化设计.pdf

硕士论文 基于分布估计算法的b p 神经网络优化设计 摘要 传统b p 算法存在着收敛速度慢，易陷入局部极小值等特点，这些缺点的存在使 得b p 神经网络的应用受到了很大的限制。分布估计算法是进化领域新兴的一种算法， 有着很强的全局搜索能力和鲁棒性。本文将分布估计算法用于神经网络的优化，取得 了不错的效果。 本文首先介绍了传统b p 算法存在的缺陷，在此基础上总结了一些改进方法。然 后介绍了几种常见的分布估计算法，并提出了几种自己的改进思想。接着将分布估计 算法用于b p 神经网络的优化，着重介绍了算法的设计方案。最后文章比较了分布估 计算法和b p 算法在收敛速度和优化性能两个方面的差异性，通过比较发现分布估计 算法在b p 神经网络的优化领域有着一定的优势。 关键词：分布估计算法；b p 神经网络；优化 a b s t r a c t n o w a d a y sb pn e u r a ln e t w o r ki st h em o s tw i d e l ya p p l i e dn e u r a ln e t w o r k ，t h e m i r r o r i n gc a p a c i t ye n s u r e st h ec l e a r - c u tc l a s s i f i c a t i o n ，e i t h e rf r o mc o m p l e xo rs i m p l e r e s p e c t i v e h o w e v e r , t r a d i t i o n a b pa l g o r i t h mh a ss o m ed e f e c t s ，e g ，s l o ws p e e do f c o n v e r g e n c er a t ei n d u c e sl o c a lm i n i m u m a l lt h e s eg i v eal i m i tt ot h ea p p l i c a t i o no fb p n e u r a ln e t w o r k e s t i m a t i o no fd i s t r i b u t i o n a l g o r i t h m i sa l l e m e r g i n ga l g o r i t h mi n g r a d u a t ef i e l do fe v o l u t i o n ，w h i c hh a sa s t r o n gg l o b a ls e a r c h i n gc a p a c i t ya n dr o b u s t n e s s i tc a l lb ea p p l i e di no p t i m i z a t i o no fn e u r a ln e t w o r k ，i tw i l l d e f i n i t e l yb r i n gi nq u i t e p o s i t i v er e s u l t s t h ep a p e ri n t r o d u c e st h ed e f e c t so ft h eb p a l g o r i t h m ，a n dc o n c l u d e sw i t hs o m em e t h o d i m p r o v e m e n t s t h e ni n t r o d u c es o m ee s t i m a t i o no fd i s t r i b u t i o na l g o r i t h ma n dp r o p o s e s o m em e t h o di m p r o v e m e n t si ne d a t h e ni t a p p l i e st h ee s t i m a t i o n o fd i s t r i b u t i o n a l g o r i t h mi no p t i m i z a t i o no fn e u r a ln e t w o r k , c o n c e n t r a t i n go nt h ed e s i g ns c h e m eo f a l g o r i t h m t h ep a p e rc o m p a r e sb pa l g o r i t h mw i t he s t i m a t i o no fd i s t r i b u t i o na l g o r i t h mi n m a i n l yt w or e s p e c t i v e ：c o n v e r g e n c es p e e da n do p t i m i z a t i o nf u n c t i o n t h ec o m p a r i s o n i n d i c a t e st h a te s t i m a t i o no fd i s t r i b u t i o na l g o r i t h mg e tt l l eb e t t e ro fb pa l g o r i t h mi n o p t i m i z a t i o n k e y w o r d s ：e d a ；b pn e u r a ln e t w o r k ；o p t i m i z e 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：虞啦 。7 年励9 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：堙生茎力j 年f 月巩日 硕士论文基于分布估计算法的b p 神经网络优化设计 1 绪论 1 1 论文研究的学术背景 人工神经网络是一个由大量简单的处理单元广泛连接组成的系统，用来模拟人脑 神经系统的结构和功能。人工神经网络特有的非线性适应性信息处理能力，克服了传 统人工智能方法对于直觉，如模式、语音识别、非结构化信息处理方面的缺陷，使之 在神经专家系统、模式识别、智能控制、组合优化、预测等领域得到成功应用。人工 神经网络与其它传统方法相结合，将推动人工智能和信息处理技术不断发展。近年来， 人工神经网络正向模拟人类认知的道路上更加深入发展，与模糊系统、遗传算法、进 化机制等结合，形成计算智能，成为人工智能的一个重要方向，将在实际应用中得到 发展。 分布估计算法是进化领域新兴起的一种基于概率模型的启发式算法。它通过概率 模型来描述变量之间的相关关系，从而对解决非线性、变量耦合的优化问题更加有效。 传统的遗传算法和人工神经网络的结合取得了很大的成功，而分布估计算法比遗传算 法有着更好的全局搜索性能，它们的结合必将取得更好的成果。 1 2 人工神经网络的历史回顾和发展现状 人工的神经网络的研究最早可以追到2 0 实际4 0 年代人类开始研究自己智能的时 期。1 9 4 3 年心里学家m c c u l l o c h 和数学家p i t t s 建立起了著名的阀值加权模型，简称 m p 模型【1 】，可以用来实现常规的b o o l e 逻辑运算，这为人类用元器件和计算机程 序去实现人工神经网络打下了坚实的基础。1 9 4 9 年心里学家d o h e b b 提出神经元突 触联系是可变的假说。并由此给出了人工神经网络的学习率h c b b 学习律 2 】。h e b b 学习律在人工神经网络的发展史中占有重要的位置，被认为是人工神经网络算法的起 点，具有里程碑的意义。2 0 世纪5 0 年代和6 0 年代，一些研究学者把心里学和生理 学的观点结合起来，成功的研制了单层感知器( 3 】【4 】 5 】) ，并用电子线路去实现它。 这一研究成果给人们带来了极大的兴奋。此时，一些学者对单层感知器进行了深入的 研究，并证明了单层感知器不能解决很多问题【l 】，甚至是最简单的“异或”问题。这一 结论给人工神经网络的发展带来了很大的消极影响。这种影响一直持续到1 9 8 2 年 h o p f i e l d 将l y a p u n o v 函数引入人工神经网络作为网络性能的判定能量函数，并提出 了一种反馈神经网络模型【6 为止。在这期间也取得了一些研究成果，主要是a d e r s o n 提出的b s b 模型【7 】、k o h o n e n 8 9 的自组织映射、g r o s s b e r g 的自适应共振模型 1 0 】 等等。1 9 8 6 年并行分布处理小组的r u m e l h a r t 等研究者重新独立的提出多层网络的误 第一章绪论硕士论文 差反向传播算法，即b p 算法 1 1 ，这一经典算法的出现对人工神经网络的研究和发 展起到了重大的推动作用，使多层前馈网络模式分类器走向实用化。进入2 0 世纪 9 0 年代，人们发现，关于人工神经网络还有很多有待解决的问题。很多学者正致力 于改进现有的模型和基本算法，以获取更好的性能。这期间进化计算的发展给人工神 经网络的算法研究诸如了新的活力，很多学者期待将进化计算与人工神将网络相结 合，能够有新的突破。 1 3 多层前馈网络算法研究现状 对于神经网络的学习问题，学习算法的任务就是在神经网络的结构确定以后计算 神经元之间的连接权值。在总结多层网络算法之前，我们先来了解神经网络一些学习 算法。按照计算规则，神经网络的学习算法可以分为以下几类： ( 1 ) h c b b 规则学习 神经心里学家d 0 h e b b 1 2 提出生物神经元突触权值的变化规则，其思想是“当 某一突触连接两端的神经元同为激活或同为抑制时，该连接的强度应增加，反之应减 弱”。h e b b 学习规则被最先用于线性联想神经网络，后来h o p f i e l d 提出的模型h o p f i e l d 神经网络模型当被用作联想存储器时，连接权的计算方法同样采用h e b b 规则。 ( 2 ) 竞争学习 1 9 7 0 年g r o s s b e r g 1 3 提出了竞争学习的思想，其后一些学者对竞争学习方法又 做了广泛的研究。竞争学习的思想是在竞争学习时网络的各输出单元互相竞争，最后 达到只有一个最强者被激活。竞争学习通常是一个两步过程，第一步，神经元根据输 入模式和现有状态进行竞争，竞争结果是只有一个神经元获胜，第二步，取胜神经元 修正连接权值，权值向量修正的方向是输入模式向量的方向。 ( 3 ) 误差纠正学习 误差修正学习法用于多层前馈神经网络的学习过程。若多层前馈网络的神经元采 用连续的神经元作用函数，则这种网络就可以采用误差修正法计算其连接权值。最典 型也是最著名的误差修正学习算法是r u m e l h a r t 等人于1 9 8 6 年提出的b p 算法 1 1 】。 这种学习算法需要首先设计一个误差函数，网络连接权值是该函数的变量，连接权值 的计算过程是使误差函数的减小过程。 前馈神经网络是发展较早应用比较广泛的网络之一，其中感知器网络( 【3 】 4 】【5 】) 是 最早提出的前馈神经网络。当多层前馈网络的神经元均采用s i g r n o i d 作用函数时，则 相应的神经网络成为b p 网络。b p 网络是由于b p 算法的提出而得名的，它又被成为 广义的万规则。b p 算法是一种基于梯度引导搜索的算法，在计算连接权值时需要构 造一个网络的误差函数e ( w ，u 1 ，u 为样本模式集合，矽为所有连接权值变量形成 的向量。算法首先将权值初始化为较小的随机数，然后利用梯度下降算法连接权值的 2 硕士论文基于分布估计算法的b p 神经网络优化设计 修正量，直到误差函数达到所要求的精度，连接权值修正量的计算方法为： a w ：一刁堕 。o w b p 算法的主要过程分为两部：分别是前向计算阶和反向传播阶段，通过误差的反传 获得了梯度的计算方法。 虽然b p 算法使b p 网络的应用成为了现实，但是b p 算法也有着自身的缺陷。 主要是算法的收敛速度太慢，而且常常陷入局部最优解。造成这种问题的原因是b p 网络的误差曲面存在着平坦区和多个极值点，而b p 算法是一种利用梯度下降来寻找 最优解的方法，这种方法往往会陷入到局部最优解而无法逃离。近年来很多学者都提 出了b p 算法的改进算法( 【1 4 】， 1 5 】，【1 6 】) ，并取得了一些效果。 1 4 分布估计算法的历史回顾与发展现状 分布估计算法是进化领域新兴起的一类随机优化算法，是当前国际进化计算领域 的研究热点。分布估计算法这个概念最早在1 9 9 6 年被提出，在2 0 0 0 年以后得到了巨 大的发展。 分布估计算法是在传统的遗传算法的基础上发展而来的，与传统的遗传算法相比 它没有了交叉变异操作，取而代之的概率模型的建立。通过概率模型的建立可以描述 变量间的耦合关系，实验表明分布估计算法能更有效的解决高维问题，甚至可以解决 一类g a 难问题。 1 9 9 4 年美国卡耐基梅隆大学的b a l u j a 首先提出了p b i l ( p o p u l a t i o nb a s e d i n c r e m e n t a ll e a r n i n g ) 算法【1 7 】，用以解决二进制编码的优化问题，这个算法也被公认 为最早的分布估计算法模型。1 9 9 6 年德国学者m u h e n b e i n 提出了u m d a ( u n i v a r i a t e m a r g i n a ll e a r n i n g ) 算法【1 8 】【1 9 】，此算法与p b i l 算法的不同在于概率向量的更新方法 上。接着美国学者h a x i k 提出了紧致遗传算法即e g a ( c o m p a c tg e n e t i ca l g o r i t h m ) 算法 【2 0 ，这种算法的群体规模小，更适合于硬件实现。而在变量相关领域，d e b o n e t 提 出了m i m i c ( m u t u a li n f o r m a t i o nm a x i m i z a t i o nf o ri n p u tc l u s t e f i n g ) 算法 21 】，b a l u j a 于 19 9 7 提出了c o m i t ( c o m b i n i n go p t i m i z e r sw i t hm u t u a li n f o r m a t i o nt r e e s ) 算法 2 2 】。 c o m i t 算法和m i m i c 最大的不同在于概率模型结构上，前者是树状的，而后者是链 状的。在多变量相关领域，比较有代表性的算法是德国学者m u h l e n b e i n 提出的 e c g a ( e x t e n d e dc o m p a c tg e n e t i ca l g o r i t h m ) 算法川，美国u i u c 大学h a r i k 等人提出 的f d a 算法 2 4 】【2 5 】和以及u i u c 大学p e l i k n 提出的b o a 算法 2 6 】。f d a 算法要事 先给出变量的关系，而且对于数学形式复杂的问题不适合求解。e c g a 对解决变量无 交叠的问题非常有效，但是若问题中变量是有交叠的则效果往往比较差。b o a 算法 采用贝叶斯网来构造概率模型，它往往可以用来解决一类g a 难问题，但是b o a 算 3 第一章绪论 硕士论文 法的结构学习是一个n p 难问题f 2 7 1 。 连续域的分布估计算法发展相对缓慢，一些学者将首先将一些简单的算法扩展到 了实数领域，如文献 2 8 】是对u m d a 的扩展，文献 2 9 】是对p b i l 的扩展。连续域中 最主要的算法有e m n a ( e s t i m a t i o no f m u l t i v a r i a t en o r m a l a l g o r i t h m ) 3 0 和 e g n a ( e s t i m a t i o no f g a u s s i a nn e t w o r k sa l g o r i t h m ) 3 1 ，前者采用多变量的高斯模型表 示解的概率分布，在进化过程中采用最大使然估计来确定高斯分布的均值向量和协方 差矩阵，后者是一种基于高斯图模型的分布估计算法。但这两者采用的都是单峰的概 率模型，对于形状复杂的优化问题，两者往往不能有效的描述解的分布。 目前分布估计算法的研究热点主要在以下几个方面。一是将分布估计算法与一些 其它的搜索算法相结合，例如文献 3 2 】是传统遗传算法和分布估计算法的结合，文献 【3 3 是爬山算法与分布估计算法的结合，目的是结合各种算法的优势，提高算法的性 能。二是在非二进制编码方面的研究，e d a 和遗传算法一样，首先起源于对二进制 编码问题的研究。但是很多优化问题都是排列优化问题和连续优化问题，最近连续域 分布估计算法取得了一些发展，文献【3 4 】将b o a 算法扩展到了实数域。三是在应用 方面的研究。分布估计算法已经在众多领域取得了成功。例如基于e d a 算法的软件 测试 3 6 】，e d a 算法在癌症分类中的应用【3 7 】。目前分布估计算法的应用已经渗透到 模式识另1 j 3 8 3 9 ，工程优化 4 0 】，机器学习 4 1 】等领域。 1 5 本文研究的问题 本文主要研究了前馈神经网络的经典算法b p 算法存在的问题，在此基础了提出 了一些改进措施。然后介绍了进化领域中新兴的分布估计算法，并提出了一些改进思 想，接着将此算法用于前向神经网络权值的优化，期望取得比传统b p 算法更好的优 化结果。 1 6 本文的组织结构 全文分为三部分内容，第一部分介绍了b p 神经网络的结构和传统的b p 算法。 第二部分介绍了分布估计算法并将其用于神经网络的权值优化。第三部分对算法的性 能进行了比较。 论文的结构安排如下： 第一章简要介绍了论文的研究背景、人工神经网络的发展现状，以及介绍了分布 估计算法的发展情况。在此基础上，提出了本文所要研究的主要问题。最后介绍了本 文的组织结构。 第二章主要介绍了b p 神经网络的基本模型，以及用于训练b p 神经网络的b p 算法，并指出了此算法的不足和实现方式，在此基础上，总结了一些改进措施。最后 4 硕士论文 基于分布估计算法的b p 神经网络优化设计 给出了b p 算法的程序实现方法。 第三章介绍了通过一个简单的例子介绍了分布估计算法的基本原理，重点介绍了 三个连续型的分布估计算法的原理及实现过程，在此基础上提出了自己的一些改进思 想，为第四章作准备。 第四章将分布估计算法用于神经网络权值的优化，提出了自己的编码方案及选择 算子，最后给出了算法设计的流程图。 第五章分析了b p 算法、三种不同分布估计优化神经网络权值的性能比较。比较 方法主要是用优化了的神经网络构造了分类器。 第二章b p 神经网络基本理论与学习算法硕士论文 2b p 神经网络基本理论与学习算法 2 1 反向传播网络简介 反向传播网络( b a c k p r o p a g a t i o nn e t w o r k ，简称b p 网络) ，是对非线性可微分 函数进行权值训练的多层前向网络。其原理产生于2 0 世纪8 0 年代中期，是应用最广 泛的网络之一，具有很强的自学习，自适应，自组织能力，能通过对样本的学习，掌 握学习对象的潜在规律，从而用于模式识别、函数优化等问题。b p 神经网络通常由 输入层，隐层，输出层组成，输入层起着输入变量特征的作用，隐藏层其着特征提取 的作用，每一层内神经元的输出都传到下一层中，这种传送由连接权的强度来控制， 而每一个神经元的净输入则是前一层输出的加权和，图2 1 1 是一个单隐层，两个输 入节点和两个输出节点的b p 神经网络： 输入层隐层输出层 图2 1 1多层前向神经网络 6 图2 基本神经元模型 图2 1 2 是一个基本神经元的模型，其中x 。，z ：，x 。是前一层输入， 硕士论文基于分布估计算法的b p 神经网络优化设计 。，w ，w b ，是连接权重，对应的是一个求和单元，= x ， i = i 2 2b p 算法 在添加了隐层之后，多层网络的学习变得比较困难，这一原因直接导致了神经网 络应用的发展。而反向传播算法的出现改变了这一局面，使得神经网络在理论和应用 上都取得了重大的研究成果。反向传播算法( 即b p 算法) 是一种依靠梯度引导搜索 的算法，通过梯度的引导是误差函数逐渐变小。b p 算法有着深厚的数学基础，该算 法的步骤可以归结为以下几点 3 5 1 , ( 1 ) 初始化 选定一个合理的网络结构，将所有权值和阀值设为均匀分布的较小数值。从样本 集中取一个样本( 以，k ) ，将以输入到网络中，分别进行前向计算和反向进算。 ( 2 ) 前向计算： 对第，层的，单元，有 7 垆( 以) = u n ) y t - 1 ) ( 刀) ， j 其中y t 卜1 ( 刀) 为l - 1 层单元f 送来的工作信号，屹7 ( 刀) 为当输入第1 1 个样本时第，层单 元j f 和第，一l 层单元f 的连接权重。若单元j f 的激活函数为s i g m o i d 函数，则 删力) 2 鬲硼1 且 矽( _ ( 刀) ) 5 篇2 乃( 玎) 一乃( 咒) 若神经元_ ，属于第一隐层，则有 y j ( o ) ( ，z ) = _ ( ，z ) 若神经元，属于输出层，则有 乃u ( 玎) = q ( ”) 且勺( ，z ) = ( 刀) 一q ( 玎) 其中巳为该单元的信号误差。 ( 3 ) 反向传播阶段： 7 第二章b p 神经网络基本理论与学习算法硕士论文 对输出单元 ( 胛) = ( 以) q ( 力) 1 - o j ( 甩) 。 对隐单元 矿( ”) = 只u ( 刀) 1 - y y ) ( 疗) 罐+ 1 ( 力磁+ 1 ( 刀) 计算之后，按以下公式修正权值 堙( 刀+ 1 ) = 碟( n ) + 刁巧f ) ( 刀) 乃( 卜1 ( 刀) 其中7 7 是学习步长。 ( 4 ) 取下一个样本，直到目标函数达到预定的要求。 以上即是b p 算法的基本过程。虽然至今b p 算法在神经网络的训练方面仍占据 着主导地位，但它也存在着很多的问题。 2 3b p 算法存在的问题 b p 算法的原理是对误差函数e ( w ，u ) 的一个寻优过程，即找到一组权值，使得 样本通过神经网络后所得到的误差最小。而误差函数e 是一个关于权值形的一个高 维超曲面，它在空间的形状变化是非常复杂的。正是因为这样的原因，使得b p 算法 存在着很多的缺陷。以下是b p 算法存在的问题： ( 1 ) 收敛速度问题 由于误差函数e 在空间中是一个高维曲面，这样的曲面很可能存在平坦区，在这 样的区域里面，误差的梯度变化是非常小的，这样即使权值的调整量很大，误差仍然 下降缓慢。另外是当网络的训练达到一定的程度以后，算法的收敛速度会是一个非常 慢的速度，有时此算法还有可能是发散的。 ( 2 ) 易陷入局部极小值 由于b p 算法采用的是最速下降法，即通过梯度来引导前进方向，其训练是沿着 误差曲面的斜面向下逼近的。对于一个复杂的网络来说，其误差曲面是高位空间中的 曲面，是非常不规则的，存在着许多局部极小点。而基于梯度引导的算法在陷入局部 极小点后很难逃离出来。 ( 3 ) 步长的选择问题 由上面的b p 算法的步骤我们可以看到，b p 算法是依靠权重的修改使其最终收 敛的。如果每步的步长选取十分小，那收敛速度会变得非常的慢，这显然使我们不愿 意看到的。两一方面，如果步长过长，则网络会变得不稳定，有时甚至出现瘫痪的情 况。 8 硕士论文基于分布估计算法的b p 神经网络优化设计 2 4b p 算法的一些改进措施 对于以上存在的这些问题，很多学者都提出了不i 司的改进措施，下面是比较常用 的几种方法。 ( 1 ) 加入动量项 标准的b p 算法实质上是一种简单的采用最速下降思想寻找极值点的算法，它按 照当时梯度的反方向修正权值，并不考虑前一阶段所积累的经验。而这样的学 - 3 过程 常常发生震荡，导致收敛缓慢。引入动量项后，当样本按顺序输入时，则权值的修正 公式可以看成以t 为变量的时问序列，其权值的修改公式就变成了如下： 州叫扩1 器 加入动量项以后若本次器与前一次同号时，则加权和增大，使w ( ”) 增大；当 器与前一次符号相反时，说明有一定的震荡，此时指数加权和减小，使蛳( 疗) 减 小。 ( 2 ) 对于收敛速度问题，有学者提出了利用牛顿法来加速收敛，即考虑了e ( ，u ) 的二阶导数信息，即将权值的修改过程变为 w ( 川) = w ( 疗) 廿1 嚣 这种方法比只考虑一阶导数的方法收敛速度快，但是h e s s i a n 矩阵的计算过程本身就 让人难以忍受，而且经常是病态的。因此这种方法在实际的运用过程中很少用到。 ( 3 ) 变步长法 一阶梯度法寻优收敛慢的一个原因式学习率口的选择不恰当，若口选太小，则收 敛速度很慢。若口选的太大，则可能导致震荡而发散，变步长法就是针对这个问题而 提出的。其计算公式如下： 呲) - - ) 器 口( f ) = 2 五a ( , - i ) 抽叫器茄 其作用原理是当连续两次梯度方向相同时，表明下降太慢，因而步长加倍。若两 9 第二章b p 神经网络基本理论与学习算法硕士论文 次迭代梯度方向相反时，表明下降过头，此时将步长减半。 此外样本的顺序对训练的结果也有着很大的影响，如果每次样本的输入都是按着 固定的顺序，那么网络训练结束之后，那些与后训练样本集接近的输入会有着更高的 精度。这是因为排在前面样本对网络的影响被排在后面的样本所慢慢掩盖了。正是因 为这个原因，我们在每次进行训练的时候，都要对样本进行重新排序。 2 5b p 算法的程序实现过程 本文所用的神经网络的结构是三层的网络结构，包括输入层，输出层和隐层，用 于实现神经网络的数据结构如下，所有的编程都用c + + 来实现。 输入层： s t r u e ti n p u t _ l a y e r i n t h u m ； s t r u c ti n p u t _ l a y e r n e x t ； ) ； 输出层： s t r u c th i d _ l a y e r h a t n u m ； s t r u c th i d _ l a y e r 幸n e x t ； ) ； 隐层： s t r u c to u t _ l a y e r i n t n u r n ； s t r u c to u t _ l a y e r n e x t ； ) ； 神经网络算法的主要实现过程如下 ( 1 ) 读入神经元的结构信息和数据信息，即将结构信息和数据信息读入内存中，可 用两个函数初始化来实现。 ( 2 ) 初始化权值阀值。这个过程主要是用小于l 的随机数对神经网络的连接权值 初始化。初始化过程关系到神经网络学习过程的收敛性，如果不对神经网络所有的连 接权值进行随机初始化，可能会导致学习过程不收敛， ( 3 ) 初始化精度控制参数占，最大循环次数m ，循环次数控制参数以及学习率 口。 ( 4 ) w h i l ee 占& & n md o e = 0 ； 1 0 硕士论文 基于分布估计算法的b p 神经网络优化设计 的每个分量的取值服从b e i n o u l l i 分布，x c v i ( 1 ，4 ) ，p 0 ( ) = 1 的概率为0 5 ，那么 p o ( x ) - n ：l p o ( 薯) 。在这里，我们假设变量之间是相互独立的，因此联合概率分布就 利益分解成4 个独立分布的乘积。随机生成的1 0 个解如表3 1 ： x 2 x 3 z 4 函数值 ll o ll 3 2 1llo3 3ll0o 2 4 oo0ll 5oll13 6 0l0l2 7l111 4 8 0o0oo 9l00o 1 1 0l0012 第二步选择最优的五个个体 表3 1初始化的种群 屯 码x 4 函数值 1l o1l3 2ll1o3 3 ll0o2 50lll3 7111l4 表3 2选择的5 个最优个体 第三步根据已选的个体估计分布 在这里我f f 3 - - 共有四个参数需要估计，即魏hd 妣) 。由已选的个体计算出四 个参数分别为p 2 ( 五id 妇) = o 8 ，仍( 毛io 咖) - o 8 ，见( 毛id 妣- - o 8 ， 见( ijd 蜥) - o 8 。这样个体分布的概率向量就更新为( o 8 ，0 8 ，0 8 ，0 8 ) ，接着又按照 此概率向量随机生成1 0 个个体，如果某准则满足，则算法停止，否则继续回到第二 步，直至算法停止。以上即是分布估计算法的基本过程，本章的主要介绍了几种常用 的分布估计算法，在此基础上提出了自己的一些改进方法。 3 2 离散型的p b i l 算法 第三章分布估计算法硕士论文 p b i l 算法首次由b a l u j a 于1 9 9 4 年提出，并由b a l 哂a 和c a r u a n a 在1 9 9 5 年进行 了改进，它的提出一开始主要用于二进制编码的最优化问题。p b i l 算法是一种基于 变量独立性假设的分布估计算法算法，其概率模型如图3 2 。 图3 2p b i l 的概率模型图，它是一种基于变量独立性假设的图模型 p b i l算法由概率向量来表达个体的概率分布， 即 易( x ) - - ( p , ( 五) ，崩( ) ，易( 而) ) ，其中a ( t ) 表示在第，代中个体的第f 个分量取 1 的概率。由于假设了变量之间是相互独立的，因此联合概率分布可以写成一些独立 分布的乘积，即易( x ) = i - i n 易( t ) 。算法首先初始化概率向量为( o 5 ，o 5 ，0 5 ) ，在 此基础上产生初始种群，然后选择m 个最优个体，这m 个个体代表了种群的前进方 向。接着在这m 个最优个体的基础上，估计概率分布，并更新概率向量，概率向量的 更新规则如下 易+ 。( x j ) - - ( 1 - , o p , ( x , ) + a p t ( 薯) 其中易7 ( ) 是由第z 代最优个体估计出的概率分布，口是学习率参数，它控制了算法 的收敛速度。p b i l 算法实现的的伪代码如下： 初始化概率向量( 葺) ，使其服从b e r n o u l l i 分布 w h i l e 停止准则不满足 d o 用p t ( x ) 随机生成m 个个体：爿，i ，。 对生成的个体估值 选择最优的m ( 坍 m ) 个个体：矿，叫埘，矽村，在此基础上计算这聊个最优个 体的概率分布。 1 4 硕士论文基于分布估计算法的b p 神经网络优化设计 更新概率向量研( z ) = ( a ( 五) ，”，易( 墨) ，易( 矗) ) f o rf = lt o 刀d o a 卅( 薯) = ( 1 一口) a ( 薯) + 口a ( 而) 3 3 连续型的p b i l 算法 虽然现在有很多离散化方法将连续域的求极值问题转化为离散域极值问题，但是 在离散化过程中带来的误差太大，因此直接在连续域上建模才是解决问题的方法。 1 9 9 8 年，s e b a g 和d u c o u l o m b i e r 将p b i l 算法推广到了实数域，它的基本思想和 离散型的没什么差别，在具体的实现过程中，眦假设变量相互独立，各个变量服 从正态分布，这样联合概率密度就可以写成一些独立的正态分布的乘积，即 p ( x ) = n ? p ( 薯) ， 其中 p ( t ) = 面1 e 匆一 坼为均值，砰为方差。 在此基础上，我们可以使用最大使然估计来分别估计均值和方差： = i 1 荟n ，岔= 吉喜( 一乏) 2 其中是变量薯的第k 个取值，坼，砰分别为和才的最大似然估计。 在每一代中，我们通过均值和方差的估计产生新的个体，均值和方差砰的更 新算法如下： = u x o t + u o t a ( 1 o 一口) 吒= 夕屹 其中材似根据最优个体估计出的概率分布，口，夕都是学习因子。 3 4 离散型的m i m i c 算法 变量的独立性假设是一个很苛刻的条件，在实际的生活中，这样的问题很少出现。 为了更有效的处理变量间存在耦合关系的问题，下面我们将介绍双变量相关的分布估 计算法。 1 5 第三章分布估计算法硕士论文 m i m i c 算法的主要思想是找到变量的最优排列万= ( ，) 使得该排列定义的 概率分布( x ) 与试验中得到的每代优良个体集合的真实概率分布a ( x ) 最为接 近，图3 4 是m i m i c 的概率模型图 图3 4m i m i c 的概翠模型图 利用节点的拓扑排序刀= ( ，) 可以把联合概率分解为一个单变量边际概率分布和 嚣一1 对条件概率分布： ( x ) = a ( i 五) 扔( 五i 五) 力( 五ql ) 乃( ) 可以用k u l l b a c k - l e i b l e r 距离来度量两个不同概率分布乃( x ) ，和( x ) 之间的差异 即： ( 脚州剐= ；聊。g 器 利用香农熵式上式可以进一步化为： 哦一工( 尸( x ) ，名2 ( x ) ) = 萎聊。g 器 = 一办( 尸( x ) ) 一e 1 0 9 弓石( x ) = 一厅( 尸( x ) ) 一e 1 。g 尸( f t ) 尸( _ i ) 尸( _ ：l k ) 尸( _ ) = 一矗( 尸( x ) ) + 厅( _ i ) + ( l _ ) + + 7 z ( k ：l k ) + 办( _ ) 1 6 硕士论文基于分布估计算法的b p 神经网络优化设计 办( 尸( 彳) ) = 一p ( x ) l o g e ( x ) a x 办( 五i _ ) = 一p ( 毛i _ ) l o g 尸( 薯i _ ) a x 上面描述的k u l l b a e k l e i b l e r 距离d r 一工( p ( x ) ，弓。( x ) ) 永远大于等于零，当这个 度量等于零时，亦即e ( x ) = 口才( x ) 时，我们说两个概率分布b ”( x ) 和p ( x ) 是最为 接近的。由于厅( 尸( x ) ) 与具体的万无关，因此我们只需找到万，使得 厅( i 气) + ( 气i ) + + 办( ki _ 一。) + 办( 气) 最小。 但是要寻找到这样的一个排列万并不是意见容易的事情，如果用穷举法罗列所有 的可能那么一共要穷举疗! 个排列。但是这样显然会出现计算量过大。目前我们一般通 过贪婪算法来寻找这样的一个最优排列。贪婪算法虽然不能保证搜索到最优的排列组 合，但一般可以得到一个次优的排列组合。下面是通过贪婪算法搜寻排列的过程： m i m i c ： 1 ) f o rf = 1t o 刀 如果办( _ ) = m i i l 厅( ) 那么= j 2 ) f o rk = 刀一1t o1 如果办b ，i 以+ - ) = ，。恶办“ix , + t ) ，那么t = j 在这计算过程中，我们需要计算办( 薯) 和办( tl _ ) 。显然该算法的时间复杂度为d ( ，2 ) 。 3 5 连续型的m i m i c 算法 连续型的分布估计算法和离散型的分布估计算法基本思想是一样的，即找到这样 的最优排列7 1 使得 厅( _ l ) + ( 气l _ ) + + 办( k ：ik 。) + 办( _ ) 最小。只是在计算过程中熵函数需要有所变动，假设变量x 服从正态分布，即 x = y ( x ，u ，) ，那么变量彳的熵计算如下： 办( x ) = i 1 刀( 1 + 1 0 9 2 z ) + 1 0 9 l l 其中是协方差矩阵。将上面的结果运用到单变量和双变量的正态分布中，可以得到 1 7 第三章分布估计算法硕士论文 办( x ) = 三玎( 1 + l 0 9 2 万) + 1 0 9 q 办( x lr ) = l ( 1 + l 0 9 2 z h 。g ( 华) 其中一和正分别表示变量x 和】，的方差，而表示两者的协方差。下面是连续型 m i m i c 的伪代码： f o rf = 1t o 刀 寻找，使得= a r g m i n ， f o r 七= 刀一1t ol 选择t ：a r g 曲，一孥 吒帕 3 6e g n a 算法 e g n a 算法是一种基于高斯图模型多变量相关的分布估计算法。其概率图模型如 图3 6 所示，图中x 。条件依赖于变量而，x ：，毛条件依赖于变量x 。，x ，。 图3 6 高斯网络的图模型 e g n a 算法假设边缘概率分布和条件概率分布都为正态分布，即 p ( x ) ：n ( x ；，) ：( 2 万) 一2 一妒) l 一( 脚) 这里是n 维均值向量，是聆力的协方差矩阵，l i 是的行列式，z 1 是的逆矩阵。 然后进一步把概率的联合分布表示为所有变量在其父节点变量下条件概率的乘积： 硕士论文基于分布估计算法的b p 神经网络优化设计 p ( x ) = 兀p ( x ，耐) 上式中的联合概率分布可以写成每一项独立且服从正态分布的条件概率的乘积，其中 的每一项为i p ( x , p a ；，包) = n ( x 。；g j + ( 一一) ，q ) ( 3 1 ) l i e p 一 心表示变量z 的无条件均值，q 表示在给定父亲节点集p a t 下变量五的条件方差，钆 表示x ，和五之间关系强度的一个线性系数。 e g n a 算法一般分为两部分，结构学习和参数学习，结构学习的目的是寻找一种 高斯网络模型，使它与所选个体的概率分布最为接近。参数学习的目的是根据所选模 型和最优个体，计算( 3 1 ) 式中的参数q ，“和6 席。 ( 1 ) 结构学习 本文对高斯网络的学习采用爬山搜索算法和b i c 信息准则 4 4 相结合的方式。即 从一个初始模型出发开始搜索，初始模型一般为无边模型。在搜索的每一步首先用搜 索算子对当前模型进行局部修改得到一系列候选模型，然后计算每个候选模型的b i c 评分，并将最优模型与当前模型比较。如果最优模型的评分大则以它作为下一个当前 模型，继续搜索。否则停止并返回当前模型。 搜索算子一般有两个：加边和减边，加边即是在网络结构中添加一条边，减边即 是减少一条边，加边有个前提即不能在网络中形成有向圈。 ( 2 ) 参数计算 参数计算是在结构学习的基础上计算式( 3 1 ) 中的q ，, u t 和6 埘，下面我们推导五 的条件期望和条件方差q 的迭代形式。本文只给出了。和吼的推导过程。假设要 求变量k 在墨，髟下的条件概率即： ：l 苎= 盆2 ： p ( x o x , ，蜀) = 彳= p 2 0 0 = n ( x o ；鳓，) o o 2 万 根据条件概率的定义可得下式： p ( x o 圳= 错 计算过程中最重要的是如何处理两个协方差矩阵z ( 州) ( 州) 和d 。d ，我们用盯1 表示 1 9 第三章分布估计算法 硕士论文 ( 州m 州) 的元素，o 2 , j 表示捌中的元素，与此相对应仃；和盯。 ，分别表示两个协方 差逆矩阵中的元素。显然有d j = 盯2 ( x ，一。) 。因为矩阵是对称的所以- 1 也是对称的 也就是说矿9 = 仃，矿。f = 口。于是： 八剐如一剐2 舞裂器一6 一生生1 一三一；( 量量( 置一曲) ( 乃一竹) ) ( 2 刀) 2i 捌i 2p1 时 从a e 6 可以看出在计算a 的过程中我们可以得蛰jc r o 的表达式： ：(dr)-t!：一二二二二：!-ia ： 2 r 产5 ( 2 万) - - f zi x 捌| - - = ，o - o 。 其次我们计算b ： 6 = i 1 ( 一( 五- , u ，) 吒( 一一以) + ( 置一t , 1 ，) 吒- l x 川) ( 一一一) ) j = o1 = 0 = lj = l = i 1 ( 一( 五一鸬) 吒( - & ) - ( x o 一硒) ( 置一以) 一。一( x o 一风) 2 民 j = lj = l t = l 一( 一硒) ( 一一以碗+ ( 五一鸬) 吒- l x 川) ( 一一一) ) j - l j - i - i ：委( 一兰童( 五一鸽) 以( t 一鲍) 一2 k d ( 五一a , ) o - l o + 2 d ( 置一以) 一。 dd k 2 瓦+ 2 五肺瓦一硒2 瓦+ ( 五一心) 吒- l x 川) ( 一一) ) j = li ；l ( 3 2 ) 为使得证明过程方便对式( 3 2 ) 做变量替换具体步骤如下： 2 0 堡主笙奎一 基于分布估计算法的b p 神经网络优化设计 ：一：一：= = ：= r ： d j 口o = ( “) 吒( _ 一一) j = l f f f i l d q = - 2 ( t 一以)