1、課程編號(hào)：21-081200-108-07 北京理工大學(xué) 2013 - 2014學(xué)年第一學(xué)期研究生人工智能期末試題班級(jí) 學(xué)號(hào) 姓名 成績 1. 學(xué)習(xí)（30分+5分） 下圖給出了兩類數(shù)據(jù)，分別如圖中和所示。另外，圖中兩條黑色粗實(shí)線分別代表橫、縱坐標(biāo)軸，其交點(diǎn)為原點(diǎn)。第1題圖現(xiàn)要求對(duì)上述數(shù)據(jù)進(jìn)行分類。(1) 10分 如果采用Decision Tree實(shí)現(xiàn)分類，請(qǐng)說明該Decision Tree的非葉節(jié)點(diǎn)、葉節(jié)點(diǎn)和邊分別是什么，并計(jì)算以下兩個(gè)值：(a) 該數(shù)據(jù)集的Entropy; (b) 當(dāng)根節(jié)點(diǎn)選擇根據(jù)x的值是否大于0來進(jìn)行決策時(shí)，所對(duì)應(yīng)的Information Gain。解：1）非葉節(jié)點(diǎn)為x與y

2、，葉節(jié)點(diǎn)為類別，邊為x與y的取值區(qū)間； 2）兩類樣本分別為6個(gè)和9個(gè)，因此： 3） (2) 10分 如果采用Naïve Bayesian Classifier實(shí)現(xiàn)分類，并將x，y的取值分別離散化為“大于0”和“小于等于0”兩種情況，請(qǐng)給出需要學(xué)習(xí)的數(shù)值及其結(jié)果，進(jìn)而判斷當(dāng)時(shí)的分類結(jié)果解：已知樣本a = a1,a2，其中a1為屬性x的值,a2為屬性y的值。類別集合C=黑框，白球若給出某一測試用例m，則需計(jì)算P(黑框|m)與P(白球|m)，并據(jù)此來進(jìn)行判別，但若要計(jì)算這兩個(gè)概率值，則需要計(jì)算各個(gè)類條件概率，下面為具體的學(xué)習(xí)過程。Step1. 根據(jù)給出的訓(xùn)練集，統(tǒng)計(jì)各類別以及各類別下各個(gè)特

3、征屬性的條件概率估計(jì)：Step2. 由于各個(gè)屬性間是獨(dú)立的，則根據(jù)貝葉斯定理有如下推導(dǎo)：則可推導(dǎo)出樣本的類別。對(duì)于樣本m = x>0, y<=0 判別其類別的過程如下： 因此，當(dāng)x>0, y<=0 則將其判別為白球類別。(3) 10分 如果采用Neural Network實(shí)現(xiàn)分類，請(qǐng)畫出能對(duì)上述數(shù)據(jù)進(jìn)行分類的網(wǎng)絡(luò)結(jié)構(gòu)（不含權(quán)值），并說明如何根據(jù)上述數(shù)據(jù)學(xué)習(xí)得到該網(wǎng)絡(luò)中的權(quán)值。解：采用多層感知器。該神經(jīng)網(wǎng)絡(luò)的輸入神經(jīng)元個(gè)數(shù)為2，分別表示x與y的值，輸出神經(jīng)元個(gè)數(shù)為1，1表示類別為黑框，0表示白球。隱含層神經(jīng)元個(gè)數(shù)為4。則其結(jié)構(gòu)如下：可利用BP學(xué)習(xí)算法來進(jìn)行學(xué)習(xí)（最小二乘法

4、、權(quán)值計(jì)算使用梯度下降等）。(4) （附加題）5分 能否使用Clustering技術(shù)解決上述分類問題？如能，應(yīng)怎樣解決？解：可以采用聚類技術(shù)求解。用k-means算法將以上數(shù)據(jù)聚成兩類，獲得相應(yīng)聚類中心。分類時(shí)，根據(jù)數(shù)據(jù)到聚類中心的距離來進(jìn)行判定?？梢杂镁垲愃惴?。但由于數(shù)據(jù)是凹型數(shù)據(jù)，因此，直接用k-means算法無法得到滿意，因此，可考試將此數(shù)據(jù)集映射到高維空間，使其變成凸型數(shù)據(jù)之后再對(duì)其使用類似于k-means的算法進(jìn)行聚類。另外一種方法則是采用可以處理凹型數(shù)據(jù)的聚類算法，譬如PCCA（Perron Cluster Cluster Analysis）方法。2. 搜索（30分+5分） 給定函

5、數(shù)：。要求計(jì)算該函數(shù)的最小值，其中的取值范圍為。(1) 10分 如果采用Gradient Descent方法求解，請(qǐng)描述其中一次迭代過程。解：梯度下降法的基本思想為：假設(shè)我們要求函數(shù)的最小值，首先需要選取一個(gè)初始點(diǎn)，然后下一點(diǎn)的產(chǎn)生是沿著梯度直線方向，這里是沿著梯度的反方向（因?yàn)槭乔笞钚≈担Ｌ荻认陆捣ǖ牡綖椋?其中，表示的是梯度的反方向，表示的是在梯度方向上的搜索步長。梯度可以通過對(duì)函數(shù)求導(dǎo)取得，步長的確定比較麻煩，太大容易發(fā)散，太小收斂速度太慢。因此步長的選擇需要沉思熟慮。另外，算法迭代的停止條件是梯度向量的幅值接近0即可。根據(jù)以上思想，對(duì)以下函數(shù)進(jìn)行最小值求解。，其中以及由于此問題

6、是存在約束條件下的最小值問題，在此條件下無法直接利用梯度下降法對(duì)其進(jìn)行優(yōu)化，需要將其進(jìn)行轉(zhuǎn)化，轉(zhuǎn)化無約束條件下進(jìn)行求解。因此有兩種方法解決，一是采用拉格朗日定理對(duì)其轉(zhuǎn)化，另一種是加入一個(gè)懲罰項(xiàng)，對(duì)超出約束條件的點(diǎn)進(jìn)行懲罰。這里可采用加入懲罰項(xiàng)來解決。因此，將上述函數(shù)轉(zhuǎn)化為以下函數(shù)表示： 其中為處罰項(xiàng)。若x1與x2均在此約束范圍內(nèi)懲罰項(xiàng)的值為0，對(duì)函數(shù)值沒有影響。下面是具體的一次迭代過程：首先，設(shè)置初始值為x1 = 0, x2 = 0.其次，計(jì)算梯度向量，對(duì)x1與x2求偏導(dǎo)：然后，計(jì)算下一點(diǎn)的值：由于此值均在約束條件下，所以此次迭代結(jié)束。(2) 10分 設(shè)計(jì)一個(gè)求解該問題的Evolutionar

7、y Algorithm。解：/*初始化遺傳算法參數(shù)*/const int maxGeneration; /進(jìn)化代數(shù)，即迭代次數(shù)const int sizeGene; /種群規(guī)模double pcross; /交叉概率選擇，0和1之間double pmutation; /變異概率選擇，0和1之間int *bestGene; /適應(yīng)度最好的染色體double bestFitness; /記錄進(jìn)化中最高的適應(yīng)度struct gene /每個(gè)染色體的結(jié)構(gòu) Double value2; /存的是x1與x2的值; int fitness; / 適應(yīng)度函數(shù)值;double Fitness()/*適應(yīng)度函數(shù)計(jì)

8、算*/double fit=;main() /初始化種群 for i=0,i< sizeGene;i+ 隨機(jī)產(chǎn)生一個(gè)初始解 /此處產(chǎn)生種群時(shí)，需注意兩點(diǎn)：一是產(chǎn)生的染色體是實(shí)數(shù)型，另一點(diǎn)是其值需要在約束條件范圍內(nèi) 計(jì)算其適應(yīng)度/ 進(jìn)化開始t = 1 / 進(jìn)化代數(shù)do選擇; 交叉;變異;重新計(jì)算適應(yīng)度函數(shù)F();bestGene = 此代進(jìn)化中適應(yīng)度最高的染色體 /記錄最優(yōu)解進(jìn)化代數(shù)t = t + 1;while(適應(yīng)度函數(shù)F()收斂| t< maxGeneration) / 進(jìn)化結(jié)束bestGene存儲(chǔ)的即為最佳路徑;(3) 10分 設(shè)計(jì)一個(gè)求解該問題的Swarm Intellig

9、ence Algorithm。解：在所設(shè)計(jì)的算法中，粒子群體規(guī)模設(shè)置為20，其中每個(gè)粒子的位置表示一種的取值，用實(shí)數(shù)表示，個(gè)體適應(yīng)度值為。最大迭代次數(shù)設(shè)置為100。具體算法流程如下：Step1. 在-5, 5區(qū)間中隨機(jī)生成20組兩兩一對(duì)的4個(gè)實(shí)數(shù)，作為粒子的初始位置和飛行速度。Step2. 計(jì)算每個(gè)粒子的適應(yīng)度。Step3. 統(tǒng)計(jì)截止當(dāng)前時(shí)刻，粒子群體對(duì)應(yīng)的最好適應(yīng)度以及每個(gè)粒子對(duì)應(yīng)的最好適應(yīng)度。Step4. 對(duì)于每個(gè)粒子，根據(jù)該粒子當(dāng)前飛行速度、該粒子最好適應(yīng)度以及群體最好適應(yīng)度，改變?cè)摿Ｗ语w行速度，并根據(jù)更新后速度調(diào)整其位置。Step5. 重復(fù)Step2-4，直到迭代次數(shù)超過100次。St

10、ep6. 輸出所得到的解答：群體最好適應(yīng)度為所求得的函數(shù)最小值，該適應(yīng)度對(duì)應(yīng)的粒子位置為所求得的值。(4) （附加題）5分 請(qǐng)用一種統(tǒng)一的算法結(jié)構(gòu)來總結(jié)以上三種算法。解：通過對(duì)解的變化，來訪問不同的解，直至獲得最優(yōu)解（參考新教材第6章）構(gòu)造及初始化解空間，選擇一種啟發(fā)式信息，迭代求解直到算法收斂或滿足一定的迭代次數(shù)。所得到的解即為找到的最優(yōu)解。A 初始點(diǎn)的選?。籅 計(jì)算在此自變量下函數(shù)的值；C 判斷是否符合終止條件，若符合則終止，相應(yīng)的函數(shù)值即為所求的解，若不符合，則根據(jù)某種搜索準(zhǔn)則，選擇下一次自變量的值，再次計(jì)算函數(shù)值，直至符合終止條件。其中，搜索準(zhǔn)則嚴(yán)重影響了迭代終止的時(shí)間與解的質(zhì)量，也就

11、是常提及的收斂速度及最優(yōu)解的全局性與局部性。3. 綜合應(yīng)用（40分）現(xiàn)要求設(shè)計(jì)一個(gè)智能系統(tǒng)，用于根據(jù)攝像頭拍攝的路況進(jìn)行汽車自動(dòng)駕駛。假設(shè)攝像頭輸入的圖像為20×20大小的二值圖像，其中每個(gè)點(diǎn)取值為1或0，當(dāng)取值為1時(shí)表示該點(diǎn)為黑色，否則為白色。根據(jù)此輸入，該智能系統(tǒng)從8種控制指令中選擇一種指令輸出，這8種指令包括起步、直行、左轉(zhuǎn)、右轉(zhuǎn)、加速、減速、剎車、停車。請(qǐng)給出該智能系統(tǒng)的設(shè)計(jì)結(jié)果，包括Perception部分、Performance部分、Evaluation部分以及Learning部分。其中Performance部分只需說明軟件部分即可，即只需設(shè)計(jì)從接受輸入的圖像到產(chǎn)生控制指

12、令的部分，忽略后面的機(jī)械控制等硬件部分。解：（1）Perception部分：攝像頭，向系統(tǒng)中輸入路況圖像。（2）Performance部分：即為從Perception部分接收的圖像后，根據(jù)learning部分學(xué)習(xí)得到的模型判別給出需要執(zhí)行的操作。此處采用多層感知器，其結(jié)構(gòu)如下：其中，第一層為輸入層，接受輸入的字符圖像，圖像大小為20×20，因此，輸入神經(jīng)元有400個(gè)，每個(gè)輸入神經(jīng)元對(duì)應(yīng)于圖像中的一個(gè)像素。第二層為隱含層，其神經(jīng)元個(gè)數(shù)確定為200個(gè)。最后一層為輸出層，為1個(gè)神經(jīng)元，輸出為1-8的整數(shù)，對(duì)應(yīng)8種指令即起步、直行、左轉(zhuǎn)、右轉(zhuǎn)、加速、減速、剎車、停車。（3）Evaluatio

13、n部分：根據(jù)車輛自動(dòng)駕駛時(shí)的操作性能，即不必人干預(yù)的程度，查看操作是否正確。正確與否的標(biāo)準(zhǔn)是與人面對(duì)Perception時(shí)所做的操作是否一致。（4）Learning部分：給出訓(xùn)練數(shù)據(jù)集（有操作的圖像集合，其中每個(gè)元素是一幅圖像及其相應(yīng)8種操作標(biāo)注）的基礎(chǔ)上，采用人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)用于完成汽車自動(dòng)駕駛?cè)蝿?wù)的學(xué)習(xí)，其結(jié)構(gòu)如Performance部分所述。其中神經(jīng)網(wǎng)絡(luò)中的各個(gè)權(quán)值采用進(jìn)化規(guī)劃算法來學(xué)習(xí)。首先，將網(wǎng)絡(luò)中所有神經(jīng)元之間的連接權(quán)值連接起來作為一個(gè)個(gè)體。其次，迭代學(xué)習(xí)，相應(yīng)偽碼如下：隨機(jī)生成10個(gè)個(gè)體。對(duì)于每個(gè)個(gè)體，在訓(xùn)練數(shù)據(jù)上進(jìn)行分類（相當(dāng)于多類劃分），統(tǒng)計(jì)識(shí)別率，作為其適應(yīng)度。Do 統(tǒng)計(jì)最

14、優(yōu)適應(yīng)度值 對(duì)于每個(gè)個(gè)體，按照高斯擾動(dòng)方法進(jìn)行突變，獲得10個(gè)新個(gè)體。對(duì)于每個(gè)新個(gè)體，在訓(xùn)練數(shù)據(jù)上進(jìn)行分類，統(tǒng)計(jì)識(shí)別率，作為其適應(yīng)度。在10個(gè)舊個(gè)體和10個(gè)新個(gè)體上，按隨機(jī)型q-競爭法選擇出10個(gè)個(gè)體。While 到達(dá)最大迭代次數(shù)or 最優(yōu)適應(yīng)度值連續(xù)10代沒有變化。最后，最好適應(yīng)度（即統(tǒng)計(jì)識(shí)別率最高）為所求得的解，即相應(yīng)的指令操作。附：可采用神經(jīng)網(wǎng)絡(luò)的算法進(jìn)行學(xué)習(xí)。具體過程為：采用單層感知器對(duì)圖像進(jìn)行識(shí)別。首先確定輸入輸出數(shù)據(jù)。將待識(shí)別的圖像轉(zhuǎn)化成網(wǎng)絡(luò)所能接受的輸入數(shù)據(jù)?？刹捎?0×20的點(diǎn)陣處理，其元素值為1或0。因此，有400個(gè)輸入點(diǎn)。輸出為一個(gè)十進(jìn)制值，可將其轉(zhuǎn)化成8位的字符

15、串，其表示起步，直行，左轉(zhuǎn)，右轉(zhuǎn)，加速，減速，剎車以及停車相應(yīng)操作，其值為1時(shí)，表示執(zhí)行此操作，其值為0時(shí)，表示不執(zhí)行此操作，注意，此表示形式能夠表示多種操作同時(shí)進(jìn)行的行為。激活函數(shù)為閾值函數(shù)，可根據(jù)訓(xùn)練樣本集自定義一種閾值函數(shù)。使其滿足某種條件下輸出某個(gè)值。其次，給出容許的目標(biāo)誤差及最大訓(xùn)練次數(shù)。最后，確定權(quán)值與閾值。可采用粒子群優(yōu)化算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)權(quán)值。具體描述為：先將網(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ù)組成的向量來表示。初始化粒子群之后利用PSO進(jìn)行學(xué)習(xí)從而優(yōu)化神經(jīng)網(wǎng)絡(luò)。在神經(jīng)網(wǎng)絡(luò)的