机器学习 周志华 第一章课后习题

1.1

在下面这张图片中若只包含编号为1和4的两个样例，试给出相应的版本空间。

书上实例：

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

2、接下来不断删除与正例不一致(或与反例一致)的假设

1. 色泽＝青绿、根蒂＝蜷缩、敲声＝浊响），好瓜
   删除假设空间中的3、5、6、8、9、11-15、17-21、23-30、32-49

2. （色泽＝乌黑、根蒂＝蜷缩、敲声＝浊响），好瓜）
   删除剩余假设空间中的2、10、16、31

3. （色泽＝青绿、根蒂＝硬挺、敲声＝清脆），坏瓜）
   删除剩余假设空间中的1

4. （色泽＝乌黑、根蒂＝稍蜷、敲声＝沉闷），坏瓜）
   剩余假设空间中无可删除的假设

3、最终假设空间为：{4、7、22}，与训练集一致：

习题解答：

1. 色泽＝青绿、根蒂＝蜷缩、敲声＝浊响），好瓜
   删除假设空间中的3、5、6、8、9、11-15、17-21、23-30、32-49
2. （色泽＝乌黑、根蒂＝稍蜷、敲声＝沉闷），坏瓜）
   剩余假设空间中删除的假设 1
3. 最终假设空间为：{2、4、7、10、16、22、31}

2. 色泽 = 青绿，根蒂 = *，敲声 = *
4. 色泽＝＊，根蒂＝蜷缩，敲声＝＊
7. 色泽＝*，根蒂＝＊，敲声＝浊响
10. 色泽＝青绿，根蒂＝蜷缩，敲声＝*
16. 色泽＝青绿，根蒂＝＊，敲声＝浊响
22. 色泽＝*，根蒂＝蜷缩，敲声＝浊响
31.  色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
1
2
3
4
5
6
7

1.2

与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。例如 好瓜 ↔ ( (色泽=) ∧ (根蒂=蜷缩) ∧ (敲声=) ) ∨ ( (色泽=乌黑) ∧ (根蒂=*) ∧ (敲声=沉闷) ) 会把“ (色泽=青绿) ∧ (根蒂=蜷缩) ∧ (敲声=清脆) ”和“ (色泽=乌黑) ∧ (根蒂=硬挺) ∧ (敲声=沉闷) ”都分类为“好瓜”。若使用最多包含 k 个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算共有多少种可能的假设。

详细可参考：https://zhuanlan.zhihu.com/p/355235881

1.3

若数据包含噪声，则假设空间中有可能不存在与所有训练样本都一致的假设。在此情况下，试设计一种归纳偏好用于假设选择。

1. 在训练过程中选择满足最多样本的假设，也可以对每个假设，求得其准确率。准确率=(符合假设的条件且为好瓜的样例数量)/(符合假设的条件的样例数量)，选择准确率最高的假设。
2. 通常认为两个数据的属性越相近，则更倾向于将他们分为同一类。若相同属性出现了两种不同的分类，则认为它属于与他最临近几个数据的属性。也可以考虑同时去掉所有具有相同属性而不同分类的数据，留下的数据就是没误差的数据，但是可能会丢失部分信息。

1.4

本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量 l，则式(1.1)将改为（将其中的指示函数改为其它性能度量 l 函数），试证明“没有免费午餐定理”仍成立。

详细可参考：https://blog.csdn.net/dicker6315/article/details/81265066

1.5

试述机器学习能在互联网搜索的哪些环节起什么作用。

1. 在向搜索引擎提交信息的阶段，能够从提交文本中进行信息提取，进行语义分析。
2. 在搜索引擎进行信息匹配的阶段，能够提高问题与各个信息的匹配程度。
3. 在向用户展示搜索结果的阶段，能够根据用户对结果感兴趣的程度进行排序。