第1章 绪论
1.1 引言
机器学习是这样一门学科，它致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。在计算机系统中，”经验“通常以”数据“形式存在，因此，机器学习所研究的主要内容，是关于在计算机上从数据中产生”模型“(model)的算法，即”学习算法“(learning algorithm)。有了学习算法，我们把经验数据提供给它，它就能基于这些数据产生模型；在面对新的情况时，模型会给我们提供相应的判断。
[Mitchell,1997]给出了一个更形式化的定义：假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过利用经验E在T中任务上获得了性能改善，则我们说关于T和P，该程序对E进行了学习。
1.2 基本术语
数据集(data set)：一组数据记录的集合。
示例(instance) or 样本(sample)：关于一个事件或对象的描述的一条记录。
属性(attribute) or 特征(feature)：反映事件或对象在某方面的表现或性质的事项。
属性值(attribute value)：属性上的取值。
属性空间(attribute space) or 样本空间(sample space) or 输入空间：属性张成的空间。
特征向量(feature vector)：属性空间中每个点对应的坐标向量。
维数(dimensionality)：令D = {x1,x2,…,xm}表示包含m个示例的数据集，每个示例由d个属性描述，则每个示例 xi = (xi1;xi2;…;xid)是d维空间χ中的一个向量，xi $\in$ χ，其中xij是xi在第j个属性上的取值，d称为样本xi的“维数”。
学习(learning) or 训练(training)：从数据中学的模型的过程，这个过程通过执行某个学习算法来完成。
训练数据(training data)：训练过程中使用的数据。
训练样本(training sample)：训练过程中每个样本。
训练集(training set)：训练样本组成的集合。
假设(hypothesis)：学得模型对应了关于数据的某种潜在的规律。
真相 or 真实(ground-truth)：潜在规律自身，学习过程就是为了找出或逼近真相。
标记(label)：关于示例结果的信息。
样例(example)：拥有了标记信息的示例。
标记空间(label space) or 输出空间：用(xi,yi)表示第i个样例，其中yi $\in$ γ是xi的标记，γ是所有标记的集合，亦称“标记空间”或“输出空间”。
分类(classification)：欲预测的是离散值时的学习任务。
回归(regression)：欲预测的是连续值时的学习任务。
二分类(binary classification) and 多分类(multi-class classification)：只涉及两个/多个类别的任务。
正类(positive class) and 反类(negative class)：二分类任务其中一个类和另一个类。
测试(testing) and 测试样本(testing sample)：学得模型后，使用其进行预测的过程称为“测试”，被预测的样本称为“测试样本”。
聚类(clustering) and 簇(cluster)：对数据做“聚类”，即将数据分成若干组，每组称为一个“簇”，这些自动形成的簇可能对应一些潜在的概念划分。
监督学习(supervised learning) and 无监督学习(unsupervised learning)：根据训练数据是否拥有标记信息，学习任务可大致划分为“监督学习”和“无监督学习”，分类和回归是前者的代表，聚类是后者的代表。
泛化(generalization)能力：学得模型适用于新样本的能力。
独立同分布(independent and identically distributed,简称i.i.d)：假设样本空间中全体样本服从一个未知“分布”(distribution)，我们获得的每个样本都是独立地从这个分布上采样获得的，即“独立同分布”。
1.3 假设空间
我们可以把学习过程看作一个在所有假设(hypothesis)组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配”(fit)的假设，即能够将训练集中的瓜判断正确的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。
可以有许多策略对假设空间进行搜索，搜索过程中不断删除与正例不一致的假设或与反例一致的假设。最终将会获得与训练集一致(即对所有训练样本能够进行正确判断)的假设，这就是我们学得的结果。
需要注意的是，现实问题中我们常面临很大的假设空间，但学习过程是基于有样本训练集进行的，因此，可能有多个假设与训练集一致，即存在一个与训练集一致的“假设集合”，我们称之为“版本空间”(version space)。
1.4 归纳偏好
当版本空间有多个假设与训练集一致，但与它们对应的模型在面临新样本的时候，会产生不同的输出，那么应该采用哪一个模型呢？
机器学习算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”(inductive vias)，或简称为“偏好”。任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果。那么有没有一般性的原则来引导算法确立“正确的”偏好呢？
“奥卡姆剃刀”(Occam’s razor)是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”。然而其并非唯一可行的原则。
“没有免费的午餐”定理(No Free Lunch Theorem,简称NFL定理)[Wolpert,1996;Wolpert and Macready,1995]：
设有学习算法ζa和ζb，假设样本空间χ和假设空间H都是离散的。令P(h|X,ζa)代表算法ζa基于训练数据X产生假设h的概率，再令f代表我们希望学习的真实目标函数。ζa的“训练集外误差”，即ζa在训练集之外的所有样本上的误差为
其中$\mathbb{I}$(•)是指示函数，若•为真则取值1，否则取值0。
考虑二分类问题，且真实目标函数可以是任何函数χ $\mapsto${0,1}，函数空间为{0,1}|χ|。对于所有可能的f按均匀分布对误差求和，有
式(1.2)显示出，总误差与学习算法无关，对于任意两个学习算法ζa和ζb，有
这就是“没有免费的午餐”定理。
需注意到，NFL定理有一个重要前提：所有“问题”出现的机会相同、或所有问题同等重要。所以，其最重要的寓意，是让我们清楚地认识到，脱离具体问题，空谈“什么学习算法更好”毫无意义。学习算法自身的归纳偏好与问题是否匹配，往往会起到决定性的作用。