机器学习-习题答案

12.5（题目略）(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).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为：（2*2*2*2）*（2*2*2*2）=256(c).这个最短序列应该为8，25628如果只有一个训练样例，则假设空间有25628个假设，我们针对每一个属性来设置训练样例，使每次的假设空间减半。则经过8次训练后，可收敛到单个正确的假设。female,blanck,short,Portuguese,female,blonde,tall,Indianmale,brown,short,Portuguese,female,blonde,tall,Indianmale,blanck,tall,Portuguese,female,blonde,tall,Indianmale,blanck,short,US,female,blonde,tall,Indianmale,blanck,short,Portuguese,male,blonde,tall,Indianmale,blanck,short,Portuguese,female,black,tall,Indianmale,blanck,short,Portuguese,female,blonde,short,Indianmale,blanck,short,Portuguese,female,blonde,tall,US(d).若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。2.6完成变型空间表示定理的证明（定理2.1）定理2.1：变型空间表示定理领X为一任意的实例集合，H为X上定义的布尔假设的集合。令c：X{0,1}为X上定义的任一目标概念，并令D为任一训练样例的集合{x,c(x)}。对所有的X，H，c，D以及良好定义的S和G：})()((|{shgGgSsHhVSggHD证明：对VSH，D中任一h：①当h∈S时，取s＝h，则有h≥gs成立②当hS时，即(h1H）[(hgh1)∧Consistent(h1,D)]若h1S，显然h≥gs成立；2否则有(h2H）[(h1gh2)∧Consistent(h2,D)]同样或者h2S，则hgh1≥gs成立；或者(h3H）[(h2gh3)∧Consistent(h3,D)]如此下去，必存在一个序列hgh1gh2g…ghnS故也有(sS)h≥gs同理，对VSH，D中任一h：①当hG时，取g＝h，则有g≥gh成立②当hG时，即(h1H）[(h1gh)∧Consistent(h1,D)]若h1G，显然g≥gh成立；否则有(h2H）[(h2gh1)∧Consistent(h2,D)]同样或者h2G，则g=h2gh1≥gh成立；或者(h3H）[(h3gh2)∧Consistent(h3,D)]如此下去，必存在一个序列g=hng…gh2gh1gh，故也有(gG)g≥gh2.9（题目略）对每个属性进行如下操作：令ai=T，遍历样例集，如果样例全部为正例，则向假设中添加ai=T，否则，令ai=F，遍历样例集，如果样例全部为正例，则向假设中添加ai=F,否则，舍弃ai，不向假设中添加ai。时间最大复杂度：2*n*样例集大小3.215.0log5.05.0log5.0log)(2212ciiippSEntropy01*621*641)(62)(641)(||||)()()(FTvAValuesvvSEntropySEntropySEntropysSSEntropyASGain3.4假设u1：EnjoySport=Yes，u2：EnjoySport=NoH(U)=-P(u1)logP(u1)–P(u2)logP(u2)=-(3/4)log(3/4)-(1/4)log(1/4)对Sky假设v1：Sky=Sunnyv2：Sky=RainyH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-1*log(1)-(0)*log(0)=0H(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)=(3/4)*0+(1/4)*0=0所以I(U,V)=H(U)-H(U|V)=H(U)此时显然信息增益最大，所以Sky作为决策树根节点，又由于对Sky取两个值对应的EnjoySport值都是确定的，因此可画出决策树为：3使用变型空间算法得到的变型空间为sunny,warm,?,srtong,?,?，决策树对应变型空间为sunny,?,?,?,?,?，显然，决策树得到的变型空间更一般。树等价于变型空间中的一个或多个成员。假设u1：EnjoySport=Yes，u2：EnjoySport=NoH(U)=-P(u1)logP(u1)–P(u2)logP(u2)=-(3/5)log(3/5)-(2/5)log(2/5)=0.971①对Sky假设v1：Sky=Sunnyv2：Sky=RainyH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=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)=(4/5)*0.811+(1/5)*0=0.6488I(U,V)=H(U)-H(U|V)=0.971-0.6488=0.3222②对AirTemp假设v1：AirTemp=Warmv2：AirTemp=ColdH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=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)=(4/5)*0.811+(1/5)*0=0.6488I(U,V)=H(U)-H(U|V)=0.971-0.6488=0.3222③对Humidity假设v1：Humidity=Normalv2：Humidity=HighH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(1/2)*log(1/2)-(1/2)*log(1/2)=1H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(2/5)*1+(3/5)*0.918=0.9508I(U,V)=H(U)-H(U|V)=0.971-0.9508=0.0202④对Wind假设v1：Wind=Strongv2：Wind=WeakH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=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)=(4/5)*0.811+(1/5)*0=0.6488I(U,V)=H(U)-H(U|V)=0.971-0.6488=0.3222⑤对Water假设v1：Water=Warmv2：Water=CoolH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(1/2)*log(1/2)-(1/2)*log(1/2)=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)=(4/5)*1+(1/5)*0=0.8I(U,V)=H(U)-H(U|V)=0.971-0.8=0.171⑥对Forecast假设v1：Forecast=Samev2：Forecast=ChangeH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(1/2)*log(1/2)-(1/2)*log(1/2)=1H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(3/5)*0.918+(2/5)*1=0.9580I(U,V)=H(U)-H(U|V)=0.971-0.9580=0.013SkyYesNoSunnyRainy4从而可画出决策树第一步为：对于Sky=Sunny选定后H(U)=-P(u1)logP(u1)–P(u2)logP(u2)=-(3/4)log(3/4)-(1/4)log(1/4)=0.811①对AirTemp假设v1：AirTemp=Warmv2：AirTemp=ColdH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(0)*log(0)=0H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(4/4)*0.811+(0/4)*0=0.811I(U,V)=H(U)-H(U|V)=0.811-0.811=0②对Humidity假设v1：Humidity=Normalv2：Humidity=HighH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(1/2)*log(1/2)-(1/2)*log(1/2)=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)=(1/2)*1+(1/2)*0=