模式识别与机器学习 习题及答案 孙仕亮

第2章贝叶斯学习基础思考与计算1. 对于2.1节给出的示例“假设某个动物园里的雌性和雄性熊猫的比例是4：6，雌性熊猫中90%的熊猫是干净整洁的，雄性熊猫中计算在该动物园中看到一只干净整洁的雄性熊猫的概率是多少？如果看到一只熊猫是干净整洁的，它是雄性的概率是多少？答：已知p(F),

p(M)0.6,

p(C|F),

p(C|M)0.2p(C,M)p(C|M)p(M)0.2p(M|C) p(C|M)p(M) p(C|M)p(M)p(C|F)p(F) 0.120.36

(2-2)2. 举例说明最小风险贝叶斯决策与最小错误率贝叶斯决策的不同。斯决策和最小风险贝叶斯决策的决策过程。假设患病白细胞浓度服从均值为2000，标准差为1000的正态分布，未患病白细胞浓度服从均值为7000，标准差为3000的正态分布，患病的人数比例为0.5%，问当白细胞浓度为3000时，应该做出什么决策？设w表示是否患病，x表示白细胞浓度，根据题意可以得到p(w0.5%p(w2)p(x|w

(2000,10002)p(x|w2)

(7000,30002)w的后验分布，计算结果如下：p(w1|x)p(x|wp(w=1.9%p(x)

p(w2|x)p(x|w2)p(w2)=98.1%p(x)

其中p(x)p(x|wp(wp(x|wp(w

(2-9)贝叶斯最小错误率决策会选择后验概率最大的类别，即h(x)2。阵为（只是假设，合理的数值应该视真实情况而定）0100

1 0其中表示将第i类数据判别为第j类的损失，也可以用(h(x)j|wi)表示。在该例子中，12表示将患病判别为正常的损失，21表示将正常判别为患病的损件风险的计算如下：R(h(x)|x)(h(x)|wi)p(wi|x)i

(2-11)可以得到将x判别为不同类别的条件风险为R(h(x)1|x)(h(x)1|wp(w1|x)(h(x)1|w2)p(w2|x)

(2-12)R(h(x)2|x)(h(x)2|wp(w1|x)(h(x)2|w2)p(w2|x)

(2-13)最小风险贝叶斯决策会选择条件风险最小的类别，即h(x)1。3. 给出在两类类别先验概率相等情况下，类条件概率分布是相等对角协方差矩阵的高斯分布的贝叶斯决策规则，并进行错误率分析。得到p(x|wi)

(μi,i),iC.贝叶斯决策得到的判别函数为gi(x)p(x|wi)p(wi)d1|

|lnp(wi)1(xμ)

1(xμ).

(2-15)2 2 i

2 i i i通过判别函数可以得到决策面gi(x)gj(x)，具体形式为1(xμ)

1(xμ)(xμ)

1(xμ

)p(wi)1|i|

(2-16)2 i i i j j j

p(wj) 2 |j|假设两类类别先验概率相等，即

p(wp(w2)

，那么p(wi)

p(wj)0gi(x)中的p(wi)类别的协方差矩阵都相等且为对角阵时，假设2...C，判别函数(2-15)可简化为g(x)1(xμ)

1(xμ).

i 2 i i将上式展开，忽略与i无关的项x

1x，判别函数进一步简化为i ig(x)(1μi i

x1μi ii i

1μ.

此时判别函数是xRi与Rj相邻时，决策面满足方程gi(x)gj(x)即

(μiμj

(xx0)其中x1(μ

μ).

(2-21)0 2 i j即x0为μi与μj连线的中点。在两分类问题下，决策面方程为1(μ

μ)

x1(μ

μ)

1(μ

μ)0.

(2-22) 1 2

2 1 2 1 2（2）为了计算错误率，这里引入最小错误率决策的负对数似然比，r(x)lnp(x|wp(x|w

(2-23)最小错误率贝叶斯决策可以表示为：如果r(x)lnp(x|wp(x|w2)如果r(x)lnp(x|wp(x|w2)

(2-24)由于r(x)是随机变量xr(x)也是随机变量。记其条件概率密度函数为p(r|，贝叶斯平均错误率的计算可以转变为关于r(x)的积分。令(error)表示将第一类样本判定为第二类的错误率，p2(error)表示将第二类样本判定为第一类的错误率，则通过先验概率加权可得（平均）错误率，即p(error)(error)0.5p2(error),其中每一类错误率可以表示为(error)

p(x|w

p(h|w12(or)R1p(x|w2dx

p(h|w2)dh.

(2-26)其中r(x)的决策边界为因此，如果知道r(x)的条件概率密度函数，即可算出错误率(error)和p2(error)。根据p(x|wi)

(μi,i),

i2，可得r(x)lnp(x|wlnp(x|w2)1(xμ)

1(xμ)dln1ln||2

1 1 2 2 1(xμ)

1(xμ

)dln1ln||2

2 2 2 2

(2-28)1(xμ)

1(xμ)1(xμ)

1(xμ

)1ln||2 1 1 2

2 2 2 ||(μ

μ)

1x1(μ

1μμ

1μ).2 1 2

1 1 2 2x虽是d维高斯分布的随机变量，r(x)却是一维的随机变量，并且是关于x的线性函数。上式可以看作对x的各分量进行线性组合，然后平移，所以r(x)服从一维高斯分布。下面计算一维高斯分布p(r(x)|w的期望和方差1：

[r(x)|w(μ

μ)

1μ

1(μ

1μμ

1μ)

(2-29)2 1 1 2

1 1 2 21(μ

μ)

1(μ

μ).2 1 2 1 2令m1(μ

μ)

1(μ

μ)，则

，并且2 1 2 1 2m2 2 11)|wμ2)μ2)

(2-30)同理可得p(r|w2)的期望m2和方差2为m1(μ

μ)

1(μ

μ)2 2 1 2 1 22(μ

μ)

1(μ

μ)2 1 2 1 2现根据式(2-26)计算(error)和p2(error)，得到(error)

p(r|w 1

exp{1(rm)2}dh1 2 )21

1rm rm)2exp{ ( )2}d( )2 1m

1)2exp( 2)d,2p2(error)

p(r|w2)dh1 1rm rm)2( )2}d( )

(2-33)m 1

2 )

2exp(12)d.其中，

2

(2-34)因此，(error)和p2(error)表示为标准高斯分布 在对应区域上的概率值。4. 推导高斯分布的均值与协方差的最大似然估计。 答：最大似然估计的求解目标为NlnN(xi|)μ,

i1下面分别求解均值和协方差。（1）对对数似然函数关于均值求导并设置为零可以得到如下方程： Nd lnN(x

|μ,)

N 1 1nd (n

μ)

1(x

i

1/2 i iidμ

i1|| 2dμN1 d(xN

μ)

1(x

μ)2 i i2 i1dμN1 (d(x

μ))1(x

μ)+(x

μ)

d(1(x

μ))22 i1N

i i i idμ

(2-35)1 (x

μ)1(d(x

μ))+(x

μ)

d(1(x

μ))22 i1N

i i i idμi12(xi2i1

μ)dμ

1dμ

Ni1

(xi

μ)

10

1N1μm iNi1（2）对对数似然函数关于协方差求导并设置为零可以得到如下方程：NarglnN(xi|μ,)μ,N

i1Nd lnN(x

|μ,) d

1 1n(n

μ)

1(x

i

1/2 i iidN

i1

2| 2d2 2Ndln|2 2

d((x

μ)

1(x

μ)) i i i1dN

(2-36)NTr[1d]1

dTr[(x

iμ)(xi

μ)

1(d)1] 2 2i12 2N 2 2 Tr[d] i1N

ddTr[1(xd

iμ)(xi

μ)

1(d)]N11(xi1

iμ)(xi

μ)

10

1N (xμ

)(xμ)Nm N

i m i m5. 推导高斯分布的均值的最大后验估计。答：均值μ的对数后验分布可以表示为Nlnp(μ| )lnp(xi|μ)lnp(μ)consti1Nln (xi|μ,)+ln (μ|0,μ)const,i1

(2-37)其中const表示与均值μ无关的项。对对数后验关于均值求导并设置为零，可以得到如下方程：(x(xi|μ,)n μ|,μ)dlnidμnN 1 nd (x

μ)

1(x

dln 1 xp{1μ

e 1/2 i ie

1/2 μ i1N|| 2 |μ| 2dμ1 d(x

μ)

1(x

μ)1dμ

2 i i 2 μ2 i1dμN21 (d(x2

μ))1(x

μ)+(x

μ)

d(1(x

μ))1(dμ

+μ

d1μ) i1N

i i i i 2 μ μdμ1 (x

μ)

1(d(x

μ))+(x

μ)

d(1(x

μ))1(μ

1dμ+μ

1dμ)22 i1N

i i i i

2 μ μμiN1(2(xμiN

μ)

12μ

1)dμ2i1

i1

(xi

μ)

1μ

10

μ(2-38)μ

.mN(N11)1.m

(N)1m6. 推导高斯分布的均值的贝叶斯参数估计。m答：假设均值服从高斯分布)p)p(|)p).p( )

(0,)，根据如下贝叶斯公式，

(2-39)可以得到均值的后验分布表达式为p(μ|

N)N)pμp(xi|μ)/p( )

NμNμ|,μ (xi|μ,)/p( )N 1 1= μ

1 1(x

μ)

1(x

μ)}/p( )1/2

μ 1/2 i i|μ| 2N

i1|| 2N 1 1

exp{1μ

1(x

μ)

1(x

μ)/p( )|2|2

2 μ 2 i iμ

i1N N 1 1

exp1μ

1

x1x

1xμ

1μ/p( )1/2

1/2

μ i i i |μ|

||

2 2i1 N N 1 1

1exp μ

(1+N1)μ2Nμ

1μ

x1x/p( )1/2

1/2

μ

m i i|μ|

||

2

i1 1exp μ

(1+N

1)μ

2Nμ

Nx

1x

const2 μ

m i i i1 =exp1μN(1+N1)1μ

(1+N1)1μN(1+N1)1μ

const2

m mm m= N

(N

)1

,(1N1)1.第3章逻辑回归思考与计算1. 选择一个UCI数据集，比较线性回归和岭回归的错误率。2. 请编程实现二类分类的逻辑回归,要求采用牛顿法进行优化求解。3. 证明一元高斯似然关于方差的共轭先验是逆伽马分布。设前提下，方差的后验分布是逆伽马分布。假设似然函数为如下高斯分布：N 1 p(y|X,β,2)2)2 (y(y,

(3-1) 2 假设方差的先验分布为逆伽马分布Inv-Gamma(a0,)，即p2)2)01(0,2

(3-2)根据贝叶斯公式可以得到方差的后验分布表达式如下2|y,X,β)2)p(y|X,β,2)/p(y|β)N(2)a0exp(2)(

2exp1yXβ)(yXβ)const2 2 a1N2)0 2exp

12(y

Xβ)(y

Xβ) 2 N 1 a0 (yXβ)(yXβ)2 2 4. 思考如何优化使用范数进行正则化的最小二乘。答：对于目标函数不是连续可微的情况，可以用次梯度来进行优化，范数的次梯度表示为

1

d0 1=sign(β) 1

0

dd0但次梯度存在两个问题：求解慢，通常不会产生稀疏解。此时可以用ProximalGradientDescent对范数正则化问题进行求解。求解过程如下。使用范数进行正则化的最小二乘的优化目标表达式如下：S

Nyf(x,)2|

i i N其中 y

f(x,)2

是可导函数，记为g(β)，且

不可导。 i i i1根据泰勒展开式g(β)可以表示为g(β)g(β

)(g(β

))(ββ

)1(ββ)

H(g(β

))(ββ

)o(||β

||2)(3-5)k k k 2

k k k k2假设g(β)满足L-Lipschitz条件，即存在常数a0使得||g(β)令H(g(βk))aI，公式(3-5)可以使用如下表达式近似ag(β)g(βk)(g(βk))(ββk)2

(ββk)(ββk)2

(3-7)aββ2

1g(β )ak k)ak k

const其中const是与变量β无关的常数。公式(3-7)中的g(β)在β=βk最小值。

1g(βa k

)时取得如果使用梯度下降来求得g(β)的最小值，在第k1步，更新公式为βk+1

=βk

1g(β)a k使用类似的思想来求解公式(3-4)的最小值，在第k1步，更新公式可以表示为βk+1

arga2

ββ

1g(β )a k)

2L||β||L1

kβ 2k公式中的优化目标中可以分别计算β的每一维βd表示为βd argmaxaβdβ

1g(β

d2)2

|βd|2k+12

βd

k a kd 2argmaxaβdβ

1g(β)

constaa aa2βd 2

k k d d βdβ

1g(β)

,

β1g(β)

0 k a

k a

k a

k a dβ)d β)dβdβ

1g(β

),

1g(β k a k

0a k a

k a dβd

β

1g(β) a k a

k a 第4章概率图模型基础思考与计算1. 设计一个贝叶斯网络的图模型，并写出所有变量的联合分布。4-1所示的一种生成式混合高斯过程图模型，其中最左侧的节点以及中间方框中的θk和Ik表示模型的超参数，其余中间与右侧方框中的节点表示模型的随机变量。图4-1混合高斯过程的图模型观察图4-1所示的贝叶斯网络的图模型，为了方便表示，使用表示12,...,z表示,z2,...,zN，使用X表示,x2,...,xN，使用y表示,y2,...,yN，可以得到如下联合分布：,μ,R,W,r,z,X,y)k|0)p(μk|μ0,R0)p(Rk|0,)p(Wk|θk,Ik)|a0,)kNp(zi|)p(xi|zi,μ,R)p(yi|zi,xi,W,r)i1

(4-1)2. 分析图4-7所示的贝叶斯网络中的其他变量之间的条件独立性。图4-7使用d-分隔判断条件独立性示例答：下面分别分析图a与其他所有变量的关系。在图4-7（a）中，节点a到节点c,d,f,g,b均只有一条路径。路径中，a到cc,d是顺序结构且ca到da,c,f是汇总结构且c的后代节点e被观测，因此a到f不被阻隔；节点c,f,g是发散结构且f未观测，因此c到g不被阻隔；节点f,g,b是顺序结构且g是未观测，因此f到b不被阻隔。总的来说，节点a到节点c,d,f,g,b均不是d-分隔的，因此在给定节点e后，节点a和节点c,d,f,g,b均不是条件独立。在图4-7（b）中，节点a到节点c,d,e,f,b均只有一条路径。路径中，a到cc,d是顺序结构且ca到dd,e是顺序结构且dc到ea,c,f是汇总结构且c的后代节点不被观测，因此a到f被阻隔；节点f,g,b是顺序结构且g被观测，因此f到ba到b是ga和b条件独立，即有af|g和ab|g。3. 写出图4-13所示的无向图的联合概率表示。图4-13满足条件独立性AB|C的无向图模型示例答：根据无向图模型的条件独立性，可以得到图4-13中的所有变量的联合分布表示为：p(x1,,,,,,,)p(x4,)p(x1,,,,,|,)p(x4,)p(x1,,|,)p(x6,,|,)

(4-2)若将概率分布根据最大团进行分解，则可以得到如下表示：p(x4,)p(x1,x2,|x4,)p(x6,x7,|x4,)1 1 1

(4-3) (x4,)Z2

21,2|4,532,3|4,5,,|,Z3图4-23因子图示例答：如图4-23所示，若只需计算节点,x2,,x4,中某一个变量的边缘分传递既可以得出所有随机变量的边缘分布。这里将图4-23中的x3作为根节点进行两次消息传递，两次消息传递示意图如图4-24（a）和图4-24（b）所示、x4和x5向根节点x3传递x3向叶子节点和x5传递图4-24对应图4-23的和积算法的消息流示意图从叶子节点向根节点的消息传递如下：1axf1a

1fx

x2fa,x2a 24cxf4cfxx41x2fcx2,x4c 25dxf5d1fx

x2fdx2,d 2xfx2fx

x2fx

x2fx

x22 b a 2 c 2 d 2fx

fbx2,xf

x2.b 3 2 bx2从根节点向叶子节点的消息传递如下：3bxf3b

1fx

x2fbx2,b 2xfx2fx

x2fx

x2fx

x22 a b 2 c 2 d 2fxfa,x2xf

x2a 1 2 ax2xf

x2fx

x2fx

x2fx

x22 c a 2 b 2 d 2fx

x4fcx2,x4xf

x2c 4 2 cx2xf

x2fx

x2fx

x2fx

x22 d a 2 b 2 c 2fx

x4fdx2,x

x.d 5 5

x2fd 2,x2,,x4,的边缘分布如下：p(x1)fxx2fax1,x2xf

x2a 1 2 ax2fa,x2fx

x2fx

x2fx

x2b 2 c 2 d 2x2fa,x2fbx2,fcx2,x4fdx2,p(x2)fxx2fxx2fx

x2fxx2a 2 b 2 c 2 d 2fa,x2fbx2,fcx2,x4fdx2,b 3 2 bp(x3)fxfbx2,xfb 3 2 bx2fbx2,fx

x2fx

x2fx

x2a 2 c 2 d 2x2fbx2,fa,x2fcx2,x4fdx2,.p(x4)fx

x4fcx2,x4xf

x24 2 cx2fcx2,x4fx

x2fx

x2fx

x2a 2 b 2 d 2x2fcx2,x4fax2fbx2,fdx2,p(x5)fx

x4fdx2,xf

x25 2 dx2fdx2,fx

x2fx

x2fx

x2a 2 b 2 c 2x2fdx2,fa,x2fbx2,fcx2,x4第7章支持向量机思考与计算1. 查找资料理解并推导互补松弛条件。解相同的必要条件之一，所有的必要条件也称为KKT条件。下面介绍拉格朗日对偶优化的原理，以及KKT条件的推导过程。假设带有约束的优化问题表示为(7-1)定义原问题的最优解为x*，目标的最优值为p*。拉格朗日对偶优化的基本思想是将约束条件以一定的权重加入到原优化目等价的解。首先，分别对约束条件引入拉格朗日乘子（也叫做对偶变量）ii拉格朗日函数L，具体表示如下：(7-2)其次，计算拉格朗日函数关于x的下界，得到拉格朗日对偶函数g(,)(7-3)进一步分析(7-3)与原问题最优值的关系。假设x表示满足约束条件的任意变量，那么可以得到如下不等式：(7-4)因此拉格朗日函数满足如下关系拉格朗日对偶函数满足如下关系由于原问题的最优解为x*也包含在x中，因此可以得到

(7-5)(7-6)(7-7)至此我们可以得到，对偶函数一定小于或等于原优化问题的最优值。因此，意义，它可能会达到原优化问题的最优值。定义对偶函数的解为*,*，最优值为d*，可以得到d*p*下面分析满足什么条件时，对偶函数的解与原问题的解等价。首先，根据原问题和对偶问题的定义，可以得到如下等式和不等式关系(7-8)偶函数的定义式(7-3)中的结果，第三行不等式利用了下界的含义，第四行利用l不等式约束条件。此，可以得到(7-9)由于每一个不等式约束都小于等于(7-10)该等式被称为互补松弛条件，表示f(x*)*中至少有一个为0。此外，根据(7-8)i im0 0 ii

pii还可以得到f(x*)是f

*f(x)

*h(x)的最小值，x*为其中的一个最下：2. 由支持向量机的原始优化目标推导得出拉格朗日对偶优化，即给出书中公式（7.7）到公式（7.9）的推导过程。能会达到原优化问题的最优值，特别是当满足KKT条件时，它等于原优化问题问题的解以及对偶问题的解满足强最大-最小性质，或者叫做鞍点性质。下面描述强最大-最小性质，并给出支持向量机的拉格朗日对偶优化表示。L来描述原问题的最优解p*示为满足条件的原问题或者是无穷大，形式化表示如下：这意味着拉格朗日函数的上界的最小值为原问题的最优值，即其次，根据前文中对偶问题的最优解的定义，可以得到并且两个问题的最优解的满足不等式关系如下：

d*p*d*p*，也被称为强对偶性，具体表示为支持向量机的原优化问题表示为，

(7-16)

w,b

1||w||22(wxib)1N).

(7-17)引入拉格朗日乘子向量,2,...,N]，我们便可以通过拉格朗日函数将约束条件融入到目标函数中，得到优化问题(7.7)对应的拉格朗日函数为NL(w,b,)1||wN

(y(wx

b)

(7-18)22

i i i其中各乘子变量i(i2,...,N)均为非负值。根据公式(7-13)，原问题表示为,

0L(w,b,wb i根据公式(7-16)，对应的拉格朗日对偶优化问题表示为：

0,

L(w,b,i wb3. 支持向量机是否可以处理多类分类，如何实现？K习多个二类分类器，常用的方法有三种：（1）分别学习K个二类分类器，第k个分类器用于判别样本是否属于第k练第k个分类器时，使用属于第k类的数据作为正样本，不属于第k类的所有数据作为负样本。训练完成后，根据K个分类器的预测结果来判断新的样本应该N属于哪一个类别，假设第k个分类器的预测函数为fk(x)yiaixxi或者N i1fk()i(xi,)b那么最终的决策类别为h(x)gxfk()一对多k策略的优点是最终的决策比较明确，相比于一对一策略所需训练的分类器较少；决策不准确。（2）分别学习K(K个二类分类器，每个分类器用于判别该样本是属于i类和第j类，i2,...,K,j2,...,K,ijij分类ijij分类器将测试数据判别为ii类投票数加1而第j类投票数减点是训练数据平衡；缺点是需要训练较多分类器，且容易出现票数相等的情况。（3）设计新的优化目标，使用所有训练数据同时训练K个分类器，优化目标为最大化每一个类别到其他类别的间隔，带有松弛变量的多类SVM优化问题表示如下：K Nii

w,b,ξ

1||w

||2Ckk2kk

i1kyiwxb

(wx

b)2k,i

ki k ii(i2,,N),k2,...,K}\yi.该多类SVMN个训练样本上解决一个复杂度O(K2N2)（较高）的优化问题，因此训练速度较慢。4. 编程实现基于核方法的支持向量机，并在UCI数据集上测试性能。答：略第8章人工神经网络与深度学习思考与计算1. 思考如果将线性函数f(x)wx用作神经网络激活函数会有什么问题。答：激活函数的主要目的一是实现数据的非线性变换，解决线性模型表达、分类能力不足的缺陷；二是实现数据的归一化，将当前数据映射到某个范围内，f(x)wx用作神具有非线性表达的能力，只有在输出层进行回归任务时可能使用线性激活函数。2. 感知机神经网络的优缺点是什么？缺点是它要求数据线性可分，难以实现非线性分类问题，比如异或、同或运算。3.如何保证神经网络具有较好的泛化能力？问题。提升测试性能的常用方法包括如下几类：1、设计更合适的网络结构，如卷积神经网络和循环神经网络；2、使用与训练数据规模匹配的神经网络架构，声、调整数据分布。4. 编程实现神经网络的误差反向传播算法，尝试动态调整学习率以提升收敛速度，并在两个公开数据集上进行实验。答：略5. 编程实现卷积神经网络，并在手写字符识别数据集MNIST上进行实验。答：略6. 编程实现循环神经网络，运用不同的结构（如LSTM和据集上进行机器翻译实验。答：略第9章高斯过程思考与计算1.思考高斯分布与高斯过程的区别。答：高斯分布用于刻画观测数据x的分布，考虑更一般的情况，当x是多维x,x2,...,xD,x2,...,xN是服从D维高斯分布的独对观测数据{x,中x与y之间映射的分布，其分布的参数是均值函数和协方差点可以估计高斯过程的超参数。假设{x1,y1},{x2,y2},...,{xN,yN}均是服从高斯过,y2,...,yN的联合N阵由输入、均值函数与核函数确定。2. 参考图9-1像。答：图9-1展示了高斯过程 (0,k(x,

的三个样本，其中k(x,x)exp{(xx)2

4}。ff()xx图9-1高斯过程的三个样本示例（三条不同的曲线对应高斯过程的三个样本）构建过程如下：首先，在输入空间上均匀采样以获得输入{x1,x2,...,xN}。在该例子中输入为[-5,5]上的实数，假设采样100个数据输入{x1,x2,...,xN}。其次，采样获得对应的100个数据输出{y1,y2,...,yN}。由于输出服从多元高斯分布，其均值向量长度为100，协方差矩阵大小为100100。假设均值向量为零向量0k(x,x)exp{(xx)2K中的每一个元素。那么{y1,y2,...,yN}服从多元高斯分布(0,K)，从该分布中采样一个样本即可以得到一组{y1,y2,...,yN}，与输入{x1,x2,...,xN}对应则可以绘制出图1中的一条曲线。3. 思考高斯过程与用于回归的其他概率模型相比有哪些特殊性质。答：1) 布，在输出有噪声的数据上性能鲁棒。2) 高斯过程通过贝叶斯模型选择的方法来对模型中的超参数进行估计，这与支持向量机使用交叉验证选参数是不同的。高斯过程中的贝叶斯学习方法可以3)高斯过程预测结果具有概率意义，提供预测均值、方差和概率密度，其中均经网络回归模型只输出预测值是不同的。4) 高斯过程是一种核方法，不需要显示地构建非线性映射，实现非线性回归。这与贝叶斯线性回归模型不同，其核函数的思想与核SVM类似。5) 用训练数据。这与神经网络假设样本之间相互独立是不同的。6) 高斯过程的训练时间复杂度是O(N3)，预测时间复杂度是O(N2)非核方法模型的复杂度都要高，目前有许多研究能够降低复杂度。4. 编程实现高斯过程回归模型，并用回归模型实现二类分类问题。答：略第10章聚类思考与计算1. 尝试其他方法证明随着聚类数目的增加，K-均值聚类的总误差逐渐减小。答：略。可补充1KK-均值聚类算法可以看作一种EM算法，利用EM算法的收敛性可以证明K-均值聚类算法的收敛性。2. 分析K-均值聚类算法与基于EM算法的高斯混合模型聚类的关系。答：这里分析批处理的K-均值算法与高斯混合模型的关系。批处理的K-均值聚类算法可以看作高斯混合模型的一个特殊版本。高斯混合模型和K-均值聚设置。具体的关系分析如下。K-均值聚类算法属于硬聚类，迭代过程中，样本确定性地属于某一个簇，计算依据如下：znargmin||xk

nk

||2.

式如下：N1 N

I(z

k)x,

kN n nkNkn1其中，Nk

N

I(zn

k).会计算，计算公式如下：p(z

)k

(xn|μk,k).n Kjj

(xn|μj,j)其中

1

Np(z

)。在得到每个样本对所有簇的所属概率后，利用所有Nk N

n样本点计算每个簇的分布的均值和协方差。Np(znkNkn,Nkp(znk)

Np(znk)(xnk)(xnk)n1 .

(10-5)k Np(znk)n1当概率p(znk)取值非0即1时，即对p(znk)进行如下近似处理p(znk)

kp(znk),k

(10-6)并且固定kK氏距离考虑数据的协方差，马氏距离的平方的表示为d(x

)

)n k k n k这里之所以是近似关系，原因是公式(10-3)中包含的高斯密度函数不仅仅依赖于混合模型等价于K-均值聚类算法。3. 到公式(10.31)的推导过程。答：归一化切割（normalizedcut）的表示是 k k1KW(A, \ k kargmin ,H 2k

vol()h h i,k

1 ifvA,i kvol(i k0 i其中vol()表示集合中所有边的权重的和，即vol()=jAdjj。下面推导出最优切割目标(10-8)关于拉普拉斯矩阵的表示以及优化问题的解。i由于公式(10-8)中优化目标的每一项可以写为W(, \)1(vol() 2

iA,jA

1 vol()

iA,jA

1 )vol()k k k k1 (

1 0)2

(0

1 2ol(ol(k)ol(k)2iA,jol(k)

(10-9) k k k k 1NN

w(h

h)2ij ik jk2i1

jhkLhk.因此，优化问题(10-8)可以表示为argminTr(HLH),Hh h i,k

1 ifvA,i kvol(i k0 如果将H约束为指示矩阵进行优化，那么可能的解有2NK种，难以遍历求解。为了解决这个问题，可以对原优化目标进行近似求解，找到满足优化目标LH)的矩阵H，但不约束H为指示矩阵。根据(10-10)中义，可得到HI。不约束H为指示矩阵，但仍约束HI，归一化切割的优化问题(10-10)可以近似表示为Tr(FD12LD12F),FFF1 2K其中F2HK个拉格朗日乘子{,,...,1 2K量，可以得到与公式(10-11)等价的无约束优化问题，表示如下：argminTr(FD12LD12F)+TrF.H

(10-11)}(10-12)对公式(10-12)中的优化目标关于F求导并设置为零，可以得到最优解H满足LNF=diag()F,N其中L2N2

，且对应的目标值为KFNF)k.k

因此F的解为为归一化的拉普拉斯矩阵

22的前K个最小特征值对FHD12F得到矩阵H并对H按照行归一化（此过程可以合并为一步，即直接对F按照行归一化得到H数据表示H进行一次聚类，比如使用K-均值聚类。4. 使用一种谱聚类算法实现对人工合成的环状数据的聚类（如图答：略5. 编程实现K-均值聚类算法和高斯混合模型聚类算法，并选择3个不同数据集进行实验分析。答：略6. 选择一种聚类算法实现图像分割。答：略第11章主成分分析与相关的谱方法思考与计算1. 给出图中的示例数据上PCA的求解过程。图使用PCA将数据投影到一维空间的示例(图中直线上的点是使用PCA将数据{(1,3),(3,2),(3,5),(4,3)}投影到一维的结果。)首先，根据如下公式计算数据在原始空间的协方差矩阵S：N N NS1N

i1

(xi

1N

i1

xi)(xi

1N

i1

xi)

1.4286 1.4286= .1.4286

1.4286其次，对协方差矩阵进行特征值分解，即Su1得到最大的特征值为2.8571，对应的特征向量为.该向量为PCA意义下的最优投影向量，对原始数据进行投影可以得到z33 2 3 54 4 3

(11-4)在原空间中的位置为

2.0 2.0 z'z[2.8284,3.5355,5.6569,4.9497]

[0.7071,0.7071]

4.0

4.0 3.5 2. 思考概率PCA的解与PCA的解的区别。答：PCA的最优投影U是协方差矩阵S的M个最大特征值2,...,M对应的特征向量u1,u2,...,uM构成的矩阵U，投影后的数据表示为 1N zU

xzU

xNxn 概率PCA的最优潜变量z的后验概率分布为p(z|x)

(z|M

(xμ),2M1),其中MWW2I。模型参数的最大似然解为M mmW U2M mm2 1 Dm,

DMmM1Nμ x,

m n其中R表示，即zM

(xμ)。当2

0时，可以得到mzMm

(xμ)W)1W

(xμ)N(diag(λ)1/2UU

diag(λ)1/2)1diag(λ)1/2U

(x1 x)

(11-11)NM M MNN

nn1Mdiag(λ)1/2UM

(x1N

n1

xn)m分析PCA与在2m

0时概率PCA现此时概率PCA得到的投影方向与PCA的投影方向一致，但是概率PCA在各个主成分方向上的数值会比PCA放缩λ1/22

0m m3. 思考在LDA中，为什么SB的秩最大为C1。答：SB的表示为CSBNccc),

其中mcm列向量，其秩为1，即rABminrA,rB，可以得到

r(mcm)1。根据秩的乘法不等式性质rmcmc)

1

根据秩的加法不等式性质r(A+B)r(A)+，可以得到C rNc(mcm)(mcm)c1

CN C CN由于m1N

x1

Nm ，因此

N(m

m)

中的任意一项NiN

c c

c c cNc

可以表示为其他项的线性组合，继而可以得到C rNc(mcm)(mcm)c1

C14. 思考求解CCA中公式(11.71)所示的广义特征值问题的计算复杂度。w答：CCA中公式(11.71)所示的广义特征值问题是求解wx式

，使其满足如下等Cw

42Cw.x x该优化问题等价于求解公式形如的广义特征值问题。广义特征值问题可以通过一些变换转化为普通特征值问题。x的维度为Dx的维度为，样本个数为N。BB1可以得到B1C,C

,C的复杂度分别为O(ND2)，O(NDD)，O(ND2)C求逆的复杂度O(D3)C1x xy y xx

x 的复杂度O(D3)，矩阵乘法C1CC1C

的复杂度D,DD2})，特征值y xxxyyyxy

x y xy分解的复杂度O(D3)，因此总复杂度为D3,，这里分开x

x x y y（2）如果B矩阵可进行Cholesky分解，即BLL，其中L是下三角阵，通过引入新的向量L，可以得到等价的特征值问题A(L1)，其中(L1)。该方法的复杂度包括计算协方差矩阵C,C

,C的复杂度分别为O(ND2)，D)，O(ND2)C进行Cholesky分解的复杂度O(D3)x xy

y x算

的复杂度

O(D3)

，矩阵乘法LCLCCC

的复杂度xD,DD2,，特征值分解的复杂度O(D3)，因此总复杂度为xx y xy x xx x y yD3,x x y y杂度。5. 试推导核PCA在{(x

没有中心化情况下的投影表示。n

n

n1 nN答：{(xN

没有中心化，表示变换后的数据均值不为零，即

(x

)0，令(x

)(x

)1

N(x

)表示数据从原始空间到高维空间的中心化后的非Mn n Nn1 nMMPCA寻找投影向量{vm的数据(X)[(x2),...,(xN经投影后在子空间各个维度的表示M(X的方差总和最大。那么在高维空间上的协方差矩阵为MS1

N(x

n(xn)

N可以得到其主成分子空间的基向量vm满足如下公式Svmmvm,

(11-18)其中vm也表示投影向量，且vm满足1N

(x(x)v

v.

(11-19)NN

n n m mm由于(xn)

vm是一个标量，vm(xn的线性组合，记为Nvm(xn,

将式(11-20)带入式(11-19)中，可得N N N1 (x(x)

(x

) (x

(1