機器學習課后作業(yè)

1、精品文檔機器學習課后作業(yè)學 院：電子工程學院專 業(yè)：電子與通信工程姓 名：葉旭慶學 號3繼續(xù)考慮EnjoySport學習任務和2.2節(jié)中描述的假設空間H。如果定義一個新 的假設空間H',它包含H中所有假設的成對析取。如H'中一假設為：<?,Cold, High, ?, ?, ?>V<Sunny, ?, High, ?, ?, Sam>試跟蹤運行使用該假設空間 H'的候選消除算法，給定的訓練樣例如表2-1所示（需要分步列出S和G集合）。S0= (K K K (|),(|),(|) v ( K K K K K (|)G0 =

2、 (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 1: <Sunny, Warm, Normal, Strong, Warm, Same, Yes>S1=(Sunny, Warm, Normal, Strong, Warm, Same) v ( 八八九九八小)G1 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 2: <Sunny, Warm, High, Strong, Warm, Same, Yes>S2= (Sunny, Warm, Normal, Strong, Wa

3、rm, Same) v (Sunny, Warm, High, Strong, Warm, Same) ，(Sunny, Warm, ? , Strong, Warm, Same) v (|),(|),(|),(|),(|),(|)G2 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 3: <Rainy, Cold, High, Strong, Warm, Change, No>S3=(Sunny, Warm,Normal, Strong, Warm,Same)v (Sunny, Warm,High, Strong, Warm, S

4、ame)，(Sunny, Warm, ? , Strong, Warm, Same) v (|),(|),(|),(|),(|),(|)G3 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?),(Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same) 2Example 4: <Sunny, Warm, High, Strong, Cool, Change, Yes>S4= (Sunny, Warm, ?, S

5、trong, ?, ?) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High,Strong, ?, ?)，(Sunny, Warm, ? , Strong, ? , ?) v ( (|),(|),(|),(|),(|),(|),(Sunny, Warm, ？ , Strong, Warm,Same)v (Sunny, Warm,High, Strong, Cool, Change)G4 = (Sunny, ?, ?, ?, ?, ?) v

6、 (?, Warm, ?, ?, ?, ?),(Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2.5 請看以下的正例和反例序例，它們描述的概念是“兩個住在同一房間中的人 ”。 每個訓練樣例描述了一個有序?qū)Γ總€人由其性別、頭發(fā)顏色 ( black , brown或 blonde)、身高(tall , medium； short )以及國籍(US French, German Irish ,Indian , Chinese 或 Portuguese )。+ &

7、lt; < male brown tall US >, < female black short US > >+ < < male brown short French >, < female black short US > >- < < female brown tall German >, < female black short Indian > >+ < < male brown tall Irish >, < female brown short Irish

8、 > >考慮在這些實例上定義的假設空間為：其中所有假設以一對4元組表示，其中每個值約束與EnjoySport 中的假設表示相似，可以為：特定值、“?”或者“?”。例如，下面的假設：< < male ? Tall ? > < female ? ? French> >它表示了所有這樣的有序?qū)Γ旱谝粋€人為高個男性(國籍和發(fā)色任意)，第二個人為法國女性(發(fā)色和身高任意)。(a)根據(jù)上述提供的訓練樣例和假設表示，手動執(zhí)行候選消除算法。特別是要 寫出處理了每一個訓練樣例后變型空間的特殊和一般邊界。(b)計算給定的假設空間中有多少假設與下面的正例一致：+ &l

9、t; < male black short Portuguese > < female blonde tall Indian > >(c)如果學習器只有一個訓練樣例如(b)中所示，現(xiàn)在由學習器提出查詢，并由施教者給出其分類。求出一個特定的查詢序列，以保證學習器收斂到單個正確的假設，而不論該假設是哪一個(假定目標概念可以使用給定的假設表示語言來描述)。求出最短的查詢序列。這一序列的長度與問題(b)的答案有什么關聯(lián)？(d)注意到這里的假設表示語言不能夠表示這些實例上的所有概念(如我們可定義出一系列的正例和反例，它們并沒有相應的可描述假設)。如果要擴展這一語言， 使其能

10、夠表達該實例語言上的所有概念，那么 ( c) 的答案應該如何更改。答： (a). 第一步：S0 <(Q Q Q Q ), (Q Q Q Q)>G0 <(? ? ? ?), (? ? ? ?)>第二步：S1 <(male brown tall US), (female black short US)>G1 <(? ? ? ?), (? ? ? ?)>第三步：S2 <(male brown ? ?), (female black short US)>G2 <(? ? ? ?), (? ? ? ?)>第四步：S3 <(ma

11、le brown ? ?), (female black short US)>G3 <(male ? ? ?), (? ? ? ?)>， <? ? ? ?>,<? ? ? US>第五步：S4 <(male brown ? ?), (female ? short ?)>G4 <(male ? ? ?), (? ? ? ?)>(b) . 假設中的每個屬性可以取兩個值，所以與題目例題一致的假設數(shù)目為：2*2*2*2 ) *( 2*2*2*2 )= 256(c) . 這個最短序列應該為8， 28 256如果只有一個訓練樣例，則假設空間有

12、28 256個假設，我們針對每一個屬性來設置訓練樣例，使每次的假設空間減半。則經(jīng)過 8 次訓練后，可收斂到單個正確的假設。<female,blanck,short,Portuguese>,<female,blonde,tall,Indian><male,brown,short,Portuguese>,<female,blonde,tall,Indian><male,blanck,tall,Portuguese>,<female,blonde,tall,Indian><male,blanck,short,US>,

13、<female,blonde,tall,Indian><male,blanck,short,Portuguese>,<male,blonde,tall,Indian><male,blanck,short,Portuguese>,<female,black,tall,Indian><male,blanck,short,Portuguese>,<female,blonde,short,Indian><male,blanck,short,Portuguese>,<female,blonde,tall

14、,US>(d) . 若要表達該實例語言上的所有概念，那么我們需要擴大假設空間，使得每個可能的假設都包括在內(nèi)，這樣假設空間就遠遠大于256，而且這樣沒法得到最終的沒法收斂，因為對每一個未見過的訓練樣例，投票沒有任何效果，因此也就沒有辦法對未見樣例分類。所以不存在一個最優(yōu)的查詢序列。4歡迎下載 。精品文檔3.2考慮下面的訓練樣例集合:實例分類*71門之1+TTfarTT3-TF4+rF5-FT6-FT(a)請計算這個訓練樣例集合對于目標函數(shù)分類的嫡。 (b)請計算屬性a2相對這些訓練樣例的信息增益。答：cEntropy (S) pi log2 pi0.5log2 0.5 0.5log2 0.

15、5i 1一 一 一 一| S, |一一Gain(S A) Entropy(S)Entropy(Sv)v Values (A) | S |1 /EntropyS) 26 Entropy(SF)1 46*1 26*1 09歡血下載3.4 ID3僅尋找一個一致的假設，而候選消除算法尋找所有一致的假設。 考慮這兩種學習算法間的對應關系。(a)假定給定EnjoySport的四個訓練樣例，畫出ID3學習的決策樹。其 中EnjoySport目標概念列在第2章的表2-1中。(b)學習到的決策樹和從同樣的樣例使用變型空間算法得到的變型空 問(見第2章圖2-3)間有什么關系？樹等價于變型空間的一個成員嗎？(c)增

16、加下面的訓練樣例，計算新的決策樹。這一次，顯示出增長樹的 每一步中每個候選屬性的信息增益。，而J/m即jG力T£研V 卯 qf/7叫"雅SmifeN0(d)假定我們希望設計一個學習器，它搜索決策樹假設空間(類似 ID3) 并尋找與數(shù)據(jù)一致的所有假設(類似候選消除)。簡單地說，我們希望應用候 選消除算法搜索決策樹假設空間。寫出經(jīng)過表 2-1的第一個訓練樣例后的S和G 集合。注意S必須包含與數(shù)據(jù)一致的最特殊的決策樹，而 成須包含最一般的。 說明遇到第二個訓練樣例時S和G®合是如何被改進的(可以去掉描述同一個概 念的語法不同的樹)。在把候選消除算法應用到?jīng)Q策樹假設空間時

17、，預計會碰 到什么樣的困難？(a)解：要畫決策樹，需要計算每個候選屬性相對于整個樣例集合S的信息增益，然后選擇信息增益最高的一個屬性作為樹節(jié)點上第一個被測試的屬性。Gain(S, Sky尸 0.8113Gain(S, AirTemp尸 0.8113Gain(S, Humidity尸 0.1226Gain(S, Wind)=0Gain(S, Water尸 0.1226Gain(S, Forecast)，0.3113(b) (1)學習到的決策樹只包含一個與訓練樣例一致的假設，使用變型空間算法得到的變型空間包含了所有與訓練樣例一致的假設，但變型空間只含各屬性合 取式的集合，如果目標函數(shù)不在假設空間中

18、，即合取連接詞不能表示最小的子式 時，變型空間將會是空的。在本例中，學習到的決策樹Sky = Sunny ”與變型空間中的 G集合中的假設<Sunny, ?,?,?,?,?> 等價，Air-Temp= Warm”與G的 v?,Warm,?,?,?,?> 等價。學習到的決策樹是用變型空間算法得到的變型空間是一種包含關系，前者是后者的子集或者說是后者的一個元素，(2)在此例子中決策樹等價于變型空間的一個成員，但是一般情況的決策 樹并不一定等價于變型空間中的一個成員，因為決策樹的判別有順序，而假設空間中的元素的各個性質(zhì)沒有順序(c)Gain(S, Sky尸 0.3219Gain(S

19、, AirTemp尸 0.3219Gain(S, Humidity尸 0.0200Gain(S, Wind尸 0.3219Gain(S, Water尸 0.1710Gain(S, Forecast尸 0.0200顯然第一個屬性應該選擇 Sky AirTemp Wind若第一個屬性為Sky則：Gain(Ssunny, AirTemp尸 0Gain(Ssunny, Humidity尸 0.3113Gain(Ssunny, Wind尸 0.8113 ( 最大)Gain(Ssunny, Water)= 0.1226Gain(Ssunny, Forecast尸 0.1226若第一個屬性為AirTemp則

20、：Gain(Swarm, Sky)= 0Gain(Swarm, Humidity)= 0.3113Gain(Swarm, Wind)= 0.8113 ( 最大)Gain(Swarm, Water)= 0.1226Gain(Swarm, Forecast尸 0.1226若第一個屬性為Wind則：Gain(Sstrony, Sky)= 0.8113 ( 最大)Gain(Sstrony, AirTemp尸 0.8113 ( 最大)Gain(Sstrony, Humidity)= 0.1226Gain(Sstrony, Water)= 0.1226Gain(Sstrony, Forecast)= 0.

21、3113Entropy (S) =-(3/5)log(3/5)(2/5)log(2/5)=0.9710所有六個屬性的信息增益為：Gain(S,Sky)=Entropy(S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1=0.97100.6490=0.3220Gain(S,Air - Temp=Entropy(S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1=0.97100.6490=0.3220Gain(S,Humidity )=Entropy(S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)13

22、*log(1/3)=0.97100.9510=0.0200Gain(S,Wind)=Entropy(S)-4/5*(1/4*log(1/4)3/4*log(3/4)1/5*log1=0.97100.6490=0.3220Gain (S, Warm! = Entropy (S)-4/5*(2/4*log(2/4)2/4*log(2/4)1/5*log1 =0.97100.8000=0.1710EntropyGain(S,Forecast)(S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)1/3*log(1/3)=0.97100.9510=0.0200選擇Sky, Air-Temp, Wind中的任何一個作為根節(jié)點的決策屬性即可，這里選擇Sky作為根節(jié)點的決策屬性，建立決策樹如下：R& iny計算下一步的信息增益如下：Entropy (Sunny = -(1/4)log(1/4)(3/4)log(3/4) =0.8113Gain (Sunny Air -Temp = Entropy ( Sunny-(1/4*log(1/4)3/4*log(3/4)=0Gain (Sunny Humidity) = Entropy ( S)-2/4*(1/2*log(1/2)*2)2/4*log1 =0.81130