第4章 非线性分类器及神经网络

第4章非线性分类器与神经网络

NonlinearClassifiersandNeuralNetworks§1引言§2异或问题§3两层感知器§4反向传播算法§5径向基函数网络§6支持向量机§7其他非线性分类法1.分段线性分类器2.树状分类器3.二次判别函数§1引言第3章讨论了由线性判别函数g(x)=WTx+w0=ATY描述的线性分类器设计。从训练集样本得到权值W和w0或者A。若两类间是线性可分的，单层感知器方法可计算出g(x)的权值。例：第k+1次叠代得到的直线方程对于线性不可分的，线性分类器的最优方法是使平方误差最小。

例：线性分类器的MSE方法对于非线性分类，选择一个合适的非线性判别函数是很困难的，如图AD,BD,CD。解决方法：⑴神经网络(即多层感知器)具有很强的处理非线性的能力，适合非线性分类。神经网络中要解决的主要问题：①学习方法－目的修改权值，如反向传播算法。②网络结构－层数，每层神经元数及连接方式。③用支持向量机(网络)可得到最优分界面。⑵用树分类器进行多级决策。在树分类器上用线性判别函数，就构成了一个分段线性分类器。⑶对一些特殊的问题可用二次判别函数。§2异或问题（XOR）异或布尔函数是非线性可分问题的典型例子。将布尔函数理解为分类任务，即根据输入x1、x2的不同，输出为0(B类)或1(A类)。图中给出了类在空间的位置。一条直线不能将这两类分开。

“与”(AND)和“或”(OR)布尔函数是线性可分的。用一个感知器可实现“或门”或“与门”。由感知器实现的决策面方程

异或(XOR)问题必须用两层感知器实现。g∑§2两层感知器一条直线不能解决异或问题，可用“或”和“与”二条直线解决，即使用两层感知器来解决。

g1(x)=x1+x2－1/2=0

g2(x)=x1+x2－3/2=0二个神经元分别实现或和与运算。二条直线将空间分成三个区域g1(x)>0

g2(x)<0

g1(x)<0

g2(x)>0因此，这个问题可分两阶段处理。

(B类)(A类)d两层感知器结构f1.两层感知器⑴两层感知器的结构与单层感知器相比增加了一个隐层。第一层为隐层，可由p个神经元组成。所有隐层神经元输入节点为xi的d个特征，i=1,2,···,d；

权wi是要通过学习调整的参数；每个神经元的输出yi不相同。第二层为输出层，图中为一个神经元，输出运算结果。若输入节点称为输入层，则也称为三层网络。d单层感知器结构wiwiwi⑵异或问题用两层感知器分两阶段解决第一阶段输入x＝[x1x2]T

，输出新向量y＝[y1y2]Ty1相对于g1(x)进行“或”运算

y2相对于g2(x)进行“与”运算由第一隐层两个神经元实现。第二阶段y＝[y1y2]T为输入，输出为类别。g(y)由一个神经元实现。g(y)=y1-y2-1/2＝0y1y2⑶两层感知器模型第一层隐层(hiddenlayer)神经元完成第一阶段的计算，是x到y的映射，即隐层神经元作用是将输入X空间映射到二维(因为二个神经元)Y空间中单位边长的正方形顶点上(00,10,10,11)。第二层的一个神经元,称为输出层(outputlayer)完成第二阶段计算,输出分类用判别函数的值。三个神经元决策线的方程y2d⑴隐层神经元：d维,隐层有p个神经元，其作用是将输入X空间映射到p维Y空间中单位边长的超立方体顶点yi上，即输入空间到超立方体顶点的映射是通过创建p个(gi=0)超平面实现的。隐层作用，也可说是产生超平面Hp的交集，即将输入拆分为由超平面交集构成的多面体。每个超平面由隐层中的一个神经元实现，神经元输出为0或1。2.两层感知器分类能力y1y2y3设d=2，p=3。根据输入x与三个平面g1,2,3(x)=0的相对位置，由平面交集定义的每个区域对应的三维立方体的一个顶点。如100顶点对应的区域为g1的(+)侧,g2的(-)侧,g3的(-)侧。即将输入拆分为由超平面交集构成的多面体。每个区域中所有向量映射到立方体(y1y2

y3)的顶点,yi∈0或1。w1∈[011,001,000]；w2∈[111,010,110,100]。⑵输出神经元超平面将超立方体分为两部分，一部分顶点位于一侧，其余为另一侧。上例d=2,p=3则该平面将三维几何空间(R3)分为两个区域：一侧(类A)顶点是000∪001∪011；另一侧(类B)顶点是010∪100∪110∪111。而101不与任一区域对应。平面方程g(y)=-y1-y2+y3+0.5=0两层感知器不能解决所有的问题，如下列类域的分离：类A－(000∪111∪110)；类B－(001∪011∪010∪100)。这取决于每个神经元的gp(x)所构成的平面位置。⑶例：两层感知器结构为2:3:1(d=2,p=3,j=1)，用分段线性方法将非线性两类分开。第一隐层三个神经元有相同的输入x，由于gi(x)

的不同，有不同的输出。i=1,2,3。其分类空间是三维的。gi(x)＝0建立的三个超平面H1H2H3将d维特征空间分割成正负两个半空间。图中的三个超平面围成7个区域，共两类(w1w2)，每个区域映射到超立方体顶点。

w2∈100∪000∪010∪011∪111∪101

w1∈110输出层组织输出。j个p个d个3.三层感知器第一层的隐层神经元构成超平面。即将有类别标记的训练样本集，先用分段线性算法gi(x)确定一组超平面的参数(权值)，超平面的数目就是神经元数，设为p个。这就构成p维空间。第二隐层有j个神经元，每个神经元在p维空间中建立一个超平面。通过选择该层的权值，决定这些超平面的组合和连接方式，构成区域。第三层输出层的神经元确定类别。这种结构称为前馈神经网络。三层网络可以实现任何复杂类型的映射。可以证明，由于在分类空间中超立方体的凸性，对于无论多么复杂的分类问题，一般来说用两个隐层已足够。图a单层感知器只能一个线性判别；图b两层感知器中每个隐层神经元都有线性判别能力，就可建立复杂的凸区域；图c三层感知器的前二层已得到了超体立方，在第三层再次建立超平面划分区域。多层感知器简称MLP。Multi-Layer-Perceptron§3反向传播算法神经网络的输出取决于输入和连接的权值。其工作过程主要分两个阶段：①学习期－通过不断地学习修改权值。②工作期－权值确定后，可计算输出。单层感知器可通过感知器算法进行学习，调整权值，完成线性分类。它的输入是训练集的样本，输出是期望值，对外是透明的。多层感知器中的中间隐层学习算法，对外是不透明的，隐层权值调整有困难。在20世纪80年代提出了误差反向传播算法，来计算隐层的权值。1.神经网络的学习方式：⑴有监督学习向网络输入训练样本，期望输出已知。比较实际输出与期望输出之误差，该误差或准则函数是权值的某种标量函数，使之达到最小，以使每个输出单元的实际输出逼近期望值。这个过程称为学习过程。准则函数可用没有错分样本或最小均方差规则，优化算法可采用梯度下降法。学习方法：如果一节点输出正确，一切不变；如果输出本应为1而为0，则权值增加一增量ΔW；反之减少ΔW，如同感知器算法。2.反向传播算法(BP法)Back-Propogation用BP算法的网络也称为BP网络。算法原理：从后向前逐层传播误差,间接算出隐层误差。采用最小二乘和梯度搜索法，以使实际输出值与期望输出值之间的误差均方值最小。工作信号：输入信号向后(正向)传播直到输出端，是输入和权的函数。误差信号：网络实际输出与期望输出之差，由输出端向前传播(反向)，逐层算出隐层误差，修改前一层的权值，以使误差最小。后前⑴BP算法推导计算某一层的第j个单元，i和k分别为其前层和后层的单元，Oj代表本层输出,netj为输入。从前到后对每层各单元计算(正向算法)

j的输入

j的输出对输出层而言，为实际输出，yj为期望值

局部梯度定义误差权值对误差影响

权值修正应使误差减少，修正量为

j单元分两种情况(反向计算)

①j是输出节点

②j不是输出节点,Oj对后层的全部节点都有影响在实际使用时，为了加快收敛速度，要加入前一次的修正量第t次的实际修正量a称为惯性系数，h为学习系数。⑵反向传播算法步骤：初始化：设可调参数(每个权值和阈值)为均匀分布的较小数，如±0.3均匀分布随机数。对每个样本作如下计算，直到收敛：①输入一个样本x

=(x1,x2,..,xd)即Oi；输入网络的期望输出yj，若输出为两个单元则j=1,2。②从前向后计算各层(正向)，各神经元输出Oj③对输出层计算dj④从后向前计算各隐层δj

（反向）

⑤计算并保存各权值修正量

⑥修正权值t=t+1，输入新的样本(或新的周期样本)，直到误差达到要求，训练结束。训练时各周期中样本的输入顺序要重新随机排序。这是对每个样本作权值修正。也可对全部样本计算dj后求和，按总误差修正权值，称为批处理方法。⑶学习曲线在训练开始误差很高，随着学习进展，误差越来越小，由此生成学习曲线。误差与训练样本的数量、网络输入、所有神经元的权值和阈值、以及网络的结构有关。测试集：独立选取的样本，误差达到或接近训练集样本，则说明该网络有推广能力。检验集：用非训练样本测试网络的现场运行性能。训练总量用回合数表示，每输入一次全部样本,称为一个回合。将新的样本或老样本随机排序后再输入，进行下一个回合的训练。3.实际应用中的有关问题：⑴有关概念神经网络是一种软件，它是通过软件编程来实现的。它是与“模型-无关”的，是一种基于距离度量的数据分类方法，通过不断的自学习来调整权值，以得到期望的输出。神经网络具有逼近任意非线性函数的能力。根据已有的输入输出数据来训练神经网络的权值，使它能精确地近似给定的非线性系统。神经网络基本上执行线性判别，执行过程是在输入信号的非线性映射空间中进行的，利用分段线性技术实现。⑵样本数据要保证训练好的网络有好的推广性，训练结果应该有效的逼近样本蕴含的内在规律。将总样本随机分为训练样本和非训练样本(测试样本),若测试样本的误差接近训练样本，则可行。输入预处理：应用Sigmoid函数会受到饱和影响，应将所有的输入特征变换到一个合适的范围,如(0,1)。输出处理：若三类设三个名义值。用阈值，可将网络的输出值变换为-1和1。⑶学习参数的选择

h对收敛性影响大，在0.1~3之间试探。通常0.5左右。

a开始在0.9~1之间选择，a>1时不收敛。训练中可不断减小。初始权值在-0.5~0.5之间选择。由于BP算法存在多个局部极小点，必须通过多次改变初始权值，通过训练求得相应的极小点，以比较网络的误差，确定全局极小点，从而得到最优的权值。上述的参数仅供参考，需要在学习过程中不断的尝试，以求达到收敛速度快，误差小。⑷神经网络结构的选择隐层：隐层节点数就是提供的超平面数。多,可降低误差，但也有可能产生“过学习”。隐层节点个数：增加节点数可提高精度。如果样本的维数较大时，第一隐层中神经元作用相当于降低维数，因此其个数应当接近于样本数协方差矩阵拥有的显著本征值个数。网络结构往往凭经验选择，在设计过程中可用几种不同的结构、初始参数分别进行试验。BP算法的优缺点优点：理论基础牢固推导过程严谨物理概念清晰通用性好所以，它是目前用来训练多层前向网络（BP网络）较好的算法。BP算法的优缺点缺点：BP算法的收敛速度一般来说比较慢；BP算法只能收敛于局部最优解，不能保证收敛于全局最优解；当隐层元的数量足够多时，网络对训练样本的识别率很高，但对测试样本的识别率有可能很差，即网络的推广能力有可能较差。BP算法的实用技术输出函数（激活函数）输入信号尺度变换c类问题的目标输出带噪声的训练法人工“制造”数据隐单元数权值初始化学习率冲量项权值衰减BP算法的实用技术输出函数（激活函数）应具备的性质非线性：非线性特征映射，否则三层网络将等同于两层网络的计算能力饱和性：存在最大和最小值，即输出有上下界连续性：在整个自变量范围内都有定义光滑性：在整个自变量范围内一阶导数存在最好有单调性：导数在自变量范围内不变号，避免引入不必要的局部极值Sigmoid函数满足上述性质，因此被广泛采用激活函数f(·)，一般选用Sigmoid函数xBP算法的实用技术输入信号尺度变换鱼分类的例子：x1:质量x2:长度x1=1500克，x2=0.3米，则网络权值的调整主要由x1控制x1=1.5千克，x2=300毫米，则网络权值的调整主要由x2控制解决方案：输入特征尺度变换，使得每个特征在整个训练集上的均值为零每个特征的方差相同，如都为1.0规范化BP算法的实用技术c类问题的目标输出Sigmoid函数的饱和值±1.716永远不可能达到，存在误差c类问题的判决准则：如果样本x属于第i类，则第i个输出单元的目标输出为+1，其他输出单元为-1例如：四类情况，x属于第3类，则目标输出为（-1，-1,+1，-1）BP算法的实用技术带噪声的训练法当训练集很小时，可以构造一个虚拟的或替代的训练模式来使用（建立概率模型），就好像它们是从源分布中抽样出来的正常的训练模式在没有具体特定信息时，一个自然的假设就是此代替模式应该加入一个d维噪声，以获得真实的训练点这种有噪声的训练方法实际上可用于任一分类方法，尽管对于高度局部化的分类器（如最近邻分类器）它通常并不改善准确率BP算法的实用技术人工“制造”数据在训练模式不足的情况下，有时可以人工制造一些训练样本需要利用问题的先验知识，如某种“几何不变性”，制造出一些能传达更多信息的训练样本数据变换：例如字符识别问题中（如：dataaugmentation）旋转缩放字符笔画宽窄变化BP算法的实用技术隐单元数：隐单元个数决定了网络的表达能力，从而决定了判决边界的复杂度简单问题需要较少的隐单元复杂问题需要较多隐单元过少隐单元造成神经网络表示能力下降过多隐单元造成对训练集的“过拟合”经验规则选取隐单元个数，使得网络中总的权值数大致为样本数的1/10BP算法的实用技术权值初始化若则无法更新权值初始化方法：从均匀分布中选取权值规格化后（方差为1.0）的d个变量作为输入，平均净激活为希望的净激活范围：-1<net<+1因此：BP算法的实用技术权值初始化输入层到隐含层的权值初始化隐含层到输出层的权值初始化与输出层连接的隐单元数BP算法的实用技术学习率：不同学习率的收敛效果Sigmoid网络的学习率：初始化学习率约为0.1；如果发散，则调小学习率；如果学习速度过慢，则调大学习率。BP算法的实用技术冲量项（momentum）问题：在的区域，权值无法更新BP算法的实用技术冲量项（momentum）误差曲面的“平坦区”较小，学习速度慢解决方法：如果让当前学习保持上一步学习的“惯性”，则可以较快通过“平坦区”“惯性”的度量：冲量BP算法的实用技术冲量项（momentum）上一步（第m步）的更新量第m+1步的BP算法更新量带冲量的反向传播学习规则退化为BP算法匀速学习通常取：BP算法的实用技术带冲量的随机反向传播算法BP算法的实用技术带冲量的随机反向传播算法BP算法的实用技术权值衰减简化网络以及避免过拟合的方法：可以采用加入一个启发式规则：即权值应当比较小实践中，较小的权值往往可以提高神经网络性能。小权值更加适合线性的模型基本方法：从具有“非常多”的权值网络开始，在训练中衰减所有的权值§4径向基函数网络

(RadialBasisFunction,RBF)1.特点：①属于前馈网络。只有一个隐层，隐层输出特性为径向基函数，输入层到隐层间的权值均为1；②输出节点为线性求和，输出权值可调。径向基函数就是沿径向对称的标量函数。定义为空间任一点x到中心xc之间欧氏距离的单调函数。高斯径向基函数：

xc

核函数中心，

s函数宽度。函数的变量为距离。网络的输出隐层的激活函数为RBF，输出为加权线性和。RBF网络的作用：①把网络看成未知函数f(x)的逼近器。任何函数可表示成一组基函数的加权和，相当于用隐层单元的输出函数构成一组基函数逼近f(x)。②从输入层到隐层的基函数输出是非线性映射,而输出是线性的。即先将原始的非线性可分的特征空间变换到一个新的线性可分的空间,然后用一个线性单元来分类。在RBF网络中有3组可调参数：①xc

(或记为ci)核函数中心、质心；

②si方差，函数宽度、平滑参数；③wi输出节点权值。2.常见的3种选择方法：⑴根据经验选取函数中心xc：如在训练样本中根据经验选定M个中心xc，其中心之间距为d。则高斯核函数的方差可s为

⑵用聚类方法选择：以各聚类中心作为核函数中心，而以各类样本的方差作为各个基函数的宽度参数。权值wi的选择：因为输出单元是线性单元，它的权值wi可用基于均方差最小的最小二乘法计算。⑶将三组可调参数q通过训练样本用误差d纠正算法求得。类似BP算法，分别计算d(k)对各组参数的偏导数，用为了得到较好的推广能力，在训练过程中可对质心样本点进行调整。每个函数都有自己的平滑参数s，在训练中根据自身的情况确定。RBF除了应用欧氏距离外，也可应用马氏距离。欧氏距离需要核函数数目多，马氏距离需要估计更多的方差。通常用欧氏距离。3.RBF网络与MLP的区别：①MLP所有隐层的神经元的输出形式都是相同的,MLP有好的扩展性；②RBF只对与xc中心欧氏距离相等的点输出是相同的，随距离不同按指数减小，因此激活响应是局部的，而MLP是全局的，所以RBF收敛快。③利用RBF网络，对于任何函数f(x)都可找到一组权重系数来逼近这个函数，即有最佳逼近性质。例：用RBF完成XOR的分类选择隐层m=2,c1=[1,1]T,c2=[0,0]T,1/2si

2

=1,

k(x)=exp(-||x-ci||2)映射后对应的y值§5支持向量机SVM(非线性情况)在第3章中，广义线性判别函数是通过构造新的高维特征向量，这样可用线性判别函数解决非线性问题。同样建立非线性支持向量机可分两步：①将非线性样本，从d维空间转换到k维空间

F={f(x)：x∈X}，f：x→F②在新的特征空间中使用线性支持向量机。需将原d维非线性特征向量的空间X，映射到高维(k)的线性空间F，在此空间求广义分类面。1.非线性空间变换方法：在线性支持向量机中的最优分类函数在变换空间中定义适当的内积函数K,此内积函数可用原空间中的变量直接计算得到，这样就不会增加计算的复杂度，即内积xiTxj→

K(xiTxj)内积函数统计学习理论指出，只要一种运算满足Mercer条件，就可作为内积函数。核函数就是这样一种内积函数。Mercer条件：

即对于满足上面公式的函数K(x,x’),都存在用K(x,x’)定义的内积空间。这样的函数也称为核。核函数也称为势函数。由势能的概念引出。例如两类模式样本集在d维特征空间可看成一个点集，具有某种能量的点，在每类的中心(核)xc的能量最大，随距离增大而减小。将附近空间上的点的能量用函数K(x,xc)来表示，这个函数就是核函数。两个d维向量x和xk同时满足下列三个条件，可作为核函数：①K(x,xk)=K(xk,x)，且当x＝xk时函数有最大值②x与xk的距离趋于无穷大时，K(x,xk)趋于零③K(x,xk)为光滑函数，且是x与xk之间距离的减函数。在支持向量机中常用的核函数：

2.支持向量机⑴算法用核函数代替最优分类面中的点积，相当于把原特征空间变换到新的特征空间，则对偶问题求λi*，分类规则算法的其它条件均不变。⑵支持向量网络输出是中间层节点的线性组合，每一个中间层节点对应于输入样本与一个支持向量的内积。该网络与RBF网络结构相似