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

機(jī)器學(xué)習(xí)課后作業(yè)學(xué)院：電子工程學(xué)院專業(yè)：電子與通信工程姓名：葉旭慶學(xué)號3繼續(xù)考慮EnjoySport學(xué)習(xí)任務(wù)和2.2節(jié)中描述的假設(shè)空間H。如果定義一個新的假設(shè)空間H′，它包含H中所有假設(shè)的成對析取。如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請看以下的正例和反例序例，它們描述的概念是“兩個住在同一房間中的人”。每個訓(xùn)練樣例描述了一個有序?qū)?，每個人由其性別、頭發(fā)顏色〔black,brown或blonde〕、身高〔tall,medium或short〕以及國籍〔US,French,German,Irish,Indian,Chinese或Portuguese〕。+<<malebrowntallUS>,<femaleblackshortUS>>+<<malebrownshortFrench>,<femaleblackshortUS>>-<<femalebrowntallGerman>,<femaleblackshortIndian>>+<<malebrowntallIrish>,<femalebrownshortIrish>>考慮在這些實例上定義的假設(shè)空間為：其中所有假設(shè)以一對4元組表示，其中每個值約束與EnjoySport中的假設(shè)表示相似，可以為：特定值、“?”或者“?”。例如，下面的假設(shè)：<<male?Tall?><female??French>>它表示了所有這樣的有序?qū)Γ旱谝粋€人為高個男性〔國籍和發(fā)色任意〕，第二個人為法國女性〔發(fā)色和身高任意〕。〔a〕根據(jù)上述提供的訓(xùn)練樣例和假設(shè)表示，手動執(zhí)行候選消除算法。特別是要寫出處理了每一個訓(xùn)練樣例后變型空間的特殊和一般邊界?！瞓〕計算給定的假設(shè)空間中有多少假設(shè)與下面的正例一致：+<<maleblackshortPortuguese><femaleblondetallIndian>>〔c〕如果學(xué)習(xí)器只有一個訓(xùn)練樣例如〔b〕中所示，現(xiàn)在由學(xué)習(xí)器提出查詢，并由施教者給出其分類。求出一個特定的查詢序列，以保證學(xué)習(xí)器收斂到單個正確的假設(shè)，而不管該假設(shè)是哪一個〔假定目標(biāo)概念可以使用給定的假設(shè)表示語言來描述〕。求出最短的查詢序列。這一序列的長度與問題〔b〕的答案有什么關(guān)聯(lián)？〔d〕注意到這里的假設(shè)表示語言不能夠表示這些實例上的所有概念〔如我們可定義出一系列的正例和反例，它們并沒有相應(yīng)的可描述假設(shè)〕。如果要擴(kuò)展這一語言，使其能夠表達(dá)該實例語言上的所有概念，那么〔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è)中的每個屬性可以取兩個值，所以與題目例題一致的假設(shè)數(shù)目為：〔2*2*2*2〕*〔2*2*2*2〕=256(c).這個最短序列應(yīng)該為8，如果只有一個訓(xùn)練樣例，那么假設(shè)空間有個假設(shè)，我們針對每一個屬性來設(shè)置訓(xùn)練樣例，使每次的假設(shè)空間減半。那么經(jīng)過8次訓(xùn)練后，可收斂到單個正確的假設(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á)該實例語言上的所有概念，那么我們需要擴(kuò)大假設(shè)空間，使得每個可能的假設(shè)都包括在內(nèi)，這樣假設(shè)空間就遠(yuǎn)遠(yuǎn)大于256，而且這樣沒法得到最終的沒法收斂，因為對每一個未見過的訓(xùn)練樣例，投票沒有任何效果，因此也就沒有方法對未見樣例分類。所以不存在一個最優(yōu)的查詢序列。3.2考慮下面的訓(xùn)練樣例集合：請計算這個訓(xùn)練樣例集合對于目標(biāo)函數(shù)分類的熵。請計算屬性a2相對這些訓(xùn)練樣例的信息增益。答：3.4ID3僅尋找一個一致的假設(shè)，而候選消除算法尋找所有一致的假設(shè)?？紤]這兩種學(xué)習(xí)算法間的對應(yīng)關(guān)系?！瞐〕假定給定EnjoySport的四個訓(xùn)練樣例，畫出ID3學(xué)習(xí)的決策樹。其中EnjoySport目標(biāo)概念列在第2章的表2-1中。〔b〕學(xué)習(xí)到的決策樹和從同樣的樣例使用變型空間算法得到的變型空間〔見第2章圖2-3〕間有什么關(guān)系？樹等價于變型空間的一個成員嗎？〔c〕增加下面的訓(xùn)練樣例，計算新的決策樹。這一次，顯示出增長樹的每一步中每個候選屬性的信息增益。〔d〕假定我們希望設(shè)計一個學(xué)習(xí)器，它搜索決策樹假設(shè)空間〔類似ID3〕并尋找與數(shù)據(jù)一致的所有假設(shè)〔類似候選消除〕。簡單地說，我們希望應(yīng)用候選消除算法搜索決策樹假設(shè)空間。寫出經(jīng)過表2-1的第一個訓(xùn)練樣例后的S和G集合。注意S必須包含與數(shù)據(jù)一致的最特殊的決策樹，而G必須包含最一般的。說明遇到第二個訓(xùn)練樣例時S和G集合是如何被改良的〔可以去掉描述同一個概念的語法不同的樹〕。在把候選消除算法應(yīng)用到?jīng)Q策樹假設(shè)空間時，預(yù)計會碰到什么樣的困難？答：〔a〕解：要畫決策樹，需要計算每個候選屬性相對于整個樣例集合S的信息增益，然后選擇信息增益最高的一個屬性作為樹節(jié)點(diǎn)上第一個被測試的屬性。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í)到的決策樹只包含一個與訓(xùn)練樣例一致的假設(shè)，使用變型空間算法得到的變型空間包含了所有與訓(xùn)練樣例一致的假設(shè)，但變型空間只含各屬性合取式的集合，如果目標(biāo)函數(shù)不在假設(shè)空間中，即合取連接詞不能表示最小的子式時，變型空間將會是空的。在本例中，學(xué)習(xí)到的決策樹“Sky=Sunny”與變型空間中的G集合中的假設(shè)<Sunny,?,?,?,?,?>等價，“Air-Temp=Warm”與G中的<?,Warm,?,?,?,?>等價。學(xué)習(xí)到的決策樹是用變型空間算法得到的變型空間是一種包含關(guān)系，前者是后者的子集或者說是后者的一個元素，〔2〕在此例子中決策樹等價于變型空間的一個成員，但是一般情況的決策樹并不一定等價于變型空間中的一個成員，因為決策樹的判別有順序，而假設(shè)空間中的元素的各個性質(zhì)沒有順序(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顯然第一個屬性應(yīng)該選擇SkyAirTempWind假設(shè)第一個屬性為Sky那么：Gain(Ssunny,AirTemp)=0Gain(Ssunny,Humidity)=0.3113Gain(Ssunny,Wind)=0.8113(最大)Gain(Ssunny,Water)=0.1226Gain(Ssunny,Forecast)=0.1226假設(shè)第一個屬性為AirTemp那么：Gain(Swarm,Sky)=0Gain(Swarm,Humidity)=0.3113Gain(Swarm,Wind)=0.8113(最大)Gain(Swarm,Water)=0.1226Gain(Swarm,Forecast)=0.1226假設(shè)第一個屬性為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所有六個屬性的信息增益為：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中的任何一個作為根節(jié)點(diǎn)的決策屬性即可，這里選擇Sky作為根節(jié)點(diǎn)的決策屬性，建立決策樹如下：計算下一步的信息增益如下：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