根植于统计力学的随机方法课件

1、组员根植于统计力学的随机方法组员组员 目录12345基础介绍随机模拟/优化方法小结确定退火和最大期望算法基于统计力学的随机机器21基础介绍(第一节：引言)统计力学的主要目标：从微观元素推导出宏观物体的热力学性质。系统越有序或者它的概率分布越集中，则熵越小。Boltzman机是第一个由统计力学导出的多层学习机，可以对给定数据的固有概率分布进行建模31基础介绍(第二节：统计力学)考虑具有许多自由度的物理系统，他可以驻留在大量可能状态中的任何一个。我们pi用表示一个随机系统中状态i发生的概率，则：41基础介绍当系统和它周围环境处于热平衡时，状态 发生的概率为：由概率规范化条件可以得到剖分函数 ：它的

2、概率分布称为典型分布或Gibbs分布。51基础介绍自由能量和熵的关系式如下其中最小自由能量原则：随机系统变元的自由能量的最小值可在热平衡时达到，此时系统服从Gibbs分布。自然偏爱具有最小自由能量的物理系统。71基础介绍（第三节：马尔科夫链）随机过程 满足称这个过程为马尔科夫链。在马尔科夫链中，从一个状态到另一个状态的转移是随机的，但输出符号确实确定的。令表示在 时刻状态 转移到 时刻状态 的转移概率。81基础介绍前面定义的一步转移概率推广至固定步数的状态转移。则从状态i到状态j的m步转移概率：马尔科夫链所具有的性质：常返性假设一个马尔科夫链从状态i开始，他以概率1返回状态i，则称状态i为常返

3、的，若pi1,任意两个子集的转移都有这种方式。并且满足以下条件：111基础介绍不可约马尔科夫链如果从状态i到状态j存在有限步的正概率的转移，则i到j是可达的。如果i与j互为可达，则状态i月状态j相通。如果马尔科夫链的两个状态相通，则其属于同一类。如果所有状态组成一个类，则称该马尔科夫链是不可分的。遍历马尔科夫链遍历意味着我们用时间的平均代替总体平均。马尔科夫链是遍历的一个充分不必要条件：他为不可约且是非周期的。121基础介绍假设时间n趋于无穷大，pij(n)趋于与i无关的j，pn可以表示为：因为定义 ，初始分布的独立向量满足这个条件。141基础介绍所以根据遍历定理：从任意初始分布开始，一个马尔

4、科夫链的转移概率将收敛于一个平稳分布，只要这个平稳分布存在。遍历的马尔科夫链的平稳分布独立于他的初始分布。状态分类152随机模拟/优化方法模拟方法优化方法Metropolis算法Gibbs采样模拟退火172随机模拟/优化方法Metropolis算法是 Monte Carlo方法的一种修改。Monte Carlo方法是对大量原子在给定温度下的平衡态的随机模拟。MCMC方法定义：对于模拟一个未知分布的MCMC方法是指产生一个遍历的马尔科夫链而它的平稳分布是未知的。MCMC方法基本原理：利用细节平衡条件构建一个概率转移矩阵，使得目标概率就是概率转移矩阵的平稳分布。随机模拟方法182随机模拟/优化方法

5、表示系统从状态 到状态 所产生的能量差。统计分析假设：192随机模拟/优化方法转移概率的选择：对于任意的马尔科夫链，设有先验概率，记为 ，满足归一性，非负性和对称性 。用先验概率和概率分布比构成期望的转移概率：202随机模拟/优化方法根据构造，转移概率的非负的且规整化为单位1。满足细节平衡原则。212随机模拟/优化方法Gibbs抽样器的转移概率是非平稳的。222随机模拟/优化方法模拟退火决定温度下降速度的调度表一个算法迭代求解每个调度表给出的新的温度下的平衡分布模拟退火解决非凸优化问题的有力工具。随机优化方法242随机模拟/优化方法基本思想：当优化一个非常复杂的大系统（即具有许多自由度的系统）

6、时不要求总是下降而是试图要求大部分时间在下降。与传统的迭代优化算法不同：1.不会陷入局部最小；2.模拟退火是自适应的。252随机模拟/优化方法模拟退火算法流程图27随机生成初始解计算目标函数扰动产生新解计算目标函数接受新解按Metropolis准则接受新解是否是否达到迭代次数是否达到迭代次数是否缓慢降低温度重置迭代次数否运算结束返回最优解2随机模拟/优化方法模拟退火特别适用于解组合优化问题。组合优化的目标是针对有很多可能解的有限离散化系统，最小化它的代价函数。283确定退火和最大期望算法确定退火时，随机性以某种形式结合到能量或代价函数中，因此在一系列下降温度情况下进行确定性最优化。聚类中需要一

7、个畸变度量 ，满足的性质为：1.对任何x它是y的凸函数。2.当变元x,y有限时，它是有限的。期望畸变：确定退火算法293确定退火和最大期望算法随机水平的主要度量为香农熵：寻找服从特定随机水平概率分布，使期望畸变最小化。拉格朗日函数：303聚类的确定退火算法：1.固定码向量，利用给定的畸变度量 的Gibbs分布计算联想概率。2.固定联想，对码向量y最优化畸变度量。确定退火和最大期望算法313确定退火和最大期望算法案例研究：混合高斯分布323在确定退火中混合高斯分布样本的相位图确定退火和最大期望算法333确定退火和最大期望算法EM算法E步骤：计算期望，即利用对未知参数的现有估计值，通过计算当前的最

8、大似然期望值，得到潜在变量的后验概率；即计算： M步骤：最大化，即重新估计未知参数，使得在E步骤求得的数据的似然性最大，给出未知参数的期望估计。即： 343确定退火和最大期望算法353确定退火和最大期望算法36样本EM计算过程3确定退火和最大期望算法37最终分类结果3确定退火和最大期望算法确定性退火与EM算法类比：确定性退火比EM算法更一般，因为确定性退火不对数据固有概率做假设。384基于统计力学的随机机器目录Boltzmann机01Logistic 信度网络02深度信度网络0339Boltzmann机01Logistic 信度网络02深度信度网络034基于统计力学的随机机器目录404.1Bo

9、ltzmann 机BM是由随机神经元组成的二值随机机器，其中的神经元都是以概率方式二值存在，只有激活和不激活两种状态，两种状态取-1和1（或0和1）；BM的随机神经元分为两个部分可见层和隐层，学习的主要目的是产生一个神经网络，对输入模式进行正确的建模，是无监督学习。414.1Boltzmann 机令x表示BM的状态向量，它的分量xi表示神经元 i 的状态，状态x代表随机向量X的一次实现。从神经元i到神经元j的突出连接记为Wij，满足wji = wij 对所有i，jwii = 0 对于所有I用一个输出恒为+1 的虚节点到所有神经元的连接权值wj0表示偏置。424.1Boltzmann 机434.

10、1Boltzmann 机为简化表示，定义单个事件A及联合事件B和C如下：实际上，联合事件B排斥A，而联合事件C包括A和B。B的概率是C关于A的边缘概率。因此，444.1Boltzmann 机将指数部分按是否包含xj表示成两项之和，其中包含xj的项为：相应地，给定B，置xj= xi=1，我们可以给出A的条件概率也就是可写成：454.1Boltzmann 机其中()为logistic函数，表示为虽然x在-1 和+1间变化，但当v充分大时，整个变量可在-到+之间变化464.1Boltzmann 机利用Gibbs抽样表示联合分布P(A, B)。基本上，如11. 6节所解释的那样，这个随机模拟开始时给网

11、络赋予任一状态，神经元以它们的自然顺序依次重复访问，每次访问，选择一个神经元，根据其他神经元的值确定该神经元状态新值的选择概率。假定这个随机模拟进行足够长的时间，则网络将达到在温度T下的平衡。但是这一热平衡过程可能非常长。为了克服这个困难，如同在11. 5节所解释的那样，对有限温度序列使用模拟退火，可以更快到达它们的边缘分布。474.1Boltzmann 机 Boltzmann机是一种随机机器，它自然依赖于用概率论评价其性能。这种标准之一是似然函数。在此基础上，根据最大似然原则，Boltzmann学习的目标是最大化似然函数或等价的对数似然函数。令状态向量x的子集x。表示可见神经元状态。向量x的

12、剩余部分x表示隐藏神经元的状态。状态向量x，x和x分别表示随机向量X, X和X的实现。Boltzmann机的运行分成两个阶段:正向阶段，在训练集的影响下运行；反向阶段，网络自由运行。484.1Boltzmann 机对整个网络给定突触间权值w，可见神经元状态为x的概率是P(X=x)。训练集中包含许多可能值x，假定它们是统计独立的，总体的概率分布是析因分布且P(X=x)。为了写出对数似然函数L(w)，对析因分布取对数且将w看作未知的参数向量。因此可以写成：494.1Boltzmann 机为了通过能量函数形成边缘概率P(X=x)的表达式E(x)，利用以下两点:1. 2.其中，Z定义为代入似然函数50

13、4.1Boltzmann 机可以得到根据得到514.1Boltzmann 机引入替换因子得到524.1Boltzmann 机Boltzmann机学习的目的是最大化对数似然函数L(w)，引入 ，其中是学习率参数，它通过和运行温度T定义，我们可以利用梯度下降法达到这一点：上式的梯度下降规则称为Boltzmann学习规则。这里所叙述的学习是集中完成的;即突触权值的改变是在整个训练样本集都给出的情况下进行的。534.1Boltzmann 机Boltzmann机学习规则的简易性归因于这样的事实，即在神经元的两种不同操作条件使用局部可观测量，这两个不同条件为:一部分钳制运行，另外的自由运行。规则另一个有趣

14、的特征是神经元i和j之间的突触权值的调整规则是独立于神经元的可见与否的，不管它们可见或都不可见，这一点可能令人吃惊。但是从实际观点看，典型地，我们发现Boltzman机的学习过程是很慢的，特别是机器中使用的隐藏神经元个数多的时候。这个令人不快的特征的原因是因为机器需要很长一段时间来达到平衡分布，这通常在可见单元不被钳制的时候经常发生。54Boltzmann机01Logistic 信度网络02深度信度网络034基于统计力学的随机机器目录554.2Logistic 信度网络Boltzmann机中对称连接被有向连接取代，从而形成无环图，这也使Neal的logistic信度网络称为有向信度网络(dir

15、ected belief net)，今后这两个术语可替换地使用。节点i是节点j的双亲节点，因为节点i到节点j是有向连接。564.2Logistic 信度网络令向量X由二值随机变量X1,X2,. XN组成，它定义由N个随机神经元构成的一个logistic信度网络。在X中的元素X，的双亲记为:也就是说，其中随机向量X最小的子集x1,x2xj ,它的条件概率Logistic信度网络的一个重要优点就是它能清楚揭示输入数据的固有概率模型的条件依赖性。特别地，第j个神经元被激发的概率由logistic函数定义，条件概率仅依赖于pa ( Xj)的输人加权和。574.2Logistic 信度网络 正如Bolt

16、zmann机一样，我们导出Logistic信度网络所期望的学习规则时仍然最大化对数似然函数，对于样本集合J最大化式中对数似然函数式L(w)。同时最大化通过定义如下突触权值wji的变化伴随着在概率空间中使用梯度下降算法:其中是学习率参数，而权值向量w表示整个网络。584.2Logistic 信度网络但是，logistic信度网络学习过程的一个严重缺陷是当它运用到密连接网络中的时候，隐藏神经元的后验概率的计算很棘手，除非在一些简单的应用中，例如带加性高斯噪声的线性模型。和Boltzmann机一样，Gibbs抽样同样可以用于近似后验概率，但是在logistic信度网络中使用Gibbs抽样被认为更加复

17、杂。59Boltzmann机01Logistic 信度网络02深度信度网络034基于统计力学的随机机器目录604.3深度信度网络为了克服logistic信度网络中推理应用的困难的缺点，Hinton等(2006)发展了一种新的logistic信度网络，而这种网络中推理很容易完成。这个模型与logistic信度网络中一样，模型可以通过同样的方式学习得到，除了在最顶层的不同之外，它(以这种新方式)形成了无向联想记忆。事实上，正是这种特点使这种新的网络被称为深度信度网络。深度信度网络建立在受限Boltzmann机(restricted Boltzmann machine，RBM)上614.3深度信度网

18、络 由于在RBM中隐藏神经元之间没有连接，也因为在可见神经元和隐藏神经元间的连接是无向的(详见图11. 8)，则给定可见状态，隐藏神经元的状态相互之间是条件独立的。所以给定一个向量钳制在可见神经元之后，RBM能够抽取后验分布中无偏见的样本。RBM的这个特点使得其对相应的有向信度网络具有很大优势。624.3深度信度网络由式(11. 44)中的logistics函数来定义RBM隐藏神经元被激活的概率。令X（0）表示一个数据向量被钳制在可见层零时刻的值。然后学习在下面两个操作之间来回交替进行。给定可见状态，并行更新所有隐藏状态。以相反方式做同样的事时:给定隐藏状态，并行更新所有可见状态。令w作为整个

19、网络的权值向量。相应地，我们发现最大似然函数L(w)对应的权值wji的梯度，wji是连接可见单元i和隐藏单元j的对称权值，如下:634.3深度信度网络其中两个分别是神经元i和j在零时刻和无穷远时间的平均相关性(Hinton等，2006;Hinton, 2007 )。除了不重要的术语变化，和Boltzmann机的数学形式相同。DBN 是由多层 RBM 组成的一个神经网络，它既可以被看作一个生成模型，也可以当作判别模型，其训练过程是：使用非监督逐层方法去预训练获得权值。644.3深度信度网络深度信度网络的训练在逐层的基础上进行，如下:受限Boltzmann机是直接在输人数据上训练的，所以使RBM的

20、隐藏层随机神经元很有可能获得刻画输人数据的重要特征。所以我们称隐藏层为深度信度网络的第一隐藏层。经过训练的特征的激活然后被作为“输入数据”，它被用于第二个RBM的训练。事实上，刚描述的过程可以视为从特征中学习特征的过程之一。这个过程一直持续到深度信度网络中一些规定的个数的隐藏层得到训练。654.3深度信度网络通过使用如图所示的方式多次交替的Gibbs取样后，可以从顶层RBM获得一个平衡样本，取样过程可以进行足够长的时间直到平衡。 从可见顶层RBM“可见”单元开始自顶向下的一次扫描用来随机挑取网络中所有另外隐藏神经层的状态。664.3深度信度网络 数据产生是很慢的，因为，首先所有顶层RBM必须达到平衡分布。幸运的是，产生不是供感知推理或者学习之用。深度信度网络为设计者提供很大自由空间。对设计者来说如何创造性地使用这个自由是个挑战。675本章小结 在本章中我们讨论利用植根于统计力学的思想作为优化技术表示和机器学习的数学基础。主要讨论了三种模拟算法: 模拟退火，一种优化算法，模拟退火能够避免局部极小值。Metropolis算法，它是Markov chain Monte Carlo (