1.2 假设空间
习题1.2 给定包含两个西瓜样例的西瓜数据集，如表1.4所示，请结合教材1.3节对“假设空间”相关概念的介绍，回答以下问题：
1.根据表1.4，计算假设空间（hypothesis space）的大小.
2.根据表1.4，给出相应的版本空间（version space）.
表1.4 西瓜数据集，“好瓜”列为标记
解答
1.表1.4中的西瓜共有两个属性，分别是“色泽”和“根蒂”.每个属性分别有2个取值，如“色泽”可取值为“青绿”或“乌黑”.参考教材1.3节中的计算方法，假设空间的大小为
（2+1）×（2+1）+1=10.
2.版本空间指与训练集（training set）中的正例一致的假设集合.如果数据的假设空间较小，可以将所有可能的假设枚举出来，根据每个训练样例排除掉不符合的假设，剩下的假设集合即为版本空间.这一求解版本空间的方法也被称为“枚举消除”（list-then-eliminate）法[4].
需要注意在假设空间的计算过程中，“假设”（hypothesis）表示的是从输入属性到输出标记之间的一种关系，对于每一个属性，一个假设可取值为属性值，也可取值为通配符“*”，因此需要在计算中有“+1”的操作.
表1.5中枚举出了共10个假设，其中有3个和训练集吻合.因此，该数据集的版本空间为{（色泽=*；根蒂=蜷缩）；（色泽=青绿；根蒂=*）；（色泽=青绿；根蒂=蜷缩）}.
表1.5 使用“枚举消除法”求解版本空间
（续）
习题1.3 给定包含若干橘子样例的橘子数据集，如表1.6所示，请结合教材1.3节对“假设空间”相关概念的介绍，回答以下问题：
1.根据表1.6，计算假设空间的大小.
2.根据表1.6，给出相应的版本空间.
表1.6 橘子数据集，“甜橘”列为标记（同表1.1）
解答
1.表1.6中的橘子共有5个属性，分别是“大小”“表皮”“色泽”“弹性”以及“果蒂”.每个属性的取值分别有2、3、4、3、2个.例如，“色泽”属性共有“橙色”“青绿”“绿色”“黄色”4个取值.所以假设空间的大小为
（2+1）×（3+1）×（4+1）×（3+1）×（2+1）+1=721.
同习题1.2，假设空间的计算也需要考虑由通配符构成的假设.
2.当前数据集假设空间较大，如果仍使用“枚举消除法”，会十分耗时耗力.针对当前的问题，可使用一种“夹逼”的思路，维护两个集合G和S——其中G由通配符假设收缩，逐步排除和负例对应的假设，获得包含正例假设的最松范围（“上界”）；而集合S由任意一个正例假设开始，逐步扩张，使得能容纳更多的正例，获得包含正例假设的最紧范围（“下界”）.最终比较S和G则可得到版本空间.依次遍历各样例，具体步骤如下：
1）编号1：（大小=大）∧（表皮=光滑）∧（色泽=橙色）∧（弹性=柔软）∧（果蒂=扁平）为正例；初始化集合G包含通配符假设，初始化集合S包含和当前正例一致的假设.
此时G最松，S最紧.
2）编号2：（大小=大）∧（表皮=粗糙）∧（色泽=青绿）∧（弹性=坚硬）∧（果蒂=凸起）为负例，不在集合S中，因此，集合S不变化，而需要减小G的范围，排除负例对应的假设，根据该样例的每个属性值更新集合G.具体而言，G当前是由通配符构成的假设，为了尽可能减小G的改动，引入基于单一属性的假设，使负例不包含在G中.首先考虑“大小”这一属性，由于编号为1和2的两个样例均具有属性值（大小=大），引入依赖于（大小=大）的假设无法排除负例.然后考虑“表皮”属性，由于编号1的正例样本中“表皮”属性取值为“光滑”，而当前负例样本中“表皮”属性取值为“粗糙”，因此可以在G中引入新假设，设置其他属性为通配符而仅通过“表皮=光滑”使其能够符合正例而排除负例.类似地，也可针对其他属性进行假设扩展以修改G，从而得到如下结果：此时，将编号2的样例代入，未能满足G中假设的条件，不会被判断为正例.
3）编号3：（大小=大）∧（表皮=粗糙）∧（色泽=橙色）∧（弹性=略软）∧（果蒂=扁平）为正例.一方面，需要对集合S进行合并，在S中增加该正例；另一方面，需要对集合G进行删减，去除和该正例不一致的假设.例如，当前正例的“表皮=粗糙”和G中依赖于“表皮=光滑”的假设不一致，因此删除G中对应假设；同时由于当前S的假设需要“表皮=光滑”，为囊括该正例，将S中的假设对“表皮”属性的取值置为通配符.
4）编号4：（大小=小）∧（表皮=破裂）∧（色泽=绿色）∧（弹性=柔软）∧（果蒂=扁平）为负例，可以根据该样例更新上一步得到的集合G中的第二种假设情况.
5）编号5：（大小=大）∧（表皮=光滑）∧（色泽=黄色）∧（弹性=柔软）∧（果蒂=扁平）为正例，据此对S和G进行更新.
此时所有样例都被遍历过一遍，且集合G=S.因此，橘子数据集所对应的版本空间为{（大小=大；表皮=*；色泽=*；弹性=*；果蒂=扁平）}.
习题注释 版本空间的求解除了可以针对离散的假设空间外，也适用于连续的假设空间.如图1.2a所示，正负号分别表示正例和负例，规定假设为矩形框（框内为正例，框外为负例），虚线框展示了一个可能的假设（由于框内包含负例，因此该假设不在版本空间中）.本题中对版本空间的求解可归纳为候选消除算法（candidate elimination algorithm）[4].该算法首先寻找一个版本空间G，使得不存在其他不在G中的假设能够使G扩张；同时寻找另一个具体的版本空间S，包含最少的满足样例的假设.而G和S的边界分别为最大泛化边界（maximally general boundary）和最大具体边界（maximally specific boundary），二者构成的区域即为版本空间，如图1.2d所示.算法流程可总结如下，对数据集中的所有样例：
图1.2 版本空间示意图
1）初始化集合G（或最大泛化边界，即最大泛化假设的集合的边界），所有属性上的取值都成立，用通配符“*”表示；
2）初始化集合S（或最大具体边界，即最大具体假设的集合边界），所有属性上根据第一个正例样本取值；
3）当前样本为正例时，修改集合S中的特例假设，使其以最小的改变满足该正例样本，删去集合G中不符合该正例样本的泛化假设；
4）当前样本为负例时，修改集合G中的泛化假设，使其以最小的改变排除该负例样本，删去集合S中符合该负例样本的特例假设；
5）如果集合G和S中均只含有一个假设：如果它们相同，则得到结果；如果它们不同，则训练样例中存在不一致噪声，继续进行下一个样例的学习.
习题1.2和习题1.3主要考查对假设空间的理解，学习的过程就是根据有限的训练样例，在所有假设组成的空间中进行搜索的过程.可以看出，当假设空间大小不同时，版本空间的计算方式也有所不同.教材第12章对假设空间进行了进一步的讨论.