書華工電信模式識別答案版

1、目錄12345緒論22810決策理論概率密度函數(shù)的估計線性判別函數(shù)非線性判別函數(shù)近鄰法經(jīng)驗風(fēng)險最小化和有序風(fēng)險最小化方法特征的選取和提取基于K-L展開式的特征提取非監(jiān)督學(xué)習(xí)方法91020221 1緒論略 2決策理論2.1 如果只知道各類的先驗概率，最小錯誤率決策規(guī)則應(yīng)如何表示？解：設(shè)一個有C類，每一類的先驗概率為P (wi)，i = 1, ., C。此時最小錯誤率決策規(guī)則為：如果imax P ( =w )，則x w 。iii2.2 利用概率論中的乘法定理和全概率公式證明公式（中下面的公式有錯誤）p(x|wi)P (wi) .P (w |x) =ip(x)證明：P (wi, x) p(x)P (

2、wi|x) =p(x|wi)P (wi)p(x)2.3 證明：在兩類情況下P (wi|x) + P (w2|x) = 1。證明：P (w1, x)p(x)P (w2, x)p(x)P (w1|x) + P (w2|x) =+P (w1, x) + P (w2, x)p(x)p(x)p(x)= 12.4 分別寫出在以下兩種情況1. P (x|w1) = P (x|w2)2. P (w1) = P (w2)下的最小錯誤率決策規(guī)則。解： 當(dāng)P (x|w1) = P (x|w2)時，如果P (w1) P (w2)，則x w1，否則x w2。當(dāng)P (w1) = P (w2)時，如果P (x|w1) P

3、(x|w2)，則x w1，否則x w2。2.51.2.對c類情況推廣最小錯誤率率決策規(guī)則；此時使錯誤率最小等價于后驗概率最大，即P (wi|x) P (wj|x) 對一切j = i成立時，x wi。2解：對于c類情況，最小錯誤率決策規(guī)則為：如果 P (wi|x) = max P (wj|x)，則x wi。利用定理可以將其寫成先驗概率和j=1,.,c類條件概率相聯(lián)系的形式，即如果 p(x|wi)P (wi)= max p(x|wj)P (wj)，則x wi。j=1,.,c2.6 對兩類問題，證明最小風(fēng)險決策規(guī)則可表示為，若p(x|w1)(12 22)P (w2) ,p(x|w2)(21 11)P

4、 (w1)則x w1，反之則屬于w2。解：計算條件風(fēng)險2 R()=P () |xw |x11jjj=1= 11P (w1|x)+ 12P (w2|x)2 R()=P () |xw |x22jjj=1= 21P (w1|x)+ 22P (w2|x)如果R(1|x) R(2|x)，則x w1。11P (w1|x)+ 12P (w2|x) (12 22)P (w2|x)(21 11)P (w1)p(x|w1) (12 22)P (w2)p(x|w2)p(x|w1)(12 22)P (w2)p(x|w2)(21 11)P (w1)所以，如果p(x|w1)(12 22)P (w2)，則x w。反之則x

5、w 。12p(x|w2)(21 11)P (w1)2.7 若11 = 22 = 0, 12 = 21，證明此時最小最大決策面是來自兩類的錯誤率相等。解： 最小最大決策時滿足(11 22)+ (21 11)p(x|w1)dx (12 22)p(x|w2)dx =0 R2R1容易得到 p(x|w2)dx = p(x|w1)dxR1R2所以此時最小最大決策面使得P1(e)= P2(e)2.8 對于同一個決策規(guī)則判別函數(shù)可定義成不同形式，從而有不同的決策面方程，決策區(qū)域是不變的。3決策規(guī)則），它的判別函數(shù)可以是j =解： 對于同一決策規(guī)則（如最小錯誤率max P (wj|x)，則x wj 。另外一種形

6、式為j = max p(x|wj)P (wj)，則x wj 。j=1,.,cj=1,.,c考慮兩類問題的分類決策面為：P (w1|x) = P (w2|x)，與p(x|w1)P (w1) = p(x|w2)P (w2)是相同的。2.9 寫出兩類和多類情況下最小風(fēng)險決策判別函數(shù)和決策面方程。量l(x)定義為l(x) = p(x|w1)，l(x)又稱為似然比，試證明2.10 隨p(x|w2) (1) Eln(x)|w1 = Eln+1(x)|w2 (2) El(x)|w2 = 1 (3) El(x)|w1 E2l(x)|w2 = varl(x)|w2（中題目有問題）= = (p(x|w1)n+1

7、d證明：對于(1)n()|w1n()(x|w1)dn+1()|w2 =，Elxx 又Elxlxpx(p(x|w )n2(p(x|w1)n+1lp(x|w2)dx =n+1dx 所以，Eln(x)|w1 = Eln+1(x)|w2x|w2)n(p對于(2)，El(x)|w2 = l(x)p(x|w2)dx = p(x|w1)dx = 1對于(3)，El(x)|w1 E2l(x)|w2 = El2(x)|w2 E2l(x)|w2 = varl(x)|w22.11 xj(j = 1, 2, ., n)為n個獨立隨量，有Exj wi = ij，varxj|wi = i2j22，計算在11 = 22 =

8、 0 及12 = 21 = 1的情況下，由定理）決策引起的錯誤率。（中心極限解： 在0 1損失下，最小風(fēng)險決策與最小錯誤率決策等價。2.12 寫出離散形式的解：公式。P (x|wi)P (x)P (w |) =i xc j=1P (x|w )P (w )ii2.13 把連續(xù)情況的最小錯誤率決策推廣到離散情況，并寫出其判別函數(shù)。2.14 寫出離散情況條件風(fēng)險R(ai|x)的定義，并解：c其決策規(guī)則。R() =P (w |)a |xxiijjj=1c= p(xw )P (w )/omit the same part p(x)|ijjjj=1R(ak|x) =minR(aj|x)，則ak就是最小風(fēng)險

9、決策。j=1,2,.,N2.15 證明多元正態(tài)分布的等密度點軌跡是一個超橢球面，且其主軸方向由的特征向量決定，軸長度由的特征值決定。證明：多元正態(tài)分布的等密度點滿足：xT 1x = C，C為常數(shù)。42.16 證明Mahalanobis距離r符合距離定義三定理，即 (1) r(a, b)= r(b, a) (2) 當(dāng)且僅當(dāng)a = b時，r(a, b)= 0 (3) r(a, c) r(a, b)+ r(b, c)證明：(1) r(a, b) = (a b)T 1(a b) = (b a)T 1(b a)= r(b, a)(2) 為半正定矩陣所以r(a, b)= (a b)T 1(a b) 0，只

10、有當(dāng)a = b時，才有r(a, b) =0。(3) 1可對角化，1 = P P T hhh12 h22hh11121d2d 2.17 若將 矩陣寫為： =11，證明距離平方為. . . Mahalanobis.h1dh2dhdddd =2h (x u )(x u )ijiijji=1 j=1證明： h11h12h1dh12h22 h2d = (x u)()2T. . . x u.h1dh2dhdddd =h (x u )(x u )ijiijji=1 j=112.18 分別對于d = 2,d = 3證明對應(yīng)與Mahalanobis距離的超橢球體積是V = Vd| 2 d2.19 假定x和m是兩

11、個隨量，并設(shè)在給定m時，x的條件密度為 11) exp (x m() = (21) /22px|m22再假設(shè)m的邊緣分布是正態(tài)分布，期望值是m0，方差是2 ，證明m 2 2 12(3 + )1 2 + 22 x + mmexp 0()= mm|xm pm22 + 2122(2) 2mmm5證明：p(x|m)p(m)p(m|x) =p(x) p(x|m)p(m)()p()d|pxmmm) exp (1) exp (1(211) /(211m m ) /2222x m220mm=22) exp (x m1) exp (m m ) /d1(2) /(211112222m22m0m22()122= (

12、3 + )1 2 + 22 x + m 2mexp 0mmm 22 + 2122(2) 2mmm2.20 對i = 2I的特殊情況，證明(1) 若P (wi) = P (wj)，則超平面靠近先驗概率較小的類；(2) 在甚么情況下，先驗概率對超平面的位置影響不大。1證明： (1)當(dāng)P (w ) = P (w )時，超平面經(jīng)過x0 = 2 (u + u )，則對于先驗概率較小的類ijij屬于它的區(qū)域會減少，所以超平面經(jīng)過的點會靠近先驗概率較小的類。 （可以這樣理解，具體證明也很簡單）(2)？不知道這是什么問題，先驗概率不管在什么時候都很重要！2.21 對i = 的特殊情況，概率小的方向移動。證明：

13、 同上面一題解釋一樣。2.24 似然比決策準(zhǔn)則為：若在先驗概率不等時，決策面沿ui點與uj點連線向先驗2.23 二維正態(tài)分布，u1 = (1, 0)T , u2 = (1, 0)T , 1 = 2 = I, P (w1) = P (w2)。試寫出對數(shù)似然比決策規(guī)則。解：h(x) = ln l(x)= ln p(x|w1) + ln p(x|w2)111|1|= 2 (x1 u1) 1 (x1 u1) 2 (x2 u2) 2 (x2 u2) + 2 ln |T 1T 1|21=(x u ) (Tx u ) (x u ) (Tx u )11222lnP (w )= 0。所以判別規(guī)則為當(dāng)(xu )

14、(xu ) (xu ) (xu )則x w ,反而，TT111221P (w2)之則s w2。即將x判給離它最近的ui的那個類。= 1121112.24 在習(xí)題2.23中若 = ， =，寫出負(fù)對數(shù)似然比決2212121121策規(guī)則。6解：h(x) = ln l(x)= ln p(x|w1) + ln p(x|w2)111|1|= 2 (x1 u1) 1 (x1 u1) 2 (x2 u2) 2 (x2 u2) + 2 ln |T 1T 1|21x ( )1x ( u1T11u )T x+ij= 2121212u + ln |1| )T 1T 1(uu u121122|2|4= x x +x412

15、133lnP (w )= 0。決策面為x ( 1) = 0，如圖1所示而，1x12P (w2)圖 1: 分類決策面2.25 在習(xí)題2.24的情況下，若考慮損失函數(shù)11 = 22 = 0, 12 = 21，畫出似然比閾值與錯誤率之間的關(guān)系。(1)求出P (e) = 0.05時完成Neyman-Pearson決策時總的錯誤率；（P (e)應(yīng)該為P (e1)或者P (e2)）(2)求出最小最大決策的域值和總的錯誤率。解：（1）損失函數(shù)在0-1損失函數(shù)條件下的最小風(fēng)險決策等價于最小錯誤率決策。似然比等于0的情況下錯誤率最小。當(dāng)P (e1) = 0.05時，71（2）最小最大決策時，(1122)+(21

16、11) p(x|w1)dx(1222) p(x|w2)dm =R2R10 可以得到，p(x|w1)dx =p(x|w2)dm，所以R1 = (x1, x2)|x1(x2 1) 0，R2R1R2 = (x1, x2)|x1(x2 1) 0 3概率密度函數(shù)的估計3.1 設(shè)總體分布密度為N (u, 1)， u x。那么此時的最大似然估計為：= max xk(3)k3.8 利用矩陣恒等式(A1 + B1)1 = A(A + B)1B = B(A + B)1A證明：(A1 + B1)A(A + B)1B = (I + B1A)(A + B)1B= B1(B + A)(A + B)1B= B1B= I所以

17、：(A1 + B1)1 = A(A + B)1B 同理證明(A1 + B1)1 = B(A + B)1A3.15 設(shè)p(x) N (u, 2)，窗函數(shù)(x) N (0, 1)，Parzen窗估計()N1x xi(x) =NhNhNi=1對于小的hN ，有如下性質(zhì)： (1) E (2) V ar () N (u, + h )22xN1(x) =2 p(x)NhN證明：(1)E(x) = (x)p(x)dx8.1Sw表示類內(nèi)離散度矩陣，Sb表示類間離散度矩陣 4線性判別函數(shù)|g(x)|是在g(x4.1 （1）從x到超平面g(x) = wT x + w = 0的距離r =) = 0的約束0q|w|條

18、件下，使|x xq|2達到極小解； g(x)= x w（2）在超平面上的投影是xp|w|2解： （1）設(shè)x在超平面的正側(cè)g(x) 0，xq是x在超平面上的投影點，則wT xq + w0 = w 0。設(shè)x到平面的距離為r，則x x = r，所以wT x wT x = r|w|，得到r =pp|w|wT x + w0g(x)。=|w|w|10wT x w0g(x)x在超平面負(fù)側(cè)時g(x) 0)之中；b （2）與原解區(qū)邊界之間的距離為。|yi|解：（1）設(shè)a滿足aT yi b，則它一定也滿足aT yi 0，所以引入余量后的解區(qū)位于原來的解區(qū)aT y 0之中。（2）aT yi b解區(qū)邊界為：aT yi

19、 = b，aT yi 0解區(qū)邊界為：baT y = 0，aT y = b到aT y = 0的距離為。iii|yi|4.10 證明，在幾何上，感知器準(zhǔn)則函數(shù)正比于被錯分類樣本到?jīng)Q策面的距離之和。證明： 感知器準(zhǔn)則函數(shù)為J (a) =(a y)。決策面方程為：a y = 0。當(dāng)TTy為錯分類yY樣本時，有a y 0，到?jīng)Q策面的距離為aT y。所有錯分類樣本到?jīng)Q策面的距離之和T為(aT y)，就是感知器準(zhǔn)則函數(shù)。4.12 寫出Widrow-Hoff法程序框圖。yYN解： 平方誤差準(zhǔn)則函數(shù)J () = | =(2a y b ) ，它的最小二乘解，偽逆解T2aY a bnnn=1或MSE解為：a = (

20、Y YY bT)1 T，采用梯度下降法來求解aJ (。)的梯度為J (a) =aa(1)2Y T (Y a b)，則梯度下降法可以寫成，選擇k =a(k + 1) = a(k) kY T (Y a b)1 ，式中 為任意正常數(shù)。1k12為了進一步減小計算量和 量，可以將上述算法修改為（單樣本修正）a(1)a(k + 1) = a(k) k(a(k)T yk bk)yk讓 隨著k的增加而逐漸減小，以確保算法收斂。一般選擇 = 1 ，還有yk和前面感kkk知器準(zhǔn)則函數(shù)中的單樣本修一樣，是在無限重復(fù)序列中的錯分類樣本。4.13A1xxT A1（1）證明矩陣恒等式(A + xxT )1 =1A 1+

21、xT A1x（2）利用上試結(jié)果證明式（4-98）。證明： （1）T ) T ) 1T 1A1xxTAxx A(A + xxA1=( A +1 1+ xT A1xxxI 1+ xT A1xA= xxTT 1Txx AxxA + xxT1 1+ xT A1x 1+ xT A1xA= AA1= IA1xxT A1所以(A + xxT )1 =1A 1+ xT A1x（2）R(k + 1)1 = R(k)1 + ykyT ，利用上面的結(jié)果可以得到： R(k + 1) = R(k) kR(k)ykyT R(k)k1+ yT R(k)ykk4.14 考慮準(zhǔn)則函數(shù) J(a)= (aT y b)2yY (a)

22、其中Y (a)是使aT y b的樣本集合。設(shè)y1是Y (a)中的唯一樣本，則J(a)的梯度為J(a) =2(aT y1 b)y1，二階偏導(dǎo)數(shù)矩陣D = 2y1yT 。據(jù)此證明， 若最優(yōu)步長選擇為k =k1|J(a)|2時，梯度下降法的迭代公式為：JT (a)DJ(a)Tb a y1= ak +kak+1y1|y1|2 證明： y1是Y (a)中的唯一樣本，則準(zhǔn)則函數(shù)為J(a) = (aT y b)2 = (aT y1 b)2，yY (a)J() = 2()y ，二階偏導(dǎo)數(shù)矩陣為D = 2所以Ty y 。Taa y b11114(T) |221a y by |11梯度下降的迭代公式為：= akk

23、J(ak)，k =kak+18()2yT y1yT y12T|y1|2 ba y1k11Tb a y1，將k代入梯度下降的迭代公式：= ak +kak+1y1|y1|2134.15 證明：當(dāng)取NNNNb =, ., ., N1 N2 NN12|Nz1 |Nz2MSE解等價于Fisher解。Ty1Ty1X2證明： Y =11，a = w , wT 則Y T Y a = Y T b，化為：.12X20.yTN 111X1w11N1TTTT11012=12N1XTX12X2wXTXT N 12T2112N1 1 N1 1 N2設(shè)m =x , m =x ，上式可化為：1i2iiC1iC2 (N1m1

24、+ N2m2)T0Nw0=(N1m1 + N2m2)Sw + N1m1mT + N2m2mTwN (m1 m2)122N 式中，Sw =( m )( m ) ，且(N m + NTm )= Nm ，m =x ，TTxxjiji1122ii=1 jCii=1上面的等式可以分解出兩個等式，第一個得到w0 = mT w，將w0代入第二個等式可以得到 1(N m + N m )(N m + N m+ S + N m+ N m mw = N ()TmTTm m )11221122w11221212NS + N1N2 (m m )(m m )T w = m m 1Nw121212N 2注意因為N1N2 (

25、m m )(m m )T w在m m 的方向上，所以上式可以化為：121212NSww = (m1 m2)與Fisher的解相同。4.16 證明： aT y0 (1)式(4-113)表示的向量y到X空間中超平面的投影。表示y |w|2w (2)該投影正交于X空間的超平面。( )aT y0證明： （1）先證明這個向量在X空間中的超平面上，再證明y y |w|2w的向量為X空間中超平面的法向量。 X空間中的超平面的方程為： g(x) = wT x +14 aT y0 xx0 = 1, w 0=a y = 0，將向量代入g(x)，得 a= a y TTTTTy |w|2 awx( ) aT yaT

26、y0aT y0|w|2 |w| = 0，又因為y 2=|w|2y |w|2ww4.17 在多類問題中，如果一組樣本可被一線性機全部正確分類，則稱這組樣本是線性可分的。對任意wi類，如果能用一超平面把wi類的樣本同其他樣本分開來，則稱總體線性可分。舉例說明，總體線性可分必定線性可分，但反之不然。解：aaccbb圖 3: 總體線性可分必定線性可分圖 4: 線性可分未必總體線性可分4.18 設(shè)有一組樣本。若存在c(c 1)/2個超平面Hij，使Hij把屬于wi類的樣本同屬于wj類的樣本分開，則稱這組樣本是成對線性可分的。舉列說明，成對線性可分的樣本不一定線性可分。圖 5: 成對線性可分不一定定線性可分15 5非線性判別函數(shù)5.1 舉例說明分段線性分界面可以近判別函數(shù)確定的超曲面。解： 分段線性函數(shù)是一類特殊的非線性函數(shù)，它確定的決策面由若干個平面段組成，所以它可以近各種形狀的超曲面。5.2 已知兩類問題如圖6所示，其中表示w1類訓(xùn)練樣本集合的原型， 表示w2類訓(xùn)練樣本集的原型。找出緊互對原型集合P；找出與緊互對行集相聯(lián)系的超平面集H ；假設(shè)訓(xùn)練集樣本與原型完全相同，找出由超平面集H 產(chǎn)生的z(x)。圖 6: 一個兩類問題