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

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1 引言,2 异或问题,3 两层感知器,4 反向传播算法,5 径向基函数网络,6 支持向量机,7 其他非线性分类法,1.分段线性分类器,2.树状分类器,3.二次判别函数,1 引言,第3章讨论了由线性判别函数,g,(,x,)=,W,T,x,+,w,0,=,A,T,Y,描述的线性分类器设计。从训练集样本得到权值,W,和,w,0,或者,A,。,若两类间是,线性可分,的，单层感知 器方法可计算出,g,(,x,)的权值。,例：第,k,+1次叠代得到的直线方程,对于,线性不可分,的，线性分类器 的最优方法是使平方误差最小。,例：,线性分类器的MSE方法,对于非线性分类,，选择一个合适的非线性判别函数是很困难的，如图,AD,BD,CD,。,解决方法：,神经网络(即多层感知器)具有很强的,处理非线性的能力，适合非线性分类。,神经网络,中要解决的主要问题：,学习方法目的,修改权值,，如反向传播算法。网络结构层数，每层神经元数及连接方式。,用支持向量机(网络)可得到最优分界面。,用,树分类器,进行,多级决策,。在树分类器上用线性判别函数，就构成了一个,分段线性分类器,。,对一些特殊的问题可用二次判别函数。,2 两层感知器,一条直线不能解决异或问题，可用“或”和“与”二条直线解决，即使用,两层,感知器来解决。,g,1,(,x,)=,x,1,+x,2,1/2,=,0,g,2,(,x,)=,x,1,+x,2,3/2=0,二个神经元分别实现,或,和,与,运算。,二条直线将空间分成,三个区域,g,1,(,x,)0,g,2,(,x,)0,g,1,(,x,)0,因此，这个问题可分两阶段处理。,(,B,类),(,A,类),d,两层感知器结构,f,1.两层感知器,两层感知器的结构,与单层感知器相比增加了一个隐层。,第一层为隐层，可由,p,个神经元组成。,所有隐层神经元输入节点,为,x,i,的,d,个特征，,i,=1,2,d,；,权,w,i,是要通过学习调整的参数；,每个神经元的输出,y,i,不相同。,第二层为输出层，图中为一个神经元，输出,运算结果。,若输入节点称为输入层，则也称为三层网络。,d,单层感知器结构,w,i,w,i,w,i,异或问题用两层感知器,分两阶段解决,第一阶段输入,x,x,1,x,2,T,，输出新向量,y,y,1,y,2,T,y,1,相对于,g,1,(,x,)进行“或”运算,y,2,相对于,g,2,(,x,)进行“与”运算,由第一隐层两个神经元实现。,第二阶段,y,y,1,y,2,T,为输入，输出为类别。,g,(,y,)由一个神经元实现。,g,(,y,)=,y,1,-y,2,-,1/20,y,1,y,2,两层感知器模型,第一层隐层,(hidden layer),神经元完成第一阶段的计算，是,x,到,y,的映射,，即隐层神经元作用是将输入X空间映射到,二维,(因为二个神经元)Y空间中单位边长的正方形顶点上(00,10,10,11)。,第二层的一个神经元,称为输出层(,output layer,)完成第二阶段计算,输出分类用判别函数的值。,三个神经元决策线的方程,y,2,d,隐层神经元：,d,维,隐层有,p,个神经元，其作用是将输入X空间映射到,p,维,Y空间中单位边长的超立方体顶点,y,i,上，即输入空间到超立方体顶点的映射是通过创建,p,个(,g,i,=0)超平面实现的。,隐层作用，也可说是产生超平 面,H,p,的交集，即将输入拆分为 由超平面交集构成的多面体。每个超平面由隐层中的一个神 经元实现，神经元输出为0或1。,2.两层感知器分类能力,y,1,y,2,y,3,设,d,=2，,p,=3。根据输入,x,与三个平面,g,1,2,3,(,x,)=0的相对位置，由平面交集定义的每个区域对应的三维立方体的一个顶点。如100顶点对应的区域为,g,1,的(+)侧,g,2,的(-)侧,g,3,的(-)侧。,即将输入拆分为由超平面交集构成的多面体。每个区域中所有向量映射到立方体(,y,1,y,2,y,3,)的,顶点,y,i,0或1。,w,1,011,001,000；,w,2,111,010,110,100。,输出神经元,超平面将超立方体分为两部分，一部分顶点位于一侧，其余为另一侧。上例,d,=2,p,=3 则,该平面将三维几何空间(,R,3,)分为两个区域：,一侧(类A)顶点是 000001011；,另一侧(类B)顶点是 010100110111。,而101不与任一区域对应。,平面方程,g,(,y,)=-,y,1,-,y,2,+,y,3,+0.5=0,两层感知器不能解决所有的问 题，如下列类域的分离：,类A(000111110)；,类B(001011010100)。,这取决于每个神经元的,g,p,(,x,)所构成的平面位置。,例：两层感知器结构为2:3:1(,d,=2,p,=3,j,=1)，用分段线性方法将非线性两类分开。,第一隐层,三个,神经元有相同的输入,x,，由于,g,i,(,x,),的不同，有不同的输出。,i,=1,2,3。,其,分类空间是三维,的。,g,i,(,x,)0 建立的三个超平面,H,1,H,2,H,3,将,d,维特征空间分割成正负两个半空间。图中的三个超平面围成7个区域，共两类(,w,1,w,2,)，每个区域,映射,到超立方体顶点。,w,2,100000010,011111101,w,1,110,输出层组织输出。,j,个,p,个,d,个,3.三层感知器,第一层的隐层神经元构成超平面。即将有类别标记的训练样本集，先用分段线性算法,g,i,(,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,分别为,其前层和,后层的单元，,O,j,代表本层输出,net,j,为输入。,从前到后对每层各单元计算(正向算法),j,的输入,j,的输出,对输出层而言，为实际输出，,y,j,为期望值,局部梯度,定义误差,权值对误差影响,权值修正应使误差减少，修正量为,j,单元分两种情况(反向计算),j,是输出节点,j,不是输出节点,O,j,对后层的全部节点都有影响,在,实际使用时，为了加快收敛速度,，要加入前一次的修正量,第,t,次的实际,修正量,a,称为惯性系数，,h,为学习系数。,反向传播算法步骤：,初始化：设可调参数(每个权值和阈值)为均匀分布的较小数，如0.3 均匀分布随机数。,对每个样本作如下计算，直到收敛：,输入一个样本,x,=(,x,1,x,2,.,x,d,)即,O,i,；输入网络的期望输出,y,j,，若输出为两个单元则,j,=1,2。,从前向后计算各层(正向)，各神经元输出,O,j,对输出层计算,d,j,从后向前计算各隐层,j,（反向）,计算并保存各权值修正量,修正权值,t,=,t,+1，输入新的样本(或新的周期样本)，直到误差达到要求，训练结束。训练时各周期中样本的输入顺序要重新随机排序。,这是对每个样本作权值修正。也可对全部样本计算,d,j,后求和，按总误差修正权值，称为批处理方法。,学习曲线,在训练开始误差很高，随着学习进展，误差越来越小，由此生成学习曲线。误差与训练样本的数量、网络输入、所有神经元的权值和阈值、以及网络的结构有关。,测试集：独立选取的样本，误差达到或接近训练集样本，则说明该网络有推广能力。,检验集：用非训练样本测试网络的现场运行性能。,训练总量用回合数表示，每输入一次全部样本,称为一个回合。将新的样本或老样本随机排序后再输入，进行下一个回合的训练。,3.实际应用中的有关问题：,有关概念,神经网络是一种软件，它是通过,软件编程,来实现的。它是与“模型-无关”的，是一种基于距离度量的数据分类方法，通过不断的自学习来调整权值，以得到期望的输出。,神经网络,具有逼近任意非线性函数的能力,。根据已有的输入输出数据来训练神经网络的权值，使它能精确地近似给定的非线性系统。,神经网络基本上执行线性判别，执行过程是在输入信号的非线性映射空间中进行的，利用分段线性技术实现。,样本数据,要保证训练好的网络有好的推广性，训练结果应该有效的逼近样本蕴含的内在规律。将总样本随机分为训练样本和非训练样本(测试样本),若测试样本的误差接近训练样本，则可行。,输入预处理：应用Sigmoid函数会受到饱和影响，应将所有的输入特征变换到一个合适的范围,如(0,1)。,输出处理：若三类设三个名义值。用阈值，可将网络的输出值变换为-1和1。,学习参数的选择,h,对收敛性影响大，在0.13之间试探。通常0.5左右。,a,开始在0.91之间选择，,a,1时不收敛。训练中可不断减小。,初始权值在-0.50.5之间选择。,由于,BP算法存在多个局部极小点,，必须通过多次改变初始权值，通过训练求得相应的极小点，以比较网络的误差，确定全局极小点，从而得到最优的权值。,上述的参数仅供参考，需要在学习过程中不断的尝试，以求达到收敛速度快，误差小。,神经网络结构的选择,隐层：隐层节点数就是提供的超平面数。多,可降低误差，但也有可能产生“过学习”。,隐层节点个数：增加节点数可提高精度。如果样本的维数较大时，,第一隐层中神经元作用相当于降低维数，因此其个数应当接近于样本数协方差矩阵拥有的显著本征值个数。,网络结构往往凭经验选择，在设计过程中可用几种不同的结构、初始参数分别进行试验。,BP算法的优缺点,优点：,理论基础牢固,推导过程严谨,物理概念清晰,通用性好,所以，它是目前用来训练,多层前向网络（BP网络）,较好的算法。,BP算法的优缺点,缺点：,BP算法的,收敛速度,一般来说比较慢；,BP算法只能收敛于,局部最优解,，不能保证收敛于全局最优解；,当隐层元的数量足够多时，网络对训练样本的识别率很高，但对测试样本的识别率有可能很差，即网络的,推广能力,有可能较差。,BP算法的实用技术,输出函数（激活函数）,输入信号尺度变换,c类问题的目标输出,带噪声的训练法,人工“制造”数据,隐单元数,权值初始化,学习率,冲量项,权值衰减,BP算法的实用技术,输出函数（激活函数）应具备的性质,非线性：,非线性特征映射，否则三层网络将等同于两层网络的计算能力,饱和性：,存在最大和最小值，即输出有上下界,连续性：,在整个自变量范围内都有定义,光滑性：,在整个自变量范围内一阶导数存在,最好有单调性：,导数在自变量范围内不变号，避免引入不必要的局部极值,Sigmoid函数满足上述性质，因此被广泛采用,激活函数,f,()，一般选用,Sigmoid函数,x,BP算法的实用技术,输入信号尺度变换,鱼分类的例子：,x,1,:质量 x,2,:长度,x,1,=1500克，x,2,=0.3米，则网络权值的调整主要由x,1,控制,x,1,=1.5千克，x,2,=300毫米，则网络权值的调整主要由x,2,控制,解决方案：,输入特征尺度变换，使得,每个特征在整个训练集上的均值为零,每个特征的方差相同，如都为1.0,规范化,BP算法的实用技术,c类问题的目标输出,Sigmoid函数的饱和值1.716永远不可能达到，存在误差,c类问题的判决准则：,如果样本x属于第i类，则第i个输出单元的目标输出为+1，其他输出单元为-1,例如：,四类情况，x属于第3类，则目标输出为,（-1，-1,+1，-1）,BP算法的实用技术,带噪声的训练法,当训练集很小时，可以构造一个虚拟的或替代的训练模式来使用,（建立概率模型）,，就好像它们是从源分布中抽样出来的正常的训练模式,在没有具体特定信息时，一个自然的假设就是此代替模式应该加入一个d维噪声，以获得真实的训练点,这种有噪声的训练方法实际上可用于任一分类方法，尽管对于高度局部化的分类器（如最近邻分类器）它通常并不改善准确率,BP算法的实用技术,人工“制造”数据,在训练模式不足的情况下，有时可以人工制造一些训练 样本,需要利用问题的先验知识，如某种“几何不变性”，制造出一些能传达更多信息的训练样本,数据变换：,例如字符识别问题中（如：data augmentation）,旋转,缩放,字符笔画宽窄变化,BP算法的实用技术,隐单元数：,隐单元个数决定了网络的表达能力，从而决定了判决边界的复杂度,简单问题需要较少的隐单元,复杂问题需要较多隐单元,过少隐单元造成神经网络表示能力下降,过多隐单元造成对训练集的“过拟合”,经验规则,选取隐单元个数，使得网络中总的权值数大致为样本数的1/10,BP算法的实用技术,权值初始化,若 则 无法更新,权值初始化方法：,从均匀分布 中选取权值,规格化后（方差为,1.0,）的,d,个变量作为输入，平均净激活为,希望的净激活范围：,-1net,a,?”就可做出决策。,训练过程如图，二维、四类。将特征空间拆分成矩形,矩 形的边与拆 分轴平行。,图中特征为,x,1,和,x,2,属性值,a,为,1/4,1/2,3/4。,2.设计决策树要点：,选择树的结构，合理安排分支和节点。确定每个节点使用的属性(阈值,a,)，以及所提的问题。,每个节点,t,与训练集,X,的一个特定的子集,X,t,相关,每个节点提的问题是“,x,i,a,或,x,i,a,?”,属性阈值,a,的值定义了子集,X,t,的一种拆分。拆分节点等于拆分两个不相交的子集,X,ty,和,X,tn,。,根节点与训练集,X,相关，,X,X,；枝节点与相应的子集,X,t,相关。,每次,X,t,拆分应满足,分支准则,从根节点到叶节点的生长中，每个分支,t,i,必须产生比父节点,X,t,更加“,类均匀,”的子集,使,X,t,中的样本更均匀地分布在子集中。,例如一个四类问题，将子集,X,t,拆分为,X,ty,和,X,tn,。,w,1,和,w,2,类的点构成子集,X,ty,w,3,和,w,4,类的点构成子集,X,tn,新子集,X,ty,和,X,tn,比,X,t,更均匀、“更纯”。,为此定义一种,度量标准,，用于量化节点不纯度(Impurity)，使子节点比父节点不纯度少。,在信息论中用熵作为信息不确定性的一种度量,它一般是概率的函数。,P,(,w,i,|,t,)表示节点,t,处样本属于第,i,类的概率，,i,=1,c,。,节点不纯度定义为,熵不纯度,I,(,t,),来自香农信息论，度量节点,t,处的“无序性”。,若所有样本概率都等于1,/c,则,I,(,t,)最大(最高不纯度)；若所有都属于一类，则,I,(,t,)0，即只有一类满足,P,(,w,i,|t,)1，其余为0(最小不纯度)。,现执行一个分支,N,ty,个样本分到“是”节点(,X,ty,)；,N,tn,个分到“否”节点(,X,tn,)，则节点不纯度减少定义为,分枝准则为在,属性集,中选择一个,问题,，使分支后的,不纯度最大限度地小,。,不纯度计算举例,如图：二维，两类，左右两种情况。,停止分支准则,一种方法：采用阈值,T,，若,D,I(t,),的最大值(所有可能的分支)小于,T,，停止。,另一种方法：如果子集,X,t,的基数足够小，或,X,t,纯的，停止分支。,分类规则,一旦某个节点声明为叶子，就必须为其分配一个类的标记。,常用多数规则，将叶子标记为,w,j,即叶子,t,指定给,X,t,中大多数样本所属的类。,树分类器算法步骤,从根节点,t,0开始，,X,t,X,对于每个新节点,t,1，2，3，,样本特征向量,x,k,k=,1,2,d,，若以此作为属性，,则对于每个属性的阈值,a,kn,根据问题,x,k,(,i,),a,kn,答案，,i=,1,2,N,t,产生,X,ty,和,X,tn,，,即将样本分开。,计算不纯度的减少量。选择,x,k,0,和相关的,a,kn,0,，使不纯度的减少最大。,如果满足停止分支规则，就节点,t,指定类标记。,如果不满足，根据问题的回答，产生两个子节点,t,y,和,t,n,，相关的子集是,X,ty,和,X,tn,。,如何计算分支后节点不纯度减少量？,例1：样本集中有,N,t,10个样本。,w,1,和,w,2,各,有4个,w,3,有 2个。分支为两个新子集,X,ty,和,X,tn,：,X,ty,中,w,1,有3个、,w,2,有1个；,X,tn,中,w,1,有1个、,w,2,有3个、,w,3,有2个。计算不纯度减少量,因此，分支后不纯度减少量是,例2：二维特征空间，有,N,=16个样本，根据熵不纯度生成二叉树分类。,非叶节点的不纯度 已标出,叶节点的 不纯度为0。,根节点不纯度,阈值,a,选,为平行于 特征轴的特征值。,顺序回答“,x,i,a,?,”就可做出决策。,决策树与神经网络,相似之处：,目标都是在特征空间中形成复杂的决策界限。,区别：,决策方式不同。,决策树以顺序方式应用分层结构定决策函数；,神经网络以并行方式利用一组软决策。,训练原理不同。,分类误差多层感知器优。,训练时间决策树优。,三、二次判别函数,决策面较复杂，是二次曲面，包括超球面、超椭球面、超双曲面等。其判别函数,有些特殊情况可用此法：,一类样本较集中，另一类均匀分布在其周围,其决策面为超椭球。,两类各自都较集中,决策面为双曲面。,例：用二次判别函数对XOR问题分类,三维向量映射到立方体的顶点上，如图(00)(000),(11)(111),(10)(100),(01)(010),这些顶点可由下面平面分类：,该平面的决策函数为,