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

1、%機(jī)器學(xué)習(xí)課后作業(yè)院:電子工程學(xué)院電子與通信工程葉旭3繼續(xù)考慮Enjoys port學(xué)習(xí)任務(wù)和2.2節(jié)中描述的假設(shè)空間H。如果定義一個新 的假設(shè)空間H',它包含H中所有假設(shè)的成對析取。女口 H中一假設(shè)為：Same>2-1 所示<?,Cold, High, ?, ?, ?> V<Sunny ?,High, ?, ?,試跟蹤運行使用該假設(shè)空間 H'的候選消除算法，給定的訓(xùn)練樣例如表 （需要分步列出S和G集合）。答：S0= ( © , © , © , © , © , © )

2、v ( © , © , © , © , © , ©)G0 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 1: <Sunny, Warm, Normal, Strong, Warm, Same, Yes> S1=(Sunny, Warm, Normal, Strong, Warm, Same) v ( G1 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)J/ IJ ) ) )/*，/©,©,©,©,

3、©,©)Example 2: <Sunny, Warm, High, Strong, Warm, Same, Yes> S2= (Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Warm, Same) ， (Sunny, Warm, ？, Strong, Warm, Same) v ( G2 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 3: <Rainy, Cold, High, Strong, Warm, C

4、hange, No>S3=(Sunny, Warm,Normal, Strong, Warm , Same)v (Sunny, Warm,High, Strong, Warm, Same)，©,©,©,©,©,©)(Sunny, Warm, ？, Strong, Warm, Same) v (G3 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?), (Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?,

5、?) v (?, ?, ?, ?, ?, Same) 2Example 4: <Sunny, Warm, High, Strong, Cool, Change, Yes>S4= (Sunny, Warm, ?, Strong, ?, ?) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, ?, ?) ，(Sunny, Warm, ？, Strong, ？, ？) v ( © , © ,

6、© , © , © , © ) ，(Sunny, Warm, ？ , Strong, Warm , Same)v (Sunny, Warm,High, Strong, Cool, Change)G4 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?), (Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2.5 請看以下的正例和反例序例，它們描述的概念是 “兩個住在同一房間中的

7、 人”。每個訓(xùn)練樣例描述了一個有序?qū)Γ?每個人由其性別、 頭發(fā)顏色（ black, brown 或bionde）、身高（tall, medium或short）以及國籍（US, French. German, Irish ,In dia n, Chin ese或 P ortuguese）。+ < <male brown tall US>, <female black short US> >+ < <male brown short French>, <female black short US> >- < <fe

8、male brown tall German>, <female black short Indian > >+ < <male brown tall Irish >, <female brown short Irish > >考慮在這些實例上定義的假設(shè)空間為：其中所有假設(shè)以一對4元組表示，其中每個值約束與 EnjoySport 中的假設(shè)表示相似，可以為：特定值、“?”或者“?”。例如，下面的假設(shè)：< <male ? Tall ? > <female ? ? French> > 它表示了所有這樣的有

9、序?qū)Γ旱谝粋€人為高個男性（國籍和發(fā)色任意），第二 個人為法國女性（發(fā)色和身高任意）。（a）根據(jù)上述提供的訓(xùn)練樣例和假設(shè)表示，手動執(zhí)行候選消除算法。特別是要 寫出處理了每一個訓(xùn)練樣例后變型空間的特殊和一般邊界。（b）計算給定的假設(shè)空間中有多少假設(shè)與下面的正例一致：+ < <male black short Portuguese> <female blonde tall Indian> >（C）如果學(xué)習(xí)器只有一個訓(xùn)練樣例如（b）中所示，現(xiàn)在由學(xué)習(xí)器提出查詢，并由施教者給出其分類。求出一個特定的查詢序列，以保證學(xué)習(xí)器收斂到單個正確的假設(shè)，而不論該假設(shè)是哪一個（假定

10、目標(biāo)概念可以使用給定的假設(shè)表示語言來描述）。求出最短的查詢序列。這一序列的長度與問題（b）的答案有什么關(guān)聯(lián)？（d）注意到這里的假設(shè)表示語言不能夠表示這些實例上的所有概念（如我們可 定義出一系列的正例和反例，它們并沒有相應(yīng)的可描述假設(shè)） 。如果要擴(kuò)展這一 語言，使其能夠表達(dá)該實例語言上的所有概念，那么（C）的答案應(yīng)該如何更改。答： (a). 第一步： S0 <(Q Q Q Q ), (Q Q Q Q)>G0 <(? ? ? ?), (? ? ? ?)>51 <(male brown tall US), (female black short US)>G1 &l

11、t;(? ? ? ?), (? ? ? ?)>52 <(male brown ? ?), (female black short US)>G2 <(? ? ? ?), (? ? ? ?)>53 <(male brown ? ?), (female black short US)>G3 <(male ? ? ?), (? ? ? ?，)><? ? ? ?>,<? ? ? US>54 <(male brown ? ?), (female ? short ?)>G4 <(male ? ? ?), (? ?

12、 ? ?)>第二步：第三步：第四步：第五步：(b) .假設(shè)中的每個屬性可以取兩個值，所以與題目例題一致的假設(shè)數(shù)目為:( 2*2*2*2 ) * ( 2*2*2*2 ) = 2568(c) . 這個最短序列應(yīng)該為 8， 282568如果只有一個訓(xùn)練樣例，則假設(shè)空間有 28 256 個假設(shè)，我們針對每一個屬性來 設(shè)置訓(xùn)練樣例， 使每次的假設(shè)空間減半。 則經(jīng)過 8 次訓(xùn)練后，可收斂到單個正確 的假設(shè)。<female,blanck,short,Portuguese>,<female,blonde,tall,Indian> <male,brown,short,Port

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

14、,tall,Indian> <male,blanck,short,Portuguese>,<female,blonde,short,Indian> <male,blanck,short,Portuguese>,<female,blonde,tall,US>(d) . 若要表達(dá)該實例語言上的所有概念， 那么我們需要擴(kuò)大假設(shè)空間， 使得每個 可能的假設(shè)都包括在內(nèi)，這樣假設(shè)空間就遠(yuǎn)遠(yuǎn)大于 256，而且這樣沒法得到最終 的沒法收斂， 因為對每一個未見過的訓(xùn)練樣例， 投票沒有任何效果， 因此也就沒 有辦法對未見樣例分類。所以不存在一個最優(yōu)的查詢序列。

15、3.2考慮下面的訓(xùn)練樣例集合:分類和1g1+TTr4+TT5-TF4+rrqk-FT6FT請計算這個訓(xùn)練樣例集合對于目標(biāo)函數(shù)分類的熵。 請計算屬性a2相對這些訓(xùn)練樣例的信息增益。答:Entropy (S)Pi log 2 Pii 10.5log2 0.5 0.5log2 0.51Gai n(S A)Entrop y(S)v Values(A) | S |Entropy(Sv)1 46 Entropy(ST)% Entropy®1 46*1 %*1 03.4 ID3僅尋找一個一致的假設(shè)，而候選消除算法尋找所有一致的假設(shè)。 考慮這兩種學(xué)習(xí)算法間的對應(yīng)關(guān)系。（a）假定給定EnjoySpor

16、t的四個訓(xùn)練樣例，畫出ID3學(xué)習(xí)的決策樹。其 中EnjoySport目標(biāo)概念列在第2章的表2-1中。（b ）學(xué)習(xí)到的決策樹和從同樣的樣例使用變型空間算法得到的變型空 間（見第2章圖2-3）間有什么關(guān)系？樹等價于變型空間的一個成員嗎？（C）增加下面的訓(xùn)練樣例，計算新的決策樹。這一次，顯示出增長樹的 每一步中每個候選屬性的信息增益。1rriirijjHivrA（d）假定我們希望設(shè)計一個學(xué)習(xí)器，它搜索決策樹假設(shè)空間（類似 ID3） 并尋找與數(shù)據(jù)一致的所有假設(shè)（類似候選消除）。簡單地說，我們希望應(yīng)用候 選消除算法搜索決策樹假設(shè)空間。寫出經(jīng)過表 2-1的第一個訓(xùn)練樣例后的S和G 集合。注意S必須包含與數(shù)

17、據(jù)一致的最特殊的決策樹， 而G必須包含最一般的。 說明遇到第二個訓(xùn)練樣例時S和 G集合是如何被改進(jìn)的（可以去掉描述同一個 概念的語法不同的樹）。在把候選消除算法應(yīng)用到?jīng)Q策樹假設(shè)空間時，預(yù)計會 碰到什么樣的困難？答:（a）解：要畫決策樹，需要計算每個候選屬性相對于整個樣例集合S的信息增益，然后選擇信息增益最高的一個屬性作為樹節(jié)點上第一個被測試的屬性。Gai n（S, Sky）= 0.8113Gai n（S, AirTem p）= 0.8113Gai n（S, Humidity）= 0.1226Gai n（S, Win d）=0Gai n（S, Water）= 0.1226Gai n（S, For

18、ecast）= 0.3113（b）（ 1）學(xué)習(xí)到的決策樹只包含一個與訓(xùn)練樣例一致的假設(shè)，使用變型空間算法得到的變型空間包含了所有與訓(xùn)練樣例一致的假設(shè)，但變型空間只含各屬性合 取式的集合，如果目標(biāo)函數(shù)不在假設(shè)空間中，即合取連接詞不能表示最小的子式 時，變型空間將會是空的。在本例中，學(xué)習(xí)到的決策樹Sky = Sunny ”與變型空間中的 G集合中的假設(shè)vSunny, ?,?,?,?,?> 等價，Air-Temp= Warm”與G中的v?,Warm?> 等價。學(xué)習(xí)到的決策樹是用變型空間算法得到的變型空間是一種包含關(guān)系，前者 是后者的子集或者說是后者的一個元素，（2）在此例子中決策樹等價于

19、變型空間的一個成員，但是一般情況的決策 樹并不一定等價于變型空間中的一個成員，因為決策樹的判別有順序，而假設(shè)空間中的元素的各個性質(zhì)沒有順序（C）Gai n(S, Sky)= 0.3219Gai n(S, AirTem p)= 0.3219Gai n(S, Humidity)= 0.0200Gai n(S, Win d)= 0.3219Gai n(S, Water)= 0.1710Gai n(S, Forecast)= 0.0200顯然第一個屬性應(yīng)該選擇 Sky AirTe mp Wind 若第一個屬性為Sky貝U：Gain(Ssunny, AirTe mp )= 0Gai n(Ssu nny,

20、 Humidity)= 0.3113Gai n(Ssu nny, Wind)= 0.8113 (最大)Gai n(Ssu nny, Water)= 0.1226Gai n(Ssu nny, Forecast)= 0.1226若第一個屬性為AirTemp貝U：Gai n(Swarm, Sky)= 0Gai n(Swarm, Humidity)= 0.3113Ga in (Swarm, Win d)= 0.8113 ( 最大)Gai n(Swarm, Water)= 0.1226Gai n(Swarm, Forecast)= 0.1226若第一個屬性為Wind貝U：最大）最大）Gai n(Sstr

21、o ny, Sky)= 0.8113 (Gain (Sstro ny, AirTem p)= 0.8113 (Gai n(Sstro ny, Humidity)= 0.1226Gai n(Sstro ny, Water)= 0.1226Gain (Sstro ny, Forecast)= 0.3113Entropy (S) = -(3/5)log(3/5)(2/5)log(2/5)=0.9710所有六個屬性的信息增益為：Ga in (S, Sky) = Entropy (S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1=0.9710 0.6490=0.3220

22、Ga in (S Air-Temp)= Entropy (S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1 =0.9710 0.6490=0.3220Ga in(S, Humidity) = Entropy (S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)13*log(1/3) =0.9710 0.9510=0.0200Gai n (S, Wind) = Entropy (S)-4/5*(1/4*log(1/4)3/4*log(3/4)1/5*log1=0.9710 0.6490=0.3220Gai n (S, Warm) =

23、 Entropy (S)-4/5*(2/4*log(2/4)2/4*log(2/4)1/5*log1=0.9710 0.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.9710 0.9510=0.0200選擇Sky, Air-Temp , Wind中的任何一個作為根節(jié)點的決策屬性即可，這里選擇Sky作為根節(jié)點的決策屬性，建立決策樹如下：計算下一步的信息增益如下：Entropy (Su nny) =-(1/4)log(1/4)(3/4)log(3/4) =0.8113Gai n (Su nny Air-Temp) = Entropy (Su nn y)-(1/4*log(1/4)3/4*log(3/4) =0Gai n (Su nny Humidity) = Entropy (S)-2/4*(1/2*log(1/2)*2)2/4*log1=0.8113 0.5000=0