第1章绪论 1.1引言 傍晚小街路面上沁出微雨后的湿润，和煦的细风吹来，抬头看看天边的晚 霞，嗯，明天又是一个好天气。走到水果摊旁，挑了个根蒂蜷缩、敲起来声音浊 响的青绿西瓜，一边满心期待着皮薄肉厚瓢甜的爽落感，一边愉快地想着，这学 期狠下了工夫，基础概念弄得清清楚楚，算法作业也是信手拈来，这门课成绩一 定差不了！ 希望各位在学期结束时有这样的感觉.作为开场，我们先大致了解一下什 么是“机器学习”(machine learning)). 回头看第一段话，我们会发现这里涉及很多基于经验做出的预判.例如，为 什么看到微湿路面、感到和风、看到晚霞，就认为明天是好天呢？这是因为在 我们的生活经验中已经遇见过很多类似情况，头一天观察到上述特征后，第二 天天气通常会很好.为什么色泽青绿、根蒂蜷缩、敲声浊响，就能判断出是正 熟的好瓜？因为我们吃过、看过很多西瓜，所以基于色泽、根蒂、敲声这几个 特征我们就可以做出相当好的判断.类似的，我们从以往的学习经验知道，下足 了工夫、弄清了概念、做好了作业，自然会取得好成绩.可以看出，我们能做出 有效的预判，是因为我们已经积累了许多经验，而通过对经验的利用，就能对新 情况做出有效的决策 上面对经验的利用是靠我们人类自身完成的.计算机能帮忙吗？ 机器学习正是这样一门学科，它致力于研究如何通过计算的手段，利用经 【Mitchell,1o97给出T 验来改善系统自身的性能.在计算机系统中，“经验”通常以“数据”形式存 设 在任务类T上的性能 在，因此，机器学习所研究的主要内容，是关于在计算机上从数据中产生“模 若一个程序通过利用经验 型”(model)的算法，即“学习算法”(learning algorithm).有了学习算法，我 E在T中任务上获得了性 们把经验数据提供给它，它就能基于这些数据产生模型；在面对新的情况时（例 能改善，则我们就说关于 T和P.该程序对E进行 如看到一个没剖开的西瓜，模型会给我们提供相应的判断（例如好瓜）.如果说 了学习 计算机科学是研究关于“算法”的学问，那么类似的，可以说机器学习是研究 关于“学习算法”的学问 本书用“模型”泛指从数据中学得的结果.有文献用“模型”指全局性结 倒如Hand etal..2001 果（例如一棵决策树），而用“模式”指局部性结果（例如一条规则）
第1章绪论 1.2基本术语 要进行机器学习，先要有数据.假定我们收集了一批关于西瓜的数据，例 如（色泽=青绿；根蒂=蜷缩；敲声=浊响），（色泽=乌黑；根蒂=稍蜷；敲声=沉 闷)，（色泽=浅白；根蒂=硬挺；敲声=清脆），，每对括号内是一条记录 “=”意思是“取值为”： 这组记录的集合称为一个“数据集”(data set),其中每条记录是关于 个事件或对象（这里是一个西瓜）的描述，称为一个“示例”(instance)或“样 因为 本”(sample),反映事件或对象在某方面的表现或性质的事项，例如“色泽” 作对样本空间的一个采样 “根蒂”“敲声”，称为“属性”(attribute)或“特征”(feature);属性上的取 通过上下文可判断出“样 本”是指单个示例还是数 值，例如“青绿”“乌黑”，称为“属性值”(attribute value).属性张成的空 据」 间称为“属性空间”(attribute space)、“样本空间”(sample space)或“输入 空间”，例如我们把“色泽”“根蒂”“敲声”作为三个坐标轴，则它们张成 一个用于描述西瓜的三维空间，每个西瓜都可在这个空间中找到自己的坐标位 置。由于空间中的每个点对应一个坐标向量，因此我们也把一个示例称为一个 “特征向量”(feature vector). 一般地，令D={c1,2,,xm}表示包含m个示例的数据集，每个 示例由d个属性描述（例如上面的西瓜数据使用了3个属性），则每个示例 x=(x;c2;xd)是d维样本空间X中的一个向量，x1∈X,其中x是 x:在第)个属性上的取值（例如上述第3个西瓜在第2个属性上的值是“硬 挺”)，d称为样本xi的“维数”(dimensionality). 从数据中学得模型的过程称为“学习”(learning)或“训练”(training) 这个过程通过执行某个学习算法来完成.训练过程中使用的数据称为“训练 数据”(training data),其中每个样本称为一个“训练样本”(training sample), 训练样本组成的集合称为“训练集”((training set).学得模型对应了关于数据 的某种潜在的规律，因此亦称“假设”(hypothesis):这种潜在规律自身，则称 为“真相”或“真实”(ground-truth),学习过程就是为了找出或逼近真相.本 书有时将模型称为“学习器”(learner),可看作学习算法在给定数据和参数空 和（或）训练数据，将产生 间上的实例化. 不同的结果 如果希望学得一个能帮助我们判断没剖开的是不是“好瓜”的模型，仅 有前面的示例数据显然是不够的.要建立这样的关于“预测”(prediction)的 模型，我们需获得训练样本的“结果”信息，例如“(（色泽=青绿；根蒂=蜷缩； 敲声=浊响)，好瓜)”.这里关于示例结果的信息，例如“好瓜”，称为“标 用作名词、也可用作动词 记”(label)；拥有了标记信息的示例，则称为“样例”(example).一般地，用
1.2基本术语 3 若将标记看作对象本身 (红，)表示第i个样例，其中h∈y是示例x:的标记，y是所有标记的集合， 的一郸分，则“样例”有 时也称为“样本” 亦称“标记空间”(label space)或“输出空间” 若我们欲预测的是离散值，例如“好瓜”“坏瓜”，此类学习任务称为 “分类”(classification:若欲预测的是连续值，例如西瓜成熟度0.95、0.37， 此类学习任务称为“回归”(regression)。对只涉及两个类别的“二分 类”(binary classification)任务，通常称其中一个类为“正类”(positive class), 亦称“负类” 另一个类为“反类”(negative class);涉及多个类别时，则称为“多分 类”(multi--class classification)任务.一般地，预测任务是希望通过对训练 集{e,h,(c2,2,,(m,m}进行学习，建立一个从输入空间X到输出 空间y的映射∫：X→y.对二分类任务，通常令y={-1,+1}或{0,1；对 多分类任务，门川>2；对回归任务，y=R,R为实数集 学得模型后，使用其进行预测的过程称为“测试”(testing),被预测的样本 使的芯力测雅本感即知在学得厂后对试例工可得到共预一 测标记y=f(x). 我们还可以对西瓜做“聚类”(clustering),即将训练集中的西瓜分成若干 组，每组称为一个“簇”(cluster);这些自动形成的簇可能对应一些潜在的概念 划分，例如“浅色瓜”“深色瓜”，甚至“本地瓜”“外地瓜”，这样的学习过 程有助于我们了解数据内在的规律，能为更深入地分析数据建立基础.需说明 的是，在聚类学习中，“浅色瓜”“本地瓜”这样的概念我们事先是不知道的， 况，见136节 而且学习过程中使用的训练样本通常不拥有标记信息 根据训练数据是否拥有标记信息，学习任务可大致划分为两大类：“监督 壳林师华习 学习”(supervised learning)和“无监督学习”(unsupervised learning),分类 和回归是前者的代表，而聚类则是后者的代表。 更确切地说，是“未见 示°（unseen instance). 需注意的是，机器学习的目标是使学得的模型能很好地适用于“新样本” 而不是仅仅在训练样本上工作得很好：即便对聚类这样的无监督学习任务，我 们也希望学得的簇划分能适用于没在训练集中出现的样本.学得模型适用于 新样本的能力，称为“泛化”(generalization)能力.具有强泛化能力的模型能 现实任务中样本空间的 很好地适用于整个样本空间.于是，尽管训练集通常只是样本空间的一个很小 规通常很 例如20 属性，每个属性有10个可 的采样，我们仍希望它能很好地反映出样本空间的特性，否则就很难期望在训 能取值，则样本空间的规 练集上学得的模型能在整个样本空间上都工作得很好.通常假设样本空间中全 模已达1020). 体样本服从一个未知“分布”(distribution)D,我们获得的每个样本都是独立 地从这个分布上采样获得的，即“独立同分布”(independent and identically distributed,简称ii.d).一般而言，训练样本越多，我们得到的关于D的信息
4 第1章绪论 越多，这样就越有可能通过学习获得具有强泛化能力的模型 1.3假设空间 归纳(induction)与演绎(deduction)是科学推理的两大基本手段.前者是从 特殊到一般的“泛化”(generalization)过程，即从具体的事实归结出一般性规 律：后者则是从一般到特殊的“特化”(specialization)过程，即从基础原理推演 出具体状况.例如，在数学公理系统中，基于一组公理和推理规则推导出与之 相洽的定理，这是演绎：而“从样例中学习”显然是一个归纳的过程，因此亦称 “归纳学习”(inductive learning). 归纳学习有狭义与广义之分，广义的归纳学习大体相当于从样例中学习 而狭义的归纳学习则要求从训练数据中学得概念(concept),因此亦称为“概念 学习”或“概念形成”，概念学习技术目前研究、应用都比较少，因为要学得 泛化性能好且语义明确的概念实在太困难了，现实常用的技术大多是产生“黑 箱”模型。然而，对概念学习有所了解，有助于理解机器学习的一些基础思想. 概念学习中最基本的是布尔概念学习，即对“是”“不是”这样的可表示 为0/1布尔值的目标概念的学习.举一个简单的例子，假定我们获得了这样 个训练数据集 表1.1西瓜数据集 编号色泽根蒂敲声好瓜 1 吉绿缘馆神响 是 乌黑缩 浊响 青绿 插辉 清脆 4 黑稍沉闷 这里要学习的目标是“好瓜”，暂且假设“好瓜”可由“色泽”“根蒂” “敲声”这三个因素完全确定，换言之，只要某个瓜的这三个属性取值明确了 我们就能判断出它是不是好瓜.于是，我们学得的将是“好瓜是某种色泽、某 种根蒂、某种敲声的瓜”这样的概念，用布尔表达式写出来则是“好瓜（色 垂一的 知(AAB)V(CAD)的析 泽=)A(根蒂=)Λ（敲声=？）”，这里“？”表示尚未确定的取值，而我们的任 合范或 务就是通过对表1.1的训练集进行学习，把“？”确定下来 读者可能马上发现，表1.1第一行：“（色泽=青绿）Λ（根蒂=蟾缩）Λ（敲 声=浊响)”不就是好瓜吗？是的，但这是一个已见过的瓜，别忘了我们学习的 目的是“泛化”，即通过对训练集中瓜的学习以获得对没见过的瓜进行判断的
1.3假设空间 、6 能力。如果仅仅把训练集中的瓜“记住”，今后再见到一模一样的瓜当然可判 是所谓的 断，但是，对没见过的瓜，例如“（色泽=浅白）入（根蒂=蜷缩）A(敲声=浊响)” ,泰见15节 怎么办呢？ 我们可以把学习过程看作一个在所有假设(ypothesis)组成的空间中进行 搜索的过程，搜索目标是找到与训练集“匹配”()的假设，即能够将训练集中 的瓜判断正确的假设。假设的表示一旦确定，假设空间及其规模大小就确定了 这里我们的假设空间由形如“（色泽=？）A(根蒂=？)A(敲声=？)”的可能取值 所形成的假设组成。例如色泽有“青绿”“乌黑”“浅白”这三种可能取值 还需考虑到，也许“色泽”无论取什么值都合适，我们用通配符“*”来表示 例如“好瓜什（色泽=）Λ（根蒂=蜷缩）A(敲声=浊响)”，即“好瓜是根蒂蟋 缩、敲声浊响的瓜，什么色泽都行”，此外，还需考虑极端情况：有可能“好 瓜”这个概念根本就不成立，世界上没有“好瓜”这种东西；我们用©表示这 个假设.这样，若“色泽”“根蒂”“敲声”分别有3、2、2种可能取值，则我 “非青绿”这样的A操 们面临的假设空间规模大小为4×3×3+1=37.图11直观地显示出了这个 作，由于训练集包含正例 因此白假设自然不出现. 西瓜问题假设空间。 [(色泽=：根彩=：敲舟=可 (色泽一青绿：根蒂=*：敲声■)[《色泽=乌黑：根蒂=：敲声=*)…。 (色泽一青绿：根蒂=婚缩：破尚=·)]（色泽=青绿：根蒂一硬挺：敲声一*）… [(色泽=青绿：根蒂=蟋缩：敲声=浊响)（色泽=青绿：根蒂=地缩：敲声=沉闷）】 图1.1西瓜问题的假设空间 可以有许多策略对这个假设空间进行搜索，例如自顶向下、从一般到特殊 或是自底向上、从特殊到一般，搜索过程中可以不断别除与正例不一致的假 设、和（或）与反例一致的假设.最终将会获得与训练集一致（即对所有训练样本 向上同时进行，在操作上 能够进行正确判断)的假设，这就是我们学得的结果 只删除与正例不一致的假 设等 需注意的是，现实问题中我们常面临很大的假设空间，但学习过程是基于 有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与 训练集一致的“假设集合”，我们称之为“版本空间”(version space).例如， 在西瓜问题中，与表1.1训练集所对应的版本空间如图12所示