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

機(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,?,?,?>∨<Sunny,?,High,?,?,Same>試跟蹤運(yùn)行使用該假設(shè)空間H′的候選消除算法，給定的訓(xùn)練樣例如表2-1所示〔需要分步列出S和G集合〕。答：S0=(φ,φ,φ,φ,φ,φ)v(φ,φ,φ,φ,φ,φ)G0=(?,?,?,?,?,?)v(?,?,?,?,?,?)Example1:<Sunny,Warm,Normal,Strong,Warm,Same,Yes>S1=(Sunny,Warm,Normal,Strong,Warm,Same)v(φ,φ,φ,φ,φ,φ)G1=(?,?,?,?,?,?)v(?,?,?,?,?,?)Example2:<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(?,?,?,?,?,?)Example3:<Rainy,Cold,High,Strong,Warm,Change,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,?,?,?,?)v(?,?,?,?,?,Same)}2Example4:<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(φ,φ,φ,φ,φ,φ)，(Sunny,Warm,？,Strong,Warm,Same)v(Sunny,Warm,High,Strong,Cool,Change)}G4={(Sunny,?,?,?,?,?)v(?,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〕。+<<malebrowntallUS>,<femaleblackshortUS>>+<<malebrownshortFrench>,<femaleblackshortUS>>-<<femalebrowntallGerman>,<femaleblackshortIndian>>+<<malebrowntallIrish>,<femalebrownshortIrish>>考慮在這些實(shí)例上定義的假設(shè)空間為：其中所有假設(shè)以一對(duì)4元組表示，其中每個(gè)值約束與EnjoySport中的假設(shè)表示相似，可以為：特定值、“?”或者“?”。例如，下面的假設(shè)：<<male?Tall?><female??French>>它表示了所有這樣的有序?qū)Γ旱谝粋€(gè)人為高個(gè)男性〔國(guó)籍和發(fā)色任意〕，第二個(gè)人為法國(guó)女性〔發(fā)色和身高任意〕?！瞐〕根據(jù)上述提供的訓(xùn)練樣例和假設(shè)表示，手動(dòng)執(zhí)行候選消除算法。特別是要寫(xiě)出處理了每一個(gè)訓(xùn)練樣例后變型空間的特殊和一般邊界?！瞓〕計(jì)算給定的假設(shè)空間中有多少假設(shè)與下面的正例一致：+<<maleblackshortPortuguese><femaleblondetallIndian>>〔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ǔ)言，使其能夠表達(dá)該實(shí)例語(yǔ)言上的所有概念，那么〔c〕的答案應(yīng)該如何更改。答：(a).第一步：S0{<(QQQQ),(QQQQ)>} G0{<(????),(????)>}第二步：S1{<(malebrowntallUS),(femaleblackshortUS)> G1{<(????),(????)>}第三步：S2{<(malebrown??),(femaleblackshortUS)> G2{<(????),(????)>}第四步：S3{<(malebrown??),(femaleblackshortUS)> G3{<(male???),(????)>，<????>,<???US>}第五步：S4{<(malebrown??),(female?short?)> G4{<(male???),(????)>}(b).假設(shè)中的每個(gè)屬性可以取兩個(gè)值，所以與題目例題一致的假設(shè)數(shù)目為：〔2*2*2*2〕*〔2*2*2*2〕=256(c).這個(gè)最短序列應(yīng)該為8，如果只有一個(gè)訓(xùn)練樣例，那么假設(shè)空間有個(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>,<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,US>(d).假設(shè)要表達(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)序列。3.2考慮下面的訓(xùn)練樣例集合：請(qǐng)計(jì)算這個(gè)訓(xùn)練樣例集合對(duì)于目標(biāo)函數(shù)分類(lèi)的熵。請(qǐng)計(jì)算屬性a2相對(duì)這些訓(xùn)練樣例的信息增益。答：3.4ID3僅尋找一個(gè)一致的假設(shè)，而候選消除算法尋找所有一致的假設(shè)。考慮這兩種學(xué)習(xí)算法間的對(duì)應(yīng)關(guān)系?！瞐〕假定給定EnjoySport的四個(gè)訓(xùn)練樣例，畫(huà)出ID3學(xué)習(xí)的決策樹(shù)。其中EnjoySport目標(biāo)概念列在第2章的表2-1中?！瞓〕學(xué)習(xí)到的決策樹(shù)和從同樣的樣例使用變型空間算法得到的變型空間〔見(jiàn)第2章圖2-3〕間有什么關(guān)系？樹(shù)等價(jià)于變型空間的一個(gè)成員嗎？〔c〕增加下面的訓(xùn)練樣例，計(jì)算新的決策樹(shù)。這一次，顯示出增長(zhǎng)樹(shù)的每一步中每個(gè)候選屬性的信息增益?！瞕〕假定我們希望設(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ù)，而G必須包含最一般的。說(shuō)明遇到第二個(gè)訓(xùn)練樣例時(shí)S和G集合是如何被改良的〔可以去掉描述同一個(gè)概念的語(yǔ)法不同的樹(shù)〕。在把候選消除算法應(yīng)用到?jīng)Q策樹(shù)假設(shè)空間時(shí)，預(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è)空間中，即合取連接詞不能表示最小的子式時(shí)，變型空間將會(huì)是空的。在本例中，學(xué)習(xí)到的決策樹(shù)“Sky=Sunny”與變型空間中的G集合中的假設(shè)<Sunny,?,?,?,?,?>等價(jià)，“Air-Temp=Warm”與G中的<?,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,AirTemp)=0.3219Gain(S,Humidity)=0.0200Gain(S,Wind)=0.3219Gain(S,Water)=0.1710Gain(S,Forecast)=0.0200顯然第一個(gè)屬性應(yīng)該選擇SkyAirTempWind假設(shè)第一個(gè)屬性為Sky那么：Gain(Ssunny,AirTemp)=0Gain(Ssunny,Humidity)=0.3113Gain(Ssunny,Wind)=0.8113(最大)Gain(Ssunny,Water)=0.1226Gain(Ssunny,Forecast)=0.1226假設(shè)第一個(gè)屬性為AirTemp那么：Gain(Swarm,Sky)=0Gain(Swarm,Humidity)=0.3113Gain(Swarm,Wind)=0.8113(最大)Gain(Swarm,Water)=0.1226Gain(Swarm,Forecast)=0.1226假設(shè)第一個(gè)屬性為Wind那么：Gain(Sstrony,Sky)=0.8113(最大)Gain(Sstrony,AirTemp)=0.8113(最大)Gain(Sstrony,Humidity)=0.1226Gain(Sstrony,Water)=0.1226Gain(Sstrony,Forecast)=0.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.9710—0.6490=0.3220Gain(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.3220Gain(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.0200Gain(S,Wind)=Entropy(S)-4/5*(1/4*log(1/4)3/4*log(3/4))1/5*log1=0.9710—0.6490=0.3220Gain(S,Warm)=Entropy(S)-4/5*(2/4*log(2/4)2/4*log(2/4))1/5*log1=0.9710—0.8000=0.1710Gain(S,Forecast)=Entropy(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中的任何一個(gè)作為根節(jié)點(diǎn)的決策屬性即可，這里選擇Sky作為根節(jié)點(diǎn)的決策屬性，建立決策樹(shù)如下：計(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.8113—0.5000=0.3113Gain(Sunny,Wind)=Entropy(S)-3/4*log1-1/4*log1=0.8113Gain(Sunny,W