机器学习-习题答案.pdfVIP

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 ? ? ?), (? ? ? ?) ，? ? ? ?,? ? ? US} 第五步： S4 {(male brown ? ?), (female ? short ?) G4 {(male ? ? ?), (? ? ? ?)} (b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为： （2*2*2*2 ）* （2*2*2*2 ） = 256 8 (c). 这个最短序列应该为 8， 2 256 8 如果只有一个训练样例，则假设空间有 2 256 个假设，我们针对每一个属性来设置训练 样例，使每次的假设空间减半。则经过 8 次训练后，可收敛到单个正确的假设。 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). 若要表达该实例语言上的所有概念， 那么我们需要扩大假设空间， 使得每个可能的假设 都包括在内，这样假设空间就远远大于 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 ： VSHD { h H | ( s S)( g G)(g g h g s} 证明：对 VSH ， D 中任一 h ： ①当 h ∈S 时，取 s＝h，则有 h≥gs 成立 ②当 h S 时，即 ( h1 H ）[(hgh1) ∧Consistent(h1,D)] 若 h1 S，显然 h ≥gs 成立；