机器学习 — 绪论

一、什么是假设空间，什么是版本空间？

假设空间即是所有属性的所有可能的取值相互间所有可能的组合构成的集合。

如监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。$\\$
模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间（hypothesis space）。$\\$
假设空间的确定意味着学习的范围的确定。$\\$

版本空间即是与当前训练集相同的假设构成的集合。

二、假定我们已获得如下表的训练数据集

（1）请求出假设空间并列出该假设空间中的所有假设组成。 $\\$
（2）请求出相应的版本空间

（1）
由上表可知，色泽的可能取值由2种、根蒂的取值由3种、敲声有3种。$\\$
但是在判断一个瓜的好坏时，可能某一属性的值可任意。（如无论色泽怎么样都是好瓜。）所以每种属性的可能值都要加1种任意（*）取值$\\$
另外还有一种情况即可能好瓜、坏瓜这种概念都不成立， 即假设空间存在一个空集$\varnothing$ $\\$
故假设空间的大小为： $3 * 4 * 4 + 1= 49$

（2）在此‘西瓜例’中，我们的学习目标为“好瓜”，所以我们要通过训练集，从假设空间中删除与正例不一致的假设（或与反例一致）

色泽＝青绿 ^ 根蒂 = 蜷缩 ^ 敲声＝浊响 → 好瓜$\\$
删除： 3、5、6、8、9、11-15、17-21、23-30、32-49

色泽＝乌黑 ^ 根蒂 = 蜷缩 ^ 敲声＝浊响 → 好瓜$\\$
删除：2、10、16、31

色泽＝青绿 ^ 根蒂 = 硬挺 ^ 敲声＝清脆 → 坏瓜$\\$
删除：1

色泽＝乌黑 ^ 根蒂 = 稍蜷 ^ 敲声＝沉闷 → 坏瓜$\\$
删除：$\varnothing$

学习完剩余假设：$\\$
4 色泽＝*，根蒂＝蜷缩，敲声＝* $\\$
7 色泽＝*，根蒂＝*，敲声＝浊响 $\\$
22 色泽＝*，根蒂＝蜷缩， 敲声＝浊响 $\\$

故版本空间为：

从上面图中可知 $\\$
根部=蜷缩 → 好瓜 $\\$
敲声=浊响 → 好瓜 $\\$
根部=蜷缩 ^ 敲声=浊响 → 好瓜

三、什么是NFL定理以及有何启示。

1. 通过公式的推导，我们发现总误差竟然与学习算法无关，对于任意两个学习算法，
2. 无论哪个算法更加”聪明“或者更加”笨拙”，它们的期望性能竟然相同。
3. 这就是”没有免费的午餐“定理（No Free Lunch Theorem,简称NFL定理)

假设样本空间$\chi$和假设空间$H$都是离散的 $\\$
令$P(h|X, L_a)$代表算法??基于训练数据$X$产生假设$h$的概率$\\$
$f$令代表希望学习的真实目标函数。$\\$
则 $L_a$ 的“训练集外误差”期望（其中$I(∙)$是指示函数，若 ∙ 为真则取值1，否则取值0）为：