《模式识别》(边肇祺)习题答案

1、模式识别（第二版）习题解答目录TOC o 1-5 h z1绪论2 HYPERLINK l bookmark22贝叶斯决策理论2 HYPERLINK l bookmark63概率密度函数的估计8 HYPERLINK l bookmark104线性判别函数10 HYPERLINK l bookmark185非线性判别函数16 HYPERLINK l bookmark206近邻法16 HYPERLINK l bookmark227经验风险最小化和有序风险最小化方法18 HYPERLINK l bookmark248特征的选取和提取18 HYPERLINK l bookmark329基于KL展开式的特

2、征提取20 HYPERLINK l bookmark3410非监督学习方法22模式识别(第二版)习题解答 1绪论略2贝叶斯决策理论2.1如果只知道各类的先验概率，最小错误率贝叶斯决策规则应如何表示？解：设一个有C类，每一类的先验概率为P(妙)，i=Co此时最小错误率贝叶斯决策规贝IJ为：如果产=maxP(wj),贝Oxewii2.2利用概率论中的乘法定理和全概率公式证明贝叶斯公式(教材中下面的公式有错误)P（xWi）P（Wi）P（咔）p（x）证明：_P（xWi）P（Wi）P（）2.3证明:在两类情况下P(wix)+P(w2x)=lo证明：P(吩)+PT)=驾評+豁P伽，)+)P()=pW_pW

3、=12.4分别写出在以下两种情况P(xwi)=P(xw2)PM=P(w2)下的最小错误率贝叶斯决策规则。解：当P(x|w!)=P(xw2)时，如果P(wi)P(w2),则rrwx,否则为6w2o当F(wi)=P(w2)时，如果P(a;|wi)P(xw2),则wi,否则w22.5对c类情况推广最小错误率率贝叶斯决策规则；昭出此时使错误率最小等价于后验概率最大，即F(wjx)P(Wjx)对一切j/i成立时，xewo解：对于C类情况，最小错误率贝叶斯决策规则为：如果P(Wix)=maxP(Wjx),贝Oxewi0利用贝叶斯定理可以将其写成先验概率和类条件概率相联萦侖谚式，即如果p(xWi)P(Wi)

4、=maxp(a;|wj)P(w),贝ixe2.6对两类问题，证明最小风险贝叶斯决策规则可表示为，若P(刑1)(A12-A22)P(w2)P(xw2)(入21入11)P(5)则Wi,反之则属于2。解：计算条件风险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)卩他)卩(问2)

5、(入21-An)F(w1)所以，如果P(创31)(入12-入22)卩(如P(XW2)(入21-An)P(Wi)则eWio反之则W2o模式识别(第二版)习题解答 27若入11=入22=012=入21,证明此时最小最大决策面是来自两类的错误率相等。解：最小最大决策时满足(入11一入22)+(入21一入11)p(xwl)dx-(A12-A22)p(xw2)djc=0容易得到/p(xw2)dx=/p(xw)dx所以此时最小最大决策面使得R(e)=P2(e)2.8对于同一个决策规则判别函数可定义成不同形式，从而有不同的决策面方程，指出决策区域是不变的。解：对于同一决策规则(如最小错误率贝叶斯决策规则)，

6、它的判别函数可以是=max贝临eiv尹。另外一种形式为=.maxp(xwj)Pu)j)y贝beWj*o考虑前类问题的分类决策面为：P(Wi|x)=P(w2|x),-p(x|w1)P(Wi)=p(x|w2)P(w2)是相同的。2.9写岀两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程。2.10随机变量心)定义为心)=学輿，心)又称为似然比，试证明P(XW2)-(1)Eln(x)wi=Eln+1(x)w2-El(x)w2=1对于(3),EZ(x)|w!-E2l(x)w2=El2(x)w2-E2lx)w2=varZ(x)|w2-El(x)wi-E2l(x)w2=varZ)|汲2(教材中题目有问

7、题)2.11Xj(j=l,2,.,n)为九个独立随机变量,有Exjwi=ijrj,var|wj=i2j2a2f计算在入11=入22=0及入12=入21=1的情况下，由贝叶斯决策引起的错误率。(中心极限定理)解：在0-1损失下，最小风险贝叶斯决策与最小错误率贝叶斯决策等价。2.12写出离散形式的贝叶斯公式。解：2.13把连续情况的最小错误率贝叶斯决策推广到离散情况，并写出其判别函数。2.14写出离散情况条件风险Raix)的定义，并指出其决策规则。R(讣)=刀入了卩(吗=1=刀Aijp(x|wJ)F(wJ)/omitthesamepartp(x)i=il?(afc|a;)=_min7?(ay|a;

8、),则蚣就是最小风险贝叶斯决策。2.15证明多元正态分布的等密度点轨迹是一个超椭球面，且其主轴方向由E的特征向量决定，轴长度由另的特征值决定。证明：多元正态分布的等密度点满足：=C为常数。2.16证明Mahalanobis距离r符合距离定义三定理，即-(l)r(a,d)=r(6,a)当且仅当a=6时，r(a,6)=0一(3)r(a,c)所以冏=(xi,x2)|xi(x2-1)0,%2=(X1,X2)XI(X2-1)03概率密度函数的估计3.1设总体分布密度为N(u,1),-ooui=l贝叶斯估计：MAP(maximumaposterior)N=aYp(Xiu)p(u)i=i(u-U0)22%将

9、讥训玄)写成的形式，利用待定系数法，可以求得:1_N11N如_1Vr+进一步求得如和处Nala2Un=+g+昇。n_Nal+721N其中，m”=如,妬就是贝叶斯估计。i=l3.3设玄=仙,血,.,射为来自点二项式分布的样本集,即f(x,P)=PxQxx=O,1,OP1,Q=1-P,试求参数P的最大似然估计。解：似然函数为：NL(F)=In(严(1-P)(7)i=iNN两边对卩求导可得dL_1XiNdPP1-P+1-P1N所以p得最大似然估计为：心命。t=l3.4假设损失函数为二次函数A(P,P)=(P-P)2,以及P的先验密度为均匀分布/(P)=l,0P0,叼是在超平面上的投影点，则wFq十w

10、o=0o设到平面的距离为r,则=侖，所以wTx-wTxp=r|w|,得至b=WTX+w0_ff(x)IMI=o龙在超平面负侧时g)则g(e)=a%映射g=l,x,x2T把一条直线映射为三维空间中的一条抛物线。4.4对于二维线性判别函数g)=xi+2x2-2-(1)将判别函数写=wTx-|-wo的形式，并画出g(x)=0的几何图形；-(2)映射成广义齐次线性函数-(3)指出上述X空间实际是Y空间的一个子空间，且aTy=0于X子空间的划分和原空间中沪十毗=0对原X空间的划分相同，并在图上表示出来。解：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空间中的一个平面i=1上。4.5指岀在Fisher线性判别中，的比例因子对Fisher判别结果无影响。解：假设乘一比例因子a,aw,经过投影后得到y=awTx.相当于对所有样本乘以一个比例因子，所以对判别结果没有影响。4.6证明两向量外积组成的矩阵一般是奇异的。证明：设两向量a,6eR它们的外积为：A=abT,因为a庐与汗a有相同的非零特征值，容易得到4的特征值为卩a,0,0,.,0。有零特征值肯定是奇异的，除非汕=1。n1力2图2:g(x)=0的几何图形4.8证明在正态等方差条

12、件下，Fisher线性判别等价于贝叶斯判别。证明：在正态等方差的条件下，判别函数g(:r)=wTx+w0中3=仙-恋),在Fisher线性判别中最优投影方向为：=刀-1(如-tz2)o4.9证明-(1)弓I入余量6以后的解区(aTVib)位于原来的解区%0)之中；-(2)与原解区边界之间的距离为侖。解：(1)设m满足也b,则它一定也满&aTyi0,所以引入余量后的解区位于原来的解区aTy0之中。(2)aTyi6区边界为：aTyi=6,aTyi0解区边界为:aTyi=0,aTyi=6至临=0的距离为4.10证明，在几何上，感知器准则函数正比于被错分类样本到决策面的距离之和。证明：感知器准则函数为

13、J(a)=(-aT2/)o决策面方程为：aTy=0o当y为错分类样本时，有fy0,到决策面的距离为-/眇所有错分类样本到决策面的距离之和为刀(-a珥/),就是感知器准则函数。模式识别(第二版)习题解答1 为了进一步减小计算量和存储量，可以将上述算法修改为(单样本修正)a(l)Ia(k+1)=a(k)-pk(a(k)Tyk-bk)yk让随着上的增加而逐渐减小，以确保算法收敛。一般选择乐=,还有泸和前面感知器准则函数中的单样本修正法一样，是在无限重复序列中的错分类样本。4.13证明矩阵恒等式(A+xx114-bd-11+xTAlx模式识别(第二版)习题解答1 #利用上试结果证明式(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十她罠利用上面的结果可以得到：R(k+1)=R(k)-R(k)yfcy：Rg1+yR(k)yk4.14考虑准则函数其中乡(a)是使aTyVJ(a)时，梯度下降法的迭代公式为:证明：S是罗)中的唯一样本，则准则函数为丿(a)=刀(叭-厅=-&)2,心(a)所以J(a)=2(aTyi-b)yi,二阶偏导数矩阵为D=2yiyo梯度下降的迭代公式为：丑+1=

15、%PNJgPk=J少秽丁叫S(ayi-b)2yyYyyiT,将朋代入梯度下降的迭代公式：a中=丑+兽詳5yir模式识别(第二版)习题解答 4.15证明：当取MSE解等价于Fisher解。Xi-X2、a=w0,wT51IJyrya=YTby化为:品-iririi&xfXJ-I2x2wj-lx?-if囂Wq设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上面的等式可以分解岀两个等式，第一个得到wo=-m

16、Tw,将30代入第二个等式可以得到-(Nimi十N2m2)(Mmi+N2m，2)T+Sw+Nimirn+N2m，2rnw=N(mm2)点Sy+(mi一m2)(mi-m2)Tw=mi一m2注意因为八导(mi-m2)(mi-m2)Twmi-g的方向上，所以上式可以化为：Sw=a(mi-m2)与Fisher的解相同。4.16证明:-式(4413)表示的向量表示g到X空间中超平面的投影。wLWJ-(2)该投影正交于X空间的超平面。证明：(1)先证明这个向量在X空间中的超平面上，再证明g(0臨llll2LWJ/的向量为X空间中超平面的法向量。X空间中的超平面的方程为：g(x)=wTx+XOX0=l,wT

17、翳|W=O,又因知-卩-0将向量代入g（叭得迅-歸aTyA-aTyII训2W)II训$W4.17在多类问题中，如果一组样本可被一线性机全部正确分类，则称这组样本是线性可分的。对任意类，如果能用一超平面把g类的样本同其他样本分开来，则称总体线性可分。举例说明，总体线性可分必定线性可分，但反之不然。解：模式识别(第二版)习题解答 #模式识别(第二版)习题解答 #图3:总体线性可分必定线性可分模式识别(第二版)习题解答 #模式识别(第二版)习题解答 图4:线性可分未必总体线性可分4.18设有一组样本。若存在c（c-1）/2个超平面丹巧，使H巧把属于叫类的样本同属于吗类的样本分开，则称这组样本是成对线

18、性可分的。举列说明，成对线性可分的样本不一定线性可分。图5:成对线性可分不一定定线性可分5非线性判别函数5.1举例说明分段线性分界面可以逼近贝叶斯判别函数确定的超曲面。解：分段线性函数是一类特殊的非线性函数，它确定的决策面由若干个平面段组成,所以它可以逼近各种形状的超曲面。5.2已知两类问题如图6所示，其中、x”表示类训练样本集合的原型，、O“表示如类训练样本集的原型。-(1)找出紧互对原型集合夕；-(2)找出与紧互对行集相联系的超平面集#;-(3)假设训练集样本与原型完全相同，找岀由超平面集#产生的z(rr)。图6:一个两类问题的原型分布解：(1)用坐标来表示样本中的样本(4,6)与血中的样

19、本(5,5)是紧互对原型，(3,4)与(3,2)是，(2,5)与(1,3)也是。如图7所示(2)如图8所示6近邻法6.1举例说明最近邻决策面是分段线性的。解：分段线性函数的决策面由若干个超平面组成。由于它的基本组成仍然是超平面,因此，与一般超平面6.2证明式(6-14)(618)o证明：记CP2(Wix)=P2(wmx)+工P2(Wix)=1im图7:紧互对原型6.3在什么情况下，最近邻平均误差P达到其上界6.5有7个二维向量：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,假定前三个为类，后四个为类。-(1)画出最近邻法决策面；-(2)求样本均值尬1,尬2,若按离样本均值距离的大小进行分类，试画岀决策面。解：第一首先要明确什么是“最近邻法”？它实际是一种分段的线性判别函数。第二根据离样本均值的距离来分类，首先求出两类的样本均值，分类决策面就是样本均值的垂直平分线。如图9所示。类的均值为=(l,0)r,地类的均值为TH2=(1,0)T,决策面如图10所示。6.6画岀炉近邻法得程序框图。解：取未知样本为的上近邻，看这公近邻中多数属于哪一类，就把龙归为那一类。6.7对于有限样本，重复剪辑是否比两分剪辑的特性要好。6.8证明如果B+D(Xi,Mp)D(x,Mp)=)D(x,Mp)-D(