线性判别函数 边肇祺ppt课件

1、第四章 线性判别函 数1;.广义线性判别函数广义线性判别函数线性判别函数的基本概念线性判别函数的基本概念设计线性判别函数设计线性判别函数的主要步骤的主要步骤感知准则函数感知准则函数及其梯度下降算法及其梯度下降算法几个基本概念几个基本概念解线性不等式的共解线性不等式的共轭梯度法轭梯度法解线性不等式的搜索解线性不等式的搜索法法2;.本章内容的目的意义贝叶斯决策方法的一般步骤概率密度函数估计的实际困难利用样本直接设计分类器线性判别函数的一般做法简单的函数形式，参数待定根据设计要求提出准则函数，优化求解线性判别函数的分类性能“次优”简单易实现，计算量及存储量小3;.4.1.1 线性判别函数的基本概念一

2、般表达式式中x是d维特征向量，又称样本向量，w称为权向量，分别表示为 (4 -1 )0()Tgwxwx1212,.,.TTddx xxw wwxww0是一个常数(阈值权)对于两类问题的线性分类器可以采用下述决策规则：令12( )( )( ) gggxxx4;.12g0g0g0 xxxxx( ) , 则决策如果( )d时通常是非奇异的。 也是对称半正定矩阵，在两类条件下，它的秩最大等于1.wSbS16;.2.在一维Y空间各类样本均值类内离散度和总类内离散度1,1,2(420)iiy Yimy iN22212()() ,1,2iTiiiy YwSymymiSSS17;.定义Fisher准则函数为了

3、使类别分离得好，应使各类模式投影均值彼此间相距尽可能大使各类样本内部尽量密集综合即有12(mm2)2212()SS122212 ( ( )(4 23)FmmJSSw2)也就是使 尽可能打的w作为投影方向。( )FJw18;. 但式（4-23） 的并不显含w，因此必须设法将 变成w的显函数。( )FJw( )FJw2121212121212()()()()() TTTTTTTTbmmS2)w mw mwmmwmmwmmmmwww由式(4-20)得111()iiiTTTiiy Yx Xx Xiiimyw xwxw mNNN19;.121222221212112212()()()() ()() ()

4、y Yy YTTXTTxTTWSSy my mSSSxxwx mx mwwx mx mwww ww122212 ( ( )-TbFTwmmSJSSSwwwww2)（4 27）( )()JJ aww( )J w20;.下面求使准则函数取极大值时的*w可以用Lagrangge乘子法求解。令分母等于非零常数，即令0Tww S wc定义Lagrangge函数为( , )()TTBwL ww S ww S wc式中 为Lagrangge乘子。将上式对w求偏导数，得(,)bwLSSwwww 令偏导数为零，得*0bwbwS wS wS wS w21;.其中 就是准则函数的极值解。1*wbSSww*wwS因为

5、 非奇异，上式两边左乘 ，可得1wS上式为求一般矩阵 的本征值问题。但在这个特殊情况下，利用 的定义，上式左边的 可以写成1wbSSbS*bS w*121212*12()()()()TbTS wmmmmwmm RRmmw式中R为一标量，所以 总是在向量 的方向上由于我们的目的是寻找最好的投影方向， 的比例因子对此并无影响，因此从式（4-30）可得（4-30）*bS w12()mm*w*1*112()wbwSSSRwwmm22;.从而可得*1*11212()()wwRwSmmwSmRm忽略比例因子得*w*w 就是是准则函数取极大值的解。也就是d维X空间到一维Y空间的最好投影方向。有了 ，利用式（

6、4-15），就可以把d维样本 投影到一维，这实际上是多维空间到一维空间的一种映射。nx几种一维分类问题的基本原则（1）当维数d和样本数N都很大时，可以采用贝叶斯决策规则，从而获得一种在一维空间的“最优”分类器。（2）如果上述条件不满足，也可以利用先验概率知识选定分界阈值点 ，如选择0y23;.2(1)10(2)1122212(3)12120122ln( ()/()22mmyN mN mymNNmmP wP wyNN1()P w2()P w1w2w*Tyw x102wyyxw或d时，没有d+1个样本落入（d-1）维子空间内；当N0 。0jTya，对，对1 iy2 jy，对，对0Tiay，当，当

7、nyjy2 jy，当，当 iy1iy这时问题就化为找一个a，使对所有的 ，有 。上述的处理称为规范化。 称为规范化的增广样本。ny0Tna y ny27;.3.解向量和解区 在线性可分的情况下，满足 的a称为权向量，记为a*。 方程 中的a和 的作用是对偶的。 一个权向量a是权空间中的一个点。每个样本yn对a的可能位置都起到限制作用。即要满足aTyn0.对所有样本满足aTyn0的a即为一个解。0,1,2,Tna ynN0Tna y ny方程aTyn=0确定了权空间中过原点的一个超平面 ，它的法向量是yn。解应在 的正侧（因为要求aTyn0） 正半空间。 N个样本确定了权空间中的N个平面，每个平

8、面把权空间分成了三部分，正侧、负侧和平面本身。nHnH28;. 所以，如果解存在，则必定在N个超平面的正半空间的相交区。这个区域称为解区。区域中的每个向量都是解向量a*。 29;.4对解区的限制 为使所得的a*对新的样本也能正确分类，a*最好位于解区的中央。 为提高泛化能力，使解更可靠，引入余量b0，寻找满足aTyn=b, i=1, 2, , N的解区。 显然，满足aTyn=b0的解区位于原aTyn0的解区之内，且离原解区边界的距离为nby30;.4.2.3感知准则函数及其梯度下降算法 设有一组样本y1, , yN（规范的增广样本向量）。目的是求一a*，使得a*Tyi0, i=1, 2, ,

9、N。( )()kTpy YJaa y构造一个准则函数， Yk ：被a所错分的样本集合。 即aTy=0。 0)(aJp所以只有当Yk为空集时，不存在错分样本，才有 *( )min( )0ppJaJa 这一准则函数是Rosenblat在五十年代末提出来的，用来模拟人脑神经细胞的模型，所以一般称为感知准则函数。 31;.可以用梯度下降法求使Jp(a)最小的a*。( )( )()kppy YJaJaya(1)( )( )kkky Ya ka kJa kykYYk 是被a所错分的样本集。 函数Jp(a)在某点ak的梯度Jp(ak)是一个向量，其方向是Jp(a)增长最快的方向，而负梯度是减小最快的方向。

10、沿梯度方向极大值 沿负梯度 极小值迭代公式： ：被a(k)错分的样本集。即，当任意给定初始权向量a(1)后，a(k+1)等于a(k)加上kky Yy32;. 可以证明，若样本线性可分，则经过有限次迭代修正后，一定可以找到一个解向量，即算法收敛。收敛速度取决于权向量a(1)和系数 上述的算法是一种“批处理”方式。用a(k)把所有的样本分类一次，然后统计错分的样本，修改一次权。 k 也可采用“单样本修正”：顺序对各个样本进行分类，分错了就修正权。 单样本修正算法为：错分的是被任意kkkkayykakaa,)() 1() 1 (其中对任何k都有a(k)Tyk0,式Ya0可写成0YabT1 , 1 ,

11、1 Nb 个式中b是N维向量，不失一般性，可取定义准则函数21( )()qJaYabYab如果Yab，则(Ya-b)和|Ya-b|同号，因此，Jq1(a)=0,反之，如果有某些yi不满足aTyibi，则(aTyi-bi)和|aTyi-bi |异号因此Jq1(a)0。不满足的yi越多， Jq1(a)越大。显然， Jq1(a)取极小值时的a为最优解a*，并且在不等式组一致的情况下，Jq1（a*）=0，在不一致的情况下， Jq1（a*）0我们称Jq1(a)为最小错分样本数准则1（4-49）38;.共轭梯度法概念 设B是一个 阶对称正定矩阵，若有两个d维向量u和v使（u,Bv）=0,称u和v对于矩阵B

12、互为共轭。显然，若u和v对于单位矩阵I互为共轭，则u和v正交。当x和y是B的本征向量时，有 dd( ,)( ,)( , )0y Bxyxy x因此，一个正定矩阵B的本征向量对于B互为共轭。共轭梯度算法就是以Ed空间中的一组对于B互为共轭的向量作为一维搜索方向，使二次正定函数0( )TTf xbb xx Bx达到极小值的最优化算法。用共轭梯度法可以求得序列x0,x1,x2,使得012()( )()f xf xf x39;.可以证明，对于二次正定函数f（x），最多用d步，就可以使序列收敛于f(x)的极值解x* 由于式（4-49）定义的准则函数不是一个二次正定函数，而是一个分段二次正定函数，因此，在

13、沿d个（对于增广空间则为d+1个）互为共轭的向量进行一维搜索后，有可能达不到准则函数Jq1(a)的最小值即算法不收敛。这时就要重新开始计算，若用r表示重新开始的周期，则r=d（或d+1）。 在任意点a（除使Jq1(a)=0的点之外），Jq1(a)的负梯度方向可表示为121( )( )| ()4| ()1|TTaqg aJaYYabYabY ppYabYabg 式中令用k表示迭代步数，用 表示满足a的不等式的数目，a*表示最优解40;.算法的具体步骤步骤1 置k=0，并任意给定初始权向量a0，计算Ya0和 。 如果 ，则令 然后继续步骤2 如果 ，则令 a*=ak ，停止；如果 ，则令a*=-a

14、k ，停止；否则继续。步骤3 计算gk。如果 ，则停止；否则计算 ，然后继续步骤4 求 如果k为 的整倍数，则令 ；否则令 ，并计算这里Sk表示第k次搜索时的梯度下降方向。若a0表示对a*的第一次逼近，则00/ 2N000000,aaYaYaN kN0k0kgkk0k1k1kkkkkSSg000Sg41;.有上述表达式所产生的S1，S2，对于二次函数中的正定矩阵时互为共轭的步骤5 寻找最佳步长 ，即计算使 取极小值时的步骤6 令步骤7 令 k=k+1 转向步骤2k()kkJ aS111,kkkkkkkkkaaS YaYaYS并计算对于式（4-49）表示的分段二次函数，在Ya=b0的一致条件下，

15、上述算法可以在有限步内使序列ak收敛于最优解a*。而在Ya=b0不一致的条件下，只要适当的选择b，使在Jq1(a)的唯一极小点a*上有 则该算法产生的序列ak也在有限步内收敛于a*。*,(1,2,)TiiaybiN42;.对于式（4-49）表示的准则函数Jq1(a)在不等式组不一致的情况下，对某些样本，可能存在0aTyi0，yi应被正确分类；但又由于aTyi0的解a*。在不一致的情况下，由于Jq1(a)是严格的凸函数，其唯一极小点是a=0，而且有因此， 的条件不成立，所以得到解向量a*,(1,2,)TiiaybiN43;.对于模式识别问题来说，我们可以用作为准则函数来解决上述问题，显然这时存在

16、下列关系也就是说使F(a)最小，同在终止条件和 下使Jq1(a)最小是等价的。这是需要对上述算法步骤1和步骤4改变如下步骤1 首先通过原有算法得到一个收敛点，记为as，并以此作为补充算法起点。步骤4 计算 和 ，并且继续 22|( )|YaYaF aa1( )( )2 ( )0aaqF aJaF aa 1( )2 ( )aqJaF aa0a 2()/ |Tkkkka ga kkkkSag44;. 可以证明，这样得到的Sk任然是Jq1(a)的下降方向。同时可以证明，假设Ya0是不一致的，且在求Jq1(a)的过程中用步骤4代替原步骤4，若所得的序列ak是有限的，则序列的最后一个元素就相当于F(a)

17、的一个局部最小值的解。若序列是无限的，则它趋向于F(a)的一个局部最小值的解。 在进行上述计算时，由于我们使用原算法的收敛点as作为起始点，它常常是全局最优解的一个很好的逼近，故可以得到F(a)的全局最优解。45;.4.4.2 解线性不等式组的搜索法 考虑齐次线性不等式组为规范化增广样本矩阵，每行yi代表一个样本，N为样本数， 为yi的维数，且有0Ya 111212122212.ddNNNdyyyyyyYyyy其中 矩阵NddNd46;.定义另一种形式的最小错分样本数准则如下211sgn()( )2NiqiJy aaNoImage1,0sgn()1,0iiiy ay ay a对于对于Jq2(a

18、)实际上是a所满足的不等式的数目。我们称之为最小错分样本数准则2。使Jq2(a)取最大值的a，就是我们要求的解向量a*。 对于每个yi，方程yia=0在权空间中建立了一个超平面Hi，而且所有超平面都通过原点。因此，N个样本向量所建立的超平面把权空间划分为凸多棱锥的有限集合，每个锥C都由有限个支撑超平面所组成。组成锥的一部分超平面，或超平面的截取部分，称为锥的“前沿”，欧式空间Ed中(1)d （4-57）47;.个超平面的交叫做锥的“棱”。 右图示出三锥凸多棱锥及其前沿和棱的一个例子。 锥C中的每一个点，都对应一个权向量a，而且某个锥C中的任何权向量对样本集的划分都是相同的，或者说某个锥中的所有

19、权向量所满足的不等式的数目是相同的。如果某个锥C中的任何权向量都能使式（4-57）的准则函数Jq2(a)为最大，那么就称这个锥为最小错误锥，记为C*。这样，求使最多数目的不等式得到满足的权向量a*的问题，就转化为寻找一个或多个最小错误锥C*的问题了。由于对于每个 存在着对称反射，即 维权向量 和 所产生的分类情况恰好相反，所以，如果对于某个a，存在dCEdaCaC48;.2( )qNJa,N21,NNNN为偶数为奇数2qNJ（-a）2( )qNJa2( )qNJa其中则必有 。由于我们只关心最小错误锥，因此，我们只限于研究使 的那些锥就可以了。如果遇到 的情况，则用-a代替a。定理4.1 假设Y满足Haar条件，令a（0）是Ed中的任何一条棱上的权向量，不是一般性，初始棱选作前 个样本yi的确定的 个超平面的交，即令：(1)d (1)d 121(0),daHHH那么，最优化权向量 一定在下面定义的搜索系列中*aC49;.1231112321123(1)1 (1)| 1 (2)| 2 (1)| (1)idiidiiii ddaaHHHHiIaaHHHHiIa daHHHHi dI ,1,2,1,kIkd(1)0,iy