1 2 .5 （题目略） (a). 第一步：S0 {<(Q Q Q Q ), (Q Q Q Q)>} G0 {<(? ? ? ?), (? ? ? ?)>} 第二步：S1 {<(male brown tall US), (female black short US)> G1 {<(? ? ? ?), (? ? ? ?)>} 第三步：S2 {<(male brown ? ?), (female black short US)> G2 {<(? ? ? ?), (? ? ? ?)>} 第四步：S3 {<(male brown ? ?), (female black short US)> G3 {<(male ? ? ?), (? ? ? ?)>，,} 第五步：S4 {<(male brown ? ?), (female ? short ?)> G4 {<(male ? ? ?), (? ? ? ?)>} (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：X{0,1} 为 X 上定义的任一目标概念，并令D 为任一训练样例的集合{} 。对所有的 X，H，c，D 以及良好定义的 S 和G： })()((|{shgGgSsHhVSggHD 证明：对 VSH，D 中任一 h： ①当h∈S 时，取 s＝h，则有 h≥gs 成立 ②当h S 时，即 (h...
