機(jī)器學(xué)習(xí)課后作業(yè)

1、精品文檔機(jī)器學(xué)習(xí)課后作業(yè)學(xué) 院：電子工程學(xué)院專(zhuān) 業(yè)：電子與通信工程姓 名：葉旭慶學(xué) 號(hào)3繼續(xù)考慮EnjoySport學(xué)習(xí)任務(wù)和2.2節(jié)中描述的假設(shè)空間H。如果定義一個(gè)新 的假設(shè)空間H',它包含H中所有假設(shè)的成對(duì)析取。如H'中一假設(shè)為：<?,Cold, High, ?, ?, ?>V<Sunny, ?, High, ?, ?, Sam>試跟蹤運(yùn)行使用該假設(shè)空間 H'的候選消除算法，給定的訓(xùn)練樣例如表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ǐng)看以下的正例和反例序例，它們描述的概念是“兩個(gè)住在同一房間中的人 ”。 每個(gè)訓(xùn)練樣例描述了一個(gè)有序?qū)?，每個(gè)人由其性別、頭發(fā)顏色 ( black , brown或 blonde)、身高(tall , medium； short )以及國(guó)籍(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、 > >考慮在這些實(shí)例上定義的假設(shè)空間為：其中所有假設(shè)以一對(duì)4元組表示，其中每個(gè)值約束與EnjoySport 中的假設(shè)表示相似，可以為：特定值、“?”或者“?”。例如，下面的假設(shè)：< < male ? Tall ? > < female ? ? French> >它表示了所有這樣的有序?qū)Γ旱谝粋€(gè)人為高個(gè)男性(國(guó)籍和發(fā)色任意)，第二個(gè)人為法國(guó)女性(發(fā)色和身高任意)。(a)根據(jù)上述提供的訓(xùn)練樣例和假設(shè)表示，手動(dòng)執(zhí)行候選消除算法。特別是要 寫(xiě)出處理了每一個(gè)訓(xùn)練樣例后變型空間的特殊和一般邊界。(b)計(jì)算給定的假設(shè)空間中有多少假設(shè)與下面的正例一致：+ &l

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

10、夠表達(dá)該實(shí)例語(yǔ)言上的所有概念，那么 ( c) 的答案應(yīng)該如何更改。答： (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è)中的每個(gè)屬性可以取兩個(gè)值，所以與題目例題一致的假設(shè)數(shù)目為：2*2*2*2 ) *( 2*2*2*2 )= 256(c) . 這個(gè)最短序列應(yīng)該為8， 28 256如果只有一個(gè)訓(xùn)練樣例，則假設(shè)空間有

12、28 256個(gè)假設(shè)，我們針對(duì)每一個(gè)屬性來(lái)設(shè)置訓(xùn)練樣例，使每次的假設(shè)空間減半。則經(jīng)過(guò) 8 次訓(xùn)練后，可收斂到單個(gè)正確的假設(shè)。<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) . 若要表達(dá)該實(shí)例語(yǔ)言上的所有概念，那么我們需要擴(kuò)大假設(shè)空間，使得每個(gè)可能的假設(shè)都包括在內(nèi)，這樣假設(shè)空間就遠(yuǎn)遠(yuǎn)大于256，而且這樣沒(méi)法得到最終的沒(méi)法收斂，因?yàn)閷?duì)每一個(gè)未見(jiàn)過(guò)的訓(xùn)練樣例，投票沒(méi)有任何效果，因此也就沒(méi)有辦法對(duì)未見(jiàn)樣例分類(lèi)。所以不存在一個(gè)最優(yōu)的查詢(xún)序列。4歡迎下載 。精品文檔3.2考慮下面的訓(xùn)練樣例集合:實(shí)例分類(lèi)*71門(mén)之1+TTfarTT3-TF4+rF5-FT6-FT(a)請(qǐng)計(jì)算這個(gè)訓(xùn)練樣例集合對(duì)于目標(biāo)函數(shù)分類(lèi)的嫡。 (b)請(qǐng)計(jì)算屬性a2相對(duì)這些訓(xùn)練樣例的信息增益。答：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僅尋找一個(gè)一致的假設(shè)，而候選消除算法尋找所有一致的假設(shè)。 考慮這兩種學(xué)習(xí)算法間的對(duì)應(yīng)關(guān)系。(a)假定給定EnjoySport的四個(gè)訓(xùn)練樣例，畫(huà)出ID3學(xué)習(xí)的決策樹(shù)。其 中EnjoySport目標(biāo)概念列在第2章的表2-1中。(b)學(xué)習(xí)到的決策樹(shù)和從同樣的樣例使用變型空間算法得到的變型空 問(wèn)(見(jiàn)第2章圖2-3)間有什么關(guān)系？樹(shù)等價(jià)于變型空間的一個(gè)成員嗎？(c)增

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

17、，預(yù)計(jì)會(huì)碰 到什么樣的困難？(a)解：要畫(huà)決策樹(shù)，需要計(jì)算每個(gè)候選屬性相對(duì)于整個(gè)樣例集合S的信息增益，然后選擇信息增益最高的一個(gè)屬性作為樹(shù)節(jié)點(diǎn)上第一個(gè)被測(cè)試的屬性。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)學(xué)習(xí)到的決策樹(shù)只包含一個(gè)與訓(xùn)練樣例一致的假設(shè)，使用變型空間算法得到的變型空間包含了所有與訓(xùn)練樣例一致的假設(shè)，但變型空間只含各屬性合 取式的集合，如果目標(biāo)函數(shù)不在假設(shè)空間中

18、，即合取連接詞不能表示最小的子式 時(shí)，變型空間將會(huì)是空的。在本例中，學(xué)習(xí)到的決策樹(shù)Sky = Sunny ”與變型空間中的 G集合中的假設(shè)<Sunny, ?,?,?,?,?> 等價(jià)，Air-Temp= Warm”與G的 v?,Warm,?,?,?,?> 等價(jià)。學(xué)習(xí)到的決策樹(shù)是用變型空間算法得到的變型空間是一種包含關(guān)系，前者是后者的子集或者說(shuō)是后者的一個(gè)元素，(2)在此例子中決策樹(shù)等價(jià)于變型空間的一個(gè)成員，但是一般情況的決策 樹(shù)并不一定等價(jià)于變型空間中的一個(gè)成員，因?yàn)闆Q策樹(shù)的判別有順序，而假設(shè)空間中的元素的各個(gè)性質(zhì)沒(méi)有順序(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顯然第一個(gè)屬性應(yīng)該選擇 Sky AirTemp Wind若第一個(gè)屬性為Sky則：Gain(Ssunny, AirTemp尸 0Gain(Ssunny, Humidity尸 0.3113Gain(Ssunny, Wind尸 0.8113 ( 最大)Gain(Ssunny, Water)= 0.1226Gain(Ssunny, Forecast尸 0.1226若第一個(gè)屬性為AirTemp則

20、：Gain(Swarm, Sky)= 0Gain(Swarm, Humidity)= 0.3113Gain(Swarm, Wind)= 0.8113 ( 最大)Gain(Swarm, Water)= 0.1226Gain(Swarm, Forecast尸 0.1226若第一個(gè)屬性為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所有六個(gè)屬性的信息增益為：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中的任何一個(gè)作為根節(jié)點(diǎn)的決策屬性即可，這里選擇Sky作為根節(jié)點(diǎn)的決策屬性，建立決策樹(shù)如下：R& iny計(jì)算下一步的信息增益如下：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