419
龚光鲁,钱敏平著 应用随机过程教程 – 与在算法和智能计算中的应用
清华大学出版社,2003
第 15 章 与数据建模有关的几个算法
1 EM 算法 – 隐状态变量分布中参数的最大似然估计
1,1 EM 算法的 基本想法
在数据资料不全 时,由已有的资料 Y 估计 缺失变量 X,或在观测到的资料 Y 并不是状态变量时,估计 状态变量 X 时 （ 或 者 估计其分布密度 ),( xf J 中的未知参数 J ）,就 与古典统计 很 不 相 同,此时 需要用观测到的资料 Y,同时估计 X 与 未知 参数 J,
这样的估计 将 面临如下困难,如果把在参数 J 下的期望记为 JE,那么,在估计状态变量 X 时,估值当然应该用条件期望 )|(^ YXEX J= ( 如果在 J及yY = 的条件下,X 的
Bayes 分布密度 ),|( Jyxf 为已知,则也常用 Bayes 估计 ∫= xdYxfxX ),|(^ J ),然而这时就需要知道参数 J 的值 ; 另一方面,为了知道 J,又必须先知道 X 的估值
^X
( 作为状态的已知样本值 ),这样,估计状 态 与估计 未知 参数之间是耦合的,
在统计中通常对付这类困难的 解耦方法 是,假定一个已知,迭代地 分别交替估计它们中的 另 一个,直至稳定,此类算法通称为 EM 算法,较为确切的表达是,
( 1 ) 设置初值 0J ；
( 2 ) ( E - 步骤 ) 对,0≥n 令 )|(
^
)( YXEX
n
n
J= ( 或用 Bayes 估计
∫= dxYxfxX nn ),|(
^
)( J ) ；
( 3 ) （ M - 步骤 ）（ 修正 J 的估计 ） 取 1+nJ 使之满足,
),(log),(log
^
)(
^
)(
1
nn
n XfMaxXf JJ J=+,
其中 E - 步骤为取条件期望 ( Expectation ),而 M - 步骤为取最大 （ Maximum ）,这种交替迭代的方法,称为 简单 的 EM 方法,
这个算法的 构思 很简单,但计 算量过大,且一般 很 难看出是否 稳定,为了克服这个缺点,Dempster,Laird 和 Rubin 提出了直接递推估计 J 的想法 ( 仍旧称为 EM 方法 ),这种经过本质改进后的方法,至少在直观上看起来有 稳定 趋势,
1,2 Rubin 算法
假定 ),( YX 具有联合分布密度 ),,( yxf J
Rubin 算法的核心 构思 为,直接使用状态变量 Y 的分布密度 ),( yg J 代替 ),( YX 的分
420
布密度 ),,( yxf J,来求 J 关于 ),( yg J 的最大似然估计
^J
,也就是 求使 ),(log Yg J 达到最大的
^J
,
由于 ),( yg J 在实际上 并 不好求,Dempster – Laird - Rubin 利 用了 下述等 式
),,( yxf J = )|,( yxf J ),( yg J,(15,1)
于是
=),(log Yg j?),,(log YXf j )|,(log YXf j,(15,1) ’
其 右方是状态变量的 对数 似然密度与 对数 条件似然密度 的 差,对 等式 两 边 取 关于 Y 的 条件期望得 到
),(log)( YgL jj?= （ )|),((log YYgE jJ= ）
)]|,(log|),,(log YXfEYYXfE jj JJ ［）］（［?=
)|()|( JjJj HQ?=?,(15,2)
在观测 资料是 y 的时候 ( 即 yY = 的 时候 ),)|( JjQ 的表达式为
)|( JjQ xdyxfyxf YX )|,(),,(log | qj∫=,
而 )|( JjH 的表达式为
=)|( JjH xdyxfyxf YX )|,(),,(log | qj∫
xdyxfyxf YXYX )|,()|,(log || qj∫=,
为了求 )(JL 的极大值点,我们将沿 用第 10 章中对 得到 隐 Markov 模型 的 模型参数估计 的 Baum - Welsh 算法的思想,为此注意
)]|()|([)]|()|([)()( JjJJJJJjJj HHQQLL?+?=?
xdYxf
Yxf
Yxf
QQ YX
YX
YX )|,(]
)|,(
)|,(
[log)]|()|([ |
|
| J
j
J
JJJj ∫+?=
)]|()|([ JJJj QQ?≥,(15,3)
其中用到 第 ２ 项是 相对熵的非负性,由 (15,3) 可知,
只要 0)|()|( ≥? JJJj QQ 就有 0)()( ≥? Jj LL,
421
所以,为了 将 J 的较粗估计 nJ,修改为较精的估计 1+nJ,只需找 1+nJ 使
0)()( 1 ≥?+ nn LL JJ,也 就是 只需要找 1+nJ 使
0)|()|( 1 ≥?+ nnnn QQ JJJJ,(15,4)
于是我们就得到如下的 Dempster – Laird - Rubin 的 EM 算法,简称 Rubin 算法 或 EM 算法,
( 1 ) 设置初值 0J ；
（ 2 ）（ E - 步骤 ） 对于,0≥n 计算 )|( nQ Jj xdyxfyxf YX )|,(),,(log | qj∫= ；
（ 3 ）（ M - 步骤 ）（ 修正 J 的估计 ） 取 1+nJ 使
)|()|( 1 nnn QMaxQ JjJJ j=+,(15,5)
由于 将 nJ 修正为 1+nJ 时,)|( 1 nnQ JJ + 比 )|( nnQ JJ 大,所以 )( nL J 是不减的,这就说明
nJ 有收敛的趋势,Rubin 证明了,在一定的条件下,nJ 确实按概率收敛于某个
^J
,于是我们可以合理地把
^J
作为分布的参数 J 的较佳的估计
注 1 )(JL 是多峰函数的时候,
^J
有可能 是 )(JL 的 局部 最大值,甚至是鞍点,为 了
纠正这种 不足,一般 可以 从多个初始值出发,找到多个
^J
值进行比较,
注 2 所谓,缺失资料,可见之于两种情形,一种是观测资料的丢失,另一种是人为
地设置一些,后台操作的,辅助随机变量,称之为 潜变量,将他们视为缺失的资料,即将他们视为不能直接测量到的状态随机变量,这种潜变量的取法可以非常灵活,依赖于人们对于问题的认识,经验的积累与对于技术掌握的成熟程度,从数 学处理的角度考虑,最好能选取潜变量 X,使它与观测随机变量 Y 的联合分布是指数型分布 ( 参见第 1 章 ),这时 E - 步骤就很容易计算,
注 3 在离散随机变量的情形,E － 步骤中的积分应该相应的改为求和 。
以上算法 也同样将 隐马氏模型中的 Baum - Welsh 算法,纳入 了 EM 算法的框架,
１,３ EM 算法的变通 – 广义 EM 算法
在实际计算中,又因为 E -步骤 的计算量很大,人们 常常 并不真去 计 算条件 期望,而是采用随机模拟,即,用在 ),( YnJ 已知的条件下,用随机模拟得到 X 的 Bayes 分布的若干独立随机数,代入 ),(log Xf j 后作样本平均,用来代替 )|( nQ Jj,这就大大地减少了计算量,实践表明这样的简化,常可以得到相当满意的效果,
同样,也因为 M-步骤 的计算量也很大,人们也 常常并 不去算最大,而是任意找一个
j,只要满足 0)|()|( ≥? nnn QQ JJJj,就取 j 为 1+nJ,这样简化了的算法,称为 广义
422
EM 算法,常称为 GEM 算法,
[注 ] 在应用 EM 方法时,为了避免 M-步骤中求 最大 值 的复杂计算,还 可以采取 其它的 灵活的替代方法,例如 有
ECM 算法 (Conditional Maximum,CM),在 多个 参数 的时候,例如 ),( 21 JJJ = 的情形,如下 的 交替 地求条件极值 的 最大化 的方法,也常被用来 代替 M-步骤,
(1) 先取 )1(2 +nJ 满足
=+ )|',(( )()1(2)(1 nnnQ JJJ )|)',((max )(2)(1'2 nnQ JJJJ ;
(2) 再取 )1(1 +nJ 满足
)),(|),(( )1(2)(1)1(2)1(1 +++ nnnnQ JJJJ )),(|),'((max )1(2)(1)1(21'1 ++= nnnQ JJJJJ,
称之为 ECM 算法 。 一般地,ECM 算法 比 EM 算法 达到稳定的时间长,
另有一种 ECME 算法 (混合算法 ),它就是 交替地使用 ECM 算法 和 EM 算法,
* 2,在 数据不完全时,用增补潜在数据,对参数的 Bayes 分布作估计 – Tanner –Wong 的潜变量法
２,１ 基本想法 － 估计后验分布
在数据资料不全 （ 缺失数据 ）,或观测到的资料 Y 并不是状态变量时,估计状态变量 X 的分布密度
),( xf J 中的未知参数 J,与古典统计不同 处 是只能 用观测到的资料 Y,这时 可以 通过 后验分布密度
)|( Yp J 得到参数 J 的 Bayes 估计,然而,后验分布 )|( Yp J 一般 并不知道,就 需 要 用 观测到的资料 Y
对后验分布 )|( Yp J 进行估计,这就是本段的目的,
Tanner – Wong 的想法是,在某些情形下,由观测数据 Y 可以通过条件分布取样的机制,来构造 某种 ＂ 增补数据 ＂ (记为 Z,称为 潜变量,Latent Variable) 的样本值,于是 Z 的这些样本值取自条件分布密度 ),|( Jyzp,)|( yzp 称为 预测分布,而 在 yY = 已知的条件下,潜变量的 各个样本值彼此 是条件独立的,
潜变量 Z 是观测不到 的,如何选好它,最为重要,最简单的情形是,观测数据 NYYYY,,,21 L=
为 N 个时刻的历史资料,其中 iY 是一个 m 维向量,如果 它的第 １ 个分量是缺失的,而其它 1?m 维就是状态变量,这时候潜变量就可取为那个缺失的一维变量,
然而,一般情形远非如此简单,潜变量的选取是关系到能 否 有效地计算的关键,Tanner-Wong 选取
Z 的原则是,同时满足以下两个条件 （ 注意在上面所提到最简单情形,下面的条件是满足的 ）,
423
（ １ ） 易于模拟 条 件分布 ),|( Jyzp 随机数,
（ ２ ） 容易计算 后验分布密度 ),|( zyp J,
下面的讨论都基于 （ １ ），（ ２ ） 均 能够施行,
2,2 未知参数的 后验分布的 迭代估计
一旦选定潜变量以后,利用广义全概 率 公式,就得到
zdyzpzypyp )|(),|()|( JJ ∫= (15,6)
和
*** )|(),|()|( JJJ dypyzpyzp ∫=,(15,7)
这两个关系式是设计迭代算法的基点,
（ 迭代可能性的理论依据 粗略地为,把 (15,7)代入 (15,6)得到
*** )|(]),|(),|([)|( JJJJJ dypzdyzpzypyp ∫∫=
*** )dy|)p(,K( JJJJ∫=记为,
这 说明 )|( yp J 是 积分核 ),( *JJK 的不变函数,积分核 ),( *JJK 依赖于观测值 y,但是观测值 y 是固定的,所以没有将它计入记号,只要对积分核 ),( *JJK 作适当的假定,就可以使迭代算法收敛到积分核的不变函数 ）,
由于积分核是不知道的,我们 就不可能直接利用 以下的迭代 算法
**
n
*
n )d()g,K(g JJJJJ ∫=+ )(1
近似 其不变函数,Tanner – Wong 提出用 Monte Carlo 迭代方法给出 )|( yp J 的 一个 估计,Tanner – Wong
设计 的 迭 代算法 是,利用按预测分布的多个独立取样,得到潜变量的多个样本值,通过它们由后验分布
),|( )(izyp J 们更新未知参数 J 的 后验密度 )|( yp J 迭代估计,注意 (15,6) 说明 )|( yp J 是
),|( zyp J 关于预测分布密度 )|( yzp 的数学期望 。 因此 如果得到了潜变量的多个样本值
)()1(,,mzz L
,就可以作 )|( yp J 的 如下的 估计
),|(1)|( )(
1
^ im
i
zypmyp JJ ∑
=
=,(15,8)
对 此 还 需要计算 潜变量加入条件的 后验分布 ),|( zyp J,
于是,估计未知参数 J 的后验密度 )|( yp J 就归结为 以 下的迭代程序,
（ 1） 置初值 )|(0 yp J ;
424
假定已经算出了 第 n 次迭代的 )|( ypn J,那么第 1+n 次迭代的 )|(1 ypn J+ 用以下的两个步骤轮番地修改 得到
（ 2） I (Imputation) 步骤 (得到潜变量的条件样本 ),先按 )|( ypn J 对 nJ 作随机取样,再
按 ),|( nyzp J 独立地取样 m 个,
)()1(,,mzz L
(m 充分大 );
（ 3） P (Posterior) 步骤 (用增补后验分布更新后验分布 ),令
),|(1)|( )(
1
1
im
i
n zypmyp JJ ∑
=
+ =,
３ 几种智能算法
3,１ 背景
随着高性能计算机的发展,出现了一系列算法,如神经网络,模拟退火,遗传算法,演化算法,隐 M arkov 模型,自适应算法等,它们大多出自仿真人的思维,不仅具有通用,稳健 (robust),简单及便于并行处理等优点,而且也有望成为将数值计 算与语义表达,形象思维等与高级智能行为相联系的桥梁,事实上,把人的智能与思维仅仅理解为主要是逻辑思维,
是有很大的片面性的,与逻辑思维相反的以因果思维与统计判决为代表的非逻辑推断,应该说在日常推断中是更为本质的,例如,在逻辑推理中,从,A 蕴涵 B” 这个命题能作的推理是,一旦 A 出现,就立知 B 发生,这只是一种简单思维,而人类的智能推断是更为高级的思维,其判断过程却往往是一个由,结果,探求 其,原因,的相反过程,例如,医生诊断疾病时,常常是,由,疾病 A 有症状 B,这一命题,从病人有症状 B,反过来推断病人有多大的可能有疾病 A,这是一种非逻辑的推断,含有不确定性,还有犯错误的风险,然而这正体现了人类的高级智能活动,同样的推理还有,法医尸检死因,侦探寻找作案人,天气预报,考古分析,矿藏探测等等,与之相联系的计算方法都 可 归入智能算法,
一般地,智能算法常具有以下的特点,
(1) 大都引入了人为的随机因素,因而其计算过程实际上是作随机过程的模拟,然而,这种人工噪声的作用不仅不起干扰的作用,而是相反地起正面的作用,使用它完全是为了控制 计算的进行方向,
(2) 大都具有自适应机制,可以在计算过程中不断调整,
(3) 大都是针对通用的目标函数而设计的,并不采用具体问题具体处理的启发式方
法,
(4) 不少算法是对高维及复杂情形设计的,它们在低维或简单的情形有时效果很差,
有时也显得很 笨拙,
３,２ 决定性的人工神经网络
神经网络是一个由彼此具有相互作用的多个神经元联结在一起的一个系统,作为神经网络的整个系统的协同工作产生一个总的效应,这个总的效应是一种功能,它可以是对应于一定的输入时有一定的相应输出,也可以 是一种记忆功能,神经网络的重点是功能研究,在功能研究的基础上,构造具有相互作用的粒子系统,称为人工神经网络,以仿真地起到成为模拟某种功能的功能器,在数学上,人工神经网络也可以用来构造具有某种给定功能的分片线性处理器,人工神经网络的操作一般具有黑箱的特点,神经网络方法的精神在于,
由从例子 ( 即样品 ) 学习中,归纳出规律,
425
因此,它并不需要知道数据来自的对象的机理,这是它的长处,当然,在规律较为明显的情形,它也就会显出不足,总体看来,可以说神经网络方法是有别于经典统计的一种另类统 计方法,
人工神经网络可分为决定性的和随机的两大类,它们又各自包括各种不同类型的神经网络,这种不同的神经网络的构造,是根据要求它完成某种制定的特殊功能而设计的,而 随机因素的引入,是为了使计算更稳定,减少往错误 的 方向进行的可能性,
决定性的人工神经网络,如 前传神经网络与随机过程并没有关系,但是它是人工神经网络的基础,它有广泛的应用,再则,通过它不仅可以了解人工神经网络的原理与功能,并且也可以更好地理解随机的神经网络,所以本书也采纳了决定性的人工神经网络,以下我们先介绍 决定性的前传人工 神经网络,而把更为一般的决定性的递归神经网络放在随机神经网络中一并处理,
3.2.1 决定性的前传人工神经网络
1,前传网络的概念
最常见的人工神经网络是多层前 传网络,这种网络可分为多层,其中 每层有一些单元组成,一般分为 3 种层次,依次为,输入层 ( 由接受输入数据的神经元组成,它们不受其他神经元的相互作用 ),隐层和输出层,作为中间层的隐层,又可分为若干个子层 ( 由 Kolmogorov
的理论结果,它等价于只有一个隐层的某个系统,然而在实际计算中,往往以采用多层更为方便,灵活 ),所谓前传网络,就是信息只能由前向后传,只有前一层的单元对其后一层的单元可能有相互作用,每一个隐层或输出层都由许多感受子 (perceptron) 组成,每一个感受子就是一个受到网络相互作用的神经元,在前传网络中,这种相互作用只允许来自上一层的神经元,
最 典型的是具有 3 层的全连接前传网络,其隐层元,例如,可以取 6 个至 8 个神经元,网络的效果相当于分片线性近似,它 是一种进行自适应学习的非线性处理器,其典型的 模式是如下的受门限限制的线性作用,设输入层为 m 个输入神经元 ),,( 1 mxxx L=,隐层 有 l 个神经 单元 (体现为分量 ) ),,( 1 lhhh L=,而输出层为 n 个单元 ),,( 1 nyyy L=,用权重
)3,2()2,1(,
klik ww 分别表示输入元 i 给隐元 k 的作用 (强度 ),和隐元 k 给输出元 j 的作用,通常取门限函数 g 为在 0 点的单位阶跃函数
<
≥=
)0(0
)0(1)(
x
xxg,(15,9)
或 S 形阈值函数,例如,
,1 1)( axexg?+= 或 ),arctan(2)( axxg p= )0( >a,(15,10)
于是输入层到隐层间的转递为
)( )2,1( ki
i
ikk xwgh q?= ∑,(15,11)
而隐层到输出层的转移为
)'( )3,2( jk
k
kjj hwgy q?= ∑,(15,12)
其中 ',jk qq 是为了方便而预先设置的 门限 常数,称为阈值,,在 g 为在 0 点的单位阶跃函数
426
时,g 取值 1 对应于神经元处于激发状态,取值 0 就表示处于抑制状态,在 g 为 S 形函数时,对应神经单元取连续的状态值,这种假定有利于在一些近似运算中求导数,此外即使在神经元只取抑制和激发两种状态时,也可以 设 置抑制和激发以外的 一些 缓冲状态,
前传神经网络是一种最简单的非线性处理器,即 一种 分片线性处理器,其 输入是输出的分片线性函数,也就是由样品确定参数的分片线性近似器 (把它与用样条函数 (Spline)近似作比较,前传神经网络除了有输出对输入并不可微的缺点外,操作与运行都远为简单 ),
2,前传人工神经网络的建模与应用
神经网络主要用在建模,模式识别,图像处理,基因表达等领域,多层前传网络的使用可以分为两个相位,训练学习相位 与 运转相位 ( 操作相位 ),
学习相位就是通过对样品的加工计算,得到权重常数 )3,2()2,1(,kjik ww 和 门限 ',jk qq 等参数的估计值,使得在这组参数估计值下,该神经网络能相对最好地执行我们冀望它完成的任务,
神经网络的学习方法分为有监督的学习与无监督的学习,多层前传网络大多采用有监督的学习,其中最广为应用的是误差后传法,有监督的学习 是 指我们可以得到一组给定输出的输入样品,在学习时可利用已知的输出 参照 比较,学习的目的 就是找出最佳未知参数,使得当将样品的输入部分输进这组参数下的网络时,能使输出最接近样品相应的输出,其要点就是根据已知的典型输入和输出,来估计连接系数 )3,2()2,1(,klik ww,而 其 实质 是 灵活 地 运用 最小二乘法,
误差后传法的主要步骤是,
( 1 ),设定参数的初始值 ;
(2 ),逐个或按 随机顺序将样品的输入,输进初始参数所对应的网络,得到输出,并将其与该样品应有的已知输出进行比较 ;
(3 ),校正最后一层 ( 设为第 n 层 ) 的网络参数,得到使得输出最接近于应有输出的最后一层参数,并解出使得误差最小的第 1?n 层输出 ;
(4 ),将第 1?n 层当作第 n 层,重复 (3 ),校正第 n - 1 层的参数,并求出 第 2?n 层输 出,使得 第 1?n 层的输出误差最小 ;
(5 ),重复 ( 4 ),向前面各层推进,直到求出所有各层的参数 ;
(6 ),重复步骤 (2 ) 至 (5 ),直到看起来稳定,
这个算法 是在未知状态 ( 各个神经元的状态 ) 的情况下估计参数,这也是缺失数据的一种参数估计,在估计参数的优化过程中,由于目标函数是非线性的,且变量数又十分大,计算往往会陷于局部极值,因此,也 可 考虑应用模拟退火等整体优化方法,
另一个相位是运 转相位,它是在学习相位的 基础上 ( 就是在确定参数以后 ),神经网络中各结点 ( 即神经元 ) 的状态按规定的方式运行 ( 即 进行运算 ),以 执行希望达到的任务,如 预测,
识别,分类等目的,
前传网络在计算机科学,人工智能等领域中有广泛的应用,它是一种比较好的另类回归模型,
3,2,2 一般的 决定性的人工神经网络模型 ( 神经元未必只取 1 或 0)
在一般的情形,神经网络对神经元 x 的总 相互作用 可以 表示 为
))()(),(()( ∑?= y xyyxwgxh qh,(15,13)
其中 ),( yxw 是神经元 y 对神经元 x 的相互作用势,)( yh 是神经元 y 所处的状态,而
427
)( xq 则是神经元 x 的激发门限值,在神经元只取 ０ 或 １ （ 抑制 或 激发 ） 两种状态时,乘积
)(),( yhyxw 是神经 元 y 对神经元 x 的作用力,g 为门限函数,它是对自变量的总相互作用超过门限的部分起的作用,其中的和号取遍一切对于神经元 x 有相互作用的神经元 y 的全体,
３,３ 随机的人工神经网络
3,3,1 一般概念
在随机的神经网络中,下一层神经元 x 被 激发 的概率 取 为
∑?
=
x
xh
xh
e
exp
)(
)(
)( b
b
,0>b,(15,14)
显见 在 )(xh 越大处,)( xp 也越大,即该处的神经元 x 被激发的概率越大,随机的神经网络与相互作用粒子的随机系统非常类似,它的运转 是一个 Markov 链,
随机因素的加入,在下面的递归网 络中能 起控制计算进行方向的稳定作用,
3,3,2 递归 ( 或反馈 ) (recurrent) 网络与 Boltzman 机
递归 ( recurrent ) 网络 也称为 反馈网络,它实际上是以全体神经元所处的状态 ( 称为一个组态 ) 为变元的 一个 动力系统,因而也具有反馈的连接,在数学上反馈提供了迭代的功能,
所以,同样作为离散动力系统,递归网络比前传网络具有更大的非线性功能,因而有更强大的应用潜力,递归网络也可以是决定性的,也可以是随机的,随机 情形的网络,是按一个随机的规则发展的,因此,全体神经元所处的 状态的时间发展,就是一个 Markov 链,
１,Hopfield 网络
Hopfield 把网络与吸引子联系起来,由此给出了一种联想记忆的模型,并给出了一种学习方法,通过学习训练确定网络连接参数,以能够使它达到所希望有的功能,Hopfield
网络是一种典型的递归网络,它源自人脑机制的研究,Hopfield 提出这种网络是希望用数学模型仿真人脑的功能,这种网络具有反馈的连接,相当于一个离散的动力系统,它不像前传网络那样简单地对输入与输出的关系感兴趣,决定性的 Hopfield 网络,一般 地 没 有输入与输出,在给定初值后,就可以通过网络的运转不断地自动更新,最后落到网络系统的某些不变集上,在这意义下可以说并没有真正的输出,但是可以通过某些手段观测到它的自动更新的进程,
(1) 决定性的 Hopfield 网络
神经网络是一个由 N 个神经元彼此 由 相互作用而联结在一起的一个系统,整个系统在协同工作下产生一个总体效应,Hopfield 网络的总体效应,是提供记忆的数学模型,即联想记忆模型,设每个神经元可以取 1? 与 1+ 两个状态 之一,其中 1? 代表该神经元处于抑制态,1+ 代表该神经元处于激发态 。 把 N 个神经元处的整体所处的状态的全体记为 X,即
)}(,11:),,{( 1 NixxxX iN ≤+?== 或L,
设神经网络对神经元 x 的总相互作用是 (它是 (15,13) 的特殊情形 )
)sgn(
1
ikik
N
k
i xwy q?= ∑
=
,(15,13)’
其中与神经元 i 相连接的神经元 k 有一个连接系数 ikw,并且假定满足 ikw kiw=,
428
学习位相就是要估计这些参数,可以用 EM 算法,
运转相位有异步动力学与同步动力学两种不同的方式,Hopfield 的异步动力学发展是每次只容许依次地改变一个神经元,其具体步骤为,
(A) 先按 (15.13)’ 把 1x 更新为 1y,并用 1y 取代 (15.13)’ 右方的 1x ;
(B) 把 2x 更新为用 (15.13)’计算出的新的 2y,并用此 2y 取代 (15.13)’ 右方的 2x ;
(C) 再把 3x 更新为用 (15.13)’计算出的新的 3y,并用此 3y 取代 (15.13)’ 右方的 3x ;
(D) 如此依次地,一个一个地使网络中的所有 N 个神经元都更新一遍 ;
(E) 重复 (A)至 (D),
Hopfield 同步动力学发展与 Hopfield 异步动力学发展的不同 之 处是,不限于每次只改变一个神经元,同步动力学的时间发展,是通过 (15,13) ’把网络的状态从 ),,( 1 Nxxx L= 转移为 ),,( 1 Nyyy L=,把它改写为通常的离散的动力系统 就是
→=? ),,( )()(1)( nNnn xxx L ),,( )1()1(1)1( ++?+ = nNnn xxx L,
)sgn( )(
1
)1(
i
n
kik
N
k
n
i xwx q?= ∑
=
+,(15,13)’’
同步动力学常常比异步动力学有更多 的 不变集,
递归神经网络更接近于生物神经网络,特别是 Hopfield 网络,它提供了一种联想记忆模式,即把 神经网络动力学发展的一个不动点,或一个不变集 ( 统称为神经网络的吸引子 ),
解释为一个记忆,这种记忆模式具有与传统的 地址 记忆模式 ( 如笔记本,硬盘,光盘等 ) 完全不同的机制,它的记忆恢复 不 需要 利用 存入记忆的目录索引,而是按内容存取,因而 它 是迄今为止最接近于脑记忆功能的网络模式,当然为了增加新的记忆,就必须不断地更新整个神经网络,使得它能容纳新的吸引子,
（ ２ ） 随 机的 Hopfield 网络
l 随机的 Hopfield 异步神经网络
随机的 Hopfield 异步网络,是 按照类似于随机场那样给出 相互作用 的,神经网络的时间发展是随机的,即 按照一个 Markov 链 nx 作随机转移,其中整个网络的状态 ( 组态,记为
),,( 1 Nxxx L= ) 之间的转移概率,例如可以 取 为
≤=
====
+?
+
)(0
)),,,,,,,((1
)|(
111
1,
其它情形
NixxyxxyN
xyPp
Niii
nnyx
LL
xx,
此处 )sgn(
1
ikik
N
k
i xwy q?= ∑
=
,),,1( Ni L=,
注意,异步 Markov 发展的要义 在于,转移矩阵是 Gibbs 型的,即转移时在网络的 N 个
429
神经元中只容许改变一个神经元,
l 随机的 Hopfield 同步神经网络
同步 Markov 发展的要义是,按转移矩阵转移时,在网络的 N 个神经元中可容许同时改变所有的神经元,在 Hopfield 同步神经网络 中 的时间发展 也 是随机的,按照一个 Markov
链 nx 作随机转移,整个网络的状态 ( 组态 ) 之间的转移矩阵中,还 常常 引进了一个倒温度参数 b,转移矩阵 则 可以 由下式给出 ( 假定 0)(
1
≠?∑
=
ikik
N
k
xw J )
iikik
N
k
yxw
N
i
nnyx
e
xyPp
)((1
1,
11
1))(|)(()(
Jb
bxbxb
=
+
∑+
====
=
∏,(15,15)
注意,在 ∞=b 时,x 就 概率为 1 转移为 == iN yyyy ),,,( 1 L )(),(
1
Nixw ikik
N
k
≤?∑
=
J,
这 就成为确定性的网络,这个 Markov 链与 I sing 模型的 Glauber 动力学非常相像,容易检查它有配称分布,且 其 配分函数 为
iikik
N
ki
yxw
y
exZ
)(2
1)(
Jb
b
∑∑
= =∑,
所以,此 Markov 链有可逆不变分布
)(
)()(
xZ
xZx
x
b
b
bp ∑
=,
决定性 Hopfield 同步网络的动力学发展的吸引子,就是 (15.13),的不变集,也就是方程
)sgn(
1
ikik
N
k
i xwx q?= ∑
=
(15,16)
的解 x,可以证明,对于 随机的 Hopfield 网络的 Mark ov 链 nx 发展而言,只要适当地控制倒温度 b,就可以使 Markov 链 nx 以大概率相对地留在方程 (15.16) 的某个指定的解附近,这就使随机 Hopfield 网络能够很好地解释联想记忆的机制 ）,
决定性 Hopfield 网络的联接系数的学习与更新
前面我们已经说过,Hopfield 网络的功能是用描述其网络发展的离散动力系统的吸引子给出 的 联想记忆模式,如何对 H opfield 网络确定个联接系数 }{ ikw 使它能容纳给定的记忆 ( 即吸引子 ) 呢? 这就需要对联接系数进行学习更新,Hopfield 给出了如下的学习律,如果要使 y 成为吸引子,只要把原有的联接系数
}{ ikw 更新为新的联接系数 }'{ ikw,其中
430
='ikw )12)(12(+ kiik yycw,
但是,在此模型下,更新联接系数后的网络并不一定保留原网络的吸引子,除非假定各次加进的吸引子是彼此独立的,所以用 Hopfield 网络来描述记忆远非完善,有很宽广的研究余地,
２,Boltzman 机
在 Hopfield 同步动力学网络中再加进输入神经元与输出神经元,就得到一种更为广泛的神经网络模型,称为 Boltzmann 机,Boltzman 机是一种神经网络,整个网络的时间发展也是一个 Markov 链,一般 设置 了 输入,Boltzmann 机 也 可以看成是前传网络与 Hopfield 网络的结合与推广,它并不对输入层神经元加以,没有 相互作用,的限制,也不限制相互作用只能由前向后,它又 设置 了 输出神经元,同时它还是一个递归式的网络,所以它兼有两种网络的优点,可用以描述和模拟十分复杂的系统,具有很强的功能,
Boltzman 机的学习方法 也 是用 EM 算法,由于 Boltzman 机计算量非常大,学习起来很复杂,用来解决实际问题远不如前传多层网络普及,但 应用 潜力却高于后者,
Boltzmann 机输入神经元的状态由每个时刻的瞬间输入决定,而输出神经元是可观测的,设整个网络有 s 个输入 单元,m 个隐单元,r 个输出单元,若以
)(),(),(),(),(),( rjnOmlnhsknI jlk ≤≤≤
分别表示输入神经元,隐神经元与输出神经元在时刻 n 的取值,在
))(,),(()( 1 nInInI sL?=,))(,),(()( 1 nhnhnh mL?=,))(,),(()( 1 nOnOnO rL?=
已知条件下,)1(),1( ++ nOnh 分别取值 ),,(),,,( 11 rm zzzyyy LL == 的条件概率 取 为,
(P ))(),(),(|)1(,)1( nOnhnIznOynh =+=+
jjmll znOnhnIU
r
j
m
l ynOnhnIU ee ))(),(),((11 ))(),(),(( 1
1
1
1
+?==? ++
= ∏∏
bb
,(15,17)
其中
j
O
ij
r
j
l
h
il
m
l
k
I
ik
s
k
i OwhwIwOhIU
)(
1
)(
1
)(
1
),,( ∑∑∑
===
++=,)( rmi +≤,(15,18)
对于 mi ≤ 及 mi > 分别表示网络对于隐单元与输出单元的作用位势,
可以看出如果 )(nI 是一个 Markov 链,那么 ))(),(),(( nOnhnI 也是一个 Markov 链,
Boltzman 机比同步网络应用更广,也更适合于复杂问题的模式识别,这种网络的缺点是,由样品的实测值来估计 相互 作用系数 ( 联接系数 ) },,{ )()()( OijhilIik www 的学习训练过于复杂,其计算量非常大,然而估计的效果比较好,而且很稳健 (Robust),
特别 地,如果只允许 I 对 h 及 h 对 O有作用,这样的 Boltzman 机 就是 随机的前传网络,
当 β =+∞ 时就退化为前传网络,
[注 ] 神经网络方法的隐单元数,连接与门限都可以调节,这种分片非线性近似具有非常大的灵活性,如果选取得当,运用得好,效果会非常好,有些人认为这种方法过于黑箱化,
会影响效果,其实效果不好往往 由于 选 取 不够灵活,并非方法的问题,再 则,在能量函数中
431
用 S 形函数 (sigmoid),比用两值函数 (signal)有明显的优点,例如在作分类器时,那些明显地属于某类的样本,既 需要让它们起作用,又 不能 让 他们 过分 起作用,因此需要用上下限来限制它们,而中间的 S 部分正是用以区分的重要部分,因为分类器的重要处在于边界处的区分,
当离散样本量不大时,作者的经验是,可以在每个样本附近的一个小球内人工地加入一些均匀随机样本,然后再分组,
３,４ 演化算法,遗传算法
遗传算法 (Stochastic Genetic Algorithm,SGA),或 演化算法 (evolution algorithm),是仿生算法,两者并无本质差别,只是不同的流派采用的不同命名,这 是借鉴自然界的进化过程而设计的,人们注意到自然界在长期的自然选择过程中,往往能够达到惊人的优化水平,就自然地想到模仿这一过程,进行优化处理,各种应用实例表明 这种算法 有较好的稳健性,
遗传算法是一种启发式的 Monte Carlo 繁 衍 算法,它 基于自然选择原理和自然遗传机制,
模拟自然界中的生命进化过程解决有复杂目标的非线性优化问题,包括参数优化,自动程序设计等 问题,这些问题的特点是,解空间是已知的,并 且可以 比较 不同解 的 优劣性,但 是,
由于这些问题的结构一般比较复杂,用一般推理的方法可能很难进行求解,与一般算法 不同,
这种算法 并不从 分析 问题出发,而 是 直接从解出发,先随机 地 的生成多个解,然后仿照自然界生物进化的思想,对这些解 作 遗传,杂交与 变异 运算,并根据优胜劣汰的思想保留更好的,
摈 弃较差的解,得到 子 代,再 不断的重复执行这种操作,直至 得到的 解令人满意为止,这种算法的优点是有智能性,包括具有自组织,自适应,自学习性,它无需事先研究问题的全部结构,再则,它具有并行性,极适合于大规模并行运算,而 其缺点在于计算量大,然而,如果 问题 的 解的适应性函数的性质不好 (例如,对于密钥号码的搜索问题,它只有一个解,其 适应性为 1,其 它 状态 的 适应性 全为 0),这 时 用演化算法 就 不能有效地求解,
遗传算法的基本形式是通过群体更新样本 ( 再抽样 ),作为自然选择,再佐以对样本作小概率的变异,以最终达到整体优化的目的,简单 地说,就是自然选择加以允许有小概率的变异,而 它的 其它变化形式,只是它在具体应用中作不同的修改 而 形成的,
遗传算法是一个群体优化过程,为了得到目标函数的最小 ( 大 ) 值,我们不是从一个初始值出发,而是从 一组初始值出发进行优化,这 一组初始值好比一个生物群体,优化的过程就是这个群体繁衍,竞争和遗传,变异的过程,所以,其主体算法在数学上可描述如下,
假定有一个单变量目标函数 U,我们 并不知道它的解析表达式,但是对于任意给定的 x,
我们通过实验可以测量到 )(xU 的值 ( 也就是知道函数的取值表 ),这时,)(xU 的优化问题
( 求 最大值或求 最小值的位置 ) 可以设计为如下的程序,
取 N 个个体,每个个体取一个初始值,把此 N 个值写成一个列向量 =0x
)(
)1(
Nx
x
M,我们引入此 N 个个体的时间发展机制,即它们以下面的随机迭代映射发展
nnn wf +=+ )(1 xx,
=
Nf
f
f M
1
,
432
其中的干扰随机向量
=
nN
n
n
w
w
w M
1
独立同分布,称为变异,从 nx 到 1+nx 的发展称为第 n 代到第 1+n 代的演化,从演化可以得到一个 Markov 链,而演化的目的是实现目标函数的优化,
希望通过它们的时间发展,最后进入目标函数的优化值 ( 最 小 值 ) 附近,
最简单的演化是按 某种优生原则,在此 N 个个体中选出 M 个进行优化 （ 竞争 ）,即选取 M 个分量,对选中的分量 i,例如 （ 假定
=
)(
)(
)(
1
xf
xf
xf
N
M ）,令
h
xUhxUxf
i
)()()(?+?=
( 在知道 )(xU 的表达式时,则取 )(')( xUxf?=,类似地,在求最 大 值的问题中,相应地用 if? 代替 if ）,而对没有选中的分量 j,则令
0,)( == njj wxxf,
这种迭代方案源自生物遗传的思想,)( xfx → 的转变,称为从父代到子代的遗传,用随机迭代映射的理论,在很宽的条件下,nx 有一个极限分布 )()( xF ∞,这个分布相对地更多地集中于目标函数的优化值附近,但是,这还不能完全达到求 )(xU 最 小 值的要求,求
Umin 的位置有多种方法,其中之一是第 8 章中介绍的模拟退火方法,另 外可以 再加入 父代与子代间的 竞争机制,称为遗传竞争,即令
nn
N
n
n
n wf +=
=
+
+
+ )(
)(
1
)1(
1
1 x
h
h
h M,
=
)(
)1(
N
n
n
n
x
x
x M,
其中
≥<=
+
++
+ ))()((
))()((
)()(
1
)(
)()(
1
)(
1)(
1 k
n
k
n
k
n
k
n
k
n
k
nk
n UU
UU
xhx
xhhx
若若,
上面讨论的是单变量目标函数的优化,在 目标函数是多变量函数 时 完全类似,在 1=M
且 f 满足一定限制条件下,用较多的概率论知识,就 可以证明,在这种竞争机制下,当
∞→n 时,演化算法最终 在 概率收敛意义下,趋向 目标函数取最小值点的某一个,
于是 我们 可以看到,遗传算法常常包含的机制 与步骤为,
(1) 参数选择 （ 设置初始值 ）,通常是对参数进行二进制编码工作,就是将空间中的一个点对应 于 一长串的单变量,对应于生物学中的每个,染色体,,这个二进制染色体的每一个二进制位称 之 为一个,基因,,基因的不同决定了染色体的不同,（ 需要注意的是,参数编码 并不意味着 仅仅 从十进制换成二进制这么简单,不同的参数根据取值范围和精度的不同,
433
变换方式也不同 ）,初始群体模型 (即初始值 )应该是随机产生的,其个体在模型空间中分布越均匀越好,以使模型个体有足够多的遗传物质,以便能较好的找到整体极值,然而,群体数量过大会导致计算量的激增,
(２ ) 竞争 遗传 (即 自然选择 ),竞争 选择是产生新群体 （ 子代 ） 的第一步,应 证优秀的个体的繁殖机会更大,这 就是 优生原则,选择初 群体 （ 父代,即 初始值组 ) 中的若干个个体来产生下一代,例如,可以 把目标函数作为评估函数 （ 这时的优化是 取 最大而不是取最小 ）,根据目标函数值的大小决定个体被选中的概率,并按这个概率选择初始群体中的个体,
以体现优生原则,具体地,竞争机制可以通过 用 Bootstrap 思想再抽样 (Re-sampling)来实现,例如说,对 每个 个体 ( 即函数定义域 (是 有限集 ) 中的 x ) 给予一个标志其优化程度的 评估 函数 (其归一化就是权重,可以看成概率 ),让具有更大的 评估 函数的个体以更大的可能性产生后代,例如,在求有限集上的函数 )0)(( ≥xf 的最大值的位置时,对 x 可取 评估 函数为 )(xf,并 设置一个门限 e,把 e<)(xf 的那些 x 先淘汰出局,而把留下的 x 们,按
1
)(
))(()((?
≥
∑= xfCxCf
xf e
是 归一化常数 )作重要度抽样,独立地取样 N 次 ( N 充分大 ),得到 N 个样本,假定其中样值 ix (一共只有有限个 )出现的次数为 )(,1 NNNN Li =++L,再把较小的 iN 们淘汰出局,得到,遗传,的子代 （ 与一般的优化方法类似,自然选择一般只能保证达到局部优化,而加上杂交和变异,能得到 整体性的 改进 ）,
（ ３ ） 杂交 (Crossover),指从亲本模型重组产生新的子体模型的过程,在遗传算法中,自然 选择和 杂 交是最重要的部分,真正体现了遗传的特点,杂 交就是遗传算法的 一种 繁殖过程,通过 杂 交可 扩大 当前的样本空间,选取亲本进行 杂 交的方式很多,一般可以设置一个交换概率 cP,并 选取一个亲本对,cP 越大说明要 杂 交的亲本对越多,还有一种方法是随机地从模型中选择亲本对进行 杂 交,杂 交的实质是在模型空间进行 更 大范围的搜索,搜索的空间区域可能与原来的采样区域相当的远,所以,这种搜索是属于非 邻 近区域的 （ 非局部的 ）
搜索过程,它可以产生一个很有效的模型空间普查,一种常见的杂交方法是,对于两个非常高维数的离散数据 ( 即被 选中的个体 ),决定性地或随机地取这两个数据的相同长度的一段分量,互相交换接成两个新个体,形成杂交的 子代 ( 对低维数据也可以便同地使用这种想法,
例如,在一维情形可以把两个选中的个体 yx,分别展开为二进小数列,决定性地或随机地取这两个序列中相同长度的一段互换,接成两个新个体 ),一般地,针对不同的实际问题,我们可以根据对所需优化的问题的了解,选取其 杂交 方式,
(4) 变异,变异是偶然 地对 后代中的一个随机选择的基因作随机摄动,这是一个低概率的随机变化过程 (即 设 定 的 变异概率 mP 很小 ),如果不存在变异,子代模型就永远得不到初始群体中没有的染色体基因,因而很难产生强有力的进化,变异的方法就是将某一个参数位的值,从 1 变为 0 或从 0 变为 1,即在优化过程中以小概率不按局部优化的方向进行,从局部看,这种演化似乎反而,劣化,了目标函数,但是,正是这种演化才为逃逸出局部极值的陷阱提供了可能性,由于我们可以控制,劣化,的变异只以很小的 概率发生,在计算 进行 了很多 代 后,总趋势会 向优化发展的,这种做法的基本思想与模拟退火算法是类似的,由于杂交和变异的存在,使遗传算法在模型空间 作搜索中 有很大的潜力,
(5) 更新,就是根据自然界中的,适者生存,的原则,取子代模型中的一个与其亲本比
434
较,摈 弃适值 （ 评估函数 ） 小的亲本或子本,这是 父代和子代之间的竞争,
(6) 算法停止规则,在多次进行 （ ２ ） 至 （ ５ ）（ 注意,这些步骤 并不要求按次序进行 ） 之后,模型群体经过多次的 竞争 选择,杂交,变异 和更新,群体的平均 评估值 （ 目标值 ）
逐渐变大,直至聚集在模 型空间的一个小范围之内,这时,可以用多种判别法来判断算法是否已经达到稳定,例如,可以用群体的平均目标函数值不变,作为算法可以停止的标准,也可以用群体的最大目标函数值与平均目标函数值 是否 接近,作为算法可以停止的标准等等,
总之,遗传算法是一组变量一起演化,所以是群体的优化,它特别适合于并行计算,
另外,群体的规模也可以不是恒定的,
4 聚类,Kohonen 自组织学习,自适应算法
４,１ k－ 平均 (k -mean) 聚类
概括地说,聚类问题就是根据一些样品,寻找较少数目的代表点 (在模式识别中就是 建立一些,标准,模板 的过程 ),这些样品称为学习样品或训练样品,一般 地,样品常具有很高的维数,而高维空间是非常 分 散的,样品的总数一般远远小于高维区域的离散采样 能近似地给出直方图所需的 数目,于是这种统计问题与经典的统计有很大的不同,这时,一个给定的子区域能包含样本点的可能性一般非常小,但是,如果样品数据集能很好地表达它的总体,一般地数据就会集中在一个体积相对地小的一个区域,于是聚类问题的重要点就是去发现这个分布的总体位于那一个相对小的区域,
k－ 平均聚类 就是预先设定为 k 个 类,从 样品 寻找 k 个 类 的代表点,其想法是,先随机地找 k 个点作为代表点的初值,按与这些初值接近的程度,把所有的样品点分成 k 类,然后求每个类的平均值,分别作为初值的修改值,再重复以上的步骤,直至稳定为止,
k－ 平均聚类 的优点是想法简单,设计方便,其缺点是缺少稳健性,对 初始值的取法与初始类的数目的设置都过于敏感,在这一方面,自适应聚类的 效果要明显得多,
４,２ 自适应聚类的基本思路
自适应聚类就是预先并不设定聚类的个数,而是 根据学习样品来得到,标准的,代表点
(或模板 ),这 就是学习或训练问题,其想法是,找到数目尽量小而能覆盖所有数据的一组小球 (这与数据压缩中的矢量量化有点类似 ),使每个球只包含一个模式的数据,这个球的中心就 可以作为 一个代表点 (或模板 ),随之,统计分析就可以只限在每个小球上 进行,而对于给定的样本的识别问题,就是要在代表点中找出这个被判别样本的合适代表,所以,模式识别就归结为决定被判定样本属于那一个球的问题,
自组织神经网络是 对于具有固定规模的学习训练问题 的 改进,这是一种自动确定代表点的 规模 大小 的 自适应聚类,其基本思路是,在聚类过程中,采取竞争学习的机制,这种想 法对于模板的样品集为非常分散的超高维数据的情形比较适用,如果一个样品在现有的模板中实在找不到合适的代表,那么,就用此样品作为一个新的模板,
４,３ 固定规模的 Kohonen 网络
Kohonen 的自组织拓扑映射 (Kohonen ’s Topological Mapping,KTM) 是一种功能非常强的,用作 聚类的 网络,但是其计算量非常大,网络的规模的确定也比较困难,然而,在一定条件下它可以改变为自动确定网络规模的算法,用它作计算机科学中的,矢量量化,( 相当于聚类,即选一些不依赖坐标的 代表点,每个代表点 作为 一个,向量,) 是很好的工具,KTM 的特长在于它要求有 所谓 的,拓扑性,,其 含 意是,用该网络所得到的代表点组能保持 标 号 的 序 之间的 拓扑 关系 不变,也就是,具有较近序标的两个代表点也较近,
KTM 的计算 步骤是,设样品集为 },,{ 1 mss L
435
(1),根据选取好的规模 ( 即代表点总数,记为 N ),随机地或决定性地选取一组初值,)}(,),1({ 00 Nxx L ( 一般每个 )(0 ix 都是一个 与 每个样品相同维数的向量 );
(2),随机地 ( 即独立同分布地,也可以按某一决定性的规则 ) 从样品集 },,{ 1 mss L
中读出一个样本 ny ;
(3),竞争修改待选的代表点,设 j 满足
)),(()),(( nnnn yixdyjxd rrrr ≤,),,2,1( Ni L=?,
则令
))())(,(()()(1 ixyjidaixix nnnnn rrrr+=+ r,
其中 )(rr 是一个严格单调递减的正函数,满足 1)0( =r,na 是一个使算法收敛的因子,称为冷却因子,而 ),( jid 则表示 ji,间的距离 ; （ 即其序标与和读 入 的样本最近的代表点的序标相近的代表点,在修改时 更多 地向读入的样本靠拢 ）,
(4),重复 (2) 和 (3),直至稳定,将稳定的结果记为,)}(,),1({ Nxx L,那么,
)(,),1( Nxx L 就是最后选取到的 N 个代表点,
Kohonen 猜测,在条件
+∞=∑ nn a,+∞<∑ 2nn a
满足时,算法是收敛的,)(rr 严格正能够使最后得到的代表点近似地有拓扑性,即除了较少数的例外代表点以外,对于多数 Nji ≤,,如果 i 与 j 较近则代表点 )(ix 与代表点 )( jx 也较近,
然而,除了一维情形以外,对高维的 K ohonen 网络 所 达到的功能,至今还只有计算机结果的图示,尚缺乏清晰的论述,还谈不上算法收敛性的严格证明,
如果不要求代表点具有拓扑性,那么 就 可以不必要求 )(rr 严格正,而 只需 0)( ≥rr,
即它可 以取 0,这表示在更新待选代表点的时间进程中,有些待选代表点可以在某些时刻不修改,其中最简单的是取
≠
==
)0(0
)0(,1)(
r
rrr,这称为,胜者统吃,的原则,它表示只对与读入样品 ny 最相近的待选代表点 做 修改,这 种 修改表现为往读入的样品 ny 处 拉近一点,此时竞争修改代表点的算法为,设 j 满足
)),(()),(( nnnn yixdyjxd rrrr ≤,),,2,1( Ni L=?,
则令
436
)(),()(1 jiixix nn ≠=+ rr,))(()()(1 jxyajxjx nnnnn rrr?+=+,
若每次只修改一个代表点,则 当代表点数很大时,这种算法要 比标准的 KTM 算法要快得多,例如,当代表点数为 300,则按,胜者统吃,的原则 计算 时,实践表明每次只修改一个代表点的算法比标准的 KTM 算法要快 300 倍,此外,为了具有拓扑性,需要调整代表点的排序,所耗费的时间远超过选取待选代表点的时间,文献中证明了,胜者统吃,算法的组态 ( 全体待选代表点组成的向量 ) 按 分布 收敛到一个分布 ( 当然 一般不具有拓扑性 ),再 则,从应用的角度看,给出 区间估计 往往 比收敛性更为重要,
[ 注 1] 按,胜者统吃,的原则来聚类,可以化为目标函数的最小值问题,设样品集为 },,{ 1 mss L,要得到 N ( Nm >> ) 个代表点,则代表点 Nxx,,1 L 就是目标函数
=),,( 1 NxxU L 2
1
),(min kiNi
m
k
sxd r≤
=
∑
取最小值之处,这个目标函数的含义为,对每一个样品 ks,希望在 N 个待选代表点
Nxx,,1 L 中选取一个与样品 ks 最近的,作为样品 ks 的代表,
[ 注 2] 对于代表点的规模不甚清楚,而有可能 出现 冗余 的待选代表点 的 情形,Jinwen
Zhang 及 Lei Xu 从另一种不同的角度考虑,对 于读入的样品 ny,让与它最近的待选代表点往 ny 拉一点,而让与它第二近的待选代表点往离 ny 远处推一点,而其它待选代表点则保持不变,这种想法是希望最后把冗余的待选代表点推向不起作用的遥远之处,此时,竞争修改代表点的算法可以为,如果 kj,满足
)),(()),(( nnnn yixdyjxd rrrr ≤,),,2,1( Ni L=?,
≤< )),(()),(( nnnn ykxdyjxd rrrr ≠)),(( nn yixd rr )),(( nn yjxd rr,
那么,例如,可以令
),(),()(1 kijiixix nn ≠≠=+ rr,
))(()()(1 jxyajxjx nnnnn rrrr?+=+,
))(())(,()()( 11 kxykxydbkxkx nnnnnnn=?+,
这种想法还相当于使用了类似于如下的目标函数,
=),,( 1 NxxU L ]),( 1min),([min ),(min),(,,2
1 00 kjsxdsxdijNj
kiNi
m
k sxd
sxd
kiiki =≠≤≤=
+∑ r,
实证显示,用这种想法常比,胜者统吃,能达到更为好的效果,这里目标函数的含义为,对每一个样品 ks 的代表点的选取,不只考虑与之最近的代表点的作用,还要顾及与之第二近
437
的代表点的作用,及希望兼顾地修改与样本最近的代表点使之更近,修改与它第二近的代表点使之更远,
4,４,网络规模的竞争学习
Kohonen 映射的缺点在于,
(1) 可能使计算陷入某种局部极小,为此 可以用加入随机干扰以逃逸出这类陷阱,
（ 2） 在 Kohonen 自组织算法中,必须 事先确定代表点 （ 小球 ） 的数目,但是通常给定一组数量较大或维数很高的数据,往往不能知道取多少代表点合适,这样,就自然地提出了怎样由数据自动地确定代表点的个数的问题,这就是规模问题,改进的方法是使代表点的数目依赖于网络的结构,这就是 4,1 段 中 的 自适应 竞争学习的思想,其目标是,对于给定的合适的精度 0>e,寻 找数目小而能覆盖所有数据的一组半径为 e 的小球,把一个小球的中心作为一个代表点 (在模式识别中代表同一类模式 ),在样品的代表球内就可以运用传统的统计,决定数据是否能降维,数据在球内的分布等等,在模式识别中,不同的球的 联系还有助于知道模式的非线性结构的复杂程度,而代表点 的 规模的大小,就相当于提供了用分片线性函数近似所需要的分片数与需要使用的神经网络的规模的信息,
对于自适应竞争学习,Grossburg 等提出了适应共振理论 (Adaptive Resonance Theory,
简称 ART),其含义为,当一个新的样本输入到学习的算法程序中时,只有它和某个待选代表点充分接近,它才能对这个待选代表点进行修正,这样就造成一种自适应的谐振状态,
ART 算法大致是这样,一开始选取代表点数很少或为 0 ; 由接受的 输入样本,按照预先设计好的相似度衡量方法与标志,充分接近,的门限,按照上述竞争原则,决定是否应按这个输入修正某个待选代表点,以及修正哪一个待选代表点,如果没有一个待选代表点和这一新的输入充分接近,则把 此输入 增加为一个新的代表点,
这 个算法有相当好的稳健性,目前文献中给出了两种相似度控制方法,e - 邻域控制法与中心控制法,这是多种模式的模式识别样品选取代表点 ( 并不要求一个模式只选取一个代表点 ) 的自适应方法,用这种算法对手写体数字模式识别的样品选取代表点 ( 矢量量化 ),
取得了很好的 效果,由于这种系列参数适应算法不要求事先给定网络规模和控制参数,从而,
它可以用来作为探索性统计分析的工具,
总之,自组织学习网络的中心思想,是利用演化历史中获得的信息指导搜索或计算,其中还可以人为地引入干扰,以免算法被套入局部陷阱,它一般表达为一个自适应的迭代算法,
其形式为
),,(1 nnnn wyxfx =+,
其中 nx 代表系统在时刻 n 时的状态,ny 代表样品,nw 代表为使搜索过程收敛而人工 加入的干扰,
5 适应最小二乘法 -- 一种适应的变步长的随机逼近
设线性回归问题的随机输入为 nx,观测为 ny,干扰为 nw,待估参数为 J 的模型为
n
T
nn wxy += J,
对此 可以设计如下的递推估计,
)( ^^1^ nTnnnnnn xyx JeJJ?+=+,
438
)( ^1 nTnnnnnn xyx Jgee?+=+,
)(1 11+= nnnn n eeee ∑
=
=
n
k
kn
1
1 e,
其中
∑ ∑ =∞=∞<
k k
nnk nO ),
1(,,gge 0→
ne,
那么,可以证明 n
^J
依概率收敛与某个
^J
,它就 作为 J 的估计,与经典的最小二乘法相比,这个方法优点是,它充分地利用了新的观测,递推地修改估计,并且最后达到概率收敛,
龚光鲁,钱敏平著 应用随机过程教程 – 与在算法和智能计算中的应用
清华大学出版社,2003
第 15 章 与数据建模有关的几个算法
1 EM 算法 – 隐状态变量分布中参数的最大似然估计
1,1 EM 算法的 基本想法
在数据资料不全 时,由已有的资料 Y 估计 缺失变量 X,或在观测到的资料 Y 并不是状态变量时,估计 状态变量 X 时 （ 或 者 估计其分布密度 ),( xf J 中的未知参数 J ）,就 与古典统计 很 不 相 同,此时 需要用观测到的资料 Y,同时估计 X 与 未知 参数 J,
这样的估计 将 面临如下困难,如果把在参数 J 下的期望记为 JE,那么,在估计状态变量 X 时,估值当然应该用条件期望 )|(^ YXEX J= ( 如果在 J及yY = 的条件下,X 的
Bayes 分布密度 ),|( Jyxf 为已知,则也常用 Bayes 估计 ∫= xdYxfxX ),|(^ J ),然而这时就需要知道参数 J 的值 ; 另一方面,为了知道 J,又必须先知道 X 的估值
^X
( 作为状态的已知样本值 ),这样,估计状 态 与估计 未知 参数之间是耦合的,
在统计中通常对付这类困难的 解耦方法 是,假定一个已知,迭代地 分别交替估计它们中的 另 一个,直至稳定,此类算法通称为 EM 算法,较为确切的表达是,
( 1 ) 设置初值 0J ；
( 2 ) ( E - 步骤 ) 对,0≥n 令 )|(
^
)( YXEX
n
n
J= ( 或用 Bayes 估计
∫= dxYxfxX nn ),|(
^
)( J ) ；
( 3 ) （ M - 步骤 ）（ 修正 J 的估计 ） 取 1+nJ 使之满足,
),(log),(log
^
)(
^
)(
1
nn
n XfMaxXf JJ J=+,
其中 E - 步骤为取条件期望 ( Expectation ),而 M - 步骤为取最大 （ Maximum ）,这种交替迭代的方法,称为 简单 的 EM 方法,
这个算法的 构思 很简单,但计 算量过大,且一般 很 难看出是否 稳定,为了克服这个缺点,Dempster,Laird 和 Rubin 提出了直接递推估计 J 的想法 ( 仍旧称为 EM 方法 ),这种经过本质改进后的方法,至少在直观上看起来有 稳定 趋势,
1,2 Rubin 算法
假定 ),( YX 具有联合分布密度 ),,( yxf J
Rubin 算法的核心 构思 为,直接使用状态变量 Y 的分布密度 ),( yg J 代替 ),( YX 的分
420
布密度 ),,( yxf J,来求 J 关于 ),( yg J 的最大似然估计
^J
,也就是 求使 ),(log Yg J 达到最大的
^J
,
由于 ),( yg J 在实际上 并 不好求,Dempster – Laird - Rubin 利 用了 下述等 式
),,( yxf J = )|,( yxf J ),( yg J,(15,1)
于是
=),(log Yg j?),,(log YXf j )|,(log YXf j,(15,1) ’
其 右方是状态变量的 对数 似然密度与 对数 条件似然密度 的 差,对 等式 两 边 取 关于 Y 的 条件期望得 到
),(log)( YgL jj?= （ )|),((log YYgE jJ= ）
)]|,(log|),,(log YXfEYYXfE jj JJ ［）］（［?=
)|()|( JjJj HQ?=?,(15,2)
在观测 资料是 y 的时候 ( 即 yY = 的 时候 ),)|( JjQ 的表达式为
)|( JjQ xdyxfyxf YX )|,(),,(log | qj∫=,
而 )|( JjH 的表达式为
=)|( JjH xdyxfyxf YX )|,(),,(log | qj∫
xdyxfyxf YXYX )|,()|,(log || qj∫=,
为了求 )(JL 的极大值点,我们将沿 用第 10 章中对 得到 隐 Markov 模型 的 模型参数估计 的 Baum - Welsh 算法的思想,为此注意
)]|()|([)]|()|([)()( JjJJJJJjJj HHQQLL?+?=?
xdYxf
Yxf
Yxf
QQ YX
YX
YX )|,(]
)|,(
)|,(
[log)]|()|([ |
|
| J
j
J
JJJj ∫+?=
)]|()|([ JJJj QQ?≥,(15,3)
其中用到 第 ２ 项是 相对熵的非负性,由 (15,3) 可知,
只要 0)|()|( ≥? JJJj QQ 就有 0)()( ≥? Jj LL,
421
所以,为了 将 J 的较粗估计 nJ,修改为较精的估计 1+nJ,只需找 1+nJ 使
0)()( 1 ≥?+ nn LL JJ,也 就是 只需要找 1+nJ 使
0)|()|( 1 ≥?+ nnnn QQ JJJJ,(15,4)
于是我们就得到如下的 Dempster – Laird - Rubin 的 EM 算法,简称 Rubin 算法 或 EM 算法,
( 1 ) 设置初值 0J ；
（ 2 ）（ E - 步骤 ） 对于,0≥n 计算 )|( nQ Jj xdyxfyxf YX )|,(),,(log | qj∫= ；
（ 3 ）（ M - 步骤 ）（ 修正 J 的估计 ） 取 1+nJ 使
)|()|( 1 nnn QMaxQ JjJJ j=+,(15,5)
由于 将 nJ 修正为 1+nJ 时,)|( 1 nnQ JJ + 比 )|( nnQ JJ 大,所以 )( nL J 是不减的,这就说明
nJ 有收敛的趋势,Rubin 证明了,在一定的条件下,nJ 确实按概率收敛于某个
^J
,于是我们可以合理地把
^J
作为分布的参数 J 的较佳的估计
注 1 )(JL 是多峰函数的时候,
^J
有可能 是 )(JL 的 局部 最大值,甚至是鞍点,为 了
纠正这种 不足,一般 可以 从多个初始值出发,找到多个
^J
值进行比较,
注 2 所谓,缺失资料,可见之于两种情形,一种是观测资料的丢失,另一种是人为
地设置一些,后台操作的,辅助随机变量,称之为 潜变量,将他们视为缺失的资料,即将他们视为不能直接测量到的状态随机变量,这种潜变量的取法可以非常灵活,依赖于人们对于问题的认识,经验的积累与对于技术掌握的成熟程度,从数 学处理的角度考虑,最好能选取潜变量 X,使它与观测随机变量 Y 的联合分布是指数型分布 ( 参见第 1 章 ),这时 E - 步骤就很容易计算,
注 3 在离散随机变量的情形,E － 步骤中的积分应该相应的改为求和 。
以上算法 也同样将 隐马氏模型中的 Baum - Welsh 算法,纳入 了 EM 算法的框架,
１,３ EM 算法的变通 – 广义 EM 算法
在实际计算中,又因为 E -步骤 的计算量很大,人们 常常 并不真去 计 算条件 期望,而是采用随机模拟,即,用在 ),( YnJ 已知的条件下,用随机模拟得到 X 的 Bayes 分布的若干独立随机数,代入 ),(log Xf j 后作样本平均,用来代替 )|( nQ Jj,这就大大地减少了计算量,实践表明这样的简化,常可以得到相当满意的效果,
同样,也因为 M-步骤 的计算量也很大,人们也 常常并 不去算最大,而是任意找一个
j,只要满足 0)|()|( ≥? nnn QQ JJJj,就取 j 为 1+nJ,这样简化了的算法,称为 广义
422
EM 算法,常称为 GEM 算法,
[注 ] 在应用 EM 方法时,为了避免 M-步骤中求 最大 值 的复杂计算,还 可以采取 其它的 灵活的替代方法,例如 有
ECM 算法 (Conditional Maximum,CM),在 多个 参数 的时候,例如 ),( 21 JJJ = 的情形,如下 的 交替 地求条件极值 的 最大化 的方法,也常被用来 代替 M-步骤,
(1) 先取 )1(2 +nJ 满足
=+ )|',(( )()1(2)(1 nnnQ JJJ )|)',((max )(2)(1'2 nnQ JJJJ ;
(2) 再取 )1(1 +nJ 满足
)),(|),(( )1(2)(1)1(2)1(1 +++ nnnnQ JJJJ )),(|),'((max )1(2)(1)1(21'1 ++= nnnQ JJJJJ,
称之为 ECM 算法 。 一般地,ECM 算法 比 EM 算法 达到稳定的时间长,
另有一种 ECME 算法 (混合算法 ),它就是 交替地使用 ECM 算法 和 EM 算法,
* 2,在 数据不完全时,用增补潜在数据,对参数的 Bayes 分布作估计 – Tanner –Wong 的潜变量法
２,１ 基本想法 － 估计后验分布
在数据资料不全 （ 缺失数据 ）,或观测到的资料 Y 并不是状态变量时,估计状态变量 X 的分布密度
),( xf J 中的未知参数 J,与古典统计不同 处 是只能 用观测到的资料 Y,这时 可以 通过 后验分布密度
)|( Yp J 得到参数 J 的 Bayes 估计,然而,后验分布 )|( Yp J 一般 并不知道,就 需 要 用 观测到的资料 Y
对后验分布 )|( Yp J 进行估计,这就是本段的目的,
Tanner – Wong 的想法是,在某些情形下,由观测数据 Y 可以通过条件分布取样的机制,来构造 某种 ＂ 增补数据 ＂ (记为 Z,称为 潜变量,Latent Variable) 的样本值,于是 Z 的这些样本值取自条件分布密度 ),|( Jyzp,)|( yzp 称为 预测分布,而 在 yY = 已知的条件下,潜变量的 各个样本值彼此 是条件独立的,
潜变量 Z 是观测不到 的,如何选好它,最为重要,最简单的情形是,观测数据 NYYYY,,,21 L=
为 N 个时刻的历史资料,其中 iY 是一个 m 维向量,如果 它的第 １ 个分量是缺失的,而其它 1?m 维就是状态变量,这时候潜变量就可取为那个缺失的一维变量,
然而,一般情形远非如此简单,潜变量的选取是关系到能 否 有效地计算的关键,Tanner-Wong 选取
Z 的原则是,同时满足以下两个条件 （ 注意在上面所提到最简单情形,下面的条件是满足的 ）,
423
（ １ ） 易于模拟 条 件分布 ),|( Jyzp 随机数,
（ ２ ） 容易计算 后验分布密度 ),|( zyp J,
下面的讨论都基于 （ １ ），（ ２ ） 均 能够施行,
2,2 未知参数的 后验分布的 迭代估计
一旦选定潜变量以后,利用广义全概 率 公式,就得到
zdyzpzypyp )|(),|()|( JJ ∫= (15,6)
和
*** )|(),|()|( JJJ dypyzpyzp ∫=,(15,7)
这两个关系式是设计迭代算法的基点,
（ 迭代可能性的理论依据 粗略地为,把 (15,7)代入 (15,6)得到
*** )|(]),|(),|([)|( JJJJJ dypzdyzpzypyp ∫∫=
*** )dy|)p(,K( JJJJ∫=记为,
这 说明 )|( yp J 是 积分核 ),( *JJK 的不变函数,积分核 ),( *JJK 依赖于观测值 y,但是观测值 y 是固定的,所以没有将它计入记号,只要对积分核 ),( *JJK 作适当的假定,就可以使迭代算法收敛到积分核的不变函数 ）,
由于积分核是不知道的,我们 就不可能直接利用 以下的迭代 算法
**
n
*
n )d()g,K(g JJJJJ ∫=+ )(1
近似 其不变函数,Tanner – Wong 提出用 Monte Carlo 迭代方法给出 )|( yp J 的 一个 估计,Tanner – Wong
设计 的 迭 代算法 是,利用按预测分布的多个独立取样,得到潜变量的多个样本值,通过它们由后验分布
),|( )(izyp J 们更新未知参数 J 的 后验密度 )|( yp J 迭代估计,注意 (15,6) 说明 )|( yp J 是
),|( zyp J 关于预测分布密度 )|( yzp 的数学期望 。 因此 如果得到了潜变量的多个样本值
)()1(,,mzz L
,就可以作 )|( yp J 的 如下的 估计
),|(1)|( )(
1
^ im
i
zypmyp JJ ∑
=
=,(15,8)
对 此 还 需要计算 潜变量加入条件的 后验分布 ),|( zyp J,
于是,估计未知参数 J 的后验密度 )|( yp J 就归结为 以 下的迭代程序,
（ 1） 置初值 )|(0 yp J ;
424
假定已经算出了 第 n 次迭代的 )|( ypn J,那么第 1+n 次迭代的 )|(1 ypn J+ 用以下的两个步骤轮番地修改 得到
（ 2） I (Imputation) 步骤 (得到潜变量的条件样本 ),先按 )|( ypn J 对 nJ 作随机取样,再
按 ),|( nyzp J 独立地取样 m 个,
)()1(,,mzz L
(m 充分大 );
（ 3） P (Posterior) 步骤 (用增补后验分布更新后验分布 ),令
),|(1)|( )(
1
1
im
i
n zypmyp JJ ∑
=
+ =,
３ 几种智能算法
3,１ 背景
随着高性能计算机的发展,出现了一系列算法,如神经网络,模拟退火,遗传算法,演化算法,隐 M arkov 模型,自适应算法等,它们大多出自仿真人的思维,不仅具有通用,稳健 (robust),简单及便于并行处理等优点,而且也有望成为将数值计 算与语义表达,形象思维等与高级智能行为相联系的桥梁,事实上,把人的智能与思维仅仅理解为主要是逻辑思维,
是有很大的片面性的,与逻辑思维相反的以因果思维与统计判决为代表的非逻辑推断,应该说在日常推断中是更为本质的,例如,在逻辑推理中,从,A 蕴涵 B” 这个命题能作的推理是,一旦 A 出现,就立知 B 发生,这只是一种简单思维,而人类的智能推断是更为高级的思维,其判断过程却往往是一个由,结果,探求 其,原因,的相反过程,例如,医生诊断疾病时,常常是,由,疾病 A 有症状 B,这一命题,从病人有症状 B,反过来推断病人有多大的可能有疾病 A,这是一种非逻辑的推断,含有不确定性,还有犯错误的风险,然而这正体现了人类的高级智能活动,同样的推理还有,法医尸检死因,侦探寻找作案人,天气预报,考古分析,矿藏探测等等,与之相联系的计算方法都 可 归入智能算法,
一般地,智能算法常具有以下的特点,
(1) 大都引入了人为的随机因素,因而其计算过程实际上是作随机过程的模拟,然而,这种人工噪声的作用不仅不起干扰的作用,而是相反地起正面的作用,使用它完全是为了控制 计算的进行方向,
(2) 大都具有自适应机制,可以在计算过程中不断调整,
(3) 大都是针对通用的目标函数而设计的,并不采用具体问题具体处理的启发式方
法,
(4) 不少算法是对高维及复杂情形设计的,它们在低维或简单的情形有时效果很差,
有时也显得很 笨拙,
３,２ 决定性的人工神经网络
神经网络是一个由彼此具有相互作用的多个神经元联结在一起的一个系统,作为神经网络的整个系统的协同工作产生一个总的效应,这个总的效应是一种功能,它可以是对应于一定的输入时有一定的相应输出,也可以 是一种记忆功能,神经网络的重点是功能研究,在功能研究的基础上,构造具有相互作用的粒子系统,称为人工神经网络,以仿真地起到成为模拟某种功能的功能器,在数学上,人工神经网络也可以用来构造具有某种给定功能的分片线性处理器,人工神经网络的操作一般具有黑箱的特点,神经网络方法的精神在于,
由从例子 ( 即样品 ) 学习中,归纳出规律,
425
因此,它并不需要知道数据来自的对象的机理,这是它的长处,当然,在规律较为明显的情形,它也就会显出不足,总体看来,可以说神经网络方法是有别于经典统计的一种另类统 计方法,
人工神经网络可分为决定性的和随机的两大类,它们又各自包括各种不同类型的神经网络,这种不同的神经网络的构造,是根据要求它完成某种制定的特殊功能而设计的,而 随机因素的引入,是为了使计算更稳定,减少往错误 的 方向进行的可能性,
决定性的人工神经网络,如 前传神经网络与随机过程并没有关系,但是它是人工神经网络的基础,它有广泛的应用,再则,通过它不仅可以了解人工神经网络的原理与功能,并且也可以更好地理解随机的神经网络,所以本书也采纳了决定性的人工神经网络,以下我们先介绍 决定性的前传人工 神经网络,而把更为一般的决定性的递归神经网络放在随机神经网络中一并处理,
3.2.1 决定性的前传人工神经网络
1,前传网络的概念
最常见的人工神经网络是多层前 传网络,这种网络可分为多层,其中 每层有一些单元组成,一般分为 3 种层次,依次为,输入层 ( 由接受输入数据的神经元组成,它们不受其他神经元的相互作用 ),隐层和输出层,作为中间层的隐层,又可分为若干个子层 ( 由 Kolmogorov
的理论结果,它等价于只有一个隐层的某个系统,然而在实际计算中,往往以采用多层更为方便,灵活 ),所谓前传网络,就是信息只能由前向后传,只有前一层的单元对其后一层的单元可能有相互作用,每一个隐层或输出层都由许多感受子 (perceptron) 组成,每一个感受子就是一个受到网络相互作用的神经元,在前传网络中,这种相互作用只允许来自上一层的神经元,
最 典型的是具有 3 层的全连接前传网络,其隐层元,例如,可以取 6 个至 8 个神经元,网络的效果相当于分片线性近似,它 是一种进行自适应学习的非线性处理器,其典型的 模式是如下的受门限限制的线性作用,设输入层为 m 个输入神经元 ),,( 1 mxxx L=,隐层 有 l 个神经 单元 (体现为分量 ) ),,( 1 lhhh L=,而输出层为 n 个单元 ),,( 1 nyyy L=,用权重
)3,2()2,1(,
klik ww 分别表示输入元 i 给隐元 k 的作用 (强度 ),和隐元 k 给输出元 j 的作用,通常取门限函数 g 为在 0 点的单位阶跃函数
<
≥=
)0(0
)0(1)(
x
xxg,(15,9)
或 S 形阈值函数,例如,
,1 1)( axexg?+= 或 ),arctan(2)( axxg p= )0( >a,(15,10)
于是输入层到隐层间的转递为
)( )2,1( ki
i
ikk xwgh q?= ∑,(15,11)
而隐层到输出层的转移为
)'( )3,2( jk
k
kjj hwgy q?= ∑,(15,12)
其中 ',jk qq 是为了方便而预先设置的 门限 常数,称为阈值,,在 g 为在 0 点的单位阶跃函数
426
时,g 取值 1 对应于神经元处于激发状态,取值 0 就表示处于抑制状态,在 g 为 S 形函数时,对应神经单元取连续的状态值,这种假定有利于在一些近似运算中求导数,此外即使在神经元只取抑制和激发两种状态时,也可以 设 置抑制和激发以外的 一些 缓冲状态,
前传神经网络是一种最简单的非线性处理器,即 一种 分片线性处理器,其 输入是输出的分片线性函数,也就是由样品确定参数的分片线性近似器 (把它与用样条函数 (Spline)近似作比较,前传神经网络除了有输出对输入并不可微的缺点外,操作与运行都远为简单 ),
2,前传人工神经网络的建模与应用
神经网络主要用在建模,模式识别,图像处理,基因表达等领域,多层前传网络的使用可以分为两个相位,训练学习相位 与 运转相位 ( 操作相位 ),
学习相位就是通过对样品的加工计算,得到权重常数 )3,2()2,1(,kjik ww 和 门限 ',jk qq 等参数的估计值,使得在这组参数估计值下,该神经网络能相对最好地执行我们冀望它完成的任务,
神经网络的学习方法分为有监督的学习与无监督的学习,多层前传网络大多采用有监督的学习,其中最广为应用的是误差后传法,有监督的学习 是 指我们可以得到一组给定输出的输入样品,在学习时可利用已知的输出 参照 比较,学习的目的 就是找出最佳未知参数,使得当将样品的输入部分输进这组参数下的网络时,能使输出最接近样品相应的输出,其要点就是根据已知的典型输入和输出,来估计连接系数 )3,2()2,1(,klik ww,而 其 实质 是 灵活 地 运用 最小二乘法,
误差后传法的主要步骤是,
( 1 ),设定参数的初始值 ;
(2 ),逐个或按 随机顺序将样品的输入,输进初始参数所对应的网络,得到输出,并将其与该样品应有的已知输出进行比较 ;
(3 ),校正最后一层 ( 设为第 n 层 ) 的网络参数,得到使得输出最接近于应有输出的最后一层参数,并解出使得误差最小的第 1?n 层输出 ;
(4 ),将第 1?n 层当作第 n 层,重复 (3 ),校正第 n - 1 层的参数,并求出 第 2?n 层输 出,使得 第 1?n 层的输出误差最小 ;
(5 ),重复 ( 4 ),向前面各层推进,直到求出所有各层的参数 ;
(6 ),重复步骤 (2 ) 至 (5 ),直到看起来稳定,
这个算法 是在未知状态 ( 各个神经元的状态 ) 的情况下估计参数,这也是缺失数据的一种参数估计,在估计参数的优化过程中,由于目标函数是非线性的,且变量数又十分大,计算往往会陷于局部极值,因此,也 可 考虑应用模拟退火等整体优化方法,
另一个相位是运 转相位,它是在学习相位的 基础上 ( 就是在确定参数以后 ),神经网络中各结点 ( 即神经元 ) 的状态按规定的方式运行 ( 即 进行运算 ),以 执行希望达到的任务,如 预测,
识别,分类等目的,
前传网络在计算机科学,人工智能等领域中有广泛的应用,它是一种比较好的另类回归模型,
3,2,2 一般的 决定性的人工神经网络模型 ( 神经元未必只取 1 或 0)
在一般的情形,神经网络对神经元 x 的总 相互作用 可以 表示 为
))()(),(()( ∑?= y xyyxwgxh qh,(15,13)
其中 ),( yxw 是神经元 y 对神经元 x 的相互作用势,)( yh 是神经元 y 所处的状态,而
427
)( xq 则是神经元 x 的激发门限值,在神经元只取 ０ 或 １ （ 抑制 或 激发 ） 两种状态时,乘积
)(),( yhyxw 是神经 元 y 对神经元 x 的作用力,g 为门限函数,它是对自变量的总相互作用超过门限的部分起的作用,其中的和号取遍一切对于神经元 x 有相互作用的神经元 y 的全体,
３,３ 随机的人工神经网络
3,3,1 一般概念
在随机的神经网络中,下一层神经元 x 被 激发 的概率 取 为
∑?
=
x
xh
xh
e
exp
)(
)(
)( b
b
,0>b,(15,14)
显见 在 )(xh 越大处,)( xp 也越大,即该处的神经元 x 被激发的概率越大,随机的神经网络与相互作用粒子的随机系统非常类似,它的运转 是一个 Markov 链,
随机因素的加入,在下面的递归网 络中能 起控制计算进行方向的稳定作用,
3,3,2 递归 ( 或反馈 ) (recurrent) 网络与 Boltzman 机
递归 ( recurrent ) 网络 也称为 反馈网络,它实际上是以全体神经元所处的状态 ( 称为一个组态 ) 为变元的 一个 动力系统,因而也具有反馈的连接,在数学上反馈提供了迭代的功能,
所以,同样作为离散动力系统,递归网络比前传网络具有更大的非线性功能,因而有更强大的应用潜力,递归网络也可以是决定性的,也可以是随机的,随机 情形的网络,是按一个随机的规则发展的,因此,全体神经元所处的 状态的时间发展,就是一个 Markov 链,
１,Hopfield 网络
Hopfield 把网络与吸引子联系起来,由此给出了一种联想记忆的模型,并给出了一种学习方法,通过学习训练确定网络连接参数,以能够使它达到所希望有的功能,Hopfield
网络是一种典型的递归网络,它源自人脑机制的研究,Hopfield 提出这种网络是希望用数学模型仿真人脑的功能,这种网络具有反馈的连接,相当于一个离散的动力系统,它不像前传网络那样简单地对输入与输出的关系感兴趣,决定性的 Hopfield 网络,一般 地 没 有输入与输出,在给定初值后,就可以通过网络的运转不断地自动更新,最后落到网络系统的某些不变集上,在这意义下可以说并没有真正的输出,但是可以通过某些手段观测到它的自动更新的进程,
(1) 决定性的 Hopfield 网络
神经网络是一个由 N 个神经元彼此 由 相互作用而联结在一起的一个系统,整个系统在协同工作下产生一个总体效应,Hopfield 网络的总体效应,是提供记忆的数学模型,即联想记忆模型,设每个神经元可以取 1? 与 1+ 两个状态 之一,其中 1? 代表该神经元处于抑制态,1+ 代表该神经元处于激发态 。 把 N 个神经元处的整体所处的状态的全体记为 X,即
)}(,11:),,{( 1 NixxxX iN ≤+?== 或L,
设神经网络对神经元 x 的总相互作用是 (它是 (15,13) 的特殊情形 )
)sgn(
1
ikik
N
k
i xwy q?= ∑
=
,(15,13)’
其中与神经元 i 相连接的神经元 k 有一个连接系数 ikw,并且假定满足 ikw kiw=,
428
学习位相就是要估计这些参数,可以用 EM 算法,
运转相位有异步动力学与同步动力学两种不同的方式,Hopfield 的异步动力学发展是每次只容许依次地改变一个神经元,其具体步骤为,
(A) 先按 (15.13)’ 把 1x 更新为 1y,并用 1y 取代 (15.13)’ 右方的 1x ;
(B) 把 2x 更新为用 (15.13)’计算出的新的 2y,并用此 2y 取代 (15.13)’ 右方的 2x ;
(C) 再把 3x 更新为用 (15.13)’计算出的新的 3y,并用此 3y 取代 (15.13)’ 右方的 3x ;
(D) 如此依次地,一个一个地使网络中的所有 N 个神经元都更新一遍 ;
(E) 重复 (A)至 (D),
Hopfield 同步动力学发展与 Hopfield 异步动力学发展的不同 之 处是,不限于每次只改变一个神经元,同步动力学的时间发展,是通过 (15,13) ’把网络的状态从 ),,( 1 Nxxx L= 转移为 ),,( 1 Nyyy L=,把它改写为通常的离散的动力系统 就是
→=? ),,( )()(1)( nNnn xxx L ),,( )1()1(1)1( ++?+ = nNnn xxx L,
)sgn( )(
1
)1(
i
n
kik
N
k
n
i xwx q?= ∑
=
+,(15,13)’’
同步动力学常常比异步动力学有更多 的 不变集,
递归神经网络更接近于生物神经网络,特别是 Hopfield 网络,它提供了一种联想记忆模式,即把 神经网络动力学发展的一个不动点,或一个不变集 ( 统称为神经网络的吸引子 ),
解释为一个记忆,这种记忆模式具有与传统的 地址 记忆模式 ( 如笔记本,硬盘,光盘等 ) 完全不同的机制,它的记忆恢复 不 需要 利用 存入记忆的目录索引,而是按内容存取,因而 它 是迄今为止最接近于脑记忆功能的网络模式,当然为了增加新的记忆,就必须不断地更新整个神经网络,使得它能容纳新的吸引子,
（ ２ ） 随 机的 Hopfield 网络
l 随机的 Hopfield 异步神经网络
随机的 Hopfield 异步网络,是 按照类似于随机场那样给出 相互作用 的,神经网络的时间发展是随机的,即 按照一个 Markov 链 nx 作随机转移,其中整个网络的状态 ( 组态,记为
),,( 1 Nxxx L= ) 之间的转移概率,例如可以 取 为
≤=
====
+?
+
)(0
)),,,,,,,((1
)|(
111
1,
其它情形
NixxyxxyN
xyPp
Niii
nnyx
LL
xx,
此处 )sgn(
1
ikik
N
k
i xwy q?= ∑
=
,),,1( Ni L=,
注意,异步 Markov 发展的要义 在于,转移矩阵是 Gibbs 型的,即转移时在网络的 N 个
429
神经元中只容许改变一个神经元,
l 随机的 Hopfield 同步神经网络
同步 Markov 发展的要义是,按转移矩阵转移时,在网络的 N 个神经元中可容许同时改变所有的神经元,在 Hopfield 同步神经网络 中 的时间发展 也 是随机的,按照一个 Markov
链 nx 作随机转移,整个网络的状态 ( 组态 ) 之间的转移矩阵中,还 常常 引进了一个倒温度参数 b,转移矩阵 则 可以 由下式给出 ( 假定 0)(
1
≠?∑
=
ikik
N
k
xw J )
iikik
N
k
yxw
N
i
nnyx
e
xyPp
)((1
1,
11
1))(|)(()(
Jb
bxbxb
=
+
∑+
====
=
∏,(15,15)
注意,在 ∞=b 时,x 就 概率为 1 转移为 == iN yyyy ),,,( 1 L )(),(
1
Nixw ikik
N
k
≤?∑
=
J,
这 就成为确定性的网络,这个 Markov 链与 I sing 模型的 Glauber 动力学非常相像,容易检查它有配称分布,且 其 配分函数 为
iikik
N
ki
yxw
y
exZ
)(2
1)(
Jb
b
∑∑
= =∑,
所以,此 Markov 链有可逆不变分布
)(
)()(
xZ
xZx
x
b
b
bp ∑
=,
决定性 Hopfield 同步网络的动力学发展的吸引子,就是 (15.13),的不变集,也就是方程
)sgn(
1
ikik
N
k
i xwx q?= ∑
=
(15,16)
的解 x,可以证明,对于 随机的 Hopfield 网络的 Mark ov 链 nx 发展而言,只要适当地控制倒温度 b,就可以使 Markov 链 nx 以大概率相对地留在方程 (15.16) 的某个指定的解附近,这就使随机 Hopfield 网络能够很好地解释联想记忆的机制 ）,
决定性 Hopfield 网络的联接系数的学习与更新
前面我们已经说过,Hopfield 网络的功能是用描述其网络发展的离散动力系统的吸引子给出 的 联想记忆模式,如何对 H opfield 网络确定个联接系数 }{ ikw 使它能容纳给定的记忆 ( 即吸引子 ) 呢? 这就需要对联接系数进行学习更新,Hopfield 给出了如下的学习律,如果要使 y 成为吸引子,只要把原有的联接系数
}{ ikw 更新为新的联接系数 }'{ ikw,其中
430
='ikw )12)(12(+ kiik yycw,
但是,在此模型下,更新联接系数后的网络并不一定保留原网络的吸引子,除非假定各次加进的吸引子是彼此独立的,所以用 Hopfield 网络来描述记忆远非完善,有很宽广的研究余地,
２,Boltzman 机
在 Hopfield 同步动力学网络中再加进输入神经元与输出神经元,就得到一种更为广泛的神经网络模型,称为 Boltzmann 机,Boltzman 机是一种神经网络,整个网络的时间发展也是一个 Markov 链,一般 设置 了 输入,Boltzmann 机 也 可以看成是前传网络与 Hopfield 网络的结合与推广,它并不对输入层神经元加以,没有 相互作用,的限制,也不限制相互作用只能由前向后,它又 设置 了 输出神经元,同时它还是一个递归式的网络,所以它兼有两种网络的优点,可用以描述和模拟十分复杂的系统,具有很强的功能,
Boltzman 机的学习方法 也 是用 EM 算法,由于 Boltzman 机计算量非常大,学习起来很复杂,用来解决实际问题远不如前传多层网络普及,但 应用 潜力却高于后者,
Boltzmann 机输入神经元的状态由每个时刻的瞬间输入决定,而输出神经元是可观测的,设整个网络有 s 个输入 单元,m 个隐单元,r 个输出单元,若以
)(),(),(),(),(),( rjnOmlnhsknI jlk ≤≤≤
分别表示输入神经元,隐神经元与输出神经元在时刻 n 的取值,在
))(,),(()( 1 nInInI sL?=,))(,),(()( 1 nhnhnh mL?=,))(,),(()( 1 nOnOnO rL?=
已知条件下,)1(),1( ++ nOnh 分别取值 ),,(),,,( 11 rm zzzyyy LL == 的条件概率 取 为,
(P ))(),(),(|)1(,)1( nOnhnIznOynh =+=+
jjmll znOnhnIU
r
j
m
l ynOnhnIU ee ))(),(),((11 ))(),(),(( 1
1
1
1
+?==? ++
= ∏∏
bb
,(15,17)
其中
j
O
ij
r
j
l
h
il
m
l
k
I
ik
s
k
i OwhwIwOhIU
)(
1
)(
1
)(
1
),,( ∑∑∑
===
++=,)( rmi +≤,(15,18)
对于 mi ≤ 及 mi > 分别表示网络对于隐单元与输出单元的作用位势,
可以看出如果 )(nI 是一个 Markov 链,那么 ))(),(),(( nOnhnI 也是一个 Markov 链,
Boltzman 机比同步网络应用更广,也更适合于复杂问题的模式识别,这种网络的缺点是,由样品的实测值来估计 相互 作用系数 ( 联接系数 ) },,{ )()()( OijhilIik www 的学习训练过于复杂,其计算量非常大,然而估计的效果比较好,而且很稳健 (Robust),
特别 地,如果只允许 I 对 h 及 h 对 O有作用,这样的 Boltzman 机 就是 随机的前传网络,
当 β =+∞ 时就退化为前传网络,
[注 ] 神经网络方法的隐单元数,连接与门限都可以调节,这种分片非线性近似具有非常大的灵活性,如果选取得当,运用得好,效果会非常好,有些人认为这种方法过于黑箱化,
会影响效果,其实效果不好往往 由于 选 取 不够灵活,并非方法的问题,再 则,在能量函数中
431
用 S 形函数 (sigmoid),比用两值函数 (signal)有明显的优点,例如在作分类器时,那些明显地属于某类的样本,既 需要让它们起作用,又 不能 让 他们 过分 起作用,因此需要用上下限来限制它们,而中间的 S 部分正是用以区分的重要部分,因为分类器的重要处在于边界处的区分,
当离散样本量不大时,作者的经验是,可以在每个样本附近的一个小球内人工地加入一些均匀随机样本,然后再分组,
３,４ 演化算法,遗传算法
遗传算法 (Stochastic Genetic Algorithm,SGA),或 演化算法 (evolution algorithm),是仿生算法,两者并无本质差别,只是不同的流派采用的不同命名,这 是借鉴自然界的进化过程而设计的,人们注意到自然界在长期的自然选择过程中,往往能够达到惊人的优化水平,就自然地想到模仿这一过程,进行优化处理,各种应用实例表明 这种算法 有较好的稳健性,
遗传算法是一种启发式的 Monte Carlo 繁 衍 算法,它 基于自然选择原理和自然遗传机制,
模拟自然界中的生命进化过程解决有复杂目标的非线性优化问题,包括参数优化,自动程序设计等 问题,这些问题的特点是,解空间是已知的,并 且可以 比较 不同解 的 优劣性,但 是,
由于这些问题的结构一般比较复杂,用一般推理的方法可能很难进行求解,与一般算法 不同,
这种算法 并不从 分析 问题出发,而 是 直接从解出发,先随机 地 的生成多个解,然后仿照自然界生物进化的思想,对这些解 作 遗传,杂交与 变异 运算,并根据优胜劣汰的思想保留更好的,
摈 弃较差的解,得到 子 代,再 不断的重复执行这种操作,直至 得到的 解令人满意为止,这种算法的优点是有智能性,包括具有自组织,自适应,自学习性,它无需事先研究问题的全部结构,再则,它具有并行性,极适合于大规模并行运算,而 其缺点在于计算量大,然而,如果 问题 的 解的适应性函数的性质不好 (例如,对于密钥号码的搜索问题,它只有一个解,其 适应性为 1,其 它 状态 的 适应性 全为 0),这 时 用演化算法 就 不能有效地求解,
遗传算法的基本形式是通过群体更新样本 ( 再抽样 ),作为自然选择,再佐以对样本作小概率的变异,以最终达到整体优化的目的,简单 地说,就是自然选择加以允许有小概率的变异,而 它的 其它变化形式,只是它在具体应用中作不同的修改 而 形成的,
遗传算法是一个群体优化过程,为了得到目标函数的最小 ( 大 ) 值,我们不是从一个初始值出发,而是从 一组初始值出发进行优化,这 一组初始值好比一个生物群体,优化的过程就是这个群体繁衍,竞争和遗传,变异的过程,所以,其主体算法在数学上可描述如下,
假定有一个单变量目标函数 U,我们 并不知道它的解析表达式,但是对于任意给定的 x,
我们通过实验可以测量到 )(xU 的值 ( 也就是知道函数的取值表 ),这时,)(xU 的优化问题
( 求 最大值或求 最小值的位置 ) 可以设计为如下的程序,
取 N 个个体,每个个体取一个初始值,把此 N 个值写成一个列向量 =0x
)(
)1(
Nx
x
M,我们引入此 N 个个体的时间发展机制,即它们以下面的随机迭代映射发展
nnn wf +=+ )(1 xx,
=
Nf
f
f M
1
,
432
其中的干扰随机向量
=
nN
n
n
w
w
w M
1
独立同分布,称为变异,从 nx 到 1+nx 的发展称为第 n 代到第 1+n 代的演化,从演化可以得到一个 Markov 链,而演化的目的是实现目标函数的优化,
希望通过它们的时间发展,最后进入目标函数的优化值 ( 最 小 值 ) 附近,
最简单的演化是按 某种优生原则,在此 N 个个体中选出 M 个进行优化 （ 竞争 ）,即选取 M 个分量,对选中的分量 i,例如 （ 假定
=
)(
)(
)(
1
xf
xf
xf
N
M ）,令
h
xUhxUxf
i
)()()(?+?=
( 在知道 )(xU 的表达式时,则取 )(')( xUxf?=,类似地,在求最 大 值的问题中,相应地用 if? 代替 if ）,而对没有选中的分量 j,则令
0,)( == njj wxxf,
这种迭代方案源自生物遗传的思想,)( xfx → 的转变,称为从父代到子代的遗传,用随机迭代映射的理论,在很宽的条件下,nx 有一个极限分布 )()( xF ∞,这个分布相对地更多地集中于目标函数的优化值附近,但是,这还不能完全达到求 )(xU 最 小 值的要求,求
Umin 的位置有多种方法,其中之一是第 8 章中介绍的模拟退火方法,另 外可以 再加入 父代与子代间的 竞争机制,称为遗传竞争,即令
nn
N
n
n
n wf +=
=
+
+
+ )(
)(
1
)1(
1
1 x
h
h
h M,
=
)(
)1(
N
n
n
n
x
x
x M,
其中
≥<=
+
++
+ ))()((
))()((
)()(
1
)(
)()(
1
)(
1)(
1 k
n
k
n
k
n
k
n
k
n
k
nk
n UU
UU
xhx
xhhx
若若,
上面讨论的是单变量目标函数的优化,在 目标函数是多变量函数 时 完全类似,在 1=M
且 f 满足一定限制条件下,用较多的概率论知识,就 可以证明,在这种竞争机制下,当
∞→n 时,演化算法最终 在 概率收敛意义下,趋向 目标函数取最小值点的某一个,
于是 我们 可以看到,遗传算法常常包含的机制 与步骤为,
(1) 参数选择 （ 设置初始值 ）,通常是对参数进行二进制编码工作,就是将空间中的一个点对应 于 一长串的单变量,对应于生物学中的每个,染色体,,这个二进制染色体的每一个二进制位称 之 为一个,基因,,基因的不同决定了染色体的不同,（ 需要注意的是,参数编码 并不意味着 仅仅 从十进制换成二进制这么简单,不同的参数根据取值范围和精度的不同,
433
变换方式也不同 ）,初始群体模型 (即初始值 )应该是随机产生的,其个体在模型空间中分布越均匀越好,以使模型个体有足够多的遗传物质,以便能较好的找到整体极值,然而,群体数量过大会导致计算量的激增,
(２ ) 竞争 遗传 (即 自然选择 ),竞争 选择是产生新群体 （ 子代 ） 的第一步,应 证优秀的个体的繁殖机会更大,这 就是 优生原则,选择初 群体 （ 父代,即 初始值组 ) 中的若干个个体来产生下一代,例如,可以 把目标函数作为评估函数 （ 这时的优化是 取 最大而不是取最小 ）,根据目标函数值的大小决定个体被选中的概率,并按这个概率选择初始群体中的个体,
以体现优生原则,具体地,竞争机制可以通过 用 Bootstrap 思想再抽样 (Re-sampling)来实现,例如说,对 每个 个体 ( 即函数定义域 (是 有限集 ) 中的 x ) 给予一个标志其优化程度的 评估 函数 (其归一化就是权重,可以看成概率 ),让具有更大的 评估 函数的个体以更大的可能性产生后代,例如,在求有限集上的函数 )0)(( ≥xf 的最大值的位置时,对 x 可取 评估 函数为 )(xf,并 设置一个门限 e,把 e<)(xf 的那些 x 先淘汰出局,而把留下的 x 们,按
1
)(
))(()((?
≥
∑= xfCxCf
xf e
是 归一化常数 )作重要度抽样,独立地取样 N 次 ( N 充分大 ),得到 N 个样本,假定其中样值 ix (一共只有有限个 )出现的次数为 )(,1 NNNN Li =++L,再把较小的 iN 们淘汰出局,得到,遗传,的子代 （ 与一般的优化方法类似,自然选择一般只能保证达到局部优化,而加上杂交和变异,能得到 整体性的 改进 ）,
（ ３ ） 杂交 (Crossover),指从亲本模型重组产生新的子体模型的过程,在遗传算法中,自然 选择和 杂 交是最重要的部分,真正体现了遗传的特点,杂 交就是遗传算法的 一种 繁殖过程,通过 杂 交可 扩大 当前的样本空间,选取亲本进行 杂 交的方式很多,一般可以设置一个交换概率 cP,并 选取一个亲本对,cP 越大说明要 杂 交的亲本对越多,还有一种方法是随机地从模型中选择亲本对进行 杂 交,杂 交的实质是在模型空间进行 更 大范围的搜索,搜索的空间区域可能与原来的采样区域相当的远,所以,这种搜索是属于非 邻 近区域的 （ 非局部的 ）
搜索过程,它可以产生一个很有效的模型空间普查,一种常见的杂交方法是,对于两个非常高维数的离散数据 ( 即被 选中的个体 ),决定性地或随机地取这两个数据的相同长度的一段分量,互相交换接成两个新个体,形成杂交的 子代 ( 对低维数据也可以便同地使用这种想法,
例如,在一维情形可以把两个选中的个体 yx,分别展开为二进小数列,决定性地或随机地取这两个序列中相同长度的一段互换,接成两个新个体 ),一般地,针对不同的实际问题,我们可以根据对所需优化的问题的了解,选取其 杂交 方式,
(4) 变异,变异是偶然 地对 后代中的一个随机选择的基因作随机摄动,这是一个低概率的随机变化过程 (即 设 定 的 变异概率 mP 很小 ),如果不存在变异,子代模型就永远得不到初始群体中没有的染色体基因,因而很难产生强有力的进化,变异的方法就是将某一个参数位的值,从 1 变为 0 或从 0 变为 1,即在优化过程中以小概率不按局部优化的方向进行,从局部看,这种演化似乎反而,劣化,了目标函数,但是,正是这种演化才为逃逸出局部极值的陷阱提供了可能性,由于我们可以控制,劣化,的变异只以很小的 概率发生,在计算 进行 了很多 代 后,总趋势会 向优化发展的,这种做法的基本思想与模拟退火算法是类似的,由于杂交和变异的存在,使遗传算法在模型空间 作搜索中 有很大的潜力,
(5) 更新,就是根据自然界中的,适者生存,的原则,取子代模型中的一个与其亲本比
434
较,摈 弃适值 （ 评估函数 ） 小的亲本或子本,这是 父代和子代之间的竞争,
(6) 算法停止规则,在多次进行 （ ２ ） 至 （ ５ ）（ 注意,这些步骤 并不要求按次序进行 ） 之后,模型群体经过多次的 竞争 选择,杂交,变异 和更新,群体的平均 评估值 （ 目标值 ）
逐渐变大,直至聚集在模 型空间的一个小范围之内,这时,可以用多种判别法来判断算法是否已经达到稳定,例如,可以用群体的平均目标函数值不变,作为算法可以停止的标准,也可以用群体的最大目标函数值与平均目标函数值 是否 接近,作为算法可以停止的标准等等,
总之,遗传算法是一组变量一起演化,所以是群体的优化,它特别适合于并行计算,
另外,群体的规模也可以不是恒定的,
4 聚类,Kohonen 自组织学习,自适应算法
４,１ k－ 平均 (k -mean) 聚类
概括地说,聚类问题就是根据一些样品,寻找较少数目的代表点 (在模式识别中就是 建立一些,标准,模板 的过程 ),这些样品称为学习样品或训练样品,一般 地,样品常具有很高的维数,而高维空间是非常 分 散的,样品的总数一般远远小于高维区域的离散采样 能近似地给出直方图所需的 数目,于是这种统计问题与经典的统计有很大的不同,这时,一个给定的子区域能包含样本点的可能性一般非常小,但是,如果样品数据集能很好地表达它的总体,一般地数据就会集中在一个体积相对地小的一个区域,于是聚类问题的重要点就是去发现这个分布的总体位于那一个相对小的区域,
k－ 平均聚类 就是预先设定为 k 个 类,从 样品 寻找 k 个 类 的代表点,其想法是,先随机地找 k 个点作为代表点的初值,按与这些初值接近的程度,把所有的样品点分成 k 类,然后求每个类的平均值,分别作为初值的修改值,再重复以上的步骤,直至稳定为止,
k－ 平均聚类 的优点是想法简单,设计方便,其缺点是缺少稳健性,对 初始值的取法与初始类的数目的设置都过于敏感,在这一方面,自适应聚类的 效果要明显得多,
４,２ 自适应聚类的基本思路
自适应聚类就是预先并不设定聚类的个数,而是 根据学习样品来得到,标准的,代表点
(或模板 ),这 就是学习或训练问题,其想法是,找到数目尽量小而能覆盖所有数据的一组小球 (这与数据压缩中的矢量量化有点类似 ),使每个球只包含一个模式的数据,这个球的中心就 可以作为 一个代表点 (或模板 ),随之,统计分析就可以只限在每个小球上 进行,而对于给定的样本的识别问题,就是要在代表点中找出这个被判别样本的合适代表,所以,模式识别就归结为决定被判定样本属于那一个球的问题,
自组织神经网络是 对于具有固定规模的学习训练问题 的 改进,这是一种自动确定代表点的 规模 大小 的 自适应聚类,其基本思路是,在聚类过程中,采取竞争学习的机制,这种想 法对于模板的样品集为非常分散的超高维数据的情形比较适用,如果一个样品在现有的模板中实在找不到合适的代表,那么,就用此样品作为一个新的模板,
４,３ 固定规模的 Kohonen 网络
Kohonen 的自组织拓扑映射 (Kohonen ’s Topological Mapping,KTM) 是一种功能非常强的,用作 聚类的 网络,但是其计算量非常大,网络的规模的确定也比较困难,然而,在一定条件下它可以改变为自动确定网络规模的算法,用它作计算机科学中的,矢量量化,( 相当于聚类,即选一些不依赖坐标的 代表点,每个代表点 作为 一个,向量,) 是很好的工具,KTM 的特长在于它要求有 所谓 的,拓扑性,,其 含 意是,用该网络所得到的代表点组能保持 标 号 的 序 之间的 拓扑 关系 不变,也就是,具有较近序标的两个代表点也较近,
KTM 的计算 步骤是,设样品集为 },,{ 1 mss L
435
(1),根据选取好的规模 ( 即代表点总数,记为 N ),随机地或决定性地选取一组初值,)}(,),1({ 00 Nxx L ( 一般每个 )(0 ix 都是一个 与 每个样品相同维数的向量 );
(2),随机地 ( 即独立同分布地,也可以按某一决定性的规则 ) 从样品集 },,{ 1 mss L
中读出一个样本 ny ;
(3),竞争修改待选的代表点,设 j 满足
)),(()),(( nnnn yixdyjxd rrrr ≤,),,2,1( Ni L=?,
则令
))())(,(()()(1 ixyjidaixix nnnnn rrrr+=+ r,
其中 )(rr 是一个严格单调递减的正函数,满足 1)0( =r,na 是一个使算法收敛的因子,称为冷却因子,而 ),( jid 则表示 ji,间的距离 ; （ 即其序标与和读 入 的样本最近的代表点的序标相近的代表点,在修改时 更多 地向读入的样本靠拢 ）,
(4),重复 (2) 和 (3),直至稳定,将稳定的结果记为,)}(,),1({ Nxx L,那么,
)(,),1( Nxx L 就是最后选取到的 N 个代表点,
Kohonen 猜测,在条件
+∞=∑ nn a,+∞<∑ 2nn a
满足时,算法是收敛的,)(rr 严格正能够使最后得到的代表点近似地有拓扑性,即除了较少数的例外代表点以外,对于多数 Nji ≤,,如果 i 与 j 较近则代表点 )(ix 与代表点 )( jx 也较近,
然而,除了一维情形以外,对高维的 K ohonen 网络 所 达到的功能,至今还只有计算机结果的图示,尚缺乏清晰的论述,还谈不上算法收敛性的严格证明,
如果不要求代表点具有拓扑性,那么 就 可以不必要求 )(rr 严格正,而 只需 0)( ≥rr,
即它可 以取 0,这表示在更新待选代表点的时间进程中,有些待选代表点可以在某些时刻不修改,其中最简单的是取
≠
==
)0(0
)0(,1)(
r
rrr,这称为,胜者统吃,的原则,它表示只对与读入样品 ny 最相近的待选代表点 做 修改,这 种 修改表现为往读入的样品 ny 处 拉近一点,此时竞争修改代表点的算法为,设 j 满足
)),(()),(( nnnn yixdyjxd rrrr ≤,),,2,1( Ni L=?,
则令
436
)(),()(1 jiixix nn ≠=+ rr,))(()()(1 jxyajxjx nnnnn rrr?+=+,
若每次只修改一个代表点,则 当代表点数很大时,这种算法要 比标准的 KTM 算法要快得多,例如,当代表点数为 300,则按,胜者统吃,的原则 计算 时,实践表明每次只修改一个代表点的算法比标准的 KTM 算法要快 300 倍,此外,为了具有拓扑性,需要调整代表点的排序,所耗费的时间远超过选取待选代表点的时间,文献中证明了,胜者统吃,算法的组态 ( 全体待选代表点组成的向量 ) 按 分布 收敛到一个分布 ( 当然 一般不具有拓扑性 ),再 则,从应用的角度看,给出 区间估计 往往 比收敛性更为重要,
[ 注 1] 按,胜者统吃,的原则来聚类,可以化为目标函数的最小值问题,设样品集为 },,{ 1 mss L,要得到 N ( Nm >> ) 个代表点,则代表点 Nxx,,1 L 就是目标函数
=),,( 1 NxxU L 2
1
),(min kiNi
m
k
sxd r≤
=
∑
取最小值之处,这个目标函数的含义为,对每一个样品 ks,希望在 N 个待选代表点
Nxx,,1 L 中选取一个与样品 ks 最近的,作为样品 ks 的代表,
[ 注 2] 对于代表点的规模不甚清楚,而有可能 出现 冗余 的待选代表点 的 情形,Jinwen
Zhang 及 Lei Xu 从另一种不同的角度考虑,对 于读入的样品 ny,让与它最近的待选代表点往 ny 拉一点,而让与它第二近的待选代表点往离 ny 远处推一点,而其它待选代表点则保持不变,这种想法是希望最后把冗余的待选代表点推向不起作用的遥远之处,此时,竞争修改代表点的算法可以为,如果 kj,满足
)),(()),(( nnnn yixdyjxd rrrr ≤,),,2,1( Ni L=?,
≤< )),(()),(( nnnn ykxdyjxd rrrr ≠)),(( nn yixd rr )),(( nn yjxd rr,
那么,例如,可以令
),(),()(1 kijiixix nn ≠≠=+ rr,
))(()()(1 jxyajxjx nnnnn rrrr?+=+,
))(())(,()()( 11 kxykxydbkxkx nnnnnnn=?+,
这种想法还相当于使用了类似于如下的目标函数,
=),,( 1 NxxU L ]),( 1min),([min ),(min),(,,2
1 00 kjsxdsxdijNj
kiNi
m
k sxd
sxd
kiiki =≠≤≤=
+∑ r,
实证显示,用这种想法常比,胜者统吃,能达到更为好的效果,这里目标函数的含义为,对每一个样品 ks 的代表点的选取,不只考虑与之最近的代表点的作用,还要顾及与之第二近
437
的代表点的作用,及希望兼顾地修改与样本最近的代表点使之更近,修改与它第二近的代表点使之更远,
4,４,网络规模的竞争学习
Kohonen 映射的缺点在于,
(1) 可能使计算陷入某种局部极小,为此 可以用加入随机干扰以逃逸出这类陷阱,
（ 2） 在 Kohonen 自组织算法中,必须 事先确定代表点 （ 小球 ） 的数目,但是通常给定一组数量较大或维数很高的数据,往往不能知道取多少代表点合适,这样,就自然地提出了怎样由数据自动地确定代表点的个数的问题,这就是规模问题,改进的方法是使代表点的数目依赖于网络的结构,这就是 4,1 段 中 的 自适应 竞争学习的思想,其目标是,对于给定的合适的精度 0>e,寻 找数目小而能覆盖所有数据的一组半径为 e 的小球,把一个小球的中心作为一个代表点 (在模式识别中代表同一类模式 ),在样品的代表球内就可以运用传统的统计,决定数据是否能降维,数据在球内的分布等等,在模式识别中,不同的球的 联系还有助于知道模式的非线性结构的复杂程度,而代表点 的 规模的大小,就相当于提供了用分片线性函数近似所需要的分片数与需要使用的神经网络的规模的信息,
对于自适应竞争学习,Grossburg 等提出了适应共振理论 (Adaptive Resonance Theory,
简称 ART),其含义为,当一个新的样本输入到学习的算法程序中时,只有它和某个待选代表点充分接近,它才能对这个待选代表点进行修正,这样就造成一种自适应的谐振状态,
ART 算法大致是这样,一开始选取代表点数很少或为 0 ; 由接受的 输入样本,按照预先设计好的相似度衡量方法与标志,充分接近,的门限,按照上述竞争原则,决定是否应按这个输入修正某个待选代表点,以及修正哪一个待选代表点,如果没有一个待选代表点和这一新的输入充分接近,则把 此输入 增加为一个新的代表点,
这 个算法有相当好的稳健性,目前文献中给出了两种相似度控制方法,e - 邻域控制法与中心控制法,这是多种模式的模式识别样品选取代表点 ( 并不要求一个模式只选取一个代表点 ) 的自适应方法,用这种算法对手写体数字模式识别的样品选取代表点 ( 矢量量化 ),
取得了很好的 效果,由于这种系列参数适应算法不要求事先给定网络规模和控制参数,从而,
它可以用来作为探索性统计分析的工具,
总之,自组织学习网络的中心思想,是利用演化历史中获得的信息指导搜索或计算,其中还可以人为地引入干扰,以免算法被套入局部陷阱,它一般表达为一个自适应的迭代算法,
其形式为
),,(1 nnnn wyxfx =+,
其中 nx 代表系统在时刻 n 时的状态,ny 代表样品,nw 代表为使搜索过程收敛而人工 加入的干扰,
5 适应最小二乘法 -- 一种适应的变步长的随机逼近
设线性回归问题的随机输入为 nx,观测为 ny,干扰为 nw,待估参数为 J 的模型为
n
T
nn wxy += J,
对此 可以设计如下的递推估计,
)( ^^1^ nTnnnnnn xyx JeJJ?+=+,
438
)( ^1 nTnnnnnn xyx Jgee?+=+,
)(1 11+= nnnn n eeee ∑
=
=
n
k
kn
1
1 e,
其中
∑ ∑ =∞=∞<
k k
nnk nO ),
1(,,gge 0→
ne,
那么,可以证明 n
^J
依概率收敛与某个
^J
,它就 作为 J 的估计,与经典的最小二乘法相比,这个方法优点是,它充分地利用了新的观测,递推地修改估计,并且最后达到概率收敛,
