参考文献 21 Kanerva,P.(1988).Sparse Distributed Memory.MIT Press,Cambridge,MA. Michalski,R.S.,J.G.Carbonell,and T.M.Mitchell,eds.(1983).Machine Learning:An Artificial Intelligence Approach.Tioga,Palo Alto,CA. Mitchell,T.(1997).Machine Learning.McGraw Hill,New York,NY. Mitchell,T.M.(1977)."Version spaces:A candidate elimination approach to rule learning."In Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI),305-310,Cambridge,MA. Mjolsness,E.and D.DeCoste.(2001)."Machine learning for science:State of the art and future prospects."Science,293(5537):2051-2055. Pan,S.J.and Q.Yang.(2010)."A survey of transfer learning."IEEE Trans- actions on Knowledge and Data 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 Knowledge and Cognition(L.W.Gregg,ed.),105-127, Erlbaum,New York,NY. Vapnik,V.N.(1998).Statistical Learning Theory.Wiley,New York,NY. Webb,G.I.(1996)."Further experimental evidence against the utility of Oc- cam's razor."Journal of Artificial 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,I.H.,E.Frank,and M.A.Hall.(2011).Data Mining:Practical Ma chine Learing Tools and Techniques,3rd edition.Elsevier,Burlington,MA. Wolpert,D.H.(1996)."The lack of a priori distinctions between learning al- gorithms."Neural Computation,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 mining."Artificial Intelligence, 143(1):139-146
22 第1章绪论 休息一会儿 小故事：“机器学习”名字的由来 1952年，阿瑟，萨缪尔(Arthur Samuel,.1901一1990) 在BM公司研制了一个西洋跳棋程序，这个程序具有自 学习能力，可通过对大量棋局的分析逐渐辨识出当前局面 下的“好棋”和“坏棋”，从而不断提高奔棋水平，并很 这个跳棋程序实质上使 用了强化学习技术，泰见 快就下赢了萨缪尔自己.1956年，萨缪尔应约翰·麦卡锡 第16章， (John MeCarthy,“人工智能之父”，1971年图灵奖得主)之邀，在标志着人 工智能学科诞生的达特茅斯会议上介绍这项工作，萨缪尔发明了“机器学习” 这个词，将其定义为“不显式编程地赋予计算机能力的研究领城”，他的文 章“Some studies in machine learning using the game of checkers'”l959年在 IBM Journal正式发表后，爱德华，费根鲍姆(Edward Feigenbaum,“知识工 程之父”，1994年图灵奖得主)为编写其巨著Computers and Thought,,在1961 年邀请萨缪尔提供一个该程序最好的对弈实例.于是，萨缪尔借机向康涅狄格 州的跳棋冠军、当时全美排名第四的棋手发起了挑战，结果萨缪尔程序获胜 在当时引起轰动 事实上，萨缪尔跳棋程序不仅在人工智能领城产生了重大影响，还影响到 整个计算机科学的发展，早期计算机科学研究认为，计算机不可能完成事先没 有显式编程好的任务，而萨缪尔跳棋程序否证了这个假设.另外，这个程序是最 早在计算机上执行非数值计算任务的程序之一，其逻辑指令设计思想极大地影 响了BM计算机的指令集，并很快被其他计算机的设计者采用
第2章模型评估与选择 2.1经验误差与过拟合 通常我们把分类错误的样本数占样本总数的比例称为“错误率”(erro rate),即如果在m个样本中有a个样本分类错误，则错误率E=a/m;相应的， a套意分比人1一am称为精度”Cc以即精度三1销误率更一投地我们完 学习器的实际预测输出与样本的真实输出之间的差异称为“误差”(eror), 受量绣证的~均学习器在训练集上的误差称为“训练误差”(ining ror)减“经验误 差”(empirical error),在新样本上的误差称为“泛化误差”(generalization error)).显然，我们希望得到泛化误差小的学习器.然而，我们事先并不知道新 不同 样本是什么样，实际能做的是努力使经验误差最小化.在很多情况下，我们可以 化经验误差。 学得一个经验误差很小、在训练集上表现很好的学习器，例如甚至对所有训练 样本都分类正确，即分类错误率为零，分类精度为100%，但这是不是我们想要 的学习器呢？遗憾的是，这样的学习器在多数情况下都不好. 我们实际希望的，是在新样本上能表现得很好的学习器.为了达到这个 目的，应该从训练样本中尽可能学出适用于所有潜在样本的“普遍规律”，这 样才能在遇到新样本时做出正确的判别.然而，当学习器把训练样本学得“太 好”了的时候，很可能已经把训练样本自身的一些特点当作了所有潜在样本都 会具有的一般性质，这样就会导致泛化性能下降.这种现象在机器学习中称为 过拟合亦称“过配” “过拟合”(overfitting).与“过拟合”相对的是“欠拟合”(underfitting),这 火拟合亦称“火配” 是指对训练样本的一般性质尚未学好.图2.1给出了关于过拟合与欠拟合的 个便于直观理解的类比. 有多种因素可能导致过拟合，其中最常见的情况是由于学习能力过于强大， 大孝的餐西过提 以至于把训练样本所包含的不太一般的特性都学到了，而欠拟合则通常是由 据内涵共同决定的 于学习能力低下而造成的.欠拟合比较容易克服，例如在决策树学习中扩展分 支、在神经网络学习中增加训练轮数等，而过拟合则很麻烦。在后面的学习中 我们将看到，过拟合是机器学习面临的关键障碍，各类学习算法都必然带有 些针对过拟合的措施：然而必须认识到，过拟合是无法彻底避免的，我们所能做 的只是“缓解”，或者说减小其风险.关于这一点，可大致这样理解：机器学习 面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内
第2章模型评估与选择 过拟合模型分类结果： 误以为树叶必须有锯齿 欠拟合模型分类结果 (误以为绿色的都是树叶 图21过拟合、欠拟合的直观类比 运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意 味着我们构造性地证明了“P=NP”;因此，只要相信“P≠NP”,过拟合就 不可避免 在现实任务中，我们往往有多种学习算法可供选择，甚至对同一个学习算 法，当使用不同的参数配置时，也会产生不同的模型.那么，我们该选用哪一个 学习算法、使用哪一种参数配置呢？这就是机器学习中的“模型选择”(mod©l selection)问题.理想的解决方案当然是对候选模型的泛化误差进行评估，然后 选择泛化误差最小的那个模型.然而如上面所讨论的，我们无法直接获得泛化 误差，而训练误差又由于过拟合现象的存在而不适合作为标准，那么，在现实中 如何进行模型评估与选择呢？ 2.2评估方法 通常，我们可通过实验测试来对学习器的泛化误差进行评估并进而做出选 专弃择，为此，需使用一个“测试集”esge来测试学习器对新样本的判别能 。可解释性等方面。 用 这里暂且只考虑泛化 力，然后以测试集上的“测试误差”(testing error)作为泛化误差的近似.通常 我们假设测试样本也是从样本真实分布中独立同分布采样而得.但需注意的 是，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未 在训练过程中使用过， 测试样本为什么要尽可能不出现在训练集中呢？为理解这一点，不妨考虑 这样一个场景：老师出了10道习题供同学们练习，考试时老师又用同样的这10 道题作为试题，这个考试成绩能否有效反映出同学们学得好不好呢？答案是否 定的，可能有的同学只会做这10道题却能得高分.回到我们的问题上来，我们
22评估方法 25 希望得到泛化性能强的模型，好比是希望同学们对课程学得很好、获得了对所 学知识“举一反三”的能力；训练样本相当于给同学们练习的习题，测试过程 则相当于考试.显然，若测试样本被用作训练了，则得到的将是过于“乐观”的 估计结果. 可是，我们只有一个包含m个样例的数据集D={(c1,h),(x2,2),, (cm,m)},既要训练，又要测试，怎样才能做到呢？答案是：通过对D进行适当 的处理，从中产生出训练集S和测试集T,下面介绍几种常见的做法 2.2.1留出法 “留出法”(hold-out)直接将数据集D划分为两个互斥的集合，其中一个 集合作为训练集S,另一个作为测试集T,即D=SUT,S门T=⑦.在S上训 练出模型后，用T来评估其测试误差，作为对泛化误差的估计. 以二分类任务为例，假定D包含1000个样本，将其划分为S包含700个样 本，T包含300个样本，用S进行训练后，如果模型在T上有90个样本分类错 误，那么其错误率为(90/300)×100%=30%，相应的，精度为1-30%=70% 需注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免 因数据划分过程引入额外的偏差而对最终结果产生影响，例如在分类任务中 至少要保持样本的类别比例相似.如果从采样(sampling)的角度来看待数据 集的划分过程，则保留类别比例的采样方式通常称为“分层采样”(stratified sampling).例如通过对D进行分层采样而获得含70%样本的训练集S和含 30%样本的测试集T,若D包含500个正例、500个反例，则分层采样得到的 S应包含350个正例、350个反例，而T则包含150个正例和150个反例：若 S、T中样本类别比例差别很大，则误差估计将由于训练/测试数据分布的差异 而产生偏差 另一个需注意的问题是，即便在给定训练/测试集的样本比例后，仍存在多 参见习题21. 种划分方式对初始数据集D进行分割.例如在上面的例子中，可以把D中的样 本排序，然后把前350个正例放到训练集中，也可以把最后350个正例放到训 练集中，…这些不同的划分将导致不同的训练/测试集，相应的，模型评估的 结果也会有差别.因此，单次使用留出法得到的估计结果往往不够稳定可靠，在 使用留出法时，一般要采用若干次随机划分、重复进行实验评估后取平均值作 为留出法的评估结果.例如进行100次随机划分，每次产生一个训练/测试集用 准风时可得估计特果的标 于实验评估，100次后就得到100个结果，而留出法返回的则是这100个结果的 平均 此外，我们希望评估的是用D训练出的模型的性能，但留出法需划分训