哈工大人工智能原理習(xí)題homework-3

1、人工智能原理 練習(xí)題-3教科書(shū)當(dāng)中的某些章節(jié)。對(duì)于加星號(hào)的習(xí)題，應(yīng)該編寫(xiě)程序來(lái)完成。5 章 不確定性推理根據(jù)基本原理證明：P (a | ba )=1。使用概率公理證明：對(duì)于任何離散隨機(jī)變量的概率分布，總和等于1。這個(gè)問(wèn)題涉及原子事件的性質(zhì)：證明所有原子事件的析取在邏輯上等價(jià)于true（）證明任何命題合法等價(jià)于蘊(yùn)涵其真值的原子事件的析取?？紤]從一副標(biāo)準(zhǔn)的52 張紙牌（不含大小王譯者注）中分發(fā)每手5 張牌的撲克牌域。假設(shè)發(fā)牌人是公平的。在聯(lián)合概率分布中共有多少個(gè)原子事件（即，共有多少種5 張手牌的組合）？每個(gè)原子事件的概率是多少？拿到大同花順（即同花的 A、K、Q、J、10譯者注）的概率是多少？四

2、同張（4張相同的牌，分別為4 種花色譯者注）的概率是多少？在一年一度的體檢之后，醫(yī)生告訴你一個(gè)好消息和一個(gè)壞消息。壞消息是你在一種嚴(yán)重疾病的測(cè)試中結(jié)果呈陽(yáng)性，而這個(gè)測(cè)試的精度為 99%（即當(dāng)你確實(shí)患這種病時(shí)，測(cè)試結(jié)果為陽(yáng)性的概率為 0.99，而當(dāng)你未患這種疾病時(shí)測(cè)試結(jié)果為陰性。好消息是，這是一種罕見(jiàn)10000 1 例。為什么“這種病很罕見(jiàn)”對(duì)于你而言是一個(gè)好消息？你確實(shí)患有這種病的概率是多少？在保持某些一般背景證據(jù)固定的上下文中，而不是完全沒(méi)有任何消息的情況下，考慮一些特定命題的結(jié)果經(jīng)常是相當(dāng)有益的e：證明乘法規(guī)則的條件化版本：P（X，Y|e）=P(X|Y,e)P(Y|e)證明公式（13.10

3、）中的貝葉斯法則的條件化版本。證明語(yǔ)句P(A,B|C)=P(A|C)P(B|C) 與語(yǔ)句 P(A|B,C)=P(A|C)，以及P(B|A,C)=P(B|C) 都是等價(jià)的。n 個(gè)無(wú)偏差硬幣的袋子，并且告訴你其中n-1 個(gè)硬幣是正常的，一面1 枚硬幣是偽造的，它的兩面都是正面。假設(shè)你把手伸進(jìn)口袋均勻隨機(jī)地取出一枚硬幣，把它拋出去，并發(fā)現(xiàn)硬幣落地后正面朝上。那么你拿到偽幣的（條件）概率是多少？假設(shè)你不停地拋這枚硬幣，拿到它之后一共拋了k 次而且看到 k 次正面向上。那么現(xiàn)在你拿到偽幣的概率是多少？k k 次拋FAK（偽造NORMA（正常這個(gè)過(guò)程發(fā)生錯(cuò)誤的（無(wú)條件）概率是多少？這道習(xí)題研究條件獨(dú)立性關(guān)

4、系對(duì)概率計(jì)算中所需信息量的影響方式。假設(shè)我們希望計(jì)算P(h|e1,e2)，而我們沒(méi)有任何條件獨(dú)立性的信息。下面哪組數(shù)據(jù)足以完成計(jì)算？(i) P(E1,E2)，P(H)，P(E1|H)，P(E2|H)(ii) P(E1,E2)，P(H)，P(E1,E2|H)(iii) P(H)，P(E1|H)，P(E2|H)1212假設(shè)我們已知對(duì)于H，E ，E 的所有取值都有 P(E |H ,E )= P(E |H)。上面的這3 1212假設(shè)X，Y，Z 3 個(gè)布爾隨機(jī)變量。將其聯(lián)合概率分布P（X,Y,Z）8 個(gè)條目依次編號(hào)為a h。把語(yǔ)句“X 與Y 關(guān)于給定的Z 條件獨(dú)立”表達(dá)為與a h 相關(guān)的一組公式。其中有

5、多少個(gè)不冗余的公式？1（改編自Pearl（198）假設(shè)你是雅典一次夜間出租車肇事逃逸的交通事故的目擊者。雅典所有的出租車都是藍(lán)色或者綠色的。而你發(fā)誓所看見(jiàn)得肇事出租車是藍(lán)色的。大量的實(shí)驗(yàn)表明，在昏暗的燈光條件下，對(duì)于藍(lán)色和綠色的區(qū)分的可靠度為 75%。有可能據(jù)（和命題“肇事車看起來(lái)是藍(lán)色的）1（改編自Pear（198）3個(gè)囚犯，和，被關(guān)在各自的獄室里。大家都和中的一個(gè)人，讓他知道明天早上他就會(huì)被赦免把赦免消息告訴了。那么，根據(jù)以上已知的信息，被處死的幾率有多大？（用數(shù)學(xué)方法解答這個(gè)問(wèn)題，而）貝葉斯網(wǎng)絡(luò)部分考慮下圖所示的汽車故障診斷網(wǎng)絡(luò)：a: IcyWeathrestarterMotor 對(duì)網(wǎng)絡(luò)

6、進(jìn)行擴(kuò)展b: 為所有的節(jié)點(diǎn)指定合理的條件概率表c: 8 個(gè)布爾節(jié)點(diǎn)的聯(lián)合概率分布中包含多少個(gè)獨(dú)立的數(shù)值?d: 在你的網(wǎng)絡(luò)的條件概率表里一共包含多少個(gè)獨(dú)立的數(shù)值?e: starts 的條件概率表可以描述為一個(gè)噪聲與（noisy-and ）分布。請(qǐng)使用一種通用的方式對(duì)其進(jìn)行定義，并分析它與噪聲或(noisy-or)分布的關(guān)系。BatteryBatteryRadioIgnitionGasstartsMoves上圖中每個(gè)變量都是布爾型并且其取值為true 時(shí)表示汽車的相應(yīng)部件正?；蛘郀顟B(tài)正常.Battery電池Radio 車內(nèi)收音機(jī)Ignition 電子打火Gas 油箱狀態(tài)Starts發(fā)動(dòng)機(jī)能夠發(fā)動(dòng)M

7、oves汽車能夠正常運(yùn)行 A(報(bào)警器響)F (報(bào)警器 出A故障)FG(測(cè)溫儀出故障)G(測(cè)溫儀讀數(shù))T（核反應(yīng)堆的核心溫度）為這個(gè)問(wèn)題域構(gòu)造一個(gè)貝葉斯網(wǎng)絡(luò)，假設(shè)當(dāng)核心溫度太高時(shí)測(cè)量以更容易出故障。你得到的貝葉斯網(wǎng)絡(luò)是多數(shù)結(jié)構(gòu)嗎G T 都只有兩種讀數(shù)，正常/偏高; 當(dāng)溫度儀正常工作時(shí)他給出正常的讀數(shù)的概率為x,出現(xiàn)故障時(shí)給出正確的讀數(shù)的概率為y,給出與G 相關(guān)聯(lián)的條件概率表假設(shè)報(bào)警器能正常工作-除非它壞了,這種情況下他不會(huì)發(fā)出報(bào)警聲.給出與 A 相關(guān)聯(lián)的條件概率表.假設(shè)報(bào)警器和測(cè)溫儀都能正常工作,并且報(bào)警器發(fā)出了報(bào)警聲.根據(jù)網(wǎng)絡(luò)中的各種條件概率,計(jì)算核反應(yīng)堆核心溫度過(guò)高的概率表達(dá)式的值.兩個(gè)來(lái)自

8、世界上不同地方的宇航員同時(shí)用他們自己的望遠(yuǎn)鏡觀測(cè)了太空中某個(gè)小區(qū)域內(nèi)N,記者兩個(gè)宇航員的觀測(cè)結(jié)果分別為M M .通常,1 顆12的誤差,發(fā)生錯(cuò)誤的概率e 很小. 而每臺(tái)望遠(yuǎn)鏡可能發(fā)生(發(fā)生的概率f 更小)對(duì)焦不準(zhǔn)確(分別F F1),3 顆甚至更多的恒星(或者說(shuō),N 3 時(shí),連一顆和星都觀測(cè)不到).考慮下圖中所示的三種貝葉斯網(wǎng)絡(luò)結(jié)構(gòu).這三種網(wǎng)絡(luò)哪個(gè)是對(duì)上述信息的正確的 (但不一定是高效的) 表示;那一種網(wǎng)絡(luò)結(jié)構(gòu)是最好的?請(qǐng)給出解釋c. 0,1,2,3,4時(shí),寫(xiě)出一個(gè)關(guān)于P(M| N)的條件概率表.概率分布11表中的每一個(gè)條目都應(yīng)該表達(dá)為e 的參數(shù)和/f 的一個(gè)函數(shù)假設(shè) MM 3 .如果我們假設(shè)N

9、 取值上沒(méi)有先驗(yàn)概率的約束,可能的恒星數(shù)目是12多少?在這些觀測(cè)的結(jié)果下,最可能的恒星數(shù)是多少?解釋如何計(jì)算這個(gè)數(shù)目,或者,如果不能計(jì)算,解釋還需要附加什么信息及它將如何影響結(jié)果.F1F2M1F1F2M1M2NF1NF2M1M2M1M2NF1F2考慮上圖M1M2NF1F2 0,1,2,3,4,3 描述的符號(hào)條件概率表.使用枚舉算法,計(jì)12算概率分布P(N | M 2,M2)12這道習(xí)題是關(guān)于例題中的變量消元算法的:對(duì)如下查詢應(yīng)用了變量消元算法P(Burglary | JohnCalls true,MaryCalls true)執(zhí)行必要的計(jì)算,并檢驗(yàn)計(jì)算結(jié)果的正確性.統(tǒng)計(jì)計(jì)算中算術(shù)運(yùn)算次數(shù),將其

10、與枚舉法完成的運(yùn)算次數(shù)進(jìn)行比較.假設(shè)貝葉斯網(wǎng)絡(luò)具有鏈?zhǔn)浇Y(jié)構(gòu),即由一個(gè)布爾隨機(jī)變量序列X , X,., X構(gòu)成;12n其中Parents(X ) X對(duì)于i 2,3,.,n.請(qǐng)問(wèn)通過(guò)枚舉法計(jì)算P(X| X)true 的復(fù)ii11n雜度是什么?用變量消元算法呢?證明對(duì)于任何排序與網(wǎng)絡(luò)結(jié)構(gòu)一致的變量,運(yùn)行多樹(shù)結(jié)構(gòu)網(wǎng)絡(luò)上的變量消元算法的復(fù)雜度與樹(shù)的規(guī)模呈線性的關(guān)系。研究通用貝葉斯網(wǎng)絡(luò)中精確推理的復(fù)雜度a, 3-sat 問(wèn)題都可以歸約到為了表示這個(gè)特定問(wèn)題而構(gòu)造的貝葉斯網(wǎng)絡(luò)的精確推理問(wèn)題,并且因此貝葉斯網(wǎng)絡(luò)的精確推理是 NP 難題.提示:考慮一個(gè)網(wǎng)絡(luò),每個(gè)命題符號(hào)用一個(gè)變量來(lái)表示,每個(gè)句子用一個(gè)變量來(lái)表示

11、,以及每個(gè)子句合取式用一個(gè)變量來(lái)表示.b, 3-sat 問(wèn)題中的可滿足復(fù)制的個(gè)數(shù)進(jìn)行統(tǒng)計(jì)是#P 完全的(個(gè)數(shù) 完全的)證明貝葉斯網(wǎng)絡(luò)的精確推理至少和這個(gè)問(wèn)題一樣難.73 支足球隊(duì)A,B,和C 兩兩之間各賽一場(chǎng).每場(chǎng)在兩隊(duì)之間進(jìn)行,結(jié)果對(duì)每支球隊(duì)而言可能是勝,負(fù),平.每支球隊(duì)都有確定但未知的實(shí)力-表示為一個(gè)0 到3 之間的整數(shù)而每場(chǎng)的比賽結(jié)果以某種概率取決于兩個(gè)球隊(duì)之間的差距.A, 構(gòu)造一個(gè)關(guān)系概率模型來(lái)描述這個(gè)閾,并為所有必要的概率分布給出數(shù)值.B, 構(gòu)造等價(jià)的貝葉斯網(wǎng)絡(luò).C, 假設(shè)在前兩場(chǎng)比賽中A B,C 戰(zhàn)平.選擇使用一種精確推理算法,3 場(chǎng)比賽結(jié)果的后驗(yàn)概率分布.D, 假設(shè)聯(lián)賽中總共有

12、n 支球隊(duì),并且我們已經(jīng)知道了除最后一場(chǎng)比賽外的所有比賽結(jié)果.現(xiàn)在要預(yù)測(cè)最后一場(chǎng)比賽的結(jié)果,其計(jì)算復(fù)雜度隨n 如何變化?E, 研究將馬爾可夫聯(lián)蒙特卡洛方法應(yīng)用于這個(gè)問(wèn)題.在實(shí)際運(yùn)算中算法的收斂速度如何?算法的規(guī)模擴(kuò)展性能如何?6 章 機(jī)器學(xué)習(xí)方法針對(duì)下述問(wèn)題畫(huà)出其決策樹(shù)：當(dāng)十字路口的信號(hào)燈變?yōu)榫G色時(shí)，判斷是否向前走。我們從不沿著決策樹(shù)中的同一條路經(jīng)對(duì)某屬性進(jìn)行兩次測(cè)試。為什么？假設(shè)我們從決策樹(shù)中生成一個(gè)訓(xùn)練集，并對(duì)該訓(xùn)練集應(yīng)用決策樹(shù)學(xué)習(xí)方法。當(dāng)訓(xùn)練集規(guī)模增加到無(wú)限的時(shí)候，學(xué)習(xí)算法最終是否能夠返回正確的決策樹(shù)？為什么？25 個(gè)實(shí)例的數(shù)據(jù)集。你計(jì)劃采用逐一刪除交叉驗(yàn)證。作為基準(zhǔn)，你使用簡(jiǎn)單的多數(shù)分

13、類器進(jìn)行實(shí)驗(yàn)（ 多數(shù)分類器是給定一個(gè)訓(xùn)練集，不考慮輸入，總是輸出在訓(xùn)練集中占多數(shù)的類別）你期望多數(shù)分類器的逐一刪除交叉驗(yàn)證的評(píng)分達(dá)到50%，但是令你驚訝的是，其評(píng)分為0。你能解釋這是為什么嗎？假定某個(gè)學(xué)習(xí)算法試圖在實(shí)例的分類實(shí)際上是隨機(jī)的情況下，找到一個(gè)一致假設(shè)?，F(xiàn)在有n 2 n個(gè)可能實(shí)例的集合中抽取出來(lái)的。計(jì)算在數(shù)據(jù)中0.5 之前，所需在的實(shí)例數(shù)目?？紤]一個(gè)使用在M 個(gè)假設(shè)具有誤差 M 和 表示的集體算法的誤差公式，并對(duì)M =5，10，以及20 而 =0.1，0.20.4 的情況分別對(duì)公式求值。如果去掉獨(dú)立假定，集體誤差是否可能差于 ？本習(xí)題關(guān)注于決策表的表達(dá)能力（第18.5 節(jié)。證明決策表

14、能夠表達(dá)任何布爾函數(shù)，如果測(cè)試的規(guī)模沒(méi)有限制的話。證明如果每個(gè)測(cè)試可以包含至多 k 個(gè)文字，那么決策表能夠表示任何可以用深度為k 的決策樹(shù)表示的函數(shù)?？紤]一個(gè)任意的貝葉斯網(wǎng)絡(luò)、該網(wǎng)絡(luò)的完全數(shù)據(jù)集，以及數(shù)據(jù)集與網(wǎng)絡(luò)相關(guān)的似然率。 計(jì)算參數(shù)值的最大似然?？疾煜旅娴臉颖炯?，每個(gè)樣本有6 個(gè)輸入和一個(gè)目標(biāo)輸出。I111111110000000I200011001101011I311101001100011I401001001011101I500110110110010I600010101101110T11111101000000在這些數(shù)據(jù)上運(yùn)行感知器學(xué)習(xí)規(guī)則，說(shuō)明最終的權(quán)值。運(yùn)行決策樹(shù)學(xué)習(xí)規(guī)則，說(shuō)明得

15、到的決策樹(shù)。評(píng)論你的結(jié)果。考慮這樣一個(gè)問(wèn)題：要將 N 個(gè)數(shù)據(jù)點(diǎn)通過(guò)一個(gè)線性分類器分成正例和反例。顯然，對(duì)d=1 N=2 個(gè)點(diǎn)，這總是可以做到的，無(wú)論點(diǎn)是如何進(jìn)行標(biāo)記的以（除非這些點(diǎn)落在相同的位置。說(shuō)明對(duì)于在一個(gè)維度d=2 的平面上的N=3 個(gè)點(diǎn)，這總是可以做到的，除非它們是共線的。說(shuō)明對(duì)于在一個(gè)維度d=2 的平面上的N=4 個(gè)點(diǎn)，這不是總能做到的。說(shuō)明對(duì)于在一個(gè)維度d=3 的空間上的N=4 個(gè)點(diǎn)，這總是可以做到的，出非它們是共面的。說(shuō)明對(duì)于在一個(gè)維度d=3 的空間上的N=5 個(gè)點(diǎn)，這不是總能做到的。有能力的學(xué)生可以試著證明：在一般位置上的（而不是）個(gè)點(diǎn)在維 空間上是線性可分的。由此可得，維線性

16、半空間的VC 維（參見(jiàn)第十八章）是N。20.1 中使用的數(shù)據(jù)可以視為由h54 個(gè)假設(shè)的每一個(gè)，分別100 的數(shù)據(jù)集，并為P(hi|d ,L ,d1P(Dm1 lime |d1,L ,dm畫(huà)出相應(yīng)的圖。評(píng)價(jià)一下你的結(jié)果。重復(fù)上一個(gè)習(xí)題，這次畫(huà)出P(Dm1 lime | hMAPP(Dm1 lime |hML的值。設(shè)Ann 對(duì)櫻桃和酸橙糖果的效用值分別是cA 和lA ，而B(niǎo)ob 的則是cB 和lB （但是只要Ann 打開(kāi)了一顆糖果的包裝，Bob ）可以想到，如果Bob 比Ann 更喜歡酸橙糖，那么對(duì)于 Ann 來(lái)說(shuō)聰明的做法是只要她足夠確信一包糖果是酸橙味的，就把它賣(mài)給Bob。另一方面，如果Ann

17、 在這個(gè)過(guò)程中打開(kāi)太多的糖果，這包糖的價(jià)值就損失了。討論如何確定賣(mài)這包糖果的最優(yōu)點(diǎn)的問(wèn)題。給定第 20.1 節(jié)中的先驗(yàn)分布，確定最優(yōu)過(guò)程的期望效用。兩個(gè)統(tǒng)計(jì)學(xué)家去看病，得到了相同的診斷：40%的幾率是一種致命疾病 A，60%的幾率是可能致命疾病B。幸運(yùn)的是，抗A 和抗B 的藥都不貴，100%有效，并且沒(méi)有副作用。統(tǒng)（狂熱的貝葉斯論者）會(huì)怎么做？總是用最大似然假設(shè)的第二個(gè)統(tǒng)計(jì)學(xué)家呢？B B B，有同樣的可能性并且都可以同樣地用抗B 3 個(gè)假設(shè)，兩個(gè)統(tǒng)計(jì)學(xué)家會(huì)怎么做呢？解釋如何把 boosting 考慮有m 個(gè)數(shù)據(jù)點(diǎn)(x , y y （20.5）x 集jjjj合生成的。找出當(dāng)數(shù)據(jù)達(dá)到最大條件對(duì)數(shù)似

18、然時(shí) ， ，和 的值。127 章 自然語(yǔ)言理解簡(jiǎn)介DCG 符號(hào)，為一種語(yǔ)言編寫(xiě)語(yǔ)法，這種語(yǔ)言正如同E1，除了它要加強(qiáng)語(yǔ)句的主語(yǔ)和動(dòng)詞之間的一致性，從而不會(huì)生成類似“ I semells the wumpus”的語(yǔ)句之外。增強(qiáng)E1的語(yǔ)法，使其能夠處理冠詞-名詞一致性問(wèn)題。也就是說(shuō)，確?！癮gents”是一個(gè)NP，而“agent”和“an agents”都不是。Java （或者任何其它你所熟悉的計(jì)算機(jī)語(yǔ)言和英語(yǔ)的主要區(qū)別，評(píng)論每種 情況下的“理解”問(wèn)題。首先可以考慮如下方面：語(yǔ)法、句法、語(yǔ)義、語(yǔ)用、合成性、上下文 依賴性、詞匯歧義、句法歧義、指代發(fā)現(xiàn)（包括代詞、背景知識(shí)以及“理解”意味著什么。下列

19、哪個(gè)是引入準(zhǔn)邏輯形式的原因？為了使書(shū)寫(xiě)簡(jiǎn)單合成語(yǔ)法的規(guī)則更容易。為了擴(kuò)展語(yǔ)義表示語(yǔ)言的表達(dá)能力。為了能夠用簡(jiǎn)潔的形式表示量詞作用范圍的歧義（除了其它歧義以外。為了使語(yǔ)義排歧更容易。用本章中的語(yǔ)法給出下列語(yǔ)句的語(yǔ)義解釋：It is a wumpus.The wumpus is dead.The wumpus is in 2,2.簡(jiǎn)單地用x xWumpuses 作為“It is a wumpus”的語(yǔ)義解釋是好主意嗎？考慮可替It was a wumpu本習(xí)題是有關(guān)非常簡(jiǎn)單語(yǔ)言的語(yǔ)法的。寫(xiě)出語(yǔ)言anbn 的上下文有關(guān)語(yǔ)法。寫(xiě)出回文語(yǔ)言（即所有字符串的后半部分是前半部分的逆串）的上下文有關(guān)語(yǔ)法。寫(xiě)出復(fù)制語(yǔ)言（即所有字符串的后半部分與前半部分相同）的上下文有關(guān)語(yǔ)法。PronounsomeonePreptoVwalkedDettheAdvPronounsomeonePreptoVwalkedDettheAdvslowlyNounsupermarket個(gè)語(yǔ)法中的哪個(gè)與該詞典結(jié)合能夠產(chǎn)生上述語(yǔ)句？畫(huà)出相應(yīng)的句法分析樹(shù)。（：B：（：SNP VPSNP VPSNP VPNP PronounNP PronounNP PronounNP Article NounNP NounNP Article NPVPVP PPNP Article NPVPVP A