西瓜书——假设空间与归纳偏好
归纳于演绎
Induction&&Deduction
归纳和演绎是科学推理的两大基本手段
前者是从特殊到一般的泛化过程：即从具体的事实归结出一般性的规律；
后者是从一般到特殊的特化过程：即从基础原理推理出具体情况。
- 归纳学习
- “从样例中学习”显然是一个归纳过程，因此叫归纳学习；
归纳学习有狭义和广义之分:
广义的归纳学习大体相当于从样例中学习；
狭义的归纳学习则要求从训练数据中学得概念，因此也被称为“概念学习”或者“概念形成”。
- 概念学习
- 布尔概念学习：即对“是”“不是”这样的可表示为0/1布尔值的目标概念的学习。
假设空间
Hypothesis Space
还是以分别西瓜的好坏为例子（这就是一个布尔概念学习）：
有一下的训练数据集：
| 编号 | 色泽 | 根蒂 | 敲声 | 好瓜 |
|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 是 |
| 2 | 乌黑 | 蜷缩 | 浊响 | 是 |
| 3 | 青绿 | 硬挺 | 清脆 | 否 |
| 4 | 乌黑 | 稍蜷 | 沉闷 | 否 |
好瓜 <-> (色泽=?)^(根蒂=?)^(敲声=?)
这里的？表示尚未确定的取值，而我们的任务就是通过对上表的训练进行学习，把？确定下来
我们可以把学习过程看作一个在所设假设组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配”的假设，即能够将训练集中的瓜判断正确的假设。
比如这里的色泽有“青绿”“乌黑”“浅白”这三种可能取值；还需考虑到，也许“色泽”无论取什么值都合适，我们这里用通配符“*”来表示。
此外，还要考虑极端情况：有可能“好瓜”这个概念并不存在，世界上没有“好瓜”这种东西。
于是我们的假设空间规模大小：
$$ 4\times4\times4+1=65 $$
可以有许多策略对这个假设空间进行搜索，例如自顶向下、从一般到特殊，或者自底向上、从特殊到一般，搜索过程中可以不断删除与正例不一致的假设，和（或）与反例一致的假设。最终将会得到与训练集一致（即对所有训练样本能够进行正确判断）的假设，这就是我们学到的结果。
版本空间
Version Space
现实问题中我们常面临很大的假设空间，但是学习过程是基于有限样本训练集进行的。因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”，我们称之为“版本空间”
例子
- 表中对应的版本空间
(1) 色泽=* 根蒂=蜷缩 敲声=浊响
(2) 色泽=* 根蒂=蜷缩 敲声=*
(3) 色泽=* 根蒂=* 敲声=浊响 - 表中若只包含编号1和编号4的两个样例，试给出相应的版本空间
（1）色泽=青绿 根蒂=蜷缩 敲声=浊响
（2）色泽=青绿 根蒂=蜷缩 敲声=*
（3）色泽=青绿 根蒂=* 敲声=浊响
（4）色泽=* 根蒂=蜷缩 敲声=浊响
（5）色泽=青绿 根蒂=* 敲声=*
（6）色泽=* 根蒂=蜷缩 敲声=*
（7）色泽=* 根蒂=* 敲声=浊响
归纳偏好
Inductive Bias
在之前给出的训练数据集中，我们得到的版本空间会给我们带来一个麻烦：
现在有三个与训练集一致的假设，但是与他们对应的模型在面临新样本的时候，却会产生不同的输出。
例如：对（色泽=青绿；根蒂=蜷缩；敲声=沉闷）这个新收来的瓜，
如果我们采用：好瓜 <->(色泽=*)^(根蒂=蜷缩)^(敲声=*)
那么将会把这个瓜判断为好瓜。
但是如果采用其余两个假设，则判断结果将不是好瓜。
那么，应该采用哪个模型（假设）呢？
这时，学习算法本身的“偏好”就会起到关键的作用。
例如：
若我们的算法喜欢“尽可能特殊”的模型，则它会选择“好瓜 <->(色泽=*)^(根蒂=蜷缩)^(敲声=浊响)”；
但若我们的算法喜欢“尽可能一般”的模型，并且由于某种原因它更“相信”根蒂，则它会选择“好瓜 <->(色泽=*)^(根蒂=蜷缩)^(敲声=*)”。
机器学习在学习过程中对某种类型假设的偏好，称为“归纳偏好”。
任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果，可以想象，如果没有偏好，我们的西瓜学习算法产生的模型每次在进行预测时随机抽选训练集上的等效假设，那么对这个新瓜（色泽=青绿；根蒂=蜷缩；敲声=沉闷），学得的模型时而告诉我们它是好的、时而告诉我们它是不好的，这样的学习结果显然是没有意义的。