资源描述
,模式识别第四章线性判别函数（2）,信息工程学院袁立,回顾：,Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。,4.3感知准则函数,感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。,4.3.1几个基本概念,设样本d维特征空间中描述，则两类别问题中线性决策面的一般形式可表示成：,其中,作特殊映射,1.线性可分性,增广样本向量y与增广权向量a,线性判别函数的齐次简化：,线性判别函数的齐次简化使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的。,广义线性判别函数,答：一个过原点的平面，方程为ay1+by2+cy3=0(B)。(A)式与(B)式形式上略有不同，但当y3=1时两者就一样了。也就是说(B)式表示的平面与y3=1子空间(一平面)的交线就是(A)式中表示的直线。,思考一下，如果在两维空间存在一条不过原点的直线，ax1+bx2+c=0(A)，采用增广向量形式：,那么，它在增加一维的三维空间中，aTY=0表示的是什么呢？,线性可分性,练习：设五维空间的线性方程为,试求出其权向量与样本向量点积的表达式,中的W，X以及增广权向量与增广样本向量形式,中的a与Y。,解：,线性可分性,判别准则是：,反过来说，如果存在一个权向量，使得对于任何都有，而对任何，都有，则称这组样本集为线性可分的；否则称样本集为线性不可分的。,线性判别函数的齐次简化：,线性可分性,2.样本的规范化根据线性可分的定义，如果样本集是线性可分的，则必存在某个或某些权向量，使得如果将第二类样本都取其反向向量，则有,4.3.1几个基本概念,上述过程称为样本的规范化，叫做规范化增广样本向量。在后面我们仍用y来表示。,也就是说不管样本原来的类别标识，只要找到一个对全部样本都满足的权向量即可。,3.解向量和解区在线性可分的情况下，满足，i=1,2,N的权向量称为解向量，记为。由满足上述条件的解向量组成的区域，就称作解区。一般来说，对解区要加以限制，目的是使解向量更可靠，越靠近解区中间的解向量，越能对新的样本正确分类。引入余量b0，并寻找满足的解向量，显然满足，位于原解区之中。,4.3.1几个基本概念,感知准则函数方法是一种利用错分类对现决策权向量进行修正直至收敛的方法。这种方法只对线性可分情况适用。在给定一个规范化增广样本集的条件下，对于任何一个增广权向量，可以计算。如果该向量是一个能将此样本集正确分类的增广权向量，则应有而对可导致错分类的增广权向量，则必有若干个yi,使，令被错分类的规范化增广样本组成的集合用yk表示，错分时，所以定义一准则函数,4.3.2感知准则函数,能将该样本集正确分类的增广权向量，使达到极小值。因此确定向量的问题变为对求极小值的问题，这个准则函数就是感知准则函数。,求准则函数的极小值问题，可以采用迭代法进行。一个常用的方法是梯度下降算法，即对第k次迭代值，求其梯度向量，并令迭代向量沿此负梯度向量方向修正，可以以较快的速度到达准则函数的极小值。,4.3.2感知准则函数,准则函数的极小值：梯度下降算法,感知准则函数利用梯度下降算法求增广权向量的做法，可简单叙述为：任意给定一向量初始值，第k+1次迭代时的权向量等于第k次的权向量加上被错分类的所有样本之和与的乘积。,梯度下降算法求增广权向量,梯度下降算法的迭代公式为：,4.3.2感知准则函数,迭代修正过程：,由于所有被a(k)错分类的样本必然都在以a(k)为法线的超平面的负侧，因而它们的总和也必然处于该侧。a(k+1)修正时，就会使a(k+1)向错分类向量和趋近，有可能使这些错分类向量之和穿过超平面，或至少朝有利方向变动。,4.3.2感知准则函数,4.3.2感知准则函数,设a(1)=0，k=1。因为aTy1=0,被错分则a(2)y1，则y3被错分类，故a(3)y1+y3，则y1又被错分类，故a(4)a(3)+y1，则y3被错分类，故a(5)a(4)+y3，则y1被错分类，故a(6)a(5)+y1,现在我们把样本集看做一个不断重复出现的序列而逐个加以考虑。对于任意权向量a(k)，如果他把某个样本分错了，则对a(k)做一次修正。这种方法称为单样本修正法。由于仅在发现分错类时才修正a(k)，所以只注意那些被分错类的样本就行了。因此经过简化后梯度下降算法可写成：,我们反复地将y1到y3依次送到分类器检验，并在发生错分类时对向量a(k)作出修正。一直迭代直至该解向量进入解区内。,例1：,4.3感知准则函数,v,例2：有两类样本1=（x1,x2）=(1,0,1)T,(0,1,1)T2=（x3,x4）=(1,1,0)T,(0,1,0)T试用感知准则函数法求判别函数？,解：先求四个样本的规范化增广样本向量y1=(1,0,1,1)Ty2=(0,1,1,1)Ty3=-(1,1,0,1)Ty4=-(0,1,0,1)T假设初始权向量a1=(1,1,1,1)Tk=1第一次迭代：,4.3感知准则函数,a1Ty1=(1,1,1,1)(1,0,1,1)T=30所以不修正a1Ty2=(1,1,1,1)(0,1,1,1)T=30所以不修正a1Ty3=-(1,1,1,1)(1,1,0,1)T=-30而g2(x)0，g3(x)0，g2(x)g3(x)。假设判别函数为：则判别边界为：,4.4多类问题最大值判决,结论：不确定区间没有了，所以这种是最好情况。,用上列方程组作图如下：,4.4多类问题最大值判决,问假设未知模式x=(x1,x2)T=(1,1)T，则x属于那一类。把它代入判别函数：得判别函数为：因为所以模式x=(1,1)T属于类。,4.4多类问题最大值判决,4.5利用感知准则实现多类判别,第四章线性判别函数,步骤：(1)增广样本，但是不用进行规范化；（注意和两分类问题的区别）(2)每一类设定一个初始权向量(3)对第i类的样本yj，若,则,(4)对所有样本重复（3），直到满足,例：,解：,4.5利用感知准则实现多类判别,4.5利用感知准则实现多类判别,4.5利用感知准则实现多类判别,4.5利用感知准则实现多类判别,4.5利用感知准则实现多类判别,4.6本章小结,线性判别函数的基本概念Fisher线性判别感知准则函数多类问题,
展开阅读全文