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

《《模式识别》(边肇祺)习题答案.pdf》由会员分享，可在线阅读，更多相关《《模式识别》(边肇祺)习题答案.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别(第二版)习题解答目录1绪论22贝叶斯决策理论23概率密度函数的估计84线性判别函数105非线性判别函数166近邻法167经验风险最小化和有序风险最小化方法188特征的选取和提取189基于K-L展开式的特征提取2010 非监督学习方法221模式识别(第二版)习题解答1绪论略2贝叶斯决策理论 2.1 如果只知道各类的先验概率，最小错误率贝叶斯决策规则应如何表示？解：设一个有C类，每一类的先验概率为P(wi)，i=1,.,C。此时最小错误率贝叶斯决策规则为：如果i=maxiP(wi)，则x wi。2.2 利用概率论中的乘法定理和全概率公式证明贝叶斯公式（教材中下面的公式有错误）P(wi|x

2、)=p(x|wi)P(wi)p(x).证明：P(wi|x)=P(wi,x)p(x)=p(x|wi)P(wi)p(x)2.3 证明：在两类情况下P(wi|x)+P(w2|x)=1。证明：P(w1|x)+P(w2|x)=P(w1,x)p(x)+P(w2,x)p(x)=P(w1,x)+P(w2,x)p(x)=p(x)p(x)=1 2.4 分别写出在以下两种情况1.P(x|w1)=P(x|w2)2.P(w1)=P(w2)下的最小错误率贝叶斯决策规则。解：当P(x|w1)=P(x|w2)时，如果P(w1)P(w2)，则x w1，否则x w2。当P(w1)=P(w2)时，如果P(x|w1)P(x|w2)，

3、则x w1，否则x w2。2.51.对c类情况推广最小错误率率贝叶斯决策规则；2.指出此时使错误率最小等价于后验概率最大，即P(wi|x)P(wj|x)对一切j=i成立时，x wi。2模式识别(第二版)习题解答解：对于c类情况，最小错误率贝叶斯决策规则为：如果 P(wi|x)=maxj=1,.,cP(wj|x)，则x wi。利用贝叶斯定理可以将其写成先验概率和类条件概率相联系的形式，即如果 p(x|wi)P(wi)=maxj=1,.,cp(x|wj)P(wj)，则x wi。2.6 对两类问题，证明最小风险贝叶斯决策规则可表示为，若p(x|w1)p(x|w2)(12 22)P(w2)(21 11

4、)P(w1),则x w1，反之则属于w2。解：计算条件风险R(1|x)=2j=11jP(wj|x)=11P(w1|x)+12P(w2|x)R(2|x)=2j=12jP(wj|x)=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)p(x|w2)(12 22)P(w2)(21 11)P(w1)所以，如果p(x|w1)p(x|w2)(12 22)P(w2)(21 11)P(w1)，则x w1。反之则x w2。2.7

5、 若11=22=0,12=21，证明此时最小最大决策面是来自两类的错误率相等。解：最小最大决策时满足(11 22)+(21 11)R2p(x|w1)dx (12 22)R1p(x|w2)dx=0容易得到R1p(x|w2)dx=R2p(x|w1)dx所以此时最小最大决策面使得P1(e)=P2(e)2.8 对于同一个决策规则判别函数可定义成不同形式，从而有不同的决策面方程，指出决策区域是不变的。3模式识别(第二版)习题解答解：对于同一决策规则（如最小错误率贝叶斯决策规则），它的判别函数可以是j=maxj=1,.,cP(wj|x)，则x wj。另外一种形式为j=maxj=1,.,cp(x|wj)P(

6、wj)，则x wj。考虑两类问题的分类决策面为：P(w1|x)=P(w2|x)，与p(x|w1)P(w1)=p(x|w2)P(w2)是相同的。2.9 写出两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程。2.10 随机变量l(x)定义为l(x)=p(x|w1)p(x|w2)，l(x)又称为似然比，试证明(1)Eln(x)|w1=Eln+1(x)|w2(2)El(x)|w2=1(3)El(x)|w1 E2l(x)|w2=varl(x)|w2（教材中题目有问题）证明：对于(1)，Eln(x)|w1=ln(x)p(x|w1)dx=(p(x|w1)n+1(p(x|w2)ndx又Eln+1(x)|

7、w2=ln+1p(x|w2)dx=(p(x|w1)n+1(p(x|w2)ndx 所以，Eln(x)|w1=Eln+1(x)|w2对于(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)|w2 2.11 xj(j=1,2,.,n)为n个独立随机变量，有Exj|wi=ij，varxj|wi=i2j22，计算在11=22=0 及12=21=1的情况下，由贝叶斯决策引起的错误率。（中心极限定理）解：在0 1损失下，最小风险贝叶斯决策与最小错误率贝叶斯决策等价。2.12 写出离

8、散形式的贝叶斯公式。解：P(wi|x)=P(x|wi)P(x)cj=1P(x|wi)P(wi)2.13 把连续情况的最小错误率贝叶斯决策推广到离散情况，并写出其判别函数。2.14 写出离散情况条件风险R(ai|x)的定义，并指出其决策规则。解：R(ai|x)=cj=1ijP(wj|x)=cj=1ijp(x|wj)P(wj)/omit the same part p(x)R(ak|x)=minj=1,2,.,NR(aj|x)，则ak就是最小风险贝叶斯决策。2.15 证明多元正态分布的等密度点轨迹是一个超椭球面，且其主轴方向由的特征向量决定，轴长度由的特征值决定。证明：多元正态分布的等密度点满足：

9、xT1x=C，C为常数。4模式识别(第二版)习题解答 2.16 证明Mahalanobis距离r符合距离定义三定理，即(1)r(a,b)=r(b,a)(2)当且仅当a=b时，r(a,b)=0(3)r(a,c)r(a,b)+r(b,c)证明：(1)r(a,b)=(a b)T1(a b)=(b a)T1(b a)=r(b,a)(2)为半正定矩阵所以r(a,b)=(ab)T1(ab)0，只有当a=b时，才有r(a,b)=0。(3)1可对角化，1=PPT 2.17 若将1矩阵写为：1=h11h12h1dh12h22h2d.h1dh2dhdd，证明Mahalanobis距离平方为2=di=1dj=1hi

10、j(xi ui)(xj uj)证明：2=(x u)Th11h12h1dh12h22h2d.h1dh2dhdd(x u)=di=1dj=1hij(xi ui)(xj uj)2.18 分别对于d=2,d=3证明对应与Mahalanobis距离的超椭球体积是V=Vd|12d 2.19 假定x和m是两个随机变量，并设在给定m时，x的条件密度为p(x|m)=(2)121exp12(x m)2/2再假设m的边缘分布是正态分布，期望值是m0，方差是2m，证明p(m|x)=(3+m)12(2)12mexp122+2m22m(m 2mx+m022+2m)25模式识别(第二版)习题解答证明：p(m|x)=p(x|

11、m)p(m)p(x)=p(x|m)p(m)p(x|m)p(m)dm=(2)121exp12(x m)2/2(2)121mexp12(m m0)2/2m(2)121exp12(x m)2/2(2)121mexp12(m m0)2/2mdm=(3+m)12(2)12mexp122+2m22m(m 2mx+m022+2m)2 2.20 对i=2I的特殊情况，证明(1)若P(wi)=P(wj)，则超平面靠近先验概率较小的类；(2)在甚么情况下，先验概率对超平面的位置影响不大。证明：(1)当P(wi)=P(wj)时，超平面经过x0=12(ui+uj)，则对于先验概率较小的类属于它的区域会减少，所以超平面

12、经过的点会靠近先验概率较小的类。（可以这样理解，具体证明也很简单）(2)？不知道这是什么问题，先验概率不管在什么时候都很重要！2.21 对i=的特殊情况，指出在先验概率不等时，决策面沿ui点与uj点连线向先验概率小的方向移动。证明：同上面一题解释一样。2.24 似然比决策准则为：若 2.23 二维正态分布，u1=(1,0)T,u2=(1,0)T,1=2=I,P(w1)=P(w2)。试写出对数似然比决策规则。解：h(x)=lnl(x)=lnp(x|w1)+lnp(x|w2)=12(x1 u1)T11(x1 u1)12(x2 u2)T12(x2 u2)+12ln|1|2|=12(x u1)T(x

13、u1)(x u2)T(x u2)而，lnP(w1)P(w2)=0。所以判别规则为当(xu1)T(xu1)(xu2)T(xu2)则x w1,反之则s w2。即将x判给离它最近的ui的那个类。2.24 在习题2.23中若1=2，1=112121，2=112121，写出负对数似然比决策规则。6模式识别(第二版)习题解答解：h(x)=lnl(x)=lnp(x|w1)+lnp(x|w2)=12(x1 u1)T11(x1 u1)12(x2 u2)T12(x2 u2)+12ln|1|2|=12xT(11 12)x (11ui 12uj)Tx+12(uT111u1 uT212u2+ln|1|2|)=43x1x

14、2+43x1而，lnP(w1)P(w2)=0。决策面为x1(x2 1)=0，如图1所示xy1图 1:分类决策面 2.25 在习题2.24的情况下，若考虑损失函数11=22=0,12=21，画出似然比阈值与错误率之间的关系。(1)求出P(e)=0.05时完成Neyman-Pearson决策时总的错误率；（P(e)应该为P(e1)或者P(e2)）(2)求出最小最大决策的域值和总的错误率。解：（1）损失函数在0-1损失函数条件下的最小风险贝叶斯决策等价于最小错误率贝叶斯决策。似然比等于0的情况下错误率最小。当P(e1)=0.05时，7模式识别(第二版)习题解答（2）最小最大决策时，(1122)+(2

15、111)R2p(x|w1)dx(1222)R1p(x|w2)dm=0 可以得到，R2p(x|w1)dx=R1p(x|w2)dm，所以R1=(x1,x2)|x1(x2 1)0，R2=(x1,x2)|x1(x2 1)03概率密度函数的估计 3.1 设总体分布密度为N(u,1)，u x。那么此时的最大似然估计为：=maxkxk(3)3.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所以：(A1+B1)1=A(A+B)1B 同理证明(A1+B1)1=B(A+B)1A 3.

16、15 设p(x)N(u,2)，窗函数(x)N(0,1)，指出Parzen窗估计 pN(x)=1NhNNi=1(x xihN)对于小的hN，有如下性质：(1)E pN(x)N(u,2+h2N)(2)V ar pN(x)=1NhN2p(x)证明：(1)E pN(x)=pN(x)p(x)dx8.1 Sw表示类内离散度矩阵，Sb表示类间离散度矩阵4线性判别函数 4.1（1）指出从x到超平面g(x)=wTx+w0=0的距离r=|g(x)|w|是在g(xq)=0的约束条件下，使|x xq|2达到极小解；（2）指出在超平面上的投影是xp=x g(x)|w|2w解：（1）设x在超平面的正侧g(x)0，xq是x

17、在超平面上的投影点，则wTxq+w0=0。设x到平面的距离为r，则x xp=rw|w|，所以wTx wTxp=r|w|，得到r=wTx+w0|w|=g(x)|w|。10模式识别(第二版)习题解答x在超平面负侧时g(x)0)之中；（2）与原解区边界之间的距离为b|yi|。解：（1）设a满足aTyi b，则它一定也满足aTyi 0，所以引入余量后的解区位于原来的解区aTy 0之中。（2）aTyi b解区边界为：aTyi=b，aTyi 0解区边界为：aTyi=0，aTyi=b到aTyi=0的距离为b|yi|。4.10 证明，在几何上，感知器准则函数正比于被错分类样本到决策面的距离之和。证明：感知器准

18、则函数为J(a)=yY(aTy)。决策面方程为：aTy=0。当y为错分类样本时，有aTy 0，到决策面的距离为aTy。所有错分类样本到决策面的距离之和为yY(aTy)，就是感知器准则函数。4.12 写出Widrow-Hoff法程序框图。解：平方误差准则函数J(a)=|Y ab|2=Nn=1(aTynbn)2，它的最小二乘解，伪逆解或MSE解为：a=(YTY)1YTb，采用梯度下降法来求解a。J(a)的梯度为J(a)=2YT(Y a b)，则梯度下降法可以写成a(1)a(k+1)=a(k)kYT(Y a b)，选择k=1k，式中1为任意正常数。12模式识别(第二版)习题解答为了进一步减小计算量和

19、存储量，可以将上述算法修改为（单样本修正）a(1)a(k+1)=a(k)k(a(k)Tyk bk)yk让k随着k的增加而逐渐减小，以确保算法收敛。一般选择k=1k，还有yk和前面感知器准则函数中的单样本修正法一样，是在无限重复序列中的错分类样本。4.13（1）证明矩阵恒等式(A+xxT)1=A1A1xxTA11+xTA1x（2）利用上试结果证明式（4-98）。证明：（1）(A+xxT)(A1A1xxTA11+xTA1x)=(A+xxT)(I A1xxT1+xTA1x)A1=(A+xxTxxT1+xTA1xxxTA1xxT1+xTA1x)A1=AA1=I所以(A+xxT)1=A1A1xxTA11

20、+xTA1x（2）R(k+1)1=R(k)1+ykyTk，利用上面的结果可以得到：R(k+1)=R(k)R(k)ykyTkR(k)1+yTkR(k)yk 4.14 考虑准则函数J(a)=yY(a)(aTy b)2其中Y(a)是使aTy b的样本集合。设y1是Y(a)中的唯一样本，则J(a)的梯度为J(a)=2(aTky1 b)y1，二阶偏导数矩阵D=2y1yT1。据此证明，若最优步长选择为k=|J(a)|2JT(a)DJ(a)时，梯度下降法的迭代公式为：ak+1=ak+b aTky1|y1|2y1证明：y1是Y(a)中的唯一样本，则准则函数为J(a)=yY(a)(aTy b)2=(aTy1 b

21、)2，所以J(a)=2(aTy1 b)y1，二阶偏导数矩阵为D=2y1yT1。梯度下降的迭代公式为：ak+1=akkJ(ak)，k=4(aTky1 b)2|y1|28(aTky1 b)2yT1y1yT1y1=12|y1|2，将k代入梯度下降的迭代公式：ak+1=ak+b aTky1|y1|2y113模式识别(第二版)习题解答 4.15 证明：当取b=NN1,.,NN1|zN1,NN2,.,NN2|zN2MSE解等价于Fisher解。证明：Y=yT1yT2.yTN=11X112X2，a=w0,wT则YTY a=YTb，化为：1T11T2XT1XT211X112X2w0w=1T11T2XT1XT2

22、NN111NN112设m1=1N1iC1xi,m2=1N2iC2xi，上式可化为：N(N1m1+N2m2)T(N1m1+N2m2)Sw+N1m1mT1+N2m2mT2w0w=0N(m1 m2)式中，Sw=2i=1jCi(xj mi)(xj mi)T，且(N1m1+N2m2)T=NmT，m=Ni=1xi，上面的等式可以分解出两个等式，第一个得到w0=mTw，将w0代入第二个等式可以得到1N(N1m1+N2m2)(N1m1+N2m2)T+Sw+N1m1mT1+N2m2mT2w=N(m1 m2)1NSw+N1N2N2(m1 m2)(m1 m2)Tw=m1 m2注意因为N1N2N(m1 m2)(m1

23、m2)Tw在m1 m2的方向上，所以上式可以化为：Sww=(m1 m2)与Fisher的解相同。4.16 证明：(1)式(4-113)表示的向量y aTy|w|20w表示y到X空间中超平面的投影。(2)该投影正交于X空间的超平面。证明：（1）先证明这个向量在X空间中的超平面上，再证明y(y aTy|w|20w)的向量为X空间中超平面的法向量。X空间中的超平面的方程为：g(x)=wTx+14模式识别(第二版)习题解答x0=1,wTx0 x=aTy=0，将向量代入g(x)，得 aTy aTy|w|2aT0w=aTy aTy|w|2|w|2=0，又因为y(y aTy|w|20w)=aTy|w|20w

24、 4.17 在多类问题中，如果一组样本可被一线性机全部正确分类，则称这组样本是线性可分的。对任意wi类，如果能用一超平面把wi类的样本同其他样本分开来，则称总体线性可分。举例说明，总体线性可分必定线性可分，但反之不然。解：acbabccba图 3:总体线性可分必定线性可分图 4:线性可分未必总体线性可分 4.18 设有一组样本。若存在c(c 1)/2个超平面Hij，使Hij把属于wi类的样本同属于wj类的样本分开，则称这组样本是成对线性可分的。举列说明，成对线性可分的样本不一定线性可分。图 5:成对线性可分不一定定线性可分15模式识别(第二版)习题解答5非线性判别函数 5.1 举例说明分段线性

25、分界面可以逼近贝叶斯判别函数确定的超曲面。解：分段线性函数是一类特殊的非线性函数，它确定的决策面由若干个平面段组成，所以它可以逼近各种形状的超曲面。5.2 已知两类问题如图6所示，其中表示w1类训练样本集合的原型，表示w2类训练样本集的原型。(1)找出紧互对原型集合P；(2)找出与紧互对行集相联系的超平面集H；(3)假设训练集样本与原型完全相同，找出由超平面集H 产生的z(x)。1050105图 6:一个两类问题的原型分布解:（1）用坐标来表示样本w1中的样本(4,6)与w2中的样本(5,5)是紧互对原型，(3,4)与(3,2)是，(2,5)与(1,3)也是。如图 7所示（2）如图8所示6近邻

26、法 6.1 举例说明最近邻决策面是分段线性的。解：分段线性函数的决策面由若干个超平面组成。由于它的基本组成仍然是超平面，因此，与一般超平面 6.2 证明式(6 14)(6 18)。证明：记ci=1P2(wi|x)=P2(wm|x)+i=mP2(wi|x)16模式识别(第二版)习题解答1050105图 7:紧互对原型 6.3 在什么情况下，最近邻平均误差P达到其上界 6.5 有7个二维向量：x1=(1,0)T,x2=(0,1)T,x3=(0,1)T,x4=(0,0)T,x5=(0,2)T,x6=(0,2)T,x7=(2,0)T，假定前三个为w1类，后四个为w2类。(1)画出最近邻法决策面；(2)

27、求样本均值m1,m2，若按离样本均值距离的大小进行分类，试画出决策面。解：第一首先要明确什么是“最近邻法”？它实际是一种分段的线性判别函数。第二根据离样本均值的距离来分类，首先求出两类的样本均值，分类决策面就是样本均值的垂直平分线。(1)如图9所示。(2)w1类的均值为m1=(12,0)T，w2类的均值为m2=(1,0)T，决策面如图10所示。6.6 画出k-近邻法得程序框图。解：取未知样本x的k近邻，看这k近邻中多数属于哪一类，就把x归为那一类。6.7 对于有限样本，重复剪辑是否比两分剪辑的特性要好。6.8 证明如果B+D(xi,Mp)D(x,Mp)D(x,xi)D(x,Mp)D(xi,Mp)所以如果当前近邻距离x的距离为B，D(x,xi)D(x,Mp)D(xi,Mp)B，即当B+D(xi,Mp)c,证明使得Je最小的划分中没有空子集。证明：假设存在一个空子集Xk,1 6 k 6 c使得Je最小，容易证明可以找到所有子集都不为空的划分使得Je更小。22