《非线性分类器及神经网络课件.ppt》由会员分享，可在线阅读，更多相关《非线性分类器及神经网络课件.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性分类器与神经网络Nonlinear Classifiers and Neural Networks1 引言2 异或问题3 两层感知器4 反向传播算法5 径向基函数网络6 支持向量机7 其他非线性分类法1.分段线性分类器2.树状分类器3.二次判别函数一、分段线性距离分类器1.最小距离分类器?在Bayes 决策中，样本为单峰正态分布，各特征为同协方差时，即 Si=s2I，用Bayes 决策规则可得到基于欧氏距离线性判别函数，当 P(w1)=P(w2)时,用均值m作为代表点，两类决策规则为：?决策面是两类均值连线的垂直平分面。?判别函数为x到中心m的距离：|x?mi|gi(x)?ln P(wi
2、)22s22.分段线性分类器图中有两类，样本为同协方差 多峰分布。?若把各类均值向量 mi作为代表点，设计最小距离分类器，得到分界面 I，显然错误率大。?若取多个代表点，如w1取2个，w2取3个，仍用距离判别函数，则得折线分界面 II。未知类别样本可分到最近代表点所属的类中去，这种分段线性的分界面II没有错误。?分段线性分界面由超平面组成，其中每一段都是最小距离分类器。?3.分段线性方法l在wi类取li个代表点，将Ri分成l个子区域，Ri表示l第 i 类的第l 个区域。用均值作为代表点，在Ri区域1lll即取mi?l?xi，其中Ni为Ri区域的样本数。Nixi?Ril定义下列判别函数lgi(x
3、)?min|x?mi|i?1,2,?cl?1,2,?,li判别规则：对于未知的样本x若有gj(x)?min gj(x)j?1,2,?,c则把x归入wj类。用均值作为各子集的代表点，这在等协方差样本分布时，分类效果好。若样本为非等协分布，会出现矛盾。二、树状分类器?将复杂的分类转化为若干个简单的分类问题。?方法：已知样本集和判别属性集，从树根开始到枝、叶，根据不同属性值组成一棵决策树。如图，分叉判别使用特征值，有 6个特征及其阈值，共3类。将样本x=(5,4,6,2,2,3)进行分类，判别二次得到 xw2。?决策树逐步把样本集划分为越来越小的子集,直到每个子集的样本属于同一类，该子集为“纯”子集
4、，则分支停止。?组成树需要解决 一系列问题，如树阈值(2,-,-,1,5,2)的结构，分叉使用的属性，“纯”的标准等。二、二次判别函数?决策面较复杂，是二次曲面，包括超球面、超椭球面、超双曲面等。其判别函数一般式TTg(x)?x Wx?w x?w0?wiix?2?22i?1dd?1j?1 i?j?1?wjixjxi?wjxj?w0j?1d式中：W是d?d实对称矩阵，w为d维向量。因此要得到g(x),需要确定系数个数：1k?d(d?3)?12?有些特殊情况可用此法：一类样本较集中，另一类均匀分布在其周围2T?1g(x)?K?(x?m1)?1(x?m1)g(x)?0?x?w1，否则w2其决策面为超
5、椭球。两类各自都较集中g(x)?x(?)x?2(m?m?)x?(m?m?)?(K1?K)g(x)?0?x?w1，否则w2决策面为双曲面。T1?11222T?11T2?12?12T1?11T2?12例：用二次判别函数对 XOR问题分类定义广义向量 y?x1x2x1x2T三维向量映射到立方体的顶点上，如图(00)(000),(11)(111),(10)(100),(01)(010)这些顶点可由下面平面分类：1y1?y2?2y3?04该平面的决策函数为1g(x)?x1?x2?2x1x24g(x)?0 x?Ag(x)?0 x?B1 引言?上一章讨论了由线性判别函数 g(x)=WTx+w0=ATY描述的
6、线性分类器设计。从训练集样本得到权值W和w0或者A。?若两类间是线性可分的，单层感知器方法可计算出g(x)的权值。例：第k+1次叠代得到的直线方程g(x)?1.42x1?0.51x2?0.5?对于线性不可分的，线性分类器的最优方法是使平方误差最小。例：线性分类器的MSE方法g(x)?3.218x1?0.241x2?1.431?对于非线性分类，选择一个合适的非线性判别函数是很困难的，如图AD,BD,CD。?解决方法：神经网络(即多层感知器)具有很强的处理非线性的能力，适合非线性分类。神经网络中要解决的主要问题：学习方法目的修改权值，如反向传播算法。网络结构层数，每层神经元数及连接方式。用支持向量
7、机(网络)可得到最优分界面。用树分类器进行多级决策。在树分类器上用线性判别函数，就构成了一个 分段线性分类器。对一些特殊的问题可用二次判别函数。2 异或问题（XOR）?异或布尔函数是非线性可分问题的典型例子。将布尔函数理解为分类任务，即根据输入 x1、x2的不同，输出为0(B类)或1(A类)。?图中给出了类在空间的位置。一条直线不能将这两类分开。?“与”(AND)和“或”(OR)布尔函数是线性可分的。?用一个感知器可实现“或门”或“与门”。g由感知器实现的决策面方程异或(XOR)问题必须用两层感知器实现。1ORg(x)?x1?x2?021ANDg(x)?x1?x2?1?022 两层感知器?一条
8、直线不能解决异或问题，可用“或”和“与”二条直线解决，即使用 两层感知器来解决。g1(x)=x1+x21/2=0 g2(x)=x1+x23/2=0 二个神经元分别实现 或和与运算。?二条直线将空间分成 三个区域g1(x)0(A类)g2(x)0 g1(x)0?因此，这个问题可分两阶段处理。1.两层感知器两层感知器的结构与单层感知器相比增加了一个隐层。单层感知器结构?第一层为隐层，可由 p个神经元组成。所有隐层神经元输入节点wiwi为xi的d个特征，i=1,2,d；wi权wi是要通过学习调整的参数；每个神经元的输出yi不相同。两层感知器结构?第二层为输出层，图中为一个神经元，输出运算结果。?若输入
9、节点称为输入层，则也称为三层网络。ddf异或问题用两层感知器 分两阶段解决?第一阶段输入xx1 x2T，输出新向量yy1 y2Ty1y1相对于g1(x)进行“或”运算y2相对于g2(x)进行“与”运算y2由第一隐层两个神经元实现。?第二阶段yy1 y2T为输入，输出为类别。g(y)由一个神经元实现。g(y)=y1-y2-1/20两层感知器模型?第一层隐层(hidden layer)神经元完成第一阶段的计算，是x到y的映射，即隐层神经元作用是将输入 X空间映射到二维(因为二个神经元)Y空间中单位边长的正方形顶点上(00,10,10,11)。?第二层的一个神经元,称为输出层(output laye
10、r)完成第二阶段计算,输出分类用判别函数的值。三个神经元决策线的方程1g1(x)?x1?x2?023g2(x)?x1?x2?021g3(y)?y1?y2?02y22.两层感知器分类能力隐层神经元：?d 维,隐层有p个神经元，其作用是将输入 X空间映射到p维Y空间中单位边长的超立方体顶点yi上，即输入空间到超立方体顶点的映射是通过创建p个(gi=0)超平面实现的。Tpp维空间：y1,?,yp?R,yi?0,1,1?i?p?隐层作用，也可说是产生超平面Hp的交集，即将输入拆分为由超平面交集构成的多面体。每个超平面由隐层中的一个神经元实现，神经元输出为 0或1。d?设d=2，p=3。根据输入x与三个
11、平面g1,2,3(x)=0的相对位置，由平面交集定义的每个区域对应的三维立方体的一个顶点。如 100顶点对应的区域为g1的(+)侧,g2的(-)侧,g3的(-)侧。?即将输入拆分为由超平面交集构成的多面体。每个区域中所有向量映射到立方体(y1 y2y3)的顶点,yi0或1。w1011,001,000；yw2111,010,110,100。2y1y3输出神经元?超平面将超立方体分为两部分，一部分顶点位于一侧，其余为另一侧。上例 d=2,p=3 则该平面将三维几何空间(R3)分为两个区域：一侧(类A)顶点是 000001011；另一侧(类B)顶点是 010100110111。而101不与任一区域对
12、应。平面方程 g(y)=-y1-y2+y3+0.5=0?两层感知器不能解决所有的问题，如下列类域的分离：类A(000111110)；类B(001011010100)。这取决于每个神经元的 gp(x)所构成的平面位置。例：两层感知器结构为 2:3:1(d=2,p=3,j=1)，用分段线性方法将非线性两类分开。?第一隐层三个神经元有相同的输入 x，由于gi(x)的不同，有不同的输出。i=1,2,3。?其分类空间是三维的。gi(x)0 建立的三个超平面H1H2H3将d维特征空间分割成正负两个半空间。图中的三个超平面围成 7个区域，共两类(w1 w2)，每个区域映射到超立方体顶点。w210000001
13、0011111101w1 110?输出层组织输出。3.三层感知器?第一层的隐层神经元构成超平面。即将有类别标记的训练样本集，先用分段线性算法 gi(x)确定一组超平面的参数(权值)，超平面的数目就是神经元数，设为p个。这就构成p维空间。?第二隐层有j个神经元，每个神经元在 p维空间中建立一个超平面。通过选择该层的权值，决定这些超平面的组合和连接方式，构成区域。?第三层输出层的神经元确定类别。?这种结构称为j个前馈神经网络。p个d个?三层网络可以实现任何复杂类型的映射。可以证明，由于在分类空间中超立方体的凸性，对于无论多么复杂的分类问题，一般来说用两个隐层已足够。?图a单层感知器只能一个线性判别
14、；图 b两层感知器中每个隐层神经元都有线性判别能力，就可建立复杂的凸区域；图 c三层感知器的前二层已得到了超体立方，在第三层再次建立超平面划分区域。?多层感知器简称MLP。Multi-Layer-Perceptron3 反向传播算法?神经网络的输出取决于输入和连接的 权值。其工作过程主要分两个阶段：学习期通过不断地学习修改 权值。工作期权值确定后，可计算输出。?单层感知器可通过感知器算法进行学习，调整权值，完成线性分类。它的输入是训练集的样本，输出是期望值，对外是 透明的。?多层感知器中的中间 隐层学习算法，对外是不透明的，隐层权值调整有困难。在 20世纪80年代提出了误差反向传播算法，来计算
15、 隐层的权值。1.神经网络的学习方式：有监督学习?向网络输入训练样本，期望输出已知。比较实际输出与期望输出之误差，该误差或准则函数是权值的某种标量函数，使之达到最小，以使每个输出单元的实际输出逼近期望值。这个过程称为学习过程。?准则函数可用没有错分样本或最小均方差规则，优化算法可采用梯度下降法。?学习方法：如果一节点输出正确，一切不变；如果输出本应为1而为0，则权值增加一增量 W；反之减少W，如同感知器算法。2.反向传播算法(BP法)Back-Propogation用BP算法的网络也称为 BP网络。?算法原理：从后向前逐层传播误差,间接算出隐层误差。采用最小二乘和梯度搜索法，以使实际输出值与期
16、望输出值之间的误差均方值最小。?工作信号：输入信号向后(正向)传播直到输出端，是输入和权的函数。后?误差信号：网络实际输出前与期望输出之差，由输出端向前传播(反向)，逐层算出隐层误差，修改前一层的权值，以使误差最小。BP算法推导?计算某一层的第j个单元，i和k分别为其前层和后层的单元，Oj代表本层输出,netj为输入。?从前到后对每层各单元计算(正向算法)j 的输入netj?wijOiij 的输出Oj?f(netj)?j?Oj为实际输出，yj为期望值y?对输出层而言，12?定义误差E?(yj?yj)2j?E局部梯度?j?netj?E?E?netj?jOi权值对误差影响?wij?netj?wij
17、?权值修正应使误差减少，修正量为?wij?jOiwij(t?1)?wij(t)?wij(t)?j 单元分两种情况(反向计算)j是输出节点Oj?y?j?j?E?y?j)f(netj)?j?(yj?y?j?netj?y12?j)其中E?(yj?y2j1Sigmoid函数y?f(x)?x1?e?xe其导数 f(x)?y(1?y)?x2(1?e)j不是输出节点,Oj对后层的全部节点都有影响?E?E?netk?Oj?j?netjk?netk?Oj?netj?kwjkf(netj)k?在实际使用时，为了加快收敛速度，要加入前一次的修正量?第t 次的实际修正量?wij(t)?jOi?a?wij(t?1)a
18、称为惯性系数，?为学习系数。反向传播算法步骤：?初始化：设可调参数(每个权值和阈值)为均匀分布的较小数，如 0.3 均匀分布随机数。?对每个样本作如下计算，直到收敛：输入一个样本 x=(x1,x2,.,xd)即Oi；输入网络的期望输出yj，若输出为两个单元则 j=1,2。从前向后计算各层(正向)，各神经元输出Ojnetj?wijOii输入Oj?1?netj1?e输出对输出层计算?j?j?(y?Oj)Oj(1?Oj)从后向前计算各隐层j（反向）?j?Oj(1?Oj)?wik?kk计算并保存各权值修正量?wij(t)?a?wij(t?1)?jOi修正权值wij(t?1)?wij?wij(t)?t=
19、t+1，输入新的样本(或新的周期样本)，直到误差达到要求，训练结束。训练时各周期中样本的输入顺序要重新随机排序。?这是对每个样本作权值修正。也可对全部样本计算?j后求和，按总误差修正权值，称为批处理方法。4.BP 算法示例：用BP算法求解异或问题(XOR)神经网络结构MLP2:2:1输入节点2个(x1,x2),隐节点2个(y1,y2)，输出节点1个(z)。计算机运行结果迭代次数：16745 次；总误差：0.05输入输出隐层网络权值和阈值：x1 x2zw11=5.24,w12=5.23,w21=6.68,w22=6.64 0 00q1=8.01,q2=2.980 11输出层网络权值和阈值1 01
20、1 10T1=10,T2=10,f4.79 用计算结果分析神经网络的意义隐层节点代表的直线方程y1:5.24x1?5.23x2?8.01?0 x1?0.998x2?1.529?0y2:6.68x1?6.64x2?2.98?0 x1?0.994x2?0.446?0?直线y1,y2将平面分成三个区域y1上方x1?x2?1.53?0,x1?x2?0.45?0y1,y2间 x1?x2?1.53?0,x1?x2?0.45?0y2下方x1?x2?1.53?0,x1?x2?0.45?0?对4个样本点：点(0,0)落入y2下方,经隐层节点的函数 f(x)(即上式)，得到y1=0，y2=0；点(1,0),(0,
21、1)落入y1,y2之间，经隐层节点的函数 f(x)，得到 y1=0,y2=1；点(1,1)落入y1上方，经隐层节点的函数 f(x)，得到 y1=1,y2=1?结论：隐层节点将平面上四个非线性样本点变成三个线性样本点(0,0),(1,0),(1,1)。输出节点代表的直线方程z:?y1?y2?0.479?0直线将平面(y1,y2)分为两个区。上方：?y1?y2?0.479?0下方：?y1?y2?0.479?0?对样本点样本点(0,1)在z线的上方，经输出节点的函数f(x)(阶跃函数)，得到 z=1；样本点(0,0)(1,1)在z线下方，经输出节点的函数f(x)，得到 z=0。?结论：输出节点将平面
22、上的三个样本变成两类样本。神经网络节点的作用 隐层节点将原非线性 4个样本变成线性3个样本。输出节点将线性样本(3个)变成两类(1或0)。?输出的f(x)函数为阶跃函数。隐层的 f(x)一般为S型函数。超平面(直线)特性隐层节点直线特性y1,y2平行，且平行于过(1,0),(0,1)点的直线L:x1+x21=0y1位于点(1,1)到L的中间位置附近(q1=1.53)。y2位于点(0,0)到L的中间位置附近(q2=0.45)。阈值可在一定范围内变化y-y=01.0q1 2，0q2 1.0其分类效果相同，神经网络的 解不是唯一的。输出节点的直线特性z平行于直线p,并位于点(0,1)到p的中间(f?
23、0.48),阈值可在一定范围变化(0f 1)，分类效果相同。125.BP算法的特点及其改进特点：?BP算法解决了单词感知器无能为力的非线性可分模式的分类问题，广泛用于模式识别和自动控制等应用领域。?BP网络本质上是输入到输出的映射，不需输入输出间精确的数学表达式(模型-无关)，只要用已知的模式样本对BP网络加于训练，网络就具有输入输出对之间的映射能力。?BP算法的关键在于中间隐层的学习规则，而中间隐层相当于对输入信息的特征抽取器。BP算法的不足?从数学上看它是一个非线性优化问题，就存在局部极小问题。?收敛速度慢，一般要迭代几千次或更多，通常只能用于离线的模式识别问题。?BP网络是前馈网络，运行
24、单向传播，没有反馈。输入-输出间的关系不是非线性动力学系统，而只是映射。?隐层数和隐层的神经元个数的选择尚无理论指导，而是凭经验选取。?新加入的样本要影响到已学习完的样本，且样本特征数要相等。改进BP算法：使用动力项，加快收敛速度wij(t?1)?wij(t)?iOj?a(wij(t)?wij(t?1)若误差下降，则取a?1(如动量系数a?1.7)若误差上升，则取 0?a?1(a?0.10.8)修改激活函数f(x)?11?e?(x?q)q阈值学习系数?的自适应调整?(t?1)?(t)E?(t)E(t?1)E样本平均误差(或准则函数J)，t 迭代次数5 支持向量机SVM(非线性情况)?在第四章中
25、，广义线性判别函数是通过构造新的高维特征向量，这样可用线性判别函数解决非线性问题。?同样建立非线性支持向量机可分两步：将非线性样本，从 d维空间转换到k维空间X?R?F?Rdkk?dF?f(x)：xX，f：xF在新的特征空间中使用线性支持向量机。?需将原d维非线性特征向量的空间 X，映射到高维(k)的线性空间F，在此空间求广义分类面。1.非线性空间变换方法：?在线性支持向量机中的最优分类函数?Tf(x)?sgn?iyi(xix)?b?i?1?Ns只有内积参与运算?在变换空间中定义适当的 内积函数K,此内积函数可用原空间中的变量直接计算得到，这样就不会增加计算的复杂度，即内积xiTxj K(xi
26、Txj)内积函数?统计学习理论指出，只要一种运算满足 Mercer条件，就可作为内积函数。核函数就是这样一种内积函数。?Mercer条件：d令x?R 和映射fdkx?R?f(x)?R,k?d 均是欧氏几何空间内积运算表示为?fr(x)fr(x)?K(x,x)r其中fr(x)是x的映射f(x)的r分量2对于任意的f(x)?0且?f(x)?，K(x,x)是对称函数，有?K(x,x)f(x)f(x)dxdx?0?即对于满足上面公式的函数 K(x,x),都存在用K(x,x)定义的内积空间。这样的函数也称为核。例：选择核函数K(xi,xj)?(x xj)。从x?x1x2(d?2)映射y?y1y2y3(k
27、?3)2?y1?x1?23x?R?y?y2?2x1x2?R2?yx2?3?y yj?(x xj)TiTi2dTi2?一般的d维向量内积运算公式：x y?xiyiTi?1在k?3维空间中向量的内积y yj已表示为原特征空间对应向量的核函数K(xi,xj)?(x xj)?(y yj)。Ti2TiTi?核函数也称为势函数。由势能的概念引出。?例如两类模式样本集在 d维特征空间可看成一个点集，具有某种能量的点，在每类的中心(核)xc的能量最大，随距离增大而减小。将附近空间上的点的能量用函数 K(x,xc)来表示，这个函数就是核函数。?两个d维向量x和xk同时满足下列三个条件，可作为核函数：K(x,xk
28、)=K(xk,x)，且当xxk时函数有最大值 x与xk的距离趋于无穷大时，K(x,xk)趋于零 K(x,xk)为光滑函数，且是 x与xk之间距离的减函数。?在支持向量机中常用的核函数：多项式形式K(x,xi)?x?xi?1q?02?x?xi?高斯径向基函数K(x,xi)?exp?2s?双曲正切S形函数 K(x,xi)?tanh(a(x?xi)?c)满足mercer 条件的一种选择a2，c?1Tq2.支持向量机算法用核函数代替最优分类面中的点积，相当于把原特征空间变换到新的特征空间，则?对偶问题求i*，NN1Q(?)?i?i?jyiyjK(xixj)2i,j?1i?1?分类规则?*?f(x)?s
29、gn?yi?iK(xi,x)?b?s?算法的其它条件均不变。支持向量网络输出是中间层节点的线性组合，每一个中间层节点对应于输入样本与一个 支持向量的内积。该网络与RBF网络结构相似。?输出（决策规则）f(x)?sgn(?iyiK(xi,x)?w0)i?1Nsf(x)权值wi?iyi式中K(xi,x)核函数x 输入向量xi支持向量Ns支持向量数目输入向量核函数权值决策3.支持向量机实例?用不同的内积函数导致不同的支持向量机算法。采用多项式形式的内积函数K(x,xi)?x?xi?1Tq得到的支持向量机是一个 q阶多项式分类器。例1：用多项式核函数(q=2)对二维数据用SVM进行非线性分类试验。两图
30、中分别有两类训练样本。虚线为得到的SVM分类线。支持样本加了圈；加了是错分样本。例2：对于不完全可分的非线性模式样本，如同线性SVM可用x、C惩罚项来修正。现用二次型SVM判别，核函数为T2K(x,xi)?x?xi?1使用了两个不同的 C的结果如图。采用高斯核函数型内积2?|x?xi|?K(x,xi)?exp?2?s?得到的支持向量机是一种径向基函数分类器。与传统RBF区别是一个基函数的中心对应一个支持向量，函数及输出权值由算法自己确定。采用S型函数作为内积,如K(x,xi)?tanh(a(x?xi)?c)SVM实现的是一个两个隐层的多层感知器神经网络，网络的权值、网络的隐层节点数目也是由算法
31、自动确定。例3：贝尔实验室用支持向量机对美国邮政手写体数据库进行分类试验。这是一个可识别性较差的数据库，每个样本都是 1616点阵(256维),训练集有7300个样本，测试集为2000个样本。?首先用人工和传统方法得到的分类器测试结果。其中LeNet1是一个专门为此问题设计的五层神经网络。?同样的问题用支持向量机测试，使用的内积函数q多项式径向基?1?K(x,xi)?x?xi?256?Sigmoid?|x?xi|?K(x,xi)?exp?2?256s?b(x?xi)?K(x,xi)?tanh?c?256?2?说明SVM较传统方法有优势，不同方法结果相近。?这是支持向量机的第一次实际应用。目前已
32、有两个标准数字数据库 USPS 和NIST，作为测试多种分类器优劣的标准。?USPS 数据库包括7291个训练样本和2007测试样本，每个样本的输入为手写阿拉伯数字的图像，1616个像素，每个像素灰度为 0到256。即每个样本的输入可用 1616256维的向量表示，其中每个分量为灰度值。?NIST数据库包括60000 个训练样本和10000 个测试样本，每个样本的输入为 2020个像素。同样，每个样本的输入可用 400维的向量表示，每个分量也是0到256的灰度值。例4：文本分类根据文本内容自动归类邮件过滤、网页搜索及办公自动化中应用。?利用支持向量机对12902 个文本进行研究，其中9603
33、个为训练样本，3299 为测试样本。每个文本约包含200个单词，分属118类。?预处理去掉无关单词，留下9947 个词根，按词根顺序组成“字典”，每个文本根据“字典”表示为9947 维向量X?(x)1,?,(x)9947Ttilog2(ri)(x)i?i?1,2,?,9947kti?文本中第i个词根出现的次数；ri?所有文本的个数与包含第i个词根文本数之比；k?调整x使其 x?1的尺寸。核函数为线性核函数K(x,x)?(x?x)作业1.根据你的理解，请说明神经网络是怎么样实现非线性分类的？请注意叙述的调理性。2.在MLP2:2:1上，用BP算法求解异或问题(XOR)。要求：输入层到隐层的权值并分析每个隐层节点的功能；在y1y2空间中画出每一种模式的代表点及判别边界；不用训练样本，在y1y2空间中画出x=0的代表点。3.请验证第81页上的例2：二维特征空间，有16个样本根据熵不纯度生成二叉树，请计算验证每个节点的不纯度（即红色的数据）。(可参考李宏东等译，模式分类一书，机械工业出版，2003)