COM070432011級人工智能基礎(chǔ)A卷標(biāo)準(zhǔn)答案

1、課程編號：COM07043 北京理工大學(xué) 2013 - 2014 學(xué)年第 一 學(xué)期2011級人工智能基礎(chǔ)期末試題A卷 班級 學(xué)號 姓名 成績 一、判斷題（10分，每小題1分）1. 按Strong AI的觀點(diǎn)，可以認(rèn)為Google自動汽車是智能的。 （´）2. BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法的優(yōu)化目標(biāo)是使實(shí)際輸出與期望輸出之間的誤差平方和最小化。 （）3. 蟻群優(yōu)化算法中，每個(gè)人工螞蟻都需要構(gòu)建自己的解。 （）4. State Space和And/Or Graph只是兩種不同的問題表示方法，但其解決問題的思路是一樣的。 （´）5. Self-Organizing Feature Map

2、(SOFM)神經(jīng)網(wǎng)絡(luò)可用于聚類。 （）6. 通過Breadth-First Search算法一定能找到最優(yōu)解。 （）7. 歸結(jié)演繹推理方法是一種反證法。 （）8. Decision Tree中的非葉節(jié)點(diǎn)對應(yīng)于屬性值。 （´）9. Genetic Algorithms屬于表現(xiàn)型進(jìn)化算法。 （´）10. k-中心點(diǎn)聚類算法中，每個(gè)簇用其均值來代表。 （´）二、填空題（20分，每空2分）1. 從計(jì)算實(shí)質(zhì)上來說，Supervised Learning是對 函數(shù) 的學(xué)習(xí)。2. 所有Heuristic Search方法想要解決的基本問題都是 利用啟發(fā)式信息，在一個(gè)解空間中，通

3、過探索有限數(shù)量的解來找到最優(yōu)解 。3. Evolutionary Algorithms中，通過 選擇 操作降低解的多樣性以便使算法收斂，通過 遺傳 操作增加解的多樣性以便發(fā)現(xiàn)全局最優(yōu)解。4. 將語句“所有瞎眼老鼠都沒有尾巴”用First-Order Logic (FOL)來表示，可以是 ，將其轉(zhuǎn)換為合取范式是。5. Minimum Description Length準(zhǔn)則是 奧卡姆剃刀 原則的體現(xiàn)。在利用該準(zhǔn)則解決決策樹學(xué)習(xí)問題時(shí)，需要考慮兩個(gè)編碼長度，分別是 決策樹的編碼長度 和 例外數(shù)據(jù)的編碼長度 6. 常用 數(shù)據(jù)采樣 手段提高聚類算法的效率。三、計(jì)算題（50分）1 在下圖所示的圖結(jié)構(gòu)上，

4、S為起始節(jié)點(diǎn)，G為目標(biāo)節(jié)點(diǎn)，邊上的數(shù)字表示從某節(jié)點(diǎn)到另一節(jié)點(diǎn)的距離?，F(xiàn)要求計(jì)算從S到G的最短路徑。 茲給出各點(diǎn)對應(yīng)的啟發(fā)函數(shù)值如下表所示：點(diǎn)SABCDG啟發(fā)距離2220812100 問題如下： 1）以上啟發(fā)函數(shù)符合A*算法的可容許性條件嗎？請回答并說明原因。3分答：符合，因?yàn)榭扇菰S性條件是：h(n)<=h*(n)，h(n)為當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值，即題中給出的啟發(fā)函數(shù)。h*(n)為實(shí)際問題的代價(jià)值，對于每一點(diǎn)，均滿足這個(gè)條件h(n)<=h*(n)，因此，此啟發(fā)函數(shù)符合A*算法的可容許性條件 2）如果以上啟發(fā)函數(shù)符合A*算法的可容許性條件，請用A*搜索方法求解該問題。給出搜索圖，在

5、圖上標(biāo)注每個(gè)節(jié)點(diǎn)的啟發(fā)函數(shù)值（h值）和估價(jià)函數(shù)值（f值），以及節(jié)點(diǎn)擴(kuò)展順序。7分節(jié)點(diǎn)擴(kuò)展順序：S > C > D > G2. 下圖所示為一棵Game Tree，其中末一行的數(shù)字是節(jié)點(diǎn)的靜態(tài)估值。如按從左到右順序進(jìn)行剪枝搜索。請?jiān)趫D上標(biāo)注搜索與剪枝過程，包括節(jié)點(diǎn)上的倒推值和被剪去的分枝（在剪枝處用×做標(biāo)記´）。在此基礎(chǔ)上說明計(jì)算的最終目標(biāo)是什么。10分 計(jì)算的最終目標(biāo)：在A狀態(tài)下，確定合適的走法，即走B好還是走C好。根據(jù)以上搜索過程，可知走C好。3. 某公司招聘工作人員，A、B、C三人面試，經(jīng)面試后公司表示如下想法： （1）三人中至少錄取一人。 （2）如果錄

6、取A而不錄取B，則一定錄取C。 （3）如果錄取B，則一定錄取C。 求證：用Resolution推理方法證明公司一定錄取C。10分答：首先表示事實(shí)和知識如下： （1） （2） （3） 并將其轉(zhuǎn)化為合取范式如下： 然后，表示結(jié)論并取反： 最后，執(zhí)行歸結(jié)過程如下： 歸結(jié)，得； 歸結(jié)，得 歸結(jié)，得 歸結(jié)，得 歸結(jié)，得NIL 因此，結(jié)論取反不成立，即公司一定錄取C.答：1)將問題中提供的知識用謂詞表示如下：Admission(x):表示x被錄用；Admission(x):表示x未被錄用Admission(x) trueAdmission(A) Admission(B) Admission(C)Admis

7、sion(B) Admission(C)2)用謂詞表示結(jié)論的否定 Admission(C)3)將上述謂詞公式轉(zhuǎn)化為子句集如下：Admission(x) Admission(A) Admission(B) Admission(C)Admission(B) Admission(C)4)按謂詞邏輯的歸結(jié)原理對此子句集進(jìn)行歸結(jié)，歸結(jié)反演樹如圖因此，公司一定錄取C.4. 假設(shè)根據(jù)以下三個(gè)因素來判斷計(jì)算機(jī)的質(zhì)量（好或壞）： （1） 計(jì)算機(jī)運(yùn)行起來是否有噪聲，設(shè)其用N來表示，其取值為true或false; （2）計(jì)算機(jī)是否容易死機(jī)，設(shè)其用F來表示，其取值為true或false; （3）應(yīng)用程序在該計(jì)算機(jī)上運(yùn)

8、行時(shí)是否速度很慢，設(shè)其用A來表示，其取值為true或false。 現(xiàn)對于該問題，提供了如下數(shù)據(jù)： 問題如下：1） 要求學(xué)習(xí)一個(gè)決策樹來解決該問題。請根據(jù)上述數(shù)據(jù)，基于信息增益方法為決策樹選擇根節(jié)點(diǎn)。10分答：1）首先，計(jì)算樣本的熵。從表格中，我們發(fā)現(xiàn)一共8個(gè)樣本，取值為ok的樣本有5個(gè)，取值為bad的有3個(gè)，因此，樣本里有5個(gè)正例，3個(gè)反例，記為S(5+,3-)，所以，樣本的熵為： （公式要改）其次，分別以N, F和A作為根節(jié)點(diǎn)，計(jì)算其信息增益： 因此，選用為N作為根結(jié)點(diǎn) （確認(rèn)以上計(jì)算結(jié)果） 2）根據(jù)上述數(shù)據(jù)，利用m-估計(jì)法（m=2）學(xué)習(xí)一個(gè)樸素貝葉斯分類器。利用該樸素貝葉斯分類器，判斷當(dāng)N

9、=false, F=true, A=true時(shí)，計(jì)算機(jī)是好還是壞，并觀察你的判斷結(jié)果與表中所給出的數(shù)據(jù)是否一致？10分答：類先驗(yàn)概率 P(ok)=5/8，P(bad)=3/8.設(shè)表示類別，取值為“bad”或者“ok”。表示第i種因素的真假有無。譬如，對于N來說，其true與false分別用N和 N表示。表示類訓(xùn)練樣本中出現(xiàn)的次數(shù)，表示用于類訓(xùn)練樣本的總數(shù)，m=2則 m-估計(jì)的計(jì)算公式為由訓(xùn)練樣本可知：P(Nok)=2/7，P(Nok)=5/7，P(Nbad)=3/5，P(Nbad)=2/5 P(Fok)=3/7，P(Fok)=4/7，P(Fbad)=3/5，P(Fbad)=2/5 P(Aok)

10、=2/7，P(Aok)=5/7，P(Abad)=2/5，P(Abad)=3/5若設(shè)all為bad與ok的集合，則相應(yīng)的分類公式為對于N=false, F=true, A=true,時(shí)， （以上數(shù)據(jù)已變化，修改）時(shí)， （以上數(shù)據(jù)已變化，修改）因此，判斷結(jié)果為bad，與所給數(shù)據(jù)庫一致。（以上數(shù)據(jù)已變化，再確認(rèn)） 四、算法題（20分）1. 要求采用人工神經(jīng)網(wǎng)絡(luò)對字符T進(jìn)行識別，其識別任務(wù)是：當(dāng)輸入任意一個(gè)大小為20×20的二值圖像時(shí)，神經(jīng)網(wǎng)絡(luò)能判斷其是否為字符T。這里，二值圖像中每個(gè)點(diǎn)取值為1或0，當(dāng)取值為1時(shí)表示該點(diǎn)為黑色，否則為白色。下圖給出了一幅輸入圖像的例子： 問題如下： 1） 請

11、給出能用于完成上述字符識別任務(wù)的人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)（不考慮其權(quán)值）。5分答：采用三層感知器對字母進(jìn)行識別。其中，第一層為輸入層，接受輸入的字符圖像，圖像大小為20×20，因此，輸入神經(jīng)元有400個(gè)，每個(gè)輸入神經(jīng)元對應(yīng)于圖像中的一個(gè)像素。第二層為隱含層，其神經(jīng)元個(gè)數(shù)確定為200個(gè)。最后一層為輸出層，僅包含一個(gè)神經(jīng)元，該神經(jīng)元輸出1表示輸入的是字母T，0則表示不是字母T. 2）請?jiān)O(shè)計(jì)一種進(jìn)化算法來學(xué)習(xí)你所設(shè)計(jì)出的上述神經(jīng)網(wǎng)絡(luò)中的權(quán)值： 2-1）給出該進(jìn)化算法的偽代碼。10分 2-2）說明該算法運(yùn)行所需的數(shù)據(jù)條件及其學(xué)習(xí)過程。5分答： 2-1）采用進(jìn)化規(guī)劃算法優(yōu)化上述神經(jīng)網(wǎng)絡(luò)：將網(wǎng)絡(luò)中所有

12、神經(jīng)元之間的連接權(quán)值連接起來作為一個(gè)個(gè)體。相應(yīng)偽碼如下：隨機(jī)生成10個(gè)個(gè)體。對于每個(gè)個(gè)體，在訓(xùn)練數(shù)據(jù)上進(jìn)行分類，統(tǒng)計(jì)識別率，作為其適應(yīng)度。Do 統(tǒng)計(jì)最優(yōu)適應(yīng)度值 對于每個(gè)個(gè)體，按照高斯擾動方法進(jìn)行突變，獲得10個(gè)新個(gè)體。 對于每個(gè)新個(gè)體，在訓(xùn)練數(shù)據(jù)上進(jìn)行分類，統(tǒng)計(jì)識別率，作為其適應(yīng)度。 在10個(gè)舊個(gè)體和10個(gè)新個(gè)體上，按隨機(jī)型q-競爭法選擇出10個(gè)個(gè)體。While 到達(dá)最大迭代次數(shù)or 最優(yōu)適應(yīng)度值連續(xù)10代沒有變化。2-2） 數(shù)據(jù)條件：有標(biāo)注的字符圖像集合，其中每個(gè)元素是一幅圖像及其類別標(biāo)注（是T或不是T）。 學(xué)習(xí)過程：收集數(shù)據(jù)并標(biāo)注；在數(shù)據(jù)集合上執(zhí)行上述算法。額外答案：粒子群優(yōu)化算法For

13、 each 粒子初始化EndDoFor each粒子計(jì)算適應(yīng)度if 此適應(yīng)度值好于此粒子對應(yīng)的歷史最佳適應(yīng)度將此值作為此粒子歷史最佳適應(yīng)值pBest。End_選擇粒子群體中所對應(yīng)的最好適應(yīng)度作為gBest_For each 粒子根據(jù)該粒子當(dāng)前飛行速度、該粒子最好適應(yīng)度以及群體最好適應(yīng)度，改變該粒子飛行速度，并調(diào)整其位置。_EndWhile 算法到達(dá)最大迭代次數(shù)or 適應(yīng)度值小于給定的誤差值用PSO算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)權(quán)值的具體描述為：首先應(yīng)將網(wǎng)絡(luò)中所有神經(jīng)元之間的連接權(quán)值編碼成實(shí)數(shù)碼串來表示一個(gè)粒子個(gè)體。網(wǎng)絡(luò)中包含了400個(gè)待優(yōu)化的權(quán)值以及一個(gè)閾值，則每個(gè)粒子個(gè)體將由401個(gè)參數(shù)組成的向量來表示。其次，初始化粒子群。初始化粒子群的規(guī)模、最大迭代次數(shù)、粒子個(gè)體極值等相關(guān)參數(shù)，并按照粒子群規(guī)模隨機(jī)產(chǎn)生一定數(shù)量的粒子個(gè)體。初始化粒子的位置、速度。同時(shí)初始化粒子個(gè)體極值和粒子群體極值。然后，利用PSO進(jìn)行學(xué)習(xí)從而優(yōu)化神經(jīng)網(wǎng)絡(luò)。在神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化過程中，給定的樣本空間往往要分為兩部分：