第七章　随机方法

7.1 内容介绍 对于高维和复杂的模型，由于经常出现许多局部极值，这时必须利用各种处理技巧。本章将主要研究两大类通用随机搜索方法。 7.1　内容介绍 对于高维和复杂的模型，由于经常出现许多局部极值，这时必须利用各种处理技巧。本章将主要研究两大类通用随机搜索方法。 其一，以Boltzmann学习机作为范例，是一种来自物理学的概念和技术；它已形成高度发展和严格的理论，并且在模式识别中取得很多成功，因而将花主要的篇幅讲述； 其二，以遗传算法为范例，源自生物学的若干概念，特别是有关进化的数学理论，它更具启发性和灵活性，当计算资源充足时，不失是一个很吸引人的方法。

7.2　随机搜索 假定给定多个变量　　　　　　　其中每个变量的数值都取两个离散值之一。为简单起见，记它们为±1　.优化问题是这样描述的：确定N个　　的合适取值，使下述代价函数或能量函数最小： 　其中的权值　　是对称的，取值可正可负，可以令到自身的反馈为0。 想像一下该网络代表N个物理磁体，每个磁体的北极要么指上（si = +1）,要么指向下（si = -1）。　　是描述磁体间的物理分离度的函数。对每对磁体间存在一个交互作用的能量，即： 优化的任务就是在由这些磁体组成的集团的所有构型当中寻找到最稳定的构型，也就是对庆于最低能能量的那个构型。

7.2.1　模拟退火 　　　在物理学中的退火中，系统首先被加热，保证其每一磁体具有充分的随机性。退火中，系统温度缓慢的逐步降低，直到零温度。此时不再有随机变动，系统被松弛到一个很低的能量构型，完成退火。

7.2.2 Boltzmann因子 物理学中有一个关键结论：系统位于一个特定（离散）构型 具有能量 的概率由 物理学中有一个关键结论：系统位于一个特定（离散）构型 具有能量　 的概率由 　 给出，其中Ｚ（Ｔ）是个归一化函数。式中分子部分称为“Boltzmann因子”，分母部分是所谓的“配分函数”，它保证上式确是个真正概率。 大致来说，高温给了系统更多的能量，使出现高能量构型的概率增大。这也定性也解释了Boltzmann因子中概率对Ｔ的相依关系： 在高温时，所有构型的概率分布大致平均，而在低温时，系统则集中分布在具有最低能量的构型周围。

模拟退火算法 　　　首先将网络随机初始化，并设定一个高的初始“温度”Ｔ（1），然后随机选择一个节点i,假定其现在的状态是si = +1，计算在这种构型下系统总能量Ｅa,接着再计算如果改变到候选状态，即si = -1时，对应的系统总能量Ｅb。如果假选状态能量Ｅb<Ｅa,则接受这次状态改变，反而则按照如下概率接受这个状态改变： 　　　　　　　　　　　　　　　　　　　　　　　　， 　　　值得指出的是，温度函数Ｔ(k)（这里k是迭代的次数）被称为冷却进度或退火进度。Ｔ（1）应该足够高，以使得全部构型有大致一样的概率。温度应该十分缓慢地逐渐下降，系统能够到达状态空间的任何区域，同时又避免陷入不希望的局部极小处。 　　　一种典型的退火进度利用了公式Ｔ（k+1）=cT(k)，其中0<c<1。若不考虑计算资源，初始值都宜设高一些。实际中，0.8<c<0.99之间的c可以工作得很好。

7.2.3 确定性模拟退火 　　　 在搜索中允许节点取模拟状态值，在搜索终止时，这些状态值被强制到最优化所需的±1。要求在高温时很大的朝上的力也不能确保si = +1，而当温度很低时，很小的外力就可以使si = +1或-1.故若令 ,表示施加在节点i上的外力，则更新后的状态值成为：

7.3　Boltzmann学习

7.3.1　可见状态的随机Boltzmann学习 假定全部可见单元的概率分布已知为Ｑ(a)，现在要求实际经由随机仿真获得的对于给定样本集合的概率分布Ｐ(a)与已知的Ｑ(a)一致。 可见构型的概率等于所有可能的隐状构型的求和： 其中Eαβ是对应可见单元和隐单元构型的系统能量。Z是系统总的配分函数。 对实际分布和期望分布差异的一个自然度量是相对熵，Kullback-Leibler距离或Kullback-Leibler散度，即：

学习的过程 Boltzmann基于相对熵的梯度下降算法。训练模式集确定了Q（a），我们的目的是确定合适的权值，使得在温度T上实际分布Ｐ(a)与已知的Ｑ(a)尽可能地接近。 可以证明，权值更新公式为： 这里已定义 同样道理，对输入－输出联想的随机学习，我们也可以得到其权值更新公式为：

7.3.2 丢失特征和类别约束 丢失特征: Boltzmann训练算法的一个关键优点在于不管在学习阶段还是识别阶段，它都能处理丢失特征的情况。训练中如果遇到一个缺损的二值模式，则对应于丢失的那个特征的输入节点的值允许发生改变——也就是说，可以暂时地将它看作是隐节点，而不是箝位输入节点。 模式补足： 模式补足问题指的是：只给定模式的一部分，要求估计出完整的模式。 Boltzmann网络能够用于模式补足，也就是真充缺损模式中的位置特征。

7.3.3　确定性Boltzmann学习 确定性Boltzmann学习的基本方法就是对状态变量允许模拟取值，到最后自动收敛到问题所需的±1上。明确说，令D表示训练模式x的集合，x中包含模式特征和类别标记，其算法过程如下:

7.3.4 初始化设置 对于隐单元数，能够表示n个不同模式最少的隐单元数也是 7.3.4　初始化设置 对于隐单元数，能够表示n个不同模式最少的隐单元数也是 尽管如此，这个隐节点个数的下界仍然不够紧，因为有可能存在这样的情况，即无法找到合适的权值组合能够惟一的表达各个模式。 对于权值，当然可以将所有权值都初始化为0,但这样作将导致训练过程不必要的慢。我们可任意令一半节点权为正，另一半为负。初始值若限于一定合适的范围，将有利于提高学习速度。 对于初始温度，一般应该服从： 对于学习率η，出于稳定性的考虑，要求：

7.4　Boltzmann网络和图示模型

7.5　进化方法 7.5.1 遗传算法

遗传算子 在基本遗传算法中，每个分类器的表达是一个二进制的位串，称为染色体。 复制：染色体被原样复制一遍，不发生任何改变； 交叉：把两条染色体混合或配对的过程，得到两条新的染色体。在染色体上随机确定一个位置并开断，将A染色体的第一部分和B染色体第二部分连接，另一半也是如此； 变异：允许每个位以一个很小的概率改变自身，比如从0变成1,或者相反。 染色体表达 最早期最简单的是令染色体中各个位表示 一个具有固定权值的两层感知器网络的各个特征； 另一种方法是令染色体的不同片断表示一个具有固定拓扑的多层神经网络的各个权值。类似地，染色体也可以用于表达网络的具体拓扑结构。

得分 对c类分类问题，通常最简便的做法是进行c次二分法操作，每一次将一个不同类别与其他所有类别区分开。进行分类时，测试模式依次提供给每一个二分法，并进行相应的类别标记。 但考虑到“过拟合”问题。一种避免“过拟合”的方法是在适应度函数中增加对分类器复杂度的征罚项。别外一种方法是运用停止准则。 选择 所谓选择，是指确定在某一代中哪些染色体可以作为父本为下一代提供遗传信息。其主要的译意风所谓的“比例适值选择”，即选中某条染色体的概率正比于其适值函数。 该方法的一种小小的修改是令选择概率正比于适应度的某个单调递增函数。如果该函数具有正的二阶导数，那么高适应度染色体被选 中的概率就会被增强。

7.6　遗传规划