模式識(shí)別與機(jī)器學(xué)習(xí) 習(xí)題及答案 孫仕亮

第2章貝葉斯學(xué)習(xí)基礎(chǔ)思考與計(jì)算1. 對(duì)于2.1節(jié)給出的示例“假設(shè)某個(gè)動(dòng)物園里的雌性和雄性熊貓的比例是4：6，雌性熊貓中90%的熊貓是干凈整潔的，雄性熊貓中計(jì)算在該動(dòng)物園中看到一只干凈整潔的雄性熊貓的概率是多少？如果看到一只熊貓是干凈整潔的，它是雄性的概率是多少？答：已知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. 舉例說明最小風(fēng)險(xiǎn)貝葉斯決策與最小錯(cuò)誤率貝葉斯決策的不同。斯決策和最小風(fēng)險(xiǎn)貝葉斯決策的決策過程。假設(shè)患病白細(xì)胞濃度服從均值為2000，標(biāo)準(zhǔn)差為1000的正態(tài)分布，未患病白細(xì)胞濃度服從均值為7000，標(biāo)準(zhǔn)差為3000的正態(tài)分布，患病的人數(shù)比例為0.5%，問當(dāng)白細(xì)胞濃度為3000時(shí)，應(yīng)該做出什么決策？設(shè)w表示是否患病，x表示白細(xì)胞濃度，根據(jù)題意可以得到p(w0.5%p(w2)p(x|w

(2000,10002)p(x|w2)

(7000,30002)w的后驗(yàn)分布，計(jì)算結(jié)果如下：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)貝葉斯最小錯(cuò)誤率決策會(huì)選擇后驗(yàn)概率最大的類別，即h(x)2。陣為（只是假設(shè)，合理的數(shù)值應(yīng)該視真實(shí)情況而定）0100

1 0其中表示將第i類數(shù)據(jù)判別為第j類的損失，也可以用(h(x)j|wi)表示。在該例子中，12表示將患病判別為正常的損失，21表示將正常判別為患病的損件風(fēng)險(xiǎn)的計(jì)算如下：R(h(x)|x)(h(x)|wi)p(wi|x)i

(2-11)可以得到將x判別為不同類別的條件風(fēng)險(xiǎn)為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)最小風(fēng)險(xiǎn)貝葉斯決策會(huì)選擇條件風(fēng)險(xiǎn)最小的類別，即h(x)1。3. 給出在兩類類別先驗(yàn)概率相等情況下，類條件概率分布是相等對(duì)角協(xié)方差矩陣的高斯分布的貝葉斯決策規(guī)則，并進(jìn)行錯(cuò)誤率分析。得到p(x|wi)

(μi,i),iC.貝葉斯決策得到的判別函數(shù)為gi(x)p(x|wi)p(wi)d1|

|lnp(wi)1(xμ)

1(xμ).

(2-15)2 2 i

2 i i i通過判別函數(shù)可以得到?jīng)Q策面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|假設(shè)兩類類別先驗(yàn)概率相等，即

p(wp(w2)

，那么p(wi)

p(wj)0gi(x)中的p(wi)類別的協(xié)方差矩陣都相等且為對(duì)角陣時(shí)，假設(shè)2...C，判別函數(shù)(2-15)可簡化為g(x)1(xμ)

1(xμ).

i 2 i i將上式展開，忽略與i無關(guān)的項(xiàng)x

1x，判別函數(shù)進(jìn)一步簡化為i ig(x)(1μi i

x1μi ii i

1μ.

此時(shí)判別函數(shù)是xRi與Rj相鄰時(shí)，決策面滿足方程gi(x)gj(x)即

(μiμj

(xx0)其中x1(μ

μ).

(2-21)0 2 i j即x0為μi與μj連線的中點(diǎn)。在兩分類問題下，決策面方程為1(μ

μ)

x1(μ

μ)

1(μ

μ)0.

(2-22) 1 2

2 1 2 1 2（2）為了計(jì)算錯(cuò)誤率，這里引入最小錯(cuò)誤率決策的負(fù)對(duì)數(shù)似然比，r(x)lnp(x|wp(x|w

(2-23)最小錯(cuò)誤率貝葉斯決策可以表示為：如果r(x)lnp(x|wp(x|w2)如果r(x)lnp(x|wp(x|w2)

(2-24)由于r(x)是隨機(jī)變量xr(x)也是隨機(jī)變量。記其條件概率密度函數(shù)為p(r|，貝葉斯平均錯(cuò)誤率的計(jì)算可以轉(zhuǎn)變?yōu)殛P(guān)于r(x)的積分。令(error)表示將第一類樣本判定為第二類的錯(cuò)誤率，p2(error)表示將第二類樣本判定為第一類的錯(cuò)誤率，則通過先驗(yàn)概率加權(quán)可得（平均）錯(cuò)誤率，即p(error)(error)0.5p2(error),其中每一類錯(cuò)誤率可以表示為(error)

p(x|w

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

p(h|w2)dh.

(2-26)其中r(x)的決策邊界為因此，如果知道r(x)的條件概率密度函數(shù)，即可算出錯(cuò)誤率(error)和p2(error)。根據(jù)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維高斯分布的隨機(jī)變量，r(x)卻是一維的隨機(jī)變量，并且是關(guān)于x的線性函數(shù)。上式可以看作對(duì)x的各分量進(jìn)行線性組合，然后平移，所以r(x)服從一維高斯分布。下面計(jì)算一維高斯分布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現(xiàn)根據(jù)式(2-26)計(jì)算(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)表示為標(biāo)準(zhǔn)高斯分布 在對(duì)應(yīng)區(qū)域上的概率值。4. 推導(dǎo)高斯分布的均值與協(xié)方差的最大似然估計(jì)。 答：最大似然估計(jì)的求解目標(biāo)為NlnN(xi|)μ,

i1下面分別求解均值和協(xié)方差。（1）對(duì)對(duì)數(shù)似然函數(shù)關(guān)于均值求導(dǎo)并設(shè)置為零可以得到如下方程： Nd lnN(x

|μ,)

N 1 1nd (n

μ)

1(x

i

1/2 i iidμ

i1|| 2dμN(yùn)1 d(xN

μ)

1(x

μ)2 i i2 i1dμN(yùn)1 (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）對(duì)對(duì)數(shù)似然函數(shù)關(guān)于協(xié)方差求導(dǎo)并設(shè)置為零可以得到如下方程：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. 推導(dǎo)高斯分布的均值的最大后驗(yàn)估計(jì)。答：均值μ的對(duì)數(shù)后驗(yàn)分布可以表示為Nlnp(μ| )lnp(xi|μ)lnp(μ)consti1Nln (xi|μ,)+ln (μ|0,μ)const,i1

(2-37)其中const表示與均值μ無關(guān)的項(xiàng)。對(duì)對(duì)數(shù)后驗(yàn)關(guān)于均值求導(dǎo)并設(shè)置為零，可以得到如下方程：(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μN(yùn)21 (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. 推導(dǎo)高斯分布的均值的貝葉斯參數(shù)估計(jì)。m答：假設(shè)均值服從高斯分布)p)p(|)p).p( )

(0,)，根據(jù)如下貝葉斯公式，

(2-39)可以得到均值的后驗(yàn)分布表達(dá)式為p(μ|

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

NμN(yù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(yùn)(1+N1)1μ

(1+N1)1μN(yùn)(1+N1)1μ

const2

m mm m= N

(N

)1

,(1N1)1.第3章邏輯回歸思考與計(jì)算1. 選擇一個(gè)UCI數(shù)據(jù)集，比較線性回歸和嶺回歸的錯(cuò)誤率。2. 請(qǐng)編程實(shí)現(xiàn)二類分類的邏輯回歸,要求采用牛頓法進(jìn)行優(yōu)化求解。3. 證明一元高斯似然關(guān)于方差的共軛先驗(yàn)是逆伽馬分布。設(shè)前提下，方差的后驗(yàn)分布是逆伽馬分布。假設(shè)似然函數(shù)為如下高斯分布：N 1 p(y|X,β,2)2)2 (y(y,

(3-1) 2 假設(shè)方差的先驗(yàn)分布為逆伽馬分布Inv-Gamma(a0,)，即p2)2)01(0,2

(3-2)根據(jù)貝葉斯公式可以得到方差的后驗(yàn)分布表達(dá)式如下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. 思考如何優(yōu)化使用范數(shù)進(jìn)行正則化的最小二乘。答：對(duì)于目標(biāo)函數(shù)不是連續(xù)可微的情況，可以用次梯度來進(jìn)行優(yōu)化，范數(shù)的次梯度表示為

1

d0 1=sign(β) 1

0

dd0但次梯度存在兩個(gè)問題：求解慢，通常不會(huì)產(chǎn)生稀疏解。此時(shí)可以用ProximalGradientDescent對(duì)范數(shù)正則化問題進(jìn)行求解。求解過程如下。使用范數(shù)進(jìn)行正則化的最小二乘的優(yōu)化目標(biāo)表達(dá)式如下：S

Nyf(x,)2|

i i N其中 y

f(x,)2

是可導(dǎo)函數(shù)，記為g(β)，且

不可導(dǎo)。 i i i1根據(jù)泰勒展開式g(β)可以表示為g(β)g(β

)(g(β

))(ββ

)1(ββ)

H(g(β

))(ββ

)o(||β

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

k k k k2假設(shè)g(β)滿足L-Lipschitz條件，即存在常數(shù)a0使得||g(β)令H(g(βk))aI，公式(3-5)可以使用如下表達(dá)式近似ag(β)g(βk)(g(βk))(ββk)2

(ββk)(ββk)2

(3-7)aββ2

1g(β )ak k)ak k

const其中const是與變量β無關(guān)的常數(shù)。公式(3-7)中的g(β)在β=βk最小值。

1g(βa k

)時(shí)取得如果使用梯度下降來求得g(β)的最小值，在第k1步，更新公式為βk+1

=βk

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

arga2

ββ

1g(β )a k)

2L||β||L1

kβ 2k公式中的優(yōu)化目標(biāo)中可以分別計(jì)算β的每一維β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章概率圖模型基礎(chǔ)思考與計(jì)算1. 設(shè)計(jì)一個(gè)貝葉斯網(wǎng)絡(luò)的圖模型，并寫出所有變量的聯(lián)合分布。4-1所示的一種生成式混合高斯過程圖模型，其中最左側(cè)的節(jié)點(diǎn)以及中間方框中的θk和Ik表示模型的超參數(shù)，其余中間與右側(cè)方框中的節(jié)點(diǎn)表示模型的隨機(jī)變量。圖4-1混合高斯過程的圖模型觀察圖4-1所示的貝葉斯網(wǎng)絡(luò)的圖模型，為了方便表示，使用表示12,...,z表示,z2,...,zN，使用X表示,x2,...,xN，使用y表示,y2,...,yN，可以得到如下聯(lián)合分布：,μ,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所示的貝葉斯網(wǎng)絡(luò)中的其他變量之間的條件獨(dú)立性。圖4-7使用d-分隔判斷條件獨(dú)立性示例答：下面分別分析圖a與其他所有變量的關(guān)系。在圖4-7（a）中，節(jié)點(diǎn)a到節(jié)點(diǎn)c,d,f,g,b均只有一條路徑。路徑中，a到cc,d是順序結(jié)構(gòu)且ca到da,c,f是匯總結(jié)構(gòu)且c的后代節(jié)點(diǎn)e被觀測(cè)，因此a到f不被阻隔；節(jié)點(diǎn)c,f,g是發(fā)散結(jié)構(gòu)且f未觀測(cè)，因此c到g不被阻隔；節(jié)點(diǎn)f,g,b是順序結(jié)構(gòu)且g是未觀測(cè)，因此f到b不被阻隔?？偟膩碚f，節(jié)點(diǎn)a到節(jié)點(diǎn)c,d,f,g,b均不是d-分隔的，因此在給定節(jié)點(diǎn)e后，節(jié)點(diǎn)a和節(jié)點(diǎn)c,d,f,g,b均不是條件獨(dú)立。在圖4-7（b）中，節(jié)點(diǎn)a到節(jié)點(diǎn)c,d,e,f,b均只有一條路徑。路徑中，a到cc,d是順序結(jié)構(gòu)且ca到dd,e是順序結(jié)構(gòu)且dc到ea,c,f是匯總結(jié)構(gòu)且c的后代節(jié)點(diǎn)不被觀測(cè)，因此a到f被阻隔；節(jié)點(diǎn)f,g,b是順序結(jié)構(gòu)且g被觀測(cè)，因此f到ba到b是ga和b條件獨(dú)立，即有af|g和ab|g。3. 寫出圖4-13所示的無向圖的聯(lián)合概率表示。圖4-13滿足條件獨(dú)立性AB|C的無向圖模型示例答：根據(jù)無向圖模型的條件獨(dú)立性，可以得到圖4-13中的所有變量的聯(lián)合分布表示為：p(x1,,,,,,,)p(x4,)p(x1,,,,,|,)p(x4,)p(x1,,|,)p(x6,,|,)

(4-2)若將概率分布根據(jù)最大團(tuán)進(jìn)行分解，則可以得到如下表示：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所示，若只需計(jì)算節(jié)點(diǎn),x2,,x4,中某一個(gè)變量的邊緣分傳遞既可以得出所有隨機(jī)變量的邊緣分布。這里將圖4-23中的x3作為根節(jié)點(diǎn)進(jìn)行兩次消息傳遞，兩次消息傳遞示意圖如圖4-24（a）和圖4-24（b）所示、x4和x5向根節(jié)點(diǎn)x3傳遞x3向葉子節(jié)點(diǎn)和x5傳遞圖4-24對(duì)應(yīng)圖4-23的和積算法的消息流示意圖從葉子節(jié)點(diǎn)向根節(jié)點(diǎn)的消息傳遞如下：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從根節(jié)點(diǎn)向葉子節(jié)點(diǎn)的消息傳遞如下：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章支持向量機(jī)思考與計(jì)算1. 查找資料理解并推導(dǎo)互補(bǔ)松弛條件。解相同的必要條件之一，所有的必要條件也稱為KKT條件。下面介紹拉格朗日對(duì)偶優(yōu)化的原理，以及KKT條件的推導(dǎo)過程。假設(shè)帶有約束的優(yōu)化問題表示為(7-1)定義原問題的最優(yōu)解為x*，目標(biāo)的最優(yōu)值為p*。拉格朗日對(duì)偶優(yōu)化的基本思想是將約束條件以一定的權(quán)重加入到原優(yōu)化目等價(jià)的解。首先，分別對(duì)約束條件引入拉格朗日乘子（也叫做對(duì)偶變量）ii拉格朗日函數(shù)L，具體表示如下：(7-2)其次，計(jì)算拉格朗日函數(shù)關(guān)于x的下界，得到拉格朗日對(duì)偶函數(shù)g(,)(7-3)進(jìn)一步分析(7-3)與原問題最優(yōu)值的關(guān)系。假設(shè)x表示滿足約束條件的任意變量，那么可以得到如下不等式：(7-4)因此拉格朗日函數(shù)滿足如下關(guān)系拉格朗日對(duì)偶函數(shù)滿足如下關(guān)系由于原問題的最優(yōu)解為x*也包含在x中，因此可以得到

(7-5)(7-6)(7-7)至此我們可以得到，對(duì)偶函數(shù)一定小于或等于原優(yōu)化問題的最優(yōu)值。因此，意義，它可能會(huì)達(dá)到原優(yōu)化問題的最優(yōu)值。定義對(duì)偶函數(shù)的解為*,*，最優(yōu)值為d*，可以得到d*p*下面分析滿足什么條件時(shí)，對(duì)偶函數(shù)的解與原問題的解等價(jià)。首先，根據(jù)原問題和對(duì)偶問題的定義，可以得到如下等式和不等式關(guān)系(7-8)偶函數(shù)的定義式(7-3)中的結(jié)果，第三行不等式利用了下界的含義，第四行利用l不等式約束條件。此，可以得到(7-9)由于每一個(gè)不等式約束都小于等于(7-10)該等式被稱為互補(bǔ)松弛條件，表示f(x*)*中至少有一個(gè)為0。此外，根據(jù)(7-8)i im0 0 ii

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

*f(x)

*h(x)的最小值，x*為其中的一個(gè)最下：2. 由支持向量機(jī)的原始優(yōu)化目標(biāo)推導(dǎo)得出拉格朗日對(duì)偶優(yōu)化，即給出書中公式（7.7）到公式（7.9）的推導(dǎo)過程。能會(huì)達(dá)到原優(yōu)化問題的最優(yōu)值，特別是當(dāng)滿足KKT條件時(shí)，它等于原優(yōu)化問題問題的解以及對(duì)偶問題的解滿足強(qiáng)最大-最小性質(zhì)，或者叫做鞍點(diǎn)性質(zhì)。下面描述強(qiáng)最大-最小性質(zhì)，并給出支持向量機(jī)的拉格朗日對(duì)偶優(yōu)化表示。L來描述原問題的最優(yōu)解p*示為滿足條件的原問題或者是無窮大，形式化表示如下：這意味著拉格朗日函數(shù)的上界的最小值為原問題的最優(yōu)值，即其次，根據(jù)前文中對(duì)偶問題的最優(yōu)解的定義，可以得到并且兩個(gè)問題的最優(yōu)解的滿足不等式關(guān)系如下：

d*p*d*p*，也被稱為強(qiáng)對(duì)偶性，具體表示為支持向量機(jī)的原優(yōu)化問題表示為，

(7-16)

w,b

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

(7-17)引入拉格朗日乘子向量,2,...,N]，我們便可以通過拉格朗日函數(shù)將約束條件融入到目標(biāo)函數(shù)中，得到優(yōu)化問題(7.7)對(duì)應(yīng)的拉格朗日函數(shù)為NL(w,b,)1||wN

(y(wx

b)

(7-18)22

i i i其中各乘子變量i(i2,...,N)均為非負(fù)值。根據(jù)公式(7-13)，原問題表示為,

0L(w,b,wb i根據(jù)公式(7-16)，對(duì)應(yīng)的拉格朗日對(duì)偶優(yōu)化問題表示為：

0,

L(w,b,i wb3. 支持向量機(jī)是否可以處理多類分類，如何實(shí)現(xiàn)？K習(xí)多個(gè)二類分類器，常用的方法有三種：（1）分別學(xué)習(xí)K個(gè)二類分類器，第k個(gè)分類器用于判別樣本是否屬于第k練第k個(gè)分類器時(shí)，使用屬于第k類的數(shù)據(jù)作為正樣本，不屬于第k類的所有數(shù)據(jù)作為負(fù)樣本。訓(xùn)練完成后，根據(jù)K個(gè)分類器的預(yù)測(cè)結(jié)果來判斷新的樣本應(yīng)該N屬于哪一個(gè)類別，假設(shè)第k個(gè)分類器的預(yù)測(cè)函數(shù)為fk(x)yiaixxi或者N i1fk()i(xi,)b那么最終的決策類別為h(x)gxfk()一對(duì)多k策略的優(yōu)點(diǎn)是最終的決策比較明確，相比于一對(duì)一策略所需訓(xùn)練的分類器較少；決策不準(zhǔn)確。（2）分別學(xué)習(xí)K(K個(gè)二類分類器，每個(gè)分類器用于判別該樣本是屬于i類和第j類，i2,...,K,j2,...,K,ijij分類ijij分類器將測(cè)試數(shù)據(jù)判別為ii類投票數(shù)加1而第j類投票數(shù)減點(diǎn)是訓(xùn)練數(shù)據(jù)平衡；缺點(diǎn)是需要訓(xùn)練較多分類器，且容易出現(xiàn)票數(shù)相等的情況。（3）設(shè)計(jì)新的優(yōu)化目標(biāo)，使用所有訓(xùn)練數(shù)據(jù)同時(shí)訓(xùn)練K個(gè)分類器，優(yōu)化目標(biāo)為最大化每一個(gè)類別到其他類別的間隔，帶有松弛變量的多類SVM優(yōu)化問題表示如下：K Nii

w,b,ξ

1||w

||2Ckk2kk

i1kyiwxb

(wx

b)2k,i

ki k ii(i2,,N),k2,...,K}\yi.該多類SVMN個(gè)訓(xùn)練樣本上解決一個(gè)復(fù)雜度O(K2N2)（較高）的優(yōu)化問題，因此訓(xùn)練速度較慢。4. 編程實(shí)現(xiàn)基于核方法的支持向量機(jī)，并在UCI數(shù)據(jù)集上測(cè)試性能。答：略第8章人工神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)思考與計(jì)算1. 思考如果將線性函數(shù)f(x)wx用作神經(jīng)網(wǎng)絡(luò)激活函數(shù)會(huì)有什么問題。答：激活函數(shù)的主要目的一是實(shí)現(xiàn)數(shù)據(jù)的非線性變換，解決線性模型表達(dá)、分類能力不足的缺陷；二是實(shí)現(xiàn)數(shù)據(jù)的歸一化，將當(dāng)前數(shù)據(jù)映射到某個(gè)范圍內(nèi)，f(x)wx用作神具有非線性表達(dá)的能力，只有在輸出層進(jìn)行回歸任務(wù)時(shí)可能使用線性激活函數(shù)。2. 感知機(jī)神經(jīng)網(wǎng)絡(luò)的優(yōu)缺點(diǎn)是什么？缺點(diǎn)是它要求數(shù)據(jù)線性可分，難以實(shí)現(xiàn)非線性分類問題，比如異或、同或運(yùn)算。3.如何保證神經(jīng)網(wǎng)絡(luò)具有較好的泛化能力？問題。提升測(cè)試性能的常用方法包括如下幾類：1、設(shè)計(jì)更合適的網(wǎng)絡(luò)結(jié)構(gòu)，如卷積神經(jīng)網(wǎng)絡(luò)和循環(huán)神經(jīng)網(wǎng)絡(luò)；2、使用與訓(xùn)練數(shù)據(jù)規(guī)模匹配的神經(jīng)網(wǎng)絡(luò)架構(gòu)，聲、調(diào)整數(shù)據(jù)分布。4. 編程實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的誤差反向傳播算法，嘗試動(dòng)態(tài)調(diào)整學(xué)習(xí)率以提升收斂速度，并在兩個(gè)公開數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。答：略5. 編程實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)，并在手寫字符識(shí)別數(shù)據(jù)集MNIST上進(jìn)行實(shí)驗(yàn)。答：略6. 編程實(shí)現(xiàn)循環(huán)神經(jīng)網(wǎng)絡(luò)，運(yùn)用不同的結(jié)構(gòu)（如LSTM和據(jù)集上進(jìn)行機(jī)器翻譯實(shí)驗(yàn)。答：略第9章高斯過程思考與計(jì)算1.思考高斯分布與高斯過程的區(qū)別。答：高斯分布用于刻畫觀測(cè)數(shù)據(jù)x的分布，考慮更一般的情況，當(dāng)x是多維x,x2,...,xD,x2,...,xN是服從D維高斯分布的獨(dú)對(duì)觀測(cè)數(shù)據(jù){x,中x與y之間映射的分布，其分布的參數(shù)是均值函數(shù)和協(xié)方差點(diǎn)可以估計(jì)高斯過程的超參數(shù)。假設(shè){x1,y1},{x2,y2},...,{xN,yN}均是服從高斯過,y2,...,yN的聯(lián)合N陣由輸入、均值函數(shù)與核函數(shù)確定。2. 參考圖9-1像。答：圖9-1展示了高斯過程 (0,k(x,

的三個(gè)樣本，其中k(x,x)exp{(xx)2

4}。ff()xx圖9-1高斯過程的三個(gè)樣本示例（三條不同的曲線對(duì)應(yīng)高斯過程的三個(gè)樣本）構(gòu)建過程如下：首先，在輸入空間上均勻采樣以獲得輸入{x1,x2,...,xN}。在該例子中輸入為[-5,5]上的實(shí)數(shù)，假設(shè)采樣100個(gè)數(shù)據(jù)輸入{x1,x2,...,xN}。其次，采樣獲得對(duì)應(yīng)的100個(gè)數(shù)據(jù)輸出{y1,y2,...,yN}。由于輸出服從多元高斯分布，其均值向量長度為100，協(xié)方差矩陣大小為100100。假設(shè)均值向量為零向量0k(x,x)exp{(xx)2K中的每一個(gè)元素。那么{y1,y2,...,yN}服從多元高斯分布(0,K)，從該分布中采樣一個(gè)樣本即可以得到一組{y1,y2,...,yN}，與輸入{x1,x2,...,xN}對(duì)應(yīng)則可以繪制出圖1中的一條曲線。3. 思考高斯過程與用于回歸的其他概率模型相比有哪些特殊性質(zhì)。答：1) 布，在輸出有噪聲的數(shù)據(jù)上性能魯棒。2) 高斯過程通過貝葉斯模型選擇的方法來對(duì)模型中的超參數(shù)進(jìn)行估計(jì)，這與支持向量機(jī)使用交叉驗(yàn)證選參數(shù)是不同的。高斯過程中的貝葉斯學(xué)習(xí)方法可以3)高斯過程預(yù)測(cè)結(jié)果具有概率意義，提供預(yù)測(cè)均值、方差和概率密度，其中均經(jīng)網(wǎng)絡(luò)回歸模型只輸出預(yù)測(cè)值是不同的。4) 高斯過程是一種核方法，不需要顯示地構(gòu)建非線性映射，實(shí)現(xiàn)非線性回歸。這與貝葉斯線性回歸模型不同，其核函數(shù)的思想與核SVM類似。5) 用訓(xùn)練數(shù)據(jù)。這與神經(jīng)網(wǎng)絡(luò)假設(shè)樣本之間相互獨(dú)立是不同的。6) 高斯過程的訓(xùn)練時(shí)間復(fù)雜度是O(N3)，預(yù)測(cè)時(shí)間復(fù)雜度是O(N2)非核方法模型的復(fù)雜度都要高，目前有許多研究能夠降低復(fù)雜度。4. 編程實(shí)現(xiàn)高斯過程回歸模型，并用回歸模型實(shí)現(xiàn)二類分類問題。答：略第10章聚類思考與計(jì)算1. 嘗試其他方法證明隨著聚類數(shù)目的增加，K-均值聚類的總誤差逐漸減小。答：略。可補(bǔ)充1KK-均值聚類算法可以看作一種EM算法，利用EM算法的收斂性可以證明K-均值聚類算法的收斂性。2. 分析K-均值聚類算法與基于EM算法的高斯混合模型聚類的關(guān)系。答：這里分析批處理的K-均值算法與高斯混合模型的關(guān)系。批處理的K-均值聚類算法可以看作高斯混合模型的一個(gè)特殊版本。高斯混合模型和K-均值聚設(shè)置。具體的關(guān)系分析如下。K-均值聚類算法屬于硬聚類，迭代過程中，樣本確定性地屬于某一個(gè)簇，計(jì)算依據(jù)如下：znargmin||xk

nk

||2.

式如下：N1 N

I(z

k)x,

kN n nkNkn1其中，Nk

N

I(zn

k).會(huì)計(jì)算，計(jì)算公式如下：p(z

)k

(xn|μk,k).n Kjj

(xn|μj,j)其中

1

Np(z

)。在得到每個(gè)樣本對(duì)所有簇的所屬概率后，利用所有Nk N

n樣本點(diǎn)計(jì)算每個(gè)簇的分布的均值和協(xié)方差。Np(znkNkn,Nkp(znk)

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

(10-5)k Np(znk)n1當(dāng)概率p(znk)取值非0即1時(shí)，即對(duì)p(znk)進(jìn)行如下近似處理p(znk)

kp(znk),k

(10-6)并且固定kK氏距離考慮數(shù)據(jù)的協(xié)方差，馬氏距離的平方的表示為d(x

)

)n k k n k這里之所以是近似關(guān)系，原因是公式(10-3)中包含的高斯密度函數(shù)不僅僅依賴于混合模型等價(jià)于K-均值聚類算法。3. 到公式(10.31)的推導(dǎo)過程。答：歸一化切割（normalizedcut）的表示是 k k1KW(A, \ k kargmin ,H 2k

vol()h h i,k

1 ifvA,i kvol(i k0 i其中vol()表示集合中所有邊的權(quán)重的和，即vol()=jAdjj。下面推導(dǎo)出最優(yōu)切割目標(biāo)(10-8)關(guān)于拉普拉斯矩陣的表示以及優(yōu)化問題的解。i由于公式(10-8)中優(yōu)化目標(biāo)的每一項(xiàng)可以寫為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.因此，優(yōu)化問題(10-8)可以表示為argminTr(HLH),Hh h i,k

1 ifvA,i kvol(i k0 如果將H約束為指示矩陣進(jìn)行優(yōu)化，那么可能的解有2NK種，難以遍歷求解。為了解決這個(gè)問題，可以對(duì)原優(yōu)化目標(biāo)進(jìn)行近似求解，找到滿足優(yōu)化目標(biāo)LH)的矩陣H，但不約束H為指示矩陣。根據(jù)(10-10)中義，可得到HI。不約束H為指示矩陣，但仍約束HI，歸一化切割的優(yōu)化問題(10-10)可以近似表示為Tr(FD12LD12F),FFF1 2K其中F2HK個(gè)拉格朗日乘子{,,...,1 2K量，可以得到與公式(10-11)等價(jià)的無約束優(yōu)化問題，表示如下：argminTr(FD12LD12F)+TrF.H

(10-11)}(10-12)對(duì)公式(10-12)中的優(yōu)化目標(biāo)關(guān)于F求導(dǎo)并設(shè)置為零，可以得到最優(yōu)解H滿足LNF=diag()F,N其中L2N2

，且對(duì)應(yīng)的目標(biāo)值為KFNF)k.k

因此F的解為為歸一化的拉普拉斯矩陣

22的前K個(gè)最小特征值對(duì)FHD12F得到矩陣H并對(duì)H按照行歸一化（此過程可以合并為一步，即直接對(duì)F按照行歸一化得到H數(shù)據(jù)表示H進(jìn)行一次聚類，比如使用K-均值聚類。4. 使用一種譜聚類算法實(shí)現(xiàn)對(duì)人工合成的環(huán)狀數(shù)據(jù)的聚類（如圖答：略5. 編程實(shí)現(xiàn)K-均值聚類算法和高斯混合模型聚類算法，并選擇3個(gè)不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析。答：略6. 選擇一種聚類算法實(shí)現(xiàn)圖像分割。答：略第11章主成分分析與相關(guān)的譜方法思考與計(jì)算1. 給出圖中的示例數(shù)據(jù)上PCA的求解過程。圖使用PCA將數(shù)據(jù)投影到一維空間的示例(圖中直線上的點(diǎn)是使用PCA將數(shù)據(jù){(1,3),(3,2),(3,5),(4,3)}投影到一維的結(jié)果。)首先，根據(jù)如下公式計(jì)算數(shù)據(jù)在原始空間的協(xié)方差矩陣S：N N NS1N

i1

(xi

1N

i1

xi)(xi

1N

i1

xi)

1.4286 1.4286= .1.4286

1.4286其次，對(duì)協(xié)方差矩陣進(jìn)行特征值分解，即Su1得到最大的特征值為2.8571，對(duì)應(yīng)的特征向量為.該向量為PCA意義下的最優(yōu)投影向量，對(duì)原始數(shù)據(jù)進(jìn)行投影可以得到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的解的區(qū)別。答：PCA的最優(yōu)投影U是協(xié)方差矩陣S的M個(gè)最大特征值2,...,M對(duì)應(yīng)的特征向量u1,u2,...,uM構(gòu)成的矩陣U，投影后的數(shù)據(jù)表示為 1N zU

xzU

xNxn 概率PCA的最優(yōu)潛變量z的后驗(yàn)概率分布為p(z|x)

(z|M

(xμ),2M1),其中MWW2I。模型參數(shù)的最大似然解為M mmW U2M mm2 1 Dm,

DMmM1Nμ x,

m n其中R表示，即zM

(xμ)。當(dāng)2

0時(shí)，可以得到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時(shí)概率PCA現(xiàn)此時(shí)概率PCA得到的投影方向與PCA的投影方向一致，但是概率PCA在各個(gè)主成分方向上的數(shù)值會(huì)比PCA放縮λ1/22

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

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

r(mcm)1。根據(jù)秩的乘法不等式性質(zhì)rmcmc)

1

根據(jù)秩的加法不等式性質(zhì)r(A+B)r(A)+，可以得到C rNc(mcm)(mcm)c1

CN C CN由于m1N

x1

Nm ，因此

N(m

m)

中的任意一項(xiàng)NiN

c c

c c cNc

可以表示為其他項(xiàng)的線性組合，繼而可以得到C rNc(mcm)(mcm)c1

C14. 思考求解CCA中公式(11.71)所示的廣義特征值問題的計(jì)算復(fù)雜度。w答：CCA中公式(11.71)所示的廣義特征值問題是求解wx式

，使其滿足如下等Cw

42Cw.x x該優(yōu)化問題等價(jià)于求解公式形如的廣義特征值問題。廣義特征值問題可以通過一些變換轉(zhuǎn)化為普通特征值問題。x的維度為Dx的維度為，樣本個(gè)數(shù)為N。BB1可以得到B1C,C

,C的復(fù)雜度分別為O(ND2)，O(NDD)，O(ND2)C求逆的復(fù)雜度O(D3)C1x xy y xx

x 的復(fù)雜度O(D3)，矩陣乘法C1CC1C

的復(fù)雜度D,DD2})，特征值y xxxyyyxy

x y xy分解的復(fù)雜度O(D3)，因此總復(fù)雜度為D3,，這里分開x

x x y y（2）如果B矩陣可進(jìn)行Cholesky分解，即BLL，其中L是下三角陣，通過引入新的向量L，可以得到等價(jià)的特征值問題A(L1)，其中(L1)。該方法的復(fù)雜度包括計(jì)算協(xié)方差矩陣C,C

,C的復(fù)雜度分別為O(ND2)，D)，O(ND2)C進(jìn)行Cholesky分解的復(fù)雜度O(D3)x xy

y x算

的復(fù)雜度

O(D3)

，矩陣乘法LCLCCC

的復(fù)雜度xD,DD2,，特征值分解的復(fù)雜度O(D3)，因此總復(fù)雜度為xx y xy x xx x y yD3,x x y y雜度。5. 試推導(dǎo)核PCA在{(x

沒有中心化情況下的投影表示。n

n

n1 nN答：{(xN

沒有中心化，表示變換后的數(shù)據(jù)均值不為零，即

(x

)0，令(x

)(x

)1

N(x

)表示數(shù)據(jù)從原始空間到高維空間的中心化后的非Mn n Nn1 nMMPCA尋找投影向量{vm的數(shù)據(jù)(X)[(x2),...,(xN經(jīng)投影后在子空間各個(gè)維度的表示M(X的方差總和最大。那么在高維空間上的協(xié)方差矩陣為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是一個(gè)標(biāo)量，vm(xn的線性組合，記為Nvm(xn,

將式(11-20)帶入式(11-19)中，可得N N N1 (x(x)

(x

) (x

(1