机器学习周志华 PDF

第1 章 绪 论 1. 1 引言 傍晚小街路面上沁出微雨后的湿润，和熙的细风吹来，抬头看看天边的晚 霞 7 嗯，明天又是一个好夭气.走到水果摊旁，挑了个根蒂蜷缩、敲起来声音浊 响的青绿西瓜...

第1 章 绪 论 1. 1 引言 傍晚小街路面上沁出微雨后的湿润，和熙的细风吹来，抬头看看天边的晚 霞 7 嗯，明天又是一个好夭气.走到水果摊旁，挑了个根蒂蜷缩、敲起来声音浊 响的青绿西瓜，一边满心期待着皮薄肉厚瓢甜的爽落感，一边愉快地想着，这学 期狠下了工夫，基础概念弄得清清楚楚，算法作业也是信手拈来，这门课成绩一 定差不了! 希望各位在学期结束时有这样的感觉.作为开场，我们先大致了解一下什 么是"机器学习" (machine learning). 回头看第一段话，我们会发现这里涉及很多基于经验做出的预判.例如，为 什么看到微温路面、感到和风、看到晚霞，就认为明天是好天呢?这是因为在 我们的生活经验中已经遇见过很多类似情况，头一天观察到上述特征后，第二 天天气通常会很好.为什么色泽青绿、根蒂蜷缩、敲声浊晌，就能判断出是正 熟的好瓜?因为我们吃过、看过很多西瓜，所以基于色泽、根蒂、敲声这几个 特征我们就可以做出相当好的判断.类似的，我们从以往的学习经验知道，下足 了工夫、弄清了概念、做好了作业，自然会取得好成绩.可以看出，我们能做出 有效的预判?是因为我们已经积累了许多经验，而通过对经验的利用?就能对新 情况做出有效的决策. 上面对经验的利用是靠我们人类自身完成的.计算机能帮忙吗? 机器学习正是这样一门学科，它致力于研究如何通过计算的手段，利用经 [Mitchell , 1997J 给出了 验来玫善系统自身的性能在计算机系统中，"经验"通常以"数据"形式存 一个更形式化的定义假 设用 P 来评估计算机程序 在，因此?机器学习所研究的主要内容，是关于在计算机上从数据中产生"模 在某任务类 T 上的性能， 若一个程序通过利用经验 型" (model) 的算法，即"学习算法" (learning algorithm). 有了学习算法，我 E 在 T 中任务丰获得了性 们把经验数据提供给它，它就能基于这些数据产生模型;在面对新的情况时(例 能改善，则我们就说关于 T 和 P ， 该程序对 E 进行 如看到一个没剖开的西瓜)，模型会给我们提供相应的判断(例如好瓜).如果说 了学习 计算机科学是研究关于"算法"的学问，那么类似的，可以说机器学习是研究 关于"学习算法"的学问. 本书用"模型"泛指从数据中学得的结果有文献用"模型"指全局性结 例如 [Hand et a l., 2001]. 果(例如一棵决策树)，而用"模式"指局部性结呆(例如 A条规则). 2 第 1 章绪论 1. 2 基本术语 要进行机器学习，先要有数据.假定我们收集了一批关于西瓜的数据，例 如(色泽=青绿;根蒂=蜷缩;敲声=浊响)， (色泽=乌黑;根蒂:稍蜷;敲声=沉 闷)， (色泽=浅自;根蒂t硬挺;敲声=清脆)，……，每对括号内是一条记录， "_，，意思是"取值为" 这组记录的集合称为一个"数据集" (data set) ，其中每条记录是关于一 个事件或对象(这里是一个西瓜)的描述，称为一个"示例" (instance) 或"样 有时整个数据集亦称一 本" (samp1e). 反映事件或对象在某方面的表现或性质的事项，例如"色泽" 个"样本"因为它可看 作对样本空间的一个采样， "根蒂" "敲声"，称为")副主" (attribute) 或"特征" (feature); 属性上的取 通过上下文可判断出"样 本"是指单个示例还是数 值，例如"青绿" "乌黑"，称为")副主值" (attribute va1ue). 属性张成的空 据集 间称为"属性空间" (attribute space) 、 "样本空间" (samp1e space) 或"输入 空间"例如我们把"色泽" "根蒂" "敲声"作为三个坐标轴，则它们张成 一个用于描述西瓜的三维空间，每个西瓜都可在这个空间中找到自己的坐标位 置.由于空间中的每个点对应一个坐标向量，因此我们也把…个示例称为一个 "特征向量" (feature vector). 一般地，令 D = {X l， 町 "..， X m } 表示包含 m 个示例的数据集，每个 示例由 d 个属性描述(例如上面的西瓜数据使用了 3 个属性)，则每个示例 Xi = (X i1; Xi2;... ; Xid) 是 d 维样本空间 X 中的一个向量 ， Xi ε X ， 其中 Xij 是 凯在第 j 个属性上的取值(例如上述第 3 个西瓜在第 2 个属性上的值是"硬 挺" ), d 称为样本院的"维数" (dimensionality). 从数据中学得模型的过程称为"学习" (le缸ning) 或"训练" (training) , 这个过程通过执行某个学习算法来完成.训练过程中使用的数据称为"训练 训练样本亦称"如11 练示 数据" (training data) ，其中每个样本称为一个叮 11 练样本" (training samp1e) , 例" (training instance) 或 "切|练例" 训练样本组成的集合称为"训练集" (training set). 学得模型对应了关于数据 的某种潜在的规律，因此亦称"假设" (hypothesis); 这种潜在规律自身，则称 为"真相"或"真实" (ground-truth) ，学习过程就是为了找出或逼近真相.本 学习算法通常有参数需 书有时将模型称为"学习器" (learner) ，可看作学习算法在给定数据和参数空 设置，使用不同的参数值 和(或)训练数据，将产生 间上的实例化. 不同的结果 如果希望学得一个能帮助我们判断没剖开的是不是"好瓜"的模型，仅 有前面的示例数据显然是不够的要建立这样的关于"预测" (prediction) 的 模型，我们需获得训练样本的"结果"信息，例如" ((色泽:青绿;根蒂二蜷缩; 将 "Iabel" 译为"标 记"而非"标签"是考 敲声=浊响)，好瓜)".这里关于示例结果的信息，例如"好瓜"，称为"标 虑到英文中 ".Iabel" 既可 记" (labe1); 拥有了标记信息的示例，则称为"样例" (examp1e). 一般地，用 用作名词、也可用作动词 1. 2 基本术语 3 若将标记看作对象本身 (Xi ， Yi) 表示第 4 个样例 7 其中执 εy 是示例 Xi 的标记 ， Y 是所有标记的集合， 的一部分，则"样例"有 时也称为"样本" 亦称"标记空间" (label 吕叩 pa肮ce叫)或"输出空间 若我们欲预测的是离散值，例如"好瓜" "坏瓜"，此类学习任务称为 "分类" (classification); 若欲预测的是连续值?例如西瓜成熟度 0.95 、 0.37 ， 此类学习任务称为"回归" (regression). 对只涉及两个类别的"二分 类" (binary cl嗣sification)任务，通常称其中一个类为 "Æ类" (positive cl甜的? 亦称"负类" 另一个类为"反类" (negative class); 涉及多个类别时，则称为"多分 类" (multi-class classificatio叫任务.一般地，预测任务是希望通过对训练 集 {(X1' Y1) , (X2 , Y2) ,..., (Xm , Ym)} 进行学习，建立一个从输入空间 X 到输出 空间 y 的映射 f: X 叶 y. 对二分类任务，通常令 Y = {-1 ，十 1} 或 {O ， l}; 对 多分类任务， IYI >2; 对回归任务， Y= lR，lR为实数集. 学得模型后，使用其母行预测的过程称为"测试" (testing) ，被预测的样本 亦称"测试示例" 称为喇试样本" (testing sample). 例如在学得 f 后，对测试例 X ， 可得到其预 (testing instance) 或"测 试例" 测标记 ν = f(x). 我们还可以对西瓜做"聚类" (clustering) ，即将训练集中的西瓜分成若干 组，每组称为 A个"簇" (cluster); 这些自动形成的簇可能对应一些潜在的概念 划分，例如"浅色瓜" "深色瓜 程有助于我们了解数据内在的规律?能为更深入地分析数据建立基础.需说明 否则标记信息直接形成 的是，在聚类学习中，"浅色瓜" "本地瓜"这样的概念我们事先是不知道的， 了簇划分，但也有例外情 而且学习过程中使用的训练样本通常不拥有标记信息. 况，参见 13.6 节 根据训练数据是否拥有标记信息，学习任务可大致划分为两大类"监督 亦称啃导f币学习"和 学习" (supervised learning) 和"无监督学习" (unsupervised learning) ，分类 ‘无导师学习 和回归是前者的代表，而聚类则是后者的代表. 史确切地说，是"未见 需注意的是，机器学习的目标是使学得的模型能很好地适用于"新样本"， 示例" (unseen instance). 而不是仅仅在训练样本上工作得很好;即便对聚类这样的无监督学习任务，我 们也希望学得的簇划分能适用于没在训练集中出现的样本.学得模型适用于 新样本的能力，称为"泛化" (generalization) 能力.具有强泛化能力的模型能 现实任务中样本空间的 很好地适用于整个样本空间.于是，尽管训练集通常只是样本需间的一个很小 规模通常很大(例如 20 个 的采样，我们仍希望它能很好地反映出样本空间的特性，否则就很难期望在训 属性 1 每个属性有 10 个可 能取佳，则样本空间的规 练集上学得的模型能在整个样本空间上都工作得很好.通常假设样本空间中全 模已达 10 20 ). 体样本服从 A个未知"分布" (distribution) Ð ， 我们获得的每个样本都是独立 地从这个分布上采样获得的，即"独立同分布" (independent and identically distributed ，简称 i.i.d.). 一般而言，训练样本越多，我们得到的关于 D 的信息 4 第 1 章绪论 越多，这样就越有可能通过学习获得具有强泛化能力的模型. 1. 3 假设空间 归纳 (induction) 与横绎 (deductio丑)是科学推理的两大基本手段.前者是从 特殊到一般的"泛化" (generalization) 过程，即从具体的事实归结出一般性规 律;后者则是从一般到特殊的"特化" (specializatio叫过程，即从基础原理推演 出具体状况.例如，在数学公理系镜中，基于一组公理和推理规则推导出与之 相洽的定理，这是演绎;而"从样例中学习"显然是一个归纳的过程?因此亦称 "归纳学习" (inductive learni吨). 归纳学习有狭义与广义之分?广义的归纳学习大体相当于从样例中学习， 而狭义的归纳学习则要求从训练数据中学得概念 (concept) ，因此亦称为"概念 学习"或"概念形成"概念学习技术目前研究、应用都比较少，因为要学得 泛化性能好且语义明确的概念实在太困难了，现实常用的技术大多是产生"黑 箱"模型.然而，对概念学习有所了解，有助于理解机器学习的一些基础思想. 概念学习中最基本的是布尔概念学习?即对"是" "不是"这样的可表示 为 0/1 布尔值的目标概念的学习.举一个简单的例子，假定我们获得了这样一 个训练数据集: 表1. 1 西瓜数据集 编号色泽根蒂敲声好瓜 1 青绿蜷缩浊响 是 2 乌黑蜷缩浊响 是 3 青绿硬挺清脆 否 4 乌黑稍蜷沉闷 否 这里要学习的目标是"好瓜"暂且假设"好瓜"可由"色泽" "根蒂" "敲声"这三个因素完全确定?换言之，只要某个瓜的这三兰个属性取值明确了? 我们就能判断出它是不是好瓜.于是?我们学得的将是"好瓜是某种色泽、某 种根蒂、某种敲声的瓜"这样的概念'用布尔表达式写出来则是"好瓜忡(色 Jt一般的情况是考虑形 如 (A^B)V(C^D) 的析 泽=?η) 八(根蒂 =7η) ^ (敲声 =7η) 合范式 务就是通过对表1.1的训练集进行字学罗习'把"?"确定下来. 读者可能马上发现，表1. 1 第一行: " (色泽=青绿)八(根蒂:蜷缩)八(敲 声=浊响)"不就是好瓜吗?是的，但这是·个己见过的瓜，别忘了我们学习的 目的是"泛化"?即通过对训练集中瓜的学习以获得对没见过的瓜进行判断的 1.3 假设空间 5 "记住"训练样本，就 能力.如果仅仅把训练集中的瓜"记住"，今后再见到一模一样的瓜当然可判 是所谓的"机械学习" [Cohen and Feigenbaum. 断，但是，对没见过的瓜，例如"(色泽=浅白) ^ (根蒂=蜷缩) ^ (敲声=浊晌)" 1983]. 或称"死记硬背式 怎么办呢? 学习"参见1. 5 节. 我们可以把学习过程看作一个在所有假设 (hypothesis) 组成的空间中进行 搜索的过程，搜索目标是找到与训练集"匹配"但t) 的假设，即能够将训练集中 的瓜判断正确的假设.假设的表示一旦确定，假设空间及其规模大小就确定了. 这里我们的假设空间由形如"(色泽=?)八(根蒂=?) ^ (敲声=?)"的可能取值 所形成的假设组成.例如色泽有"青绿" "乌黑" "浅白"这三种可能取值; 还需考虑到，也许"色泽"无论取什么值都合适，我们用通配符"*"来表示， 例如"好瓜件(色泽= *) ^(根蒂口蜷缩)八(敲声=浊响)" ，即"好瓜是根蒂蜷 缩、敲声浊响的瓜，什么色泽都行"此外，还需考虑极端情况:有可能"好 瓜"这个概念根本就不成立，世界上没有"好瓜"这种东西;我们用 m 表示这 这里我们假定训练样 个假设.这样，若"色泽" "根蒂" "敲声"分别有3 、 2 、 2 种可能取值，则我 本不含噪声，并且不考虑 "非青绿"这样的 -，A 操 们面临的假设空间规模大小为 4 x 3 x 3 + 1 = 37. 图1. 1 直观地显示出了这个 作由于训练集包含正例， 因此 g 假设自然不出现. 西瓜问题假设空间. (色泽兰兰青绿;根蒂=蜷缩;敲声=*) 7 Ls色泽二青绿;根蒂 z蜷缩;敲声=浊响) 11 (色泽=青绿;根蒂 z蜷缩;敲声二沉闷) 固1. 1 西瓜问题的假设空间 可以有许多策略对这个假设空间进行搜索，例如自顶向下、从一般到特殊， 或是自底向上、从特殊到一般，搜索过程中可以不断删除与正例不一致的假 有许多可能的选择，如 设、和(或)与反例→致的假设.最终将会获得与训练集一致(即对所有训练样本 在路径上自顶向下与自底 向上同时进行，在操作土 能够进行正确判断)的假设，这就是我们学得的结果. 只删除与正例不一致的假 设等 需注意的是，现实问题中我们常面临很大的假设空间?但学习过程是基于 有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与 训练集一致的"假设集合"，我们称之为"版本空间" (version space). 例如， 在西瓜问题中，与表1. 1 训练集所对应的版本空间如图1. 2 所示. 6 第 1 章绪论 图1. 2 西瓜问题的版本空间 1. 4 归纳偏好 通过学习得到的模型对应了假设空间中的一个假设.于是，图1. 2 的西瓜 版本空间给我们带来一个麻烦:现在有三个与训练集一致的假设，但与它们 对应的模型在面临新样本的时候，却会产生不同的输出.例如，对(色泽口青绿; 根蒂=蜷缩;敲声=沉闷)这个新收来的瓜，如果我们采用的是"好瓜村(色 泽= *)八(根蒂=蜷缩)八(敲声=*)"，那么将会把新瓜判断为好瓜，而如果采 用了另外两个假设，则判断的结果将不是好瓜.那么，应该采用哪一个模型(或 假设)昵? 若仅有表1. 1 中的训练样本，则无法断定上述三三三个假设中明哪F 一个"更好 然而，对于一个具体的学习算法而言?它必须要产生一个模型.这时，学习算 法本身的"偏好"就会起到关键的作用.例如，若我们的算法喜欢"尽可能特 尽可能特殊即"适用情 殊"的模型，则它会选择"好瓜件(色泽= *)八(根蒂=蜷缩)八(敲声=浊晌)" ; 形尽可能少".尽可能一 般即"适用情形尽可能 但若我们的算法喜欢"尽可能一般"的模型，并且由于某种原因它更"相信" 多" 根蒂，则它会选择"好瓜件(色泽= *) ^ (根蒂=蜷缩)八(敲声= *)".机器学习 对"根蒂"还是对"敲 算法在学习过程中对某种类型假设的偏好，称为"归纳偏好" (inductive bias) , 声"灵重视，.看起来和属 性选择，亦称"特征选 或简称为"偏好" 择" (feature selection) 有 关，但需注意的是，机器学 任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看 习中的特征选择仍是基于 似在训练集上"等效"的假设所迷惑，而无法产生确定的学习结果.可以想象， 对训练样本的分析进行的， 而在此处我们并非基于特 如果没有偏好，我们的西瓜学习算法产生的模型每次在进行预测时随机抽选 征选择做出对"根蒂"的 重视，这里对"根蒂"的 训练集上的等效假设，那么对这个新瓜"(色泽=青绿;根蒂口蜷缩;敲声=沉 信赖可视为基于某种领域 闷)" ，学得模型时而告诉我们它是好的、时而告诉我们它是不好的，这样的学 知识而产生的归纳偏好­ 关于特征选择方面的内容 习结果显然没有意义. 参见第 11 幸 归纳偏好的作用在图1. 3 这个回归学习图示中可能更直观.这里的每个训 练样本是因中的一个点 (x ， y) ， 要学得一个与训练集一致的模型，相当于找到一 条穿过所有训练样本点的曲线.显然，对有限个样本点组成的训练集，存在着 很多条曲线与其一致.我们的学习算法必须有某种偏好，才能产出它认为"正 确"的模型.例如，若认为相似的样本应有相似的输出(例如，在各种属性上都 1. 4 归纳偏好 7 y ，、 J 、 & B 、 、 /、‘ EE1 " 、 , 、 /' 、 、 _一 -, 『旬_-， 、 、 \ A x 图1. 3 存在多条曲线与有限样本训练集一致 很相像的西瓜，成熟程度应该比较接近)，则对应的学习算法可能偏好图1. 3 中 比较"平滑"的曲线 A 而不是比较"崎岖"的曲线 R 归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进 行选择的启发式或"价值观"那么，有没有一般性的原则来引导算法确立 "正确的"偏好呢? "奥卡姆剃刀" (Occam's razor) 是一种常用的、自然科学 研究中最基本的原则，即"若有多个假设与观察一致，则选最简单的那个"如 果采用这个原则，并且假设我们认为"更平滑"意味着"更简单" (例如曲线 A 更易于描述，其方程式是 y = _X 2 + 6x + 1 ，而曲线 B 则要复杂得多) ，则在 图1. 3 中我们会自然地偏好"平滑"的曲线 A. 然而，奥卡姆剃刀并非唯一可行的原则.退一步说，即使假定我们是奥卡姆 剃刀的铁杆拥走，也需注意到，奥卡姆剃刀本身存在不同的诠释，使用奥卡姆剃 刀原则并不平凡.例如对我们已经很熟悉的西瓜问题来说，"假设 1: 好瓜件 (色泽= *) ^ (根蒂=蜷缩)八(敲声=浊响)"和假设 2: "好瓜件(色泽= *) ^ (根蒂=蜷缩)八(敲声= *)"这两个假设，哪一个更"简单"呢?这个问题并不 简单，需借助其他机制才能解决. 事实上，归纳偏好对应了学习算法本身所做出的关于"什么样的模型更 好"的假设.在具体的现实问题中，这个假设是否成立，即算法的归纳偏好是否 与问题本身匹配，大多数时候直接决定了算法能否取得好的性能. 让我们再回头看看图1. 3. 假设学习算法 Zα 基于某种归纳偏好产生了对应 于曲线 A 的模型，学习算法 ~b 基于另一种归纳偏好产生了对应于曲线 B 的模 型.基于前面讨论的平滑曲线的某种"描述简单性"?我们满怀信心地期待算 法乌比岛更好.确实，图1. 4(a) 显示出?与 B 相比， A 与训练集外的样本更一 致;换言之， A 的泛化能力比 B 强. 8 第 1 置在绪 论 y y , ，.0-‘回 B J 、。 / B , ‘BEES S飞 1;才; 咽' 。 、 、。、 (a) A 优于 B (b) B 优于 A 国1. 4 没有免费的午餐(黑点:训练、样本;白点:测试样本) 但是，且慢!虽然我们希望并相信乌比马更好，但会不会出现图1.4(b) 的 情况:与 A 相比， B 与训练集外的样本更一致? 很遗憾，这种情况完全可能出现.换言之，对于一个学习算法鸟，若它在某 些问题上比学习算法岛好，则必然存在另一些问题，在那里岛比 2α 好.有趣 的是，这个结论对任何算法均成立，哪怕是把本书后面将要介绍的一些聪明算 法作为乌而将"随机胡猜"这样的笨拙算法作为乌.惊讶吗?让我们看看下 面这个简短的讨论: 这里只用到一些非常基 础的数学知识，只准备读 为简单起见，假设样本空间 X 和假设空间组都是离散的.令 P(hIX，'ca) 第 1 幸且有"数学恐惧" 代表算法乌基于训练数据 X 产生假设 h 的概率，再令 f 代表我们希望学习的 的读者可以跳过这个部分 而不会影响理解，只需相 真实目标函数. 'ca 的"训练集外误差"，即鸟在训练、集之外的所有样本上的 信，上面这个看起来"匪 误差为 夷所思"的结论确实是成 立的. Eote(乌 IX， f) 二三二三二 P(x) lI (h 忡忡 f(x))P(h I x，，cα) ， (1. 1) h æEX-X 其中1I(. )是指示函数，若·为真则取值 1 ，否则取值 o. 考虑二分类问题，且真实目标函数可以是任何函数 X 叶 {O ， l} ，函数空间 为 {O ， l}IXI. 对所有可能的 f 按均匀分布对误差求和，有 三二 ιdαIX，f) =艺 2二三二 P(x) lI(h(x) 纠 (x)) P(h I X，乌) f f h æεX…X =汇 P(x) 艺 P(h I X ,'ca) L)(h(x) 并 f(x)) 若 f 均匀分布，则有一 半的 f.对面的预测与 h(æ) = L P(x) 艺 P(h I X , 'ca)~2IXI 不一致. æEX-X h =jHZKZ) 汇 P例 X，'ca) zε X-X h 1. 4 归纳偏好 9 = 21.1' 1- 1 三二 P(æ). 1. (1. 2) æE二.1' -x 式(1. 2) 显示出，总误差竟然与学习算法无关!对于任意两个学习算法乌和 鸟，我们都有 三二 ιte(~αIX，f) =汇 ιte(~bIX， f) , (1. 3) f f 也就是说，无论学习算法乌多聪明、学习算法鸟多笨拙，它们的期望性能竟 严格的 NFL 定理证明比 然相同!这就是"没有免费的午餐"定理 (No Free Lunch Theorem，简称 NFL 这里的简化论述繁难得多. 定理) [Wolpert , 1996; Wolpert and Macready , 1995]. 这下子，读者对机器学习的热情可能被一盆冷水浇透了:既然所有学习算 法的期望性能都跟随机胡猜差不多，那还有什么好学的? 我们需注意到， NFL 定理有一个重要前提:所有"问题"出现的机会相 同、或所有问题同等重要.但实际情形并不是这样.很多时候，我们只关注自 己正在试图解决的问题(例如某个具体应用任务)，希望为它找到一个解决方案， 至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案，我们并不 关心.例如，为了快速从 A 地到达 B 地，如果我们正在考虑的 A 地是南京鼓· 楼、 B 地是南京新街口，那么"骑自行车"是很好的解决方案;这个方案对 A 地是南京鼓楼、 B 地是北京新街口的情形显然很糟糕，但我们对此并不关心. 事实上，上面 NFL 定理的简短论述过程中假设了 f 的均匀分布，而实际情 形并非如此.例如，回到我们熟悉的西瓜问题，考虑{假设 1: 好瓜件(色泽= *) 八(根蒂=蜷缩)八(敲声=浊响)}和{假设 2: 好瓜村(色泽= *) ^ (根蒂=硬挺) ^ (敲声:清脆)}.从 NFL 定理可知，这两个假设同样好.我们立即会想到符 合条件的例子，对好瓜(色泽=青绿;娘蒂=蜷缩;敲声=浊响)是假设 1 更好，而 对好瓜(色泽=乌黑;根蒂=硬挺;敲声=清脆)则是假设 2 更好.看上去的确是 这样.然而需注意到， " (根蒂=蜷缩;敲声=浊晌)"的好瓜很常见，而"(根 蒂:硬挺;敲声z清脆)"的好瓜罕见，甚至不存在. 所以， NFL 走理最重要的寓意?是让我们清楚地认识到，脱离具体问题，空 泛地谈论"什么学习算法更好"毫无意义，因为若考虑所有潜在的问题，贝。所 有学习算法都一样好.要谈论算法的相对优劣，必须要针对具体的学习问题;在 某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意，学习算法 自身的归纳偏好与问题是否相配，往往会起到决定性的作用. 10 第 1 章绪论 1. 5 发展历程 机器学习是人工智能 (artificial intelligence)研究发展到一定阶段的必然产 物.二十世纪五十年代到七十年代初，人工智能研究处于"推理期"，那时人们 以为只要能赋予机器逻辑推理能力，机器就能具有智能.这一阶段的代表性工 作主要有 A. Newell 和 H. Simon 的"逻辑理论家" (Logic Theorist)程序以及 此后的"通用问题求解" (General Problem Solving) 程序等，这些工作在当时 取得了令人振奋的结果.例如"逻辑理论家"程序在 1952 年证明了著名数学 家罗素和怀特海的名著《数学原理》中的 38 条定理 7 在 1963 年证明了全部 52 条定理，特别值得一提的是，定理 2.85 甚至比罗素和怀特海证明得更巧妙. A. Newell 和 H. Simon 因为这方面的工作获得了 1975 年圈灵奖.然而?随着研究 向前发展，人们逐渐认识到，仅具有逻辑推理能力是远远实现不了人工智能的- E. A. Feigenbau日1 等人认为，要使机器具有智能?就必须设法使机器拥有知识. 所谓"知识就是力量>> 在他们的倡导下，从二十世纪七十年代中期开始，人工智能研究进入了"知识 1965 年， Feigenbaum 主 期"在这一时期，大量专家系统问世，在很多应用领域取得了大量成果.E.A. 持研制了世界丰第一个专 家系统 DENDRAL. Feigenbaum 作为"知识工程"之父在 1994 年获得图灵奖.但是，人们逐渐认 识到，专家系统面临"知识工程瓶颈"，简单地说，就是由人来把知识总结出来 再教给计算机是相当困难的.于是?一些学者想到，如果机器自己能够学斗知识 该多好! 事实上，图灵在 1950 年关于图灵测试的文章中?就曾提到了机器学习的可 能;二十世纪五十年代初已有机器学习的相关研究，例如 A. Samucl 著名的跳 参见 p.22 棋程序.五十年代中后期 7 基于神经网络的"连接主义" (conncctionism) 学习 开始出现?代表性工作有 F. Rosenblatt 的感知机 (Perceptron) 、 B. Widrow 的 Adaline 等.在六七十年代，基于逻辑表示的"符号主义" (symbolism) 学习技 术建勃发展，代表性王作有 P. Winston 的"结构学习系统"、R. S. Michalski 等人的"基于逻辑的归纳学习系统'人E. B. Hunt 等人的"概念学习系统" 等;以决策理论为基础的学习技术以及强化学习技术等也得到发展，代表性份工 作有 N. J. Nilson 的"学习机器"等·二十多年后红极一时的统计学习理论的 一些奠基性结果也是在这个时期取得的. 1980 年夏，在美国卡耐基梅隆大学举行了第一届机器学习研讨会 (IWML); IWIVIL 后来发展为国际 机器学习会议 ICIVIL 同年， ((策略分析与信息系统》连出三期机器学习专辑; 1983 年， Tioga 山版社 出版了R. S. Michalski、 J. G. Carbonell 和 T. Mitchell 主编的《机器学习:一 种人工智能途径)) [Michalski et a l., 1983] ，对当时的机器学习研究工作进行了 总结; 1986 年 7 第→本机器学习专业期刊 Machine LeαTηing 创刊; 1989 年，人 1. 5 发展历程 11 工智能领域的权威期刊 Artificial Intelligence 出版机器学习专辑，刊发了当时 一些比较活跃的研究工作?其内容后来出现在 J. G. Carbonell 主编、 MIT 出 版社 1990 年的《机器学习:范型与方法>> [Carbonell , 1990] 一书中.总的来看， 二十世纪八十年代是机器学习成为一个独立的学科领域、各种机器学习技术 百花初绽的时期. R. S. Michalski 等人 [Michalski et a l., 1983] 把机器学习研究划分为"从样 例中学习" "在问题求解和规划中学习" "通过观察和发现学习" "从指令 中学习"等种类; E. A. Feigenbaum 等人在著名的《人工智能手册>> (第二卷) [Cohen and Feigenbau日1 ， 1983] 中，则把机器学习划分为"机械学习" "示教 学习" "类比学习"和"归纳学习"机械学习亦称"死记硬背式学习"，即 把外界输入的信息全部记录下来，在需要时原封不动地取出来使用?这实际上 没有进行真正的学习?仅是在进行信息存储与检索;示教学习和类比学习类似 于R. S. Michalski 等人所说的"从指令中学习"和"通过观察和发现学习" 归纳学习相当于"从样例中学习"，即从训练样例中归纳出学习结果.二十世 纪八十年代以来，被研究最多、应用最广的是"从样例中学习" (也就是广义 的归纳学习) ，它涵盖了监督学习、无监督学习等，本书大部分内容均属此范畴. 下面我们对这方面主流技术的演进做一个简单回顾. 在二十世纪八十年代，"从样例中学习"的一大主流是符号主义学习， 其代表包括决策树 (decision tree) 和基于逻辑的学习.典型的决策树学习以信 参几第 4 幸. 息论为基础，以信息娟的最小化为目标，直接模拟了人类对概念进行判定的 树形流程.基于逻辑的学习的著名代表是归纳逻辑程序设计 (Inductive Logic 这时实际是 ILP 的前身 Programming，简称 ILP) ，可看作机器学习与逻辑程序设计的交叉，它使用一 参见第 15 章 阶逻辑(即谓词逻辑)来进行知识表示，通过修改和扩充逻辑表达式(例如 Prolog 表达式)来完成对数据的归纳.符号主义学习占据主流地位与整个人工智能领域 的发展历程是分不开的.前面说过，人工智能在二十世纪五十到八十年代经历 了"推理期"和"知识期"，在"推理期"人们基于符号知识表示、通过演绎 推理技术取得了很大成就，而在"知识期"人们基于符号知识表示、通过获取 和利用领域知识来建立专家系统取得了大量成果，因此，在"学习期"的开始? 符号知识表示很自然地受到青睐.事实上 7 机器学习在二十世纪八十年代正是 被视为"解决知识工程瓶颈问题的关键"而走上人工智能主舞台的.决策树学 习技术由于简单易用，到今天仍是最常用的机器学习技术之一. ILP 具有很强 的知识表示能力，可以较容易地表达出复杂数据关系，而且领域知识通常可方 便地通过逻辑表达式进行描述，因此， ILP 不仅可利用领域知识辅助学习，还可 12 第 1 章绪论 通过学习对领域知识进行精化和增强;然而，成也萧何、败也萧何，由于表示能 力太强，直接导致学习过程面临的假设宅间太大、复杂度极高?因此，问题规模 稍大就难以有效进行学习，九十年代中期后这方面的研究相对陷入低潮. 二十世纪九十年代中期之前，"从样例中学习"的另一主流技术是基于神 经网络的连接主义学习.连接主义学习在二十世纪五十年代取得了大发展，但 因为早期的很多人工智能研究者对符号表示有特别偏爱?例如图灵奖得主 E Simon 曾断言人工智能是研究"对智能行为的符号化建模"，所以当时连接主 义的研究未被纳入主流人工智能研究范畴.尤其是连接主义自身也遇到了很大 的障碍?正如图灵奖得主 M. Minsky 丰11 S. Papert 在 1969 年指出， (当时的)神经 网络只能处理线性分类 7 甚至对"异或"这么简单的问题都处理小了. 1983 年， J. J. Hopfield 利用神经网络求解"流动推销员问题"这个著名的 NP 难题取得 重大进展，使得连接主义重新受到人们关注. 1986 年， D. E. Rumelhart 等人重 参见第 5 幸. 新发明了著名的 BP 算法，产生了深远影响.与符号主义学习能产生明确的概 念表示不同，连接主义学习产生的是"黑箱"模型，因此从知识获取的角度来 看?连接主义学习技术有明显弱点;然而，由于有 BP 这样有效的算法，使得它 可以在很多现实问题上发挥作用.事实上， BP 一直是被应用得最广泛的机器 学习算法之一.连接主义学习的最大局限是其"试错性 'p; 简单地说?其学习过 程涉及大量参数，而参数的设置缺乏理论指导，主要靠于工"调参"夸张一点 说，参数调节上失之毫厘，学习结果可能谬以千里. 二十世纪九十年代中期"统计学习" (statistical learning) 闪亮登场并 迅速占据主流舞台，代表性技术是支持向量机 (Support Vector Machine ，简称 参见第 6 章. SVM) 以及更一般的"核方法" (kernel methods). 这方面的研究早在二十世 纪六七十年代就已开始，统计学习理论 [Vapnik， 1998] 在那个时期也已打下 了基础?例如 V. N. Vapnik 在 1963 年提出了"支持向量"概念，他和 A. J. Chervonenkis 在 1968 年提出 VC 维，在 1974 年提出了结构风险最小化原则等. 但直到九十年代中期统计学习才开始成为机器学习的主流，一方面是由于有效 的支持向量机算法在九十年代初才被提出，其优越性能到九十年代中期在文 本分类应用中才得以显现;坤一方面，正是在连接主义学习技术的局限性凸显 之后，人们才把目光转向了以统计学习理论为直接支撑的统计学习技术.事实 参见习题 6.5. 上，统计学习与连接主义学习有密切的联系.在支持向量机被普遍接受后，核技 巧 (kernel trick) 被人们用到了机器学习的几乎每一个角落，核方法也逐渐成为 机器学习的基本内容之一. 有趣的是?二十一世纪初，连接主义学习又卷土重来，掀起了以"深度学 1. 6 应用现状 13 参见 5.6 节 习"为名的热潮.所谓深度学习?狭义地说就是"很多层"的神经网络.在若 干测试和竞赛上，尤其是涉及语音、图像等复杂对象的应用中，深度学习技术 取得了优越性能.以往机器学习技术在应用中要取得好性能，对使用者的要求 较高;而深度学习技术涉及的模型复杂度非常高，以至于只要下工夫"调参 把参数调节好?性能往往就好.因此，深度学习虽缺乏严格的理论基础，但它显 著降低了机器学习应用者的门槛，为机器学习技术走向工程实践带来了便利. 那么?它为什么此时才热起来呢?有两个基本原因:数据大了、计算能力强了 "过拟俨参见第 2 章 深度学习模型拥有大量参数?若数据样本少，则很容易"过拟合".如此复杂的 模型、如此大的数据样本 7 若缺乏强力计算设备，根本无法求解.恰由于人类进 入了"大数据时代 习技术焕发又一春.有趣的是，神经网络在二十世纪八十年代中期走红，与当时 Intel x86 系列微处理器与内存条技术的广泛应用所造成的计算能力、数据访 存效率比七十年代有显著提高不无关联.深度学习此时的状况，与彼时的神经 网络何其相似. 需说明的是?机器学习现在已经发展成为一个相当大的学科领域，本节仅 是管中窥豹，很多重要技术都没有谈及，耐心的读者在读完本书后会有更全面 的了解. 1. 6 应用现状 在过去二十年中，人类收集、存储、传输、处理数据的能力取得了飞速提 升，人类社会的各个角落都积累了大量数据，亟需能有效地对数据进行分析利 用的计算机算法?而机器学习恰顺应了大时代的这个迫切需求，因此该学科领 域很自然地取得巨大发展、受到广泛关注. 今天?在计算机科学的诸多分支学科领域中?无论是多媒体、图形学，还是 网络通信、软件工程，乃至体系结构、芯片设计?都能找到机器学习技术的身 影，尤其是在计算机视觉、自然语言处理等"计算机应用技术"领域，机器学 习已成为最重要的技术进步源泉之一. 机器学习还为许多交叉学科提供了重要的技术支撑.例如"生物信息 学"试图利用信息技术来研究生命现象和规律，而基因组计划的实施和基因药 物的美好愿景让人们为之心潮薛湃.生物信息学研究涉及从"生命现象"到 "规律发现"的整个过程，其间必然包括数据获取、数据管理、数据分析、仿 真实验等环节，而"数据分析"恰是机器学习技术的舞台，各种机器学习技术 已经在这个舞台上大放异彩. 14 第 1 章绪论 事实上，随着科学研究的基本手段从传统的"理论十实验"走向现在的 "理论+实验十计算"?乃至出现"数据科学"这样的提法?机器学习的重要 性日趋显著，因为"计算"的目的往往是数据分析，而数据科学的核心也恰是 通过分析数据来获得价值.若要列出目前计算机科学技术中最活跃、最受瞩 NASA-JPL 的全称是美 目的研究分支，那么机器学习必居其中. 2001 年?美国 NASA-JPL 的科学家 国航空航天局喷气推进实 7 验室，著名的"勇气"号 在 Science 杂志上专门撰文 [Mjolsness and DeCoste , 2001] 指出，机器学习对 ZJZ;;225; 科学研究的整个过程正起到越来越大的支撑作用?其进展对科技发展意义重大 2003 年， DARPA 启动 PAL 计划， i号机器学习的重要'性上升到美国国家安全的 DARPA 的全称是美国 高度来考虑.众所周知，美国最尖端科技的研究通常是由 NASA 和 DARPA 推 国防部先进研究计划局， 互联网、全球卫星定位系 进的，而这两大机构不约而同地强调机器学习的重要性，其意义不言而喻 统等都源于 DARPA 启动 的研究项目 2006 年，卡耐基梅隆大学宣告成立世界上第一个"机器学习系"，机器学 习领域奠基人之- T. Mitchell 教授出任首任系主任. 2012 年 3 月 7 美国奥巴马 政府启动"大数据研究与发展计划"，美国国家科学基金会旋即在加州大学伯 克利分校启动加强计划，强调要深入研究和整合大数据时代的三大关键技术: 机器学习提供数据分析 机器学习、云计算、众包 (crowdsourcing).显然，机器学习在大数据时代是必 能力，云计算提供数据处 理能力，众包提供数据标 不可少的核心技术，道理很简单:收集、存储、传输、管理大数据的目的，是为 记能力. 了"利用"大数据?而如果没有机器学习技术分析数据?则"利用"无从谈起. 谈到对数据进行分析利用，很多人会想到"数据挖掘" (data mining) ，这 里简单探讨一下数据挖掘与机器学习的联系.数据挖掘领域在二十世纪九十年 "数据挖掘"这个词很 早就在统计学界出现并略 代形成，它受到很多学科领域的影响，其中数据库、机器学习、统计学无疑影 带贬义，这是由于传统统 响最大 [Zhou， 2003]. 数据挖掘是从海量数据中发掘知识，这就必然涉及对"海 计学研究往往醉心于理论 的优美而忽视实际效用. 量数据"的管理和分析.大体来说，数据库领域的研究为数据挖掘提供数据管 但最近情况发生变化，越 来越多的统计学家开始关 理技术?而机器学习和统计学的研究为数据挖掘提供数据分析技术.由于统计 注现实问题，进入机器学 学界的研究成果通常需要经由机器学习研究来形成有效的学习算法，之后再进 习和数据挖掘领域- 入数据挖掘领域，因此从这个意义上说，统计学主要是通过机器学习对数据挖 掘发挥影响，而机器学习领域和数据库领域则是数据挖掘的两大支撑. 今天，机器学习己经与普通人的生活密切相关.例如在天气预报、能源勘 探、环境监测等方面，有效地利用机器学习技术对卫星和传感器发国的数据进 行分析，是提高预报和检测准确性的重要途径;在商业营销中?有效地利用机器 学习技术对销售数据、客户信息进行分析，不仅可帮助商家优化库存降低成本， 还有助于针对用户群设计特殊营销策略;……下面再举几例; 众所周知，谷歌、百度等互联网搜索引擎己开始改变人类的生活方式，例 如很多人已习惯于在出行前通过互联网搜索来了解目的地信息、寻找合适的 1.6 应用现状 15 酒店、餐馆等.美国《新闻周刊》曾对谷歌有一句话评论"它使任何人离任 何问题的答案间的距离变得只有点击一下鼠标这么远"显然，互联网搜索是 通过分析网络上的数据来找到用户所需的信息，在这个过程中，用户查询是输 入、搜索结果是输出，而要建立输入与输出之间的联系，内核必然需要机器学 习技术.事实上，互联网搜索发展至今，机器学习技术的支撑居功至伟.到了今 天，搜索的对象、内容日趋复杂，机器学习技术的影响更为明显，例如在进行 "图片搜索"时?无论谷歌还是百度都在使用最新潮的机器学习技术.谷歌、 百度、脸书、雅虎等公司纷纷成立专攻机器学习技术的研究团队，甚至直接以 机器学习技术命名的研究院，充分体现出机器学习技术的发展和应用，甚至在 一定程度上影响了互联网产业的走向 再举一例.车祸是人类最凶险的杀手之丁全世界每年有上百万人丧生车 轮?仅我国每年就存约十万人死于车祸.由计算机来实现自动汽车驾驶是一个 理想的方案，因为机器上路时可以确保不是新手驾驶、不会波劳驾驶，更不会 酒后驾驶，而且还有重要的军事用途.美国在二十世纪八十年代就开始进行这 例如著名机器学习教科 方面研究.这里最大的困难是无法在汽车厂里事先把汽车上路后所会遇到的所 书 [Mitchell. 1997]4.2 节介 绍了二十世纪九十年代早 有情况都考虑到、设计出处理规则并加以编程实现，而只能根据上路时遇到的 期利用神经网络学习来控 制自动驾驶车的 ALVINN 情况即时处理.若把车载传感器接收到的信息作为输入?把方向、刹车、油门 系统 的控制行为作为输出，则这里的关键问题怆可抽象为→个机器学习任务.2004 年 3 月，在美国 DARPA 组织的自动驾驶车比赛中 3 斯坦福大学机器学习专家 S. Thrun 的小组研制的参赛车用 6 小时 53 分钟成功走完了 132 英里赛程获得 冠军.比赛路段是在内华达州西南部的山区和沙漠中 7 路况相当复杂，在这样的 路段上行车即使对经验丰富的人类司机来说也是一个挑战. S. Thrun 后来到谷 歌领导自动驾驶牢项目团队.值得…提的是自动驾驶车在近几年取得了飞跃 式发展，除谷歌外?通用、奥迪、大众、宝马等传统汽车公司均投入巨资进行 研发，目前已开始有产品进入市场. 2011 年 6 月，美国内华达州议会通过法案? 成为美国第一个认可自动驾驶车的州，此后，夏威夷州和佛罗里达州也先后通 过类似法案，自动驾驶汽车可望在不久的将来出现在普通人的生活中，而机器 学习技术则起到了"司机"作用. 机器学习技术甚至己影响到人类社会政治生活. 2012 年美国大选期间，奥 巴马磨下有一支机器学习团队，他们对各类选情数据进行分析，为奥巴马提示 下一步竞选行葫.例如他们使用机器学习技术分析社交网络数据，判断出在总 统候选人第一次辩论之后哪些选民会倒戈，并根据分析的结果开发出个性化宣 传策略，能为每位选民找出一个最有说服力的挽留理由;他们基于机器学习模 16 第 1 章绪论 型的分析结果提示奥巳马应去何处开展拉票活动，有些建议甚至让专业竞选顾 问大吃一惊，而结果表明去这些地方大有收获.总统选举需要大量金钱，机器 学习技术在这方面发挥了奇效.例如，机器学习模型分析出，某电影明星对某 地区某年龄段的特定人群很有吸引力?而这个群体很愿意出高价与该明星及奥 巴马共进晚餐........果然，这样一次筹资晚宴成功募集到 1500 万美元;最终，借 助机器学习模型，奥巴马筹到了创纪录的 10 亿美元竞选经费.机器学习技术不 仅有助于竞选经费"开源"还可帮助"节流 "7 例如机器学习模型通过对不 同群体选民进行分析，建议购买了→些冷门节目的广告时段，而没有采用在昂 贵的黄金时段购买广告的传统做法，使得广告资金效率相比 2008 年竞选提高 了 14%; ……胜选后， ((时代》周刊专门报道了这个被奥巴马称为"竞选核武 器"、由半监督学习研究专家R. Ghani 领导的团队. 值得一提的是，机器学习备受瞩目当然是由于它已成为智能数据分析技术 的创新源泉 7 但机器学习研究还有另一个不可忽视的意义，即通过建立一些关 于学习的计算模型来促进我们理解"人类如何学习"例如， P. Kanerva 在二 十世纪八十年代中期提出 SDM (Sparse Distributed Memory)模型 [Kanerva， 1988] 时并没有刻意模仿脑生理结构，但后来神经科学的研究发现， SDM 的稀 疏编码机制在视觉、昕觉、嗅觉功能的脑皮层中广泛存在，从而为理解脑的某 些功能提供了一定的启发.自然科学研究的驱动力归结起来无外是人类对宇宙 本源、万物本质、生命本性、自我本识的好奇，而"人类如何学习"无疑是一 个有关自我本识的重大问题.从这个意义上说，机器学习不仅在信息科学中占 有重要地位，还具有一定的自然科学探索色彩. 1. 7 阅读材料 [Mitchell , 1997] 是第一本机器学习专门性教材， [Duda et al., 2001; Alc paydin , 2004; Flach , 2012] 都是出色的入门读物. [Hastie et al. , 2009] 是很好 的进阶读物， [Bishop , 2006] 也很有参考价值?尤其适合于贝叶斯学习偏好者. [Shalev-Shwartz and Ben-David , 2014] 则适合于理论偏好者. [Witten et 此， WEKA 是著名的免费 2011] 是基于 WEKA 撰写的入门读物 7 有助于初学者通过 WEKA 实践快速掌 机器学习算法程序库，由 新西兰 Wail咀t。大学研 握常用机器学习算法. 究人员基于 JAVA 开发 ι http://www.cs.waikato. 本书1. 5 和1. 6 节主要取材于[周志华， 2007]. ((机器学习:一种人工智能 ac.nz/ml/weka j. 途径)) [Michalski et a l., 1983] 汇集了 20 位学者撰写的 16 篇文章，是机器学习 早期最重要的文献.该书出版后产生了很大反响， Morgan Kaufmann 出版社后 来分别于 1986 年和 1990 年出版了该书的续篇，编为第二卷和第二卷. ((人工 1.7 阅读材料 17 智能手册》系列是图灵奖得主 E. A. Feigenbau日1 与不同学者合作编写而成，该 书第三卷 [Cohen and Feigenbaum , 1983] 对机器学习进行了讨论，是机器学习 早期的重要文献. [Dietterich , 199可对机器学习领域的发展进行了评述和展望. 早期的很多文献在今天仍值得重视，一些闪光的思想在相关技术进步后可能焕 发新的活力，例如近来流行的"迁移学习" (transfer learning) [Pan and Yang , 2010] ，恰似"类比学习" (1earning by analogy) 在统计学习技术大发展后的升 级版;红极一时的"深度学习" (deep learning) 在思想上井未显著超越二十世 深度学习参见 5.6 节 纪八十年代中后期神经网络学习的研究. 机器学习中关于概念学习的研究开始很早，从中产生的不少思想对整个 领域都有深远影响.例如作为主流学习技术之一的决策树学习，就起源于关 于概念形成的树结构研究 [Hu日.t and Hovlar吨 1963]. [Winston , 1970] ;在著 名的"积木世界"研究中，将概念学习与基于泛化和特化的搜索过程联系起 来. [Simon and Lea , 1974] 较早提出了"学习"是在假设空间中搜索的观点. [Mitchell , 197句稍后提出了版本空间的概念.概念学习中有很多关于规则学习 规则学习参见第 15 章 的内容. 奥卡姆剃刀原则主张选择与经验观察一致的最简单假设 7 它在自然科学如 物理学、天文学等领域中是一个广为沿用的基础性原则，例如哥白尼坚持"日 心说"的理由之一就是它比托勒密的"地心说"更简单且符合天文观测.奥 卡姆剃刀在机器学习领域也有很多追随者 [Blumer et a l., 1996]. 但机器学习 中什么是"更简单的"这个问题一直困扰着研究者们，因此，对奥卡姆剃刀在 机器学习领域的作用一直存在着争议阳"ebb ， 1996; Domingo民 1999]. 需注意 的是，奥卡姆剃刀并非科学研究中唯一可行的假设选择原则，例如古希腊哲学 家伊壁坞鲁(公元前341年一前270年)提出的"多释原则" (principle of multiple explanations) ，主张保留与经验观察一致的所有假设 [Asmis ， 1984]，这与集成 集成学习参见第 8 章. 学习 (ensemble learning) 方面的研究更加吻合. 机器学习领域最重要的国际学术会议是国际机器学习会议 (ICML) 、国际 神经信息处理系统会议 (NIPS) 和国际学习理论会议 (COLT) ，重要的区域性会 议主要有欧洲机器学习会议 (ECML) 和亚洲机器学习会议 (ACML); 最重要的 国际学术期刊是 Journal of Machine Learning Research 和 Machine Learning. 人工智能领域的重要会议如 IJCAI、 AAAI 以及重要期刊如 Art侨c归1 Intelli- gence 、 Journal of Art听cial Intelligence Reseαrch， 数据挖掘领域的重要会议 如 KDD 、 ICDM 以及重要期刊如 ACM Transactions on Knowledge Discovery fromDα归、 Dαtα Mining and Knowledge Discovery， 计算机视觉与模式识别 18. 第 1 章绪论 领域的重要会议如 CVPR 以及重要期刊如 IEEE Transactions on Pattem Analysis and Machine Intelligence， 神经网络领域的重要期刊如 Neural Com- putation 、 IEEE Transaιtions on Neural Networks αηd Leαming 8ystems 等 也经常发表机器学习方面的论文.此外，统计学领域的重要期刊如 Annals 旷 8tαtistics 等也常有关于统计学习方面的理论文章发表. 国内不少书籍包含机器学习方面的内容，例如[陆汝铃， 1996]. [李航， 2012] 是以统计学习为主题的读物.国内机器学习领域最主要的活动是两年一次 的中国机器学习大会 (CCML) 以及每年举行的"机器学习及其应用"研讨 会 (MLA); 很多学术刊物都经常刊登有关机器学习的论文. 习题 19 习题 1.1 表1. 1 中若只包含编号为 1 和 4 的两个样例?试给出相应的版本空间. 1. 2 与使用单个合取式来进行假设表示相比，使用"析合范式"将使得假 析合范式即多个合取式 设空间具有更强的表示能力.例如 的析取z 好瓜件((色泽=们(根蒂=蜷缩) ^ (敲声= *)) v ((色泽=乌黑) ^ (根蒂=们(敲声=沉闷)) , 会把"(色泽=青绿)八(根蒂=蜷缩)八(敲声=清脆)"以及"(色泽= 乌黑) ^ (根蒂=硬挺)八(敲声=沉闷)"都分类为"好瓜"若使用最 提示注意冗余情况， 多包含 k 个合取式的析合范式来表达表1. 1 西瓜分类问题的假设空 如 (A= α) V (A = *) 与 (A = *)等价. 间 7 试估算共有多少种可能的假设. I!p 不存在训练错误为 0 1. 3 若数据包含噪声，则假设空间中有可能不存在与所有训练样本都一致 的假设 的假设在此情形下，试设计一种归纳偏好用于假设选择. 1.4* 本章1. 4 节在论述"没有免费的午餐"定理时，默认使用了"分类错 误率"作为性能度量来对分类器进行评估.若换用其他性能度最孔则 式(1. 1) 将改为 Eote(i:，αIX，!) = 2二三二 p(x)e(h(x) ，J (x))P(h I X， 刻， h æε x-x 试证明"没有免费的午餐定理"仍成立. 1. 5 试述机器学习能在互联网搜索的哪曲环节起什么作用. 20 第 1 章绪论 参考文献 陆汝铃. (1996). 人工智能(下册).科学出版社，北京. 周志华. (2007). "机器学习与数据挖掘"中国计算机学会通讯， 3(12):35-44. 李航. (2012). 统计学习方法.清华大学出版社，北京. Alpaydin , E. (2004). Introduction to Machine Learning. MIT Press , Cambridge , MA. Asinis , E. (1984). Epicurus' Sc的tt侨c Method. Cornell University Press , It haca , NY. Bishop , C. M. (2006). Pattern Recognition and Machine Learnir协 Springer ， New York , NY. Blumer , A. , A. Ehrenfeucht , D. Haussler , and M. K. Warml灿. (1996). "咱 - Oc­ cam'、s 阳 ra 缸zor 巳 r." Ca 缸，r协 b onell ， J. G. , ed. (1990). Machine Learning: Pαradigms and Methods. MIT Press , Cambridge , MA. Cohen , P. R. and E. A. Feige巾au日1 ， eds. (1983). The H，α ndbook of Art~卢cial Intelligence , volume 3. William Kaufmann , New York , NY. Dietterich, T. G. (1997). "Machine learni吨 research: Four current directions." AIM，α.gazine， 18(4):97~136. Domi吨os ， P. (1999). "The role of Occam's razor in knowledge discovery." Dαtα Mining and K noω ledge Discovery, 3(4) 油9-425. Duda , R. 0. , P. E. Hart , and D. G. Stork. (2001). Pattern Classi.声cαtion， 2nd edition. John 飞iViley & Sons , New York , NY. Flach, P. (2012). Machine Leαrning: The Art and Science of Algo时thms that Mα ke Sense of Datα. Cambridge University Press , Cambridge , UK. Hand ，且， H. Mannila , and P. Smyth. (2001). Principles of Dαtα Mining. MIT Press , Cambridge , MA. Hastie , T. , R. Tibshira风 and J. Friedman. (2009). The Elements of Stαtistical Learning, 2nd edition. Springer , New York , NY. Hunt , E. G. and D. 1. Hovland. (1963). "Programming a model of human con- cept ，for 岛口ma 旧，tion." 1丑 Compu 时t化 er， 附 8αη 叫 d Thought (E. Feige由au日1 and J. Feldma几 eds.) , 310-325 , McGraw Hill , New York , NY. 参考文献 21 Kanerva , P. (1988). Spαrse Distributed Memory. MIT Press , Cambridge , MA. Michalski , R.丘， J. G. Carbonell , and T. M. Mitchell , eds. (1983). Machine Learning: An A付侨cial Intelligence Approαch. Tioga , Palo Alto , CA. Mitchell , T. (1997). Mαchine Learning. McGraw Hill , New York , NY. Mitchell , T. M. (1977). "Version spaces: A candidate elimination approach to rule learning." In Proceedings of the 5th Intern αtional Joint Confe陀 nce on A付侨cial Intelligence (IJCA刀， 305-310 , Cambridge , MA. Mjolsne盹 E. and D. DeCoste. (2001). "Machine learni吨 for science: State of the art and future prospects." Science , 293(5537):2051-2055. Pan , S. J. and Q. Yang. (2010). 咀 survey of transfer learning." IEEE Trαns­ αctions on Knowledge αnd Datα Engineering， 22(10):1345-1359. Shalev-Shwartz , S. and S. Ben-David. (2014). Understanding Machine Learn- ing. Cambridge University Press , Cambridge , UK. Simon , H. A. and G. Lea. (1974). "Problem solving and rule induction: A unified view." In K noω ledge and Cognition (L. W. Gre腿， ed.) , 105-127, Erlbaum , New York , NY. Vapnik , V. N. (1998). Stαtistical Learning Theo啡 Wiley， New York , NY. Webb , G. 1. (1996). "F\川her experimental evidence against the utility of Oc- cam's razor." Journal of Art~卢 cial Intelligence Research, 43:397-417. Winston , P. H. (1970). "Learning structural descriptions from examples." Tech- nical Report AI-TR-231 , AI Lab , MIT , Cambridge , MA. Witten ,1. 且， E..Frank , and M. A. Hall. (2011). Dαtα Mining: Pmctical Ma- chine Learing Tools αnd Techniques , 3rd edition. Elsevier , Burlington, MA. Wolpe叽 D. H. (1996). "The lack of a p巾ri distinctions between learning al- gorithms." Neural Computatio风 8(7) :1341-1390. Wolpert , D. H. and W. G. Macready. (1995). "No free lunch theorems for search." Technical Report SFI-TR-05-010 , Santa Fe Institute , Sante Fe , NM. Zhou , Z.-H. (2003). "Three perspectives of data m扭扭g." Art~声ciallntelligence， 143(1):139-146. 22 第 1 章绪论 休息一会儿 小故事: "机器学习"名字的由来 1952 年，阿瑟·萨缪尔 (Arthur Samuel , 1901- 1990) 在 IBM 公司研制了一个西洋跳棋程序，这 个程序具有自 学习 能力， 可通过对大量棋局的分析逐 渐辨识 出当前局 面 下的 "好 棋"和"坏 棋'\ 从而不断提高 弈棋 水平 ，并很 这个跳棋程序实质上使 快就下 赢了 萨缪尔自己 1956 年，萨 缪尔应约 翰·麦 卡锡 用了强化学习技术，参见 第 16 章. (John McCarthy, "人工智能之父" , 1971 年图灵奖得主 )之邀， 在标志着 人 工智能学科诞生的达特茅斯会议上介绍这项工作.萨 缪尔发明了"机器学习" 这个词，将其定义为"不显式编程地赋予计算机能力的研究领域"他的文 章 "Some studies in machine learning using the game of checkers" 1959 年在 IBMJournal 正式发表后 ， 爱德华·费根鲍姆 (Edward Feigenbau日1，"知识工 程之父" ， 1994 年图灵 奖得 主)为编写其巨著 Computers and Thought， 在 1961 年邀请萨缪尔提供 一 个该程序最好的对弈实例.于是，萨缪尔借机 向康涅 狄格 州的跳棋冠军、当时全美排名第四的棋手发起了挑战，结果萨缪尔程序获胜， 在当时引起轰动. 事实上，萨缪尔跳棋程序不仅在人王智能领域产生了重大 影 响，还影响到 整个计算机科学的发展.早期计算机科学研究认为，计算机不可能完成事先没 有显式编程好的任务，而萨缪尔跳棋程序 否证了 这个假设. 另外，这个程序是最 早在计算机上执行非数值计算任务的程序之一，其逻辑指令设计思想极大地影 响 1 IBM 计算机的指令集， 并很快被其他计 算机 的设计者采用.  第2章 模型评估与选择 2.1 经验误差与过拟合 通常我们把分类错误的样本数占样本总数的比例称为"错误率" (error rate) ，即如果在 m 个样本中有 α 个样本分类错误，则错误率 E= α1m; 相应的， 精度常写为百分比形式 1 一 α1m 称为"精度" (acc旧acy) ，即"精度 =1 一错误率"更一般地，我们把 。- -;:;) x 100% 学习器的实际预测输出与样本的真实输出之间的差异称为"误差" (error) , 这里所说的"误差"均 学习器在训练集上的误差称为"训练误差" (training error) 或"经验误 指误差期望- 差" (empirical error) ，在新样本上的误差称为"泛化误差" (generalization error). 显然，我们希望得到泛化误差小的学习器.然而，我们事先并不知道新 在后面的章节中将介绍 样本是什么样，实际能做的是努力使经验误差最小化.在很多情况下，我们可以 不同的学习算法如何最小 化经验误差 学得一个经验误差很小、在训练集上表现很好的学习器，例如甚至对所有训练 样本都分类正确，即分类错误率为零，分类精度为 100% ，但这是不是我们想要 的学习器呢?遗憾的是，这样的学习器在多数情况下都不好. 我们实际希望的，是在新样本上能表现得很好的学习器.为了达到这个 目的，应该从训练样本中尽可能学出适用于所有潜在样本的"普遍规律"，这 样才能在遇到新样本时做出正确的判别.然而，当学习器把训练样本学得"太 好"了的时候，很可能巳经把训练样本自身的一些特点当作了所有潜在样本都 会具有的一般性质，这样就会导致泛化性能下降这种现象在机器学习中称为 过拟合亦称"过自己" "过拟合" (overfitting). 与"过拟合"相对的是"欠拟合" (underfitting) ，这 欠拟合亦称"欠配" 是指对训练样本的一般性质尚未学好.图 2.1 给出了关于过拟合与欠拟含的一 个便于直观理解的类比. 有多种因素可能导致过拟合，其中最常见的情况是由于学习能力过于强大， 学习能力是否"过于强 以至于把训练样本所包含的不太一般的特性都学到了，而欠拟合则通常是由 大，是由学习算法和数 据内涵共同决定的 于学习能力低下而造成的欠拟合比较容易克服，例如在决策树学习中扩展分 支、在神经网络学习中增加训练轮数等，而过拟合则很麻烦.在后面的学习中 我们将看到，过拟合是机器学习面临的关键障碍，各类学习算法都必然带有一 些针对过拟合的措施;然而必须认识到，过拟合是无法彻底避免的，我们所能做 的只是"缓解'气或者说减小其风险.关于这一点，可大致这样理解:机器学习 面临的问题通常是 NP 难甚至更难，而有效的学习算法必然是在多项式时间内 24 第 2 章模型评估与选择 过拟合模型 分类结果 : 树叶 训练样本 → 不是树叶 新样本 ( 误以为树叶必 须有铅齿 ) 欠拟合模型分类结 果. →是树叶 (误 以为绿色 的都是树 叶) 图 2.1 过拟合 、欠拟合的 直观类比 运行完成 ，若可彻底避免过拟合， 则通过经验误差最小化就能获最优解，这 就意 味着我们 构造性地证 明了 " P=NP" ;因此7 只要 相信 "p 并 NP " ，过拟合就 不 可避免 在现实任务中，我们往往有 多 种 学习算沾 了IJ供选择 ，甚至对同 - 个 学习算 法，当使用不同的参数配置 时 ?也会产生不 同的模 型. 那么，我们 该选用 哪 -个 学习算法、使用哪 一种参数配置呢?这就是机器学习 中的" 模型选择" (model selection) 问题.理想的解决方案当然是对候选模型的泛化误差进行 评估 7 然后 选择泛化误差最 小的那个模型.然而如上面所讨 论的，我们无法直接获得泛化 误差，而训练误差又由于过拟合现象的存在而不适合作为标准，那么，在现实中 如何进行模型评估与选择呢? 2.2 评估方法 通常， 我们 可通过实验测试来对 学习器的泛化误差进行评估并进而做出 选 在现实任务中往往还会 择 为此， 需使用一个 "测试集 " (testing set)来测试学习器对新样本 的判别 能 考虑时间开信 销、可解释性等方面的因 力，然后 以 测试集上的"测试误差" (testing error) 作为 泛化误差的 近似通常 素，这里暂且只考虑泛化 误差 我们假设测试样本也是 从样 本真实分布 中独立同分布采样 而得但需 注意 的 是，测试集应该尽可能 与训练集互斥， 即测试样本尽量不在 训练集 中出现、未 在训 练过程 中使用过. 测试样本为什么要尽可能不出现在 训练集中呢?为理解这一 点 ，不妨考虑 这样一个场景:老师出了 10 道习题供同学们 练习 ，考试时老师又用 同样的这 10 道题作为试题，这个考试成绩 能否有效反 映出同学们 学得好不好呢?答案是否 定 的，可能有的同学只 会做这 10 道题却能得高分.回到我们的问题上来，我们 2.2 评估方法 25 希望得到泛化性能强的模型?好比是希望同学们对课程学得很好、获得了对所 学知识"举一反三"的能力;训练样本相当于给同学们练习的习题，测试过程 则相当于考试.显然，若测试样本被用作训练了，则得到的将是过于"乐观"的 估计结果. 可是，我们只有一个包含 m 个样例的数据集 D={(叫 ， Yl) , (X2 ,Y2) , … 7 (Xm ， Ym)} ， 既要训练，又要测试，怎样才能做到呢?答案是:通过对 D 进行适当 的处理，从中产生出训练集 S 和测试集 T. 下面介绍儿种常见的做法. 2.2.1 留出法 "留出法" (hold-out) 直接将数据集 D 划分为两个互斥的集合?其中一个 集合作为训练集 5 ，另一个作为测试集 T， 即 D=BUT ， 5 门 T= 正~.在 S 上训 练出模型后，用 T 来评估其测试误差，作为对泛化误差的估计. 以二分类任务为例，假定 D 包含 1000 个样本，将其划分为 8 包含 700 个样 本 ， T 包含 300 个样本，用 S 进行训练后，如果模型在 T 上有 90 个样本分类错 误，那么其错误率为 (90/300) x 100% 口 30% ，相应的，精度为 1- 30% = 70%. 需注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免 困数据划分过程引入额外的偏差而对最终结果产生影响，例如在分类任务中 至少要保持样本的类别比例相似.如果从来样 (sampling) 的角度来看待数据 集的划分过程，则保留类别比例的采样方式通常称为"分层采样" (stratified sampling). 例如通过对 D 进行分层采样而获得含 70% 样本的训练集 S 和含 30% 样本的测试集 T， 若 D 包含 500 个正例、 500 个反例，则分层采样得到的 S 应包含 350 个正例、 350 个反例?而 T 则包含 150 个正例和 150 个反例;若 S、 T 中样本类别比例差别很大，则误差估计将由于训练/测试数据分布的差异 而产生偏差. 另一个需注意的问题是，即使在给定训练/测试集的样本比例后，仍存在多 参见习题 2.1 种划分方式对初始数据集 D 进行分割.例如在上面的例子中，可以把 D 中的样 本排序，然后把前 350 个 E 例放到训练集中，也可以把最后 350 个正例放到训 练集中，……这些不同的划分将导致不同的训练/测试集，相应的?模型评估的 结果也会有差别.因此?单次使用留出法得到的估计结果往往不够稳定可靠，在 使用留出法时，一般要采用若干次随机划分、重复进行实验评估后取平均值作 为留出法的评估结果.例如进行 100 次随机划分，每次产生一个训练/测试集用 同时可得估计结呆的标 于实验评估， 100 次后就得到 100 个结果?而留出法返回的则是这 100 个结果的 准差， 平均. 此外，我们希望评估的是用 D 训练出的模型的性能，但留出法需划分训 26 第 2 章模型评估与选择 练/测试集7 这就会导致一个窘境:若令训练集 S 包含绝大多数样本7 则训 练出 可从"偏差-方差" (参 见 2.6 节)的 角度 来理解 的模型可能更接近于用 D 训 练 出的模型， 但由 于 T 比较小 ，评估 结果可能不够 测试集小 时 ，坪千古结采的 稳定准确 ;若令测试集 T 多包含一些样本， 则训 练集 S 与 D 差别更大了，被评 方差较大， 训练集小 时，评 估结果的偏差较大 估的模型与用 D 训练出 的模型相比可能有较大差别?从而 降低了评估结果的保 一般 而言，测试集 至少 真性 (fidelity) 这个问题没有完美 的解决方案 ， 常见做法是将大约 2/3 rv 4/5 的 应含 30 个样例 [Mitchell ， 样本用于训练，剩余样本用 于测试. 1997] 2.2.2 交叉验证法 "交叉验证法" (cross validation) 先 将数据 集 D 划 分为 k 个大 小相 似的 互斥子集， 即 D = D 1 U D2υ... U D k, Di n Dj = ø (í 手 j ). 每个子集 Di 都 尽可 能 保持数据分布的 一 致性 ，即从 D 中 通过 分层采样得到. 然 后，每次用 k-1 个子集 的并集作 为训练集 ?余 F 的那个子集作 为 测 试集;这样就可获得 k 组训练/测 试集，从而可 进行 k 次训练和 测试? 最终返回的是 这 k 个测试 结果 的均值 显然，交叉验证法评估结果的 稳定 性 和保真 性在很大程度 上取决于 k 的取值 ，为强调这一点 ，通常把交叉验证法称为 " k 折 交叉验证" (k-fold cross 亦称 "k 倍交又验证" validat ion). k 最常用 的取值是 10 ，此时 称为 1 0 折交叉验 证 ; 其他常用 的 k 值 有 5、 20 等.图 2.2 给出了 10 折交叉验证的 示意 图. D G ID1 1D2 1 31D4 1Ds ID6 1D71 D81Dg IDlOI D 训练集 测试集 | 叭 队 I D31 马 IDs I D6 1 D71 D81 D91 ~ →测 试结采 1 1 |叭 队 I D31乌 IDs I D6 I D7 1 D81 DlOI 巨~ →测试结果 2 廿生返回 r r 结果 ID2 1马 I D4 IDsID6ID7ID8IDgID lO l 囚 →测 议结果1 0 J 图 2.2 10 折交又验证示 意图 与 留出法相似，将数据集 D 划 分 为 k 个子集同样存在多种 划 分方式.为 减 小 因样本划分不同 而 引入的差别 ， k 折交叉验证通常 要随机使用不同的划分 重复 p 次?最终的评估 结果是这 p 次 k 折交叉验证 结果 的均值，例如常 见的有 ({ 10 次 10 折交又验 "10 次 10 折交叉验证 证法"与 " 100 次留 出 法"都是进行了 100 次训 {假 院定数据集 D 中包含 m 个样本3 若令 k=m ， 则得 到了交叉验证法的 一 练/，，1'] i式 个特例:留 一法 (Leave- One-Ot比，简称 LOO). 显然 ， 留 一 法不受随机样本 划分 2.2 评估方法 27 方式的影响，因为 m 个样本只有唯一的方式划分为 m 个子集一一每个子集包含 一个样本;留一法使用的训练集与初始数据集相比只少了一个样本，这就使得 在绝大多数情况下，留一法中被实际评估的模型与期望评估的用 D 训练出的模 型很相似.因此，留一法的评估结果往往被认为比较准确.然而，留一法也有其 缺陷:在数据集比较大时，训练 m 个模型的计算开销可能是难以忍受的(例如数 据集包含 1 百万个样本，则需训练 1 百万个模型)，而这还是在未考虑算法调参 参见习题 2.2 的情况下.另外，留一法的估计结果也未必永远比其他评估方法准确;"没有免 NFL 定理参见1. 4 节 费的午餐"定理对实验评估方法同样适用. 2.2.3 自助法 我们希望评估的是用 D 训练出的模型.但在留出法和交叉验证法中，由于 保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比 D 小，这 关于样本复杂度与泛化 必然会引入一些因训练样本规模不同而导致的估计偏差.留一法受训练样本规 性能之间的关系，参见第 12 章. 模变化的影响较小，但计算复杂度又太高了.有没有什么办法可以减少训练样 本规模不同造成的影响，同时还能比较高效地进行实验估计呢? "自助法" (bootstrapping) 是一个比较好的解决方案，它直接以自助采样 Bootstrap本意是"解靴 法 (bootstrap sampling) 为基础 [Efron and Tibshirani , 1993]. 给定包含 m 个样 带"这里是在使用德国 18 世纪文学作品《吹牛 本的数据集 D ， 我们对它进行采样产生数据集 D': 每次随机从 D 中挑选一个 大王历险记》中解靴带自 助的典故，因此本书译为 样本 7 将其拷贝放入 DF' 然后再将该样本放回初始数据集 D 中，使得该样本在 "自助法" 自助采样亦 下次采样时仍有可能被采到;这个过程重复执行 m 次后?我们就得到了包含 m 称"可重复采样"或"有 放回采样" 个样本的数据集 DF ，这就是自助采样的结果.显然 ， D 中有一部分样本会在 D' 中多次出现，而另一部分样本不出现.可以做一个简单的估计，样本在 m 次采 样中始终不被采到的概率是 (1 一去 )m ， 取极限得到 已是自然常数 (2.1) 即通过自助来样，初始数据集 D 中约有 36.8% 的样本未出现在采样数据集 D' 气"表示集合;或法 中.于是我们可将 D' 用作训练、集 ， D\D' 用作测试集;这样?实际评估的模型与 期望评估的模型都使用 m 个训练、样本，而我们仍有数据总量约 1/3 的、没在训 练集中出现的样本用于测试.这样的测试结果，亦称"包外估计" (out-of-bag estimate). 自助法在数据集较小、难以有效划分训练/测试集时很有用;此外，自助法 能从初始数据集中产生多个不同的训练集，这对集成学习等方法有很大的好处. 集成学习参见第 8 章 然而，自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差.因 28 第 2 章模型评估与选择 此，在初始数据量足够时，留出法和交叉验证法更常用一些. 2.2.4 调参与最终模型 大多数学习算法都有些参数 (parameter) 需要设定，参数配置不同，学得模 型的性能往往有显著差别.因此，在进行模型评估与选择时，除了要对适用学习 算法进行选择，还需对算法参数进行设定，这就是通常所说的"参数调节"或 简称"调参" (parameter tuning). 读者可能马上想到，调参和算法选择没什么本质区别:对每种参数配置都 训练出模型，然后把对应最好模型的参数作为结果.这样的考虑基本是正确的， 但有一点需注意:学习算法的很多参数是在实数范围内取值，因此，对每种参数 配置都训练出模型来是不可行的.现实中常用的做法?是对每个参数选定一个 范围和变化步长，例如在 [0 ， 0.2] 范围内以 0.05 为步长，则实际要评估的候选参 数值有 5 个，最终是从这 5 个候选值中产生选定值.显然，这样选定的参数值往 往不是"最佳"值，但这是在计算开销和性能估计之间进行折中的结果，通过 这个折中，学习过程才变得可行.事实上，即便在进行这样的折中后，调参往往 仍很困难.可以简单估算一下:假定算法有 3 个参数，每个参数仅考虑 5 个候选 值，这样对每一组训练/测试集就有 53 = 125 个模型需考察;很多强大的学习算 法有大量参数需设定，这将导致极大的调参工程量，以至于在不少应用任务中， 例如大型"深度学习" 参数调得好不好往往对最终模型性能有关键性影响. 模型甚至有上百亿个参数. 给定包含 m 个样本的数据集 D ，在模型评估与选择过程中由于需要留出 一部分数据进行评估测试，事实上我们只使用了一部分数据训练、模型.因此，在 模型选择完成后，学习算法和参数配置己选定，此时应该用数据集 D 重新训练 模型.这个模型在训练过程中使用了所有 m 个样本，这才是我们最终提交给用 户的模型. 另外，需注意的是，我们通常把学得模型在实际使用中遇到的数据称为测 试数据，为了加以区分，模型评估与选择中用于评估测试的数据集常称为"验 证集" (validation set). 例如，在研究对比不同算法的泛化性能时，我们用测试 集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分 为训练集和验证集，基于验证集上的性能来进行模型选择和调参. 2.3 性能度量 对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需 要有衡量模型泛化能力的评价标准，这就是性能度量 (performance measure). 2.3 性能度量 29 性能度量反映了任务需求，在对比不同模型的能力时，使用不同的性能度量往 往会导致不同的评判结果;这意味着模型的"好坏"是相对的，什么样的模型 是好的?不仅取决于算法和数据，还决定于任务需求. 聚类的性能度量参见第 在预测任务中?给定样例集 D = {(X1 , Y1) , (X2 ， 的)，... , (Xm, Ym)} ， 其中饥 9章 是示例 Xi 的真实标记.要评估学习器 f 的性能，就要把学习器预测结果 I(x) 与真实标记 υ 进行比较. 回归任务最常用的性能度量是"均方误差" (mean squared error) E(川)=二 (f (Xi) 一切)2 (2.2) 更一般的，对于数据分布 Ð 和概率密度函数 p(.) ， 均方误差可描述为 E (f ;Ð) = i~Ð 州一的(x)dx (2.3) 本节下面主要介绍分类任务中常用的性能度量. 2.3.1 错误率与精度 本章开头提到了错误率和精度?这是分类任务中最常用的两种性能度量， 既适用于二分类任务，也适用于多分类任务.错误率是分类错误的样本数占样 本总数的比例，精度则是分类正确的样本数占样本总数的比例.对样例集 D ， 分 类错误率定义为 EU;D)=tEM) 并执) (2.4) 精度则定义为 acc (f; D) 主兰1I (f (Xi) = 饥) (2.5) 1- E (f ;D). 旦王‘般的，对于数据分布 Ð 和概率密度函数 p(.) ， 错误率与精度可分别描 述为 E(fiD)ZLJfW 川)dx ,