人工神经网络7Boltzmanppt课件.ppt

1,人工神经网络 (Artifical Neural Network),张 凯 副教授,武汉科技大学 计算机学院,2,要点简介,1. 研究背景,2. 随机神经网络,3. 模拟退火算法,4. Boltzmann机,随机神经网络,随机神经网络是统计力学思想引入神经网络研究的结果。 统计力学是研究大系统宏观平衡性质的学科，这种大系统的组成元素服从微观机制。统计力学的主要目的是寻找从微观粒子（原子、电子）的运动开始的宏观物体的热力学性质，由于所遇到的自由度数目很大，因此只能使用概率的方法进行研究。,随机神经网络,BP网络是一种“贪心”算法，容易陷入局部最小点。 Hopfield网络很难避免出现伪状态，网络是严格按照能量减小的方向运行的，容易陷入局部极小点，而无法跳出。 所以，在用BP网络和Hopfield网络进行最优化的计算时，由于限定条件的不足，往往会使网络稳定在误差或能量函数的局部最小点，而不是全局最小点，即所得的解不是最优解。,随机神经网络,随机神经网络,网络陷入局部最小点的原因主要有两点： (1)网络结构上存在着输入到输出之间的非线性函数关系，从而使网络误差或能量函数所构成的空间是一个含有多极点的非线性空间。 (2)在算法上，网络的误差或能量函数只能单方向减小，不能有一点上升。,6,随机神经网络,随机神经网络的基本思想： 网络向误差或能量函数减小方向运行的概率大，同时向误差或能量函数增大方向运行的概率存在，这样网络跳出局部极小点的可能性存在，而且向全局最小点收敛的概率最大。,模拟退火算法(Simulated Annealing)来源于固体退火原理，将固体加温至充高，再让其徐徐冷却，加温时，固体内部粒子随温度升高变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 它由Metropolis算法和退火过程(Annealing Procedure，AP)组成。,模拟退火算法,模拟退火算法的基本思路,首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统的低能区域； 随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。,9,模拟退火算法的基本思路,当使用最速下降法(gradient descent)时，系统可能陷入局部最小值(local minimum),模拟退火算法的基本思路,仿真退火算法 基本概念 改变系统能量 以组合最速下降与随机过程的方式搜寻能量函数的总体最小值 在搜寻的过程中，通常以最速下降法使其解答状态在搜寻空间中往能量函数值较低处移动，但透过随机过程，偶而往能量函数值较高处移动，以跳过局部最小值,模拟退火算法的基本思路,最速下降 模拟退火,模拟退火概念,在模拟退火搜寻过程中，当次一个解的能量函数值比现行解的能量函数值低时，移至此解。 反之，则允许少许机率移动到能量函数值较高的次一个解，此机率通常假设为两个解间能量函数差额的Boltzmann机率分布函数。,模拟退火算法的基本思路,模拟退火的最初目的是寻找代表复杂系统的代价函数的全局最小值。因此，这种方法为解决凹平面最优问题提供了一个强有力的工具，其中心思想在于：在用模拟退火最优化一个复杂系统（如：一个拥有很多自由度的系统）时，误差或能量函数绝大部分的时间在下降，但不是一直下降，即误差或能量函数的总趋势向减小的方向变化，但有时也向增大的方向变化，这样可跳出局部极小点，向全局最小点收敛。,模拟退火与传统迭代最优算法的比较： (1)当系统在非零温度下时，从局部最优中跳出是非常可能的，因此不会陷入局部最优。 (2)系统最终状态的总特征可以在较高温度下看到，而状态的好的细节却在低温下表现，因此，模拟退火是自适应的.。,模拟退火算法的基本思路,1. Metropolis抽样过程,模拟退火算法原理,1. Metropolis抽样过程 假定一随机变量在某一时刻的状态为vi。在另一时刻的状态为vj。假设这种状态的转移满足以下条件： E表示系统从状态vi转移至状态vj所引起的能量差。 如果能量差E为负，这种转移就导致状态能量的降低，这种转移就被接受。接下来，新状态作为算法下一步的起始点。,模拟退火算法原理,模拟退火算法原理,若能量差为正，算法在这一点进行概率操作。首先，选定一个在0,1内服从均匀分布的随机数。如果e-E/T，则接受这种转移。否则，拒绝这种转移；即在算法的下一步中拒绝旧的状态。如此反复，达到系统在此温度下的热平衡。 这个过程称作Metropolis抽样过程。Metropolis抽样过程就是在一确定温度下，使系统达到热平衡的过程。,模拟退火算法原理,2. 退火过程（降温过程） 在Metropolis抽样过程中温度T缓慢的降低。模拟退火过程就是通过T参数的变化使状态收敛于最小能量处。因而，T参数的选择对于算法最后的结果有很大影响。初始温度和终止温度设置的过低或过高都会延长搜索时间。降温步骤太快，往往会漏掉全局最优点，使算法收敛至局部最优点。降温步骤太慢，则会大大延长搜索全局最优点的计算时间，从而难以实际应用。因此，T可以理解为一个控制参数。,模拟退火算法原理,为寻找在有限时间逼近全局最优的模拟退火算法，设置了许多控制算法收敛的参数。在退火过程中指定了有限的退火温度值和在每一温度下的转移数目。Kirlpatrick等人在退火步骤中设定的参数如下： (1)初始温度值：初始温度值T0要选的足够高，保证模拟退火算法中所有可能的转移都能被接受。,2019年7月23日星期二,20,模拟退火算法原理,(2)温度的下降：原先使用指数函数实现温度的下降。但是这种方法使降温幅度过小，从而延长搜索时间。在实际中，通常使用下式： 此处是一小于却接近于1的常数。通常的取值在0.8至0.99之间。在每一温度下，实验足够多的转移次数。,2019年7月23日星期二,21,模拟退火算法原理,(3)终止温度：如果在连续的若干个温度下没有可接受的新状态，系统冻结或退火停止。 模拟退火尤其适合解决组合优化问题，下面以模拟退火算法解决组合优化问题来进一步介绍模拟退火算法的步骤。,2019年7月23日星期二,22,许多工程上和理论上的问题，其目标都是在一个很大的解空间中寻求一个最优解，这些问题统称为组合优化问题。 在许多组合优化问题中，一个解通常是满足一定规则的一些离散对象的排列，所有这些解的集合叫做解空间。通常用一个“代价函数”C(x)来衡量一个解的优劣，目标就是选择一个解使其代价函数C(x)最小，如TSP问题、大规模集成电路布局布线问题等。,2019年7月23日星期二,23,模拟退火求解组合优化问题,2019年7月23日星期二,24,模拟退火求解组合优化问题,设V=V1,V2,Vn为所有可能的组合（或状态）所构成的集合。C()是V的函数，且 ，反映取状态Vi为解的代价，目标是寻找 使 模拟退火算法应用于组合优化问题的基本思想就是把每种组合状态Vi看成某一物质体系的微观状态，C(Vi)可看成该物质体系在Vi下的能量 ，温度T为控制参数。,模拟退火求解组合优化问题,让T从一个足够高的值慢慢下降，对于每个T，对当前状态V作随机扰动产生一个新状态V，计算其增量C=C(V)-C(V)，并以概率e-C/kT接受V作为新的当前状态。根据统计力学的知识，当重复如此随机扰动足够次数后，状态Vi的出现概率如下：,2019年7月23日星期二,26,模拟退火求解组合优化问题,k为Boltzmann常数,第一步：初始化。依据所要解决的组合优化问题，确定代价函数C()的表达式，随机选择初始状态V=V(0)，设定初始温度T0，终止温度Tfinal，概率阈值。 第二步：Metropolis抽样过程 （1）在温度T下依据某一规定的方式，根据当前解所处的状态V，产生一个近邻子集N(V)（可包括V，也可不包括V），在N(V)内随机寻找一个新状态S作为下一个当前解的候选解，计算C=C(V)-C(V)。,2019年7月23日星期二,27,模拟退火求解组合优化问题,模拟退火求解组合优化问题,（2）若C0，则计算概率e-C/T，若其大于给定概率阈值，则取下一状态为V=V，否则，保留这一状态。 （3）按某一给定的收敛算法检查算法在温度T下是否应停止，若符合收敛条件则表示已达到热平衡，转向第三步的退火过程，若不符合收敛条件，则转向（1）继续迭代，直至在此温度下收敛。,2019年7月23日星期二,28,模拟退火求解组合优化问题,第三步：退火过程。 按照一定的降温方法得到一个新的温度T，检查T是否小于给定的温度终止阈值Tfinal。若小于，则退火过程结束，当前状态V即为算法最终输出解。若温度T大于等于给定阈值，则转至Metropolis抽样过程，在新的温度下搜索状态。 注意：在上述退火过程中，模拟退火算法是否能达到能量E的最小值，取决于T0是否足够高，和T下降得是否充分慢，以及对每个T时系统是否稳定。,（1）T0的选择方法： a. 均匀随机抽样Vi，取此时C(Vi)的方差为T0 b. 在所有可能的组合状态中，选两个状态使C 最大，取T0为C的若干倍； c. 按经验给出。,2019年7月23日星期二,30,模拟退火参数控制,模拟退火参数控制,(2) 退火过程中Tfinal 的选取方法： a 依据经验确定 b 检验系统的熵是已否达到最小，若达到最小， 即可认为温度已达到终止温度。 c T下降n次后都没有改善，即可认为能量已降 到最低，没有必要再降温。,2019年7月23日星期二,31,模拟退火参数控制,（3）Metropolis抽样过程的收敛算法： a.检验目标函数C()的均值是否稳定； b.继续若干步，C()变化很小（设定阈值）； c.按一个固定步数抽样。 （4）降温方法的确定： 根据Kirlpatrick的方法令 ，,模拟退火参数控制,模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应用于其他领域。如VLSL设计、图像识别等。当待解决的问题复杂性较高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟退火算法最合适。因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领域知识来提高算法的性能。,模拟退火参数控制,但是，从另一方面来说，已知有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意义的课题。,2019年7月23日星期二,34,模拟退火参数控制,模拟退火算法具有跳出局部最优陷阱的能力，因此被Ackley、Hinton和Sejnowski用作Boltzmann机学习算法，从而使Boltzmann机克服了Hopfield网络经常收敛到局部最优点的缺点。在Boltmann机中，即使系统落入局部最优的陷阱，经过一段时间后，它还能重新跳出来，使系统最终将往全局最优点的方向收敛。,2019年7月23日星期二,35,模拟退火参数控制,模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点： (1)收敛速度比较慢。 (2)尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率1收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。 (3)在每一温度下很难判定是否达到了平衡状态。,模拟退火参数控制,为此，人们对模拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟退火算法和对模拟退火算法中各个函数和参数的重新设计等。,Boltzmann机,20世纪80年代，Ackley, Hinton 和Sejnowski等人以模拟退火思想为基础，对Hopfield网络引入了随机机制，推出Boltzmann机,Geoffrey Hinton,David H. Ackley,Boltzmann机,Boltzmann机是第一个受统计力学启发的多层学习机，它是一类典型的随机神经网络，属于反馈神经网络类型 其命名来源于Boltzmann在统计热力学中的早期工作和网络本身的动态分布行为 Boltzmann机结合BP网络和Hopfield网络在网络结构、学习算法和动态运行机制的优点，是建立在Hopfield网基础上的，具有学习能力，能够通过一个模拟退火过程寻求解答。不过，其训练时间比BP网络要长。,40,Boltzmann机的网络结构,Boltzmann机的网络结构,Boltzmann机由输入部、输出部和中间部构成。输入神经元和输出神经元可称为显见神经元，它们是网络与外部环境进行信息交换的媒介。中间部的神经元称为隐见神经元，它们通过显见神经元与外部进行信息交换。 每一对神经元之间的信息传递是双向对称的，即wij= wji ，而且自身无反馈即wii=0。学习期间，显见神经元将被外部环境“约束”在某一特定的状态，而中间部隐见神经元则不受外部环境约束。,41,2019年7月23日星期二,42,Boltzmann机的单个神经元,Boltzmann机中每个神经元的兴奋或抑制具有随机性，其概率取决于神经元的输入。 神经元 i 的全部输入信号的总和为 ui为：,2019年7月23日星期二,43,式中bi是该神经元的阈值。,Boltzmann机的网络结构,神经元的输出 vi 依概率取1或0 vi取1的概率： vi取0的概率：,44,由此可见， vi 取1的概率受两个因素的影响： (1) ui 越大 vi 则取1的概率越大，而取0的概率越小。 (2) 参数T称为“温度”，在不同的温度下vi 取1的概率P随 ui 的变化如图所示。,Boltzmann机的网络结构,pu的关系,Boltzmann机的网络结构,可见，T 越高时，曲线越平滑，因此，即使ui有很大变动，也不会对vi取1的概率变化造成很大的影响；反之，T 越低时，曲线越陡峭，当ui有稍许变动时就会使概率有很大差异。即温度高时状态变化接近随机，随着温度的降低向确定性的动作靠近。 当T0时，每个神经元不再具有随机特性，而具有确定的特性，激励函数变为阶跃函数，这时Boltzmann机趋向于Hopfield 网络。,46,Boltzmann机的网络结构,Boltzmann机的工作原理,Boltzmann机采用下式所示的能量函数作为描述其状态的函数。 将Boltzmann机视为一动力系统，能量函数的极小值对应系统的稳定平衡点，由于能量函数有界，当网络温度以某种方式逐渐下降到某一特定值时，系统必趋于稳定状态Boltzmann机的运行过程就是逐步降低其能量函数的过程。,47,2019年7月23日星期二,48,每个神经元 j 的能量为 Boltzmann机在运行时，假设每次只改变一个神经元的状态，如第 i 个神经元，t 时刻到 t+1时刻，它们的能量变化差值为Ei,Boltzmann机的工作原理,有一个凹凸不平的盆，要使一个小球稳定在最低的地方，如果把小球轻轻地放入盆中，那么结果必然是小球稳定在距放入地方最近的低洼处。 但是稳定所在的地方并不保证是最低的地方，这一动作与Hopfield网络相当。Boltzmann机则是大幅度摇晃刚放入小球的盆子，然后逐渐减小摇晃的幅度。这样，小球才有可能到盆子的最低处处。,2019年7月23日星期二,49,Boltzmann机的学习算法,假定Boltzmann机中有V1和V2两种状态：在V1状态下神经元i的输出vi=1，V2状态下神经元i的输出vi=0，而所有其他神经元在这两种状态下的取值都是一致的，另外假设两种状态出现的概率分别是 和 ：,2019年7月23日星期二,50,Boltzmann机的学习算法,k 为常数,Boltzmann机的学习算法,对于网络中任意两个状态V1和V2的出现概率分别为 和 。它们之间的关系为 上式符合统计理学中己知的Boltzmann分布。Boltzmann机由此得名。,2019年7月23日星期二,51,2019年7月23日星期二,52,一方面： 这就说明了能量低的状态出现的概率大，能量高的状态出现的概率小。 另一方面：温度参数T也会影响Boltzmann机处于某种状态的概率。,Boltzmann机的学习算法,(1) T 很高时，各状态出现的概率差异大大减小，也就是说网络停留在全局最小点的概率，并不比局部最小点的概率甚至非局部最小点高很多。也即网络不会陷在某个极小点中拔不出来，网络在搜索过程中能够“很快”的穿行于各极小点之间，但落于全局最小点的概率还是最大的。这一点保证网络状态落入全局最小点的可能性大。,2019年7月23日星期二,53,Boltzmann机的学习算法,(2) T 很低时，情况正好相反。概率差距被加大，一旦网络陷于某个极小点之后，虽然还有可能跳出该极小点，但是所需的搜索次数将是非常多的。这一点保证网络状态一旦达到全局最小点，跳出的可能性小。 (3) T0（Hopfield网络)。差距被无限扩展，跳出局部最小点的概率趋于无穷小。这一点保证网络状态稳定在全局最小点。,2019年7月23日星期二,54,Boltzmann机的学习算法,Boltzmann机的运行步骤,设一个Boltzmann机具有n个随机神经元（p个显见神经元，q个隐见神经元），第i个神经元与第j个神经元的连接权值为wij，i，j1,2,n。T0为初始温度，m1,2,M为迭代次数。Boltzmann机的运行步骤为： 第一步：对网络进行初始化。设定初始温度T0、终止温度Tfinal和阈值，以及网络各神经元的连接权值wij。,2019年7月23日星期二,56,第二步：在温度Tm条件下（初始温度为T0）随机选取网络中的一个神经元i，计算神经元i的输入信号总和ui： 第三步：若ui0，即能量差Ei0，取vi=1为神经元i的下一状态值。若ui0，计算概率：,Boltzmann机的运行步骤,2019年7月23日星期二,57,第四步：判断网络在温度Tm下是否达到稳定，若未达到稳定，则继续在网络中随机选取另一神经元j，令ji，转至第二步重复计算，直至网络在Tm下达到稳定。若网络在Tm下已达到稳定则转至第五步计算。 第五步：以一定规律降低温度，使Tm+1Tm，判断Tm+1是否小于Tfinal，若Tm+1大于等于Tfinal，则Tm=Tm1，转至第二步重复计算；若Tm+1小于Tfinal ，则运行结束。此时在Tm下所求得的网络稳定状态，即为网络的输出。,Boltzmann机的运行步骤,Boltzmann机学习注意问题,（1）初始温度T0的选择方法。初始温度T0的选取主要有以下方法：随机选取网络中k个神经元，选取这k个神经元能量的方差作为T0；在初始网络中选取使E最大的两个神经元，取T0为Emax的若干倍；按经验值给出T0等。 （2）确定终止温度阈值Tfinal的方法。主要根据经验选取，若在连续若干温度下网络状态保持不变，也可认为已达到终止温度。,2019年7月23日星期二,58,Boltzmann机学习注意问题,（3）概率阈值的确定方法。的选取方法主要有：在网络初始化时按照经验确定或在网络每次运行过程中选取一个0,0.5之间均匀分布的随机数。 （4）网络权值wij的确定方法。 （5）在每一温度下达到热平衡的条件。通常在每一温度下，实验足够多的次数，直至网络状态在此温度下不再发生变化为止。,2019年7月23日星期二,59,Boltzmann机学习注意问题,（6）降温的方法。通常采用指数的方法进行降温，即： 为加快网络收敛速度也可采用倍乘一个小于1的降温系数的方法进行快速降温。,2019年7月23日星期二,60,Boltzmann机的学习规则,Boltzmann机是一种随机神经网络，可使用概率中的似然函数量度其模拟外界环境概率分布的性能。因此，Boltzmann机的学习规则就是根据最大似然规则，通过调整权值wij，最小化似然函数或其对数。 假设给定需要网络模拟其概率分布的样本集合，Vx是样本集合中的一个状态向量，Vx即可代表网络中显见神经元的一个状态，假设向量Vy表示网络中隐见神经元的一个可能状态，则V=Vx Vy即可表示整个网络所处的状态。,2019年7月23日星期二,61,Boltzmann机的学习规则,由于网络学习的最终目的是模拟外界给定样本集合的概率分布，而Boltzmann机含有显见神经元和隐见神经元，因此Boltzmann机的学习过程包括以下两个阶段： （1）主动阶段：网络在外界环境约束下运行，即由样本集合中的状态向量Vx控制显见神经元的状态。定义神经元i和j的状态在主动阶段的平均关联为：,Boltzmann机的学习规则,其中概率P(Vy|Vx)表示网络的显见神经元约束在Vx下隐见神经元处于Vy的条件概率，它与网络在主动阶段的运行过程有关。 (2)被动阶段：网络不受外界环境约束，显见神经元和隐见神经元自由运行，不受约束。被动阶段的平均关联为：定义神经元i和j的状态在,Boltzmann机的学习规则,P(V)为网络处于V状态时的概率，vi和vj分别是神经元i和j的输出状态。由于网络在自由运行阶段服从Boltzmann分布，因此: E(V)为网络处于V状态时的能量。 网络的权值wij需遵循下面的调整规则：,Boltzmann机的学习规则,wij(t)为在第t步时神经元i，j之间的连接权值，为学习速率，T是网络温度。 Boltzmann机的优点： (1)通过训练，神经元体现了与周围环境相匹配的概率分布； (2)网络提供了一种可用于寻找、表示和训练的普遍方法； (3)若保证学习过程中温度降低的足够慢，根据状态的演化，可以使网络状态的能量达到全局最小点。,Boltzmann机的学习规则,但是在Boltzmann机的学习过程中被动阶段的存在具有两个很大的缺点： （1）增加计算时间。在外界环境约束条件下，一些神经元由外部环境约束，而在自由运行条件下，所有的神经元自由运行，这样增加了Boltzmann机的随机仿真时间。 （2）对于统计错误的敏感。Boltzmann机的学习规则包含了主动阶段关联和被动阶段关联的差值。当这两种关联相类似时，取样噪声的存在使得这个差值更加不准确。,仿真实例,一个含有三个神经元的BM神经网络结构如图所示，其网络权值矩阵和阀值为,V1,V2,V3,试计算其运行过程，并确定网络的最后热平衡状态。,68,Thank You !,