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

模式识别(第二版)习题解答 目录 1 绪论 2 2 贝叶斯决策理论 2 3 概率密度函数的估计 8 4 线性判别函数 10 5 非线性判别函数 16 6 近邻法 16 7 经验风险最小化和有序风险最小化方法 18 8 特征的选取和提取 18 9 基于K-L展开式的特征提取 20 10 非监督学习方法 22 1 模式识别(第二版)习题解答 x 1 绪论 略 x 2 贝叶斯决策理论 � 2.1如果只知道各类的先验概率，最小错误率贝叶斯决策规则应如何表示？ 解：设一个有C类，每一类的先验概率为P (wi)，i = 1; :::; C。此时最小错误率贝叶斯 决策规则为：如果i� = max i P (wi)，则x 2 wi。 � 2.2利用概率论中的乘法定理和全概率公式证明贝叶斯公式（教材中下面的公式有错 误） P (wijx) = p(xjwi)P (wi) p(x) : 证明： P (wijx) = P (wi; x) p(x) = p(xjwi)P (wi) p(x) � 2.3证明：在两类情况下P (wijx) + P (w2jx) = 1。 证明： P (w1jx) + P (w2jx) = 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 (xjw1) = P (xjw2) 2. P (w1) = P (w2) 下的最小错误率贝叶斯决策规则。 解：当P (xjw1) = P (xjw2)时，如果P (w1) > P (w2)，则x 2 w1，否则x 2 w2。 当P (w1) = P (w2)时，如果P (xjw1) > P (xjw2)，则x 2 w1，否则x 2 w2。 � 2.5 1. 对c类情况推广最小错误率率贝叶斯决策规则； 2. 指出此时使错误率最小等价于后验概率最大，即P (wijx) > P (wj jx)对一切j 6= i 成立时，x 2 wi。 2 BBQ 椭圆形 BBQ 椭圆形 模式识别(第二版)习题解答 解：对于c类情况，最小错误率贝叶斯决策规则为： 如果 P (wijx) = max j=1;:::;c P (wj jx)，则x 2 wi。利用贝叶斯定理可以将其写成先验概率和 类条件概率相联系的形式，即 如果 p(xjwi)P (wi) = max j=1;:::;c p(xjwj)P (wj)，则x 2 wi。 � 2.6对两类问题，证明最小风险贝叶斯决策规则可表示为，若 p(xjw1) p(xjw2) > (�12 � �22)P (w2) (�21 � �11)P (w1) ; 则x 2 w1，反之则属于w2。 解：计算条件风险 R(�1jx) = 2X j=1 �1jP (wj jx) = �11P (w1jx) + �12P (w2jx) R(�2jx) = 2X j=1 �2jP (wj jx) = �21P (w1jx) + �22P (w2jx) 如果R(�1jx) < R(�2jx)，则x 2 w1。 �11P (w1jx) + �12P (w2jx) < �21P (w1jx) + �22P (w2jx) (�21 � �11)P (w1jx) > (�12 � �22)P (w2jx) (�21 � �11)P (w1)p(xjw1) > (�12 � �22)P (w2)p(xjw2) p(xjw1) p(xjw2) > (�12 � �22)P (w2) (�21 � �11)P (w1) 所以，如果p(xjw1) p(xjw2) > (�12 � �22)P (w2) (�21 � �11)P (w1)，则x 2 w1。反之则x 2 w2。 � 2.7若�11 = �22 = 0; �12 = �21，证明此时最小最大决策面是来自两类的错误率相等。 解：最小最大决策时满足 (�11 � �22) + (�21 � �11) Z R2 p(xjw1)dx� (�12 � �22) Z R1 p(xjw2)dx = 0 容易得到 Z R1 p(xjw2)dx = Z R2 p(xjw1)dx 所以此时最小最大决策面使得P1(e) = P2(e) � 2.8对于同一个决策规则判别函数可定义成不同形式，从而有不同的决策面方程，指出 决策区域是不变的。 3 BBQ 椭圆形 模式识别(第二版)习题解答 解： 对于同一决策规则（如最小错误率贝叶斯决策规则），它的判别函数可以是j� = max j=1;:::;c P (wj jx)，则x 2 wj�。另外一种形式为j� = max j=1;:::;c p(xjwj)P (wj)，则x 2 wj�。 考虑两类问题的分类决策面为：P (w1jx) = P (w2jx)，与p(xjw1)P (w1) = p(xjw2)P (w2) 是相同的。 � 2.9写出两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程。 � 2.10随机变量l(x)定义为l(x) = p(xjw1) p(xjw2)，l(x)又称为似然比，试证明 { (1) Efln(x)jw1g = Efln+1(x)jw2g { (2) Efl(x)jw2g = 1 { (3) Efl(x)jw1g � E2fl(x)jw2g = varfl(x)jw2g（教材中题目有问题） 证明：对于(1)，Efln(x)jw1g = Z ln(x)p(xjw1)dx = Z (p(xjw1))n+1 (p(xjw2))n dx又Efl n+1(x)jw2g =Z ln+1p(xjw2)dx = Z (p(xjw1))n+1 (p(xjw2))n dx所以，Efl n(x)jw1g = Efln+1(x)jw2g 对于(2)，Efl(x)jw2g = Z l(x)p(xjw2)dx = Z p(xjw1)dx = 1 对于(3)，Efl(x)jw1g � E2fl(x)jw2g = Efl2(x)jw2g � E2fl(x)jw2g = varfl(x)jw2g � 2.11 xj(j = 1; 2; :::; n)为n个独立随机变量，有E[xj jwi] = ij�，var[xj jwi] = i2j2�2，计 算在�11 = �22 = 0及�12 = �21 = 1的情况下，由贝叶斯决策引起的错误率。（中心极限 定理） 解：在0� 1损失下，最小风险贝叶斯决策与最小错误率贝叶斯决策等价。 � 2.12写出离散形式的贝叶斯公式。 解： P (wijx) = P (xjwi)P (x)Pc j=1 P (xjwi)P (wi) � 2.13把连续情况的最小错误率贝叶斯决策推广到离散情况，并写出其判别函数。 � 2.14写出离散情况条件风险R(aijx)的定义，并指出其决策规则。 解： R(aijx) = cX j=1 �ijP (wj jx) = cX j=1 �ijp(xjwj)P (wj)////omit the same part p(x) R(akjx) = min j=1;2;:::;N R(aj jx)，则ak就是最小风险贝叶斯决策。 � 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 = P�P T � 2.17若将��1矩阵写为：��1 = 26664 h11 h12 � � � h1d h12 h22 � � � h2d ... ... . . . ... h1d h2d � � � hdd 37775，证明Mahalanobis距离平方为 2 = dX i=1 dX j=1 hij(xi � ui)(xj � uj) 证明： 2 = (x� u)T 26664 h11 h12 � � � h1d h12 h22 � � � h2d ... ... . . . ... h1d h2d � � � hdd 37775 (x� u) = dX i=1 dX j=1 hij(xi � ui)(xj � uj) � 2.18分别对于d = 2; d = 3证明对应与Mahalanobis距离 的超椭球体积是V = Vdj�j 12 d � 2.19假定x和m是两个随机变量，并设在给定m时，x的条件密度为 p(xjm) = (2�) 12��1 exp � �1 2 (x�m)2/�2 � 再假设m的边缘分布是正态分布，期望值是m0，方差是�2m，证明 p(mjx) = (� 3 + �m) 1 2 (2�) 1 2��m exp " �1 2 �2 + �2m �2�2m � m� � 2 mx+m0� 2 �2 + �2m �2# 5 模式识别(第二版)习题解答 证明： p(mjx) = p(xjm)p(m) p(x) = p(xjm)p(m)R p(xjm)p(m)dm = (2�) 1 2��1 exp ��12(x�m)2/�2 (2�) 12��1m exp��12(m�m0)2/�2m R (2�) 1 2��1 exp ��12(x�m)2/�2 (2�) 12��1m exp��12(m�m0)2/�2m dm = (�3 + �m) 1 2 (2�) 1 2��m exp " �1 2 �2 + �2m �2�2m � m� � 2 mx+m0� 2 �2 + �2m �2# � 2.20对�i = �2I的特殊情况，证明 { (1)若P (wi) 6= P (wj)，则超平面靠近先验概率较小的类； { (2)在甚么情况下，先验概率对超平面的位置影响不大。 证明： (1)当P (wi) = P (wj)时，超平面经过x0 = 12(ui+ uj)，则对于先验概率较小的类 属于它的区域会减少，所以超平面经过的点会靠近先验概率较小的类。（可以这样理 解，具体证明也很简单） (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)] = � ln p(xjw1) + ln p(xjw2) = 1 2 (x1 � u1)T��11 (x1 � u1)� 1 2 (x2 � u2)T��12 (x2 � u2) + 1 2 ln j�1jj�2j = 1 2 � (x� u1)T (x� u1)� (x� u2)T (x� u2) � 而，ln h P (w1) P (w2) i = 0。所以判别规则为当(x�u1)T (x�u1) > (x�u2)T (x�u2)则x 2 w1,反 之则s 2 w2。即将x判给离它最近的ui的那个类。 � 2.24在习题2.23中若�1 6= �2，�1 = � 1 12 1 2 1 � ，�2 = � 1 �12 �12 1 � ，写出负对数似然比决 策规则。 6 BBQ 椭圆形 模式识别(第二版)习题解答 解： h(x) = � ln [l(x)] = � ln p(xjw1) + ln p(xjw2) = 1 2 (x1 � u1)T��11 (x1 � u1)� 1 2 (x2 � u2)T��12 (x2 � u2) + 1 2 ln j�1jj�2j = 1 2 xT (��11 � ��12 )x� (��11 ui � ��12 uj)Tx+ 1 2 (uT1 � �1 1 u1 � uT2 ��12 u2 + ln j�1j j�2j) = �4 3 x1x2 + 4 3 x1 而，ln h P (w1) P (w2) i = 0。决策面为x1(x2 � 1) = 0，如图1所示 x y 1 图 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) Z R2 p(xjw1)dx�(�12��22) Z R1 p(xjw2)dm = 0 可以得到， Z R2 p(xjw1)dx = Z R1 p(xjw2)dm，所以R1 = f(x1; x2)jx1(x2 � 1) > 0g， R2 = f(x1; x2)jx1(x2 � 1) < 0g x 3 概率密度函数的估计 � 3.1设总体分布密度为N(u; 1)，�1 < u < +1，并设X = fx1; x2; :::; xNg，分别用最 大似然估计和贝叶斯估计计算u^。已知u的先验分布p(u) � N(0; 1)。 解：似然函数为： L(u) = ln p(X ju) = NX i=1 ln p(xiju) = �12 NX i=1 (xi � u)2 + C 似然函数u求导 @L(u) @u = NX i=1 xi �Nu = 0 所以u的最大似然估计：u^ = 1 N NX i=1 xi 贝叶斯估计：MAP(maximum a posterior) p(ujX ) = p(X ju)p(u)R p(X ju)p(u)du = � NY i=1 p(xiju)p(u) = � NY i=1 1p 2�� exp � �(xi � u) 2 2�2 � � 1p 2��0 exp � �(u� u0) 2 2�20 � = �0 exp " �1 2 NX i=1 � u� xi � �2 + � u� u0 �0 �2!# = �00 exp " �1 2 "� N �2 + 1 �20 � u2 � 2 1 �2 NX i=1 xi + u0 �20 ! u ## 将p(ujX )写成N(un; �2n)的形式，利用待定系数法，可以求得： 1 �2n = N �2 + 1 �20 un �2n = 1 �2 NX i=1 xi + u0 �20 8 BBQ 椭圆形 模式识别(第二版)习题解答 进一步求得un和�2n un = N�20 N�20 + �2 mN + �2 N�20 + �2 u0 �2n = �20� 2 N�20 + �2 其中，mN = 1 N NX i=1 xi，un就是贝叶斯估计。 � 3.3设X = fx1; x2; :::; xNg为来自点二项式分布的样本集，即f(x; P ) = P xQ(1�x); x = 0; 1; 0 � P � 1; Q = 1� P，试求参数P的最大似然估计。 解：似然函数为： L(P ) = NX i=1 ln � P xi(1� P )(1�xi) � = NX i=1 xi lnP +N ln(1� P ) + NX i=1 xi lnP 两边对P求导可得 @L @P = PN i=1 xi P � N 1� P + PN i=1 xi 1� P = 0 所以P得最大似然估计为：P^ = 1 N NX i=1 xi。 � 3.4 假设损失函数为二次函数�(P^ ; P ) = (P^ � P )2，以及P的先验密度为均匀分布 f(P ) = 1; 0 � P � 1。在这样的假设条件下，求3.3题的贝叶斯估计P^。 解： P (X jP ) = NY i=1 P xi(1� P )1�xi 利用贝叶斯公式求出P的后验概率 P (P jX ) = P (X jP )f(P )R P (X jP )f(P )dP = QN i=1 P xi(1� P )1�xiR 1 0 QN i=1 P xi(1� P )1�xidP � 3.7设X = fx1; x2; :::; xNg是来自p(xj�)的随机样本，其中0 6 x 6 �时，p(xj�) = 1 � ，否 则为0。证明�的最大似然估计是max k xk。 最大似然估计的目标是最大化对数似然函数，对数似然函数为： L(�) = ln p(Xj�) (1) = �N ln � (2) 9 模式识别(第二版)习题解答 要使得L(�)最大，同时要满足� > x。那么此时�的最大似然估计为： �� = max k xk (3) � 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窗估计 p^N (x) = 1 NhN NX i=1 ' � x� xi hN � 对于小的hN，有如下性质： { (1) E [p^N (x)] � N(u; �2 + h2N ) { (2) V ar [p^N (x)] = 1 NhN2 p � p(x) 证明： (1)E[p^N (x)] = Z p^N (x)p(x)dx 8.1 Sw表示类内离散度矩阵，Sb表示类间离散度矩阵 x 4 线性判别函数 � 4.1（1）指出从x到超平面g(x) = wTx+ w0 = 0的距离r = jg(x)jjjwjj 是在g(xq) = 0的约束 条件下，使jjx� xqjj2达到极小解； （2）指出在超平面上的投影是xp = x� g(x)jjwjj2w 解：（1）设x在超平面的正侧g(x) > 0，xq是x在超平面上的投影点，则wTxq + w0 = 0。设x到平面的距离为r，则x � xp = r wjjwjj，所以w Tx � wTxp = rjjwjj，得到r = wTx+ w0 jjwjj = g(x) jjwjj。 10 模式识别(第二版)习题解答 x在超平面负侧时g(x) < 0，得r = �w Tx� w0 jjwjj = �g(x) jjwjj 。 所以r = jg(x)jjjwjj （2）x在超平面正侧时，x � xp = r wjjwjj = g(x) jjwjj2w，所以xp = x � g(x) jjwjj2w；当x在超 平面的负侧时，x� xp = �r wjjwjj = g(x) jjwjj2w，所以xp = x� g(x) jjwjj2w。 � 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) = aT y （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) = aT y。 � 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) = aT y。 （2）映射y = [1; x; x2]T把一条直线映射为三维空间中的一条抛物线。 � 4.4对于二维线性判别函数g(x) = x1 + 2x2 � 2 { （1）将判别函数写成g(x) = wTx+ w0的形式，并画出g(x) = 0的几何图形； { （2）映射成广义齐次线性函数g(x) = aT y； { （3）指出上述X空间实际是Y空间的一个子空间，且aT y = 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) = aT y。 （3）y1 = 1; y2 = x1; y3 = x2，在所以所有的样本在Y空间中的一个平面y1 = 1上。 � 4.5指出在Fisher线性判别中，w的比例因子对Fisher判别结果无影响。 解：假设w乘一比例因子�，�w，经过投影后得到y = �wTx。相当于对所有样本乘以 一个比例因子，所以对判别结果没有影响。 � 4.6证明两向量外积组成的矩阵一般是奇异的。 证明：设两向量a; b 2 Rn，它们的外积为：A = abT，因为abT与bTa有相同的非零特征 值，容易得到 A的特征值为bTa; 0; 0; :::; 0| {z } n�1 。有零特征值肯定是奇异的，除非n = 1。 11 BBQ 椭圆形 BBQ 椭圆形 模式识别(第二版)习题解答 x1 x2 1 2 图 2: g(x) = 0的几何图形 � 4.8证明在正态等方差条件下，Fisher线性判别等价于贝叶斯判别。 证明： 在正态等方差的条件下，判别函数g(x) = wTx + w0中w = ��1(u1 � u2)， 在Fisher线性判别中最优投影方向为： w = ��1(u1 � u2)。 � 4.9证明 { （1）引入余量b以后的解区(aT yi � b)位于原来的解区(aT yi > 0)之中； { （2）与原解区边界之间的距离为 bjjyijj。 解：（1）设a�满足aT yi � b，则它一定也满足aT yi > 0，所以引入余量后的解区位于 原来的解区aT y > 0之中。（2）aT yi � b解区边界为：aT yi = b，aT yi > 0解区边界为： aT yi = 0，aT yi = b到aT yi = 0的距离为 bjjyijj。 � 4.10证明，在几何上，感知器准则函数正比于被错分类样本到决策面的距离之和。 证明：感知器准则函数为J(a) = X y2Y (�aT y)。决策面方程为：aT y = 0。当y为错分类 样本时，有aT y � 0，到决策面的距离为�aT y。所有错分类样本到决策面的距离之和 为 X y2Y (�aT y)，就是感知器准则函数。 � 4.12写出Widrow-Hoff法程序框图。 解：平方误差准则函数J(a) = jjY a�bjj2 = NX n=1 (aT yn�bn)2，它的最小二乘解，伪逆解 或MSE解为：a� = (Y TY )�1Y T b，采用梯度下降法来求解a�。J(a)的梯度为rJ(a) = 2Y T (Y a� b)，则梯度下降法可以写成 � a(1) a(k + 1) = a(k)� �kY T (Y a� b) ，选择�k = �1 k ，式中�1为任意正常数。 12 模式识别(第二版)习题解答 为了进一步减小计算量和存储量，可以将上述算法修改为（单样本修正）� a(1) a(k + 1) = a(k)� �k(a(k)T yk � bk)yk 让�k随着k的增加而逐渐减小，以确保算法收敛。一般选择�k = �1 k ，还有yk和前面感 知器准则函数中的单样本修正法一样，是在无限重复序列中的错分类样本。 � 4.13 { （1）证明矩阵恒等式(A+ xxT )�1 = A�1 � A �1xxTA�1 1 + xTA�1x { （2）利用上试结果证明式（4-98）。 证明：（1） (A+ xxT ) � A�1 � A �1xxTA�1 1 + xTA�1x � = (A+ xxT ) � I � A �1xxT 1 + xTA�1x � A�1 = � A+ xxT � xx T 1 + xTA�1x � xx TA�1xxT 1 + xTA�1x � A�1 = AA�1 = I 所以(A+ xxT )�1 = A�1 � A �1xxTA�1 1 + xTA�1x （2）R(k + 1)�1 = R(k)�1 + ykyTk，利用上面的结果可以得到： R(k + 1) = R(k) � R(k)ykyTk R(k) 1 + yTk R(k)yk � 4.14考虑准则函数 J(a) = X y2Y (a) (aT y � b)2 其中Y (a)是使aT y � b的样本集合。设y1是Y (a)中的唯一样本，则J(a)的梯度为rJ(a) = 2(aTk y1 � b)y1，二阶偏导数矩阵D = 2y1yT1。据此证明，若最优步长选择为�k = jjrJ(a)jj2 rJT (a)DrJ(a)时，梯度下降法的迭代公式为： ak+1 = ak + b� aTk y1 jjy1jj2 y1 证明： y1是Y (a)中的唯一样本，则准则函数为J(a) = X y2Y (a) (aT y � b)2 = (aT y1 � b)2， 所以rJ(a) = 2(aT y1 � b)y1，二阶偏导数矩阵为D = 2y1yT1。 梯度下降的迭代公式为：ak+1 = ak��krJ(ak)，�k = 4(a T k y1 � b)2jjy1jj2 8(aTk y1 � b)2yT1 y1yT1 y1 = 1 2jjy1jj2 ，将�k代入梯度下降的迭代公式：ak+1 = ak + b� a T k y1 jjy1jj2 y1 13 模式识别(第二版)习题解答 � 4.15证明：当取 b = 2664 NN1 ; :::; NN1| {z } N1 ; N N2 ; :::; N N2| {z } N2 3775 MSE解等价于Fisher解。 证明： Y = 26664 yT1 yT2 ... yTN 37775 = � 11 X1 �12 �X2 � ，a = [w0;w]T则Y TY a = Y T b，化为： � 1T1 �1T2 XT1 �XT2 � � 11 X1 �12 �X2 � � w0 w � = � 1T1 �1T2 XT1 �XT2 �" N N1 11 N N1 12 # 设m1 = 1 N1 X i2C1 xi;m2 = 1 N2 X i2C2 xi，上式可化为： � N (N1m1 +N2m2)T (N1m1 +N2m2) Sw +N1m1mT1 +N2m2m T 2 � � w0 w � = � 0 N(m1 �m2) � 式中，Sw = 2X i=1 X j2Ci (xj �mi)(xj �mi)T，且(N1m1 +N2m2)T = NmT，m = NX i=1 xi， 上面的等式可以分解出两个等式，第一个得到w0 = �mTw，将w0代入第二个等式可以 得到 � � 1 N (N1m1 +N2m2)(N1m1 +N2m2)T + Sw +N1m1mT1 +N2m2m T 2 � w = N(m1 �m2)� 1 N Sw + N1N2 N2 (m1 �m2)(m1 �m2)T � w = m1 �m2 注意因为N1N2 N (m1 �m2)(m1 �m2)Tw在m1 �m2的方向上，所以上式可以化为： Sww = �(m1 �m2) 与Fisher的解相同。 � 4.16证明： { (1)式(4-113)表示的向量y � a T y jjwjj2 � 0 w � 表示y到X空间中超平面的投影。 { (2)该投影正交于X空间的超平面。 证明： （1）先证明这个向量在X空间中的超平面上，再证明y � � y � a T y jjwjj2 � 0 w �� 的向量为X空间中超平面的法向量。 X空间中的超平面的方程为：g(x) = wTx + 14 模式识别(第二版)习题解答 x0 = [1;wT ] � x0 x � = aT y = 0，将向量代入g(x)，得 aT y � a T y jjwjj2a T � 0 w � = aT y � aT y jjwjj2 jjwjj 2 = 0，又因为y � � y � a T y jjwjj2 � 0 w �� = aT y jjwjj2 � 0 w � � 4.17在多类问题中，如果一组样本可被一线性机全部正确分类，则称这组样本是线性 可分的。对任意wi类，如果能用一超平面把wi类的样本同其他样本分开来，则称总体 线性可分。举例说明，总体线性可分必定线性可分，但反之不然。 解： a c b a b c c b a 图 3: 总体线性可分必定线性可分 图 4: 线性可分未必总体线性可分 � 4.18设有一组样本。若存在c(c � 1)/2个超平面Hij，使Hij把属于wi类的样本同属于wj 类的样本分开，则称这组样本是成对线性可分的。举列说明，成对线性可分的样本不 一定线性可分。 图 5: 成对线性可分不一定定线性可分 15 模式识别(第二版)习题解答 x 5 非线性判别函数 � 5.1举例说明分段线性分界面可以逼近贝叶斯判别函数确定的超曲面。 解： 分段线性函数是一类特殊的非线性函数，它确定的决策面由若干个平面段组成， 所以它可以逼近各种形状的超曲面。 � 5.2已知两类问题如图6所示，其中``�''表示w1类训练样本集合的原型，`` ''表示w2类 训练样本集的原型。 { (1)找出紧互对原型集合P； { (2)找出与紧互对行集相联系的超平面集H； { (3)假设训练集样本与原型完全相同，找出由超平面集H产生的z(x)。 1050 10 5 图 6: 一个两类问题的原型分布 解:（1）用坐标来表示样本w1中的样本(4; 6)与w2中的样本(5; 5)是紧互对原型，(3; 4) 与(3; 2)是，(2; 5)与(1; 3)也是。如图 7所示（2）如图8所示 x 6 近邻法 � 6.1举例说明最近邻决策面是分段线性的。 解： 分段线性函数的决策面由若干个超平面组成。由于它的基本组成仍然是超平面， 因此，与一般超平面 � 6.2证明式(6� 14) � (6� 18)。 证明：记 cX i=1 P 2(wijx) = P 2(wmjx) + X i 6=m P 2(wijx) 16 模式识别(第二版)习题解答 1050 10 5 图 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，若按离样本均值距离的大小进行分类，试画出决策面。 解： 第一首先要明确什么是“最近邻法”？它实际是一种分段的线性判别函数。第 二根据离样本均值的距离来分类，首先求出两类的样本均值，分类决策面就是样本 均值的垂直平分线。 (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)，其中xi 2Xp，则xi不是x的近邻。 证明：有三角不等式 D(x; xi) +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) < D(x;Mp) 时，x的近邻一定不在Xp中。 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 ：近邻法的快速算法。 17 BBQ 椭圆形 BBQ 椭圆形 模式识别(第二版)习题解答 1050 10 5 图 8: 利用紧互对原型 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的分段线性分类器 x 7 经验风险最小化和有序风险最小化方法 x 8 特征的选取和提取 � 8.1三类w1; w2; w3，求Sw; Sb。 解：对应w1类的样本点f(1; 0)T ; (2; 0)T ; (1; 1)T g， w2类的样本点f(0; 1)T ; (�1; 0)T ; (�1; 1)T g， w3类的样本点f(0;�1)T ; (�1;�1)T ; (0;�2)T g。 w1类的均值u1 = (43 ; 1 3 )T，协方差矩阵为： �1 = 1 3 X xi2w1 (xi � u1)(xi � u1)T = 1 9 � 2 �1 �1 2 � w2类的均值u2 = (�23 ; 2 3 )T，协方差矩阵为： �2 = 1 3 X xi2w2 (xi � u2)(xi � u2)T = 1 9 � 2 1 1 2 � 18 模式识别(第二版)习题解答 0 1 图 9: 最近邻法分类决策面 w3类的均值u3 = (�13 ;� 4 3 )T，协方差矩阵为： �2 = 1 3 X xi2w3 (xi � u3)(xi � u3)T = 1 9 � 2 �1 �1 2 � 所以类内散布度矩阵为： Sw = 1 3 (�1 +�2 +�3) = 1 27 � 6 �1 �1 6 � 总体均值为u = 1 3 3X i=1 ui = ( 1 9 ;�1 9 )T，所以类间散布度矩阵为： Sb = 1 3 3X i=1 (ui � u)(ui � u)T = 1 81 � 62 13 13 62 � � 8.2设有两个正态分布的样本集，它们的期望及方差矩阵分别等于上题中w1及w2的均值 向量及协方差矩阵，计算w1和w2的散度及Bhattacharyya距离。 解： p(xjwi) = 1(2�)d/2j�ij1/2 exp[�1 2 (x� ui)T��1i (x� ui)] 19 模式识别(第二版)习题解答 0 1 图 10: 按样本均值分类的决策面 I12 = Z p(xjw1) ln p(xjw1) p(xjw2 dx = Z � 1 2 ln j�2jj�1j � 1 2 tr[��11 (x� u1)(x� u1)T ] + 1 2 tr[��12 (x� u2)(x� u2)T ] � p(wjx1)dx w1和w2的散度为： JD =Iij + Iji = Z [p(xjwi)� p(xjwj)] ln p(xjwi) p(xjwj) = 1 2 tr[��11 �2 +� �1 2 �1 � 2I] + 1 2 (u1 � u2)T (��11 +��12 )(u1 � u2) x 9 基于K-L展开式的特征提取 � 9.1若有下列两类样本集： w1 w2 x1 = (0; 0; 0)T y1 = (0; 0; 1)T x2 = (1; 0; 0)T y2 = (0; 1; 0)T x3 = (1; 0; 1)T y3 = (0; 1; 1)T x4 = (1; 1; 0)T y4 = (1; 1; 1)T 用K-L变换，分别把特征空间维数降到d = 2和d = 1并用图画出样本在该特征空间中的 位置。 解： w1和w2的协方差矩阵分别为： �1 = 1 4 240:75 0:25 0:250:25 0:75 �0:25 0:25 �0:25 0:75 35 20 BBQ 椭圆形 模式识别(第二版)习题解答 �2 = 1 4 240:75 0:25 0:250:25 0:75 �0:25 0:25 �0:25 0:75 35 则总类内散布度矩阵Sw为： Sw = 1 2 (�1 +�2) = 1 8 241:5 0:5 0:50:5 1:5 �0:5 0:5 �0:5 1:5 35 它的特征值矩阵和特征向量分别为： � = 1 4 240:5 0 00 2 0 0 0 2 35 ; U = 264� 1p 3 � 1p 42 3p 14 � 1p 3 � 5p 42 1p 14 1p 3 4p 42 2p 14 375 所以，降到d = 2维的变换矩阵U = 264� 1p 42 3p 14 � 5p 42 1p 14 4p 42 2p 14 375 又Sb为 Sb = 24 18 �18 �18�18 18 18 �18 18 18 35 所以 J(x1) = uT1 Sbu1 �1 = 0:375 J(x2) = uT2 Sbu2 �2 = 0 J(x3) = uT3 Sbu3 �3 = 0 � 9.3 令�i和Pi分别为类wi(i = 1; 2)的协方差矩阵和先验概率。假定对数据进行白化变 换，即使得BTSwB = I，这里 Sw = P i Pi�i，I是单位矩阵。证明矩阵P1BT�1B和 矩阵P2BT�2B所产生的K-L坐标轴是相同的，若用�i表示矩阵PiBT�iB的特征值矩阵， 求证： �1 = I � �2 证明：因为： Sw = P1�1 + P2�2 BTSwB = P1BT�1B + P2BT�2B = I 设P1BT�1Bu = �u，则 (I � P2BT�2B)u = �u P2B T�2Bu = (1� �)u 可见矩阵P1BT�1B和矩阵P2BT�2B具有相同的特征向量。产生的K-L坐标轴相同。再 由上面的推倒，设P1BT�1B的特征值为�1则P2BT�2B有一个特征值�2 = 1 � �1 容易 得到特征值矩阵满足�1 = I � �2 21 模式识别(第二版)习题解答 x 10 非监督学习方法 � 10.1令x1; x2; :::; xN是d维样本，�是任一非奇异d� d矩阵，证明使 NX k=1 (xk � x)T��1(xk � x) 最小的向量x是样本的均值� = 1 N NX i=1 xi 证明：设 g(x) = NX k=1 (xk � x)T��1(xk � x) 上式对x求导得 @g(x) @x = 2 NX k=1 ��1(x� xk) 导数为0得到极值，易得 x = 1 N NX k xk � 10.2令s(x; x0) = x Tx0 jjxjj � jjx0jj。若x的d个特征只取+1和�1二值，即当x具有第i个特征时， xi = 1而当x没有这个特征时xi = �1，说明s是一个相似性度量。证明对于这种情况 jjx� x0jj2 = 2d(1� s(x; x0)) 证明： jjx� x0jj2 = (x� x0)T (x� x0) = xTx� 2xTx0 + x0Tx0 = 2d� 2xTx0 = 2d(1� x Tx0p d p d ) = 2d(1� x Tx0 jjxjj � jjx0jj) = 2d(1� s(x; x0)) � 10.3假使一个有N个样本的集合X划分为c个不相交的子集X1; :::;Xc，假使Xi是空集， 则Xi中样本的均值mi不定义。在这种情况下，误差平方和只和非空子集有关： Je = X i X x2Xi jjx�mijj2 这里i是不包含空子集的子集标号。假定N > c,证明使得Je最小的划分中没有空子集。 证明：假设存在一个空子集Xk; 1 6 k 6 c使得Je最小，容易证明可以找到所有子集都 不为空的划分使得Je更小。 22 BBQ 椭圆形 绪论 贝叶斯决策理论 概率密度函数的估计 线性判别函数 非线性判别函数 近邻法 经验风险最小化和有序风险最小化方法 特征的选取和提取 基于K-L展开式的特征提取 非监督学习方法