模式识别第二版答案完整版

模式识别(第二版) 习题解答

目录

1绪论

2贝叶斯决策理论3概率密度函数的估计4线性判别函数5非线性判别函数6近邻法

7经验风险最小化和有序风险最小化方法8特征的选取和提取9基于K-L 展开式的特征提取10非监督学习方法

[**************]22

§1绪论

略

§2贝叶斯决策理论

•2.1如果只知道各类的先验概率，最小错误率贝叶斯决策规则应如何表示？

解：设一个有C 类，每一类的先验概率为P (w i ) ，i =1,..., C 。此时最小错误率贝叶斯决策规则为：如果i ∗=max P (w i ) ，则x ∈w i 。

i

•2.2利用概率论中的乘法定理和全概率公式证明贝叶斯公式（教材中下面的公式有错误）

p (x |w i ) P (w i )

P (w i |x ) =.

p (x ) 证明：

P (w i |x ) =

P (w i , x ) p (x )

p (x |w i ) P (w i ) =

p (x )

•2.3证明：在两类情况下P (w i |x ) +P (w 2|x ) =1。证明：

P (w 1|x ) +P (w 2|x ) =

P (w 1, x ) P (w 2, x )

+

p (x ) p (x ) P (w 1, x ) +P (w 2, x ) =

p (x )

p (x ) =

p (x ) =1

•2.4分别写出在以下两种情况

1. P (x |w 1) =P (x |w 2) 2. P (w 1) =P (w 2)

下的最小错误率贝叶斯决策规则。

解：当P (x |w 1) =P (x |w 2) 时，如果P (w 1) >P (w 2) ，则x ∈w 1，否则x ∈w 2。当P (w 1) =P (w 2) 时，如果P (x |w 1) >P (x |w 2) ，则x ∈w 1，否则x ∈w 2。•2.5

1. 对c 类情况推广最小错误率率贝叶斯决策规则；

2. 指出此时使错误率最小等价于后验概率最大，即P (w i |x ) >P (w j |x ) 对一切j =i 成立时，x ∈w i 。

解：对于c 类情况，最小错误率贝叶斯决策规则为：

如果P (w i |x ) =max P (w j |x ) ，则x ∈w i 。利用贝叶斯定理可以将其写成先验概率和

j =1,...,c

类条件概率相联系的形式，即

如果p (x |w i ) P (w i ) =max p (x |w j ) P (w j ) ，则x ∈w i 。

j =1,...,c

•2.6对两类问题，证明最小风险贝叶斯决策规则可表示为，若

p (x |w 1) (λ12−λ22) P (w 2)

>,

p (x |w 2) (λ2111) P (w 1)

则x ∈w 1，反之则属于w 2。解：计算条件风险

R (α1|x ) =

2∑j =1

λ1j P (w j |x )

=λ11P (w 1|x ) +λ12P (w 2|x )

R (α2|x ) =

2∑j =1

λ2j P (w j |x )

=λ21P (w 1|x ) +λ22P (w 2|x )

如果R (α1|x )

λ11P (w 1|x ) +λ12P (w 2|x )

(λ21−λ11) P (w 1|x ) >(λ12−λ22) P (w 2|x ) (λ21−λ11) P (w 1) p (x |w 1) >(λ12−λ22) P (w 2) p (x |w 2)

p (x |w 1) (λ12−λ22) P (w 2)

>

p (x |w 2) (λ2111) P (w 1)

所以，如果

p (x |w 1) (λ12−λ22) P (w 2)

>，则x ∈w 1。反之则x ∈w 2。

p (x |w 2) (λ2111) P (w 1)

•2.7若λ11=λ22=0, λ12=λ21，证明此时最小最大决策面是来自两类的错误率相等。解：最小最大决策时满足

∫

(λ11−λ22) +(λ21−λ11)

容易得到

∫

R 1

R 2

∫

p (x |w 1) dx −(λ12−λ22)

∫

R 1

p (x |w 2) dx =0

p (x |w 2) dx =

R 2

p (x |w 1) dx

所以此时最小最大决策面使得P 1(e ) =P 2(e )

•2.8对于同一个决策规则判别函数可定义成不同形式，从而有不同的决策面方程，指出

决策区域是不变的。

解：对于同一决策规则（如最小错误率贝叶斯决策规则），它的判别函数可以是j ∗=max P (w j |x ) ，则x ∈w j ∗。另外一种形式为j ∗=max p (x |w j ) P (w j ) ，则x ∈w j ∗。

j =1,...,c

j =1,...,c

考虑两类问题的分类决策面为：P (w 1|x ) =P (w 2|x ) ，与p (x |w 1) P (w 1) =p (x |w 2) P (w 2) 是相同的。

•2.9写出两类和多类情况下最小风险贝叶斯决策判别函数和决策面方程。•2.10随机变量l (x ) 定义为l (x ) =

p (x |w 1)

，l (x ) 又称为似然比，试证明

p (x |w 2)

–(1)E {l n (x ) |w 1}=E {l n +1(x ) |w 2}–(2)E {l (x ) |w 2}=1

–(3)E {l (x ) |w 1}−E 2{l (x ) |w 2}=var {l (x ) |w 2}（教材中题目有问题）

∫∫

(p (x |w 1)) n +1n n n +1

证明：对于(1)，E {l (x ) |w 1}=l (x ) p (x |w 1) d x =(x ) |w 2}=d x 又E {l (p (x |w 2)) ∫∫

(p (x |w 1)) n +1n +1n n +1(x ) |w }l p (x |w 2) d x =2d x 所以，E {l (x ) |w 1}=E {l (p (x |w 2)) ∫∫

对于(2)，E {l (x ) |w 2}=l (x ) p (x |w 2) d x =p (x |w 1) d x =1

对于(3)，E {l (x ) |w 1}−E 2{l (x ) |w 2}=E {l 2(x ) |w 2}−E 2{l (x ) |w 2}=var {l (x ) |w 2}•2.11x j (j =1, 2,..., n ) 为n 个独立随机变量，有E [x j |w i ]=ijη，var [x j |w i ]=i 2j 2σ2，计算在λ11=λ22=0及λ12=λ21=1的情况下，由贝叶斯决策引起的错误率。（中心极限定理）解：在0−1损失下，最小风险贝叶斯决策与最小错误率贝叶斯决策等价。•2.12写出离散形式的贝叶斯公式。解：

P (w i |x ) =P (x |w i ) P (x ) j =1P (x |w i ) P (w i )

•2.13把连续情况的最小错误率贝叶斯决策推广到离散情况，并写出其判别函数。•2.14写出离散情况条件风险R (a i |x ) 的定义，并指出其决策规则。解：

R (a i |x ) =

=

R (a k |x ) =

min

c ∑j =1c ∑j =1

λij P (w j |x )

λij p (x |w j ) P (w j )////omit the same part p (x )

j =1, 2,...,N

R (a j |x ) ，则a k 就是最小风险贝叶斯决策。

•2.15证明多元正态分布的等密度点轨迹是一个超椭球面，且其主轴方向由Σ的特征向量

决定，轴长度由Σ的特征值决定。证明：多元正态分布的等密度点满足：x T Σ−1x =C ，C 为常数。

•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

h 1d h 2d

，证明Mahalanobis 距离平方为. . . h dd

h 11h 12···

h 12h 22··· = . . . . . . . . .

h 1d h 2d ···

d d ∑∑i =1j =1

γ=

2

h ij (x i −u i )(x j −u j )

证明：

h 11h 12··· h h 22···2T 12

γ=(x −u ) . . . . . . . . .

h 1d h 2d ···=

d d ∑∑i =1j =1

h 1d

h 2d

(x −u ) . . . h dd

h ij (x i −u i )(x j −u j )

1

•2.18分别对于d =2, d =3证明对应与Mahalanobis 距离γ的超椭球体积是V =V d |Σ|γd •2.19假定x 和m 是两个随机变量，并设在给定m 时，x 的条件密度为

}{

11

p (x |m ) =(2π) σ−1exp −(x −m ) 2/σ2

2

2，证明再假设m 的边缘分布是正态分布，期望值是m 0，方差是σm

[() 2]1

32222(σ+σm ) 1σ+σm σm x +m 0σ

p (m |x ) =exp −m −1222σ2σm σ2+σm (2π) σσm

证明：p (m |x ) =

p (x |m ) p (m )

p (x )

p (x |m ) p (m ) =p (x |m ) p (m ) d m

}{1{}11

−1exp −1(m −m ) 2/σ2(2π) σ−1exp −(x −m ) 2/σ2(2π) σm 0m =11−1

2d m (2π) σ−1exp −(x −m ) 2/σ2(2π) σm exp −(m −m 0) 2/σm

[() 2]1

32222(σ+σm ) σm x +m 0σ1σ+σm =m −exp −2σσm σ+σm (2π) σσm

•2.20对Σi =σ2I 的特殊情况，证明

–(1)若P (w i ) =P (w j ) ，则超平面靠近先验概率较小的类；–(2)在甚么情况下，先验概率对超平面的位置影响不大。

1

证明：(1)当P (w i ) =P (w j ) 时，超平面经过x 0=(u i +u j ) ，则对于先验概率较小的类

2

属于它的区域会减少，所以超平面经过的点会靠近先验概率较小的类。（可以这样理解，具体证明也很简单）

(2)？不知道这是什么问题，先验概率不管在什么时候都很重要！

•2.21对Σi =Σ的特殊情况，指出在先验概率不等时，决策面沿u i 点与u j 点连线向先验概率小的方向移动。证明：同上面一题解释一样。•2.24似然比决策准则为：若

•2.23二维正态分布，u 1=(−1, 0) T , u 2=(1, 0) T , Σ1=Σ2=I, P (w 1) =P (w 2) 。试写出对数似然比决策规则。解：

h (x ) =−ln [l (x )]

=−ln p (x |w 1) +ln p (x |w 2)

11|Σ1|11T −1

(x −u ) −(x −u ) Σ(x −u ) +ln =(x 1−u 1) T Σ−11222212

2222]1[

=(x −u 1) T (x −u 1) −(x −u 2) T (x −u 2) 2

[]P (w 1)

而，ln 2=0。所以判别规则为当(x −u 1) T (x −u 1) >(x −u 2) T (x −u 2) 则x ∈w 1, 反之则s ∈w 2。即将x 判给离它最近的u i 的那个类。

[][111

•2.24在习题2.23中若Σ1=Σ2，Σ1=1，Σ2=

−11策规则。

]−1，写出负对数似然比决1

解：

h (x ) =−ln [l (x )]

=−ln p (x |w 1) +ln p (x |w 2) 111|Σ1|1T −1=(x 1−u 1) T Σ−(x −u ) −(x −u ) Σ(x −u ) +ln 11222212

22221T −1−1−11T x (Σ1−Σ−2) x −(Σ1u i −Σ2u j ) x +2=

1T −1|Σ1|−1(u 1Σ1u 1−u T Σu +ln ) 2222244=−x 1x 2+x 1

33

[]P (w 1)

而，ln 2=0。决策面为x 1(x 2−1) =0，如图1

所示

x

图1:分类决策面

•2.25在习题2.24的情况下，若考虑损失函数λ11=λ22=0, λ12=λ21，画出似然比阈值与错误率之间的关系。

–(1)求出P (e ) =0. 05时完成Neyman-Pearson 决策时总的错误率；（P (e ) 应该为P (e 1) 或者P (e 2) ）–(2)求出最小最大决策的域值和总的错误率。解：

（1）损失函数在0-1损失函数条件下的最小风险贝叶斯决策等价于最小错误率贝叶斯决策。似然比等于0的情况下错误率最小。当P (e 1) =0. 05时，

∫∫

（2）最小最大决策时，(λ11−λ22)+(λ21−λ11) p (x |w 1) d x −(λ12−λ22) p (x |w 2) d m =

R R 21∫∫

0可以得到，p (x |w 1) d x =p (x |w 2) d m ，所以R 1={(x 1, x 2) |x 1(x 2−1) >0}，R 2={(x 1, x 2) |x 1(x 2−1)

R 2

R 1

§3概率密度函数的估计

•3.1设总体分布密度为N (u, 1) ，−∞

L (u ) =ln p (X |u ) =

似然函数u 求导

∂L(u ) ∑

=x i −Nu =0∂u

N i =1

N 1∑

所以u 的最大似然估计：u ˆ=x i

N

i =1

N ∑i =1

1∑

(x i −u ) 2+C ln p (x i |u ) =−2

N i =1

贝叶斯估计：MAP(maximuma posterior)

p (u |X ) ==α

p (X |u ) p (u ) p (X |u ) p (u ) d u

N ∏i =1N ∏

p (x i |u ) p (u )

[][]

1(x i −u ) 21(u −u 0) 2=αexp −exp −·2σ2σ00i =1[(N () 2() 2)]∑1u −x i u −u 0

=α′exp −+

2σσ0

i =1

) ]][[(() N ∑1N 11u 02

u =α′′exp −+u −2x +i 2σσ0σσ0

i =1

2) 的形式，利用待定系数法，可以求得：将p (u |X ) 写成N (u n , σn

11N

+=σn σσ0

N

u n u 01∑

x +=i σn σσ0i =1

2进一步求得u n 和σn

2Nσ0σ2

u n =+σm N +Nσ+σu 0Nσ00

2σ2σ02

σn =+σNσ0

其中，m N

N

1∑=x i ，u n 就是贝叶斯估计。N

i =1

•3.3设X ={x 1, x 2,..., x N }为来自点二项式分布的样本集，即f (x, P ) =P x Q (1−x ) , x =0, 1, 0≤P ≤1, Q =1−P ，试求参数P 的最大似然估计。解：似然函数为：

L (P ) =

=

两边对P 求导可得

∂L

=∂P

N ∑i =1N ∑i =1

()

x i (1−x i )

ln P (1−P ) x i ln P +N ln (1−P ) +

N ∑i =1

x i ln P

∑N

∑N

x x i N i =1i

−+i =1=0P 1−P 1−P

N ∑1ˆ=所以P 得最大似然估计为：P x i 。N

i =1

ˆ, P ) =(P ˆ−P ) 2，以及P 的先验密度为均匀分布•3.4假设损失函数为二次函数λ(P

ˆ。f (P ) =1, 0≤P ≤1。在这样的假设条件下，求3.3题的贝叶斯估计P 解：

P (X |P ) =

利用贝叶斯公式求出P 的后验概率

P (P |X ) =P (X |P ) f (P )

P (X |P ) f (P ) d P ∏N

x i 1−x i

i =1P (1−P ) =N

x i 1−x i d P i =1P (1−P ) 0

1

，否θ

N ∏i =1

P x i (1−P ) 1−x i

•3.7设X ={x 1, x 2,..., x N }是来自p (x |θ) 的随机样本，其中0 x θ时，p (x |θ) =则为0。证明θ的最大似然估计是max x k 。

k

最大似然估计的目标是最大化对数似然函数，对数似然函数为：

L (θ) =ln p (X |θ)

=−N ln θ(1)(2)

要使得L (θ) 最大，同时要满足θ x 。那么此时θ的最大似然估计为：

θ∗=max x k

k

(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 窗估计

() N

x −x i 1∑

p ˆN (x ) =φ

Nh N h N

i =1

对于小的h N ，有如下性质：

–(1)E [ˆp N (x )]∼N (u, σ2+h 2N )

1

p (x ) –(2)V ar [ˆp N (x )]=

Nh N 2证明：(1)E [ˆp N (x )]=

∫

p ˆN (x ) p (x ) d x

8.1S w 表示类内离散度矩阵，S b 表示类间离散度矩阵

§4线性判别函数

•4.1（1）指出从x 到超平面g (x ) =w T x +w 0=0的距离r =条件下，使||x −x q ||2达到极小解；（2）指出在超平面上的投影是x p =x −

g (x )

w |g (x ) |

是在g (x q ) =0的约束解：（1）设x 在超平面的正侧g (x ) >0，x q 是x 在超平面上的投影点，则w T x q +w 0=

w

，所以w T x −w T x p =r ||w ||，得到r =0。设x 到平面的距离为r ，则x −x p =r T w x +w 0g (x )

=。

−w T x −w 0−g (x ) x 在超平面负侧时g (x )

g (x ) g (x ) w =w ，所以x =x −w ；当x 在超p w g (x ) g (x ) 平面的负侧时，x −x p =−r =w ，所以x =x −w 。p 22（2）x 在超平面正侧时，x −x p =r •4.3设有一维空间二次判别函数g (x ) =5+7x +9x 2

–(1)试映射成广义齐次线性判别函数；

–(2)总结把高次函数映射成齐次线性函数的方法。

解：（1）设y =[y 1, y 2, y 3]T =[1, x, x 2]T ，a =[5, 7, 9]T ，则广义齐次线性判别函数为：g (x ) =a T y

（2）对于n 次函数g (x ) =c 0+c 1x +c 2x 2+... +c n x n ，令y =[y 1, y 2,..., y n +1]T =

[1, x,..., x n ]T ，a =[c 0, c 1,..., c n ]T ，则g (x ) =a T y 。

•4.3（1）通过映射把一维二次判别函数g (x ) =a 1+a 2x +a 3x 2映射成三维广义线性判别函数；

（2）若x 在一维空间具有分布密度p (x ) ，说明三维空间中的分布退化成只在一条曲线上有值，且曲线上值无穷大。

解：（1）y =[1, x, x 2]T ，a =[a 1, a 2, a 3]T ，则g (x ) =a T y 。

（2）映射y =[1, x, x 2]T 把一条直线映射为三维空间中的一条抛物线。

•4.4对于二维线性判别函数g (x ) =x 1+2x 2−2

–（1）将判别函数写成g (x ) =w T x +w 0的形式，并画出g (x ) =0的几何图形；–（2）映射成广义齐次线性函数g (x ) =a T y ；

–（3）指出上述X 空间实际是Y 空间的一个子空间，且a T y =0对于X 子空间的划分和原空间中w T +w 0=0对原X 空间的划分相同，并在图上表示出来。

解：（1）w =[1, 2]T , x =[x 1, x 2]T , w 0=−2，则g (x ) =w T x +w 0，g (x ) =0的图形如下图2：

（2）y =[y 1, y 2, y 3]T =[1, x 1, x 2]T ，a =[−2, 1, 2]T ，则g (x ) =a T y 。

（3）y 1=1, y 2=x 1, y 3=x 2，在所以所有的样本在Y 空间中的一个平面y 1=1上。•4.5指出在Fisher 线性判别中，w 的比例因子对Fisher 判别结果无影响。

解：假设w 乘一比例因子α，αw，经过投影后得到y =αwT x 。相当于对所有样本乘以一个比例因子，所以对判别结果没有影响。

•4.6证明两向量外积组成的矩阵一般是奇异的。

证明：设两向量a, b ∈R n ，它们的外积为：A =ab T ，因为ab T 与b T a 有相同的非零特征值，容易得到A 的特征值为b T a, 0, 0,..., 0。有零特征值肯定是奇异的，除非n =1。 n −1

x x 1

图2:g (x ) =0的几何图形

•4.8证明在正态等方差条件下，Fisher 线性判别等价于贝叶斯判别。

证明：在正态等方差的条件下，判别函数g (x ) =w T x +w 0中w =Σ−1(u 1−u 2) ，在Fisher 线性判别中最优投影方向为：w =Σ−1(u 1−u 2) 。

•4.9证明

–（1）引入余量b 以后的解区(a T y i ≥b ) 位于原来的解区(a T y i >0) 之中；

b –（2）与原解区边界之间的距离为。i 解：（1）设a ∗满足a T y i ≥b ，则它一定也满足a T y i >0，所以引入余量后的解区位于原来的解区a T y >0之中。（2）a T y i ≥b 解区边界为：a T y i =b ，a T y i >0解区边界为：b a T y i =0，a T y i =b 到a T y i =0的距离为。i •4.10证明，在几何上，感知器准则函数正比于被错分类样本到决策面的距离之和。∑证明：感知器准则函数为J (a ) =(−a T y ) 。决策面方程为：a T y =0。当y 为错分类

y ∈Y

样本时，有a T y ≤0，到决策面的距离为−a T y 。所有错分类样本到决策面的距离之和∑为(−a T y ) ，就是感知器准则函数。

y ∈Y

•4.12写出Widrow-Hoff 法程序框图。

解：平方误差准则函数J (a ) =||Y a −b ||=

或MSE 解为：a ∗=(Y {2N ∑(a T y n −b n ) 2，它的最小二乘解，伪逆解=n =1T Y ) −1Y T b ，采用梯度下降法来求解a ∗。J (a ) 的梯度为∇J (a ) 2Y T (Y a −b ) ，则梯度下降法可以写成

ρ1，式中ρ1为任意正常数。k a (1)，选择ρk =a (k +1) =a (k ) −ρk Y T (Y a −b )

为了进一步减小计算量和存储量，可以将上述算法修改为（单样本修正）

{a (1)

a (k +1) =a (k ) −ρk (a (k ) T y k −b k ) y k

ρ1，还有y k 和前面感k 知器准则函数中的单样本修正法一样，是在无限重复序列中的错分类样本。让ρk 随着k 的增加而逐渐减小，以确保算法收敛。一般选择ρk =

•4.13

–（1）证明矩阵恒等式(A +xx ) T −1=A −1A −1xx T A −1−1+x A x

–（2）利用上试结果证明式（4-98）。

证明：（1）

() () −1xx T A −1−1xx T A A (A +xx T ) A −1−=(A +xx T ) I −A −11+x A x 1+x A x () T T A −1xx T xx xx =A +xx T −−A −11+x A x 1+x A x

=AA −1

=I

所以(A +xx ) T −1

（2）R (k +1) −1

T R (k ) R (k ) y k y k

R (k ) y 1+y k k A −1xx T A −1=A −1+x A x T ，利用上面的结果可以得到：R (k +1) =R (k ) −=R (k ) −1+y k y k −1

•4.14考虑准则函数

J (a ) =∑(a T y −b ) 2

y ∈Y (a )

其中Y (a ) 是使a T y ≤b 的样本集合。设y 1是Y (a ) 中的唯一样本，则J (a ) 的梯度为∇J (a ) =

T 2(a T k y 1−b ) y 1，二阶偏导数矩阵D =2y 1y 1。据此证明，若最优步长选择为ρk =

||∇J (a ) ||2

时，梯度下降法的迭代公式为：(a ) D ∇J (a )

a k +1b −a T k y 1y 1=a k +1∑(a T y −b ) 2=(a T y 1−b ) 2，证明：y 1是Y (a ) 中的唯一样本，则准则函数为J (a ) =

y ∈Y (a )

T 。所以∇J (a ) =2(a T y 1−b ) y 1，二阶偏导数矩阵为D =2y 1y 1

224(a T k y 1−b ) ||y 1||梯度下降的迭代公式为：a k +1=a k −ρk ∇J (a k ) ，ρk =28(a k y 1−b ) y 1y 1y 1y 1

b −a T k y 1，将ρk 代入梯度下降的迭代公式：a k +1=a k +y 112=12||y 1

•4.15证明：当取

N N N N b = ,..., , ,..., N 1N 1N 2N 2 N 1N 2

MSE 解等价于Fisher 解。 T y 1] y T [11X 1 2 证明：Y = . =，a =[w 0, w ]T 则Y T Y a =Y T b ，化为：−12−X 2 . .

T y N

[1T 1

X T 1−1T 2−X T 2][11−12][][T 1w 0X 1=1−X 2w X T 1−1T 2−X T 2][N 111N 112]

设m 1=1∑1∑x i , m 2=x i ，上式可化为：N 1N 2i ∈C 1i ∈C 2

[N (N 1m 1+N 2m 2) T

T (N 1m 1+N 2m 2) S w +N 1m 1m T 1+N 2m 2m 2

2∑∑

i =1j ∈C i T ][][]w 00=w N (m 1−m 2) ) T =Nm T ，m =N ∑式中，S w =(x j −m i )(x j −m i ) ，且(N 1m 1+N 2m 2x i ，

上面的等式可以分解出两个等式，第一个得到w 0=

得到

[i =1T −m w ，将w 0代入第二个等式可以]1T −(N 1m 1+N 2m 2)(N 1m 1+N 2m 2) T +S w +N 1m 1m T 1+N 2m 2m 2w =N (m 1−m 2) N []1N 1N 2S w +(m 1−m 2)(m 1−m 2) T w =m 1−m 2N N

N 1N 2(m 1−m 2)(m 1−m 2) T w 在m 1−m 2的方向上，所以上式可以化为：N

S w w =α(m 1−m 2) 注意因为

与Fisher 的解相同。

•4.16证明：[]a T y 0–(1)式(4-113)表示的向量y −表示y 到X 空间中超平面的投影。w

–(2)该投影正交于X 空间的超平面。

[])a T y 0证明：（1）先证明这个向量在X 空间中的超平面上，再证明y −y −2w

的向量为X 空间中超平面的法向量。X 空间中的超平面的方程为：g (x ) =w T x +(

[][]T y a x T 0x 0=[1, w T ]0=a T y =0，将向量代入g (x ) ，得a T y −a =a T y −x w ([])[]a T y a T y 0a T y 02||w ||=0，又因为y −y −=22w 2w

•4.17在多类问题中，如果一组样本可被一线性机全部正确分类，则称这组样本是线性可分的。对任意w i 类，如果能用一超平面把w i 类的样本同其他样本分开来，则称总体线性可分。举例说明，总体线性可分必定线性可分，但反之不然。

解：

图3:

总体线性可分必定线性可分

图4:线性可分未必总体线性可分

•4.18设有一组样本。若存在c (c −1)/2个超平面H ij ，使H ij 把属于w i 类的样本同属于w j 类的样本分开，则称这组样本是成对线性可分的。举列说明，成对线性可分的样本不

一定线性可分。

图5:成对线性可分不一定定线性可分

§5非线性判别函数

•5.1举例说明分段线性分界面可以逼近贝叶斯判别函数确定的超曲面。

解：分段线性函数是一类特殊的非线性函数，它确定的决策面由若干个平面段组成，所以它可以逼近各种形状的超曲面。

•5.2已知两类问题如图6所示，其中``×'' 表示w 1类训练样本集合的原型，``⃝'' 表示w 2类训练样本集的原型。

–(1)找出紧互对原型集合P ；

–(2)找出与紧互对行集相联系的超平面集H ；

–(3)假设训练集样本与原型完全相同，找出由超平面集H 产生的z (x )

。

图6:一个两类问题的原型分布

解:（1）用坐标来表示样本w 1中的样本(4, 6) 与w 2中的样本(5, 5) 是紧互对原型，(3, 4) 与(3, 2) 是，(2, 5) 与(1, 3) 也是。如图7所示（2）如图8所示

§6近邻法

•6.1举例说明最近邻决策面是分段线性的。

解：分段线性函数的决策面由若干个超平面组成。由于它的基本组成仍然是超平面，因此，与一般超平面

•6.2证明式(6−14) ∼(6−18) 。

证明：记c ∑

i =1P 2(w i |x ) =P 2(w m |x ) +∑i =m P 2(w i |x )

图7:紧互对原型

•6.3在什么情况下，最近邻平均误差P 达到其上界

•6.5有7个二维向量：x 1=(1, 0) T , x 2=(0, 1) T , x 3=(0, −1) T , x 4=(0, 0) T , x 5=(0, 2) T , x 6=(0, −2) T , x 7=(−2, 0) T ，假定前三个为w 1类，后四个为w 2类。

–(1)画出最近邻法决策面；

–(2)求样本均值m 1, m 2，若按离样本均值距离的大小进行分类，试画出决策面。解：第一首先要明确什么是“最近邻法”？它实际是一种分段的线性判别函数。第二根据离样本均值的距离来分类，首先求出两类的样本均值，分类决策面就是样本1均值的垂直平分线。(1)如图9所示。(2)w 1类的均值为m 1=(, 0) T ，w 2类的均值2T 为m 2=(−1, 0) ，决策面如图10所示。

•6.6画出k -近邻法得程序框图。

解：取未知样本x 的k 近邻，看这k 近邻中多数属于哪一类，就把x 归为那一类。•6.7对于有限样本，重复剪辑是否比两分剪辑的特性要好。

•6.8证明如果B +D (x i , M p )

D (x, x i ) +D (x i , M p ) >D (x, M p ) ⇒D (x, x i ) >D (x, M p ) −D (x i , M p )

所以如果当前近邻距离x 的距离为B ，D (x, x i ) >D (x, M p ) −D (x i , M p ) >B ，即当

B +D (x i , M p )

时，x 的近邻一定不在X p 中。

知识点：近邻法的快速算法。

图8:利用紧互对原型设计的分段线性分类器

§7

§8经验风险最小化和有序风险最小化方法特征的选取和提取

•8.1三类w 1, w 2, w 3，求S w , S b 。

解：对应w 1类的样本点{(1, 0) T , (2, 0) T , (1, 1) T }，

w 2类的样本点{(0, 1) T , (−1, 0) T , (−1, 1) T }，

w 3类的样本点{(0, −1) T , (−1, −1) T , (0, −2) T }。

41w 1类的均值u 1=(, ) T ，协方差矩阵为：33

1∑Σ1=(x i −u 1)(x i −u 1) T

3x ∈w 1i () 12−1=9−12

22w 2类的均值u 2=(−, ) T ，协方差矩阵为：33

1∑Σ2=(x i −u 2)(x i −u 2) T

3x ∈w 2i () 121=912

图9:最近邻法分类决策面

14w 3类的均值u 3=(−, −) T ，协方差矩阵为：33

1∑Σ2=(x i −u 3)(x i −u 3) T

3x ∈w 3i () 12−1=9−12所以类内散布度矩阵为：

1S w =(Σ1+Σ2+Σ3) 3() 16−1=27−16

1∑11u i =(, −) T ，所以类间散布度矩阵为：总体均值为u =3993i =11∑S b =(u i −u )(u i −u ) T

3i =1() 16213=8113623

•8.2设有两个正态分布的样本集，它们的期望及方差矩阵分别等于上题中w 1及w 2的均值向量及协方差矩阵，计算w 1和w 2的散度及Bhattacharyya 距离。

解：

p (x |w i ) =111exp [−(x −u i ) T Σ−i (x −u i )]d /21/22(2π) i

图10:按样本均值分类的决策面

I 12=p (x |w 1) p (x |w 1) ln d x p (x |w 2}∫{1|Σ2|111−1T T =ln −tr [Σ−1(x −u 1)(x −u 1) ]+tr [Σ2(x −u 2)(x −u 2) ]p (w |x 1) d x 2122

J D =I ij +I ji ∫p (x |w i ) =[p (x |w i ) −p (x |w j )]ln p (x |w j )

111−11−1=tr [Σ−Σ+ΣΣ−2I ]+(u 1−u 2) T (Σ−21121+Σ2)(u 1−u 2) 22∫w 1和w 2的散度为：

§9基于K-L 展开式的特征提取

•9.1若有下列两类样本集：

w 1w 2

x 1=(0, 0, 0) T y 1=(0, 0, 1) T

x 2=(1, 0, 0) T y 2=(0, 1, 0) T

x 3=(1, 0, 1) T y 3=(0, 1, 1) T

x 4=(1, 1, 0) T y 4=(1, 1, 1) T

用K-L 变换，分别把特征空间维数降到d =2和d =1并用图画出样本在该特征空间中的位置。

解：w 1和w 2的协方差矩阵分别为： 0. 750. 250. 251Σ1= 0. 250. 75−0. 25 40. 25−0. 250. 75

0. 750. 250. 251

Σ2= 0. 250. 75−0. 25

4

0. 25−0. 250. 75

则总类内散布度矩阵S w 为：

1. 50. 50. 51 1

0. 51. 5−0. 5 S w =(Σ1+Σ2) =

28

0. 5−0. 51. 5

−1

5−431 2它的特征值矩阵和特征向量分别为：

1 −0. 500

1 1Λ= 020 , U = −41002

−1

−5

所以，降到d =2维的变换矩阵U = 4

1

31 2

又S b 为

S b = −1−1所以

−11

1−111

u T S b u 1

J (x 1) =1=0. 375

λ1u T S b u 2

J (x 2) =2=0

λ2u T S b u 3

J (x 3) =3=0

λ3

•9.3令Σi 和P i 分别为类w i (i =1, 2) 的协方差矩阵和先验概率。假定对数据进行白化变∑

换，即使得B T S w B =I ，这里S w =i P i Σi ，I 是单位矩阵。证明矩阵P 1B T Σ1B 和矩阵P 2B T Σ2B 所产生的K-L 坐标轴是相同的，若用Λi 表示矩阵P i B T Σi B 的特征值矩阵，求证：

Λ1=I −Λ2证明：因为：

S w =P 1Σ1+P 2Σ2

B T S w B =P 1B T Σ1B +P 2B T Σ2B =I

设P 1B T Σ1Bu =λu，则

(I −P 2B T Σ2B ) u =λuP 2B T Σ2Bu =(1−λ) u

可见矩阵P 1B T Σ1B 和矩阵P 2B T Σ2B 具有相同的特征向量。产生的K-L 坐标轴相同。再由上面的推倒，设P 1B T Σ1B 的特征值为λ1则P 2B T Σ2B 有一个特征值λ2=1−λ1容易得到特征值矩阵满足Λ1=I −Λ2

§10非监督学习方法

•10.1令x 1, x 2,..., x N 是d 维样本，Σ是任一非奇异d ×d 矩阵，证明使

N ∑k =1

N 1∑

最小的向量x 是样本的均值µ=x i

N

i =1

(x k −x ) T Σ−1(x k −x )

证明：设

g (x ) =

上式对x 求导得

N ∑k =1

(x k −x ) T Σ−1(x k −x )

N

∑∂g(x ) =2Σ−1(x −x k ) ∂x

k =1

导数为0得到极值，易得

N 1∑

x k x =N

k

x T x ′

•10.2令s (x , x ) =。若x 的d 个特征只取+1和−1二值，即当x 具有第i 个特征时，

x i =1而当x 没有这个特征时x i =−1，说明s 是一个相似性度量。证明对于这种情况

′

||x −x ′||2=2d (1−s (x , x ′))

证明：

||x −x ′||2=(x −x ′) T (x −x ′)

=x T x −2x T x ′+x ′T x ′=2d −2x T x ′

x T x ′

=2d (1−)

x T x ′

=2d (1−)

=2d (1−s (x , x ′))

•10.3假使一个有N 个样本的集合X 划分为c 个不相交的子集X 1,..., X c ，假使X i 是空集，则X i 中样本的均值m i 不定义。在这种情况下，误差平方和只和非空子集有关：

∑∑J e =||x −m i ||2

i x ∈X i

这里i 是不包含空子集的子集标号。假定N c , 证明使得J e 最小的划分中没有空子集。证明：假设存在一个空子集X k , 1 k c 使得J e 最小，容易证明可以找到所有子集都

不为空的划分使得J e 更小。