05 线性判别函数

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,05,线性判别函数,Bayesian,分类器设计方法，已知,类条件概率密度,p,(,x,|,i,),参数表达式,先验概率,P,(,i,),利用样本估计,p,(,x,|,i,),的未知参数,用贝叶斯规则将其转换成后验概率,P,(,i,|,x,),，并根据后验概率的大小进行分类决策。,解决实际问题方法,在实际中存在问题,样本特征空间的类条件概率密度形式常常很难确定,利用,Parzen,窗等非参数方法恢复分布往往需要大量样本，而且随着特征空间维数的增加所需样本数急剧增加。,因此，在解决实际问题时，往往是利用样本集直接设计分类器，而不恢复类条件概率密度。,即采用判别函数，首先给定某个判别函数类，然后利用样本集确定出判别函数中的未知参数。,线性判别函数,问题描述,线性判别函数,如下图,:,三类的分类问题,它们的边界线就是一个判别函数,判别函数包含两类,:,线性判别函数,:,线性判别函,数,广义线性判别函数,(,所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数,),分段线性判别函数,非线性判别函数,线性分类器的三种典型方法,以,Fisher,准则为代表的传统模式识别方法,以感知准则函数为代表的机器自学习方法,以支持向量机为代表的统计学习理论。,分段线性判别函数,:,近邻法,2024/10/1,5,2024/10/1,6,2024/10/1,7,判别函数的形式,模式的特征矢量：,判别函数：,称为权矢量或系数矢量,判别函数的形式,增广,特征矢量：,增广,权矢量：,判别函数：,两类问题线性判别准则,决策规则,:,对于两类问题的线性分类器决策规则：,方程,g(,x,)=0,定义了一个决策面，把归类于,1,类的点和归类于,2,的点分割开。,假设,x,1,和,x,2,都在决策面,H,上，则有,w,T,x,1,+,w,0,=,w,T,x,2,+,w,0,(4-3),或,w,T,(,x,1,x,2,)=0 (4-4),表明，,w,和超平面,H,上任一向量正交，即,w,是,H,的法向量。,一般地，一个超平面,H,把特征空间分成两个半空间，即对,1,类的决策域,R,1,和对,2,类的决策域,R,2,。,因为当,x,在,R,1,中时，,g(,x,)0,，所以决策面的法向量是指向,R,1,的。,因此，有时称,R,1,中的任何,x,在,H,的正侧，相应地，称,R,2,中的任何,x,在,H,的负侧。,判别函数,g(x),是特征空间中某点,x,到超平面距离的一种代数量度。,若把,x,表示成,式中,x,p,：是,x,在,H,上的投影向量；,r,：,是,x,到,H,的垂直距离；,：是,w,方向上的单位向量。,若,x,为原点，则,g(,x,)=,w,0,(4-7),将,(4-7),代入,(4-6),，就得到从原点到超平面,H,的距离,(4-6),判别函数,g(x),是特征空间中某点,x,到超平面距离的一种代数量度。,如果,w,0,0,，则原点在,H,的正侧；,若,w,0,0,，,g,j,(,x,)0,，,ji,，则判别,x,属于,i,类,；,其它情况，拒识。,多类问题（情况二）,每两个类别之间可以用一个超平面分开；,c,个类别的问题需要,c(c-1)/2,个线性分类界面；,第,i,类与第,j,类之间的判别函数为：,多类问题（情况二）判别准则,如果对任意,j,i,，有,g,ij,(,x,),0,，则决策,x,属于,i,。,其它情况，则拒识。,结论：判别区间增大，不确定区间减小,IR,（,2,）,i,/,j,二分法,多类问题（情况三）,情况三是情况二的特例，不存在拒识区域。,多类问题（情况三）判别函数,c,个类别需要,c,个线性函数：,判别准则：,（,3,）最大判别准则,结论：无不确定区间,例：假设判别函数为：,问 属于哪一类。,解：,所以,三种方法小结,分类方法,判别函数个数,不确定区,难易,i,/,i,二分法,i,/,j,二分法,最大判别准则,M,M(M-1)/2,M,最多,较少,没有,较难,较易,较易,2024/10/1,31,Fisher,准则的基本原理,2024/10/1,32,基本参量的定义,2024/10/1,33,基本参量的定义,2024/10/1,34,Fisher,线性判别,Fisher,线性判别,Fisher,线性判别,Fisher,线性判别,Fisher,线性判别,2024/10/1,40,Fisher,线性判别,看书课堂练习,2024/10/1,42,2024/10/1,43,2024/10/1,44,2024/10/1,45,2024/10/1,46,2024/10/1,47,感知器概念及其训练方法,2024/10/1,48,2024/10/1,49,2024/10/1,50,2024/10/1,51,两个问题：,（,1,）构造准则函数,（,2,）如何最快地搜索到使准则函数取极小值的解,线性判别函数的学习,问题的提出：假设有一个包含,n,个样本的集合,y,1,y,2, ,y,n,一些标记为,1,另一些标记为,2,，用这些样本来确定一个判别函数,g(,x,)=,a,t,x,的权矢量,a,。,在线性可分的情况下，希望得到的判别函数能够将所有的训练样本正确分类；,线性不可分的情况下，判别函数产生错误的概率最小。,训练样本的规范化,非规范化：,规范化：,最优问题的求解：,（,1,）一个适当的代价函数（准则函数）,（,2,）一个优化算法,梯度下降法,一次准则函数及梯度下降法,(Gradient Descent Algorithm),感知准则函数（,Rosenblatt,）,可微函数在某点的梯度是一个向量,函数在该点的变化率最大的方向,函数 的梯度向量定义为,梯度下降法的迭代公式为：,任给定初始权矢量，第,k+1,次迭代时的权矢量等于第,k,次的权矢量加上被,w,（,k,）错分的样本,之,和,乘,以某个系数。,批量修正,准则函数的梯度：,将梯度下降法应用到一次准则函数中,感知器算法,把样本集看成不断出现的序列逐一考虑，称为单样本修正法。 且令 ，称为固定增量法。,若 使得,+,-,+,-,感知器算法,(Perceptron Approach),算法思想,任选一初始增广权矢量,用训练样本检验用分类正确否,对进行校正,对所有训练样本都能正确分类？,END,Yes,Yes,No,No,一、感知器算法,算法步骤：,增广的训练样本集 每个类别已知，,（,1,）令步数,k=1,增量 为正的常数， 的各分量为较小的任意值,（,2,）输入训练模式 ，计算判别函数值,（,3,）调整增广权矢量，规则：,（,a,）如果,（,b,）如果,（,c,）如果,（,4,）如果,kN,，令,k=k+1,，,GOTO,（,2,）,如果,k=N,，则检验 对所有训练样本是否都正确分类，是则结束，否则，令,k=1,，,GOTO,（,2,）,一、感知器算法,收敛定理：如果训练模式是线性可分的，感知器训练算法在有限次迭代后可以收敛到正确的解矢量,证明：。,一、感知器算法,感知器算法在多类问题中的运行步骤：,增广的训练样本集 每个类别已知，,（,1,）令步数,k=1,增量 为正的常数，,C,个权矢量赋任意初值,（,2,）输入符号未规范化的增广训练模式 ，计算,C,个判别函数值,（,3,）调整增广权矢量，规则：,（,a,）如果,（,b,）如果,（,4,）如果,kN,，令,k=k+1,，,GOTO,（,2,）,如果,k=N,，则检验 对所有训练样本是否都正确分类，是则结束，否则，令,k=1,，,GOTO,（,2,）,感知器算法,(,批量调整版本,),begin initialize, , k,0,do,k,k+1,until,return a,end,例,有两类模式的训练样本：,1,：, (0,0), (0,1) ,2,：, (1,0), (1,1) ,用感知器算法求取判别函数，将两类样本分开。,解：,(1),训练样本分量增广化及符号规范化：,(2),给增广权矢量赋任意初值 ，取增量,=1,，,68,例题,:,已知训练样本,(0,0),T,1,，,(1,1),T,2,，,(-1,1),T,3,试求解向量,w,1,、,w,2,和,w,3,。,（,2,）运用感知器训练算法。置,k=1,，增量,=1,，赋初值：,w,1,=(0,0,0),T,w,2,=(0,0,0),T,w,3,=(0,0,0),T,进行迭代运算：,解,:,（,1,）训练样本分量增广化。将训练样本变成增广训练模式：,x,1,=(0,0,1),T,x,2,=(1,1,1),T,x,3,=(-1,1,1),T,这里的下标恰是所属类别，各类样本不需符号规范化。,69,例题,:,已知训练样本,(0,0),T,1,，,(1,1),T,2,，,(-1,1),T,3,试求解向量,w,1,、,w,2,和,w,3,。,k=1,x,k,=,x,1,1,因为,d,1,(,x,1,)=d,2,(,x,1,)=0,，,d,1,(,x,1,)=d,3,(,x,1,)=0,，,错分，所以,:,w,1,(2)=,w,1,(1)+,x,1,=(0,0,1),T,w,2,(2)=,w,2,(1)-,x,1,=(0,0,-1),T,w,3,(2)=,w,3,(1)-,x,1,=(0,0,-1),T,k=2,x,k,=x,2,2,因为,d,2,(x,2,)=-1d,1,(x,2,)=1,，,d,2,(x,2,)=d,3,(x,2,)=-1,，错分，,所以,w,1,(3)=w,1,(2)- x,2,=(-1,-1, 0),T,w,2,(3)=w,2,(2)+ x,2,=( 1, 1, 0),T,w,3,(3)=w,3,(2)- x,2,=(-1,-1,-2),T,70,例题,:,已知训练样本,(0,0),T,1,，,(1,1),T,2,，,(-1,1),T,3,试求解向量,w,1,、,w,2,和,w,3,。,k=3,x,k,=x,3,3,因为,d,3,(x,3,)=-2d,1,(x,2,)=-2,，,d,2,(x,2,)=0d,3,(x,2,)=-4,，正确，,所以,w,1,(6)=w,1,(5)=( 0,-2, 0),T,w,2,(6)=w,2,(5)=( 2, 0,-2),T,w,3,(6)=w,3,(5)=(-2, 0,-2),T,k=6,x,k,=x,3,3,因为,d,3,(x,3,)=0d,1,(x,3,)=-2,，,d,3,(x,3,)=0d,2,(x,3,)=-4,，正确，,所以,w,1,(7)=w,1,(6)=( 0,-2, 0),T,w,2,(7)=w,2,(6)=( 2, 0,-2),T,w,3,(7)=w,3,(6)=(-2, 0,-2),T,72,例题,:,已知训练样本,(0,0),T,1,，,(1,1),T,2,，,(-1,1),T,3,试求解向量,w,1,、,w,2,和,w,3,。,k=7,x,k,=x,1,1,因为,d,1,(x,1,)=0d,2,(x,1,)=-2,，,d,1,(x,1,)=0d,3,(x,1,)=-2,，正确，,三个权矢量不再变化，因此可以确定所有训练样本均已被正确分类，,由此得到三个解矢量：,w,1,*,=,w,1,(5),，,w,2,*,=,w,2,(5),，,w,3,*,=,w,3,(5),同时可得三个判别函数,:,d,1,(,x,) = -2,x,2,d,2,(,x,) = 2,x,1,-2,d,3,(,x,) = -2,x,1,-2,MATLAB,程序示例,gzhq.m,2024/10/1,73,二次准则函数及其解法,问题：,一次准则函数及其算法（如感知器算法）只适用于线性可分的情况，如果是线性不可分的，分类过程将不收敛,?,能否找到一种算法，使之能够测试出模式样本集是否线性可分，并且对线性不可分的情况也能给出,“,次最优,”,的解？,如果训练模式是线性不可分,不等式组是,不一致,的，不等式组没解。此时，,目标,最少的训练模式被错分。,（一）最小错分模式数目准则,对线性不可分样本集，求一解矢量使得错分的模式数目最少。,对于两类问题，设,n+1,维增广训练模式,已符号规范化,。,如果训练模式是线性可分的，则存在权矢量 使不等式组,成立。,式中 是 矩阵。,将上面的不等式组写成矩阵方程形式，并引入,N,维余量矢量 ，于是不等式方程组变为,（二）最小方差准则及,W-H,算法,针对方程组,构造方差准则函数,对于,此时的,而对于,此时的 。如果方程组有唯一解,说,明训练模式集是线性可分的,如果方程组无解,极小点值是最小二乘解。一般情况下使 极小等价于误分模式数目最少,。,伪逆法,求 对 的梯度并令其为零，有,可得,(3-6-12),当,(,X,X,),-1,存在时，,X,+,=(,X,X,),-1,X,称为,X,的伪逆,(,也称广义逆或,M-P,逆,),， 称为 的伪逆解。,X,X,是,(,n,+1),(,n,+1),矩阵，一般是非奇异的。,当,(,X,X,),-1,不存在时，可用广义逆法解,这里,(,X,X,),+,为,X,X,的广义逆矩阵。,求解最佳权矢量的方法：,梯度法,由前述知， 的梯度为,梯度下降算法迭代公式为,Step1.,任取,Step2.,(3-6-13),可以证明，当 为任意正的常数，则该算法使权矢量序列 收敛于,;,满足 ， 也称为,MSE,解。,此算法的两个性质,:,1.,当 时,MSE,解 等价于,Fisher,解。,2.,令,在样本数 时,MSE,解以最小均方误差逼近贝叶斯判决函数,Step1.,任取,Step2.,此算法通常称为,W,H(Widrow,Hoff),算法,仿前采用单样本修正法，则式,(3-6-13),可以修改为,为了减少计算量和存储量，由于,(3-6-14),2024/10/1,81,LMS.M,MSE.M,2024/10/1,82,83,H-K,算法,求解最佳权矢量的方法,H-K,算法的迭代公式为：,其中,84,85,H-K,算法步骤,Step2.,置初值,Step1.,将训练样本符号规范化，得,X,求伪逆,Step3.,计算,86,H-K,算法步骤,Step6.,k=k+1,; goto Step3;,Step5.,87,88,示例代码,HK.M,2024/10/1,89,2024/10/1,90,广义线性判决函数,2024/10/1,91,2024/10/1,92,2024/10/1,93,3.4,广义线性判别函数,一维样本空间,显然没有一个线性判别函数,3.4,广义线性判别函数,设,n,维模式特征矢量集 在特征空间 中是非线性可分的，对模式 作非线性变换：,3.4,广义线性判别函数,97,1,98,的项数为：,99,的维数,令,其中,3.5,势函数法,-,概念,3.5,势函数法,-,概念,3.5,势函数法,-,算法,3.5,势函数法,-,算法,例：已知如图,(3-12-1),所示两类训练样本： 试用势函数法进行分类器训练。,解：选用第二类势函数，令,=1,，在二维情况下，,为积累位势函数,),(,exp,),),0,(,),0,(,(,exp,),(,),(,1,2,2,2,1,2,2,2,1,1,1,1,1,x,x,x,x,x,x,K,x,K,x,j,+,-,=,-,+,-,-,=,=,=,r,r,r,r,w,令,判别界面,判别界面,x,2,=x,1,-1,x,2,=1-x,1,2024/10/1,109,程序：,