新版线性判别函数市公开课获奖课件

1、第四章 线性判别函数Bayesian分类器设计办法，已知类条件概率密度 p(x|i) 参数表示式先验概率 P(i) 利用样本预计 p(x| i) 未知参数用贝叶斯规则将其转换成后验概率 P(i|x) ，并依据后验概率大小进行分类决议。第1页第1页处理实际问题办法在实际中存在问题样本特性空间类条件概率密度形式经常很难拟定利用 Parzen 窗等非参数办法恢复分布往往需要大量样本，并且伴随特性空间维数增长所需样本数急剧增长。因此，在处理实际问题时，往往是利用样本集直接设计分类器，而不恢复类条件概率密度。即采用判别函数，首先给定某个判别函数类，然后利用样本集拟定出判别函数中未知参数。第2页第2页线性

2、判别函数线性判别函数法是一类较为简朴判别函数。是统计模式辨认基本办法之一。它首先假定判别函数 g(x) 是 x 线性函数，即 g(x)=wTx+ w0 ，对于 c 类问题，能够定义 c 个判别函数， gi(x)=wiTx+ wi0 ， i=1,2 ， c 。用样本去预计各 wi 和 wi0 ，并把未知样本 x 归到含有最大判别函数值类别中去。关键是如何利用样本集求得 wi 和 wi0 。第3页第3页训练和学习“训练”和“学习” 在待辨认模式中，挑选一批有代表性样本，通过人工判读，成为已知分类样本，把这批样本逐一输入到计算机中“训练”程序或算法中，通过一次次迭代，最后得到正确线性判别函数。这样迭

3、代过程称之为训练过程，所构成分类器称为有些人监督或有教师分类器。第4页第4页4.1.1 线性判别函数基本概念在正态分布Bayesian判别中，已经碰到过在两类情况下判别函数为线性情况。假设有1 和2 两类模式，在二维模式特性空间可用始终线把这两类模式划分开，如图 4.1 所表示。第5页第5页x1x2g(x) = w2x2+w1x1+w0 图4.1两类模式一个简朴判别函数+划分直线方程参数坐标变量4.1.1 线性判别函数基本概念第6页第6页判别规则若给定一个未知类别模式x当g(x)0 时，则决议 x 属于1 ；当 g(x)0，因此决议面法向量是指向 R1 。因此，有时称 R1 中任何 x 在 H

4、 正侧，相应地，称 R2 中任何 x 在 H 负侧。4.1.1 线性判别函数基本概念第12页第12页判别函数 g(x) 是特性空间中某点 x 到超平面距离一个代数量度。若把 x 表示成式中 xp ：是 x 在 H 上投影向量； r ：是 x 到 H 垂直距离；：是w方向上单位向量。4.1.1 线性判别函数基本概念第13页第13页若 x 为原点，则 g(x)=w0 (4-7)将 (4-7) 代入 (4-6) ，就得到从原点到超平面 H 距离 (4-6) 判别函数 g(x) 是特性空间中某点 x 到超平面距离一个代数量度。4.1.1 线性判别函数基本概念第14页第14页假如 w00 ，则原点在 H

5、 正侧；若 w00 ，则原点在 H 负侧。若w0=0 ，则 g(x) 含有齐次形式 wTx ，阐明超平面 H 通过原点。判别函数 g(x) 是特性空间中某点 x 到超平面距离一个代数量度。4.1.1 线性判别函数基本概念第15页第15页图 4.2 对这些结果作了几何解释。4.1.1 线性判别函数基本概念第16页第16页结论利用线性判别函数进行决议，就是用一个超平面把特性空间分割成两个决议区域。超平面方向由权向量 w 拟定，它位置由阈值权 w0 拟定。判别函数 g(x) 正比于 x 点到超平面代数距离（带正负号）当 x 在 H 正侧时， g(x) 0 ，在负侧时， g(x) 0 。4.1.1 线

6、性判别函数基本概念第17页第17页4.1.2 广义线性判别函数如图 4.3 所表示二类问题。设有一维样本空间 X ，所希望划分是：假如 xa ，则 x 属于1 类；假如 b x0 ，则决议 x1g(x)0 ，则决议 x2二次判别函数可写成下列普通形式g(x)=c0+c1x+ c2x2(4-10)假如适当选择 x y 映射，则可把二次判别函数化为 y 线性函数4.1.2 广义线性判别函数第20页第20页式中称为广义判别函数，a叫做广义权向量。 普通地，对于任意高次判别函数 g(x)(这时 g(x) 可看作对任意判别函数作级数展开，然后取其截尾部分迫近)，都能够通过适当变换，化为广义线性判别函数来

7、处理。4.1.2 广义线性判别函数第21页第21页存在问题通过变换后，维数大大增长了，这将使问题不久陷入所谓“维数劫难”。在统计学习理论中，对广义线性分类器进行研究，克服了“维数劫难”问题，进而发展出了最新模式辨认办法支持向量机，成为处理有限样本情况下非线性分类问题有效手段。4.1.2 广义线性判别函数第22页第22页把 (4-1) 式定义线性判别函数写成下面形式(4-12)增广特性向量Augmented feature vector增广权向量(广义权向量)Augmented weight vector4.1.2 广义线性判别函数第23页第23页结论y 与 x 相比，即使增长了一维，但保持了样

8、本间欧氏距离不变，变换后样本向量仍然所有位于 d 维子空间，即原 X 空间中，方程(4-13)在Y空间拟定了一个通过原点超平面 。它对 d 维子空间划分与原决议面 wTx+ w0=0 对原 X 空间划分完全相同。4.1.2 广义线性判别函数第24页第24页例子这种办法优缺点可通过例子来阐明。考虑二次判别函数得到三维向量y从x到y映射如图所表示。4.1.2 广义线性判别函数第25页第25页例子4.1.2 广义线性判别函数数据仍保持固有一维，由于改变x将造成y沿着一个三维曲线运动。假如x服从某一个概率分布时，得到密度函数是退化，即曲线之外是0，在曲线上是无穷大，这是从低维空间到高维空间映射普遍问题

9、。第26页第26页例子4.1.2 广义线性判别函数图中映射y=(1,x,x2)T把一条直线映射为三维空间中一条抛物线。由于两类问题，在三维空间中，一个平面就是一个分隔面。因此，由图可见，这产生了原始一维x空间不连通性第27页第27页例子g(x)=1+x+ 2x2x0.5时g(x)0a=(-1, 1,2)T4.1.2 广义线性判别函数由aTy=0定义平面将y空间分成两个判别区域，如图给出当a=(-1,1,2)T时分类平面和x空间相应判别区域。第28页第28页结论aTy=0在2维空间不穿过原点4.1.2 广义线性判别函数一个三维增广特性空间y和增广权向量a(在原点)。满足aTy=0点集是一个穿过y

10、空间原点超平面(用红色表示)，这个平面垂直于a。这个平面在其本来二维空间中不一定穿过原点(即立方体顶部虚线所表示判决边界)。因此存在一个增广权向量a，能够取得x空间中任意鉴定线。第29页第29页4.1.3 设计线性分类器主要环节设计线性分类器，就是建立线性判别函数(4-l)式g(x) =wTx+w0或广义线性判别函数(4-12)式这样，设计线性分类器就转化为，利用训练样本集寻找准则函数极值点 和 或 。第30页第30页设计线性分类器主要环节下列： 要有一组含有类别标志样本集X=x1，x2，xN。假如在样本 xn 抽出后，把它看作一个拟定观测值，则这组样本集称为拟定性样本集；若把 xn 看作一个

11、随机变量，则这组样本集称为随机样本集。有时也将样本集 X 转换成增广样本集 Y 来处理。4.1.3 设计线性分类器主要环节第31页第31页 要依据实际情况拟定一个准则函数 J 它必须满足： J 值反应分类器性能，它极值解则相应于 最好 决议。 J是样本集X和w、w0或 a 函数；设计线性分类器主要环节下列：4.1.3 设计线性分类器主要环节第32页第32页用最优化技术求出准则函数极值解 和 w*或a*。这样就能够得到线性判别函数或设计线性分类器主要环节下列：4.1.3 设计线性分类器主要环节第33页第33页4.2 Fisher线性判别Fisher线性判别函数是典型判别办法之一，应用非常广泛。应

12、用统计办法处理模式辨认问题时，困难之一是维数问题。在低维空间里行得通办法，在高维空间里往往行不通。因此，减少维数有时就成为处理实际问题关键。第34页第34页在数学上通常能够把 d 维空间样本投影到一条直线上，形成一维空间，即把维数压缩到一维。在普通情况下，总能够找到某个方向，使在这个方向直线上，样本投影能分开得最好。问题是如何依据实际情况找到这条最好、使最易于分类投影线。这就是Fisher法所要处理基本问题 (见图 4.4) 。4.2 Fisher线性判别第35页第35页4.2 Fisher线性判别第36页第36页从 d 维空间到一维空间数学变换办法假设有一集合 X 包括 N 个 d 维样本

13、x1 ， x2 ，xN ，其中 N1 个属于1 类样本记为子集 X1 ，N2 个属于2 类样本记为 X2 ，若对 xn 分量作线性组合可得标量yn=wTxn, n=1 ， 2 ， Ni这样便得到 N 个一维样本 yn 构成集合，并可分为两个子集 Y1 和 Y2 。4.2 Fisher线性判别第37页第37页w* 就是最好投影方向从几何上看，假如 |w|=1 ，则每个 yn 就是相对应 xn 到方向为 w 直线上投影，实际上，w 绝对值是无关紧要，它仅使 yn 乘上一个百分比因子，主要是选择 w 方向。w 方向不同，将使样本投影后可分离程度不同，从而直接影响识别效果。因此，前述所谓寻找最好投影方

14、向问题，在数学上就是寻找最好变换向量 w*问题。4.2 Fisher线性判别第38页第38页定义几种基本参量在 d 维 X 空间各类样本均值向量mi， i =1，2 样本类内离散度矩阵 Si 和总类内离散度矩阵 Sw，i =1，2 Sw=S1+ S24.2 Fisher线性判别第39页第39页样本类间离散度矩阵SbSb=(m1 m2)(m1 m2)T其中 Sw 是对称半正定矩阵，并且当 Nd 时通常是非奇异。Sb 也是对称半正定矩阵，在两类条件下，它秩最大等于 1 。定义几种基本参量4.2 Fisher线性判别第40页第40页在一维 Y 空间各类样本均值，i =1，2 样本类内离散度 和总类内

15、离散度4.2 Fisher线性判别第41页第41页定义Fisher准则函数希望投影后，在一维 Y 空间里各类样本尽也许分得开些，即希望两类均值之差越大越好；希望各类样本内部尽也许密集，即希望类内离散度越小越好。因此，能够定义Fisher准则函数为：4.2 Fisher线性判别第42页第42页寻找使JF(w) 尽也许大 w 作为投影方向。但 JF(w)式并不显含w，因此必须设法JF(w) 将变成w显函数。尽也许大尽也许小Fisher准则函数4.2 Fisher线性判别第43页第43页Fisher准则函数4.2 Fisher线性判别第44页第44页Fisher准则函数4.2 Fisher线性判别第

16、45页第45页Fisher准则合理性：JF(w)只与投影方向相关，与大小无关若w是一个最优解， kw也是最优解，k是任何不为零常数。4.2 Fisher线性判别第46页第46页Fisher最佳投影方向求解：要求：Sw = S1 + S2正定。不然，存在投影方向w，使得wTSww=0，所有数据被投影到一点上。 JF(w)没有极大值。求出最佳投影方向上任何一个w即可。JF(w)有上界，最佳投影方向一定存在！(Sb)max，(Sw)min分别是Sb，Sw矩阵最大、最小特性根。4.2 Fisher线性判别第47页第47页Fisher最佳投影方向求解：一定存在一个最优w ，满足wTSww=1，由于Sw

17、正定。无约束最优化：等价于带约束最优化： max wTSbw wTSww=14.2 Fisher线性判别第48页第48页由于分母等于1是非零常数，wTSww=10定义 Lagrange 函数为JF(w)是广义Rayleigh商，带等式约束最优化，能够用Lagrange乘子法求解。Fisher最佳投影方向求解：4.2 Fisher线性判别第49页第49页式中 为Lagrange乘子，将上式对w求偏导数，得Fisher最佳投影方向求解：4.2 Fisher线性判别第50页第50页最优解满足：其中 w*就是 JF(w) 极值解。由于Sw非奇异，上式两边左乘 ，可得 Fisher最佳投影方向求解：4.

18、2 Fisher线性判别第51页第51页解上式是求普通矩阵 本征值问题。依据类间离散度Sb 定义，上式左边 Sbw*能够写成Fisher最佳投影方向求解：注意 是一个数，因此 总是在向量(m1m2)方向上。4.2 Fisher线性判别第52页第52页只关怀投影方向：w*就是使Fisher准则函数JF(w)取极大值时解，也就是d维X空间到一维Y空间最好投影方向。Fisher最佳投影方向求解：4.2 Fisher线性判别第53页第53页几种分类阈值拟定均值中点法类样本数加权法4.2 Fisher线性判别第54页第54页依据决议规则先验概率加权法就可判断x属于什么类别。y y0 x120，n=1，2

19、，N权向量a即可。a被称作分离向量(separating vector)或解向量(solution vector)。 样本规范化 4.3.1 几种基本概念 线性可分性第63页第63页 解向量和解区解向量假如存在，则必在 正侧，由于只有在正侧才干满足 。4.3.1 几种基本概念 线性可分性第64页第64页 解向量和解区4.3.1 几种基本概念 线性可分性第65页第65页4.3.2 梯度下降算法 ，n=1,2，N，设有一组样本y1，y2，yN，其中yn是规范化增广样本向量，目是找一个解向量 a，使采用办法是：定义一个准则函数J(a)，当a是解向量时，J(a)最小。标量函数最小化问题用梯度下降法。第

20、66页第66页4.3.2 梯度下降算法 梯度下降法原理：从随意选择权向量a(1)开始，计算其梯度向量 J(a(1)， a(2)由自a(1)向下降最陡方向移一段距离得到。设定步长学习率(learn rate)或正百分比因子。取得权向量序列，使J(a)极小第67页第67页Algorithm 1 (Basic gradient descent) ：1 begin initialize a; criterion , (), k 02 do k k + 13 a a (k) J(a)4 until |(k) J(a)| 5 return a6 end4.3.2 梯度下降算法 第68页第68页其中H是赫森

21、矩阵，是J(a)在a(k)二阶偏导：4.3.2 梯度下降算法 梯度下降法存在问题：如何选择学习率(k)？假如(k)太小，收敛将非常慢；而假如(k)太大话也许会过冲(overshoot)，甚至发散。牛顿下降法：第69页第69页牛顿下降法：Algorithm 2 (Newton descent)1 begin initialize a; criterion 2 do3 a aH1J(a)4 until |H1J(a)| 5 return a6 end4.3.2 梯度下降算法 第70页第70页简朴梯度下降法和牛顿下降法比较:简朴梯度下降法牛顿(二阶)算法每一步都给出更加好步长但求赫森逆矩阵计算量很大

22、4.3.2 梯度下降算法 第71页第71页4.3.3 感知器准则函数(perceptron criterion function)结构这样一个准则函数式中Yk是被权向量a错分类样本集合。当y被错分类时也就是说，当且仅当不存在错分样本，即Yk为空集时第72页第72页4.3.3 感知器准则函数求准则函数梯度第73页第73页感知器准则函数算法(批处理)：Algorithm 3 (Batch Perceptron)1 begin initialize a; (), criterion , k 02 do k k + 13 a a + (k) yYky4 until |(k) yYky| 0所表示不等式

23、组，4.4.1解线性不等式组共轭梯度法 第95页第95页为使解更可靠，引入余量b 0，那么规范化增广样本矩阵4.4.1解线性不等式组共轭梯度法 第96页第96页对于(4-47)式能够定义准则函数 (4-47)N维向量4.4.1解线性不等式组共轭梯度法 第97页第97页假如 则 和 同号，因此， ，反之，假如有一些yi不满足 ，则 和 异号，因此， 。不满足yi越多， 越大。 4.4.1解线性不等式组共轭梯度法 第98页第98页显然， 取极小值时a为最优解a*。并且在不等式组一致情况下， ，在不等式组不一致情况下， 。 称为最小错分样本数准则1。 4.4.1解线性不等式组共轭梯度法 第99页第9

24、9页共轭梯度算法基本概念设B是一个dd阶对称正定矩阵，若有两个d维向量u和v使(u，Bv)=0，则称u和v对于矩阵B互为共轭。显然，若u和v对于单位阵I互为共轭，则u和v正交，当x和y是B本征向量时，有 (y，Bx)=(y,x)=(y，x) = 0因此，一个正定矩阵B本征向量对于B互为共轭。4.4.1解线性不等式组共轭梯度法 第100页第100页共轭梯度算法就是以Ed空间中一组对于B互为共轭向量作为一维搜索方向，使二次正定函数f(x) = b0+bTx+xTBx 达到极小值最优化算法。用共轭梯度法能够求得序列x0，x1，x2，使得f (x0)f (x1)f (x2)能够证实，对于二次正定函数f

25、 (x)，最多用d步，就能够使序列x收敛于f (x)极值解x*。4.4.1解线性不等式组共轭梯度法 第101页第101页因此，在沿d个(对于增广空间则为d+1个)互为共轭向量进行一维搜索后，有也许达不到准则函数最小值，即算法通过d(或d+1)步也许不收敛，这时就要重新开始计算，若用r表示重新开始周期，则r = d(或d+1)。由于 式定义准则函数不是一个二次正定函数，而是一个分段二次正定函数，4.4.1解线性不等式组共轭梯度法 第102页第102页在任意点 ， 负梯度方向可表示为4.4.1解线性不等式组共轭梯度法 令第103页第103页这种算法详细环节下列：用k表示迭代步数，用 表示满足于 不

26、等式数目， 表示最优解。置k = 0，并任意给定初始权向量 ，计算 和 。 假如 ，则令然后继续。 4.4.1解线性不等式组共轭梯度法 假如 ，则令 ，停止；假如 ，则令 ，停止；不然继续。第104页第104页计算gk。假如gk=0，则停止；不然计算 ，然后继续。 求k。假如k为r整数倍，则令k= 0；不然令k=1，并计算Sk表示第k次搜索时梯度下降方向。若 表示对 第一次迫近，则 。能够证实，由上述表示式所产生S1，S2，对于二次函数中正定矩阵是互为共轭。4.4.1解线性不等式组共轭梯度法 第105页第105页寻找最佳步长vk，即计算使 取极小值时v。 令 ， 并计算 。 令k = k +

27、1，转向环节2。 4.4.1解线性不等式组共轭梯度法 第106页第106页Nagaraja和Krishna证实，对于 表示分段二次函数，在 一致条件下，上述算法能够在有限步内使序列收敛于最优解。4.4.1解线性不等式组共轭梯度法 而在 不一致条件下，只要适当选择b，使在 唯一极小点 上，有，i=1，2，N第107页第107页则该算法产生序列a也在有限步内收敛于 a* 。对于 表示准则函数，在不等式组不一致情况下，对一些样本，也许存在 因此就产生了一个阈值问题。这时，由于 aTyi0，yi应被正确分类；但又由于 aTyi0收敛于解a*。在不一致情况下，由于Jq1(a)是严格凸函数，其唯一极小点是

28、a=0，并且有4.4.1解线性不等式组共轭梯度法 第109页第109页因此，aTyi bi(i=1，2，N)条件不成立，因此得不到解向量a*。4.4.1解线性不等式组共轭梯度法 作为准则函数来处理上述问题。显然，这时存在下列关系： 第110页第110页也就是说，使 最小，同在终止条件和 下使 最小是等价。这时需要将上述算法环节1和4改变下列：4.4.1解线性不等式组共轭梯度法 通过原有算法得到一个收敛点，记为 ，并以此作为补充算法起点。计算 和 ，并且继续。第111页第111页能够证实，这样得到Sk仍然是 下降方向。同时能够证实，假使Ya0是不一致，且在求Jq1(a)最小值过程中用环节代替原算

29、法环节4，若所得序列a是有限，则序列最后一个元素就相称于F(a)一个局部最小值解。4.4.1解线性不等式组共轭梯度法 第112页第112页若序列是无限，则它趋向于F(a)一个局部最小值解。在进行上述计算时，由于我们使用原算法收敛点as 作为起始点，它经常是全局最优解F(a)一个较好迫近，故能够得到全局最优解。4.4.1解线性不等式组共轭梯度法 第113页第113页4.4.2解线性不等式组搜索法 考虑齐次线性不等式组其中 矩阵 为规范化增广样本矩阵，每一行yi代表一个样本，N为样本数，为yi维数。且有第114页第114页式中 事实上是 所满足不等式数目。称之为最小错分样本数准则2。使Jq2(a)

30、取最大值a就是要求解 a*。现在定义另一个形式最小错分样本数准则下列： 4.4.2解线性不等式组搜索法 第115页第115页因此，N个样本向量所建立超平面把权空间划分成为凸多棱锥有限集合，每个锥C都由有限个支撑超平面所构成。对于每个yi，方程yia =0在权空间中建立了一个超平面Hi，并且所有超平面都通过原点。构成锥一部分超平面，或超平面截取部分，称为锥“前沿”，欧氏空间Ed中 个超平面交叫做锥棱。4.4.2解线性不等式组搜索法 第116页第116页图4.10示出三维凸多棱锥及其前沿和棱一个例子。C+C+C+C原点前沿棱图 4.10并且某个锥C中任何权向量对样本集划分都是相同，或者说，某个锥中

31、所有权向量所满足不等式数目是相同。 锥C中每一个点，都相应一个权向量a4.4.2解线性不等式组搜索法 第117页第117页假如某个锥C中任何权向量都能使上式准则函数为最大，那么就称这个锥为最小错误锥，记为C*。这样，求使最多数目的不等式得到满足权向量 问题，就转化为寻找一个或多个最小错误锥C*问题了。由于对于每个CEd，存在着对称反射，即 维权向量 和 所产生分类情况正好相反，因此，假如对于某个存在4.4.2解线性不等式组搜索法 第118页第118页其中则必有 。由于我们只关怀最小错误锥，因此，我们只限于研究使锥就能够了。假如碰到情况，则用 代替 。 那些4.4.2解线性不等式组搜索法 第119页第119页寻找最小错误锥C*搜索算法。 定理 假设Y满足Haar(Y每个 子阵秩都是 )条件，令 是Ed中任何一条棱上权