黄庆明-模式识别与机器学习-第三章-作业

1、在一个10类的模式识别问题中， 有3类单独满足多类情况1 ,其余的类别满足多类情况 2。 问该模式识别问题所需判别函数的最少数目是多少？c 7*6应该是 3 1 c72 4 7-6 4 21 252其中加一是分别3类和7类一个三类问题，其判别函数如下:d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1(1)设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。r*孑利区域di (x)0q-05-tc. y(l-t(2)设为多类情况 2,并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别界面和

2、多类 情况2的区域。设d1(x), d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。中!1凶酝两类模式，每类包括 5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量?(设模式的良好分布不因模式变化而改变。)如果线性可分，则 4个建立二次的多项式判别函数，则 c： 10个 (1)用感知器算法求下列模式分类的解向量w:1: (0 0 0)t,(1 00)t,(1 01)t,(1 1 0)t2: (0 0 1)t,(0 11)t,(0 10)t,(1 1 1)t将属于3 2的训练样

3、本乘以(-1),并写成增广向量的形式。x =(0 0 0 1)x =(0 0 -1 -1)t, x =(1 0 0 1)t, x =(1 0 1 1)t, x =(1 1 0 1) t,x =(0 -1 -1 -1)第一轮迭代：取 c=1, w(1)=(0 0 0 0) 因 wt (1) x =(0 0 0 0)(0 0 0 1) 因 wt(2) x =(0 0 0 1)(1 0 0 1),x =(0 -1 0 -1), x =(-1 -1 -1 -1)tt =0 0,故 w(2)=w(1)+ x =(0 0 0 1)t =10 ,故 w(3)=w(2)=(0 0 0 1) t因 wt(3)x

4、 =(0 0 0 1)(1 0 1 1)因 wt(4)x =(0 0 0 1)(1 1 0 1)因 wt(5)x =(0 0 0 1)(0 0 -1 -1)因 wt(6)x =(0 0 -1 0)(0 -1 -1 -1)t因 w(7)x =(0 0 -1 0)(0 -1 0 -1)因 wt(8)x =(0 -1 -1 -1)(-1 -1 -1 -1)=10,故 w(4)=w(3) =(0 0 0 1) t=10,故 w(5)=w(4)=(0 0 0 1) tt=-10,故 w(6)=w(5)+ x =(0 0 -1 0) tt=10,故 w(7)=w(6)=(0 0 -1 0) tt=00,故

5、 w(8)=w(7)+ x =(0 -1 -1 -1)t=30,故 w(9)=w(8) =(0 -1 -1 -1)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第二轮迭代。第二轮迭代：因 wt(9)x =(0 -1 -1 -1)(0 0 0 1)t=-1 0,故 w(10)=w(9)+ x =(0 -1 -1 0)wt(10)x=(0-1-10)(10 01)wt(11)x=(1-1-11)(10 11)wt(12)x=(1-1-11)(11 01)wt(13)x=(1-1-11)(0 0 -1-1)twt(14)x =(1 -1 -2 0)( 0 -1 -1 -1)wt(15

6、)x =(1 -1 -2 0)( 0 -1 0 -1) twt(16)x =(1 -1 -2 0)( -1 -1 -1 -1)t=00,故 w(11)=w(10)+ x =(1-1-1 1)t=10,故 w(12)=w(11) =(1 -1 -1 1)t=10,故 w(13)=w(12) =(1 -1 -1 1)t=00,故 w(14)=w(13)+ x =(1 -1 -2 0)t=30,故 w(15)=w(14) =(1 -1 -2 0)t=10,故 w(16)=w(15) =(1 -1 -2 0) tt=20,故 w(17)=w(16) =(1 -1 -2 0)因为只有对全部模式都能正确判

7、别的权向量才是正确的解，因此需进行第三轮迭代。第三轮迭代：w(25)=(2 -2 -2 0);因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第四轮迭代。第四轮迭代：w(33)=(2 -2 -2 1)因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第五轮迭代。第五轮迭代：w(41)=(2 -2 -2 1)因为该轮迭代的权向量对全部模式都能正确判别。所以权向量即为 (2 -2 -2 1), 相应的判别 函数为 d(x) 2x1 2x2 2x3 1(2)编写求解上述问题的感知器算法程序。见附件 用多类感知器算法求下列模式的判别函数：31： (-1 -1)t32： (0

8、0)t33： (1 1)t将模式样本写成增广形式：x=(-1 -1 1)t, x =(0 0 1) t, x =(1 1 1) t取初始值w1(1)=w 2(1)=w 3(1)=(0 0 0)t， c=1。第一轮迭代( k=1 ) ：以 x =(-1 -1 1)t 作为训练样本。d1(1)=w； (1)x=(00 0)(-1-11)t=0d2(1)=wt (1)x=(00 0)(-1-11)t=0d3(1)=wt(1)x =(00 0)(-1-11)t=0因 d1(1) d2(1),d1(1) d3(1),故w1(2)=w 1(1)+x =(-1 -1 1) w2(2)=w 2(1)-x =(

9、1 1 -1) w3(2)=w 3(1)-x =(1 1 -1)第二轮迭代(k=2)：以x=(0 0 1) t作为训练样本d1(2)= w： x=(-1 -1 1)(0 0 1)t=1d2(2)= wt (2) x=(1 1 -1)(0 0 1)t=-1d3(2)= wt x=(1 1 -1)(0 0 1) t=-1因 d2(2)d1(2) , d2(2) d3(2),故 w1(3)=w 1(2)-x =(-1 -1 0) t w2(3)=w 2(2)+x =(1 1 0) tt w3(3)=w 3(2)-x =(1 1 -2)第三轮迭代(k=3):以x=(1 1 1) t作为训练样本d1(3

10、)= w：(3)x =(-1-1 0)(1 1 1)t=-2d2(3)= wt (3) x=(1 1 0)(1 1 1)t=2d3(3)= wt (3) x=(1 1 -2)(1 1 1)t=0因 d3(3) d2(3),故w1(4)=w 1(3) =(-1 -1 0) tt w2(4)=w 2(3)-x =(0 0 -1) w3(4)=w 3(3)+x =(2 2 -1) t第四轮迭代(k=4)：以x=(-1 -1 1) t作为训练样本d1(4)= w： (4) x=(-1 -1 0)(-1 -1 1)t=2d2(4)= wt (4) x=(0 0 -1)(-1 -1 1)t=-1d3(4)

11、= wt (4) x=(2 2 -1)(-1 -1 1)t=-5因 d1(4)d 2(4) ， d1(4)d 3(4) ，故t w1(5)=w 1(4) =(-1 -1 0) w2(5)=w 2(4) =(0 0 -1) t w3(5)=w 3(4) =(2 2 -1) t第五轮迭代(k=5):以x=(0 0 1) t作为训练样本d1(5)= w； (5) x=(-1 -1 0)(0 0 1)t=0d2(5)= wt(5)x =(0 0 -1)(0 0 1)t=-1d3(5)= wt(5)x =(2 2 -1)(0 0 1)t=-1因 d2(5)d1(5) , d2(5)d3(5),故w1(6

12、)=w 1(5)-x =(-1 -1 -1)w2(6)=w 2(5)+x =(0 0 0) w3(6)=w 3(5)-x =(2 2 -2)第六轮迭代(k=6):以x=(1 1 1) t作为训练样本d1(6)= w： (6)x=(-1 -1 -1)(1 1 1)t=-3d2(6)= wt (6) x=(0 0 0)(1 1 1)t=0d3(6)= wt (6) x=(2 2 -2)(1 1 1)t=2因 d3(6)d 1(6) , d3(6)d 2(6),故w1(7)=w 1(6)w2(7)=w 2(6)w3(7)=w 3(6)第七轮迭代(k=7)：以x=(-1 -1 1) t作为训练样本d1

13、(7)= w： (7) x=(-1 -1 -1)(-1 -1 1)t=1d2(7)= wt (7) x=(0 0 0)(-1 -1 1)t=0d3(7)= wt (7) x=(2 2 -2)(-1 -1 1) t=-6因d1(7)d 2(7) , d1(7)d 3(7),分类结果正确，故权向量不变。由于第五、六、七次迭代中x、x、x均已正确分类，所以权向量的解为:w1=(-1 -1 -1) w2=(0 0 0)w3=(2 2 -2)-x2-11+2x2-2三个判别函数:d1(x)=- x d2(x)=0 d3(x)=2x采用梯度法和准则函数j(w, x, b)2(wtx b)8xwtx b2式

14、中实数b0,试导出两类模式的分类算法。j 1 ttt2 (w x b) |w x b| * x-x*sign(w x b) w 4l|x|if wtx-bsign(wtx b)其中,1 if wtx b 0当wtx b 0时，则w(k+1) = w(k),此时不对权向量进行修正；当11 xk |wtx b 0时，则w(k 1) w(k)cxk2限飞 b，需对权向量进行校正，初始权向量w(1)的值可任选。即0if wtx b 0w(k 1) w(k) cxkt12 (wk xkb) if w x b 0i |xk |用二次埃尔米特多项式的势函数算法求解以下模式的分类问题03 1： (0 1)t,

15、 (0 -1)tco 2: (1 0)t, (-1 0)t(1)1 (x)1(x1,x2)h0(x1)h0(x2)12 (x)2 (x1, x2 ) h 0(x1)h 1 (x2) 2x223(x)3(x1,x2)h0(x1)h2(x2)4x224(x)4(x1,x?)小(不用0%) 2x15(x)5(x1,x2)h 1(x1)h 1 (x2)4x1x26(x)6(x1，x2)h1 (x1)h 2 (x2)2x1(4 x22)7 (x)7(x1,x2)h 2(x1)h 0(x2)4x1228(x)8(x1,x2)h2(x1)h(x2)2x2 (4x12)9(x)9(x1，x2) h2(x1)h

16、2(x2) (4x12)(4 x2按第一类势函数定义，得到势函数9k(x,xk)i(x) i(xk)i 1其中 x (x1,x2)t, xk(xk1, xk2 )t(2)通过训练样本逐步计算累积位势k(x)给定训练样本：w 1类为x=(0 1) t, x=(0 -1) t3 2 类为 x=(1 0) t, x =(-1 0) t累积位势k(x)的迭代算法如下第一步：取 x=(0 1) tc1,故 _2_22k1(x)15 20x2 40x2 24x132x1第二步：取 x=(0 -1) tc1,故k(x)=52)2 264x1 x2因 k1(x )0 且 x c 1,故 k2(x)=k 1(x

17、)第三步：取 x=(1 0) tc 3 2,故kz(x)=9因k(x)0且xc 3 2,故_ 2_ 2k3(x) k2(x) k(x,x3)20x2 16x2 20xi 16xi第四步：取 x=(-i 0)te 3 2,故 &(x)=4因k3(x)0且xc 3 2,_2_22_22k4(x) k3(x) k(x,x4)15 20x2 56xi 8x2 32x x2 64x x2将全部训练样本重复迭代一次，得第五步：取 x=x=(0 1) tc si, k4(x )=270故 k5(x)=k 4(x)第六步：取 x=x=(0 -1) tc 31, k5(x)=-130故 k6(x) k5(x)

18、k(x,x6)32x2 32x2第七步：取 x=x=(1 0) tc 3 2, k6(x )=-320故 k7(x)=k 6(x)第八步：取 x=x=(-1 0) tc 3 2, k7(x)=-320故 k9(x)=k 8(x)第十步：取 x=x=(0 -1) tc 31, k9(x)=320故 ki0(x)=k 9(x)其中第七步到第十步的迭代过程中对全部训练样本都能正确分类，因此算法收敛于判 别函数d(x) k10(x)32x12 32x2用下列势函数k(x,xk) e 1|x xk12求解以下模式的分类问题“:(0 1)t, (0 -1)t32: (1 0)t, (-1 0)t取a =1

19、,在二维情况下势函数为k(x,xk)enxxke(xi xki)2 (x2 x，)2这里：3 i 类为 x=(0 1) t, x =(0 -1) t3 2 类为 x=(1 0) t, x =(-1 0) t可以看出，这两类模式是线性不可分的。算法步骤如下：第一步：取 x=(0 1) tc 1,则 ki(x) exp x； (x2 1)2第二步：取 x=(0 -1)te 3 i因 k(x 尸e-(4+0)=e-40,故 &(x)=k i(x)第三步：取 x=(1 0)te2因 k2(x )=e -(i+i) =e-2 0，故k3(x) k2(x) k(x,x3) exp xi2 (x2 i)2 exp (xi i)2 x22第四步：取x=(-1 0) * 3 2因 &(x )=e-(1+1) - e -(4+0) =e-2- e -40,故k4(x)k3(x)k(x,x4)e