第1章绪论 (色泽=*；根蒂=蟾缩；敲声=*)（色泽=*；根蒂=*；敲声=清脆） (色泽=：根蒂一蜷缩；敲声=清脆) 图12西瓜问题的版本空间 1.4归纳偏好 通过学习得到的模型对应了假设空间中的一个假设.于是，图1.2的西瓜 版本空间给我们带来一个麻烦：现在有三个与训练集一致的假设，但与它们 对应的模型在面临新样本的时候，却会产生不同的输出.例如，对（色泽=青绿 根蒂=蜷缩；敲声=沉闷)这个新收来的瓜，如果我们采用的是“好瓜口（色 泽=*)人（根蒂=蜷缩）Λ（敲声=*）”，那么将会把新瓜判断为好瓜，而如果采 用了另外两个假设，则判断的结果将不是好瓜.那么，应该采用哪一个模型（或 假设)呢？ 若仅有表1.1中的训练样本，则无法断定上述三个假设中哪一个“更好” 然而，对于一个具体的学习算法而言，它必须要产生一个模型.。这时，学习算 法本身的“偏好”就会起到关键的作用.例如，若我们的算法喜欢“尽可能特 殊”的模型，则它会选择“好瓜分（色泽=*）Λ（根蒂=蜷缩）A(敲声=浊响)”： 即·用情尽能但若我们的算法喜欢“尽可能一般”的模型，并且由于某种原因它更“相信” 根蒂，则它会选择“好瓜+（色泽=*）Λ（根蒂=蜷缩）A(敲声=*)”，机器学习 算法在学习过程中对某种类型假设的偏好，称为“归纳偏好”(inductive bias) 或简称为“偏好” 关，但需注意的是，机器学 任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看 习中的特征选择仍是基于 对训练样本的分析进行的， 似在训练集上“等效”的假设所迷惑，而无法产生确定的学习结果.可以想象 而在此处我们并非基于特 如果没有偏好，我们的西瓜学习算法产生的模型每次在进行预测时随机抽选 征选择做出对“根蒂】 重视：这里对 “根薄 的的， 训练集上的等效假设，那么对这个新瓜“（色泽=青绿；根蒂=蜷缩；敲声=沉 的 闷)”，学得模型时而告诉我们它是好的、时而告诉我们它是不好的，这样的学 习结果显然没有意义 参见第11章. 归纳偏好的作用在图1.3这个回归学习图示中可能更直观.这里的每个训 练样本是图中的一个点(，)，要学得一个与训练集一致的模型，相当于找到 条穿过所有训练样本点的曲线.显然，对有限个样本点组成的训练集，存在着 很多条曲线与其一致，我们的学习算法必须有某种偏好，才能产出它认为“正 确”的模型.例如，若认为相似的样本应有相似的输出（例如，在各种属性上都
1.4归纳偏好 图13存在多条曲线与有限样本训练集一致 很相像的西瓜，成熟程度应该比较接近)，则对应的学习算法可能偏好图1.3中 比较“平滑”的曲线A而不是比较“崎岖”的曲线B 归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进 行选择的启发式或“价值观”.那么，有没有一般性的原则来引导算法确立 “正确的”偏好呢？“奥卡姆剃刀”(Occam's razor)是一种常用的、自然科学 研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”.如 果采用这个原则，并且假设我们认为“更平滑”意味着“更简单”（例如曲线 A更易于描述，其方程式是y=-x2+6x+1,而曲线B则要复杂得多)，则在 图13中我们会自然地偏好“平滑”的曲线A. 然而，奥卡姆剃刀并非唯一可行的原则.退一步说，即便假定我们是奥卡姆 剃刀的铁杆拥趸，也需注意到，奥卡姆剃刀本身存在不同的诠释，使用奥卡姆剃 刀原则并不平凡.例如对我们已经很熟悉的西瓜问题来说，“假设1：好瓜分 (色泽=*)Λ（根蒂=蜷缩）A(敲声=浊响)”和假设2：“好瓜：（色泽=*）Λ (根蒂=蜷缩)Λ（敲声=*）”这两个假设，哪一个更“简单”呢？这个问题并不 简单，需借助其他机制才能解决 事实上，归纳偏好对应了学习算法本身所做出的关于“什么样的模型更 好”的假设.在具体的现实问题中，这个假设是否成立，即算法的归纳偏好是否 与问题本身匹配，大多数时候直接决定了算法能否取得好的性能。 让我们再回头看看图1.3.假设学习算法￡。基于某种归纳偏好产生了对应 于曲线A的模型，学习算法基于另一种归纳偏好产生了对应于曲线B的模 型.基于前面讨论的平滑曲线的某种“描述简单性”，我们满怀信心地期待算 法￡。比更好.确实，图1.4()显示出，与B相比，A与训练集外的样本更 致；换言之，A的泛化能力比B强
第1章绪论 (a)A优于B (b)B优于A 图1,4没有免费的午餐.（黑点：训练样本；白点：测试样本） 但是，且慢！虽然我们希望并相信￡。比C更好，但会不会出现图1,4(b)的 情况：与A相比，B与训练集外的样本更一致？ 很遗憾，这种情况完全可能出现.换言之，对于一个学习算法￡，若它在某 些问题上比学习算法，好，则必然存在另一些问题，在那里比。好.有趣 的是，这个结论对任何算法均成立，哪怕是把本书后面将要介绍的一些聪明算 法作为￡。而将“随机胡猜”这样的笨拙算法作为.惊讶吗？让我们看看下 面这个简短的讨论： 这里只用到一些非常蒸 础的数学知识，只准备读 为简单起见，假设样本空间X和假设空间H都是离散的.令P(X,) 代表算法。基于训练数据X产生假设h的概率，再令∫代表我们希望学习的 ,只需相 真实目标函数.￡。的“训练集外误差”，即。在训练集之外的所有样本上的 信，上面这个看起来 夷所思”的结论确实是成 误差为 立的。 Eae(alXf)=∑∑P(e)Ih(e)≠f(o》Ph|X,a),(1.1) h IEX-X 其中1（是指示函数，若·为真则取值1，否则取值0. 考虑二分类问题，且真实目标函数可以是任何函数X→{0,1，函数空间 为{0,1}心.对所有可能的∫按均匀分布对误差求和，有 Ea(calX,f)=∑∑∑P()h()≠fe)Ph|X,&a) 了hxX-X =∑P(m)∑Ph|X,)∑h(a)≠fz》 EX-X h 若均匀分右时有 半的/对的预测与h(】 =∑P(e)∑Ph|X,&)52W 不一 sEX-X h =2州∑P∑Pa1X,) EEX-X h
14归纳偏好 9 =2x-1P(x)1 (1.2) wEY-x 式(12)显示出，总误差竟然与学习算法无关！对于任意两个学习算法￡。和 ,我们都有 ∑Eae(calX,f)=∑Ete(clX,f), (1.3) 也就是说，无论学习算法。多聪明、学习算法C多笨拙，它们的期望性能竟 严格的NL定理证明比 然相同！这就是“没有免费的午餐”定理(No Free Lunch Theorem,简称NFL 这里的简化论述繁难得多。 )[Wolpert,1996;Wolpert and Macready,1995]. 这下子，读者对机器学习的热情可能被一盆冷水浇透了：既然所有学习算 法的期望性能都跟随机胡猜差不多，那还有什么好学的？ 我们需注意到，NFL定理有一个重要前提：所有“问题”出现的机会相 同、或所有问题同等重要.但实际情形并不是这样.很多时候，我们只关注自 己正在试图解决的问题（例如某个具体应用任务），希望为它找到一个解决方案 至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案，我们并不 关心.例如，为了快速从A地到达B地，如果我们正在考虑的A地是南京鼓 楼、B地是南京新街口，那么“骑自行车”是很好的解决方案；这个方案对A 地是南京鼓楼、B地是北京新街口的情形显然很糟糕，但我们对此并不关心。 事实上，上面NFL定理的简短论述过程中假设了∫的均匀分布，而实际情 形并非如此.例如，回到我们熟悉的西瓜问题，考虑假设1：好瓜分（色泽=*） Λ（根蒂=蜷缩）A(敲声=浊响)}和{假设2：好瓜艹（色泽=*）A(根蒂=硬挺) A(敲声=清脆).从NFL定理可知，这两个假设同样好.我们立即会想到符 合条件的例子，对好瓜（色泽=青绿；根蒂=蜷缩；敲声=浊响）是假设1更好，而 对好瓜（色泽=乌黑；根蒂=硬挺；敲声=清脆）则是假设2更好.看上去的确是 这样.然而需注意到，“（根蒂=蜷缩；敲声=浊响）”的好瓜很常见，而“（根 蒂=硬挺；敲声=清脆)”的好瓜罕见，甚至不存在. 所以，N℉L定理最重要的寓意，是让我们清楚地认识到，脱离具体问题，空 泛地谈论“什么学习算法更好”毫无意义，因为若考虑所有潜在的问题，则所 有学习算法都一样好.要谈论算法的相对优劣，必须要针对具体的学习问题；在 某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意，学习算法 自身的归纳偏好与问题是否相配，往往会起到决定性的作用
10 第1章绪论 1.5发展历程 机器学习是人工智能(artificial intelligence)研究发展到一定阶段的必然产 物.二十世纪五十年代到七十年代初，人工智能研究处于“推理期”，那时人们 以为只要能赋予机器逻辑推理能力，机器就能具有智能.这一阶段的代表性工 作主要有A.Newell和H.Simon的“逻辑理论家”(Logic Theorist)程序以及 此后的“通用问题求解”(General Problem Solving)程序等，这些工作在当时 取得了令人振奋的结果.例如，“逻辑理论家”程序在1952年证明了著名数学 家罗素和怀特海的名著《数学原理》中的38条定理，在1963年证明了全部52 条定理，特别值得一提的是，定理2.85甚至比罗素和怀特海证明得更巧妙.A Newell和H.Simon因为这方面的工作获得了1975年图灵奖.然而，随着研究 向前发展，人们逐渐认识到，仅具有逻辑推理能力是远远实现不了人工智能的. E.A.Feigenbaum等人认为，要使机器具有智能，就必须设法使机器拥有知识， 所谓“知识就是力量” 在他们的倡导下，从二十世纪七十年代中期开始，人工智能研究进入了“知识 1965年.Feigenbaum主 持研制了世界上第一个专 期”，在这一时期，大量专家系统问世，在很多应用领域取得了大量成果.E.A 家系统DENDRAL Feigenbaum作为“知识工程”之父在1994年获得图灵奖.但是，人们逐渐认 识到，专家系统面临“知识工程瓶颈”，简单地说，就是由人来把知识总结出来 再教给计算机是相当困难的.于是，一些学者想到，如果机器自己能够学习知识 该多好！ 事实上，图灵在1950年关于图灵测试的文章中，就曾提到了机器学习的可 能：二十世纪五十年代初已有机器学习的相关研究，例如A.Samuel著名的跳 泰见p,22 棋程序.五十年代中后期，基于神经网络的“连接主义”(connectionism)学习 开始出现，代表性工作有F.Rosenblatt的感知机(Perceptron)、B.Widrow的 Adaline等.在六七十年代，基于逻辑表示的“符号主义”(symbolism)学习技 术蓬勃发展，代表性工作有P.Winston的“结构学习系统”、R.S.Michalski 等人的“基于逻辑的归纳学习系统”、E.B.Hut等人的“概念学习系统” 等；以决策理论为基础的学习技术以及强化学习技术等也得到发展，代表性工 作有N.J.Nlso加的“学习机器”等；二十多年后红极一时的统计学习理论的 些奠基性结果也是在这个时期取得的. 1980年夏，在美国卡耐基梅隆大学举行了第一届机器学习研讨会(IWML) 同年，《策略分析与信息系统》连出三期机器学习专辑；1983年，Tioga出版社 出版了R.S.Michalski、J.G.Carbonell和T.Mitchell主编的《机器学习：一 种人工智能途径》Michalski et al,.1983],对当时的机器学习研究工作进行了 总结；1986年，第一本机器学习专业期刊Machine Learning创f刊；1989年，人