模式识别-张学工

张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity1第四章线性判别函数（线性分类器）张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity24.1引言从基于概率密度（估计）的分类器设计---model-basedmethod到基于样本的直接分类器设计思路：首先选定判别函数类和一定的目标（准则），利用样本集确定出函数类中的某些未知参数，使所选的准则最好。形式化：判别函数类),(g，：未定参数准则函数)(L求*：)(min)(*LL张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity3本章只考虑线性判别函数0)(wxwxgT多类情况0)(iTiiwxwxg，ci,,1——次优分类器（相对于贝叶斯分类器）当正态分布且各类协方差相同时可为最优分类器张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity44.2一些基本概念张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity54.3Fisher线性判别FisherDiscriminantAnalysis(FDA)出发点：把所有样本都投影到一维，使在投影线上最易于分类。----寻找投影方向样本集Nxx,,1X1类11111,,NxxX，2类22122,,NxxX投影iTixwy，Ni,,1张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity6离散度矩阵（ScatterMatrix）：在X空间：类均值向量类内离散度矩阵within-classscatter总类内离散度矩阵或类间离散度矩阵between-classscatter2211SNNSNNSw21SSSw2,1,))((imxmxSijxTijijiX2,1,1ixNmijxjiiXTbmmmmS))((21212,1,))((1imxmxNSijxTijijiiX提示：注意2010年第一次印刷的勘误张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity7在Y空间（一维投影）：类均值2,1,1~iyNmijxjiiY类内离散度2,1,)~(~22imySijxijiY总类内离散度2221~~~SSSw类间离散度2212)~~(~mmSbFisher准则函数(Fisher’sCriterion)：2221221~~)~~()(maxSSmmwJF即：使两类之间尽可能分开，各类内部尽可能聚集。张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity8代入xwyT，可得求解：令分母0cwSwwT，最大化分子。定义Lagrange函数)(),(cwSwwSwwLwTbT0/wL，得即**wSwSwb。*w为极值解。wSwwSwwJwTbTF)()(max:*wJwFw0**wSwSwb张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity9（当dN时wS通常是非奇异的），两边左乘1wS，得**1wwSSbw即*w为bwSS1矩阵的本征向量。将bS代入，有*21211*))((wmmmmSwTwRmmSw)(211（*21)(wmmRT为标量）只考虑*w的方向，得决策规则：)(211*mmSww210,00)(xxwxwxgT则若张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity10选阈值0w：（1）d和N很大时，y近似正态分布，可在Y空间内用贝叶斯分类器。（2）经验，如：)~~(21210mmwmw~0)()(ln21)~~(212121210PPNNmmw张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity114.4感知器（Perceptron）线性判别函数的齐次简化ywxwxgTT0)(,xy1，ww0两类1、2Nyyy,,,21Y:dˆ维增广样本向量决策规则)(yg0，则21y增广权向量增广样本向量张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity12线性可分性：存在一个权向量，使所有样本被正确分类。即：0then,if0then,if,21iTiiTiyyyyNi,,1若定义,if,,if,21iiiiiyyyyyNi,,1则有0iTy,Ni,,1iy叫做规范化增广样本向量，仍记为iy本节只考虑线性可分情况。张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity13解向量*：满足0iTy，Ni,,1的权向量。解区：权值空间中所有解向量组成的区域。对每个样本iy，0iTy为权空间中的一个超平面iHˆ，解区只可能在iHˆ的正侧。所有样本对应的超平面iHˆ的正侧的交集就是解区。余量：解区中所有权向量都是解，但越靠近解区中间的解向量，所得的分类面离各类样本越远（最近距离越远），对将来的样本错分的可能性越小。张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity14引入余量0b，要求解向量满足byiT，Ni.,1（若要求b最大则为“最优分类面”）目的：1.解更可靠，（推广性更强）2.防止算法收敛到解区边界感知准则函数及其求解：如果样本ky被错分，则有0kTy，因此可定义如下的感知准则函数：)()(jTyPyJkjY其中kY是被错分样本的集合。张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity15当且仅当0)(min)(*PPJJ时，无错分样本。----Rosenblatt用梯度下降法求解：Jkkk)()1()(/)(jyPyJJkjYjykykkkjY)()1(张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity16单样本修正：固定增量法：（1）初值)0(任意（2）对样本jy，若0)(jTyk，则jykk)()1(（1k）（3）对所有样本重复（2），直至0PJ显然，如果错分条件改为bykjT)(，则考虑了余量b变增量，如绝对修正法：2)(jjTkyyk收敛：对线性可分样本集，经过有限次修正后一定可以找到一个解*。张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity174.5最小平方误差（MSE）准则函数MinimumSquared-ErrorCriterionFunction把不等式0iTy变为0iiTby，Ni,,1于是不等式组变为方程组bYTNbbbb,,,21通常dNˆ，方程个数多于未知数个数，为矛盾方程组，误差bYe，可求最小二乘近似解。MSE准则*：)(minSJ212)(iiTNiSbybYJ张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity18MSE准则函数的伪逆解0)(2)(令bYYJTS得bYbYYYTT1*)(TTYYYY1)(：伪逆（YYT是ddˆˆ方阵，一般非奇异）张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity19几个关系：1.若b取为2211if,/if,/iiiyNNyNNb，则MSE解*等价于Fisher解，且其中**0wmwT，)(12211mNmNNm.相当于Fisher中my~02.若b取为T]1,,1,1[，则当N时，MSE解yygT)(以最小均方误差逼近Bayes判别函数)|()|()(210xPxPxg即*使dxxpxgyeT)()(202极小。张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity20MSE准则函数的梯度下降算法)(2)(bYYJTs算法：（1）初值)0(任意（2）)()()1(bYYkkTkuntil)(SJ或)()1(kk可选kk/0，00单样本修正：kkTkkyykbkk))(()()1(ky是使kkTbyk)(的样本——Widrow-Hoff算法张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity21小结线性判别函数0)(wxWxgT，决策面0)(xg，规则210)(xxg准则函数)(J，0wwT求*：利用各种最优化方法张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity224.6最优分类超平面与线性支持向量机线性可分情况下的多解性张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity234.6.1最优分类超平面训练样本集线形可分性：存在超平面0)()(bxwxg把所有N个样本都没有错误地分开。最优超平面：一个超平面，如果它能够将训练样本没有错误地分开，并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的，则我们把这个超平面称作最优分类超平面（OptimalSeperatingHyperplane），简称最优超平面（OptimalHyperplane）。两类样本中离分类面最近的样本到分类面的距离称作分类间隔（margin），最优超平面也称作最大间隔超平面。}1,1{,),,(,),,(),,(2211idiNNyRxyxyxyx张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity24尺度调整问题（规范化）1,0)(1,0)(iiiiybxwybxw若若1,1)(1,1)(iiiiybxwybxw若若张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity25最优超平面的问题就成为2,21minwbws.t.Nibxwyii,,2,1,01)(引入拉格朗日系数Nii,,1,0等价问题NiiiibwbxwywwbwL1,1)()(21),,(maxmin张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity26最优解处：Niiiixyw1**01*Niiiy最优超平面的对偶问题（thedualproblem）：NjijijijiNiixxyyQ1,1)(21)(maxs.t.01NiiiyNii,,1,0张学工《模式识别》教学课件XuegongZhang,TsinghuaUniversity27原问题的解Niiiixyw1***1**)(sgn)(sgn)(sgn)(bxxybxwxgxfNiiii库恩-塔克（Kuhn-Tucker）条件，拉格朗日泛函的鞍点处满足Nibxwyiii,,2,1,01])[(等号成立的样本所对应的i才会大于0。----支持向量（SupportVectors）求解b：01])