機(jī)器學(xué)習(xí)-習(xí)題答案

1、12.5（題目略）（題目略）(a).第一步：S0G0第二步：S1G1第三步：S2G2第四步：S3G3，第五步：S4G4(b).假設(shè)中的每個(gè)屬性可以取兩個(gè)值，所以與題目例題一致的假設(shè)數(shù)目為：（2222）（2222）=256(c).這個(gè)最短序列應(yīng)該為8，25628?如果只有一個(gè)訓(xùn)練樣例，則假設(shè)空間有25628?個(gè)假設(shè)，我們針對每一個(gè)屬性來設(shè)置訓(xùn)練樣例，使每次的假設(shè)空間減半。則經(jīng)過8次訓(xùn)練后，可收斂到單個(gè)正確的假設(shè)。(d).若要表達(dá)該實(shí)例語言

2、上的所有概念，那么我們需要擴(kuò)大假設(shè)空間，使得每個(gè)可能的假設(shè)都包括在內(nèi)，這樣假設(shè)空間就遠(yuǎn)遠(yuǎn)大于256，而且這樣沒法得到最終的沒法收斂，因?yàn)閷γ恳粋€(gè)未見過的訓(xùn)練樣例，投票沒有任何效果，因此也就沒有辦法對未見樣例分類。所以不存在一個(gè)最優(yōu)的查詢序列。2.6完成變型空間表示定理的證明（定理完成變型空間表示定理的證明（定理2.1）定理2.1：變型空間表示定理領(lǐng)X為一任意的實(shí)例集合，H為X上定義的布爾假設(shè)的集合。令c：X?01為X上定義的任一目標(biāo)概念

3、，并令D為任一訓(xùn)練樣例的集合。對所有的X，H，c，D以及良好定義的S和G：)()((|shgGgSsHhVSggHD????????證明：對VSH，D中任一h：①當(dāng)h∈S時(shí)，取s＝h，則有h≥gs成立②當(dāng)h?S時(shí)，即(?h1?H）[(hgh1)∧Consistent(h1D)]若h1?S，顯然h≥gs成立；3點(diǎn)，又由于對Sky取兩個(gè)值對應(yīng)的EnjoySpt值都是確定的，因此可畫出決策樹為：SkyYesNoSunnyRainy使用變型空間

4、算法得到的變型空間為，決策樹對應(yīng)變型空間為，顯然，決策樹得到的變型空間更一般。樹等價(jià)于變型空間中的一個(gè)或多個(gè)成員。假設(shè)u1：EnjoySpt=Yes，u2：EnjoySpt=NoH(U)=P(u1)logP(u1)–P(u2)logP(u2)=(35)log(35)(25)log(25)=0.971①對Sky假設(shè)v1：Sky=Sunnyv2：Sky=RainyH(U|v1)=P(u1|v1)logP(u1|v1)P(u2|v1)logP

5、(u2|v1)=(34)log(34)(14)log(14)=0.811H(U|v2)=P(u1|v2)logP(u1|v2)P(u2|v2)logP(u2|v2)=(0)log(0)(1)log(1)=0H(U|V)=P(v1)H(U|v1)P(v2)H(U|v2)=(45)0.811(15)0=0.6488I(UV)=H(U)H(U|V)=0.9710.6488=0.3222②對AirTemp假設(shè)v1：AirTemp=Warmv2：

6、AirTemp=ColdH(U|v1)=P(u1|v1)logP(u1|v1)P(u2|v1)logP(u2|v1)=(34)log(34)(14)log(14)=0.811H(U|v2)=P(u1|v2)logP(u1|v2)P(u2|v2)logP(u2|v2)=(0)log(0)(1)log(1)=0H(U|V)=P(v1)H(U|v1)P(v2)H(U|v2)=(45)0.811(15)0=0.6488I(UV)=H(U)H(U

7、|V)=0.9710.6488=0.3222③對Huity假設(shè)v1：Huity=Nmalv2：Huity=HighH(U|v1)=P(u1|v1)logP(u1|v1)P(u2|v1)logP(u2|v1)=(12)log(12)(12)log(12)=1H(U|v2)=P(u1|v2)logP(u1|v2)P(u2|v2)logP(u2|v2)=(23)log(23)(13)log(13)=0.918H(U|V)=P(v1)H(U|v

8、1)P(v2)H(U|v2)=(25)1(35)0.918=0.9508I(UV)=H(U)H(U|V)=0.9710.9508=0.0202④對Wind假設(shè)v1：Wind=Strongv2：Wind=WeakH(U|v1)=P(u1|v1)logP(u1|v1)P(u2|v1)logP(u2|v1)=(34)log(34)(14)log(14)=0.811H(U|v2)=P(u1|v2)logP(u1|v2)P(u2|v2)logP(

9、u2|v2)=(0)log(0)(1)log(1)=0H(U|V)=P(v1)H(U|v1)P(v2)H(U|v2)=(45)0.811(15)0=0.6488I(UV)=H(U)H(U|V)=0.9710.6488=0.3222⑤對Water假設(shè)v1：Water=Warmv2：Water=CoolH(U|v1)=P(u1|v1)logP(u1|v1)P(u2|v1)logP(u2|v1)=(12)log(12)(12)log(12)=

10、1H(U|v2)=P(u1|v2)logP(u1|v2)P(u2|v2)logP(u2|v2)=(1)log(1)(0)log(0)=0H(U|V)=P(v1)H(U|v1)P(v2)H(U|v2)=(45)1(15)0=0.8I(UV)=H(U)H(U|V)=0.9710.8=0.171⑥對Fecast假設(shè)v1：Fecast=Samev2：Fecast=ChangeH(U|v1)=P(u1|v1)logP(u1|v1)P(u2|v1)