1. 引言

模型和模式

模型泛指从数据中学得的结果

【模型】：指全局性结果（如一棵判断什么是好瓜的决策树）

判断一个西瓜是否是好瓜的决策树

【模式】：指局部性的结果（如一条判断好瓜的规则）

例如：色泽乌黑、根蒂蜷缩、敲声浊响的是好瓜

一条判断好瓜的规则

2. 基本术语

2.1 数据相关

例如：x1=（色泽=青绿；根蒂=蜷缩；敲声=浊响），x2=（色泽=乌黑；根蒂=稍蜷；敲声=沉闷），x3=（色泽=浅白；根蒂=硬挺；敲声=清脆），......

【数据集(data set)】：上面这组记录的集合

例如：这组西瓜的集合，x1=（色泽=青绿；根蒂=蜷缩；敲声=浊响），x2=（色泽=乌黑；根蒂=稍蜷；敲声=沉闷），x3=（色泽=浅白；根蒂=硬挺；敲声=清脆），......

【示例 (instance)或样本 (sample)】：关于一个事件或对象的描述的每条记录

例如：对其中一个西瓜的描述，x1=（色泽=青绿；根蒂=蜷缩；敲声=浊响）

【属性(attribute)或特征(feature)】：反应事件或对象在某方面的表现或性质的事项

例如：色泽，根蒂，敲声

【属性值(attribute value)】：属性上的取值

例如：色泽=青绿，根蒂=蜷缩，敲声=浊响

【属性空间(attribute space)、样本空间(sample space)或输入空间(input space)】：属性张成的空间

例如：以西瓜的三种属性为三个坐标轴，建立坐标系得到的空间

属性空间

【特征向量】：空间中的每个点对应的坐标向量

例如：X1就是一个特征向量

特征向量

【数学表达】

一般的，令D表示包含m个示例（样本）的数据集，xi表示每个示例（样本），每个示例由d个属性描述，其中xij表示是示例（样本）xi在第j个属性的取值，d称为维数

数据集 示例

2.2 学习过程

【学习(learning)、训练(training)】：从数据中学得模型的过程

例如：从西瓜样本数据集中得到判断好瓜的决策树的过程

【训练数据(training data)、训练集(training set)】：训练过程中使用的数据，是数据集的子集

例如：为得到判断好瓜的决策树，我们从10000条对西瓜的描述的记录中选择其中的8000条记录的作为训练数据

【训练样本】：训练集中的每一个样本

例如：8000条记录中的每一条记录都是一个样本

【测试】：学得模型后，使用其进行预测的过程

例如：通过得到的判断好瓜的决策树，判断一个西瓜是否是好瓜的过程

【测试数据】：测试过程中使用的数据

例如：我们从10000条对西瓜的描述的记录中选择剩下的2000条数据作为测试数据

【测试样本】：测试集中的每一个样本

例如：剩下的2000条记录中的每一条记录都是一个样本

【假设】：学得模型对应的关于数据的某种潜在规律

例如：学得的判断好瓜的决策树对应的某种潜在规律就是一种假设）

【真相、真实】：潜在规律的自身

例如：判断好瓜决策树对应的“客观上判断好瓜的规律”可能与学习得到的判断好瓜决策树有出入

【学习目的】：为了找出或逼近真相

2.3 监督学习和无监督学习

【标记】：关于示例的结果的信息

例如：色泽=青绿；根蒂=蜷缩；敲声=>浊响的西瓜是好瓜

【样例】：拥有了标记信息的示例

例如：（（色泽=青绿；根蒂=蜷缩；敲声=浊响），好瓜）

【标记空间、输出空间】：所有标记的集合

(xi，yi）表示第i个样例

有监督学习

对具有概念标记（分类）的训练样本进行学习，以尽可能对训练样本集外的数据进行标记（分类）预测

所有的标记（分类）是已知的。因此，训练样本的岐义性低

【分类】：预测的是离散值

例如：好瓜，坏瓜

【回归】：预测的是连续值

例如：西瓜的成熟度0.95/0.37

无监督学习

对没有概念标记（分类）的训练样本进行学习，以发现训练样本集中的结构性知识

所有的标记（分类）是未知的。因此，训练样本的岐义性高

【聚类】：将训练集中的样本分为若干组，每组称为一个“簇”，有助于我们了解数据内在的规律，能为更深入地分析数据建立基础

例如：“浅色瓜”、“深色瓜”，在聚类学习中，“浅色瓜”、“深色瓜” 这些概念事先我们是不知道的，而且学习过程中使用的样本通常不拥有标记信息

机器学习的目标

机器学习的目标是使学得的模型可以更好的适用于“新样本”，而不仅仅在训练样本上工作的很好，也就是拥有比较强的泛化能力，这样能更好的适用于整个样本空间，因此我们希望训练集合能很好的反应样本空间的特性

通常假设样本空间的全体样本服从一个未知分布Ɗ，我们获得的每个样本都是独立地从这个分布上采样获得的 ，即“独立同分布”；一般而言，训练样本越多，得到关于D的信息就越多，越有可能通过学习获得强泛化能力的模型

【泛化能力】：学得模型适用于新样本的能力

3. 假设空间

【归纳(induction)】：从特殊到一般的“泛化”过程，即从具体的事实归结出一般性规律（机器学习显然是一个归纳过程）

【演绎( deduction)】：从一般到特殊的“特化”过程，即从基础原理推演出具体情况

【假设空间】：所有的假设组成的空间

例如：（色泽=？）&&（根蒂=？）&&（敲声=？）的可能取值所形成的假设组成。

如色泽有“青绿” “乌黑” “浅白”，还需要考虑色泽无论取什么值都合适，我们用通配符“*”表示，此外还要考虑极端情况：有可能“好瓜”这个概率根本不成立，我们用O表示。若“色泽”、“根蒂”、“敲声”分别有3、2、2中取值。则假设空间的规模大小为4 x 3 x 3 + 1 = 37

西瓜问题的假设空间

【版本空间】：当存在多个假设与训练集一致时，这些与训练集一致的假设的集合

西瓜问题的版本空间

4. 归纳偏好

问题：现在有三个与训练集一致的假设，但是他们在面临新的样本的时候，却产生不同的输出

例如：对这个新瓜 （色泽=青绿；根蒂=蜷缩；敲声=沉闷），如果采用好瓜<->（色泽= *）&&（根蒂=蜷缩）&&（敲声=*）这个假设时，它会被判断为好瓜，然而当我们使用另外两个假设时，它却被判断为不好的

【归纳偏好】：机器学习算法在学习过程中对某种类型假设的偏好

任何一个有效的机器学习算法都必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，而无法产生确定的结果

例如：我们在每次进行预测是随机抽选训练集上等效的假设，那么对这个新瓜 （色泽=青绿；根蒂=蜷缩；敲声=沉闷），学习模型时而告诉我们它是好瓜，时而告诉我们它是不好的，这显然没有意义

【“奥卡姆剃刀”原则】：若多个假设与观察一致，则选择“最简单”的那个，这个“简单”并不简单

例如：对于上面三个与训练集一致的假设，哪一个更简单呢？

【“没有免费的午餐”定理（NFL）】：无论学习算法多聪明、学习算法多笨拙，他们的期望性能相同，但是有一个重要的前提：所有“问题”出现的机会相同或所有的问题同等重要

实际情况是很多时候我们只关注自己试图解决的问题，希望为它找到一个解决方案，至于其他问题甚至是相似的问题我们并不关心

NPL定理假设了 f 的均匀分布，而实际情况并非如此

NPL定理告诉我们脱离具体的问题，空泛地讨论“什么学习算法更好”毫无意义，因为若考虑所有潜在的问题，则所有算法一样好