“假设空间”与“版本空间”概念辨析及python实现

我在阅读机器学习西瓜书的假设空间章节时，对文中版本空间的理解有些模糊，因此去网上查阅了相关资料，并用python模拟了“假设空间”与“版本空间”的计算过程。
本文以机器学习西瓜书1.3 假设空间中的描述和数据集为例：

1. 这里的学习的目标是识别“好瓜”，假设“好瓜”可由 “色泽”、“根蒂”、“敲声” 三个因素确定。
2. 假定色泽有“青绿”“乌黑”“浅白”三种可能取值，还有可能无论取什么值都合适的，用“*”表示。
   

1 概念辨析

假设空间

不同地方的的定义：

• Hypothesis space is the set of all the possible legal hypothesis.（假设空间是所有可能的合法的假设集合）
• 机器学习中可能的函数构成的空间称为“假设空间”.

比较通俗的理解就是，属性所有可能的取值组成的样本。以书中的西瓜数据集为例，“色泽”“根蒂”“敲声”分别有3（青绿、乌黑、浅白）、3（蜷缩、硬挺、稍蜷）、3（浊响、清脆、沉闷）种可能的取值，每个再加上一个无论取和值的情况“*”，最后补上上一个空集的情况，因此假设空间的大小为4 * 4 * 4 + 1 = 65
说明：我看到网上的一些博文写的是49，他们是“色泽”这里少了一个“浅白”色，算的是3 * 4 * 4 + 1 = 49，这个颜色在上面数据集的表中没有，但是在书的正文里有提到；我在Z-library下的电子书里这部分算的是37，电子书里写的是分别有3、2、2种取值，再加上任意的情况“*”，最后是4 * 3 * 3 + 1 = 37。这几种应该是各自的前提假设不一样，但都是对的，我以我在看的纸质书的描述为准，结果是65。

版本空间

不同地方的定义：

• 可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”，我们称之为“版本空间”（version space）
• 版本空间就是与已知样本一致的所有假设的一个子集。

我的理解是，在假设空间里找到可以满足训练集里每个样本的一个最大子集。具体的算法是取假设空间里的一个样本，这个样本可以包含训练集所有正类，不包含训练集所有的父类。

2 python模拟

以西瓜书中的描述为例，先把一些属性值列出来（命名恐惧症，直接用书中的中文来命名了）

色泽 = ['*', '青绿', '乌黑', '浅白']
根蒂 = ['*', '蜷缩', '硬挺', '稍蜷']
敲声 = ['*', '浊响', '清脆', '沉闷']

西瓜数据集 = [
    (1, '青绿', '蜷缩', '浊响'),
    (1, '乌黑', '蜷缩', '浊响'),
    (0, '青绿', '硬挺', '清脆'),
    (0, '乌黑', '稍蜷', '沉闷')
]
1
2
3
4
5
6
7
8
9
10

接下来开始写输出“假设空间”的函数。假设空间比较好理解，就是在每个属性里取一个，最后三个属性值就可以组合成一个样本。

def hypothesis_space():
    cnt = 1 # 序号
    hypothesis_space = []
    for sz in 色泽:
        for gd in 根蒂:
            for qs in 敲声:
                hypothesis_space.append([cnt, (sz, gd, qs)])  
                cnt += 1
    hypothesis_space.append([cnt, ()])
    
    print('假设空间')
    for i in hypothesis_space:
        print(i)

    return hypothesis_space

if __name__ == '__main__':
    hypothesis_space()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

执行上述代码，打印“假设空间”

然后计算“版本空间”，计算“版本空间”最重要的是判断假设空间的一个样本是否包含训练集的某个样本。在本例中，是否包含就是看假设空间里的样本和训练集里的样本的每个属性值是否相等，或者假设空间里的样本的该属性值是“*”，是可以任取的。判断是否包含我封装成了一个函数：

def contain(a, b):
    '''whether a contain b'''
    if (len(a) != len(b)):
        return False
    for i in range(len(a)):
        if (a[i] != '*' and a[i] != b[i]):
            return False
    return True
1
2
3
4
5
6
7
8

有了判断包含的函数，对于正类（是好瓜），如果假设空间的样本没有包含训练集的样本，则从假设空间中将该样本删除，对于负类（不是好瓜），如果假设空间的样本包含训练集的样本，同理将其从假设空间里删除。
为了避免各种问题，直接给出了所有代码（包含上面的代码）。如果不太熟悉python，对于版本空间部分代码需要注意的是：

1. python需要使用list_a = list_b[:]实现list的拷贝。若使用list_a = list_b，变量list_a存的只是list_b的地址
2. 对于删除list里的某一项，不能边遍历边删，会导致部分元素没被遍历到，下面的代码是通过额外申请空间实现的

色泽 = ['*', '青绿', '乌黑', '浅白']
根蒂 = ['*', '蜷缩', '硬挺', '稍蜷']
敲声 = ['*', '浊响', '清脆', '沉闷']

西瓜数据集 = [
    (1, '青绿', '蜷缩', '浊响'),
    (1, '乌黑', '蜷缩', '浊响'),
    (0, '青绿', '硬挺', '清脆'),
    (0, '乌黑', '稍蜷', '沉闷')
]

def hypothesis_space():
    cnt = 1
    hypothesis_space = []
    for sz in 色泽:
        for gd in 根蒂:
            for qs in 敲声:
                hypothesis_space.append([cnt, (sz, gd, qs)])  
                cnt += 1
    hypothesis_space.append([cnt, ()])
    
    print('假设空间')
    for i in hypothesis_space:
        print(i)

    return hypothesis_space

def version_space(hypothesis_space, dataset):
    version_space = hypothesis_space[:]
    for data in dataset: # 遍历数据集
        print(data, '可删除:')
        tmp_space = version_space[:]
        for space_item in tmp_space:
            if data[0] == 1 and not contain(space_item[1], data[1:]) or data[0] == 0 and contain(space_item[1], data[1:]): 
            # 训练集是正类且假设函数样本不包含训练集样本，或
            # 训练集是负类且假设函数样本 包含 训练集样本
                print('remove', space_item)
                version_space.remove(space_item)

    print('版本空间')
    for i in version_space:
        print(i)

def contain(a, b):
    '''whether a contain b'''
    if (len(a) != len(b)):
        return False
    for i in range(len(a)):
        if (a[i] != '*' and a[i] != b[i]):
            return False
    return True

if __name__ == '__main__':
    hypothesis_space = hypothesis_space()
    version_space(hypothesis_space, 西瓜数据集)
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
50
51
52
53
54
55

执行代码，结果如图

3 总结

通过对“版本空间”计算的模拟，可以看到”版本空间“主要适用与二分类的数据集。啃西瓜书ing，如果有错误，欢迎在评论区指出。

参考

【机器学习笔记】 假设空间与版本空间
Version Spaces
如何理解假设空间与版本空间？