1 2.5 （题目略）(a). 第一步： S0 G0 第二步： S1 G1 第三步： S2 G2 第四步： S3 G3 ，, 第五步： S4 G4 (b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为：（2*2*2*2 ） *（2*2*2*2 ） = 256 (c). 这个最短序列应该为8，25628如果只有一个训练样例，则假设空间有25628个假设，我们针对每一个属性来设置训练样例，使每次的假设空间减半。则经过8 次训练后，可收敛到单个正确的假设。, , , , , , , , (d). 若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。2.6 完成变型空间表示定理的证明（定理2.1）定理 2.1：变型空间表示定理领 X 为一任意的实例集合，H 为 X 上定义的布尔假设的集合。令 c：X0,1 为 X 上定义的任一目标概念，并令D 为任一训练样例的集合 。对所有的 X，H，c， D 以及良好定义的S 和 G：)()( |shgGgSsHhVSggHD证明：对 VSH ， D 中任一 h：当 h S时，取 sh，则有 hgs 成立当 h S 时，即( h1H）(hgh1) Consistent(h1,D) 若 h1S，显然 hgs 成立；2 否则有( h2H）(h1gh2) Consistent(h2,D) 同样或者h2 S，则 hgh1gs 成立；或者( h3H）(h2gh3) Consistent(h3,D) 如此下去，必存在一个序列hgh1gh2g ghnS 故也有( s S)hgs 同理，对 VSH ， D 中任一 h：当 h G 时，取 gh，则有 ggh 成立当 h G 时，即( h1H）(h1gh) Consistent(h1,D) 若 h1G，显然 ggh 成立；否则有( h2H）(h2gh1) Consistent(h2,D) 同样或者h2 G，则 g=h2gh1gh 成立； 或者( h3H）(h3gh2) Consistent(h3,D) 如此下去，必存在一个序列g=hng gh2gh1gh ，故也有( g G)ggh 2.9 （题目略）对每个属性进行如下操作：令 ai=T，遍历样例集，如果样例全部为正例，则向假设中添加ai=T，否则，令 ai=F，遍历样例集，如果样例全部为正例，则向假设中添加ai=F, 否则，舍弃ai，不向假设中添加ai。时间最大复杂度：2*n* 样例集大小3.2 15.0log5 .05 .0log5.0log)(2212ciiippSEntropy01*621*641)(62)(641)(|)()()(FTvAValuesvvSEntropySEntropySEntropysSSEntropyASGain3.4 假设 u1：EnjoySport=Yes ，u2：EnjoySport=No H(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/4)log(3/4)-(1/4)log(1/4) 对 Sky 假设 v1：Sky=Sunny v2 ：Sky=Rainy H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) = -1*log(1)-(0)*log(0)=0 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(1)*log(1)=0 H(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 使用变型空间算法得到的变型空间为，决策树对应变型空间为 ，显然， 决策树得到的变型空间更一般。树等价于变型空间中的一个或多个成员。假设 u1：EnjoySport=Yes ，u2：EnjoySport=No H(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/5)log(3/5)-(2/5)log(2/5)=0.971 对 Sky 假设 v1： Sky=Sunny v2：Sky=Rainy H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(1)*log(1)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)* 0.811+(1/5)*0=0.6488 I(U, V)=H(U)-H(U|V)=0.971-0.6488=0.3222 对 AirTemp 假设 v1：AirTemp=Warm v2：AirTemp=Cold H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(1)*log(1)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488 I(U, V)=H(U)-H(U|V)=0.971-0.6488=0.3222 对 Humidity 假设 v1：Humidity=Normal v2：Humidity =High H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(2/5)*1+(3/5)*0.918=0.9508 I(U, V)=H(U)-H(U|V)=0.971-0.9508=0.0202 对 Wind 假设 v1： Wind=Strong v2：Wind =Weak H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(0)*log(0)-(1)*log(1)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488 I(U, V)=H(U)-H(U|V)=0.971-0.6488=0.3222 对 Water 假设 v1：Water=Warm v2：Water =Cool H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1)*log(1)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)*1+(1/5)*0=0.8 I(U, V)=H(U)-H(U|V)=0.971-0.8=0.171 对 Forecast假设 v1：Forecast=Same v2：Forecast=Change H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(3/5)*0.918+(2/5)*1=0.9580 I(U, V)=H(U)-H(U|V)=0.971-0.9580=0.013 Sky Yes No Sunny Rainy 4 从而可画出决策树第一步为：对于 Sky=Sunny 选定后H(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/4)log(3/4)-(1/4)log(1/4)=0.811 对 AirTemp 假设 v1：AirTemp=Warm v2：AirTemp=Cold H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/4)*0.811+(0/4)*0=0.811 I(U, V)=H(U)-H(U|V)=0.811-0.811=0 对 Humidity 假设 v1：Humidity=Normal v2：Humidity =High H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1)*log(1)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(1/2)*1+(1/2)*0 =0.5 I(U, V)=H(U)-H(U|V)=0.811-0.5=0.311 对 Wind 假设 v1： Wind=Strong v2：Wind =Weak H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1)*log(1)-(0)*log(0)=0 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(0)*log(0)-(1)*log(1)=0 H(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)=0.811-0=0.811 对 Water 假设 v1：Water=Warm v2：Water =Cool H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2