机器学习讲义

1、 1一 月二 月三 月产品名称数量金额利润产品名称数量金额利润产品名称数量金额利润合 计合 计合 计四 月五 月六 月产品名称数量金额利润产品名称数量金额利润产品名称数量金额利润合 计合 计合 计机器学习讲义（2010年春硕士课程试用）第一章 绪论序 机器学习通常被认为是人工智能领域的一个分支，但和人工智能一样，实际上是多学科的融合。为了说明什么是机器学习，我们来看一下“自动”(automation) 和“自主”(autonomy) 这两个概念的区别。在通常的“自动化”系统中，所有的“智能”都是系统设计者预先注入的。当系统放入它的运行环境中去之后，将按照预定的程序进行活动。但是如果设计者对环境

2、的了解是不全面的，系统就有可能陷入无所适从的境地（系统中的知识是由人工编程输入的，知识中的错误也不能自动改正。）。这时“学习”的能力就成为唯一可依靠的解决方法，也是实现机器超过人这个终极智能的唯一手段。具有学习能力的系统称为是“自主的”。学习意味着根据经验改进自身。学习的真谛在于：感知不仅用于当前的行动，而且用于改进以后的行动。学习是系统和环境交互的结果，也来自于系统对自己决策过程的观察。学习的范围极广，从仅仅记住经验，到创造整个的科学理论，所有这些活动都是学习的过程。简而言之，机器学习意味着通过编程使计算机进行学习。比如，让计算机从医疗记录中学到治疗新疾病的最佳方案；使智能房屋根据经验学到基

3、于主人生活习惯的能源消耗优化方案；开发个人软件助手为用户从在线晨报中摘出该用户特别感兴趣的内容；等等。机器学习研究的进展对社会经济的影响将是巨大的，它能使计算机的应用领域大为扩展，并使个人和组织的竟争力提高到新的水平，甚至形成人类全新的生活方式。另外，对机器学习的信息处理算法的研究将导致对人脑学习能力（及其缺陷）的更好的理解。就机器学习研究的现状而言，我们必须承认，目前还不能使计算机具有类似人那样的学习能力。但是，对某些类型的学习任务已经发明了有效的算法，对学习的理论研究也已经开始，人们已经开发出许多计算机程序，它们显示了有效的学习能力，有商业价值的应用系统也已经开始出现。在理论方面，关于观察

4、例的数目，所考虑的假设的数目和学习到的假设的预计误差之间的基本关系的刻画已经取得成果。我们已经获得人类和动物学习的初步模型，开始了解它们与计算机学习算法之间的关系。在应用方面，近十年来的进展尤为迅速。下面是一些突出的应用实例： 语音识别：所有最成功的语音识别系统都以某种形式使用了机器学习技术。例如，sphinx系统学习针对具体讲话人的策略从接受到的语音信号中识别单音和单词。神经网络学习方法和学习隐藏的markov模型的方法可有效地应用于对个别讲话人，词汇表，麦克风的特性，背景噪音等的自动适应。类似的技术也可用于许多其他的信号解释问题。 自动车驾驶：机器学习方法已用于训练计算机控制的车辆在各种类

5、型的道路上的正确行驶。例如，alvinn系统使用学习到的策略在高速公路上与别的车辆一起以每小时70英里的速度自动行驶了90英里。类似的技术也可用于许多其他的基于传感器的控制问题。 新天体的分类：机器学习方法已用于各种各样的大型数据库以发现隐藏在数据中的一般规律。例如，nasa用决策树学习算法对天体进行分类。该系统现在被用来对所有的对象进行分类，所用的数据库含有三兆字节的图象数据。 计算机弈棋：大多数成功的计算机弈棋程序均基于机器学习算法。例如，td-gammon通过与自己对弈100多万次来学习下backgammon棋的策略。该系统目前已达到人类世界冠军的水平。类似的技术也可用于许多其他的涉及具

6、有非常大搜索空间的实际问题。总之，随着我们对计算机研究的进一步加深，机器学习将不可避免地在计算机科学技术中起到越来越重要的作用。 机器学习本质上是一个多学科的领域。下面我们列出主要的相关学科及其影响机器学习领域的主要思想。 人工智能： 概念的符号表达的学习， 作为搜索问题的机器学习， 学习作为改善问题求解的方法， 将先验知识和训练数据结合起来指导学习。 贝叶斯方法：贝叶斯定理是做猜想的概率计算的基础， 简单贝叶斯分类器， 计算未观察到的变量值的算法。 计算复杂性理论：各种学习任务的内在复杂性的理论边界，而复杂性是 以学习所需的计算量，训练例数，错误数等来度量的。 控制论： 学习控制进程以优化预

7、定义对象， 学习预测所控制的进程的下一状态。 信息论：熵和信息内容的度量， 哲学。 心理学与神经生物学。 统计学。1.1 学习问题的一般表达定义 如果一个计算机系统在完成某一类任务t时的性能p能够随着经验e而改进，则称该系统为一个学习系统。显然，要讨论一个学习系统，首先必须确定它的三个关键成分：任务t，性能指标p和经验来源e。例子：1 下跳棋： t：下跳棋 p：胜率 e：自弈 2 手迹辨认： t：手写字图象的识别与分类 p：正确分类率 e：手写字及其已知分类的数据库 3 行车机器人： t：使用视觉传感器在四道高速公路上行驶 p：平均无错误行驶的里程 e：人类驾驶员行车的路况和操作的系列记录1.

8、2 学习系统的设计 学习系统的设计要作四个关键的设计选择（训练经验的选择，目标函数的选择，目标函数表示的选择，函数近似算法即学习算法的选择），从而确定系统的四个核心模块（行动模块，评价模块，学习模块，知识生成模块）所使用的策略和算法。121 训练经验的选择训练经验的类型对学习系统的成败具有重要的影响。训练经验的关键特征有： 训练经验对行为模块的选择提供直接的还是间接的反馈。比如在计算机下跳棋系统中，如果例子集由各种棋盘态势及其正确走步组成，这种训练经验就是直接的（因为例子集直接地告诉行为模块遇到什么情况走什么步）；如果例子集由各盘比赛的走步序列及其胜负结果组成，这种训练经验就是间接的（因为例子

9、集不能直接地告诉行为模块遇到什么情况走什么步，而只是提供一些间接的下跳棋经验）。从直接经验的学习显然要比从间接经验的学习容易，因为在间接经验的情况下，走步序列中的每一走步的“得分”（即它对比赛最终胜负的影响）需要另作推敲，而且得分的估计有时是十分困难的。 学习系统对训练例子序列能够控制到何种程度。比如在计算机下跳棋系统中，可能是由教师决定考虑何种棋盘态势及其正确走步；也可能是由系统提出自己感到困难的棋盘态势并向教师询问其正确走步；还可能是计算机自己跟自己下跳棋，它对棋盘态势及其训练分类有着完全的控制（它可以试验崭新的棋盘态势以学习新的技术，也可以对它迄今所知的最好棋局略作改变以改进自己的技术）

10、。在本书中我们将考虑各种各样的学习系统。 训练经验与最终用来测试系统性能p的那些例子之间的关系。训练例与测试例的分布越相似，学习的结果就越可靠。假如计算机下跳棋学习系统的目的是参加世界锦标赛（即p为该系统将来在世界锦标赛上的胜率），那么用计算机自己跟自己下跳棋的方式进行学习就可能是不够的，因为这时所用的训练例难以代表在世界锦标赛上所遇到的可能棋局。在目前的有关机器学习的书中，人们通常假定训练例与测试例的分布是一致的，这样才能获得一定的理论成果。但是，我们要记住，现实中这两者的分布是有差别的。在下面关于学习系统设计的讨论中，我们以计算机通过自己跟自己下跳棋的方式进行学习的系统作为实例。注意，这意

11、味着没有外部训练者，而系统能够生成足够多的训练数据。122 目标函数的选择学习系统的目的是改进在完成某一类任务t时的性能p。我们通常把这一目的转换成对某目标函数的学习。于是，目标函数的选择就成了学习系统设计的一个关键问题。例如，在计算机下跳棋问题里，目标函数可为：choosemove : b m其中，b为合法棋盘态势集，m为合法走步集。给定任一棋盘态势m，choosemove(m)给出m下的最佳走步。对于计算机下跳棋问题，显然choosemove是一个合适的目标函数。但是，如果训练例是间接的（即给出各盘比赛的走步序列及其胜负结果），choosemove的学习将是十分困难的。另一个可能的目标函数

12、可为：v : b r其中，b为合法棋盘态势集，r为实数集。给定任一棋盘态势m，v(m) 给出m的估价值（估价值v(m) 越高，棋盘态势m越有利）。根据这个估价函数v，不难求出最佳走步。最简单的方法是：对当前棋盘态势m，可生成所有可能的后继态势m1 , m2 , , mn，选择具有最大的v(mi)值的后继态势mi，达到mi的走步就是最佳走步。若采取向前看几步的策略，可使用人工智能中熟知的a-b过程。于是，机器学习的任务就归结为发现目标函数v的可操作的描述。在许多实际问题里，这是一个十分困难的任务，所以仅要求描述v的一个近似v。因此，学习目标函数的算法通常称为函数近似算法。123 目标函数的表示的

13、选择这里所说的目标函数v的表示即它的近似v的表示方法。越是表达力强的方法越能够接近理想的目标函数v，但也就需要越多的训练数据来确定它的值。在计算机下跳棋问题里，我们可用下面的棋盘特性的一个线性组合来表示v：v(b) = w0 + w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6这显然是目标函数v的一个可操作的近似描述。其中， x1为棋盘b上黑子的个数 x2为棋盘b上红子的个数 x3为棋盘b上黑王的个数 x4为棋盘b上红王的个数 x5为棋盘b上受红方威胁的黑子的个数 x6为棋盘b上受黑方威胁的红子的个数 w0 , w1 , w2 , w3 , w4 , w5 , w

14、6为待定系数wi ( i = 1,2,6 ) 表达棋盘特性xi的相对重要性，w0则是为整个棋盘附加的一个常数。系统的学习任务（由函数近似算法完成）就是通过训练例来设置这些系数。一旦这些系数被确定，对任何棋盘态势b，计算机下跳棋系统很容易计算v(b)的值，从而选择最佳走步。当然，真的让该系统参加世界锦标赛，其表现不见得就一定令人满意。影响系统性能的因素有：v(b)表示的精密度，函数近似算法（它负责从训练例学习系数wi的值）的质量，以及训练例的数量和质量。实际上，系数wi的值并非是一次性确定的。开始时，不妨按某种策略设定它们的初值，然后在学习过程中不断对它们进行调整和改进。124 函数近似算法的选

15、择 如果我们采用v(b)作为目标函数的近似表达，棋盘态势b就可以表达为元组。假设计算机下跳棋系统所用的间接训练经验为各盘比赛的走步序列及其胜负结果。我们现在的任务是要通过训练例来设置v函数中的那些系数wi 。这可以通过两个步骤完成：1 从间接训练经验提取形如 (b, vtrain(b) 的直接训练例子。其中vtrain(b)称为训练值，是v(b)的估计值。2 用一组(b, vtrain(b)例子调节系数wi的值。下面我们分别对这两个步骤进行说明。1 估计训练值vtrain(b)的方法 既然v的系数待定（或待改进），v(b)值的估计必定是一个含糊的任务。我们可以这样想，当前的系数值（不管它们是否

16、仍待改进）用于接近尾盘时的精度总比用于较早期棋局时的精度高。考虑当前棋局b和经过计算机和对手的两次走步(各走一次)后的棋局succ(b)（间接训练例可给出succ(b)）。使用当前系数值可求出v(succ(b)。如果把它作为v(b)值的估计，即：vtrain(b) v(succ(b)，我们可以期待它比用当前系数值算出的v(b)更精确。（当然，对于终局b，若为胜局，可设vtrain(b) +；若为负局，可设vtrain(b) -；若为和局，可设vtrain(b) 0）。实践证明这个简单的方法颇为有效。理论上可以证明，在一定条件下，这种用后继状态的估计值递推改进前面状态的估计值的方法可收敛于精确的

17、估计值。2 调节系数的方法我们已有了一组直接训练例(b, vtrain(b)，b取一盘比赛历史中各个轮到机器走步时的状态。现在的任务是确定（或改进）函数近似v（即它的系数wi），使之与训练例达到最好的匹配。严格地说，就是求wi，使方差达到最小。在一定条件下，最小方差e对应于（对观察到的训练数据来说）最可能的关于wi的假设。求使e达到最小值的线性函数的系数的算法有多种。我们需要的算法应能随着训练例的逐个出现步进地改进系数，并对估计的训练值中的错误具有抵抗性。最小均方系数调整规则（lms系数调整规则）就是这样的一个算法：lms系数调整规则对每一个训练例(b, vtrain(b)： 使用当前系数值计

18、算v(b) 对每一个系数wi：这里h为一个小常数（如0.1），使系数的每次改变不至于太大。该算法的合理性在直观上可作如下理解：(1). 若(vtrain(b) - v(b)为正数，说明当前v(b)值偏低，而按算法wi将增大，从而使v(b)值增加。(2). 若(vtrain(b) - v(b)为负数，说明当前v(b)值偏高，而按算法wi将减少，从而使v(b)值减少。(3). 若(vtrain(b) - v(b)为0，说明当前v(b)值合适，而按算法wi将不变，从而使v(b)值不变。(4). 各系数wi变化的大小与其相应特性在棋盘中出现的次数（即xi的值）成正比。特别地，若某棋盘特性不出现在b中（

19、即xi=0），它的系数wi不变。理论上，这属于随机梯度下降搜索方法，在系数空间里搜索使e达到最小值的系数。可证明，在一定的条件下，这个简单的微调算法确实收敛于vtrain(b)的最小方差估计。125 学习系统的最终设计学习系统含有四个核心模块，上面讲解的四个设计选择决定了各个模块内部的策略和算法。也就是说，针对某个具体问题，作出四个具体的设计选择，产生四个核心模块的具体版本，从而设计出解决该具体问题的学习系统。以计算机下跳棋系统为例，四个核心模块为：1 行动模块（又称行为系统）。接受感知信息（输入），决定系统所要采取的行动。在计算机下跳棋问题中，行动就是走步。该模块的输入为一局新棋（连同当前学

20、习到的目标函数v），输出为本局棋的走步序列（产生一个新的间接训练例）。其基本策略是：根据学习到的目标函数v决定每一步的走法。显然，随着v的不断精密化，系统的性能将不断改善。一般来说，学习的目的是改进行动模块的性能，所以我们首先要弄清楚行动模块中哪些成分需要改进。行动模块可能有以下各种成分，它们都能够被学习改进： (1) 从当前状态（的条件）到行动的直接映射 (2) 从感知信息序列推断出环境的有关性质的手段 (3) 关于环境演变方式的信息 (4) 关于系统可采取的可能行动的后果信息 (5) 指示状态是否良好的辅助信息 (6) 指示在特定状态采取特定行动是否合适的“行动值”信息 (7) 目标，它描

21、述一组使系统能力得到最大发挥的状态行动模块需要改进的成分的表达方式有确定性描述，逻辑公式，概率描述，等等，都可以抽象地描述为函数（称为目标函数），学习的任务就是要获得目标函数的定义，使之与训练例最为匹配（在满足系统的一般约束条件下）。2 评价模块（又称批评模块）。根据系统外固定的性能标准，接受关于系统行为后果的感知信息，评价系统的性能，并将评价意见反馈给学习模块。在计算机下跳棋系统中，评价模块以行动模块的输出（新的棋局历史，即新的间接训练例）作为自己的输入，产生一组形如 (bi, vtrain(bi) 的直接训练例子，其中bi为棋局历史中出现的各个棋盘态势，训练值vtrain(bi) 的计算使

22、用我们上面讲过的公式vtrain(b) v(succ(b)。将这些新的直接训练例子反馈给学习模块，以改进目标函数v。一般来说，我们可以有以下几种可以使用的反馈：若目标函数（即要改进的行动成分的数学表达）的输入和输出（实际输出和正确的输出）都是可以感知的，称为有指导的学习；若只有对实际输出的评价，却不给出正确的输出值，称为强化学习（又称奖惩式学习）；若对正确的输出值没有任何提示，称为无指导的学习。计算机下跳棋问题是一个典型的强化学习问题。3 学习模块（又称推广模块）。了解行动模块的工作特性，接受评价模块发来的关于系统性能的反馈信息，决定并告诉行动模块应如何改进以图在将来更好地工作。在计算机下跳棋

23、系统中，学习模块以评价模块的输出（形如 (bi, vtrain(bi) 的直接训练例子）作为自己的输入，用以改进目标函数v（即改进它的各个系数wi），以图在下一盘棋中系统能显示更好的性能。按照我们前面的选择，采用的学习算法是lms系数调整规则。4 问题生成模块（又称试验生成模块）。根据学习模块给出的学习目标，向行动模块建议进行某种偏离常规的探索性行动，试图获得新的有价值的经验。在计算机下跳棋系统中，问题生成模块可简单地建议“用新的目标函数v从头再下一盘”，以递推地改进v；也可以根据学习模块提供的其它改进意见生成特殊的残局让行动模块去下，以探索新的经验（即搜索状态空间中了解得还不够充分的特定部分

24、），从而提高系统的整体性能。1.3 机器学习所研究的主要问题将上面讨论的计算机下跳棋问题一般化，我们可以看到，研究一个机器学习问题或设计一个机器学习系统，需要弄清楚如下要点： 学习任务t 性能度量p 训练例e 抽象的目标函数f（代表系统行为中需要学习改进的成分） 目标函数的具体（近似）表示f（如系数待定的数学函数） 从训练例e导出f值的方法 根据f的特殊输入/输出对子，学习改进f的定义的方法 我们可将机器学习看成是搜索问题。作为搜索问题，我们要考察搜索空间，搜索空间的结构，搜索目的，搜索策略及其收敛性，等等。机器学习问题的搜索空间（又称假设空间）是所有可能的目标函数（又称假设）；目标函数的表达

25、方式决定了搜索空间的结构；搜索目的是寻找与训练例最为匹配的（且满足系统的一般约束条件的）假设；搜索策略就是针对各种不同结构的搜索空间的学习算法，是机器学习领域的主要研究对象。理论上，主要问题是学习算法的收敛性，以及关于训练例的数量，搜索空间的大小和特性，对学习到的假设的信任度（它能正确解释未来实例的能力）这三者之间关系的定量分析。“学习即搜索” 是本书的基本观点，从这个观点出发，我们可以总结出机器学习所研究的主要问题：1 从特殊训练例学习一般性目标函数的算法有哪些？一个特定的算法在何种条件下能够收敛到所求的函数（当然要给予它充分多的训练数据）？各种算法最适用于何种学习问题和何种表达方式？2 多

26、少训练例算是充分的？训练例的数量，搜索空间的大小和特性，对学习到的假设的信任度这三者之间有何定量关系？3 学习系统掌握的先验知识在什么情况下及如何指导学习过程？近似正确的先验知识也能被利用吗？4 学习过程中选用下一个训练例的最佳策略是什么？选例策略对系统的复杂度有什么影响？5 如何将学习任务化为函数近似问题（即如何找出特定的函数）？这一过程能够自动化吗？6 系统如何自动地改变自己的表达方式以加强表示和学习目标函数的能力？本书后面的章节将根据机器学习领域的研究成果，对这些问题进行回答。第二章 概念学习21 导言概念学习是一种有指导的学习。设有对象集合x（如所有动物），一个概念c（如鸟类）定义了一

27、个对象类，即x的一个子集。概念学习意味着从概念的正例（属于该类的一些对象）和负例（不属于该类的一些对象）导出概念的定义。参考机器学习问题的一般表述格式，概念学习问题的要点为： 学习任务t：判别任一对象是否属于概念c 性能度量p：用该定义判别训练例之外的对象是否属于c的准确率 训练例e： 抽象的目标函数f: x bool 目标函数的具体（近似）表示f: 施加于对象的各个属性的约束的合取式 从训练例e导出f值的方法：此处为直接训练例，无需转换 根据f的特殊输入/输出事例，学习改进f的定义的方法：22 概念学习任务为了叙述的方便，我们把概念学习任务表达为与上面的格式等价的形式：给定： 对象集合x，每

28、一个对象xx由n个属性a1, a2, , an描述 目标概念c : x bool 训练例集e：每个训练例形如。e分为正例集e+和负例集e-。 c(x) = true 的例子称为正例，c(x) = false 的例子称为负例。 假设空间h：每个假设 hh和c一样是布尔函数x bool。 我们暂时只考虑一种简单的表示方法，将h表达为施加于对象的各个属性的约束的合取式。若对象x满足所有的约束，则h(x) = true，即：h判定x属于目标概念c，为一个正例。 为阅读的方便，我们将假设h写成的形式，读作：“a1的值为v1且a2的值为v2 且且an的值为vn”。vi可取特殊值“?”，表示属性ai可取任意

29、值；若某vi为，则表示属性ai取任意值均不容许，此时h将所有对象均判定为负例。确定： h中与目标概念c完全一致的假设h：xx h(x) = c(x)注意，上面要求找到与目标概念c在全体对象集x一致的假设h。但是，除了在训练例集e上，c(x)的值是系统所不知道的，我们无法断定假设h是否达到了要求。我们能保证的只是：假设h与目标概念c在训练例集e上是一致的。因此机器学习领域通常采用所谓“归纳学习假说”：任何在充分大的训练例集e上对目标概念c作出良好近似的假设h亦将在其它未见例子上对目标概念c作出良好近似。23 假设空间上的一个偏序概念学习是对假设空间h的搜索。h的元素是假设，每一个假设h是一个布尔

30、函数。在假设空间h上有一个偏序（称为一般化序 g），它使假设空间h具有格的结构，有利于对h的搜索。因此在讲任何搜索算法之前，我们先来讨论这个偏序。 定义。 设h1 , h2是定义在对象集x上的两个布尔函数。我们说h1比h2更一般（亦称h2比h1更特殊），记为h1 g h2 ，当且仅当xx (h2(x) h1(x) 直观上说，“h1比h2更一般”意味着：满足h2的对象也满足h1，所以h1划定的对象子集包含着h2划定的对象子集。 定义。 设h1 , h2是定义在对象集x上的两个布尔函数。我们说h1比h2严格地更一般，记为h1 g h2 ，当且仅当 (h1 g h2 ) (h2 g h1) 24 寻

31、找与正例一致的最特殊假设的算法find-s机器学习文献中利用一般化序g的搜索算法有很多，我们现在要讲的第一个搜索算法是寻找与正例一致的最特殊假设的算法find-s。所谓“与正例一致的最特殊假设”是指覆盖所有观察到的正例（即对所有观察到的正例均能正确判定）的最特殊的假设（其它覆盖所有观察到的正例的假设均比此假设更一般），又称“极大特殊假设”(maximally specific hypothesis)或“极小一般假设” (least general generalizatin - lgg)。find-s算法从最特殊的假设h开始，沿着偏序 g的一条链对h进行一般化。在每一步（处理一个新的正例x），

32、只做最必要的一般化使h覆盖x。从而，在算法的任意时刻，h总是覆盖迄今所观察到的所有正例的最特殊的假设。find-s算法的形式化描述如下：算法：find-s。1 将h初始化为最特殊的假设 2 对每一个观察到的正例x 对h 中的每一个属性约束ai 如果 约束ai被x满足 则 什么也不做 否则 ai 被x满足的下一个更一般的约束3输出假设h 下面给出算法find-s的运行例子并加以讨论。find-s算法的的一个运行例：对于概念学习，我们目前只考虑最简单的一种假设表示方法：将h表达为施加于对象的各个属性的约束的合取式。我们将假设h写成的形式，读作：“a1的值为v1且a2的值为v2 且且an的值为vn”

33、。vi可取特殊值“?”，表示属性ai 可取任意值；若某vi为，则表示属性ai取任意值均不容许，此时h将所有对象均判定为负例。下面是这种简单表达方式的一个例子：对象： 日子目标概念：适合冲浪运动：日子集d bool训练例：日子 属性表 a1 a2 a3 a4 a5 a6 正/负例 阴晴 气温 湿度 风力 水温 明日预报 -x1 sunny warm normal strong warm same 正x2 sunny warm high strong warm same 正x3 rainy cold high strong warm change 负x4 sunny warm high stron

34、g cool change 正find-s算法运行历史： h0 = 遇正例x1 : h1 = 遇正例x2 : h2 = 遇负例x3 : h3 = = h2 遇正例x4 : h4 = 输出覆盖所有正例的最特殊的假设h4，此假设断言：“晴朗，温暖，有强风的天气适合冲浪运动”。注：假设h4是与所有观察到的正例一致的最特殊假设，也与负例一致。关于算法find-s的讨论：1 简单表达方式下算法中一些操作的具体实现： “最特殊的假设”为 “ai的被x满足的下一个更一般的约束”next(ai)： 若ai= 则 next(ai)=x.vi （即当前正例x的属性值vi） 若ai=u (x.vi) 则 next(

35、ai)=? （即任意值均可）2. 算法的关键性质：对于简单表达方式（将h表达为施加于对象的各个属性的约束的合取式），算法必定输出覆盖所有观察到的正例的最特殊的假设；并且，若h含有正确的目标概念c且训练例无误，则结果与负例也一致（尽管算法中遇到负例时什么也未做）。证明：在任何时刻，h总是覆盖迄今所观察到的所有正例的最特殊的假设，而因为h含有正确的目标概念c ，故c也可看成是一个覆盖迄今所观察到的所有正例的假设。因此，c g h。另一方面，正确的c不覆盖负例，所以h也不会覆盖负例。（反之，若训练例为 x1 sunny warm normal strong warm same 正 x2 sunny

36、warm high strong warm same 正 x3 sunny warm middle strong warm same 负 则h中不含有正确的目标概念c（即c无法用简单的表达方式表示），算法的结果不能保证与负例一致。）3 算法存在的问题： 不能保证结果收敛到目标概念c（只知道结果h与训练例一致，不知h是否为唯一的与训练例一致的假设）。 只能找到与训练例一致的最特殊假设。有时我们可能希望得到与训练例一致的最一般假设或某中间假设，find-s算法不能满足这些需要。 不能识别和处理训练例中的错误和噪音。此算法根本不检查负例，而假定数据的完全正确性。这样，实际问题中通常存在的错误和噪音将

37、严重影响算法结果的有效性。 不能处理多个极大特殊假设的情况。在简单表达方式下，只有一个极大特殊假设，find-s算法沿着偏序的一个分支搜索即可。若表达方式复杂一些，可能有多个极大特殊假设，而目标概念c是其中的一个。这时算法应具有回溯功能。另外，有的问题可能不存在极大特殊的一致性假设。我们在后面讲解别的学习算法时，将要考虑这些问题。25 版本空间与候选剪除算法第二个利用一般化序g的搜索算法是候选剪除算法。find-s算法仅给出一个特定的与训练例一致的假设，而候选剪除算法给出所有与训练例一致的假设（并非列举，而是给出一致假设集合的一个描述）。候选剪除算法的策略是维持一致假设集合的一个简洁表示，并力

38、图通过训练例不断地改进这个表示。候选剪除算法虽比find-s算法好，但仍不能处理噪音问题。我们讲解这两个算法的主要目的不是为了实用，而是为了引入机器学习的一些重要概念。251 版本空间及其结构定义。假设h与训练例集e一致，记为consistent(h,e),当且仅当:(x,c(x)e h(x) = c(x) 定义。对于假设空间h 和训练例集e的版本空间是所有与e一致的假设的集合（此集合中的每一个假设均是目标概念c的一个可能的版本），记为vsh,e：vsh,e = h h | consistent(h,e) 定义。对于假设空间h 和训练例集e的一般化界g是h中与e一致的极大一般化成员的集合:g

39、= gh | consistent(g, e) $gh g g g consistent(g,e) 定义。对于假设空间h 和训练例集e的特殊化界s是h中与e一致的极小一般化成员的集合:s = sh | consistent(s, e) $sh s g s consistent(s,e) 定理。只要g和s能够合适地定义, 版本空间就完全被它们所确定:vsh,e = hh | ($ss) ($gg) (g g h g s ) 证明: 252 候选剪除算法下面的候选剪除算法计算g和s，从而计算出整个的版本空间（由上面的定理）。算法适用于所有的概念学习问题，但其中有几个操作依赖于对象和假设的具体表示方

40、法。在下面的算法描述中，我们特意指出这些依赖于具体表示的操作，并在注解中说明在本章所考虑的简单表示方式下它们的具体形式：算法：候选剪除。1 将g初始化为h中的最一般假设的集合 2 将s初始化为h中的最特殊假设的集合 3对每一个训练例x 如果 x是正例 则 从g中剪除所有与x不一致的假设 对s中每一个与x不一致的假设s 将s从s中剪除 s s | s 为s的最小一般化 s 与x一致 g中某成员比s更（严格）一般 s s s 从s中剪除比s中另一个假设更（严格）一般的所有假设 如果 x是负例 则 从s中剪除所有与x不一致的假设 对g中每一个与x不一致的假设g 将g从g中剪除 g g | g 为g的

41、最小特殊化 g 与x一致 s中某成员比g更（严格）特殊 g g g 从g中剪除比g中另一个假设更（严格）特殊的所有假设 例子：再次考虑本章前面的简单表示方式的例子：x1 sunny warm normal strong warm same 正x2 sunny warm high strong warm same 正x3 rainy cold high strong warm change 负x4 sunny warm high strong cool change 正候选剪除算法的运行历史如下：g0 = s0 = 遇正例x1 : g1 = g0 （不变） s = s = s1 = 遇正例x2

42、: g2 = g1 （不变） s = s = s2 = 遇负例x3 : s3 = s2 （不变） g = g = , , , 标记x3为负例的比g2特殊一点的假设集合（利用第3个条件，去掉不能覆盖前面正例的那些假设） = , g3 = ,遇正例x4 : g4 = , s = s = s4 = 输出s4 和 g4，这两个界集合划定了整个的版本空间（含6个与训练例一致的假设）：特殊界 s4 = 中间 一般界 g4 = ,本例的结果与训练例的次序无关。当遇到更多的训练例时，s 和g将单调地越来越靠近，划定越来越小的版本空间。算法的讨论1 收敛性。若训练例无错，且目标概念包含在h中，则此算法计算出的版

43、本空间收敛于目标概念。（因为每一个训练例均排除一些对目标概念的模糊认识，当充分多的训练例被观察到时，g和s这两个界将收敛于同一个假设，它就是那个包含在h中的目标概念）。2 噪音处理。此算法不能处理噪音。例如，若正例e被错标为负例，则目标概念与e不一致，按算法步骤目标概念将被剪除，从而不可能计算出正确的目标概念。关于噪音，本算法只有一点可以做到：若训练例中有噪音或目标概念不包含在h中（假设h的表示方式无法描述目标概念），当有充分多的训练例被观察到时，g和s这两个界将收敛于空集，即版本空间为空，表明h中没有与所有训练例一致的假设。3 训练例的次序。如果学习系统能够自己做实验生成例子并通过请教外部教

44、师知道生成的例子是正是负，我们说该系统能够查询。假定系统已经计算出上面的含有6个假设的版本空间，下一步应该查询什么（即生成什么例子来请教外部教师）？最理想的例子x* 应被版本空间中一半的假设判为真，被另一半的假设判为假。无论教师说x*是正例还是负例，算法必将把版本空间缩小一半。例如在我们的简单实例中，x* 为。如果这样的x*总是可以确定，系统只要做 log2vs 次实验就能发现目标概念。可惜，在多数问题里难以确定恰与版本空间中一半的假设匹配的实例，所以通常要做多于 log2vs 次实验才能找到目标概念。4 未完全学习出的概念的应用。当版本空间尚含有多个假设时，目标概念尚未完全学习出来。但是，仍

45、然可以用这个部分学习出的概念来判别新的例子。在特殊情况下判别的可信度如同用真正的目标概念来判别时一样；多数情况下可信度会降低，但我们可以给出可信度的度量。例如在我们的简单实例中，用部分学习到的含6个假设版本空间来判别下面4个新例子： x5 sunny warm normal strong cool change 正/负？ x6 rainy cold normal light warm same 正/负？ x7 sunny warm normal light warm same 正/负？ x8 sunny cold normal strong warm same 正/负？ 因为版本空间的所有假设

46、均认为x5是正例，所以目标概念也将判它为正例。 因为版本空间的所有假设均认为x6是负例，所以目标概念也将判它为负例。 因为版本空间的假设一半认为x7是正例，一半认为x7是负例，所以x7应该被选择为下一个查询x*。 因为版本空间的假设1/3认为x8是正例，2/3认为x8是负例，所以x8应该 按多数的意见被判定为负的，其可信度可置为0.667（若h中所有假设具有相等的先验概率）。26 归纳偏向本节在候选剪除算法的框架下讨论归纳学习的几个根本问题，但结论对任何概念小系统均有效。这些根本问题为：目标概念不在假设空间里怎么办？是否应该使用包含一切可能假设的空间？假设空间的大小如何影响必须观察到的例子的数量？假设空间的大小如何影响算法判别非训练例子的能力？261 有偏向与无偏向的概念学习在我们简单的表示方式中，对假设空间已经有了偏向：只认为那些表达为施加于对象的各个属性的约束（ai=vi/?/）的合取式是可能的假设。在此偏向下，很普通的概念如（a1=v1 a1=v2,sky=sunny or sky=cloudy）也表达不了。回到以前我们考察过的训练例： x1 sunny warm normal strong warm same 正 x2 cloudy warm n