哈工大人工智能原理習題homework-3

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

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

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

4、系對概率計算中所需信息量的影響方式。假設(shè)我們希望計算P(h|e1,e2)，而我們沒有任何條件獨立性的信息。下面哪組數(shù)據(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è)我們已知對于H，E ，E 的所有取值都有 P(E |H ,E )= P(E |H)。上面的這3 1212假設(shè)X，Y，Z 3 個布爾隨機變量。將其聯(lián)合概率分布P（X,Y,Z）8 個條目依次編號為a h。把語句“X 與Y 關(guān)于給定的Z 條件獨立”表達為與a h 相關(guān)的一組公式。其中有

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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