第五章-非线性分类器

刘园园非线性分类器2023/11/17西安电子科技大学计算机学院引言2023/11/17西安电子科技大学计算机学院2提纲2023/11/17西安电子科技大学计算机学院3分段线性判别函数二次判别函数支持向量机核函数机多层感知器神经网络分段线性判别函数2023/11/17西安电子科技大学计算机学院4思路：如果两类可以划分为线性可分的若干子类，则可以设计多个线性分类器，实现分段线性分类器。联系：

上一章的多类线性判别函数实际就是分段线性判别函数。分段线性判别函数2023/11/17西安电子科技大学计算机学院5最简单情况：直接依据样本到各子类中心的距离判别

更一般情况：对每个子类求一个线性判别函数。分段线性判别函数2023/11/17西安电子科技大学计算机学院6三种设计方法：若已知子类划分，则可直接用多类线性分类方法只知子类数目，不知子类划分，用下述错误修正法分段线性判别函数2023/11/17西安电子科技大学计算机学院7分段线性判别函数2023/11/17西安电子科技大学计算机学院83.未知子类数目：二次判别函数2023/11/17西安电子科技大学计算机学院9需要d(d+3)/2+1个参数，计算复杂支持向量机2023/11/17西安电子科技大学计算机学院10广义线性判别函数核函数变换与支持向量机支持向量机的应用与实现算法多类支持向量机用于函数拟合的支持向量机支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院11经过变换，维数大大增加。使得问题很快陷入”维数灾难”计算变得非常复杂而不可行样本变换到高维空间后样本数目并未增加，在高维空间变得很稀疏，算法会因为病态矩阵等问题无法进行广义线性判别函数：支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院122.核函数变换与支持向量机回顾：

1.线性支持向量机的对偶问题2.判别函数：3.支持向量满足等式：支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院13核函数与支持向量机：支持向量机并没有直接计算复杂的线性变化，采用了巧妙的迂回方法简介实现这种变化基本思路：1.特征x进行非线性变换2.优化问题：支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院143.决策函数：变换空间的权向量变换空间的特征新的特征空间变换对支持向量机的影响是把两个样本在原始空间中的内积变成了新空间的内积(核函数)我们没有必要知道非线性映射的具体形式，直接设计核函数而不用设计支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院15选择一个满足Mercer条件的核函数，就可以构建非线性的支持向量机。可以证明Mercer条件可以放松为如下条件的正定核支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院16对于满足正定条件的核函数，肯定存在一个从X空间到内积空间H的变化，使得这样构成的空间在泛函中定义的所谓的可再生核希尔伯特空间RKHS。判别函数支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院17原始的内积变成了核函数，计算和函数的复杂度与计算内积的复杂度没有差别判别函数：支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院18SVM基本思想：通过非线性变换将输入空间变换到一个高维空间，在这个新空间求解最优分类面即最大间隔分类面非线性变换通过适当的内积核函数实现4.求解一个有约束的二次优化问题，有唯一最优解，这与多层感知器网络相比是一个优势。5.问题的计算复杂度由样本数目决定，不取决与样本变换特征维数与所采用的核函数支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院19SVM形式上类似与一个神经网络常用核函数：支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院20支持向量机的实现算法：支持向量机(SupportVectorMachines)2023/11/17西安电子科技大学计算机学院21美国邮政USPS手写数字数据库，7300训练样本，2000个测试样本，每个样本16*16的点阵，256维的原始特征支持向量机应用举例多类支持向量机两类基于核的支持向量机的正则化框架多类支持向量机：松弛因子项间隔最大化项2023/11/17西安电子科技大学计算机学院22最小化目标函数：最小化目标函数：决策规则：核函数机器大间隔机器与核函数：任何的线性方法，如果把特征进行适当的变换，就可以得到相应的非线性方法。

存在问题：1.样本维数呈指数增加。2.求解的决策函数复杂度增加，推广能力差。

支持向量机:大间隔以及核函数

核函数：运算不需要在高维的空间里进行。映射后的空间实际上还是无穷维，推广能力仍然是一个很大的问题。大间隔：控制最大化分类间隔，在很高维的空间里仍能保持最好的推广能力2023/11/17西安电子科技大学计算机学院23核Fisher判别2023/11/17西安电子科技大学计算机学院241.回顾线性可分Fisher准则函数(Fisher’sCriterion)2.非线性可分核Fisher判别(KernelFisher’sDiscriminant)2.1非线性变换2.2变换空间的类内离散度和类间离散度基本思想：第i类的第j个样本核Fisher判别2023/11/17西安电子科技大学计算机学院252.3判别函数w:变换空间里的权值向量带来的问题：

变化复杂、维数高，直接求解没有优势甚至不可行。如何求解？核Fisher判别2023/11/17西安电子科技大学计算机学院26再生核希尔伯特空间理论：任何解都处在F空间中所有训练样本张成的子空间中2.4关键定理：设：Mercer条件核Fisher判别2023/11/17西安电子科技大学计算机学院27再生核希尔伯特空间理论：任何解都处在F空间中所有训练样本张成的子空间中2.4关键定理：设：Mercer条件核Fisher判别2023/11/17西安电子科技大学计算机学院28第j类核函数矩阵：所有元素都为的矩阵设：Mercer条件核Fisher判别2023/11/17西安电子科技大学计算机学院29通过Fisher线性判别类似的推导，解是的最大本征值对应的本征向量，最优解的方向是：变换空间的Fisher线性判别准则：对于病态问题通常矩阵N非正定的，因此一种补偿的方法，使为正定矩阵用替代算法中的N求解：核Fisher判别2023/11/17西安电子科技大学计算机学院30思考：如何用核方法构造非线性的最小平法误差方法MSE？通过求得的最优则决策规则：人工神经网络

感知机多层感知机反向传播算法径向基函数网络总结2023/11/17西安电子科技大学计算机学院31引言2023/11/17西安电子科技大学计算机学院32（人工）神经网络的基本结构：

大量简单的计算单元（结点）以某种形式相连接，形成一个网络，其中的某些因素，如连接强度（权值）、结点计算特性甚至网络结构等，可依某种规则随外部数据进行适当的调整，最终实现某种功能。

引言2023/11/17西安电子科技大学计算机学院33三个要素：神经元的计算特性（传递函数）网络的结构（连接形式）学习规则三要素的不同形成了各种各样的神经网模型人工神经网络三种类型：前馈型网络、反馈型网络、竞争学习网络前馈型网络：节点按照一定的层次排列，信号按照单一的方向从一层传递到下一层，把每一层看作是对特征进行的一次家加工或变换。(网络连接是单向的)反馈型网络：输入信号作用到神经元节点上，各个节点的输出又作为输入反馈到各节点上，形成动态系统，当系统稳定后读取其输出。引言2023/11/17西安电子科技大学计算机学院34引言2023/11/17西安电子科技大学计算机学院35发展历程：引言2023/11/17西安电子科技大学计算机学院36基本的神经元模型McCulloch-PittsModel(1943)(ThresholdLogicUnit-TLU)

引言2023/11/17西安电子科技大学计算机学院37大规模并行、分布式表达和计算本质上可以理解为函数逼近感知器2023/11/17西安电子科技大学计算机学院38感知器（Perceptrons）模型：感知器2023/11/17西安电子科技大学计算机学院39等价表示：感知器2023/11/17西安电子科技大学计算机学院40感知器学习算法：训练数据：权重：感知器2023/11/17西安电子科技大学计算机学院41初始化：迭代：感知器2023/11/17西安电子科技大学计算机学院42学习算法收敛性：对线性可分的数据有下面的定理感知器2023/11/17西安电子科技大学计算机学院43对应于线性判别函数算法的问题：对线性不可分的数据，算法不收敛！一个解决方案：

多层感知器，非线性分类器。多层感知器2023/11/17西安电子科技大学计算机学院44多层感知器（MultilayerPerceptrons）结构多层感知器2023/11/17西安电子科技大学计算机学院45激活函数(activationfunction)符号函数(不可微)Sigmoid函数(可微)多层感知器2023/11/17西安电子科技大学计算机学院46多层感知机的一致逼近性定理(Funahashi(1989),Hornik(1989),Stinchcombe&White(1989),Hecht(1989))：具有一个隐含层的感知机，可以在闭区间上一致逼近任意连续函数。只要增加网络隐单元个数，就能提高逼近精度。因此，复杂的网络可以实现训练数据集上的零错误率分类器。多层感知器2023/11/17西安电子科技大学计算机学院47例子(XOR问题)问题的提出以及重要性：1956-1958年Rosenblatt提出感知器，是为了实现另一种形式（模拟）的计算机。与数字计算机形成鲜明对照。数字计算机是用逻辑门电路实现的。逻辑门电路的设计：AND,OR,NOT;实际上，数字计算机的所有逻辑电路都是用XOR门实现的。XOR是通用门(universallogicgate)：任何一个逻辑电路都可以只用XOR门来实现（因为用XOR可以实现AND、OR、NOT）。而AND,OR,NOT都不是通用门。能否实现XOR关系到学习机的“学习”能力，若连XOR都实现不了，更不用谈实现计算机。多层感知器2023/11/17西安电子科技大学计算机学院48感知器不能解决。多层感知器2023/11/17西安电子科技大学计算机学院49两个隐单元的三层感知机解决XOR问题。多层感知器2023/11/17西安电子科技大学计算机学院50XOR真值表多层感知器2023/11/17西安电子科技大学计算机学院51解决XOR问题多层感知器2023/11/17西安电子科技大学计算机学院52多层感知机把输入空间变换到由其隐层输出所张成的空间，然后在这个空间中进行线性分类。与Bayes决策的关系：对两类问题[0，1]，采用最小均方误差训练时，多层感知机的输出是Bayes后验概率的估计。多层感知器2023/11/17西安电子科技大学计算机学院53式中第二项与权值无关，因而最小化均方误差等效于最小化式中第一项，即网络输出与样本后验概率之间的平方误差在所有可能样本上的数学期望。多层感知器2023/11/17西安电子科技大学计算机学院54结论：„当训练样本无穷多时，以均方误差最小为目标训练的神经网络的输出在统计意义上是对样本后验概率的最小均方误差估计。反向传播算法2023/11/17西安电子科技大学计算机学院55多层感知机的中间隐层不直接与外界连接，其误差无法估计。反向传播算法

„从输入层经隐层逐层正向计算各单元的输出；„

由输出误差逐层反向计算隐层各单元的误差，并用此误差修正前层的权值。反向传播算法2023/11/17西安电子科技大学计算机学院56多层感知器的例子和符号反向传播算法2023/11/17西安电子科技大学计算机学院57多层感知器符号：第层第i个神经元的输出：Sigmoid传递函数：反向传播算法2023/11/17西安电子科技大学计算机学院58最小平方误差（LeastSquare）准则平方误差：最速下降法：反向传播算法2023/11/17西安电子科技大学计算机学院59Least-Mean-Square（LMS）准则第t步只用当前误差：反向传播算法2023/11/17西安电子科技大学计算机学院60准则的选用：通常用LMS稳定，计算量比LS小；LMS的最优解的数学期望收敛到LS的最优解收敛速度快反向传播算法2023/11/17西安电子科技大学计算机学院61BP算法反向传播算法2023/11/17西安电子科技大学计算机学院62BP算法反向传播算法2023/11/17西安电子科技大学计算机学院63

的计算LMS准则Sigmoid函数导数

反向传播算法2023/11/17西安电子科技大学计算机学院64

的计算

对于输出层(),是当前输出与期望输出之误差对权值的导数对中间层，是输出误差反向传播到该层的误差对权值的导数。

反向传播算法2023/11/17西安电子科技大学计算机学院65改进：如

时变，加记忆项，网络结点可剪裁，等等。反向传播算法2023/11/17西安电子科技大学计算机学院66多层感知器2023/11/17西安电子科技大学计算机学院67多层感知器

2023/11/17西安电子科技大学计算机学院68用多层感知器网络实现模式识别多层感知器2023/11/17西安电子科技大学计算机学院69神经网络结构的选择神经元的传递函数

----通常选Sigmoid函数网络结构

----通常三层（1个隐层）即可满足常见任务需求，隐层节点数目？连接权值

----通常采用

BP算法学习过学习（over-fitting）与欠学习（under-fitting）问题隐层节点数目：根据具体问题进行试探选择据对问题的先验知识去精心地设计隐层节点的层数和节点数目用算法来推测适当的隐层节点数目多层感知器2023/11/17西安电子科技大学计算机学院70

过拟合现象：

增加隐单元个数

训练数据分类正确率测试数据正确率提高

识别正确率与隐单元个数有很大关系！训练数据分类正确率提高？？多层感知器2023/11/17西安电子科技大学计算机学院71其他类型的人工神经网络2023/11/17西安电子科技大学计算机学院72其他类型神经网络：径向基函数（RBF）网络Hopfield网络：反馈型神经网络自组织映射网络：竞争学习的神经网络径向基函数网络2023/11/17西安电子科技大学计算机学院73径向基函数