西瓜书第一章

第一章 绪论

---

基本概念

1. 学习算法：假设用 P 来估计计算机程序在某任务 T 上的性能，若一个程序通过利用经验 E 在 T 任务上获得了性能改善，则我们就说关于 T 和 P，该程序对 E 进行了学习。
2. 模型：本书中泛指从数据中学得的结果
3. 示例（instance）或样本（sample）：关于一个事件或对象的描述，也可称为特征向量
4. 样例（example）：拥有标记信息的示例
5. 属性（attribute）或特征（feature）：反映事件或对象在某方面的表现或性质，其值为属性值
6. 数据集（data set）：记录的集合，每条记录都是一个示例或样本
7. 属性空间、样本空间、输入空间：属性张成的空间
8. 标记空间、输出空间：所有标记的集合
9. 监督学习：预测离散值：分类（二分类（正类、反类）、多分类）；预测连续值：回归
10. 无监督学习：聚类（clustering）：将训练集（无标记）中的样本自动分为若干组，每组称为一个簇（cluster）
11. 泛化（generalization）能力：学得模型适用于新样本的能力

假设空间

若“好瓜”仅由“色泽”、“根蒂”、“敲声”完全确定：“ $好瓜 $\longleftrightarrow$ (色泽=?) $\bigwedge$ (根蒂=?) $\bigwedge$ (敲声=?) ”

我们可以把学习过程看做在一个所有假设组成的空间内进行搜索的过程，搜索目标是寻找与训练集匹配(fit)的假设。

这样，若色泽、根蒂、敲声分别有3，3，3种可能取值，再考虑可以取任意值(*)，则假设空间的规模即为 4*4*4+1=65

对假设空间进行搜索，搜索过程中不断删除与正例不一致、与反例一致的假设，最终即可得到与训练集一致的假设，可能会包含多个假设，称之为版本空间

版本空间从假设空间剔除了与正例不一致和与反例一致的假设，它可以看成是对正例的最大泛化。

归纳偏好

机器学习算法再学习过程中对某种类型假设的偏好，称之为归纳偏好

任何一种机器学习算法必有其归纳偏好，否则它将被假设空间内看似“等效”的假设所迷惑，而无法产生确定的结果。

奥卡姆剃刀（Occam’s razor）是一种常用的、自然科学研究最基本的原则：若有多个假设与观察一致，则选择最简单的那个

没有免费的午餐（NFL定理：No Free Lunch Theorem）：在所有问题出现的概率相等、所有问题同等重要的情况下，任何一种算法的总误差与学习算法无关。

证明：
假设样本空间 $\chi$ 和假设空间 $H$ 都是离散的. 令 $P(h|X,L_a)$ 代表算法 $L_a$ 基于训练数据 X 产生假设 h 的概率, 再令 $f$ 表示希望学到的真实目标函数.
则 $L_a$ 的训练集外误差, 即 $L_a$ 在训练集外的所有样本上的误差为:($\prod(.)$ 是指示函数)

$$E_{ote}(L_a|X,f) = \sum_{h}\sum_{x\in\chi-X}{P(x)\prod(h(x)\neq f(x))P(h|X, L_a)}$$

考虑二分类问题, 且真实目标函数可以是任何函数 $\chi \rightarrow {\lbrace0,1\rbrace}$, 函数空间为 ${\lbrace0,1\rbrace}^{|\chi|}$
对所有可能的 $f$ 按均匀分布对误差求和:

$$\begin{aligned} \sum_fE_{ote}(L_a|X,f)&=\sum_f\sum_h\sum_{x\in\chi-X}P(x)\prod(h(x)\neq f(x))P(h|X,L_a)\\ &=\sum_{x\in\chi-X}P(x)\sum_hP(h|X,L_a)\sum_f\prod(h(x)\neq f(x))\\ &=\sum_{x\in\chi-X}P(x)\sum_hP(h|X,L_a)\frac{1}{2}2^{|\chi|}\\ &=\frac{1}{2}2^{|\chi|}\sum_{x\in\chi-X}P(x)\sum_hP(h|X,L_a)\\ &=2^{|\chi|-1}\sum_{x\in\chi-X}P(x) \end{aligned}$$

也即,学习算法的总误差与学习算法无关

但是现实生活中的问题并非如此，因此必须结合具体的学习问题，设计相应的算法。

要讨论学习算法的相对优劣，必须针对具体的学习问题，学习算法自身的归纳偏好与问题是否相配，往往会起到决定性的作用。

习题

答案解析部分转载自CSDN博主「四去六进一」的原创文章：参考答案总目录， 第一章答案， 第一章第二题答案

习题 1.1

表 1.1 中若只包含编号为1,4的两个样例，试给出相应的版本空间

编号	色泽	根蒂	敲声	好瓜
1	青绿	蜷缩	浊响	是
4	乌黑	稍蜷	沉闷	否

数据集有3个属性，每个属性2种取值，一共 3∗3∗3+1=283∗3∗3+1=28种假设，分别为

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

编号1的数据可以删除 2−8，10−12，14−16，18−20，22，24，26，282−8，10−12，14−16，18−20，22，24，26，28(不包含数据1)

编号1的数据可以删除 2 7 27(包含了数据2)

所以版本空间为:

1.色泽=青绿 根蒂=蜷缩 敲声=浊响
9.色泽=青绿 根蒂=蜷缩 敲声=*
13.色泽=青绿 根蒂=* 敲声=浊响
17.色泽=* 根蒂=蜷缩 敲声=浊响
21.色泽=青绿 根蒂=* 敲声=*
23.色泽=* 根蒂=蜷缩 敲声=*
25.色泽=* 根蒂=* 敲声=浊响

一般情况下版本空间是正例的泛化，但由于数据集中只有1个正例，所以在版本空间中依然包含了这个样本的假设(假设1)。