感知机和多分类.pptx

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