非线性分类器及神经网络

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的距离：)(ln2|)(22i

2、iiPxxgwsm2. 分段线性分类器 图中有两类，样本为同协方差多峰分布。 若把各类均值向量mi作为代表点，设计最小距离分类器，得到分界面 I，显然错误率大。 若取多个代表点，如w1取2个，w2取3个，仍用距离判别函数，则得折线分界面 II。 未知类别样本可分到最近代表 点所属的类中去，这种分段线 性的分界面II没有错误。 分段线性分界面由超平面 组成，其中每一段都是最 小距离分类器。 盾。非等协分布，会出现矛分类效果好。若样本为时，本分布表点，这在等协方差样用均值作为各子集的代类。归入则把若有样本判别规则：对于未知的定义下列判别函数区域的样本数。为其中，即取区域表点，在个区域。用均值作为代

3、类的第第表示个子区域，分成个代表点，将类取在分段线性方法jjcjjlillililiRxililililiiiixxgxgxcimxxgRNxNmRliRlRliliiww)(min)(, 2 , 1|min)(1. 3, 2, 1, 2, 1二、 树状分类器 将复杂的分类转化为若干个简单的分类问题。 方法：已知样本集和判别属性集，从树根开始到枝、叶，根据不同属性值组成一棵决策树。如图，分叉判别使用特征值，有6个特征及其阈值，共3类。将样本x=(5,4,6,2,2,3)进行分类，判别二次得到 xw2。 决策树逐步把样本集划分为越来越小的 子集, 直到每个子集的样本属于同一类， 该子集为“纯”子

4、集，则分支停止。 组成树需要解决 一系列问题，如树 的结构，分叉使用的属性，“纯”的 标准等。阈值(2,-,-,1,5,2)二、二次判别函数 决策面较复杂，是二次曲面，包括超球面、超椭球面、超双曲面等。其判别函数 djjjdjjiijjidiiiTTwxwxxwxwwxwxWxxg1011112202)(一般式1)3(21),(ddkxgdwddW需要确定系数个数：因此要得到维向量。为实对称矩阵，是式中： 有些特殊情况可用此法：一类样本较集中，另一类均匀分布在其周围 其决策面为超椭球。两类各自都较集中 决策面为双曲面。21111120)()()()(ww，否则xxgmxmxKxgT212221

5、12211112211112110)()()()(2)()(ww，否则xxgKKmmxmmxxxgTTTTT例：用二次判别函数对XOR问题分类 三维向量映射到立方体的顶点上，如图(00)(000), (11)(111), (10)(100), (01)(010) 这些顶点可由下面平面分类： 该平面的决策函数为Txxxxy2121定义广义向量BxxgAxxgxxxxxg0)(0)(241)(21210412321yyy 1 引言 上一章讨论了由线性判别函数g(x)=WTx+w0=ATY描述的线性分类器设计。从训练集样本得到权值W和w0或者A。 若两类间是线性可分的，单层感知 器方法可计算出g(x

6、)的权值。 例：第k+1次叠代得到的直线方程 对于线性不可分的，线性分类器 的最优方法是使平方误差最小。 例：线性分类器的MSE方法5 . 051. 042. 1)(21xxxg431. 1241. 0218. 3)(21xxxg 对于非线性分类，选择一个合适的非线性判别函数是很困难的，如图AD, BD, CD。 解决方法：神经网络 (即多层感知器)具有很强的 处理非线性的能力，适合非线性分类。 神经网络中要解决的主要问题： 学习方法目的修改权值，如反向传播算法。 网络结构层数，每层神经元数及连接方式。 用支持向量机(网络)可得到最优分界面。 用树分类器进行多级决策。在树分类器上用线性判别函数

7、，就构成了一个分段线性分类器。 对一些特殊的问题可用二次判别函数。2 异或问题（XOR） 异或布尔函数是非线性可分问题的典型例子。将布尔函数理解为分类任务，即根据输入 x1、x2的不同，输出为0(B类)或1(A类)。 图中给出了类在空间的位置。 一条直线不能将这两类分开。 “与” (AND)和“或” (OR)布尔函数是线性可分的。 用一个感知器可实现“或门”或“与门”。 由感知器实现的决策面方程 异或(XOR)问题必须用两层感知器实现。0211)(AND021)(OR2121xxxgxxxgg 2 两层感知器 一条直线不能解决异或问题，可用“或”和“与” 二条直线解决，即使用两层感知器来解决。

8、 g1(x)= x1+x21/2=0 g2(x)= x1+x23/2= 0 二个神经元分别实现或和与运算。 二条直线将空间分成三个区域 g1(x) 0 g2(x) 0 g1(x) 0 因此，这个问题可分两阶段处理。 (B类)(A类)d两层感知器结构f1. 两层感知器两层感知器的结构 与单层感知器相比增加了一个隐层。 第一层为隐层，可由p个神经元组成。 所有隐层神经元输入节点 为xi的d个特征，i=1,2,d； 权wi是要通过学习调整的参数； 每个神经元的输出yi不相同。 第二层为输出层，图中为一个神经元，输出 运算结果。 若输入节点称为输入层，则也称为三层网络。d单层感知器结构wiwiwi异或

9、问题用两层感知器分两阶段解决 第一阶段输入x x1 x2T ，输出新向量yy1 y2T y1相对于g1(x) 进行“或”运算 y2相对于g2(x) 进行“与”运算 由第一隐层两个神经元实现。 第二阶段yy1 y2T为输入，输出为类别。 g(y)由一个神经元实现。 g(y)= y1-y2-1/20y1y2两层感知器模型 第一层隐层(hidden layer)神经元完成第一阶段的计算，是x到y的映射，即隐层神经元作用是将输入X空间映射到二维(因为二个神经元)Y空间中单位边长的正方形顶点上(00, 10, 10, 11) 。 第二层的一个神经元, 称为输出层(output layer)完成第二阶段计

10、算, 输出分类用判别函数的值。三个神经元决策线的方程021)(023)(021)(213212211yyygxxxgxxxgy2d隐层神经元： d 维, 隐层有p个神经元，其作用是将输入X空间映射到p维Y空间中单位边长的超立方体顶点 yi上，即输入空间到超立方体顶点的映射是通过创建p个(gi=0)超平面实现的。 隐层作用，也可说是产生超平 面Hp的交集，即将输入拆分为 由超平面交集构成的多面体。 每个超平面由隐层中的一个神 经元实现，神经元输出为0或1。1,1 , 0,1piyRyypipTp维空间：2. 两层感知器分类能力y1y2y3 设d=2， p=3。根据输入x与三个平面g1,2,3(x

11、)=0的相对位置，由平面交集定义的每个区域对应的三维立方体的一个顶点。如100顶点对应的区域为g1的(+)侧, g2的(-)侧, g3的(-)侧。 即将输入拆分为由超平面交集构成的多面体。每个区域中所有向量映射到立方体(y1 y2 y3)的顶点, yi0或1。 w1011,001, 000； w2111,010,110,100。输出神经元 超平面将超立方体分为两部分，一部分顶点位于一侧，其余为另一侧。上例 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) ，每个区域映射到超立方体顶点。 w2

13、 100000010 011111101 w1 110 输出层组织输出。j个p个d个3. 三层感知器 第一层的隐层神经元构成超平面。即将有类别标记的训练样本集，先用分段线性算法gi (x)确定一组超平面的参数(权值)，超平面的数目就是神经元数，设为p个。这就构成p维空间。 第二隐层有j个神经元，每个神经元在p维空间中建立一个超平面。通过选择该层的权值，决定这些超平面的组合和连接方式，构成区域。 第三层输出层的 神经元确定类别。 这种结构称为 前馈神经网络。 三层网络可以实现任何复杂类型的映射。可以证明，由于在分类空间中超立方体的凸性，对于无论多么复杂的分类问题，一般来说用两个隐层已足够。 图a

14、单层感知器只能一个线性判别；图b两层感知器中每个隐层神经元都有线性判别能力，就可建立复杂的凸区域；图c三层感知器的前二层已得到了超体立方，在第三层再次建立超平面划分区域。 多层感知器简称 MLP。 Multi-Layer-Perceptron 3 反向传播算法 神经网络的输出取决于输入和连接的权值。 其工作过程主要分两个阶段： 学习期通过不断地学习修改权值。 工作期权值确定后，可计算输出。 单层感知器可通过感知器算法进行学习，调整权值，完成线性分类。它的输入是训练集的样本，输出是期望值，对外是透明的。 多层感知器中的中间隐层学习算法，对外是不透明的，隐层权值调整有困难。在20世纪80年代提出了

15、误差反向传播算法，来计算隐层的权值。1. 神经网络的学习方式：有监督学习 向网络输入训练样本，期望输出已知。比较实际输出与期望输出之误差，该误差或准则函数是权值的某种标量函数，使之达到最小，以使每个输出单元的实际输出逼近期望值。这个过程称为学习过程。 准则函数可用没有错分样本或最小均方差规则，优化算法可采用梯度下降法。 学习方法：如果一节点输出正确，一切不变；如果输出本应为1而为0，则权值增加一增量W；反之减少W，如同感知器算法。 2. 反向传播算法(BP法) Back-Propogation 用BP算法的网络也称为BP网络。 算法原理：从后向前逐层传播误差, 间接算出隐层误差。采用最小二乘和

16、梯度搜索法，以使实际输出值与期望输出值之间的误差均方值最小。 工作信号：输入信号向后(正向)传播直到输出端，是输入和权的函数。 误差信号：网络实际输出 与期望输出之差，由输出 端向前传播(反向) ，逐层 算出隐层误差，修改前一 层的权值，以使误差最小。后前 BP算法推导 计算某一层的第j个单元，i和k分别为其前层和后层的单元，Oj代表本层输出, netj为输入。 从前到后对每层各单元计算(正向算法) j 的输入 j 的输出 对输出层而言， 为实际输出，yj为期望值 局部梯度 iiijjOwnet)(jjnetfOjjOy jjnetEijijjjijOwnetnetEwEjjjyyE2)(21

17、定义误差权值对误差影响 权值修正应使误差减少，修正量为 j 单元分两种情况(反向计算) j是输出节点 jjjyyE2)(21其中)()(jjjjjjjnetfyynetyyEjjyOijijOw)()()1(twtwtwijijij)1 ()1 ()(11)(Sigmoid2yyeexfexfyxxx其导数函数 j不是输出节点, Oj对后层的全部节点都有影响 在实际使用时，为了加快收敛速度，要加入前一次的修正量 第t 次的实际修正量 a a 称为惯性系数，为学习系数。)(jkjkkjjjkkkjjnetfwnetOOnetnetEnetE) 1()(twOtwijijija反向传播算法步骤：

18、初始化：设可调参数(每个权值和阈值)为均匀分布的较小数，如0.3 均匀分布随机数。 对每个样本作如下计算，直到收敛： 输入一个样本 x =(x1,x2,.,xd) 即Oi ；输入网络的期望输出yj，若输出为两个单元则 j =1, 2。 从前向后计算各层(正向)，各神经元输出Oj 对输出层计算j输出jnetjeO11)1 ()(jjjjOOOy输入iiijjOwnet 从后向前计算各隐层j （反向） 计算并保存各权值修正量 修正权值 t =t+1，输入新的样本(或新的周期样本)，直到误差达到要求，训练结束。训练时各周期中样本的输入顺序要重新随机排序。 这是对每个样本作权值修正。也可对全部样本计算

19、j后求和，按总误差修正权值，称为批处理方法。ijijijOtwtw a a) 1()()() 1(twwtwijijijkkikjjjwOO)1 (4. BP算法示例： 用BP算法求解异或问题(XOR)神经网络结构MLP2:2:1 输入节点2个(x1,x2), 隐节点2个(y1 , y2)， 输出节点1个(z) 。计算机运行结果 迭代次数：16745次；总误差：0.05 隐层网络权值和阈值： w11=5.24, w12=5.23, w21=6.68, w22=6.64 q1=8.01, q2=2.98 输出层网络权值和阈值 T1 =10, T2 =10, f4.79 输入x1 x2输出 z 0

20、 0 0 0 1 1 1 0 1 1 1 0用计算结果分析神经网络的意义隐层节点代表的直线方程 直线y1 , y2将平面分成三个区域 对4个样本点： 点(0,0)落入y2 下方, 经隐层节点的函数 f (x)(即上式)，得到y1 =0， y2 =0 ；0446. 0994. 0098. 264. 668. 6:0529. 1998. 0001. 823. 524. 5:2121221211xxxxyxxxxy045. 0, 053. 1045. 0, 053. 1,045. 0, 053. 12121221212121211xxxxyxxxxyyxxxxy下方间上方 点(1,0),(0,1)落

21、入y1 , y2之间，经隐层节点的函数 f(x)，得到 y1 =0, y2 =1； 点(1,1)落入y1 上方，经隐层节点的函数 f(x)，得到 y1 =1, y2 =1 结论：隐层节点将平面上四个非线性样本点变成三个线性样本点(0,0),(1,0), (1,1)。输出节点代表的直线方程 直线将平面(y1 , y2)分为两个区。0479. 0:21yyz0479. 00479. 02121yyyy下方：上方： 对样本点 样本点(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=0 y1位于点(1,1)到L的中间位置附近(q1 =1.53)。 y2位于点(0,0)到L的中间位置附近(q2 =0.45)。 阈值可在一定范围内变化 1.0q1 2，0q2 1.0 其分类效果相同，神经网络的解不是唯一的。 输出节点的直线特性 z平行于直线p,

23、 并位于点(0,1)到p的中间(f0.48),阈值可在一定范围变化(0f 1)，分类效果相同。 y1-y2=05. BP算法的特点及其改进特点： BP算法解决了单词感知器无能为力的非线性可分模式的分类问题，广泛用于模式识别和自动控制等应用领域。 BP网络本质上是输入到输出的映射，不需输入输出间精确的数学表达式(模型-无关)，只要用已知的模式样本对BP网络加于训练，网络就具有输入输出对之间的映射能力。 BP算法的关键在于中间隐层的学习规则，而中间隐层相当于对输入信息的特征抽取器。BP算法的不足 从数学上看它是一个非线性优化问题，就存在局部极小问题。 收敛速度慢，一般要迭代几千次或更多，通常只能用

24、于离线的模式识别问题。 BP网络是前馈网络，运行单向传播，没有反馈。输入-输出间的关系不是非线性动力学系统，而只是映射。 隐层数和隐层的神经元个数的选择尚无理论指导，而是凭经验选取。 新加入的样本要影响到已学习完的样本，且样本特征数要相等。改进BP算法： 使用动力项，加快收敛速度 修改激活函数 E样本平均误差(或准则函数J)，t 迭代次数)8 . 01 . 0(10)7 . 1(1)1()()() 1(aaaaa若误差上升，则取如动量系数若误差下降，则取twtwOtwtwijijjiijij)()1()()1(ttttEE阈值qq)(11)(xexf学习系数 的自适应调整5 支持向量机SVM(

25、非线性情况) 在第四章中，广义线性判别函数是通过构造新的高维特征向量，这样可用线性判别函数解决非线性问题。 同样建立非线性支持向量机可分两步： 将非线性样本，从d维空间转换到k维空间 Ff(x)：xX， f：xF 在新的特征空间中使用线性 支持向量机。 需将原d维非线性特征向量的空间X，映射到高维(k)的线性空间F，在此空间求广义分类面。dkRFRXkd1. 非线性空间变换方法： 在线性支持向量机中的最优分类函数 在变换空间中定义适当的内积函数K, 此内积函数可用原空间中的变量直接计算得到，这样就不会增加计算的复杂度，即 内积 xiTxj K(xiTxj) 内积函数 统计学习理论指出，只要一种

26、运算满足Mercer条件，就可作为内积函数。核函数就是这样一种内积函数。只有内积参与运算bxxyxfTiNiiis)(sgn)(1 Mercer条件： 即对于满足上面公式的函数 K(x,x), 都存在用K(x,x)定义的内积空间。这样的函数也称为核。 0) ()() ,() ,()(0)()()() ,() ()(,)(2dxdxxxxxKxxKxxrxxxxxKxxdkRxRxRxrrrrkddffffffffff是对称函数，有，且对于任意的分量的的映射是其中内积运算表示为均是欧氏几何空间和映射令。空间对应向量的核函数已表示为原特征维空间中向量的内积在)()(),(32jTijTijijTi

27、yyxxxxKyyk322212132123212122) 3()2()(),(RxxxxyyyyRxkyyyydxxxxxxxKjTiji映射从。选择核函数例：)(12diiiTjTijTiyxyxdxxyy维向量内积运算公式：一般的 核函数也称为势函数。由势能的概念引出。 例如两类模式样本集在d维特征空间可看成一个点集，具有某种能量的点，在每类的中心(核)xc的能量最大，随距离增大而减小。将附近空间上的点的能量用函数K(x, xc)来表示，这个函数就是核函数。 两个d维向量x和xk同时满足下列三个条件，可作为核函数： K(x, xk) = K(xk, x)，且当xxk 时函数有最大值 x与

28、xk 的距离趋于无穷大时， K(x, xk)趋于零 K(x, xk) 为光滑函数，且是x与xk 之间距离的减函数。 在支持向量机中常用的核函数： 12)(tanh(),(exp),(0 1),(22cmercercxxxxKSxxxxKqxxxxKiiiiqiTi，条件的一种选择满足形函数双曲正切高斯径向基函数多项式形式aas2. 支持向量机算法 用核函数代替最优分类面中的点积，相当于把原特征空间变换到新的特征空间，则 对偶问题求i*， 分类规则 算法的其它条件均不变。siiibxxKyxf*),(sgn)()(21)(1,1jijijNjiiNiixxKyyQ 支持向量网络 输出是中间层节点

29、的线性组合，每一个中间层节点对应于输入样本与一个支持向量的内积。该网络与RBF网络结构相似。 输出（决策规则） 式中 K(xi,x) 核函数 x 输入向量 xi 支持向量 Ns支持向量数目iiiNiiiiywwxxKyxfs权值),(sgn()(01输入向量核函数权值决策f(x)3. 支持向量机实例 用不同的内积函数导致不同的支持向量机算法。采用多项式形式的内积函数 得到的支持向量机是一个q阶多项式分类器。例1：用多项式核函数(q=2)对二维数据用SVM进行非线性分类试验。 两图中分别有两类 训练样本 。虚线为 得到的SVM分类线。 支持样本加了圈； 加了是错分样本。qiTixxxxK 1),(例2：对于不完全可分的非线性模式样本，如同线性SVM可用x、C惩罚项来修正。 现用二次型SVM判别，核函数为 使用了两个不同的C的结果如图。2 1),(iTixxxxK采用高斯核函数型内积 得到的支持向量机是一种径向基函数分类器。与传统RBF区别是一个基函数的中心对应一个支持向量，函数及输出权值由算法自己确定。采用S型函数作为内积,如 SVM实现的是一个两个隐层的多层感知器神经网络，网络的权值、网络的隐层节点数目也是由算法自动确定。22|exp),(siixxxxK)(tanh(),(cxxxxKiia例3：贝尔实验室用支持向量机对美国邮政手写