书华工电信模式识别答案版

1、目录12345绪论22810决策理论概率密度函数的估计线性判别函数非线性判别函数近邻法经验风险最小化和有序风险最小化方法特征的选取和提取基于K-L展开式的特征提取非监督学习方法91020221 1绪论略 2决策理论2.1 如果只知道各类的先验概率，最小错误率决策规则应如何表示？解：设一个有C类，每一类的先验概率为P (wi)，i = 1, ., C。此时最小错误率决策规则为：如果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)下的最小错误率决策规则。解： 当P (x|w1) = P (x|w2)时，如果P (w1) P (w2)，则x w1，否则x w2。当P (w1) = P (w2)时，如果P (x|w1) P

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

4、 (w1)则x w1，反之则属于w2。解：计算条件风险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 对于同一个决策规则判别函数可定义成不同形式，从而有不同的决策面方程，决策区域是不变的。3决策规则），它的判别函数可以是j =解： 对于同一决策规则（如最小错误率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 写出两类和多类情况下最小风险决策判别函数和决策面方程。量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损失下，最小风险决策与最小错误率决策等价。2.12 写出离散形式的解：公式。P (x|wi)P (x)P (w |) =i xc j=1P (x|w )P (w )ii2.13 把连续情况的最小错误率决策推广到离散情况，并写出其判别函数。2.14 写出离散情况条件风险R(ai|x)的定义，并解：c其决策规则。R() =P (w |)a |xxiijjj=1c= p(xw )P (w )/omit the same part p(x)|ijjjj=1R(ak|x) =minR(aj|x)，则ak就是最小风险

9、决策。j=1,2,.,N2.15 证明多元正态分布的等密度点轨迹是一个超椭球面，且其主轴方向由的特征向量决定，轴长度由的特征值决定。证明：多元正态分布的等密度点满足：xT 1x = C，C为常数。42.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，只

10、有当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证明对应与Mahalanobis距离的超椭球体积是V = Vd| 2 d2.19 假定x和m是两

11、个随量，并设在给定m时，x的条件密度为 11) exp (x m() = (21) /22px|m22再假设m的边缘分布是正态分布，期望值是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)当P (w ) = P (w )时，超平面经过x0 = 2 (u + u )，则对于先验概率较小的类ijij属于它的区域会减少，所以超平面经过的点会靠近先验概率较小的类。 （可以这样理解，具体证明也很简单）(2)？不知道这是什么问题，先验概率不管在什么时候都很重要！2.21 对i = 的特殊情况，概率小的方向移动。证明：

13、 同上面一题解释一样。2.24 似然比决策准则为：若在先验概率不等时，决策面沿ui点与uj点连线向先验2.23 二维正态分布，u1 = (1, 0)T , u2 = (1, 0)T , 1 = 2 = I, P (w1) = P (w2)。试写出对数似然比决策规则。解：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。所以判别规则为当(xu )

14、(xu ) (xu ) (xu )则x w ,反而，TT111221P (w2)之则s w2。即将x判给离它最近的ui的那个类。= 1121112.24 在习题2.23中若 = ， =，写出负对数似然比决2212121121策规则。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 在习题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时，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概率密度函数的估计3.1 设总体分布密度为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 设p(x) N (u, 2)，窗函数(x) N (0, 1)，Parzen窗估计()N1x xi(x) =NhNhNi=1对于小的hN ，有如下性质： (1) E (2) V ar () N (u, + h )22xN1(x) =2 p(x)NhN证明：(1)E(x) = (x)p(x)dx8.1Sw表示类内离散度矩阵，Sb表示类间离散度矩阵 4线性判别函数|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）设x在超平面的正侧g(x) 0，xq是x在超平面上的投影点，则wT xq + w0 = w 0。设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在超平面负侧时g(x) 0)之中；b （2）与原解区边界之间的距离为。|yi|解：（1）设a满足aT yi b，则它一定也满足aT yi 0，所以引入余量后的解区位于原来的解区aT y 0之中。（2）aT yi b解区边界为：aT yi

19、 = b，aT yi 0解区边界为：baT y = 0，aT y = b到aT y = 0的距离为。iii|yi|4.10 证明，在几何上，感知器准则函数正比于被错分类样本到决策面的距离之和。证明： 感知器准则函数为J (a) =(a y)。决策面方程为：a y = 0。当TTy为错分类yY样本时，有a y 0，到决策面的距离为aT y。所有错分类样本到决策面的距离之和T为(aT y)，就是感知器准则函数。4.12 写出Widrow-Hoff法程序框图。yYN解： 平方误差准则函数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 ，式中 为任意正常数。1k12为了进一步减小计算量和 量，可以将上述算法修改为（单样本修正）a(1)a(k + 1) = a(k) k(a(k)T yk bk)yk让 随着k的增加而逐渐减小，以确保算法收敛。一般选择 = 1 ，还有yk和前面感kkk知器准则函数中的单样本修一样，是在无限重复序列中的错分类样本。4.13A1xxT A1（1）证明矩阵恒等式(A + xxT )1 =1A 1+

21、xT A1x（2）利用上试结果证明式（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 ，利用上面的结果可以得到： R(k + 1) = R(k) kR(k)ykyT R(k)k1+ yT R(k)ykk4.14 考虑准则函数 J(a)= (aT y b)2yY (a)

22、其中Y (a)是使aT y b的样本集合。设y1是Y (a)中的唯一样本，则J(a)的梯度为J(a) =2(aT y1 b)y1，二阶偏导数矩阵D = 2y1yT 。据此证明， 若最优步长选择为k =k1|J(a)|2时，梯度下降法的迭代公式为：JT (a)DJ(a)Tb a y1= ak +kak+1y1|y1|2 证明： y1是Y (a)中的唯一样本，则准则函数为J(a) = (aT y b)2 = (aT y1 b)2，yY (a)J() = 2()y ，二阶偏导数矩阵为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 证明：当取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设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 设有一组样本。若存在c(c 1)/2个超平面Hij，使Hij把属于wi类的样本同属于wj类的样本分开，则称这组样本是成对线性可分的。举列说明，成对线性可分的样本不一定线性可分。图 5: 成对线性可分不一定定线性可分15 5非线性判别函数5.1 举例说明分段线性分界面可以近判别函数确定的超曲面。解： 分段线性函数是一类特殊的非线性函数，它确定的决策面由若干个平面段组成，所以它可以近各种形状的超曲面。5.2 已知两类问题如图6所示，其中表示w1类训练样本集合的原型， 表示w2类训练样本集的原型。找出紧互对原型集合P；找出与紧互对行集相联系的超平面集H ；假设训练集样本与原型完全相同，找出由超平面集H 产生的z(x)。图 6: 一个两类问题