第一章 绪论

思维导图

关键问题

1.假设空间

概念

所有属性可能取值构成的假设集合

计算

列出可能的样本点，即特征向量

2.版本空间

概念

与训练集一致的假设集合

习题:

1.1

计算步骤

1. 先列出假设空间
2. 删除与正例不一致，与反例一致的假设
3. 得到版本空间

第一步 假设空间：

• 色泽取值：青绿、乌黑
• 根蒂取值：蜷缩、稍蜷
• 敲声取值： 浊响、沉闷

 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. Ø

可知假设空间的规模为(2+1)(2+1)(2+1) + 1 = 28

第二步 删除与正例不一致或与反例一致的假设

学习过程：
（1，（色泽＝青绿、根蒂＝蜷缩、敲声＝浊响），好瓜）
删除假设空间中的反例得到：

 1. 色泽 = *, 根蒂 = *, 敲声 = *
 2. 色泽 = 青绿, 根蒂 = *, 敲声 = *
 3. 色泽 = *, 根蒂 = 蜷缩, 敲声 = *
 4. 色泽 = *, 根蒂 = *, 敲声 = 浊响
 5. 色泽 = 青绿, 根蒂 = 蜷缩, 敲声 = *
 6. 色泽 = 青绿, 根蒂 = *, 敲声 = 浊响
 7. 色泽 = *, 根蒂 = 蜷缩, 敲声 = 浊响
 8. 色泽 = 青绿, 根蒂 = 蜷缩, 敲声 = 浊响

（4，（色泽＝乌黑、根蒂＝稍蜷、敲声＝沉闷），坏瓜）
删除假设空间中的1得到:

 9. 色泽 = 青绿, 根蒂 = *, 敲声 = *
 10. 色泽 = *, 根蒂 = 蜷缩, 敲声 = *
 11. 色泽 = *, 根蒂 = *, 敲声 = 浊响
 12. 色泽 = 青绿, 根蒂 = 蜷缩, 敲声 = *
 13. 色泽 = 青绿, 根蒂 = *, 敲声 = 浊响
 14. 色泽 = *, 根蒂 = 蜷缩, 敲声 = 浊响
 15. 色泽 = 青绿, 根蒂 = 蜷缩, 敲声 = 浊响

从而得到相应的版本空间为：

1. 色泽 = 青绿, 根蒂 = *, 敲声 = *
2. 色泽 = *, 根蒂 = 蜷缩, 敲声 = *
3. 色泽 = *, 根蒂 = *, 敲声 = 浊响
4. 色泽 = 青绿, 根蒂 = 蜷缩, 敲声 = *
5. 色泽 = 青绿, 根蒂 = *, 敲声 = 浊响
6. 色泽 = *, 根蒂 = 蜷缩, 敲声 = 浊响
7. 色泽 = 青绿, 根蒂 = 蜷缩, 敲声 = 浊响

参考博文:西瓜书假设空间与版本空间的理解

1.2

表1.1中有4个样例，三个属性值：

• 色泽=青绿、乌黑
• 根蒂=蜷缩、稍蜷、坚挺
• 敲声=浊响、清脆、沉闷

假设空间中一共：(2+1)(3+1)(3+1) + 1 = 49种假设

全部不泛化：233 = 18种假设
一个属性泛化：23+33+2*3=21种假设
两个属性泛化：3+3+2=8种假设
三个属性泛化：1种假设

合取式：多个条件同时满足(多个集合取交集)
析取式：多个条件满足其中一个以上即可(多个集合取并集)

不考虑空集，k的最大取值18，最终可能有2^18-1种假设

1.3

答：

通常认为两个数据的属性越相近，则更倾向于将他们分为同一类。若相同属性出现了两种不同的分类，则认为它属于与他最临近几个数据的属性。也可以考虑同时去掉所有具有相同属性而不同分类的数据，留下的数据就是没误差的数据，但是可能会丢失部分信息。

1.4

答：
还是考虑二分类问题，NFL首先要保证真是目标函数f均匀分布，对于有X个样本的二分类问题，显然f共有2^|X|种情况。其中一半是与假设一致的，也就P(f(x) == h(x)) = l 。
此时,应该是个常数，隐含的条件就该是(一个比较合理的充分条件) 。如果不满足， NFL 应该就不成立了(或者不那么容易证明)。

1.5

答：

• 消息推送，京东，淘宝购物推荐。
• 网站相关度排行，通过点击量，网页内容进行综合分析。
• 图片搜索，现在大部分还是通过标签来搜索。

参考博客：西瓜书第一章习题答案