《机器学习》（周志华）第一章课后习题参考答案_表1.1中若只包含编号为1和4的两个样例

《机器学习》（周志华）第一章课后习题参考答案

1.1 求版本空间

题目：表1.1中若只包含编号为1和4的两个样例，试给出相应的版本空间。
P5：与训练集一致的“假设集合”我们称之为版本空间。本题即在假设空间中搜索包含正例且不包含反例的所有假设。（详细说明见后思考）
首先，用一个六位二进制数将整个假设空间表示出来，每两位描述一个属性。前两位取01表示色泽的取值为“青绿”，10表示色泽取值为“乌黑”，11表示色泽取值为 *。后四位分别表示根蒂与敲声的取值，以此类推.注意题中只包含1和4两个样例，因此假设空间中色泽的取值范围为：* ，乌黑、青绿；根蒂的取值范围为：*，蜷缩、稍蜷；敲声的取值范围为：*，浊响、沉闷。

假设空间

若两个假设的二进制表示分别为A和B，则 A | B==A ⇒ B⊂A，A&B==B ⇒ B⊂A.（任意一个等式都可以判断出假设A是否包含假设B）
设P为假设1（正例），N为假设4（反例），假设H只要满足H | P==H && H | N != H为真，那么假设H就应该被包含在版本空间内。遍历假设空间内的所有假设进行上述判断，就可以获得版本空间内的所有假设。

#include<stdio.h>

int hypo_const[27] = {
  0x3f,0x3d,0x3e,0x37,0x3b,0x1f,0x2f,0x35,0x36,0x39,0x3a,0x1d,0x1e,0x2d,0x2e,
                      0x17,0x1b,0x27,0x2b,0x15,0x16,0x19,0x1a,0x25,0x26,0x29,0x2a};

void main()
{

    int sample[2] = {
  0x15,0x2a},sum=0;
    for(int i=0;i<27;i++)
    {
        if( (hypo_const[i] | sample[1] ) != hypo_const[i] && (hypo_const[i] | sample[0]) == hypo_const[i] )  
        {
            sum++;
            printf("%x  %d\n",hypo_const[i],i+1);
        }
    }
    printf("\nsum:%d\n\n",sum);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

求得版本空间为假设2、4、6、8、12、16、20.

版本空间

思考：书中P5提到，版本空间的求法为遍历假设空间，不断删除与正例不一致的假设和（或）与反例一致的假设。按照我的理解，版本空间有以下3种不同的求法。

• 删除不能包含所有正例以及包含任意反例的假设
• 删除不能包含所有正例的假设
• 删除包含任意反例的假设

• 本题使用了第一种方法来求版本空间，三种求法的选择应该属于归纳偏好的范畴。

  1.2 求假设空间大小

  题目：与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含k个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算有多少种可能的假设。
  分析：本题可以延续上一题的假设表述方法，每个合取式用一个8位二进制整数来表示，则一共有48个数待选。遍历C(48,k)种可能的选取组合，求出每种组合中k个合取式的合并结果，再去掉重复和冗余的情况，就是包含k个合取式的析合范式所能表达的假设空间大小。请注意，题目所述为“最多包含k个合取式的析合范式”，也就是说1,2,3…k个合取式组成的析合范式都满足条件，而不是仅考虑k个合取式组成的析合范式。
  难点：
  1. 假设空间太大，穷举所有组合不现实。
  2. 合取式的合并结果（析取式）如何求，如何用一个整数表示。

  先来看难点2
  前文所述的表示方法，合取式的合并算法十分低效，因此有必要定义一种新的表达方式。在48个基本假设（基本合取式）中，有2*3*3=18个叶子假设（叶子合取式）：每个特征的取值都为具体值。任何合取式、析取式都可以用这18个叶子合取式的组合来表示。因此可以用一个18位的二进制整数来表示任意假设：将18个叶子合取式编号，若某假设包含序号为1的叶子合取式，则该假设第一位为1，否则第一位为0。其它位类推。在这种新的表达方式下，合并合取式（或析取式）A,B，只需作 C=A|B 的按位或运算，C即为表示A、B合并析取式的整数。（C语言按位或运算的速度非常快）
  新的表达方式下，代表每个假设整数的求法如下：
  1.将48个基本合取式的旧表达式存在数组hypo_old中
  2.将18个叶子合取式的旧表达式存在数组hypo_leaf中
  3.对hypo_old中的每个元素，循环对hypo_leaf中的18个元素xi作如下判断：若A|xi==A，则Anew中第i位为1，否则Anew中第i为为0.
  将新的表达结果（48个整数）存在hypo_const中。
  这种表达方式不仅大大提高了合并合取式算法的效率，还让我们有了一个额外发现：本题的最大假设空间大小为262143.为什么会有这个结论呢？原因就是18位二进制整数所能表示的最大范围即262143，又因为析取范式不考虑空集∅，即整数不为0，因此假设空间的大小即262143.这个结论非常重要，甚至一定程度上它就是本道题的答案（k足够大）。

  难点1
  如图所示，以k=3时为例，遍历C(48,3)中所有组合的情况实际上就是3个标记依次不断向右移动的过程。序号大的标记，总是在序号小的标记的右侧。
  
  在移动过程中，我们总是先确定标记1的位置（初始记为1），然后在标记1的右侧确定标记2的位置（初始记为1+1）……直到确定标记k的位置（初始记为k-1+1，这么写有些奇怪，原因下面会讲）。每确定完一次标记k，就形成一次组合。之后，将标记k自增，若标记k≤48，则又形成新的组合，继续自增；若标记k>48，则标记k越界，转而向前先寻找标记k-1的位置（自增），若k-1也越界（标记k-1>47），继续向前寻找标记k-2位置（自增），直到向前寻得标记k-i自增后不越界（标记k-i≤48-i），此时调转趋势，向后寻找标记k-i+1的位置（递增，值为标记k-i的值+1），直到标记k的位置（标记k-1的值+1）。
  确定方式：每个标记有两种可能的确定方式。若是从后面的标记越界返回，则改变方式为自增，若是从前面的标记顺序向下确定，则改变方式为递增（上一个标记的值+1）。额外规定：1.形成一次组合后，标记k的改变方式为自增。2.标记1的改变方式总为自增。
  优化方法：
  动态申请长度为k的一维数组poslist和hypo_process，poslist用来保存k个标记的位置，hypo_process用来保存前k个合取式合并的