第2章-线性判别函数法ppt课件.ppt

《第2章-线性判别函数法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章-线性判别函数法ppt课件.ppt（114页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 判别函数及几何分类法判别函数及几何分类法2.1 判别函数判别函数2.2 线性判别函数线性判别函数2.3 广义线性判别函数广义线性判别函数2.4 线性判别函数的几何性质线性判别函数的几何性质2.5 感知器算法感知器算法2.6 梯度法梯度法2.7 最小平方误差算法最小平方误差算法2.8 非线性判别函数非线性判别函数2.1 判别函数判别函数聚类分析法（第6章）判决函数法几何分类法确定性事件分类（第2章）概率分类法随机事件分类（第3章）线性判决函数法统 计 决 策 方 法非线性判决函数法复习与引申：复习与引申：模式识别统计若分属于1，2的两类模式可用一方程d(X) =0来划分，那么称d(X

2、) 为判别函数，或称判决函数、决策函数。2.1 判别函数判别函数(discriminant function) 直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于1，2两类的模式可用一直线方程 d(X)=0来划分。0)(32211wxwxwd X21,xx为坐标变量，321,www为方程参数。式中：图2.2 两类二维模式的分布1判别函数的定义判别函数的定义若 ，则若 ，则 类；若 ，则 类；0)(Xd1X0)(Xd2X0)(Xd21XX或 或拒绝将某一未知模式 X 代入：维数=3时：判别边界为一平面。维数3时：判别边界为一超平面。32211)(wxwxwd

3、X d(X) 表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。 判别界面的正负侧，是在训练判别函数的权值时确定的。2判别函数正负值的确定判别函数正负值的确定图2.3 判别函数正负的确定1）判决函数d(X)的几何性质。它可以是线性的或非线性的函 数，维数在特征提取时已经确定。如：已知三维线性分类 判决函数的性质就确定了判决函数 的形式：4332211)(wxwxwxwdX3. 确定判别函数的两个因素确定判别函数的两个因素例：非线性判决函数2）判决函数d(X)的系数。用所给的模式样本确定。2.2 线性判别函数线性判别函数2.2.1 线性判别函数的一般形式线性判别函数的一般形式将二

4、维模式推广到n维，线性判别函数的一般形式为：T1 122nn00 dw xw xw xwwXW X (2-2)T21,.,nxxxX式中：1 122nn012T120 11nndw xw xw xwxxwwwwxL LMXW XT120,.,nwwwwWT211 ,.,nxxxX增广向量的形式：式中：为增广权向量，为增广模式向量。T12,.,nw wwW权向量2.2.2 线性判别函数的性质线性判别函数的性质21T, 0, 0)(XXXWX若若d1. 两类情况d(X) = 0：不可判别情况，可以或拒绝或21XX） 对M个线性可分模式类，1， 2， M，有三种划分方式：2. 多类情况 ii两分法j

5、i两分法ji两分法特例ii两分法(1)多类情况1： 用线性判别函数将属于i类的模式与其余不属于i类的模式分开。将某个待分类模式 X 分别代入 M 个类的d (X)中，若只有di(X)0，其他d(X)均0的条件超过一个，或全部的di(X)dj(X)就相当于多类情况2中的dij(X) 0。ji两分法特例(3)多类情况3： 因此对具有判别函数 Midii, 1,)(TXWX的M类情况，判别函数性质为： ijiMjiijddXXX若, 2 , 1,;,)(或： ikiMkddXXX若, 1,max)( 识别分类时： 判别界面需要做差值。对i类，应满足： di其他所有dj2313dddd0122x1x

6、0)(21-XdXd- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd3 除边界区外，没有不确定区域。特点： 是第二种情况的特例。由于dij(X)= di (X) dj(X) ，若在第三种情况下可分，则在第二种情况下也可分，但反过来不一定。2313dddd0122x1x 0)(21-XdXd- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd3 把 M 类情况分成了(M -1)个两类问题。并且 类的判别界面全部与 类的判别界面相邻（向无穷远处延伸的区域除外）。iijj特别的定义23212211)(1)()(xdxxdxxd-XXX例例2.5

7、 一个三类模式（M=3）分类器，其判决函数为： 试判断X0=1,1T属于哪一类，且分别给出三类的判决界面。解： 2003020102030201)()()()(1)(1111)(011)(-XXXXXXXXddddddd012)()(121-xddXX02)()(2131-xxddXX012)()(112-xddXX012)()(2132-xxddXX)()(1331XXdd-)()(2332XXdd-类的判决函数：1判决界面如图所示。类的判决函数：2类的判决函数：3- 0)(21-XdXd2313dddd0.5x2- 0)(31-XdXd 0)(32-XdXd3212dddd3121dddd

8、110.5123x1-O2x1x 0)(21-XXdd- 0)(31-XXdd 0)(32-XXdd例例2.6 已知判决界面的位置和正负侧，分析三类模式的分布 区域 。132(1) 明确概念：线性可分。 一旦线性判别函数的系数Wk被确定以后，这些函数就可以作为模式分类的基础。3. 小结小结(2) 分法的比较：jiii与 对于M类模式的分类， 两分法共需要M个判别函数，但 两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。 jiii原因： 一种类别模式的分布要比M-1类模式的分布更为聚集， 分法受到的限制条件少，故线性可分的可能

9、性大。jiii两分法 全部不属任何类 IR，可能 属于1或3 1230)(2Xd0)(3XdIR，可能 属于3或2 -0)(1Xd0, 0312ddd0, 0321ddd0, 0,321dddIR，可能属于1或2 0, 0213ddd2x1x若只有di(X)0，其他d(X)均 0时，原点在超平面的正侧；wn+1 Tik XW()=1+kW( )ickXW+( )kW( )0Tik XW若( )0Tik XW若（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。 分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换

10、。感知器算法是一种赏罚过程：感知器算法是一种赏罚过程：3. 收敛性收敛性收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。可以证明感知器算法是收敛的。收敛条件：模式类别线性可分。 例例2.8 已知两类训练样本解：所有样本写成增广向量形式； 进行规范化处理，属于2的样本乘以(1)。T11 , 0 , 0XT21 , 1 , 0XT31, 0 , 1 -XT41, 1, 1-X用感知器算法求出将模式分为两类的权向量解和判别函数。 :1T10,0X:2T21 ,0XT30, 1XT41 , 1X任取W(1)=0，取c=1，迭代过程为：第一轮： 0,1000

11、, 0 , 0) 1 (1TXWT11 , 0 , 0) 1 () 2(, 0XWW故1,1101 , 0 , 0)2(2TXWT1 , 0 , 0) 2() 3 (, 0WW故-1,1-01-1 , 0 , 0)3(3TXWT30 , 0 , 1-) 3 () 4(, 0XWW故1,1-1-1-0 , 0 , 1-)4(4TXWT0 , 0 , 1-) 4() 5 (, 0WW故有两个WT(k)Xi 0的情况（错判），进行第二轮迭代。T11T1 , 0 , 1-)5()6(,00)5(XWWXW故T2T1 , 0 , 1-(6)7(,01)6(WWXW故T33T0 , 0 , 2-)7()8

12、(,00)7(XWWXW故T4T0 , 0 , 2-)8()9(,02)8(WWXW故第二轮：T11T1 , 0 , 2-)9()10(,00)9(XWWXW故(10)11(,01)10(2TWWXW故)11()12(,01)11(3TWWXW故)12()13(,01)12(4TWWXW故第三轮：)13()14(,01)13(1TWWXW故(14)15(,01)14(2TWWXW故)15()16(,01)15(3TWWXW故)16()17(,01)16(4TWWXW故第四轮：T1 , 0 , 2-W该轮迭代的分类结果全部正确，故解向量1()21dx -X相应的判别函数为： 当c、W(1)取其他

13、值时，结果可能不一样，所以感知器算法的解不是单值的。判别界面d(X)=0如图示。采用多类情况3的方法时，应有：4. 感知器算法用于多类情况感知器算法用于多类情况Mj, 1= iX ,)(ijddjiXX若，则 Midi, 1,对于M类模式应存在M个判决函数：算法主要内容：M,21设有 M 种模式类别： Mjj, 1,1W设其权向量初值为： 第k次迭代时，一个属于i类的模式样本 X 被送入分类器，计算所有判别函数训练样本为增广向量形式，但不需要规范化处理不需要规范化处理。 分二种情况修改权向量： Mjkkdjj, 1,TXW 若第l个权向量使 ，则相应的权向量作调整，即： -lijkkckkck

14、kjjllii,111WWXWWXWW 可以证明：只要模式类在情况3判别函数时是可分的，则经过有限次迭代后算法收敛。， c为正的校正增量例例2.9 设有三个线性可分的模式类，三类的训练样本分别为 若 则权向量不变； Mjijkdkdji, 2 , 1;, Mjkkjj, 2 , 1,1WW( )( )kdkdli T33T22T111 , 11 , 10 , 0-XXX：；：；：现采用多类情况3的方式分类，试用感知器算法求出判别函数。 解：增广向量形式：T3T2T11,1, 1,1,1, 1,1 , 0 , 0-XXX注意，这里任一类的样本都不能乘以（1）。任取初始权向量T3210 , 0 ,

15、 0) 1 () 1 () 1 (WWW；c=1 第一次迭代： 0111T11XWd 0111T22XWd 0111T33XWd三个权向量都需要修改：11X 1121dd 1131dd，但且不成立，T1111 , 0 , 0) 1 ()2(XWWT1221, 0 , 0) 1 ()2(-XWWT1331, 0 , 0) 1 ()2(-XWW第二次迭代： 1222T11XWd 1222T22-XWd 1222T33-XWd22X 2212dd 2232dd，但且不成立，修改权向量：T2110 , 1, 1)2() 3(-XWWT2220 , 1 , 1)2() 3(XWWT2332, 1, 1)

16、2()3(-XWW第三次迭代： 修改为权向量。33X 3313dd 3323dd，但且不成立， 以上进行的一轮迭代运算中，三个样本都未正确分类，进行下一轮迭代。第四次迭代： 在第五、六、七迭代中，对所有三个样本都已正确分类。权向量的解：T11110 , 2, 0)5()6()7(-WWWWT22222, 0 , 2)5()6()7(-WWWWT33332, 0 , 2)5()6()7(-WWWW判别函数：212)(xd-X22)(12-xdX22)(13-xdX 设函数f (Y)是向量 的函数，则f (Y)的梯度定义为：2.6 梯度法梯度法T21,nyyyY T21,ddnyfyfyfffYY

17、Y梯度的方向方向是函数 f (Y) 在Y点增长最快的方向，梯度的模模是f (Y)在增长最快的方向上的增长率 (增长率最大值)。1. 梯度概念梯度概念 梯度向量的最重要性质之一：指出函数梯度向量的最重要性质之一：指出函数 f 在其自变量增加在其自变量增加时，增长最快的方向。时，增长最快的方向。2.6.1 梯度法基本原理梯度法基本原理显然：负梯度指出了最陡下降方向。梯度算法的依据。即：2. 梯度算法梯度算法 设两个线性可分的模式类1和2的样本共N个，2类样本乘(-1)。将两类样本分开的判决函数d(X)应满足： 梯度算法的目的仍然是求一个满足上述条件的权向量，主导思想是将联立不等式求解W的问题，转换

18、成求准则函数极小值的问题。Nidii, 2 , 10)(TXWXN个不等式 准则函数的选取原则： 具有唯一的最小值，并且这个最小值发生在W TXi0时。 用负梯度向量的值对权向量W进行修正，实现使准则函数达到极小值的目的。 基本思路： 定义一个对错误分类敏感的准则函数J(W, X)，在J的梯度方向上对权向量进行修改。一般关系表示成从W(k)导出W(k+1)：其中c是正的比例因子。 梯度法求解步骤： JckJckk-WWW)(1 kJckkWWWXWWW-,1（1）将样本写成规范化增广向量形式，选择准则函数，设置初始权向量W(1)，括号内为迭代次数k=1。 权向量修正为：)(,)(kiJkJWW

19、WXW )(1kJckk-WW迭代次数k加1，输入下一个训练样本，计算新的权向量，直至对全部训练样本完成一轮迭代。 （3）在一轮迭代中，如果有一个样本使 ，回到(2)进行下 一轮迭代。否则， W不再变化，算法收敛。0J（2）依次输入训练样本X。设第k次迭代时输入样本为Xi，此时 已有权向量W(k)，求 ：)(kJ例例2.10 选择准则函数 ， ，简单地考虑X为一维增广模式的情况X=1，此时W=w，两者均为标量，XWXWXWTT),(-JwwJ-),(XW错误分类时： 22,1-wwwwwJJXXWW0010TwwXW ckckk221-WWW， 对权向量校正。 Jckk-WW1正确分类时：00

20、10TwwXW0-wwwJ kckkWWW-01， 对权向量不做修正。说明： 随着权向量W向理想值接近，准则函数关于W的导数 ( )越来越趋近于零，这意味着准则函数J 越来越接近最小值。当 最终 时，J达到最小值，此时W不再改变，算法收敛。J0J 将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题。 kJckJckkWWWXWWWW-,1 c) 梯度算法是求解权向量的一般解法，算法的具体计算形式取决于准则函数J(W, X)的选择，J(W, X)的形式不同，得到的具体算法不同。a) b) c值的选择很重要，如c值太小，收敛太慢；但若太大，搜索又可能过头，甚至引起发散。2.6.2 固

21、定增量法固定增量法准则函数：求W(k)的递推公式：1. 求J的梯度?,WXWJJ方法：函数对向量求导=函数对向量的分量求导，即T1,nxfxffX该准则函数有唯一最小值“0”，且发生在 的时候。 0TXW设 ，T211 ,nxxxXT121,nnwwwwWXWXWXWTT21),(-J部分：niniiwxw11TWWXWT111111,iniininiikniniiwxwwwxwwwxwwXT11 ,nkxxxnnddddIXXXXTT 111111TnnnnXXIWXWXWT首先求另：矩阵论中有XWXWXWTT21),(-JXXWXWXW-Tsgn21,JJ其中 -0, 10, 1sgnTT

22、TXWXWXW若若 由的结论 有： XWXWTXWXWWXWXWTTT0时，XWXWWXWXW-TTT0时，XXWWXWTTsgnXWXWXWTT21),(-J kJckJckkWWWXWWWW-,12. 求W(k+1)将 代入得： XXWXWW-)(sgn211Tkckk 0)(,0)(, 0TTXWXXWWkckk若若 XWXXW)(sgn2Tkck-XXWXWXW-Tsgn21,JJ 由此可以看出，感知器赏罚算法是梯度法的特例。即：梯度法是将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题，将原来有多个解的情况，变成求最优解的情况。上式即为固定增量算法，与感知器赏罚算法形式

23、完全相同 。 0)(,0)(, 01TTXWXXWWWkckkk若若即： 0, 0,1TTiiikckkkkXWXWXWWW若若只要模式类是线性可分的，算法就会给出解。由于c是预先选定的固定值，因此叫固定增量算法。n线性分类器设计任务：给定样本集K，确定线性判别函数g(x)=wTx的各项系数w。步骤：1.抽取类别标志明确的样本集合 K=x1,x2,xN作为训练样本集。2.确定一准则函数J(K,w)，其值反映分类器的性能，其极值解对应于“最好”决策。3.用最优化技术求准则函数J的极值解w*，从而确定判别函数，完成分类器设计。*argmax (,)J Kwwwn对于未知样本x，计算g(x)，判断其

24、类别2.7 Fisher线性判别线性判别n线性判别函数y=g(x)=wTx:n样本向量x各分量的线性加权n样本向量x与权向量w的向量点积n如果| w |=1，则视作向量x在向量w上的投影 nFisher准则的基本原理：找到一个最合适的投影方向，使两类样本在该方向上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑，从而使分类效果为最佳。Fisher线性判别线性判别图例图例Fisher判别x1x2w1H: g=0w2Fisher准则的描述：用投影后数据的统计性质均值和离散度的函数作为判别优劣的标准。d维空间样本分布的描述量维空间样本分布的描述量Fisher判别n各类样本均值向量mi1 1,2i

25、ix KiiNmxn样本类内离散度类内离散度矩阵Si与总类内离散度矩阵Sw ()() , 1,2iTiiii-xSxmxm12wSSSn样本类间离散度类间离散度矩阵Sb：1212()()Tb-Smmmm离散度矩阵在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而离散矩阵只是表示有限个样本在空间分布的离散程度一维一维Y空间样本分布的描述量空间样本分布的描述量n各类样本均值1, 1,2iiyimyiNn样本类内离散度和总类内离散度2() , 1,2iiiySymi-12wSSSn样本类间离散度 212()bSmm-以上定义描述d维空间样本点到一向量投影的分投影的分散情况散情况，因此也就是对某

26、向量w的投影在w上的分布。样本离散度的定义与随机变量方差相类似 nFisher准则函数定义的原则为，希望投影后，在一维空间中样本类别区分清晰，即两类距离越大越好，也就是类间离散度越大越好；各类样本内部密集，即类内离散度越小越好，根据上述准则，构造Fisher准则函数。12wSSS2121212()( )bFSmmJwSSSS-样本与其投影统计量间的关系样本与其投影统计量间的关系22()()()()iiiiiyTTix KTTiiix KTSSym-w xw mwwxmxwwm1212()TTwSSSSSwwww2212121212()()()()TTTbTbTSSmm-w mw mwwmmmm

27、wwFisher准则函数准则函数n评价投影方向w的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内尽可能密集的要求nFisher准则函数的定义：12( )TbbFTwSSJwSSSwwwwnFisher最佳投影方向的求解*argmax( )FJwwwFisher最佳投影方向的求解最佳投影方向的求解n采用拉格朗日乘子算法解决*112()wS-wmmm1-m2是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对m1-m2 向量按Sw-

28、1作一线性变换，从而使Fisher准则函数达到极值点判别函数的确定n前面讨论了使Fisher准则函数极大的d维向量w*的计算方法，判别函数中的另一项y0（阈值）可采用以下几种方法确定：1202mmy1122012N mN mymNN1212012ln()/()22PPmmyNN-0102TTyyyyw xxw xxn分类规则:2.7 最小平方误差算法最小平方误差算法（least mean square error, LMSE；亦称Ho-Kashyap算法） 上述的感知器算法、梯度算法、固定增量算法或其他类似方法，只有当模式类可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次

29、迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：a) 迭代过程本身收敛缓慢b) 模式本身不可分对可分模式收敛。对于类别不可分的情况也能指出来。LMSE算法特点：1. 分类器的不等式方程分类器的不等式方程11121211121222221122000ddddNNdNdNa ya ya ya ya ya ya ya ya yL LL LML对对对yyy类1类2T0ia y 两类分类问题的解相当于求一组线性不等式的解。如果给出分属于 ， 两个模式类的训练样本集 ，寻找权值a应满足：12,1,2,iiNLy其中，yi是规范化增广样本向量， 。T12,1iiiinyyyLy上式分开写为：5.

30、4 最小平方误差算法(LMSE)nLMSE方法的基本思想是将求解线性不等式组的问题转化为求解线性方程组：1112111212222212ddNNNddNyyyabyyyabyyyab,Ya =b0b最小平方误差的准则函数n定义误差矢量e，用e长度的平方作为准则函数：-eYab 221()NSiiiJa yb-aYab使得 SJa最小的解*a称为最小二乘解，又称为伪逆解或MSE解。由上式定义的准则函数也称为MSE准则函数。权值矢量的求解(伪逆求解法) 12()2NSiiiiJaa yb yaa-YYb0aY YY b1*a-Y YY bYb1-YY YY称为Y的伪逆矩阵()Yn如果按照式求解a*

31、时，需要计算矩阵 及其逆矩阵 ,计算量大，通常可以使用梯度下降法以迭代的方式求解。n由最小均方误差准则的梯度公式Y Y1()-Y Y 2SJaaa-YYb使用梯度下降法作迭代式1)kkkaaab-Y (Y其中0a为任意的迭代初始值，经过有限次迭代可得到最优解0a1()kkkkkkkaaba yy-kyn为了进一步减少计算量和存储空间，可以使用单个样本修正 算法，则迭代式可修正为其中迭代初始向量为任意向量，单个样本 为满足kkka yb的样本。由于kbkkkayb1kk是任意给定的正常数，因此理想的逼近条件几乎是永远不可能够满足的，修正过程永远不可能结束。为了保证算法的收敛性，选取使得步长因子随

32、迭代步数的增加而逐渐减少，保证算法收敛于满意的解 。*an例: 有两类模式的训练样本：1： (0,0), (0,1) 2： (1,0), (1,1) 用LMSE算法求取判别函数，将两类样本分开。权值矢量的求解(迭代求解法)1.begin initialize a(0), b, , (0), k0；2. do kk+1；3. 4. 5. until 6.return a7.end 11niiiikkkb-aaa yy 1niiiikb-a yyLMSE算法的特点n算法的收敛依靠(k)的衰减，一般取(k)=(1)/k；n算法对于线性不可分的训练样本也能够收敛于一个均方误差最小解；n取b=1时，当样

33、本数趋于无穷多时，算法的解以最小均方误差逼近贝叶斯判别函数； 见边肇祺编写清华大学出版社模式识别1. 分类器的不等式方程分类器的不等式方程-NnNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX对对对00012211212222211111122111类1类20TiXW 两类分类问题的解相当于求一组线性不等式的解。如果给出分属于 ， 两个模式类的训练样本集 ，应满足：12, 2 , 1,NiiX其中，Xi是规范化增广样本向量， 。T21 1,iniiixxxX上式分开写为：写成矩阵形式为 ： 令N (n+1) 的长方矩阵为X，则 , 变为：0TiXW0XW0-1111211

34、2122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx-NnNnnNNnnnnnnwxwxwxwwxwxwxwwxwxwxwXXX对对对00012211212222211111122111类1类21,.iNL式中：T121,nnwwwwW121TT1TT2T1-nNNNiXXXXXX0XW0-11112112122221112110000111NnnnnNNnNNnnwwwwxxxxxxxxx0为零向量 感知器算法是通过解不等式组 ，求出W。0XW2. LMSE算法算法1) 原理原理的求解。式中： 两式等价。T21,NibbbbB为各分量均为较小正值的矢量。L

35、MSE算法把对满足 XW 0 的求解，改为满足BXW 在方程组系数矩阵中当行数列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数N总是大于模式的维数n，因此方程的个数(行数)模式向量的维数(列数)，是矛盾方程组矛盾方程组，只能求近似解W*，即说明：极小-BXW * LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，XW=B 可得到近似解（最小二乘近似解）。 LMSE算法的思路：BWBXWXW、通过求准则函数极小找求解对求解对 0转化为转化为准则函数定义为： 221,BXWBXW-J“最小二乘”： 最小：使方程组两边误差最小， 也即使J最小。 二乘：次数为2

36、，乘了两次最小平方（误差算法）1111121111221111111111-NNinnnnNNnNininnbbbwwwwxxxxxxxxBXW-NNiiNNnnNnNinnininnnbbbbwwxwxbwwxwxbwwxwxXWXWXWTT11T1111111111111向量各分量的平方和向量各分量的平方和-22BXW-NiiiNNbbb12T2T211T2XWXWXWBXW考察向量(XWB) 有：可以看出： 当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。 因为因为J有两个变量有两个变量W和和B，有更多的自由度供选择求解，有更多的自由度供选择求解，故可望

37、改善算法的收敛速率。，故可望改善算法的收敛速率。21T22121,-NiiibJXWBXWBXWXW=B 的近似解也称“最优近似解”： 使方程组两边所有误差之和最小（即最优）的解。准则函数：BXBXXXWBXXWXBXWX#T1TTTT0-使J 对W求最小，令 ，得：2) 推导推导LMSE算法递推公式算法递推公式与问题相关的两个梯度： BXWXW-TJBXWBXWB-21J (3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求递推公式：(1) 求W 的递推关系X为N(n+1)长方阵，X#为(n+1) N 长方阵。T1T#XXXX-称为X的伪逆，式中： (3-45)0WJ(2

38、) 求B(k+1)的迭代式 kJckkBBBBB-1 kkkkckkBXWBXWBB-21(3-46)代入，得cc 2 kkk-XWBe 令，定义(3-49) 1kkckkBBee(3-50)(3-46)BXWBXWB-21J利用梯度算法公式有： kJckkWWWXWWW-,1 kkBBXXXXX-#T1T kckckeXeXBX#(3) 求W(k+1)的迭代式将(3-50)代入(3-47)式W=X#B 有： kkckkkeeBXBXW#11 kkkBXWXXXeX-T1T#=0 kckeXW#0 kkkeBXW-(3-49) kkckkeeBB1(3-50) 11#BXW kkkBXWe-

39、kckkeXWW#1 kkckkeeBB111#kkBXW总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数 。W(k+1)、B(k+1)互相独立，先后次序无关。求出B，W后，再迭代出下一个e，从而计算出新的B， W。 11#BXW kkkBXWe- kkckkeeBB1或另一算法：先算B(k+1)，再算W(k+1)。3）模式类别可分性判别）模式类别可分性判别 如果e(k)0 ，表明XW(k)B(k) 0， 隐含有解。继续迭代， 可使e(k) 0 。 如果e(k)0，有解。分以下几种情况：111-kkkBXWe kkWW1 kkee1 kkBB111#kkBXW情况分析： kkckk

40、eeBB1e(k)0，线性可分，若进入(5)可使e(k) 0 ，得最优解。如果e(k)0，线性不可分，停止迭代，无解，算法结束。如果e(k)=0，线性可分，解为W(k)，算法结束。否则，说明e(k)的各分量值有正有负，进入(5)。 kckkeXWW#1 kkckkeeBB1 kkckkeeBB111#kkBXW(5) 计算W(k+1)和B(k+1)。方法1：分别计算方法2：先计算再计算迭代次数k加1，返回(4)。3. 算法特点算法特点(1) 算法尽管略为复杂一些，但提供了线性可分的测试特征。(2) 同时利用N个训练样本，同时修改W和B，故收敛速度快。(3) 计算矩阵 复杂，但可用迭代算法计算。

41、1T-XX例3.11 已知两类模式训练样本： TT11 ,0,0,0:TT21 ,1,0,1:试用LMSE算法求解权向量。-111101110100X解：(1) 写出规范化增广样本矩阵： Aij是aij的代数余子式，注意两者的行和列的标号互换。 T1T#XXXX- (2) 求伪逆矩阵-422221212111101110100111110101100TXX*11AAA-求逆矩阵：333231232221131211aaaaaaaaaA332313232212312111*AAAAAAAAAA若，则 |A|A的行列式A*A的伴随矩阵422221212TXX 划去aij所在的行和列的元素，余下元素

42、构成的行列式做aij的余子式，记作Mij ，将 叫做元素aij的代数余子式。例：代数余子式定义： ijijAM ji1- 323112113231121132231-aaaaaaaaA-322240204413222402041T1TXXXX44884416422221212T-XX行列式: 333231232221131211aaaaaaaaaA*11AAA-1113222222224111111010110032224020441#X -1024084111111113222222224111#BXW(3) 取 和 c=1 开始迭代： T1 , 1 , 1 , 11 B -00001111

43、11111111102111101110100111BXWe 121-xd X解为 W(1) ，判断函数为：T1T#XXXX-图示如下：例3.12 已知模式训练样本： ，TT11 , 1,0 ,0:TT20, 1,1 ,0:-101110111100X( 2) 求 ：T1T#XXXX-11132222222241#X解：(1) 规范化增广样本矩阵：(3) 取 和c=1，迭代： T1 , 1 , 1 , 11 B用LMSE算法求解权向量。 T#00011BXW TTT111111110000111-BXWe e(1)全部分量为负，无解，停止迭代。为线性不可分模式。 小结：小结：(1) 感知器法、梯度法、最小平方误差算法讨论的分类算法都是通过模式样本来确定判别函数的系数，所以要使一个分类器设计完善，必须采用有代表性的数据，训练判别函数的权系数。它们能合理反映模式数据的总体。(2) 要获得一个有较好判别性能的线性分类器，所需要的训练样本的数目的确定。用指标二分法能力N0来确定训练样本的数目：通常训练样本的数目不能低于N0 ，选为 N0的510倍左右。二维：不能低于6个样本，最好选在3060个样本之间。三维：不能低于8个样本，最好选在4080个样本之间。120nNn为模式维数如