基本术语

假设空间

  训练集中的全部特征的可能取值所形成的假设，加上 $\varnothing$（指根本不存在“正例”这个概念） 这种极端假设，所形成的集合叫做假设空间。

版本空间

  在假设空间中删除与正例不一致的假设、和(或)与反例一致的假设，最终将会获得一个能够对所有训练集样本正确分类的一个假设集合，这个集合叫做版本空间。

数据集(训练集)

表1.1 西瓜数据集

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

习题解答

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

1. 若只包含1和4，则训练集如下:

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

2. 因为版本空间是假设空间经过删除与正例不一致的假设、和(或)与反例一致的假设所形成的，所以要得到假设空间:
   色泽、根蒂、敲声 分别有2、2、2种可能取值，有可能每个特征的特征值无论取什么值都合适，此外再加上 $\varnothing$ 情况，所以假设空间规模大小为(2+1)$\times$(2+1)$\times$(2+1)+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 $\varnothing$

3. 版本空间
   删除与编号1(正例)相反的假设：3、6-9、12、15、16-28
   删除与编号4(反例)相同的假设：1
   版本空间为剩余假设：2、4、5、10、11、13、14 七种
   用合取式表示为：
   （色泽=*) ^ (根蒂=*) ^ (敲声=浊响)
   （色泽=*) ^ (根蒂=蜷缩) ^ (敲声=*)
   （色泽=*) ^ (根蒂=蜷缩) ^ (敲声=浊响)
   （色泽=青绿) ^ (根蒂=*) ^ (敲声=*)
   （色泽=青绿) ^ (根蒂=*) ^ (敲声=浊响)
   （色泽=青绿) ^ (根蒂=蜷缩) ^ (敲声=*)
   （色泽=青绿) ^ (根蒂=蜷缩) ^ (敲声=浊响)

1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含k个合取式的析合范式来表达表1.1的西瓜分类问题的假设空间，试估算有多少种可能的假设。

• 不考虑冗余
  表1.1共3个特征，假设空间中有3∗4∗4+1=49种假设。k的最大值是49，每次从中选出k个来组成析合式，即$\Sigma$$C_{49}^k$ k最大为49，根据二项式定理得2⁴⁹种假设
• 考虑冗余
  //todo

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

• 去掉噪声数据
• 将噪声值变为特征值最多的值

1.4 试证明"没有免费的午餐"

西瓜书P8说到，一个学习算法${\xi }_a$若在某些问题上比算法${\xi }_b$好，则必然另存在一些问题算法${\xi }_b$比算法${\xi }_a$要好，这个结论对任何算法都成立。

以下公式含义：算法${\xi }_a$学得的假设在训练集外的所有样本上的误差的期望
$E_{ote}\left({\xi }_a|X,f\right)$ = ${\sum }_h$${\sum }_{x\in \chi -X}$$P$($x$) $II($$h$($x$)$̸=$$f(x))$$P$($h$| $X$,${\xi }_a$)

${\xi }_a$：学习算法a。
$P$($h$| $X$,${\xi }_a$)：首先$P$是概率，是算法${\xi }_a$基于训练集$X$，产生出假设$h$的概率。我的个人理解是：就像假设空间产生版本空间一样，所以产生版本空间的每一个假设的概率和为1，即 ${\sum }_h$$P$($h$| $X$,${\xi }_a$)=1。
$f(x)$：真实值
$II($$h$($x$)$̸=$$f(x))$ ： 若预测值$h$($x$)$̸=$真实值$f(x)$为真 $II($$h$($x$)$̸=$$f(x))$=1，否则等于0。
$P(x)$： $x\in \chi -X$ ，$x$是$X$训练集中的元素，$P(x)$即假设$x$在假设空间被取到的概率。

剩余的便是求和$\sum$部分, 为便于理解，先举一个小例子：
${\sum }_i^m$${\sum }_j^o$${\sum }_k^n$$a_i$$b_j$$c_k$
= ${\sum }_i^m$$a_i$${\sum }_j^o$$b_j$${\sum }_k^n$$c_k$
=$(a_1+a_1+...+a_m)(b_1+a_1+...+b_j)(c_1+c_1+...+c_k)$
=$(a_1{b}_1{c}_1)(a_1{b}_1{c}_2)...(a_m{b}_j{c}_k)$
理解上述例子推导在来看这个公式：
${\sum }_f$$E_{ote}\left({\xi }_a|X,f\right)$
=${\sum }_f$ ${\sum }_h$${\sum }_{x\in \chi -X}$$P$($x$) $II($$h$($x$)$̸=$$f(x))$$P$($h$| $X$,${\xi }_a$)
=${\sum }_{x\in \chi -X}$$P$($x$) ${\sum }_h$$P$($h$| $X$,${\xi }_a$)${\sum }_f$$II($$h$($x$)$̸=$$f(x))$
=$\frac{1}{2}\ast 2^{|x|}$${\sum }_{x\in \chi -X}$$P$($x$) ${\sum }_h$$P$($h$| $X$,${\xi }_a$)
=$2^{|x|-1}$${\sum }_{x\in \chi -X}$$P$($x$)
最后推导出的结果与算法${\xi }_a$无关！

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

• sao排名
• 个性化推荐
• tf-idf关键词提取

如有错误欢迎指正