第五章-非线性分类器.ppt

刘园园,非线性分类器,2020/4/26,西安电子科技大学计算机学院,引言,2020/4/26,西安电子科技大学计算机学院,2,提纲,2020/4/26,西安电子科技大学计算机学院,3,分段线性判别函数二次判别函数支持向量机核函数机多层感知器神经网络,分段线性判别函数,2020/4/26,西安电子科技大学计算机学院,4,思路：如果两类可以划分为线性可分的若干子类，则可以设计多个线性分类器，实现分段线性分类器。联系：上一章的多类线性判别函数实际就是分段线性判别函数。,分段线性判别函数,2020/4/26,西安电子科技大学计算机学院,5,最简单情况：直接依据样本到各子类中心的距离判别更一般情况：对每个子类求一个线性判别函数。,分段线性判别函数,2020/4/26,西安电子科技大学计算机学院,6,三种设计方法：若已知子类划分，则可直接用多类线性分类方法只知子类数目，不知子类划分，用下述错误修正法,分段线性判别函数,2020/4/26,西安电子科技大学计算机学院,7,分段线性判别函数,2020/4/26,西安电子科技大学计算机学院,8,3.未知子类数目：,二次判别函数,2020/4/26,西安电子科技大学计算机学院,9,需要d(d+3)/2+1个参数，计算复杂,支持向量机,2020/4/26,西安电子科技大学计算机学院,10,广义线性判别函数核函数变换与支持向量机支持向量机的应用与实现算法多类支持向量机用于函数拟合的支持向量机,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,11,经过变换，维数大大增加。使得问题很快陷入”维数灾难”计算变得非常复杂而不可行样本变换到高维空间后样本数目并未增加，在高维空间变得很稀疏，算法会因为病态矩阵等问题无法进行,广义线性判别函数：,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,12,2.核函数变换与支持向量机回顾：1.线性支持向量机的对偶问题,2.判别函数：,3.支持向量满足等式：,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,13,核函数与支持向量机：支持向量机并没有直接计算复杂的线性变化，采用了巧妙的迂回方法简介实现这种变化,基本思路：1.特征x进行非线性变换2.优化问题：,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,14,3.决策函数：,变换空间的权向量,变换空间的特征,新的特征空间,变换对支持向量机的影响是把两个样本在原始空间中的内积变成了新空间的内积(核函数)我们没有必要知道非线性映射的具体形式，直接设计核函数而不用设计,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,15,选择一个满足Mercer条件的核函数，就可以构建非线性的支持向量机。可以证明Mercer条件可以放松为如下条件的正定核,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,16,对于满足正定条件的核函数，肯定存在一个从X空间到内积空间H的变化，使得,这样构成的空间在泛函中定义的所谓的可再生核希尔伯特空间RKHS。,判别函数,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,17,原始的内积变成了核函数，计算和函数的复杂度与计算内积的复杂度没有差别,判别函数：,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,18,SVM基本思想：通过非线性变换将输入空间变换到一个高维空间，在这个新空间求解最优分类面即最大间隔分类面非线性变换通过适当的内积核函数实现4.求解一个有约束的二次优化问题，有唯一最优解，这与多层感知器网络相比是一个优势。5.问题的计算复杂度由样本数目决定，不取决与样本变换特征维数与所采用的核函数,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,19,SVM形式上类似与一个神经网络,常用核函数：,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,20,支持向量机的实现算法：,支持向量机(SupportVectorMachines),2020/4/26,西安电子科技大学计算机学院,21,美国邮政USPS手写数字数据库，7300训练样本，2000个测试样本，每个样本16*16的点阵，256维的原始特征,支持向量机应用举例,多类支持向量机,两类基于核的支持向量机的正则化框架多类支持向量机：松弛因子项间隔最大化项,2020/4/26,西安电子科技大学计算机学院,22,最小化目标函数：,最小化目标函数：,决策规则：,核函数机器,大间隔机器与核函数：任何的线性方法，如果把特征进行适当的变换，就可以得到相应的非线性方法。存在问题：1.样本维数呈指数增加。2.求解的决策函数复杂度增加，推广能力差。支持向量机:大间隔以及核函数核函数：运算不需要在高维的空间里进行。映射后的空间实际上还是无穷维，推广能力仍然是一个很大的问题。大间隔：控制最大化分类间隔，在很高维的空间里仍能保持最好的推广能力,2020/4/26,西安电子科技大学计算机学院,23,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,24,1.回顾线性可分Fisher准则函数(FishersCriterion),2.非线性可分核Fisher判别(KernelFishersDiscriminant),2.1非线性变换,2.2变换空间的类内离散度和类间离散度,基本思想：,第i类的第j个样本,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,25,2.3判别函数,w:变换空间里的权值向量,带来的问题：变化复杂、维数高，直接求解没有优势甚至不可行。如何求解？,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,26,再生核希尔伯特空间理论：任何解都处在F空间中所有训练样本张成的子空间中,2.4关键定理：,设：,Mercer条件,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,27,再生核希尔伯特空间理论：任何解都处在F空间中所有训练样本张成的子空间中,2.4关键定理：,设：,Mercer条件,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,28,第j类核函数矩阵,：所有元素都为的矩阵,设：,Mercer条件,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,29,通过Fisher线性判别类似的推导，解是的最大本征值对应的本征向量，最优解的方向是：,变换空间的Fisher线性判别准则：,对于病态问题通常矩阵N非正定的，因此一种补偿的方法，使,为正定矩阵,用替代算法中的N,求解：,核Fisher判别,2020/4/26,西安电子科技大学计算机学院,30,思考：如何用核方法构造非线性的最小平法误差方法MSE？,通过求得的最优,则决策规则：,人工神经网络,感知机多层感知机反向传播算法径向基函数网络总结,2020/4/26,西安电子科技大学计算机学院,31,引言,2020/4/26,西安电子科技大学计算机学院,32,（人工）神经网络的基本结构：大量简单的计算单元（结点）以某种形式相连接，形成一个网络，其中的某些因素，如连接强度（权值）、结点计算特性甚至网络结构等，可依某种规则随外部数据进行适当的调整，最终实现某种功能。,引言,2020/4/26,西安电子科技大学计算机学院,33,三个要素：神经元的计算特性（传递函数）网络的结构（连接形式）学习规则三要素的不同形成了各种各样的神经网模型人工神经网络三种类型：前馈型网络、反馈型网络、竞争学习网络前馈型网络：节点按照一定的层次排列，信号按照单一的方向从一层传递到下一层，把每一层看作是对特征进行的一次家加工或变换。(网络连接是单向的)反馈型网络：输入信号作用到神经元节点上，各个节点的输出又作为输入反馈到各节点上，形成动态系统，当系统稳定后读取其输出。,引言,2020/4/26,西安电子科技大学计算机学院,34,引言,2020/4/26,西安电子科技大学计算机学院,35,发展历程：,引言,2020/4/26,西安电子科技大学计算机学院,36,基本的神经元模型McCulloch-PittsModel(1943)(ThresholdLogicUnit-TLU),引言,2020/4/26,西安电子科技大学计算机学院,37,大规模并行、分布式表达和计算本质上可以理解为函数逼近,感知器,2020/4/26,西安电子科技大学计算机学院,38,感知器（Perceptrons）模型：,感知器,2020/4/26,西安电子科技大学计算机学院,39,等价表示：,感知器,2020/4/26,西安电子科技大学计算机学院,40,感知器学习算法：,训练数据：,权重：,感知器,2020/4/26,西安电子科技大学计算机学院,41,初始化：迭代：,感知器,2020/4/26,西安电子科技大学计算机学院,42,学习算法收敛性：对线性可分的数据有下面的定理,感知器,2020/4/26,西安电子科技大学计算机学院,43,对应于线性判别函数算法的问题：对线性不可分的数据，算法不收敛！一个解决方案：多层感知器，非线性分类器。,多层感知器,2020/4/26,西安电子科技大学计算机学院,44,多层感知器（MultilayerPerceptrons）结构,多层感知器,2020/4/26,西安电子科技大学计算机学院,45,激活函数(activationfunction),符号函数(不可微),Sigmoid函数(可微),多层感知器,2020/4/26,西安电子科技大学计算机学院,46,多层感知机的一致逼近性,定理(Funahashi(1989),Hornik(1989),Stinchcombe实际上，数字计算机的所有逻辑电路都是用XOR门实现的。XOR是通用门(universallogicgate)：任何一个逻辑电路都可以只用XOR门来实现（因为用XOR可以实现AND、OR、NOT）。而AND,OR,NOT都不是通用门。能否实现XOR关系到学习机的“学习”能力，若连XOR都实现不了，更不用谈实现计算机。,多层感知器,2020/4/26,西安电子科技大学计算机学院,48,感知器不能解决。,多层感知器,2020/4/26,西安电子科技大学计算机学院,49,两个隐单元的三层感知机解决XOR问题。,多层感知器,2020/4/26,西安电子科技大学计算机学院,50,XOR真值表,多层感知器,2020/4/26,西安电子科技大学计算机学院,51,解决XOR问题,多层感知器,2020/4/26,西安电子科技大学计算机学院,52,多层感知机把输入空间变换到由其隐层输出所张成的空间，然后在这个空间中进行线性分类。与Bayes决策的关系：对两类问题0，1，采用最小均方误差训练时，多层感知机的输出是Bayes后验概率的估计。,多层感知器,2020/4/26,西安电子科技大学计算机学院,53,式中第二项与权值无关，因而最小化均方误差等效于最小化式中第一项，即网络输出与样本后验概率之间的平方误差在所有可能样本上的数学期望。,多层感知器,2020/4/26,西安电子科技大学计算机学院,54,结论：当训练样本无穷多时，以均方误差最小为目标训练的神经网络的输出在统计意义上是对样本后验概率的最小均方误差估计。,反向传播算法,2020/4/26,西安电子科技大学计算机学院,55,多层感知机的中间隐层不直接与外界连接，其误差无法估计。,反向传播算法从输入层经隐层逐层正向计算各单元的输出；由输出误差逐层反向计算隐层各单元的误差，并用此误差修正前层的权值。,反向传播算法,2020/4/26,西安电子科技大学计算机学院,56,多层感知器的例子和符号,反向传播算法,2020/4/26,西安电子科技大学计算机学院,57,多层感知器符号：,第层第i个神经元的输出：,Sigmoid传递函数：,反向传播算法,2020/4/26,西安电子科技大学计算机学院,58,最小平方误差（LeastSquare）准则,平方误差：,最速下降法：,反向传播算法,2020/4/26,西安电子科技大学计算机学院,59,Least-Mean-Square（LMS）准则,第t步只用当前误差：,反向传播算法,2020/4/26,西安电子科技大学计算机学院,60,准则的选用：通常用LMS,稳定，计算量比LS小；LMS的最优解的数学期望收敛到LS的最优解收敛速度快,反向传播算法,2020/4/26,西安电子科技大学计算机学院,61,BP算法,反向传播算法,2020/4/26,西安电子科技大学计算机学院,62,BP算法,反向传播算法,2020/4/26,西安电子科技大学计算机学院,63,的计算LMS准则Sigmoid函数导数,反向传播算法,2020/4/26,西安电子科技大学计算机学院,64,的计算对于输出层(),是当前输出与期望输出之误差对权值的导数对中间层，是输出误差反向传播到该层的误差对权值的导数。,反向传播算法,2020/4/26,西安电子科技大学计算机学院,65,改进：如时变，加记忆项，网络结点可剪裁，等等。,反向传播算法,2020/4/26,西安电子科技大学计算机学院,66,多层感知器,2020/4/26,西安电子科技大学计算机学院,67,多层感知器,2020/4/26,西安电子科技大学计算机学院,68,用多层感知器网络实现模式识别,多层感知器,2020/4/26,西安电子科技大学计算机学院,69,神经网络结构的选择神经元的传递函数-通常选Sigmoid函数网络结构-通常三层（1个隐层）即可满足常见任务需求，隐层节点数目？连接权值-通常采用BP算法学习过学习（over-fitting）与欠学习（under-fitting）问题隐层节点数目：根据具体问题进行试探选择据对问题的先验知识去精心地设计隐层节点的层数和节点数目用算法来推测适当的隐层节点数目,多层感知器,2020/4/26,西安电子科技大学计算机学院,70,过拟合现象：增加隐单元个数训练数据分类正确率测试数据正确率提高识别正确率与隐单元个数有很大关系！,训练数据分类正确率提高,？,多层感知器,2020/4/26,西安电子科技大学计算机学院,71,其他类型的人工神经网络,2020/4/26,西安电子科技大学计算机学院,72,其他类型神经网络：径向基函数（RBF）网络Hopfield网络：反馈型神经网络自组织映射网络：竞争学习的神经网络,径向基函数网络,2020/4/26,西安电子科技大学计算机学院,73,径向基函数网络,2020/4/26,西安电子科技大学计算机学院,