1.1 求版本空间 先看书中示例 版本空间： 从假设空间删除掉与正例不一致和与反例一致的假设后，剩余的假设所组成的集合。它可以看成是对正例的最大泛化。 表1.1的训练数据集对应的假设空间应该如下： 1 色泽＝＊，根蒂＝＊，敲声＝＊ 2 色泽＝青绿，根蒂＝＊，敲声＝＊ 3 色泽＝乌黑，根蒂＝＊，敲声＝＊ 4 色泽＝＊，根蒂＝蜷缩，敲声＝＊ 5 色泽＝＊，根蒂＝硬挺，敲声＝＊ 6 色泽＝＊，根蒂＝稍蜷，敲声＝＊ 7 色泽＝＊，根蒂＝＊，敲声＝浊响 8 色泽＝＊，根蒂＝＊，敲声＝清脆 9 色泽＝＊，根蒂＝＊，敲声＝沉闷 10 色泽＝青绿，根蒂＝蜷缩，敲声＝＊ 11 色泽＝青绿，根蒂＝硬挺，敲声＝＊ 12 色泽＝青绿，根蒂＝稍蜷，敲声＝＊ 13 色泽＝乌黑，根蒂＝蜷缩，敲声＝＊ 14 色泽＝乌黑，根蒂＝硬挺，敲声＝＊ 15 色泽＝乌黑，根蒂＝稍蜷，敲声＝＊ 16 色泽＝青绿，根蒂＝＊，敲声＝浊响 17 色泽＝青绿，根蒂＝＊，敲声＝清脆 18 色泽＝青绿，根蒂＝＊，敲声＝沉闷 19 色泽＝乌黑，根蒂＝＊，敲声＝浊响 20 色泽＝乌黑，根蒂＝＊，敲声＝清脆 21 色泽＝乌黑，根蒂＝＊，敲声＝沉闷 22 色泽＝＊，根蒂＝蜷缩，敲声＝浊响 23 色泽＝＊，根蒂＝蜷缩，敲声＝清脆 24 色泽＝＊，根蒂＝蜷缩，敲声＝沉闷 25 色泽＝＊，根蒂＝硬挺，敲声＝浊响 26 色泽＝＊，根蒂＝硬挺，敲声＝清脆 27 色泽＝＊，根蒂＝硬挺，敲声＝沉闷 28 色泽＝＊，根蒂＝稍蜷，敲声＝浊响 29 色泽＝＊，根蒂＝稍蜷，敲声＝清脆 30 色泽＝＊，根蒂＝稍蜷，敲声＝沉闷 31 色泽＝青绿，根蒂＝蜷缩，敲声＝浊响 32 色泽＝青绿，根蒂＝蜷缩，敲声＝清脆 33 色泽＝青绿，根蒂＝蜷缩，敲声＝沉闷 34 色泽＝青绿，根蒂＝硬挺，敲声＝浊响 35 色泽＝青绿，根蒂＝硬挺，敲声＝清脆 36 色泽＝青绿，根蒂＝硬挺，敲声＝沉闷 37 色泽＝青绿，根蒂＝稍蜷，敲声＝浊响 38 色泽＝青绿，根蒂＝稍蜷，敲声＝清脆 39 色泽＝青绿，根蒂＝稍蜷，敲声＝沉闷 40 色泽＝乌黑，根蒂＝蜷缩，敲声＝浊响 41 色泽＝乌黑，根蒂＝蜷缩，敲声＝清脆 42 色泽＝乌黑，根蒂＝蜷缩，敲声＝沉闷 43 色泽＝乌黑，根蒂＝硬挺，敲声＝浊响 44 色泽＝乌黑，根蒂＝硬挺，敲声＝清脆 45 色泽＝乌黑，根蒂＝硬挺，敲声＝沉闷 46 色泽＝乌黑，根蒂＝稍蜷，敲声＝浊响 47 色泽＝乌黑，根蒂＝稍蜷，敲声＝清脆 48 色泽＝乌黑，根蒂＝稍蜷，敲声＝沉闷 49 Ø 按照上述过程进行学习： （1，（色泽＝青绿、根蒂＝蜷缩、敲声＝浊响），好瓜） 可以删除假设空间中的3、5、6、8、9、11-15、17-21、23-30、32-49 （2，（色泽＝乌黑、根蒂＝蜷缩、敲声＝浊响），好瓜） 可以删除剩余假设空间中的2、10、16、31 （3，（色泽＝青绿、根蒂＝硬挺、敲声＝清脆），坏瓜） 可以删除剩余假设空间中的1 （4，（色泽＝乌黑、根蒂＝稍蜷、敲声＝沉闷），坏瓜） 剩余假设空间中无可删除的假设

学习过后剩余的假设为 4 色泽＝＊，根蒂＝蜷缩，敲声＝＊ 7 色泽＝＊，根蒂＝＊，敲声＝浊响 22 色泽＝＊，根蒂＝蜷缩，敲声＝浊响 这就是最后的“假设集合”，也就是“版本空间”。 其中：图中清脆应改为浊响。

本题解析 西瓜1（（色泽＝青绿、根蒂＝蜷缩、敲声＝浊响），好瓜））为正例 找到与它不一致的假设：3、5、6、8、9、11-15、17-21、23-30、32-49 西瓜4（（色泽＝乌黑、根蒂＝稍蜷、敲声＝沉闷），坏瓜））为反例 找到与它一致的假设：1,、3、6、9、15、21、30、48 所以在搜索过程中删除的假设有：1、3、5、6、8、9、11-15、17-21、23-30、32-49 剩下的假设有为：2、4、7、10、16、22、31 所以，所求版本空间为：{2、4、7、10、16、22、31}

1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。例如：好瓜←→（（色泽=）∧（根蒂=蜷缩）∧（敲声=））∨（（色泽=乌黑）∧（根蒂=）∧（敲声=沉闷）），会把“（色泽=）∧（根蒂=蜷缩）∧（敲声=）”以及“（色泽=乌黑）∧（根蒂=）∧（敲声=沉闷）”都分类为“好瓜”。若使用最多包含k个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算共有多少中可能的假设。（提示：注意冗余情况，如（A=a）∨（A=）与（A=）等价。） 本题解析 由题1.1知，共有49种假设，其中： 全部不泛化 2∗3∗3=182∗3∗3=18种假设； 一个属性泛化：2∗3+3∗3+2∗3=21种假设； 两个属性泛化：2+3+3=82+3+3=8种假设； 三属性泛化：1种假设 空集：1种假设 不考虑空集，则有48种假设，所以k的最大值为48。 而组成的析合范式是这48种假设的排列组合，展开序列为（即杨辉三角的一排）：（1、48、1128、… 、1128、48、1）共49个数，左边的1表示：一个假设都没选，右边的1表示：全部假设都被选。

如果k=48，就是说最多采用48种合取式来组成析合范式，排除一种都不选的情况，就是2^48 - 1种。（2^48是根据二项式系数之和得的） 如果0