《模式識(shí)別》(邊肇祺)習(xí)題答案

1、模式識(shí)別（第二版）習(xí)題解答目錄TOC o 1-5 h z1緒論2 HYPERLINK l bookmark22貝葉斯決策理論2 HYPERLINK l bookmark63概率密度函數(shù)的估計(jì)8 HYPERLINK l bookmark104線性判別函數(shù)10 HYPERLINK l bookmark185非線性判別函數(shù)16 HYPERLINK l bookmark206近鄰法16 HYPERLINK l bookmark227經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化和有序風(fēng)險(xiǎn)最小化方法18 HYPERLINK l bookmark248特征的選取和提取18 HYPERLINK l bookmark329基于KL展開式的特

2、征提取20 HYPERLINK l bookmark3410非監(jiān)督學(xué)習(xí)方法22模式識(shí)別(第二版)習(xí)題解答 1緒論略2貝葉斯決策理論2.1如果只知道各類的先驗(yàn)概率，最小錯(cuò)誤率貝葉斯決策規(guī)則應(yīng)如何表示？解：設(shè)一個(gè)有C類，每一類的先驗(yàn)概率為P(妙)，i=Co此時(shí)最小錯(cuò)誤率貝葉斯決策規(guī)貝IJ為：如果產(chǎn)=maxP(wj),貝Oxewii2.2利用概率論中的乘法定理和全概率公式證明貝葉斯公式(教材中下面的公式有錯(cuò)誤)P（xWi）P（Wi）P（咔）p（x）證明：_P（xWi）P（Wi）P（）2.3證明:在兩類情況下P(wix)+P(w2x)=lo證明：P(吩)+PT)=駕評(píng)+豁P伽，)+)P()=pW_pW

3、=12.4分別寫出在以下兩種情況P(xwi)=P(xw2)PM=P(w2)下的最小錯(cuò)誤率貝葉斯決策規(guī)則。解：當(dāng)P(x|w!)=P(xw2)時(shí)，如果P(wi)P(w2),則rrwx,否則為6w2o當(dāng)F(wi)=P(w2)時(shí)，如果P(a;|wi)P(xw2),則wi,否則w22.5對(duì)c類情況推廣最小錯(cuò)誤率率貝葉斯決策規(guī)則；昭出此時(shí)使錯(cuò)誤率最小等價(jià)于后驗(yàn)概率最大，即F(wjx)P(Wjx)對(duì)一切j/i成立時(shí)，xewo解：對(duì)于C類情況，最小錯(cuò)誤率貝葉斯決策規(guī)則為：如果P(Wix)=maxP(Wjx),貝Oxewi0利用貝葉斯定理可以將其寫成先驗(yàn)概率和類條件概率相聯(lián)縈侖諺式，即如果p(xWi)P(Wi)

4、=maxp(a;|wj)P(w),貝ixe2.6對(duì)兩類問(wèn)題，證明最小風(fēng)險(xiǎn)貝葉斯決策規(guī)則可表示為，若P(刑1)(A12-A22)P(w2)P(xw2)(入21入11)P(5)則Wi,反之則屬于2。解：計(jì)算條件風(fēng)險(xiǎn)2Rx)=fXljP(wjx)J=1=AiiF(wi|x)十Xi2P(w2x)2R(Q2X)=刀入2/P伽|另)J=1=入21P(3i|十入22卩(色2|)如果R(aix)R(a2x)y貝!rrewioAnP(Wi|x)+Ai2P(w2|x)(A12-入22)卩仙2卜)(入21-An)P(Wi)p(x|wi)(A12-入22)P(W2)P|W2)P(|如(入12-入22)卩他)卩(問(wèn)2)

5、(入21-An)F(w1)所以，如果P(創(chuàng)31)(入12-入22)卩(如P(XW2)(入21-An)P(Wi)則eWio反之則W2o模式識(shí)別(第二版)習(xí)題解答 27若入11=入22=012=入21,證明此時(shí)最小最大決策面是來(lái)自兩類的錯(cuò)誤率相等。解：最小最大決策時(shí)滿足(入11一入22)+(入21一入11)p(xwl)dx-(A12-A22)p(xw2)djc=0容易得到/p(xw2)dx=/p(xw)dx所以此時(shí)最小最大決策面使得R(e)=P2(e)2.8對(duì)于同一個(gè)決策規(guī)則判別函數(shù)可定義成不同形式，從而有不同的決策面方程，指出決策區(qū)域是不變的。解：對(duì)于同一決策規(guī)則(如最小錯(cuò)誤率貝葉斯決策規(guī)則)，

6、它的判別函數(shù)可以是=max貝臨eiv尹。另外一種形式為=.maxp(xwj)Pu)j)y貝beWj*o考慮前類問(wèn)題的分類決策面為：P(Wi|x)=P(w2|x),-p(x|w1)P(Wi)=p(x|w2)P(w2)是相同的。2.9寫岀兩類和多類情況下最小風(fēng)險(xiǎn)貝葉斯決策判別函數(shù)和決策面方程。2.10隨機(jī)變量心)定義為心)=學(xué)輿，心)又稱為似然比，試證明P(XW2)-(1)Eln(x)wi=Eln+1(x)w2-El(x)w2=1對(duì)于(3),EZ(x)|w!-E2l(x)w2=El2(x)w2-E2lx)w2=varZ(x)|w2-El(x)wi-E2l(x)w2=varZ)|汲2(教材中題目有問(wèn)

7、題)2.11Xj(j=l,2,.,n)為九個(gè)獨(dú)立隨機(jī)變量,有Exjwi=ijrj,var|wj=i2j2a2f計(jì)算在入11=入22=0及入12=入21=1的情況下，由貝葉斯決策引起的錯(cuò)誤率。(中心極限定理)解：在0-1損失下，最小風(fēng)險(xiǎn)貝葉斯決策與最小錯(cuò)誤率貝葉斯決策等價(jià)。2.12寫出離散形式的貝葉斯公式。解：2.13把連續(xù)情況的最小錯(cuò)誤率貝葉斯決策推廣到離散情況，并寫出其判別函數(shù)。2.14寫出離散情況條件風(fēng)險(xiǎn)Raix)的定義，并指出其決策規(guī)則。R(訃)=刀入了卩(嗎=1=刀Aijp(x|wJ)F(wJ)/omitthesamepartp(x)i=il?(afc|a;)=_min7?(ay|a;

8、),則蚣就是最小風(fēng)險(xiǎn)貝葉斯決策。2.15證明多元正態(tài)分布的等密度點(diǎn)軌跡是一個(gè)超橢球面，且其主軸方向由E的特征向量決定，軸長(zhǎng)度由另的特征值決定。證明：多元正態(tài)分布的等密度點(diǎn)滿足：=C為常數(shù)。2.16證明Mahalanobis距離r符合距離定義三定理，即-(l)r(a,d)=r(6,a)當(dāng)且僅當(dāng)a=6時(shí)，r(a,6)=0一(3)r(a,c)所以冏=(xi,x2)|xi(x2-1)0,%2=(X1,X2)XI(X2-1)03概率密度函數(shù)的估計(jì)3.1設(shè)總體分布密度為N(u,1),-ooui=l貝葉斯估計(jì)：MAP(maximumaposterior)N=aYp(Xiu)p(u)i=i(u-U0)22%將

9、譏訓(xùn)玄)寫成的形式，利用待定系數(shù)法，可以求得:1_N11N如_1Vr+進(jìn)一步求得如和處Nala2Un=+g+昇。n_Nal+721N其中，m”=如,妬就是貝葉斯估計(jì)。i=l3.3設(shè)玄=仙,血,.,射為來(lái)自點(diǎn)二項(xiàng)式分布的樣本集,即f(x,P)=PxQxx=O,1,OP1,Q=1-P,試求參數(shù)P的最大似然估計(jì)。解：似然函數(shù)為：NL(F)=In(嚴(yán)(1-P)(7)i=iNN兩邊對(duì)卩求導(dǎo)可得dL_1XiNdPP1-P+1-P1N所以p得最大似然估計(jì)為：心命。t=l3.4假設(shè)損失函數(shù)為二次函數(shù)A(P,P)=(P-P)2,以及P的先驗(yàn)密度為均勻分布/(P)=l,0P0,叼是在超平面上的投影點(diǎn)，則wFq十w

10、o=0o設(shè)到平面的距離為r,則=侖，所以wTx-wTxp=r|w|,得至b=WTX+w0_ff(x)IMI=o龍?jiān)诔矫尕?fù)側(cè)時(shí)g)則g(e)=a%映射g=l,x,x2T把一條直線映射為三維空間中的一條拋物線。4.4對(duì)于二維線性判別函數(shù)g)=xi+2x2-2-(1)將判別函數(shù)寫=wTx-|-wo的形式，并畫出g(x)=0的幾何圖形；-(2)映射成廣義齊次線性函數(shù)-(3)指出上述X空間實(shí)際是Y空間的一個(gè)子空間，且aTy=0于X子空間的劃分和原空間中滬十毗=0對(duì)原X空間的劃分相同，并在圖上表示出來(lái)。解：w=l,2T,x=x1,x2t,w0=-2,則g(x)=wTx+w0,g(x)=0的圖形如下圖2：

11、妙=卩,衍,叼T,a=-2,1,2T,則g(x)=aTy0Vl=1,2/2=龍1,2/3=龍2,在所以所有的樣本在Y空間中的一個(gè)平面i=1上。4.5指岀在Fisher線性判別中，的比例因子對(duì)Fisher判別結(jié)果無(wú)影響。解：假設(shè)乘一比例因子a,aw,經(jīng)過(guò)投影后得到y(tǒng)=awTx.相當(dāng)于對(duì)所有樣本乘以一個(gè)比例因子，所以對(duì)判別結(jié)果沒有影響。4.6證明兩向量外積組成的矩陣一般是奇異的。證明：設(shè)兩向量a,6eR它們的外積為：A=abT,因?yàn)閍廬與汗a有相同的非零特征值，容易得到4的特征值為卩a,0,0,.,0。有零特征值肯定是奇異的，除非汕=1。n1力2圖2:g(x)=0的幾何圖形4.8證明在正態(tài)等方差條

12、件下，F(xiàn)isher線性判別等價(jià)于貝葉斯判別。證明：在正態(tài)等方差的條件下，判別函數(shù)g(:r)=wTx+w0中3=仙-戀),在Fisher線性判別中最優(yōu)投影方向?yàn)椋?刀-1(如-tz2)o4.9證明-(1)弓I入余量6以后的解區(qū)(aTVib)位于原來(lái)的解區(qū)%0)之中；-(2)與原解區(qū)邊界之間的距離為侖。解：(1)設(shè)m滿足也b,則它一定也滿&aTyi0,所以引入余量后的解區(qū)位于原來(lái)的解區(qū)aTy0之中。(2)aTyi6區(qū)邊界為：aTyi=6,aTyi0解區(qū)邊界為:aTyi=0,aTyi=6至臨=0的距離為4.10證明，在幾何上，感知器準(zhǔn)則函數(shù)正比于被錯(cuò)分類樣本到?jīng)Q策面的距離之和。證明：感知器準(zhǔn)則函數(shù)為

13、J(a)=(-aT2/)o決策面方程為：aTy=0o當(dāng)y為錯(cuò)分類樣本時(shí)，有fy0,到?jīng)Q策面的距離為-/眇所有錯(cuò)分類樣本到?jīng)Q策面的距離之和為刀(-a珥/),就是感知器準(zhǔn)則函數(shù)。模式識(shí)別(第二版)習(xí)題解答1 為了進(jìn)一步減小計(jì)算量和存儲(chǔ)量，可以將上述算法修改為(單樣本修正)a(l)Ia(k+1)=a(k)-pk(a(k)Tyk-bk)yk讓隨著上的增加而逐漸減小，以確保算法收斂。一般選擇樂=,還有瀘和前面感知器準(zhǔn)則函數(shù)中的單樣本修正法一樣，是在無(wú)限重復(fù)序列中的錯(cuò)分類樣本。4.13證明矩陣恒等式(A+xx114-bd-11+xTAlx模式識(shí)別(第二版)習(xí)題解答1 #利用上試結(jié)果證明式(498)o證明：

14、(A+xxT)(A1A1xxTA11+xTAx)=(A+xxT)(IAr1xxr1+xTAlx)(4+xxTXXT1+xTArxxxTA1xxT1+xTAx)=AA所以(4十xxT)_1=Al-A1xxTA11+xTAx(2)R(k+I)1=Rg7十她罠利用上面的結(jié)果可以得到：R(k+1)=R(k)-R(k)yfcy：Rg1+yR(k)yk4.14考慮準(zhǔn)則函數(shù)其中鄉(xiāng)(a)是使aTyVJ(a)時(shí)，梯度下降法的迭代公式為:證明：S是羅)中的唯一樣本，則準(zhǔn)則函數(shù)為丿(a)=刀(叭-廳=-&)2,心(a)所以J(a)=2(aTyi-b)yi,二階偏導(dǎo)數(shù)矩陣為D=2yiyo梯度下降的迭代公式為：丑+1=

15、%PNJgPk=J少穢丁叫S(ayi-b)2yyYyyiT,將朋代入梯度下降的迭代公式：a中=丑+獸詳5yir模式識(shí)別(第二版)習(xí)題解答 4.15證明：當(dāng)取MSE解等價(jià)于Fisher解。Xi-X2、a=w0,wT51IJyrya=YTby化為:品-iririi&xfXJ-I2x2wj-lx?-if囂Wq設(shè)mi=右%m2=#Y上式可化為:1ieci2iec2N(Mi+N2m2)Tw00(Nig+N2m2)Sw+Nimimf+N2m2rnwN(mi-m2)2N式中，Su,=H(叼-m)T,且(Mmi+N2m2)T=NmTtm=菇,i=ljE6i=l上面的等式可以分解岀兩個(gè)等式，第一個(gè)得到wo=-m

16、Tw,將30代入第二個(gè)等式可以得到-(Nimi十N2m2)(Mmi+N2m，2)T+Sw+Nimirn+N2m，2rnw=N(mm2)點(diǎn)Sy+(mi一m2)(mi-m2)Tw=mi一m2注意因?yàn)榘藢?dǎo)(mi-m2)(mi-m2)Twmi-g的方向上，所以上式可以化為：Sw=a(mi-m2)與Fisher的解相同。4.16證明:-式(4413)表示的向量表示g到X空間中超平面的投影。wLWJ-(2)該投影正交于X空間的超平面。證明：(1)先證明這個(gè)向量在X空間中的超平面上，再證明g(0臨llll2LWJ/的向量為X空間中超平面的法向量。X空間中的超平面的方程為：g(x)=wTx+XOX0=l,wT

17、翳|W=O,又因知-卩-0將向量代入g（叭得迅-歸aTyA-aTyII訓(xùn)2W)II訓(xùn)$W4.17在多類問(wèn)題中，如果一組樣本可被一線性機(jī)全部正確分類，則稱這組樣本是線性可分的。對(duì)任意類，如果能用一超平面把g類的樣本同其他樣本分開來(lái)，則稱總體線性可分。舉例說(shuō)明，總體線性可分必定線性可分，但反之不然。解：模式識(shí)別(第二版)習(xí)題解答 #模式識(shí)別(第二版)習(xí)題解答 #圖3:總體線性可分必定線性可分模式識(shí)別(第二版)習(xí)題解答 #模式識(shí)別(第二版)習(xí)題解答 圖4:線性可分未必總體線性可分4.18設(shè)有一組樣本。若存在c（c-1）/2個(gè)超平面丹巧，使H巧把屬于叫類的樣本同屬于嗎類的樣本分開，則稱這組樣本是成對(duì)線

18、性可分的。舉列說(shuō)明，成對(duì)線性可分的樣本不一定線性可分。圖5:成對(duì)線性可分不一定定線性可分5非線性判別函數(shù)5.1舉例說(shuō)明分段線性分界面可以逼近貝葉斯判別函數(shù)確定的超曲面。解：分段線性函數(shù)是一類特殊的非線性函數(shù)，它確定的決策面由若干個(gè)平面段組成,所以它可以逼近各種形狀的超曲面。5.2已知兩類問(wèn)題如圖6所示，其中、x”表示類訓(xùn)練樣本集合的原型，、O“表示如類訓(xùn)練樣本集的原型。-(1)找出緊互對(duì)原型集合夕；-(2)找出與緊互對(duì)行集相聯(lián)系的超平面集#;-(3)假設(shè)訓(xùn)練集樣本與原型完全相同，找岀由超平面集#產(chǎn)生的z(rr)。圖6:一個(gè)兩類問(wèn)題的原型分布解：(1)用坐標(biāo)來(lái)表示樣本中的樣本(4,6)與血中的樣

19、本(5,5)是緊互對(duì)原型，(3,4)與(3,2)是，(2,5)與(1,3)也是。如圖7所示(2)如圖8所示6近鄰法6.1舉例說(shuō)明最近鄰決策面是分段線性的。解：分段線性函數(shù)的決策面由若干個(gè)超平面組成。由于它的基本組成仍然是超平面,因此，與一般超平面6.2證明式(6-14)(618)o證明：記CP2(Wix)=P2(wmx)+工P2(Wix)=1im圖7:緊互對(duì)原型6.3在什么情況下，最近鄰平均誤差P達(dá)到其上界6.5有7個(gè)二維向量：Xi=(1,0)t,x2=(0,1)t,x3=(0,-1)t,x4=(0,0)r,x5=(0,2)r,x6=(0,-2)t,x7=(-2,0)T,假定前三個(gè)為類，后四個(gè)為類。-(1)畫出最近鄰法決策面；-(2)求樣本均值尬1,尬2,若按離樣本均值距離的大小進(jìn)行分類，試畫岀決策面。解：第一首先要明確什么是“最近鄰法”？它實(shí)際是一種分段的線性判別函數(shù)。第二根據(jù)離樣本均值的距離來(lái)分類，首先求出兩類的樣本均值，分類決策面就是樣本均值的垂直平分線。如圖9所示。類的均值為=(l,0)r,地類的均值為TH2=(1,0)T,決策面如圖10所示。6.6畫岀爐近鄰法得程序框圖。解：取未知樣本為的上近鄰，看這公近鄰中多數(shù)屬于哪一類，就把龍歸為那一類。6.7對(duì)于有限樣本，重復(fù)剪輯是否比兩分剪輯的特性要好。6.8證明如果B+D(Xi,Mp)D(x,Mp)=)D(x,Mp)-D(