《人工智能導(dǎo)論：模型與算法》習(xí)題答案及期末試題

《人工智能導(dǎo)論：模型與算法》習(xí)題參考答案

第一章緒論

1.B

2.D

3.B

4.D

5.C

6.B

7.略

8.略

9.略

10.參考答案：

強(qiáng)化學(xué)習(xí)有環(huán)境、智能體、狀態(tài)、獎(jiǎng)勵(lì)、決策等諸多要素，涉及序列決策

過(guò)程，智能體之前作出的決策會(huì)影響智能體當(dāng)前的狀態(tài)，從而影響“未來(lái)”的決

策過(guò)程。而監(jiān)督學(xué)習(xí)中，對(duì)每一個(gè)樣本輸入做出的決策不會(huì)影響到“未來(lái)”的決

策。

監(jiān)督學(xué)習(xí)的每次決策后得到的反饋是“最終反饋”，它包含了最佳決策的信

息。而強(qiáng)化學(xué)習(xí)每次決策后得到的反饋只是當(dāng)前步的反饋。

11.略

第二章邏輯與推理

1.c

2.D

3.D

4.D

5.參考答案：

a)不是命題，因?yàn)闊o(wú)法判斷真假；

b)不是命題，因?yàn)椴皇顷愂鼍洌?/p>

c)是命題，其真值為真。

6.參考答案：

應(yīng)用歸結(jié)法：

(1)aV/?(已知);

(2)「0Vy(b進(jìn)行蘊(yùn)涵消除);

(3)aVy(由1和2);

(4)-i(aVy)(c使用DeMorgan定律)

(5)3和4矛盾，因此原命題集是不可滿足的。

7.參考答案：

>

a)-i(\fx')(<Basketball_player(<x)->HigherJ:han(x,l.Smy)a其中，

Bas/cetbaplayer(x)表示久是籃球運(yùn)動(dòng)員，Higher_than(x,1.8m)表示％的身高

超過(guò)1米80

b)(Vx)(/?ea/(x)More_than(Square(x'),0))o其中，Rea/(x)表示》是實(shí)數(shù)，

Square(x)表示為的平方，More_than(Square(x'),0)表示》的平方大于等于0。

8.參考答案：

(1)-.(Vx)(F(x)tG(x))

⑵。%)「(F(%)-G(尤))

(3)RxAJFCOvGQ))

(4)(3X)(F(X)A-,G(%))

(5)F(a)A-1G(a)(存在量詞消去)

(6)F(a)(由5知)

(7)—iG((z)(由5知)

(8)(Vx)(F(x)-?G(x)V//(%))

(9)E(a)-G(a)V”(a)(全稱量詞消去)

(10)G(a)VH(a)(6和9的假言推理)

(11)H(a)(由7和10知)

(12)F(a)AH(a)(由6和11知)

(13)a%)(F(%)A“(%))(存在量詞引入)

9.參考答案：

在給定目標(biāo)謂詞Mother。,y)之后，可如下表來(lái)構(gòu)造背景知識(shí)樣例和訓(xùn)練樣

例。

Mother(James,Mike)

Sibling(Ann,Mike)

目標(biāo)謂詞-\Mother(James,David)

背景知識(shí)Coup/e(James,David)

訓(xùn)練樣例-iMother(David,Ann)

樣例集合Father(David,Ann)

集合-iMot/ier(David,Mike)

Fat/ier(David,Mike)

-iMot/ier(Ann,Mike)

按照表2.3.1中FOIL算法所列步驟依次將每個(gè)候選前提約束謂詞加入到推

理規(guī)則中，并計(jì)算所得新的推理規(guī)則對(duì)應(yīng)的FOIL增益值?；谟?jì)算所得FOIL

增益值來(lái)確定最佳前提約束謂詞。下表給出了添加前提約束謂詞后信息增益的

計(jì)算結(jié)果。

推理規(guī)則涵」盒的正例和反FOIL信息增益

推理規(guī)則

伊數(shù)值

前提約束謂

目標(biāo)謂詞正例反例信息增益值

詞

Mother(x,y)

空集m=1=4/

<—+

Father(xfy}ntj.=0mL=2NA

Father(x,z)二0ml=2NA

Fatherfy,%)房二0ml=0NA

Father(y,z)m^.=0ml=1NA

Father{z,x)西二0ml=1NA

Father{z,y)ntj.=1ml=30.32

Sibling(x,y)自二0mL=1NA

Sibling(x,z)=0mL=1NA

Mother(x,y)Sibling(y,x)西二0ml=0NA

<—Sibling(y,z)m^.=0ml=1NA

Sibling(z,x)西=0ml=0NA

Sibling(z,y)二1mL=20.74

Couple(x,y)m^.=0mL=1NA

Couple(x,z)m+=1tn_=11.32

CoupleQy,%)m+二0ml=0NA

Couple(yfz)西=0ml=0NA

Couple(z,%)nfj.=0mL=2NA

Couple(z,y)自二0mL=1NA

由于Coap/e(x,z)的FOIL增益值最大，因此選擇Coap/e(%,z)加入推理規(guī)

則，得到Coup/e(%,z)-Mot/ier(x,y)這一新的推理規(guī)則，并將訓(xùn)練樣例集合中

與該推理規(guī)則不符樣例去掉。此時(shí)，背景知識(shí)樣例和訓(xùn)練樣本如下表：

Sibling(Ann,Mike)

目標(biāo)謂詞

背景知識(shí)Coup/e(James,David)Mother(James,Mike)

訓(xùn)練樣例

樣例集合Father(David,Ann)-\Mother(James,David)

集合

Fat/ier(David,Mike)

接著，再用相同方法繼續(xù)將其他謂詞逐一作為前提約束謂詞加入推理規(guī)則

進(jìn)行考察，用FOIL增益值來(lái)判斷選取最優(yōu)推理規(guī)則。

推理規(guī)則涵蓋的FOIL信息增

推理規(guī)則

正例和反例數(shù)益值

擬加入前提

現(xiàn)有規(guī)則正例反例信息增益值

約束謂詞

m+

Mother(x,y)<—Couple(x,z)m_=1/

=1

自

AFather{xy)ml=0NA

f=0

歷；

AFather{x,z)m_=0NA

=0

歷；

AFather(y,x)mL=0NA

=0

西

AFatherly,z)ml=0NA

=0

沅；

AFather(z,%)ml=0NA

=0

m+ml

AFather(z,y)1

=1=0

歷；

ASibling(x,y)ml=0NA

=0

Mother(x,y)歷；

ASibling(x,z)ml=0NA

<—Couple(x,z)=0

沅；

ASibling(y,%)ml=0NA

=0

歷；

ASibling(y,z)ml=0NA

=0

自

ASibling(z,%)ml=0NA

=0

吊+

ASibling(z,y)ml=0NA

=0

自

ACouple(x,y)m_=1NA

=0

自

ACouple^x,z)ml=10

=1

自

ACoupleQy,%)ml=0NA

=0

沅；

ACouple(yz)ml=0NA

f=0

西

ACouple{z,x)m_=0NA

=0

歷；

ACouple{z,y)ml=0NA

=0

當(dāng)Fatherdy)作為前提約束謂詞加入到推理規(guī)則后FO/L_Ga沅值最大，因

此將Father(z,y)加入，得到新的推理規(guī)則Father(z,y)ACouple(xfz)t

Mother(x,y)o當(dāng)％=James、y二Mike和2=口@丫1(1時(shí)，該推理規(guī)則覆蓋訓(xùn)練樣本

集合的正例Mot/ier(James,Mike)>且不覆蓋任意反例，因此算法學(xué)習(xí)結(jié)束。

當(dāng)學(xué)習(xí)得到(V%)(Vy)(Vz)(尸ather(z,y)ACouple(x,z)-Mother(%,y))這

一推理規(guī)則后，由題意可知Father(David,Ann)和Coap加(James,David),因此可

推理得到新的知識(shí)Mother(James,Ann),即James和Ann的關(guān)系為Mother關(guān)

系O

10.參考答案：

(1)目標(biāo)關(guān)系：Mother

(2)對(duì)于目標(biāo)關(guān)系Mother,生成四組訓(xùn)練樣例，一個(gè)為正例、三個(gè)為負(fù)例：

正例：(James,Mike)

負(fù)例：(James,David),(David,Ann),(David,Mike)

(3)從知識(shí)圖譜采樣得到路徑，每一路徑鏈接上述每個(gè)訓(xùn)練樣例中兩個(gè)實(shí)體：

(James,Mike)對(duì)應(yīng)路徑：Couple—Father

(James,David)對(duì)應(yīng)路徑：Mother->Father1(Father-'與尸ather為相反關(guān)

系)

(David,Ann)對(duì)應(yīng)路徑：FathertSibling

(David,Mike)對(duì)應(yīng)路徑：CoupletMother

(4)對(duì)于每一個(gè)正例/負(fù)例，判斷上述四條路徑可否鏈接其包含的兩個(gè)實(shí)體，將

可鏈接(記為1)和不可鏈接(記為0)作為特征，于是每一個(gè)正例/負(fù)例得到

一個(gè)四維特征向量：

(James,Mike):{[1,0,0,0],1}

(James,David):{[0,1,0,0],—1)

(David,Ann):{[0,0,1,0],—1}

(David,Mike):{[0,0,1,1],-1}

(5)依據(jù)(4)中的訓(xùn)練樣本，訓(xùn)練分類器M。

(6)預(yù)測(cè)。對(duì)于樣例(James,Ann),得到其特征值為[1,0,0,0],將特征向量輸入

到分類器M中，分類器M給出分類結(jié)果為1,Mot%r(David,Ann)成立。

11.參考答案:

下面我們用本章節(jié)式2.4.4(調(diào)整公式)來(lái)求解是否存在“女性歧視”問(wèn)題。

用X=1表示男性，X=0表示女性；丫=1表示錄??；Z=0,1,2,3分別表示英

語(yǔ)、俄語(yǔ)、西班牙語(yǔ)和意大利語(yǔ)，則有：

p(y=i\do(x=i))

=P(Y=1\X=1,Z=0)P(Z=0)+P(Y=l\x=1,Z=1)P(Z=1)

+P(Y=1\X=1,Z=2)P(Z=2)+P(Y=1\X=1,Z=3)P(Z=3)

帶入表1中數(shù)據(jù)，可得男性被錄取的因果效應(yīng)為：

P(Y=l|do(X=1))

(825+108)(560+25)

=0.62X———r4-0.63X

(2175+849)(2175+849)

(417+375)

+0.33!X白---------白+0.06

(2175+849)

(373+341)

X之--——=0.41376

(21754-849)

類似地，可以求得女性被錄取的因果效應(yīng)為：

p(y=i\do(x=o))

(825+108)(560+25)

=0.82x^――—―<-+0.68X

(2175+849)(2175+849)

(417+375)(373+341)

+0.35x------------+0.07x-----------

(2175+849)(2175+849)

=0.49274

最后，我們發(fā)現(xiàn)女性錄取率(0.49274)比男性錄取率(0.41376)要高，即

不存在所謂的“女性歧視”。

12.參考答案：

使用乘積分解規(guī)則：

P(X1,X2,X3,X4,X5,X6,Xi,Xj)

=P(X1)XP(X2|X4,X5)xP(X3|Xi)xP(X4|X1,X3,X5)xP(X5)

xP(X6|X3)xP(X7\X4,X6,X8)xP(X8|X5)

外生變量：Xi,x5；內(nèi)生變量：x2,x3,x4,x6,x7,x8

13*.參考答案：

為了阻塞節(jié)點(diǎn)X6和節(jié)點(diǎn)Xg,我們需要讓從節(jié)點(diǎn)X6到節(jié)點(diǎn)Xg的所有路徑滿足

D-分離性質(zhì)。從節(jié)點(diǎn)X6到節(jié)點(diǎn)X8共有以下7條路徑：

PlX6^X7<-X8(基于定義2.18(2),節(jié)點(diǎn)*7不能在限定集Z中)

P2X6<rX3^X4^X7^X8(基于定義2.18,節(jié)點(diǎn)X3或或X7需要出現(xiàn)在限定

集Z中)

P3X6（X39X46X5fX8（基于定義2.18,節(jié)點(diǎn)X3或Xs出現(xiàn)在Z中，或者節(jié)點(diǎn)

X4不出現(xiàn)在Z中）

P4X6（X39X4fX26X59X8（基于定義2.18,節(jié)點(diǎn)X3或X4或Xs出現(xiàn)在Z中，

或者節(jié)點(diǎn)X2不出現(xiàn)在Z中）

P5X6<-X3<rXx^>X4-^X7-^X8（基于定義2.18,節(jié)點(diǎn)X3或X1或或X7出現(xiàn)在Z

中即可）

P6X6<-X3-^X44-X5-^X8（基于定義2.18,節(jié)點(diǎn)X3或Xi或X5出現(xiàn)在Z中，

或者節(jié)點(diǎn)X4不出現(xiàn)在Z中）

P7X6<-X3^^4-^X2<-Xs-^x8（基于定義2.18,節(jié)點(diǎn)X3或X1或X4或Xs出現(xiàn)

在Z中，或者節(jié)點(diǎn)X2不出現(xiàn)在Z中）

P8:X6^X7<rX4<rX5^X8

P9:X69X76X4^X26X59X8

綜上，能讓從節(jié)點(diǎn)X6到節(jié)點(diǎn)X8的所有路徑滿足D-分離性質(zhì)的限定集為：

所有包含節(jié)點(diǎn)X3或{X4,X5}且不包含節(jié)點(diǎn)X7的限定集，例如{X3},{X3,X4}

等。

第三章搜索與求解

1.B

A如果圖不連通，則可能不存在路徑。如果圖中存在負(fù)值回路（當(dāng)然還有其他

情況），則可能不存在最短路徑。

B顯然不是最優(yōu)的。

C在這種情況下，節(jié)點(diǎn)所在層數(shù)和其路徑長(zhǎng)度是成正比的，因此優(yōu)先擴(kuò)展淺層

節(jié)點(diǎn)等價(jià)于優(yōu)先擴(kuò)展路徑代價(jià)小的節(jié)點(diǎn)，這在圖搜索中是最優(yōu)的（可參見

Dijkstra算法）。

D因?yàn)閳D搜索是在樹搜索的基礎(chǔ)上進(jìn)一步剪枝，因此擴(kuò)展的節(jié)點(diǎn)數(shù)量通常更

少。

2.D

A只有可容的啟發(fā)函數(shù)才不會(huì)過(guò)高估計(jì)從當(dāng)前節(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)之間的實(shí)際代

價(jià)。

B如果存在負(fù)值邊，則很容易構(gòu)造反例。

C啟發(fā)函數(shù)通常是對(duì)當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離的估計(jì)，評(píng)價(jià)函數(shù)不一定有實(shí)際

意義。

D根據(jù)對(duì)A*算法的分析，不難證明。

3.A

A只需要重新定義黑方的動(dòng)作為每次落兩子即可。

B導(dǎo)致問(wèn)題中信息不完全，因此Minimax算法無(wú)法求解。

C導(dǎo)致問(wèn)題不再是兩人對(duì)抗問(wèn)題，每個(gè)人的目標(biāo)不能再簡(jiǎn)單地用最大化/最小化

某一個(gè)人的分?jǐn)?shù)來(lái)衡量。

D使該問(wèn)題不是零和博弈。白方最大化自己的分?jǐn)?shù)不一定必須最小化黑方的分

數(shù)。

4.D

A、B、C顯然正確。

D中置信上界的含義是樣本取值以極大的概率不會(huì)超過(guò)置信上界，并不是說(shuō)不

可能超過(guò)。

5.B

A選擇過(guò)程中UCB1算法即體現(xiàn)了探索與利用的平衡。

B只栗有一個(gè)子節(jié)點(diǎn)未被擴(kuò)展，算法就會(huì)進(jìn)入擴(kuò)展步驟。

C模擬步驟的策略不一定要和選擇步驟相同，模擬步驟通常會(huì)采取更簡(jiǎn)單的策

略。

D對(duì)。更新當(dāng)前路徑上的節(jié)點(diǎn)，且不在搜索樹中的當(dāng)然不用更新。

6.參考答案：

下圖中粗線表示路徑，節(jié)點(diǎn)旁的數(shù)字表示擴(kuò)展順序。

（1）

A)1

⑵

7.參考答案：

下圖中紅線表示路徑，節(jié)點(diǎn)旁的數(shù)字表示擴(kuò)展順序。

(1)

8.參考答案：

(1)不矛盾。貪婪最佳優(yōu)先搜索并不具有最優(yōu)性，本題中的例子只是它能找到

最優(yōu)解的一個(gè)特例。"A*搜索是在已知信息下同類搜索策略中最優(yōu)的“，其

含義是：額外信息僅包括當(dāng)前的啟發(fā)函數(shù)時(shí)，所有能夠保證最優(yōu)性(即在

任意有最短路徑的問(wèn)題中都能找到最短路徑)的算法中，A*算法擴(kuò)展的節(jié)

點(diǎn)數(shù)量是最少的。

(2)啟發(fā)函數(shù)在滿足可容性或一致性的基礎(chǔ)上，其值越接近當(dāng)前節(jié)點(diǎn)到終止節(jié)

點(diǎn)的最小代價(jià)，搜索的效率越高。當(dāng)啟發(fā)函數(shù)值等于當(dāng)前節(jié)點(diǎn)到終止節(jié)點(diǎn)

的最小代價(jià)時(shí)，算法每一步都會(huì)朝著最優(yōu)的方向探索，以0(m)的復(fù)雜度

得到最優(yōu)解。

9.參考答案：

擴(kuò)展情況如下。顯然擴(kuò)展順序會(huì)影響最終擴(kuò)展的節(jié)點(diǎn)數(shù)量(算法時(shí)間效

率)。

(1)擴(kuò)展節(jié)點(diǎn)數(shù)量為20。

10.參考答案:

(1)第一步三個(gè)節(jié)點(diǎn)的UCB值從左到右分別為2+—=2.97,—+—

1V14V4

6.24,5+J等=4.89,因此第一步選擇第二層中間的節(jié)點(diǎn)。第二步三個(gè)

7

節(jié)點(diǎn)的UCB值從左到右分別為恒亙=7.67,-+回亙-+

1

1yl1yl3..67,

誓=8,67,因此第二步選擇獎(jiǎng)勵(lì)為7的節(jié)點(diǎn)。如下圖所示。

獎(jiǎng)勵(lì)

(2)由于此時(shí)已經(jīng)到達(dá)葉子節(jié)點(diǎn)，因此不需要進(jìn)行擴(kuò)展和模擬過(guò)程，反向傳播

后結(jié)果如下圖所示

獎(jiǎng)勵(lì)

(3)算法在很長(zhǎng)一段時(shí)間內(nèi)都會(huì)選擇獎(jiǎng)勵(lì)為7的節(jié)點(diǎn)，而不會(huì)探索獎(jiǎng)勵(lì)為9的

節(jié)點(diǎn)。當(dāng)實(shí)驗(yàn)次數(shù)足夠多時(shí)，第二層左側(cè)的節(jié)點(diǎn)的UCB值最終會(huì)超過(guò)第

二層中間節(jié)點(diǎn)的UCB值，因此只要實(shí)驗(yàn)次數(shù)足夠多，算法是有可能探索

到獎(jiǎng)勵(lì)為9的節(jié)點(diǎn)的。如果希望提高算法的效率，可考慮加大探索的力度,

即取一個(gè)更大的超參數(shù)C。不難驗(yàn)證，在原題中的狀態(tài)下，取C=10即可

令算法選擇第二層左側(cè)的節(jié)點(diǎn)。

11.參考答案：

假設(shè)S]T…TSj的代價(jià)為G,Sj->…TSk的代價(jià)為,由于S1->S2T…T

Sk是一條最短路徑，因此從S1到Sk的最小代價(jià)C*=Q+C2o已知路徑P是從Si到

國(guó)的最短路徑，因此P的代價(jià)CjWG，所以C*=Cl++。2，即路徑PT

Sj+1->???->Sk的代價(jià)小于等于從Si到外最短路徑的代價(jià)，因此P->si+1—

Sk必然也為一條最短路徑。

12.參考答案：

(1)因?yàn)橛涗浽摲謹(jǐn)?shù)是為了讓當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)選擇一個(gè)置信上界最大的孩

子節(jié)點(diǎn)，由于要最大化父節(jié)點(diǎn)玩家的收益相當(dāng)于最小化當(dāng)前玩家的收益，

因此此處需要減去當(dāng)前玩家的而收益。如果要修改為加上終局得分，該得

分應(yīng)該從當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)或子節(jié)點(diǎn)玩家的角度來(lái)計(jì)算。

(2)關(guān)鍵在于修改BackPropagate函數(shù)的第三行，由于不存在兩個(gè)玩家對(duì)抗，

此處只要加上終局獎(jiǎng)勵(lì)得分(或代價(jià)的相反數(shù))即可。

13*.參考答案：

當(dāng)搜索樹的高度(最長(zhǎng)路徑長(zhǎng)度)為小且是一棵滿b叉樹時(shí)，假設(shè)alpha-beta

剪枝擴(kuò)展的最少節(jié)點(diǎn)數(shù)量為f(m)。如本章正文中圖3.3.11所示，觀察其第二層

的節(jié)點(diǎn)，不難發(fā)現(xiàn)：因?yàn)榈诙幼钭髠?cè)節(jié)點(diǎn)繼承了根節(jié)點(diǎn)(-8,+8)的范圍，因

此對(duì)該節(jié)點(diǎn)所在的子樹進(jìn)行搜索等價(jià)于樹的高度為6-1的原問(wèn)題，因此擴(kuò)展節(jié)

點(diǎn)數(shù)量最少為考慮第二層的其余b-l個(gè)節(jié)點(diǎn)所在的子樹，最優(yōu)情況

下這些高度為m-1的子樹的每個(gè)第一層節(jié)點(diǎn)擴(kuò)展1個(gè)子節(jié)點(diǎn)，每個(gè)第二層節(jié)點(diǎn)

擴(kuò)展b個(gè)子節(jié)點(diǎn)，每個(gè)第三層節(jié)點(diǎn)擴(kuò)展1個(gè)子節(jié)點(diǎn)，每個(gè)第四層節(jié)點(diǎn)擴(kuò)展b個(gè)子

節(jié)點(diǎn)，如此循環(huán)。因此每棵子樹擴(kuò)展節(jié)點(diǎn)數(shù)為

im-2|i?n-l|

l+l+b+b+…+從2I+21

d)

用+】

<2b

2

=4b1叫

由此可得遞推關(guān)系

1)+4(b-l)bl21+1

/(m)<f(jn-

2)+4(/?-l)b121+1

f(jn-1)<f(m-

不等式左右兩邊同時(shí)求和，可得

-1)(調(diào)+調(diào)+…+4*)

/(m)</(0)+m+4(b

)(1+6+…+b用)

<1+m+8(b—1

bl*+i_1

=1+m+8(b—1)b-1

im+l|

=8-2J+m—7

|7n+l|

=0(b'21+m)

在b和m足夠大時(shí)，顯然4笑斗>TH,因此算法在最優(yōu)情況下的時(shí)間復(fù)雜度為

|tn+l|

O(bE)。

14*.參考答案：

(1)令啟發(fā)函數(shù)九何)=0,則圖搜索的A*算法退化為Dijkstra算法。對(duì)于任意一

個(gè)節(jié)點(diǎn)凡假設(shè)通過(guò)動(dòng)作a能得到后繼節(jié)點(diǎn)以，當(dāng)圖中沒(méi)有負(fù)值邊，即單步代價(jià)

c(n,a,nz)20時(shí)，有九(n‘)+c(n,a,n')=c(n,a,n')>0=h(n),可知恒為0的啟

發(fā)函數(shù)滿足一致性。因此此時(shí)的圖搜索A*算法——Dijkstra算法——是最優(yōu)的。

(2)跟據(jù)原狀態(tài)轉(zhuǎn)移圖G,構(gòu)造一個(gè)新的狀態(tài)轉(zhuǎn)移圖G',其中狀態(tài)和狀態(tài)轉(zhuǎn)移關(guān)

系不變，只對(duì)狀態(tài)轉(zhuǎn)移代價(jià)進(jìn)行調(diào)整。新的單步代價(jià)定義為c'(n,a,n')：=

c(n,a,n')+h(nr)-h(n),若啟發(fā)函數(shù)滿足一致性，則顯然c'5,a,7i')>0。根據(jù)

(1)中結(jié)論，可知在Dijkstra算法在G'能夠找到最優(yōu)解。

首先證明，給定起始和終止?fàn)顟B(tài)Si和Sk，則在圖G'中找到的任意一條最短路

徑，必然也是G中的最短路徑?？紤]G'中的最短路徑叫,電，…，(按照本章中

的定義，嚴(yán)格來(lái)說(shuō)這不是一條路徑，但通過(guò)這些節(jié)點(diǎn)的狀態(tài)能找到一條路徑。

以下為了方便說(shuō)明，將節(jié)點(diǎn)序列也稱為路徑。)，其代價(jià)為

以電卬電)+c'(n2，a2,n3)+-+c'(_nk_1,ak_1,nk')

=[c(n1,a1,n2)+h(n2)--%)]+…

+[cg-i,aL)+h(nk)-八(心_。]

=c(%,%,電)+c(n2,a2^3)+…+。(心-1，%-1，幾卜)+h(n。-"陽(yáng))

當(dāng)初始狀態(tài)和終止?fàn)顟B(tài)給定時(shí)，/1(以)一/1(九1)與路徑本身無(wú)關(guān)，因此可以

認(rèn)為路徑在G'中的代價(jià)是它在G中代價(jià)加上一個(gè)與路徑無(wú)關(guān)的常數(shù)，因此G'中

的最短路徑必然也是G中的最短路徑。

接著證明，給定起始和終止?fàn)顟B(tài)Si和Sk,對(duì)于任意一個(gè)在G上搜索的A*算

法流程，必然存在一個(gè)在G'上的Dijkstra算法流程與其擁有相同的節(jié)點(diǎn)擴(kuò)展順

序(稱在不同算法中對(duì)應(yīng)路徑相同的節(jié)點(diǎn)為同一個(gè)節(jié)點(diǎn))，因此這兩個(gè)算法會(huì)

找到同一條從Si到Sk的路徑。不妨稱G上的A*算法為算法41,G'上的Dijkstra

算法為算法42。對(duì)于/I搜索樹中的任意節(jié)點(diǎn)小可找到A2搜索樹中對(duì)應(yīng)相同路

徑的節(jié)點(diǎn)n',根據(jù)上一段中的論證過(guò)程，可知g(n')=g(/i)+八(九)—h(7ii),其

中?11為根節(jié)點(diǎn)。那么算法41(A*算法)中評(píng)價(jià)函數(shù)為f(九)=g(九)+42

算法(Dijkstra算法)中評(píng)價(jià)函數(shù)f(以)=g("),因此可得等式f(n)=f(川)+

h(n^a即，當(dāng)根節(jié)點(diǎn)確定時(shí)，算法41和算法A2中對(duì)應(yīng)同一路徑的節(jié)點(diǎn)其評(píng)價(jià)

函數(shù)值只相差一個(gè)常數(shù)。根據(jù)這個(gè)性質(zhì)，不難用數(shù)學(xué)歸納法證明，對(duì)于任意一

個(gè)算法A1可能導(dǎo)致的節(jié)點(diǎn)擴(kuò)展順序(此處強(qiáng)調(diào)任意是因?yàn)樵u(píng)價(jià)函數(shù)相同的節(jié)點(diǎn)

擴(kuò)展順序可能不確定)，都存在一個(gè)42算法的擴(kuò)展順序與之相同。由于篇幅限

制，此處省略具體的數(shù)學(xué)歸納法證明。

綜上所述，給定起始和終止?fàn)顟B(tài)si和Sk，若A*算法找到了一條路徑P,則

該路徑必然也能在圖G'上被Dijkstra算法找到。根據(jù)問(wèn)題(1)中的結(jié)論，路徑P是

圖G'上從Si到%的最短路徑。又根據(jù)上述證明，路徑P也是圖G上從狀態(tài)Si和外

的最短路徑，至此A*算法的最優(yōu)性得證。

第四章監(jiān)督學(xué)習(xí)

1.A

2.B

3.F

4.C

5.A

6.A

7.參考答案（A圖是正確的）：

1.對(duì)于每個(gè)數(shù)據(jù)集，隨著模型復(fù)雜度增大，模型在訓(xùn)練集上的錯(cuò)誤率會(huì)不

斷下降，而在測(cè)試集上的錯(cuò)誤率會(huì)先下降后上升。

2.隨著模型復(fù)雜度增大，在更大的數(shù)據(jù)集A上模型更難擬合，因此也就不

容易過(guò)擬合，但具有更好的泛化性。所以合理的猜測(cè)是，曲線（A,

Train）會(huì)在（B,Train）的上方，曲線（A,Test）會(huì)在（B,Test）的下

方，而曲線（A,Test）達(dá)到過(guò)擬合的轉(zhuǎn)折點(diǎn)會(huì)比而曲線（B,Test）更靠

后一些。

8.略

10.參考答案：

（1）該標(biāo)準(zhǔn)化項(xiàng)與參數(shù)w無(wú)關(guān)，該項(xiàng)對(duì)w的導(dǎo)數(shù)永遠(yuǎn)為0,對(duì)w的優(yōu)化求解沒(méi)有

作用。

（2）L2標(biāo)準(zhǔn)化項(xiàng)通過(guò)懲罰過(guò)大的參數(shù)w來(lái)避免過(guò)擬合，之小于0意味著該損失

函數(shù)傾向于更大的w,從而激勵(lì)過(guò)擬合，失去了標(biāo)準(zhǔn)化的作用。

11.參考答案：

（1）心情指數(shù)大于1出去玩，等于1不出去玩。

（2）

迭代前：

1/101/101/101/101/101/101/101/101/101/10

迭代后：

1/161/164/161/161/161/161/161/161/164/16

（3）有同伴就出去玩，沒(méi)同伴不出去玩

1

-In3

2

（4）三次迭代的分類器分別為：

Q:心情指數(shù)大于1出去玩，等于1不出去玩

C2:有同伴出去玩，沒(méi)同伴不出去玩

C3:天氣好出去玩，天氣不好不出去玩

強(qiáng)分類器可表示為:

111

sig九份In(4)G+-In(3)C2+-ln

12*.參考答案：

P-ly=l)P(y=1)

0gp(%|y=0)P(y=0)

p(y=1)11

oclog-----—+-(x-〃i)TzT(x-41)-5-〃0)上-1(%-Mo)

p(y=U)，L

P(%|y=l)P(y=1)

°gp(%|y=0)P(y=0)

p(y=1)11

0clog-7(〃I)T￡T(%)+5OOAETQO)

p.riy”—_umj乙L

+婷工-1(〃1一〃o)

=b+wTx

T1

其中b=log-101)Z-(Mi)+2(〃0尸工-1(〃0)是一個(gè)常量，w=

￡一1(生-的)是一個(gè)線性參數(shù)向量。證畢。

第五章無(wú)監(jiān)督學(xué)習(xí)

1.D

2.C

3.D

4.D

5.C

6.略

7.參考答案：

在每一次聚類過(guò)程中，每個(gè)數(shù)據(jù)點(diǎn)都被分配到與其距離最近聚類中心所在集

合，即argmin|E—q|『，因此在聚類步驟中￡3巳的一.|產(chǎn)中的每一項(xiàng)都

Cjec

保持不變或減小，僅當(dāng)算法收斂時(shí)才會(huì)每一項(xiàng)都保持不變。因此，只要算法沒(méi)有

收斂，在每一次聚類后目標(biāo)函數(shù)都會(huì)減小。

設(shè)一組數(shù)據(jù)點(diǎn)的聚類中心為Z,則對(duì)于該組數(shù)據(jù)｛%?,￡￡1(%—z)2=

?3((x—元)2+2(%—x)(x—z)+(%—z)2)=￡皂(%—x)2+2(x—

Z)2￡1(久一元)+?3(%-Z)2=2X1(%-X)2+?3(%-Z)2,當(dāng)Z=土?xí)r取最小

值。因此在更新聚類中心的步驟中，對(duì)每組數(shù)據(jù)取均值為新的中心將最小化每

一個(gè)2獲611%-01|2。同樣，只要算法沒(méi)有收斂，在每一次更新聚類中心后目

標(biāo)函數(shù)都會(huì)減小。

綜上，在算法收斂前目標(biāo)函數(shù)都將嚴(yán)格遞減。因此，k-means算法不可能兩

次訪問(wèn)完全相同的聚類情況。而將有限數(shù)量的數(shù)據(jù)點(diǎn)分為k類的總可能是有限

的，能保證不循環(huán)的k-means算法一定能夠收斂。

8.參考答案：

初始化兩枚硬幣的概率為0.30和0.70

迭代硬幣A硬幣A硬幣B硬幣B硬幣A投硬幣B投

次數(shù)為正面次為反面次為正面為反面擲正面概率擲正面概率

數(shù)數(shù)次數(shù)次數(shù)0A%

16.8218.1917.187.810.270.69

21.8921.1222.114.870.080.82

31.5215.1622.4810.830.090.67

41.0910.3622.9115.640.090.59

51.019.7922.9916.210.090.59

9.參考答案：

k-means算法可以被看做EM算法的一種特殊實(shí)現(xiàn)，其隱變量即為各聚類中

心。在E步驟中，通過(guò)歐氏距離來(lái)估計(jì)各數(shù)據(jù)點(diǎn)最有可能歸屬于哪個(gè)聚類中心；

在M步驟中，通過(guò)計(jì)算均值更新聚類中心位置來(lái)最大化這些數(shù)據(jù)點(diǎn)屬于該聚類

中心的可能性。

10.參考答案：

a）樣本均值是對(duì)總體均值無(wú)偏估計(jì)的證明過(guò)程

證明：

r1石+冷+--HX

E[x]=E———-------------n

''Ln

1

=-￡"[^1+%2+---1"

1

=一(￡1[%/+E[X]+…+E[x])

n2n

1

二一(〃+4H-----Ffl)

n

n/j.

n

=〃

可見，樣本均值是對(duì)總體均值的無(wú)偏估計(jì)。

b)E臣仁心-/丹=/小

證明：

n1rn

E[W(土一修)2=E12((無(wú)一“)一3一"))2

-i=l--i=l-

-n[

=E-Y((x-M)2-2(x-〃)(/-〃)+(%i-4)2)

i=l」

-nn

=E------------2/左一〃)+^2(項(xiàng)-〃)2

.i=li=l

二E（元一〃）2一2（無(wú)一4）2+1、（勺一〃）2

71乙」

i=l

-n

=E-V（%i-M）2-F[（x-/z）2]

nZ-j

i=l

n—19

=--------G乙

n

在上面的證明過(guò)程中，利用了如下的結(jié)果：

由于E(X2)=[E(X)]2+Var(X)、Var(a+X)=Par(X)、Var^aX)=

c^Var{X}

因此

E[(x—ft)2]=[E(x—ft)]2+Var(x—/z)=Var(x)

(X、+x+—Fx\na2a2

=Var----2--------n--=一—二—

\n/nzn

從E[；2X13—陽(yáng))2]=、1/可知，；2仁1(三一項(xiàng))2是對(duì)總體方差的一個(gè)低

估，因此在用樣本方差來(lái)代替總體方差時(shí)，需要將樣本方差定義為

±2憶1(/一4)2,這才能從樣本方差出發(fā)，得到總體方差。2,這是一個(gè)無(wú)

偏估計(jì)。

答案:

nn

n12（元-陽(yáng)）2nX71-1^2=o-2

K=E

n—1n—1n

i=li=l

第六章深度學(xué)習(xí)

1.D

2.i和iii

3.D

4.D

5.C

6.C

7.A

8.參考答案：

數(shù)據(jù)：深度學(xué)習(xí)適合處理大數(shù)據(jù)，機(jī)器學(xué)習(xí)算法更適用于小數(shù)據(jù)；

硬件：深度學(xué)習(xí)由于巨大的計(jì)算量，需要大量計(jì)算資源，比如GPU,機(jī)器

學(xué)習(xí)算法對(duì)計(jì)算資源的需求相對(duì)較低；

特征構(gòu)建：深度學(xué)習(xí)試圖從數(shù)據(jù)中學(xué)習(xí)特征，機(jī)器學(xué)習(xí)中許多特征都需要由

行業(yè)專家確定，并手工構(gòu)造；

解決問(wèn)題方式：深度學(xué)習(xí)通常利用“端到端'’的方式構(gòu)建模型，機(jī)器學(xué)習(xí)通常

將問(wèn)題分為幾個(gè)步驟，每個(gè)步驟逐一解決，然后將結(jié)果組合。

9.參考答案：

(1)根據(jù)圖62可知，在異或操作中，點(diǎn)(0,0)與(1,1)為0,點(diǎn)(0,1)

和(1,0)為1,由于感知機(jī)是線性分類器，無(wú)法構(gòu)建超平面可以將這兩類分

開。

(2)輸入層維度為2,用于接收兩個(gè)操作數(shù)；至少有一層隱藏層，且隱藏

層中的神經(jīng)元需要包含非線性激活函數(shù)；輸出層維度為1,用于輸出結(jié)果。

10.參考答案:

不能初始化為0,也不能被同時(shí)初始化為其他相同的值。

如果參數(shù)被初始化為相同的值后，在誤差反向傳播過(guò)程中，同一層的神經(jīng)元

所接收到的誤差都相同，更新后這些參數(shù)的值仍然相同。不管經(jīng)過(guò)多少輪迭

代，同一層神經(jīng)元的參數(shù)保持相同，因此不同的神經(jīng)元無(wú)法學(xué)習(xí)到不同特征

的重要程度，失去了深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)特征的能力。

11.參考答案：

(1)L=，售1-%*logy-

(2)in+i=-%+i*，ogyZ+i

?n=-yn*logy'

_^=+駕*%

aw—dyn+1dhn+1dhndwn-!dyndhndwn^

12*.參考答案：

RNN的計(jì)算公式可以寫為：

ct=W-[xt,+b

假設(shè)時(shí)序長(zhǎng)度為T,則在梯度反向傳播過(guò)程中，T時(shí)刻的誤差I(lǐng)T對(duì)W的梯度

為：

T

dlTdlT1~~rdCjdcT

麗=乙=1購(gòu)*(]lj=i+1dcj_^dW

n：=i+i^中每一項(xiàng)都時(shí)介于o-i之間的小數(shù)，當(dāng)T很大時(shí)，n}=i+i券；

值趨近于0,從而產(chǎn)生梯度消失問(wèn)題。

在LSTM中，和=4?c1+i-tanh(W-[h_x]+b),因此3-=f,

tctvtcdCjt

由于ft通常為1或者為0,當(dāng)為1時(shí)，所有梯度能夠在LSTM中傳遞，當(dāng)為0

時(shí)，說(shuō)明上一時(shí)刻的信息對(duì)當(dāng)前時(shí)刻沒(méi)有影響，因此沒(méi)有必要傳回梯度更新參

數(shù)。這樣，LSTM解決了RNN的梯度消失問(wèn)題。

第七章強(qiáng)化學(xué)習(xí)

1.A

2.D

3.A

4.B

5.B;C

6.參考答案：

根據(jù)公式(7.1.5)所示的價(jià)值函數(shù)的貝爾曼方程聯(lián)立方程組：

'4G1)=R(S1，上,S3)+y/($3)=0+0.99x%(53)

%。2)=R(S2,上,S4)+丫/。4)=1+0.99X/GJ

'/(S3)=R(S3,上,sQ+y/6d)=-1+0.99X/(sQ

4(S4)=0

、/(Sd)=0

解得：

|%(S1)=-0.99

%⑸)=1

</⑸)=-1

%⑸)=0

<%(Sd)=0

7.參考答案

由于機(jī)器人每一步只能向上或者向右移動(dòng)一個(gè)方格，首先計(jì)算狀態(tài)S3選擇這兩

個(gè)不同動(dòng)作后分別所得動(dòng)作-價(jià)值函數(shù)取值：

9兀（$3,上）=2P（s1s3,上）囚⑸，上,s'）+y/G'）］

sres

=1x（-1+0.99x0）+0x???=-1

%（$3,右）=WP（S［S3,右）［R（S3,右,s'）+y/S）］

sres

=1x(1+0.99x0)+0x???=1

可見，智能體在狀態(tài)S3選擇“向上移動(dòng)一個(gè)方格”行動(dòng)所得回報(bào)《兀國(guó),上）值

為-1、選擇“向右移動(dòng)一個(gè)方格”行動(dòng)所得回報(bào)《式$3,右）值為1。顯然，智能體

在狀態(tài)S3應(yīng)該選擇“向右移動(dòng)一個(gè)方格”行動(dòng)，這樣能夠獲得更大的回報(bào)。

于是，經(jīng)過(guò)策略優(yōu)化后，狀態(tài)S3