模式识别课件)(第4章NO2)(感知器判别函数)

1、4.3 感知准则函数一一.几个基本概念几个基本概念 1. 线性可分性线性可分性 含义：含义：若存在一个权向量权向量a(即直线)，能将样本集按类分开将样本集按类分开，则称之为是线性可分的。 定义：定义：设有d维维N个样本的样本集个样本的样本集X1,X2Xn，且分别来自1和和2类类。其线性判别函数线性判别函数为： WTXi+W0其中其中 WT=W1,Wd， XiT=Xi1,Xid (i=1,N) 则其齐次式为：则其齐次式为：aTYi其中其中 aT=W0,W1,Wd=W0 W 增广权向量增广权向量 YiT=1,xi1,xid=1 XiT 增广样本向量增广样本向量即即Yi为为 维维(d+1维维)增广样

2、本向量。增广样本向量。d如果存在一个如果存在一个权向量权向量aT，满足下式：满足下式： aTY 0 则则Y 1类类 aTY 0 则则Yi1；若若aTYj 0 样本的规范化式样本的规范化式其中 Yi Yi 1 Yn= -Yj Yj 2 yn代表全部样本全部样本，其称为规范化增广样本向量规范化增广样本向量。现在的问题现在的问题：只要找到满足aTYn 0 的权向量aT就行(n=1,N).4. 解向量和解区解向量和解区(1) 解向量：解向量：满足aTYn0 (n=1,N)的权向量的权向量a称之为解向量。(2) 权空间：权空间：由权向量组成的空间权向量组成的空间。 权向量a可视为可视为权空间中的一点一点

3、，且每个样本每个样本Yn对对a的可能位置都起到作用，即要求aTYn0。(3) 权空间原点的超平面：权空间原点的超平面：是由aTYn=0确定的超平面确定的超平面 n. 注意：注意： n的法向量为法向量为Yn。 N个样本将产生N个超平面个超平面。HH(4) 解向量如果存在解向量如果存在，则必在必在 n的正侧的正侧（因为只有正侧时才满正侧时才满足足aTYn0）。(5) 解区：解区：由于每个超平面每个超平面把权空间分为两个半空间两个半空间，所以解向量如果存在，必在必在N个正半空间的交迭区个正半空间的交迭区，而且该区中的任该区中的任意向量都是解向量意向量都是解向量。因此解向量往往不只一个解向量往往不只一

4、个，而是由无穷由无穷多个解向量组成的区域多个解向量组成的区域（该区称为解区）。对于二维问题，可看下图（书图4.5）。H解向量解区分界面解区解向量分界面：第一类样本：第二类样本（a）未规范化（b）规范化。5. 对解区的限制对解区的限制 目的是目的是：使解向量更可靠。：使解向量更可靠。 一般，越靠近越靠近解区中间解区中间的解向量，越能正确分类。的解向量，越能正确分类。 所以，引入余量引入余量 b 0 。 使使 aTYnb 的解向量即为的解向量即为限制后的解向量限制后的解向量。 而而 aTYnb0 所产生的所产生的新解区新解区位于原解区之中。位于原解区之中。 b/YnaTYnbaTYn0二二. 感知

5、准则函数及其梯度下降算法感知准则函数及其梯度下降算法1. 问题描述问题描述 设有设有一组一组d维样本维样本Y1,YN，其中，其中 Yn是是规范化增广样本向量规范化增广样本向量。 现在的问题是：现在的问题是：找一个解向量找一个解向量a*，使得，使得 aTYn0 ,(n=1,2,N) 为了解此线性不等式组，需构造一个需构造一个准则函数准则函数： 式中 是是被（增广）权向量被（增广）权向量a错分类错分类的样本集合。的样本集合。(因为因为当样本Y被错分类时，有被错分类时，有aTY 0 或 -aTY 0，此时，此时 )kkPJYT)Ya(a)(0a)(PJ感知准则函数感知准则函数说明：说明： 是解权向量

6、a的函数的函数。 当且仅当 为空集空集时，即 时， 达到极小值。 即 或者说，当对于某个向量当对于某个向量a， 达到极小值极小值(如如“”)的话，的话，a 就是解权向量就是解权向量，这时样本被错分类最少样本被错分类最少(或或没有没有)，这个a就是要找的解权向量解权向量a*。 几何上几何上，感知准则函数正比于正比于被错分样本被错分样本到决策面的距决策面的距离之和离之和。 这时，就可用最优化方法最优化方法寻找使达到极小值的解权向量a*，为此，可采用梯度下降法求解梯度下降法求解。 k0a)(mina)(*PPJJka)(PJa)(PJa)(PJa)(PJ 函数函数 在某点某点ak的梯度的梯度 是一个

7、向量向量，它的方向与过点ak的等量面 的法线方向重合法线方向重合，指向 增加的一方增加的一方，是准则函数变化率最大的方向准则函数变化率最大的方向；反之，负梯负梯度的方向则是度的方向则是 减少得减少得最快最快的方向的方向。 所以，在求求 的极小值的极小值时，沿负梯度方向负梯度方向搜索有可能最快地找到极小值最快地找到极小值。（梯度下降法的基本思想）。a)(PJa)(PJ)a (kPJC)a (kPJa)(PJ)a (kPJ 梯度下降法的实现梯度下降法的实现 先任意给定一个初始权向量任意给定一个初始权向量a(1)，计算a(1)上的梯度上的梯度 JP ( a(1) ) ，从a(1)出发出发在最陡方向（

8、即负梯度方向）最陡方向（即负梯度方向）上移动一个距离以得到下一个权向量值移动一个距离以得到下一个权向量值a(2)，反复下去，经过有有限步循环限步循环，就可找到解向量解向量a*，其迭代算法迭代算法如下：式中 是一个正的比例因子正的比例因子，称为步长或增量步长或增量。a(k)(-a(k)1)a(kPkJk. 求使求使JP(a)达到极小值的解权向量达到极小值的解权向量a* 因为 JP(a)的第第k个梯度分量个梯度分量是 现在将将JP(a)式对式对a求梯度求梯度，这是一个标量函数对向量的求导一个标量函数对向量的求导，得如下式 将上式代入迭代式，可得 式中 是当第当第k步迭代步迭代，用a(k)来分类时被

9、误分类的样本集来分类时被误分类的样本集。kkYPP(-Y)a(k)a(J(a)JkYYa(k)1)a(kka(k) )a(JP解释：解释：这种寻找解权向量的梯度下降法可描述为： 将被被a(k)误分类的样本之和误分类的样本之和并与与某个系数系数 的乘积的乘积之后，再加上加上第第k次的权向量次的权向量a(k) ，即为第（第（k+1）次的权向量）次的权向量。可证得，对于线性可分的样本集，经过有限步线性可分的样本集，经过有限步，一定可找到一个解向量一个解向量a*，即算法在有限步内收敛有限步内收敛，其收敛速度取决于收敛速度取决于初始权向量初始权向量a(1)和系数系数 。kk3. 感知准则函数梯度下降算法

10、感知准则函数梯度下降算法感知准则函数梯度下降算法的步骤如下：(1) 给定初始权向量给定初始权向量a(1)和步长步长 ；(2) 找出被权向量找出被权向量错分类的样本，错分类的样本，转第转第(3)步步；如果无错分类如果无错分类样本，算法结束；样本，算法结束；(3) 按下面的迭代公式按下面的迭代公式求新的权向量求新的权向量然后转第然后转第(2)步。步。kkYYa(k)1)a(kk例如：例如：设a(1)=0，=1，有3个样本在三维下的样本序列为：k1yy个错分样本。步迭代时，有）第者为错分样本。注：）带kkyyyyyyyyyyyyyyy 32153214321332123211 第第1步迭代时：步迭代

11、时： a(1)=0, a(1)Tyi=0 (i=1,2,3) 故故 a(2) = a(1) y1+y2+y3第第2步迭代时：步迭代时：即用a(2)分类时，有a(2)Ty30故 a(3) a(2)y3第第3步时：步时：aT(3) y10a(4)=a(3)+ y1第第4步时：步时：aT(4) y30a(5)=a(4)+ y3第第5步时：步时：aT(5) yi0 (i=1,2,3) 故故 a(5)为解向量为解向量 。y1y3a(2)=y1+y2+y3a(4)y2a(3)a(5) a(1)4.4 最小错分样本数准则最小错分样本数准则由于感知准则函数及其梯度下降算法感知准则函数及其梯度下降算法只适用于线

12、性可分情况线性可分情况，而对于线性不可分情况线性不可分情况迭代过程将无休止，即算法不收敛算法不收敛。由于实际中，常无法事先知道样本集是否线性可分常无法事先知道样本集是否线性可分，所以，希望找到一种既适用于线性可分，适用于线性可分，又适用于线性不可分适用于线性不可分的方法，此方法对线性可分问题对线性可分问题，可得到一个如感知准则函数那样的解向如感知准则函数那样的解向量量a*，使得对两类样本集进行正确分类类；对两类样本集进行正确分类类；而对于线性不可分问对于线性不可分问题题，则得到一个使两类样本集使两类样本集错分数目最少错分数目最少的权向量的权向量a*。这就是所谓的最小错分样本数准则最小错分样本数

13、准则。 一一. 解线性不等式组的共轭梯度法解线性不等式组的共轭梯度法对于2类类问题。设 (=d+1)维维的N个增广样本向量增广样本向量Y=y1,yn已符号规范化符号规范化，则线性判别函数线性判别函数可写为：g(X)=aTY。如果样本集是线性可分的，则存在权向量线性可分的，则存在权向量a，使得aTYn 0 (n=1,2,N) 成立，成立，即不等式组是一致的不等式组是一致的，有解有解。说明说明yn能被正确分类能被正确分类。如果样本集是非线性可分非线性可分的，表明不存在不存在a使所有的样本被使所有的样本被正确分类正确分类，即无论任何的无论任何的a都有某些样本被错分都有某些样本被错分。这时上述不等不等

14、式组不能成立式组不能成立，即不等式组是不一致的。不等式组无解不等式组无解。这时必必有某些样本被错分类有某些样本被错分类。因此，我们的目标应是所求得的权向量目标应是所求得的权向量a使尽可能多的不等式被满足使尽可能多的不等式被满足，即使最少的样本被错分使最少的样本被错分。d将上述不等式组写成矩阵形式矩阵形式，另外为使解可靠为使解可靠，引入引入N维维余量向量余量向量 b 0，则不等式组不等式组可写成： Ya b 0其中,Y是N 符号规范化增广样本矩阵符号规范化增广样本矩阵,a是是 1权向量权向量,bN1。针对我们的目标，由上式可定义如下准则函数准则函数（是一个分段分段二次函数二次函数）： Jq1(a

15、) =(Ya - b) -Ya b 2 min说明：说明： 如果如果 Ya b，则 (Ya - b) 与Ya - b的各分量分别对应分别对应相等相等，则Jq1(a) = 0。 如果有某些某些yi分量不满足分量不满足aTyibi，则分量( aTyi-bi ) 和 aTyi - bi异号异号，则Jq1(a) 0。dd显然，不满足不满足不等式的（增广）样本样本yi数目越少数目越少，则Jq1(a)就越小就越小。所以，使使Jq1(a)取最小值时的取最小值时的a为最优解为最优解a*。并且在样本集是线性可分时线性可分时，即不等式组一致条件不等式组一致条件下，必必有有Jq1(a*) = 0，即表明用用a*构造

16、的判别函数对所有样本均能正确构造的判别函数对所有样本均能正确分类分类。而在样本集是线性不可分时线性不可分时，即不等式组不一致条件不等式组不一致条件下，有有Jq1(a*) 0，但a*使误分样本数最少使误分样本数最少，我们称Jq1(a)为最小错为最小错分样本数准则分样本数准则。h 共轭梯度法简介：共轭梯度法简介：共轭梯度法是一种改进搜索方向改进搜索方向的方法，它是为快速迭代快速迭代而形成的一种方法，它要求迭代过程应沿梯度的共轭方向进行迭代过程应沿梯度的共轭方向进行搜索搜索，从而得出序列解序列解的方法。具体的说，就是把前一点的梯把前一点的梯度乘以适当的系数度乘以适当的系数v，加到该点的梯度加到该点的

17、梯度上，得到新的搜索方向新的搜索方向。而“共轭共轭”是对一组向量一组向量而言。 例如例如，设X与Y是两个d维非维非0向量向量，而Bdd是一个对称正定矩对称正定矩阵阵，如果有 XTBY 0 则称X和和Y关于关于B互为共轭互为共轭。显然，如果如果B=I(单位阵单位阵)，则，则XTBY=0，就意味着对于I互为共互为共轭的轭的X与与Y是正交的是正交的。而对称正定矩阵对称正定矩阵B相应于不同特征值的两个特征向量不同特征值的两个特征向量X与与Y对于B是互为共轭的是互为共轭的。另若 是相对Y的特征值的特征值， 则有： XTBY = XT Y = XTY = 0共轭梯度法就是以以Ed空间中的一组对于空间中的一

18、组对于B互为共轭的向量作互为共轭的向量作为一维搜索方向为一维搜索方向，使二次正定函数二次正定函数 f(X) = b0+ bTX + XTBX 达到极小值的最优化算法达到极小值的最优化算法，用共轭梯度法可求得共轭梯度法可求得序列序列X0,X1,X*，使得 f(X0) f(X1) f(X*)对于二次正定函数f(X)，最多用最多用d步，就可收敛于步，就可收敛于f(X)的极值解的极值解X*.4.5 最小平方误差准则函数最小平方误差准则函数前述法是对于所有样本所有样本都能满足不等式组不等式组aTYi0(i=1,2N) ,而建立的二次准则函数二次准则函数，从而使错分样本数最少错分样本数最少。最小平方误差准

19、则函数最小平方误差准则函数方法，是一个基于全体样本基于全体样本的准则函数，它要求满足等式满足等式 aTYibi( i=1,N)(bi0)，这样就可用解一组线解一组线性方程组性方程组的问题来替代原来的解一组线性不等式的问题。也就是说，适当选择适当选择b (0)，可以针对等式方程组针对等式方程组 Ya = b(式中Y是N 矩阵，即由规范化增广样本向量Yi(i=1,2,N)组成的；a是 1的增广权向量增广权向量；bN1) 建立二次准则函数建立二次准则函数，然后运用最优化技术求解权向量最优化技术求解权向量a。 ddd如果Y是非奇异矩阵是非奇异矩阵，则可得解得解a=Y-1b，但这在大多数情况下是不可能的

20、，因为一般情况，样本数样本数N总是大于维数总是大于维数(即N )，因此，Y是长方阵是长方阵(即行数列数)，也就是说，方程式数方程式数大于未知数的数目大于未知数的数目，这是一个矛盾方程组矛盾方程组，对其通常没有精确没有精确解存在解存在。为此，只可能找到一个解权向量只可能找到一个解权向量a，它使Ya与b之间的误差极小化。因此，可定义误差向量定义误差向量为： e=Ya-b 则求求a为最优的方法就是使为最优的方法就是使e为最小为最小。 所以，定义平方误差准则函数定义平方误差准则函数Js(a)为如下： Js(a) =e2=Ya-b2 = (aTYn- bn)2 min即求找一个使求找一个使Js(a)极小

21、化的极小化的a作为问题的解作为问题的解， 这就是矛盾方程组的最小二乘近似解最小二乘近似解，亦称 MSE解解。ddNn 1显然：显然：若若aTYnbn（n=1,2,N）,则此时 Js(a)=0；若存在某些存在某些Yn使使aTYnbn，则 Js(a)0。而当b给定后给定后，可采用最优化技术搜索搜索Js(a)极小值点以求解等式极小值点以求解等式方程组方程组Ya=b。 如果方程组有唯一解，极小值点即是该解有唯一解，极小值点即是该解。说明样本集是样本集是线性可分的线性可分的； 如果方程组无解，极小值点是最小二乘解无解，极小值点是最小二乘解。而使使Js(a)极小极小等价于误分样本数最少等价于误分样本数最少

22、。一一. 采用伪逆法求采用伪逆法求MSE解解 对Js(a)求导求导/梯度并令其为零梯度并令其为零 aJs(a) = 2(aTYn - bn) Yn = 2YT(Ya - b) = 0 则得： YTYa = YTb 上式即为准则函数极小化的必要条件准则函数极小化的必要条件。 (式中YTY是一个是一个 矩阵矩阵)。Nn 1dd若其为若其为非奇异非奇异(即即(YTY)-1)存在存在，则可得到a的唯一解的唯一解(用用a*表示表示)。 a* = (YTY)-1YTb =Y+b式中 Y+=(YTY)-1YT 称为Y的伪逆的伪逆（亦称广义逆广义逆或M-P逆逆）。而 a*=Y+b 称为a的伪逆解的伪逆解（即M

23、SE解解）。 当(YTY)-1不存在不存在时，可用伪逆法解伪逆法解的： a*= (YTY)+YTb 式中(YTY)+为为YTY的伪逆阵的伪逆阵。由于求伪逆计算量较大，误差也较大求伪逆计算量较大，误差也较大，所以这只在解析上可行解析上可行。伪逆性质：伪逆性质： 当 Y为非奇异方阵非奇异方阵时，Y的伪逆和它的逆相等的伪逆和它的逆相等。 Y+Y = I 但一般一般 YY+ I二二. 采用梯度法求采用梯度法求MSE解解Js(a) 的梯度的梯度为： aJs(a)= 2YT(Ya - b)这样可得梯度下降算法梯度下降算法为： 任意给定初始权向量任意给定初始权向量a(1)； 如果第如果第k步不能满足：步不能

24、满足：YT(Ya-b) = 0 则按下式求第（第（k+1）步的权向量）步的权向量a(k+1) a(k+1) = a(k) - YT(Ya(k) - b)可以证明，如果选择如果选择 （ 为任意正常数）为任意正常数）则该算法使权向量序列权向量序列a(1), a(2),，收敛于满足方程Js(a)=0的权向量的权向量a*（即（即MSE解）解）。kk11k而且该方法，不论不论YTY是否为奇异矩阵是否为奇异矩阵，总能产生一个解总能产生一个解（即得有用的权向量得有用的权向量）a*，且该算法该算法只需计算只需计算 方阵(YTY),这比计算比计算 N矩阵矩阵(YTY)-1YT的计算量要小的多的计算量要小的多。为

25、了进一步减少进一步减少计算量计算量和和存储量存储量，由于 YT(Ya - b) = (aTYk - bk) Yk 采用类似于“感知准则函数”中的单样本修正法单样本修正法，将梯度下降算梯度下降算法修改为法修改为： a(1) 任意给定初值 a(k+1) = a(k) + (bk - aT(k) Yk) Yk这称为W-H(Widrow-Hoff)算法算法。kNk 1ddd说明：说明：不论用伪逆法伪逆法还是梯度法梯度法所求得的a*都依赖于都依赖于b，当b取某些特殊值时取某些特殊值时，MSE解将具有一些特殊的性质特殊的性质。(1) 设N为总的样本数，为总的样本数，N1和和N2分别为分别为1和和2类的样本数类的样本数，a*1为Fisher准则函数取最大值时的解准则函数取最大值时的解。当 时MSE解解a*等价于等价于Fisher 解解。即TNNNNNNNNb),.,.,(2211NmNmNmXNmimXmXSSSSmWmwmmSwiiWXiiWXTiiiWTWT221121*T10211*1T0* 1 )2,1( )( a )(a W:) W(a 式中 (2) 令 b=(1,1,1)T（N个1），当样本数样本数N时，MSE解解以最小均方误差逼近以最小均方误