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

'模式识别(第二版)习题解答目录1绪论22贝叶斯决策理论23概率密度函数的估计84线性判别函数105非线性判别函数166近邻法167经验风险最小化和有序风险最小化方法188特征的选取和提取189基于K-L展开式的特征提取2010非监督学习方法221 模式识别(第二版)习题解答§1绪论略§2贝叶斯决策理论•2.1如果只知道各类的先验概率，最小错误率贝叶斯决策规则应如何表示？解：设一个有C类，每一类的先验概率为P(wi)，i=1,...,C。此时最小错误率贝叶斯决策规则为：如果i∗=maxP(w)，则x∈w。iii•2.2利用概率论中的乘法定理和全概率公式证明贝叶斯公式（教材中下面的公式有错误）p(x|wi)P(wi)P(wi|x)=.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(w2|x)=+p(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)，则x∈w1，否则x∈w2。•2.51.对c类情况推广最小错误率率贝叶斯决策规则；2.指出此时使错误率最小等价于后验概率最大，即P(wi|x)>P(wj|x)对一切j̸=i成立时，x∈wi。2 模式识别(第二版)习题解答解：对于c类情况，最小错误率贝叶斯决策规则为：如果P(wi|x)=maxP(wj|x)，则x∈wi。利用贝叶斯定理可以将其写成先验概率和j=1;:::;c类条件概率相联系的形式，即如果p(x|wi)P(wi)=maxp(x|wj)P(wj)，则x∈wi。j=1;:::;c•2.6对两类问题，证明最小风险贝叶斯决策规则可表示为，若p(x|w1)(λ12−λ22)P(w2)>,p(x|w2)(λ21−λ11)P(w1)则x∈w1，反之则属于w2。解：计算条件风险∑2R(α1|x)=λ1jP(wj|x)j=1=λ11P(w1|x)+λ12P(w2|x)∑2R(α2|x)=λ2jP(wj|x)j=1=λ21P(w1|x)+λ22P(w2|x)如果R(α1|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∈w1。反之则x∈w2。p(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=0R2R1容易得到∫∫p(x|w2)dx=p(x|w1)dxR1R2所以此时最小最大决策面使得P1(e)=P2(e)•2.8对于同一个决策规则判别函数可定义成不同形式，从而有不同的决策面方程，指出决策区域是不变的。3 模式识别(第二版)习题解答解：对于同一决策规则（如最小错误率贝叶斯决策规则），它的判别函数可以是j∗=∗maxP(wj|x)，则x∈wj。另外一种形式为j=maxp(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写出两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程。p(x|w1)•2.10随机变量l(x)定义为l(x)=，l(x)又称为似然比，试证明p(x|w2){(1)E{ln(x)|w1}=E{ln+1(x)|w2}{(2)E{l(x)|w2}=1{(3)E{l(x)|w1}−E2{l(x)|w2}=var{l(x)|w2}（教材中题目有问题）∫∫n+1nn(p(x|w1))n+1证明：对于(1)，E{l(x)|w1}=l(x)p(x|w1)dx=ndx又E{l(x)|w2}=(p(x|w2))∫∫n+1n+1(p(x|w1))nn+1lp(x|w2)dx=ndx所以，E{l(x)|w1}=E{l(x)|w2}(p(x|w2))∫∫对于(2)，E{l(x)|w2}=l(x)p(x|w2)dx=p(x|w1)dx=1对于(3)，E{l(x)|w}−E2{l(x)|w}=E{l2(x)|w}−E2{l(x)|w}=var{l(x)|w}12222•2.11xj(j=1,2,...,n)为n个独立随机变量，有E[xj|wi]=ijη，var[xj|wi]=i2j2σ2，计算在λ11=λ22=0及λ12=λ21=1的情况下，由贝叶斯决策引起的错误率。（中心极限定理）解：在0−1损失下，最小风险贝叶斯决策与最小错误率贝叶斯决策等价。•2.12写出离散形式的贝叶斯公式。解：P(x|wi)P(x)P(wi|x)=∑cj=1P(x|wi)P(wi)•2.13把连续情况的最小错误率贝叶斯决策推广到离散情况，并写出其判别函数。•2.14写出离散情况条件风险R(ai|x)的定义，并指出其决策规则。解：∑cR(ai|x)=λijP(wj|x)j=1∑c=λijp(x|wj)P(wj)////omitthesamepartp(x)j=1R(ak|x)=minR(aj|x)，则ak就是最小风险贝叶斯决策。j=1;2;:::;N•2.15证明多元正态分布的等密度点轨迹是一个超椭球面，且其主轴方向由的特征向量决定，轴长度由的特征值决定。证明：多元正态分布的等密度点满足：xT−1x=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)T−1(a−b)=(b−a)T−1(b−a)=r(b,a)(2)为半正定矩阵所以r(a,b)=(a−b)T−1(a−b)≥0，只有当a=b时，才有r(a,b)=0。(3)−1可对角化，−1=PPTh11h12···h1dh12h22···h2d•2.17若将−1矩阵写为：−1=.....，证明Mahalanobis距离平方为.......h1dh2d···hdd∑d∑dγ2=h(x−u)(x−u)ijiijji=1j=1证明：h11h12···h1dh12h22···h2dγ2=(x−u)T(x−u)............h1dh2d···hdd∑d∑d=hij(xi−ui)(xj−uj)i=1j=11d•2.18分别对于d=2,d=3证明对应与Mahalanobis距离γ的超椭球体积是V=Vd||2γ•2.19假定x和m是两个随机变量，并设在给定m时，x的条件密度为{}1−1122p(x|m)=(2π)2σexp−(x−m)/σ2再假设m的边缘分布是正态分布，期望值是m0，方差是σm2，证明1[()2]32222(σ+σm)21σ+σmσmx+m0σp(m|x)=exp−m−12σ2σ2σ2+σ2(2π)2σσmmm5 模式识别(第二版)习题解答证明：p(x|m)p(m)p(m|x)=p(x)p(x|m)p(m)=∫p(x|m)p(m)dm1{}1{}−1122−1122(2π)2σexp−2(x−m)/σ(2π)2σmexp−2(m−m0)/σm=∫1{}1{}(2π)2σ−1exp−1(x−m)2/σ2(2π)2σm−1exp−1(m−m0)2/σ2dm[22]m3122(22)2(σ+σm)21σ+σmσmx+m0σ=exp−m−12σ2σ2σ2+σ2(2π)2σσmmm•2.20对i=σ2I的特殊情况，证明{(1)若P(wi)̸=P(wj)，则超平面靠近先验概率较小的类；{(2)在甚么情况下，先验概率对超平面的位置影响不大。1证明：(1)当P(wi)=P(wj)时，超平面经过x0=(ui+uj)，则对于先验概率较小的类2属于它的区域会减少，所以超平面经过的点会靠近先验概率较小的类。（可以这样理解，具体证明也很简单）(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)=−ln[l(x)]=−lnp(x|w1)+lnp(x|w2)1T−11T−11|1|=(x1−u1)1(x1−u1)−(x2−u2)2(x2−u2)+ln222|2|1[]=(x−u)T(x−u)−(x−u)T(x−u)11222[]而，lnP(w1)=0。所以判别规则为当(x−u)T(x−u)>(x−u)T(x−u)则x∈w,反P(w2)11221之则s∈w2。即将x判给离它最近的ui的那个类。[][]111−1•2.24在习题2.23中若1̸=2，1=12，2=12，写出负对数似然比决1−122策规则。6 模式识别(第二版)习题解答解：h(x)=−ln[l(x)]=−lnp(x|w1)+lnp(x|w2)1T−11T−11|1|=(x1−u1)1(x1−u1)−(x2−u2)2(x2−u2)+ln222|2|1T−1−1−1−1Tx(1−2)x−(1ui−2uj)x+2=1T−1T−1|1|(u11u1−u22u2+ln)2|2|44=−x1x2+x133[]P(w1)而，lnP(w2)=0。决策面为x1(x2−1)=0，如图1所示y1x图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）最小最大决策时，(λ11−λ22)+(λ21−λ11)p(x|w1)dx−(λ12−λ22)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概率密度函数的估计•3.1设总体分布密度为N(u,1)，−∞x。那么此时θ的最大似然估计为：θ∗=maxx(3)kk•3.8利用矩阵恒等式(A−1+B−1)−1=A(A+B)−1B=B(A+B)−1A证明：(A−1+B−1)A(A+B)−1B=(I+B−1A)(A+B)−1B=B−1(B+A)(A+B)−1B=B−1B=I所以：(A−1+B−1)−1=A(A+B)−1B同理证明(A−1+B−1)−1=B(A+B)−1A•3.15设p(x)∼N(u,σ2)，窗函数φ(x)∼N(0,1)，指出Parzen窗估计N()1∑x−xip^N(x)=φNhNhNi=1对于小的hN，有如下性质：{(1)E[^p(x)]∼N(u,σ2+h2)NN1{(2)Var[^pN(x)]=√p(x)NhN2π证明：∫(1)E[^pN(x)]=p^N(x)p(x)dx8.1Sw表示类内离散度矩阵，Sb表示类间离散度矩阵§4线性判别函数|g(x)|•4.1（1）指出从x到超平面g(x)=wTx+w0=0的距离r=是在g(xq)=0的约束||w||条件下，使||x−xq||2达到极小解；g(x)（2）指出在超平面上的投影是xp=x−w||w||2解：（1）设x在超平面的正侧g(x)>0，xq是x在超平面上的投影点，则wTxq+w0=wTT0。设x到平面的距离为r，则x−xp=r，所以wx−wxp=r||w||，得到r=||w||wTx+w0g(x)=。||w||||w||10 模式识别(第二版)习题解答−wTx−w0−g(x)x在超平面负侧时g(x)<0，得r==。||w||||w|||g(x)|所以r=||w||wg(x)g(x)（2）x在超平面正侧时，x−xp=r||w||=||w||2w，所以xp=x−||w||2w；当x在超wg(x)g(x)平面的负侧时，x−xp=−r||w||=||w||2w，所以xp=x−||w||2w。•4.3设有一维空间二次判别函数g(x)=5+7x+9x2{(1)试映射成广义齐次线性判别函数；{(2)总结把高次函数映射成齐次线性函数的方法。解：（1）设y=[y1,y2,y3]T=[1,x,x2]T，a=[5,7,9]T，则广义齐次线性判别函数为：g(x)=aTy（2）对于n次函数g(x)=c0+c1x+c2x2+...+cnxn，令y=[y1,y2,...,yn+1]T=[1,x,...,xn]T，a=[c0,c1,...,cn]T，则g(x)=aTy。•4.3（1）通过映射把一维二次判别函数g(x)=a1+a2x+a3x2映射成三维广义线性判别函数；（2）若x在一维空间具有分布密度p(x)，说明三维空间中的分布退化成只在一条曲线上有值，且曲线上值无穷大。解：（1）y=[1,x,x2]T，a=[a1,a2,a3]T，则g(x)=aTy。（2）映射y=[1,x,x2]T把一条直线映射为三维空间中的一条抛物线。•4.4对于二维线性判别函数g(x)=x1+2x2−2{（1）将判别函数写成g(x)=wTx+w0的形式，并画出g(x)=0的几何图形；{（2）映射成广义齐次线性函数g(x)=aTy；{（3）指出上述X空间实际是Y空间的一个子空间，且aTy=0对于X子空间的划分和原空间中wT+w0=0对原X空间的划分相同，并在图上表示出来。解：（1）w=[1,2]T,x=[x1,x2]T,w0=−2，则g(x)=wTx+w0，g(x)=0的图形如下图2：（2）y=[y1,y2,y3]T=[1,x1,x2]T，a=[−2,1,2]T，则g(x)=aTy。（3）y1=1,y2=x1,y3=x2，在所以所有的样本在Y空间中的一个平面y1=1上。•4.5指出在Fisher线性判别中，w的比例因子对Fisher判别结果无影响。解：假设w乘一比例因子α，αw，经过投影后得到y=αwTx。相当于对所有样本乘以一个比例因子，所以对判别结果没有影响。•4.6证明两向量外积组成的矩阵一般是奇异的。证明：设两向量a,b∈Rn，它们的外积为：A=abT，因为abT与bTa有相同的非零特征值，容易得到A的特征值为bTa,0,0,...,0。有零特征值肯定是奇异的，除非n=1。|{z}n−111 模式识别(第二版)习题解答x212x1图2:g(x)=0的几何图形•4.8证明在正态等方差条件下，Fisher线性判别等价于贝叶斯判别。证明：在正态等方差的条件下，判别函数g(x)=wTx+w0中w=−1(u1−u2)，在Fisher线性判别中最优投影方向为：w=−1(u1−u2)。•4.9证明{（1）引入余量b以后的解区(aTyi≥b)位于原来的解区(aTyi>0)之中；b{（2）与原解区边界之间的距离为。||yi||解：（1）设a∗满足aTyi≥b，则它一定也满足aTyi>0，所以引入余量后的解区位于原来的解区aTy>0之中。（2）aTyi≥b解区边界为：aTyi=b，aTyi>0解区边界为：baTyi=0，aTyi=b到aTyi=0的距离为。||yi||•4.10证明，在几何上，感知器准则函数正比于被错分类样本到决策面的距离之和。∑证明：感知器准则函数为J(a)=(−aTy)。决策面方程为：aTy=0。当y为错分类y∈Y样本时，有aTy≤0，到决策面的距离为−aTy。所有错分类样本到决策面的距离之和∑为(−aTy)，就是感知器准则函数。y∈Y•4.12写出Widrow-Hoff法程序框图。∑N解：平方误差准则函数J(a)=||Ya−b||2=(aTy−b)2，它的最小二乘解，伪逆解nnn=1或MSE解为：a∗=(YTY)−1YTb，采用梯度下降法来求解a∗。J(a)的梯度为∇J(a)={Ta(1)2Y(Ya−b)，则梯度下降法可以写成T，选择ρk=a(k+1)=a(k)−ρkY(Ya−b)ρ1，式中ρ1为任意正常数。k12 模式识别(第二版)习题解答为了进一步减小计算量和存储量，可以将上述算法修改为（单样本修正）{a(1)a(k+1)=a(k)−ρk(a(k)Tyk−bk)ykρ1k让ρk随着k的增加而逐渐减小，以确保算法收敛。一般选择ρk=，还有y和前面感k知器准则函数中的单样本修正法一样，是在无限重复序列中的错分类样本。•4.13A−1xxTA−1{（1）证明矩阵恒等式(A+xxT)−1=A−1−1+xTA−1x{（2）利用上试结果证明式（4-98）。证明：（1）()()T−1A−1xxTA−1TA−1xxT−1(A+xx)A−=(A+xx)I−A1+xTA−1x1+xTA−1x()TxxTxxTA−1xxT−1=A+xx−−A1+xTA−1x1+xTA−1x=AA−1=IA−1xxTA−1所以(A+xxT)−1=A−1−1+xTA−1x（2）R(k+1)−1=R(k)−1+ykyT，利用上面的结果可以得到：R(k+1)=R(k)−kR(k)ykyTR(k)k1+yTR(k)ykk•4.14考虑准则函数∑J(a)=(aTy−b)2y∈Y(a)其中Y(a)是使aTy≤b的样本集合。设y1是Y(a)中的唯一样本，则J(a)的梯度为∇J(a)=2(aTy1−b)y1，二阶偏导数矩阵D=2y1y1T。据此证明，若最优步长选择为ρk=k||∇J(a)||2时，梯度下降法的迭代公式为：∇JT(a)D∇J(a)b−aTy1a=a+kyk+1k21||y1||∑证明：y是Y(a)中的唯一样本，则准则函数为J(a)=(aTy−b)2=(aTy−b)2，11y∈Y(a)所以∇J(a)=2(aTy1−b)y1，二阶偏导数矩阵为D=2y1y1T。4(aTy1−b)2||y1||21梯度下降的迭代公式为：a=a−ρ∇J(a)，ρ=k=k+1kkkk8(aTy−b)2yTyyTy2||y||2k111111b−aTy1，将ρ代入梯度下降的迭代公式：a=a+kykk+1k21||y1||13 模式识别(第二版)习题解答•4.15证明：当取NNNNb=,...,,,...,N1N1N2N2|{z}|{z}N1N2MSE解等价于Fisher解。yT1yT[]211X1TTT证明：Y=.=，a=[w0,w]则YYa=Yb，化为：..−12−X2yTN[][][][][]1T−1T1Xw1T−1TN112110=12N11XT−XT−1−XwXT−XTN1122212N121∑1∑设m1=xi,m2=xi，上式可化为：N1N2i∈C1i∈C2[][][]N(N1m1+N2m2)Tw00TT=(N1m1+N2m2)Sw+N1m1m1+N2m2m2wN(m1−m2)∑2∑∑N式中，S=(x−m)(x−m)T，且(Nm+Nm)T=NmT，m=x，wjiji1122ii=1j∈Cii=1上面的等式可以分解出两个等式，第一个得到w0=−mTw，将w0代入第二个等式可以得到[]1TTT−(N1m1+N2m2)(N1m1+N2m2)+Sw+N1m1m1+N2m2m2w=N(m1−m2)N[]1N1N2TSw+2(m1−m2)(m1−m2)w=m1−m2NNN1N2T注意因为(m1−m2)(m1−m2)w在m1−m2的方向上，所以上式可以化为：NSww=α(m1−m2)与Fisher的解相同。•4.16证明：[]aTy0{(1)式(4-113)表示的向量y−表示y到X空间中超平面的投影。||w||2w{(2)该投影正交于X空间的超平面。([])aTy0证明：（1）先证明这个向量在X空间中的超平面上，再证明y−y−||w||2w的向量为X空间中超平面的法向量。X空间中的超平面的方程为：g(x)=wTx+14 模式识别(第二版)习题解答[][]xaTy0x=[1,wT]0=aTy=0，将向量代入g(x)，得aTy−aT=aTy−0x2w||w||([])[]aTy2aTy0aTy0||w||=0，又因为y−y−=||w||2||w||2w||w||2w•4.17在多类问题中，如果一组样本可被一线性机全部正确分类，则称这组样本是线性可分的。对任意wi类，如果能用一超平面把wi类的样本同其他样本分开来，则称总体线性可分。举例说明，总体线性可分必定线性可分，但反之不然。解：aaccacbbb图3:总体线性可分必定线性可分图4:线性可分未必总体线性可分•4.18设有一组样本。若存在c(c−1)/2个超平面Hij，使Hij把属于wi类的样本同属于wj类的样本分开，则称这组样本是成对线性可分的。举列说明，成对线性可分的样本不一定线性可分。图5:成对线性可分不一定定线性可分15 模式识别(第二版)习题解答§5非线性判别函数•5.1举例说明分段线性分界面可以逼近贝叶斯判别函数确定的超曲面。解：分段线性函数是一类特殊的非线性函数，它确定的决策面由若干个平面段组成，所以它可以逼近各种形状的超曲面。•5.2已知两类问题如图6所示，其中``×""表示w1类训练样本集合的原型，``⃝""表示w2类训练样本集的原型。{(1)找出紧互对原型集合P；{(2)找出与紧互对行集相联系的超平面集H；{(3)假设训练集样本与原型完全相同，找出由超平面集H产生的z(x)。1050510图6:一个两类问题的原型分布解:（1）用坐标来表示样本w1中的样本(4,6)与w2中的样本(5,5)是紧互对原型，(3,4)与(3,2)是，(2,5)与(1,3)也是。如图7所示（2）如图8所示§6近邻法•6.1举例说明最近邻决策面是分段线性的。解：分段线性函数的决策面由若干个超平面组成。由于它的基本组成仍然是超平面，因此，与一般超平面•6.2证明式(6−14)∼(6−18)。证明：记∑c∑P2(w|x)=P2(w|x)+P2(w|x)imii=1i̸=m16 模式识别(第二版)习题解答1050510图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)求样本均值m1,m2，若按离样本均值距离的大小进行分类，试画出决策面。解：第一首先要明确什么是“最近邻法”？它实际是一种分段的线性判别函数。第二根据离样本均值的距离来分类，首先求出两类的样本均值，分类决策面就是样本1T均值的垂直平分线。(1)如图9所示。(2)w1类的均值为m1=(,0)，w2类的均值2为m=(−1,0)T，决策面如图10所示。2•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,16k6c使得Je最小，容易证明可以找到所有子集都不为空的划分使得Je更小。22'