机器学习——第一章绪论

1. 1 引言

1. 2 基本术语

1.3 假设空间

1.4 归纳偏好

1. 1 引言

机器学习致力于研究如何通过计算的手段，利用经验来玫善系统自身的性能在计算机系统中，"经验"通常以"数据"形式存在，因此，机器学习所研究的主要内容，是关于在计算机上从数据中产生"模型" (model) 的算法，即"学习算法" (learning algorithm)。有了学习算法，我们把经验数据提供给它，它就能基于这些数据产生模型。，可以说机器学习是研究关于"学习算法"的学问。

1. 2 基本术语

数据集(data set) ：一组记录的集合；
"示例" (instance) 或"样本" (sample)：每条记录关于一个事件或对象的描述；
"属性" (attribute) 或"特征" (feature)：反映事件或对象在某方面的表现或性质的事项；
"属性空间" (attribute space) “样本空间” (sample space) 或"输入空间"：属性张成的空间；
"特征向量" (feature vector)：一个示例也称为一个特征向量；
"学习" (learning) 或"训练" (training)：从数据中学得模型的过程；
"训练数据" (training data): 训练过程中使用的数据;
“训练样本" (training sample)：每个样本；
"训练集" (training set)：训练样本组成的集合；
"假设" (hypothesis)：学得模型对应了关于数据的某种潜在的规律；
"真相"或"真实" (ground-truth)：这种潜在规律自身；
"学习器" (learner)：学习过程就是为了找出或逼近真相.本书有时将模型称为 “学习器” (learner)；
"标记" (label) 这里关于示例结果的信息，例如"好瓜";
"样例" (example)：拥有了标记信息的示例；
测试样本" (testing sample)：被预测的样本；
假设空间：假设(hypothesis) 组成的空间；
"版本空间" (version space)：学习过程是基于有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的"假设集合"，我们称之为版本空间；

1.3 假设空间

类似由样本构成的样本空间和由标记构成的标记空间，所有的假设共同构成了假设空间。学习的过程就可以看作是在假设空间中搜索最能**匹配(fit)**训练集的假设。

假设空间的规模有多大呢？举个例子，样本空间维度是3，也即每个样本由3个特征来表示。这三个属性可能的取值分别为3，2，2。那么假设空间的规模就是 4 × 3 × 3 + 1 = 37，为什么呢？因为除了可能的取值之外，每个属性还有一种选择就是使用通配符*号表示，即无论取何值都可以。所以一个有3种可能取值的属性在排列组合时有4种情形。最后的加一表示的是**$\varnothing$假设**，它对应的是一种无论属性取何值都不可能达到目的的状况。比方说，前面的假设都是假设怎样的瓜会是好瓜，而$\varnothing$假设则对应于好瓜根本不存在。

有时候会出现多个假设都能匹配训练集的情形，这些假设的集合就称为版本空间(version space)。版本空间是假设空间的子空间。

1.4 归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好，称为 “归纳偏好”（inductive bias）, 或简称为“偏好”。

为什么需要归纳偏好？- 从版本空间中找出最准确的假设

因为是使用同一训练样本集进行学习，所以无法判断版本空间中的多个假设的好坏，对于一个具体的学习算法而言，它必须要产生一个模型。这时，学习算法本身的“偏好”就会起到关键的作用。

任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中在同一训练集上“等效”的假设所迷惑，而无法产生确定的学习结果。如果没有偏好，西瓜学习算法产生的模型每次在进行预测时随机抽选训练集上的等效假设，那么将新样本输入模型，时而告诉我们它是好的、时而告诉我们它是不好的，这样的学习结果显然没有意义。

如何引导算法确立“正确的”偏好？- 奥卡姆剃刀
“奥卡姆剃刀" （Occam’s razor）是一种常用的、自然科学研究中最基本的原则，即 “若有多个假设与观察一致,则选最简单的那个”。奥卡姆剃刀并非唯一可行的原则，奥卡姆剃刀本身存在不同的诠释，使用奥卡姆剃刀原则并不平凡，需借助其他机制才能解决。

根据奥卡姆剃刀原则，在上图A和B两个假设中，A更简单，所以A优于B，但是，会不会出现现图1.4(b)的情况：与 A 相比，B 与训练集外的样本更一致？

与 A 相比，B 与训练集外的样本更一致，这种情况完全可能出现。换句话说，对于一个学习算法 a ，若它在某些问题上比学习算法 b 好，则必然存在另一些问题中 b 算法比 a 算法好。

没有免费的午餐定理理（No Free Lunch Theorem，简称NFL定理）对任何算法均成立，哪怕是把本书后面将要介绍的一些聪明算法作为 a 而将 “随机胡猜”这样的笨拙算法作为 b，没有免费的午餐定理仍然成立。

对于学习算法来说，要产生一个模型就意味着要从版本空间中挑选出一个假设。但是版本空间中的假设都和训练集一致，无法直接分辨出哪一个更好，这时候归纳偏好，简称偏好就起作用了。

注意区分偏好和特征选择，前者是基于某种领域知识而产生的，后者则是基于对训练样本的分析进行的。

偏好指的是，在多个假设等效时，学习算法会认为某一种假设更优，并选择这种假设来建立最终的模型。如果一个学习算法没有偏好，比方说每次随机地从版本空间中选择一个假设，则它所给出的结果是时好时坏，自相矛盾的。所以任何一个有效的学习算法都应当有自己的归纳偏好。

怎样确定归纳偏好呢？一个常用的原则是奥卡姆剃刀(Occam's razor)，用一句话概述就是：若多个假设与观察一致，则选最简单的那个。注意，奥卡姆剃刀并不是唯一的准则，并且如何诠释“最简单”也是待考虑的。

给定基于某种归纳偏好的算法产生的模型A和基于另一种归纳偏好的算法产生的模型B，有时我们会注意到，A和B在不同的样本集上的表现各有好坏，有时候A的效果更好，有时候B的效果更好。甚至一个随机产生的模型都有可能在某个样本集上表现得优于我们精心设计的算法所产生的模型。怎样去定位这个问题呢？

书中使用NFL定理(No Free Lunch Theorem)来解答了这个问题，有一个关键点就是总误差与学习算法无关，证明在书上有，这里主要解析一下书中想要表达的思路。当我们考虑样本空间的所有可能分布，并认为它们都以相同的概率出现或同等重要时，无论使用什么模型，造成的总误差都是相同的，与学习算法无关！

但是！现实中并不是这样的，我们只考虑样本空间服从同一种分布的情形。打个比方，模型A是精心设计的算法产生的，模型B则简单地设定为把任何样本预测为负类。那么对于按照样本分布抽样所得的测试集，模型A效果会比B好；但是如果只抽取负类样本作为测试集，则模型B优于A。显然这种情况下模型B没有任何意义，因为我们根本就不care全是负类这种分布！

所以说，若考虑所有潜在的问题，则所有算法都一样好。**要谈论算法的优劣，必须结合具体问题！**学习算法的归纳偏好和问题是否相配，往往起到决定性的作用。