加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 机器学习中文版

机器学习中文版.pdf

机器学习中文版

housebuilding
2010-04-26 0人阅读 举报 0 0 暂无简介

简介:本文档为《机器学习中文版pdf》,可适用于IT/计算机领域

序言机器学习这门学科所关注的问题是:计算机程序如何随着经验积累自动提高性能?近年来机器学习被成功地应用于很多领域从检测信用卡交易欺诈的数据挖掘程序到获取用户阅读兴趣的信息过滤系统再到能在高速公路上自动行驶的汽车。同时这个学科的基础理论和算法也有了重大的进展。这本教材的目标是展现机器学习中核心的算法和理论。机器学习从很多学科吸收了成果和概念包括统计学、人工智能、哲学、信息论、生物学、认知科学、计算复杂性和控制论等。我相信研究机器学习的最佳途径是从这些学科的观点看待机器学习并且以此来理解问题的背景、算法以及其中隐含的假定。这些在以往很难做到因为在这一领域缺少包容广泛的原始资料。这本书的主要目的就是提供这样的一份资料。由于素材的多学科性这本书不要求读者具有相应的知识背景而是在必要时介绍其他一些学科的基本概念如统计学、人工智能、信息论等。介绍的重点是与机器学习关系最密切的那些概念。本书可以作为计算机科学与工程、统计学和社会科学等专业的大学生或研究生的教材也可作为软件研究人员或从业人员的参考。指导这本书写作的两条原则为:它是在校大学生可以理解的它应该包含博士生在开始研究机器学习前要掌握的内容。指导这本书写作的第三条原则是:它应该体现理论和实践两者的平衡。机器学习理论致力于回答这样的问题“学习性能是怎样随着给定的训练样例的数量变化的?”和“对于不同类型的学习任务哪个学习算法最适合?”利用来自统计学、计算复杂性和贝叶斯分析的理论成果这本书讨论了这一类理论问题。同时本书也覆盖了很多实践方面的内容:介绍了这一领域的主要算法并阐明了算法的运行过程。一些算法的实现和数据可以在互联网上通过网址http:wwwcscmuedu~tommlbookhtml得到。其中包括用于人脸识别的神经网络、用于信贷分析的决策树学习、及分析文本文档的贝叶斯分类器各自的源代码和所需数据。我很感谢那些帮助我创建这些在线资源的同事包括JasonRennie、PaulHsiung、JeffShufelt、MattGlickman、ScottDavies、JosephO’Sullivan、KenLang、AndrewMcCallum和ThorstenJoachims。致谢在写作这本书的过程中我幸运地得到了机器学习领域很多学科分支的技术专家的帮助。没有他们的帮助这本书是不可能完成的。我深深地感激下面的科学家们他们花时间检阅本书的草稿并且以他们各自领域的专长对我进行了指导。(⋯⋯)我也很感谢各所大学的很多讲师和学生他们实地测试了本书的很多草稿并提出了他们的建议。尽管没有足够的版面来感谢上百名的学生、讲师和其他测试了草稿的人我要感谢下面各位感谢他们特别有帮助的建议和讨论。(⋯⋯)我感谢JoanMitchell建立了本书的索引。我也感谢JeanHarpley帮助编辑了很多插图。ETPHarrison的JaneLoftus帮助整理了本书的手稿。我的编辑McGrawHill出版社的EricMunson在项目的整个过程中提供了鼓励和意见。通常一个人最该感谢的是他的同事、朋友和家庭。对于我尤其要表达自己的感激。我很难想象有人比我在CarnegieMellon拥有更好的智者云集的环境和更多的鼎力相助的朋友。在这些很多帮助过我的人当中我特别感谢SebastianThrun在这个项目的自始至终他一直对我进行着精神鼓励、技术指导等各种支持。我的父母与以往一样的鼓励我并在最恰当的时候问“已经完成了吗?”最后我一定要感谢我的家人:MeghanShannon和Joan。他们在不知不觉中以各种方式对此书作出了贡献。这本书是献给他们的。TomMMitchell第章绪论自从计算机被发明以来人们就想知道它们能不能学习。如果我们理解了计算机学习的内在机制即怎样使它们根据经验来自动提高那么影响将是空前的。想象一下在未来计算机能从医疗记录中学习获取治疗新疾病的最有效方法住宅管理系统分析住户的用电模式以降低能源消耗个人软件助理跟踪用户的兴趣并为其选择最感兴趣的在线新闻⋯⋯。对计算机学习的成功理解将开辟出全新的应用领域并使其计算能力和可定制性上升到新的层次。同时透彻地理解机器学习的信息处理算法也会有助于更好地理解人类的学习能力。目前我们还不知道怎样使计算机的学习能力和人类相媲美。然而一些针对特定学习任务的算法已经产生。关于学习的理论认识已开始逐步形成。人们开发出了很多实践性的计算机程序来实现不同类型的学习一些商业化的应用也已经出现。例如对于语音识别这样的课题至今为止基于机器学习的算法明显胜过其他的方法。在数据挖掘领域机器学习算法理所当然地得到应用从包含设备维护记录、借贷申请、金融交易、医疗记录等类似信息的大型数据库中发现有价值的信息。随着对计算机的理解的日益成熟机器学习必将在计算机科学和技术中扮演越来越重要的角色!通过一些特定的成就我们可以看到这门技术的现状:计算机已经能够成功地识别人类的讲话(WaibelLee)预测肺炎患者的康复率(Cooperetal)检测信用卡欺诈在高速公路上驾驶(Pomerleau)以接近人类世界冠军的水平对弈西洋双陆棋①这样的游戏(Tesauro,)。已有了很多理论成果能够对训练样例数量、假设空间大小、和学得假设错误率这三者间的基本关系进行刻画。我们正在开始获取人类和动物学习的原始模型用以理解它们和计算机的学习算法间的关系(例如LairdetalAndersonQinetalChiBassockAhnBrewer)。在过去的十年中无论是应用、算法、理论还是生物系统的研究都取得了值得注目的进步。机器学习最近的几种应用被归纳在表中。LangleySimon()以及Rumelhartetal()调查了机器学习的一些其他应用。表机器学习的一些成功应用•学习识别人类的讲话所有最成功的语音识别系统都使用了某种形式的机器学习技术。例如Sphinx系统(参见Lee)可学习特定讲话者的语音识别策略从检测到的语音信号中识别出基本的音素(phoneme)和单词。神经网络学习方法(例如Waibeletal)和隐式马尔可夫模型(hiddenMarkovmodel)的学习方法(例如Lee)在语音识别系统中也非常有效它们可以让系统自动适应不同的讲话者、词汇、麦克风特性和背景噪音等等。类似的技术在很多信号解释课题中有应用潜力。•学习驾驶车辆①译注:一种类似飞行棋的游戏双方各持十五子通过掷骰子来决定棋子移动的步数。机器学习方法已被用于训练计算机控制的车辆使其在各种类型的道路上正确行驶。例如ALVINN系统(Pomerleau)已经利用它学会的策略独自在高速公路的其他车辆之间奔驰以英里的时速共行驶了英里。类似的技术可能在很多基于传感器的控制问题中得到应用。•学习分类新的天文结构机器学习方法已经被用于从各种大规模的数据库中发现隐藏的一般规律。例如决策树学习算法已经被美国国家航空和航天局(NASA)用来分类天体数据来自第二帕洛马天文台太空调查(Fayyadetal)。这一系统现在被用于自动分类太空调查中的所有天体其中包含了T字节的图像数据。•学习以世界级的水平对弈西洋双陆棋最成功的博弈类(如西洋双陆棋)计算机程序是基于机器学习算法的。例如世界最好的西洋双陆棋程序TDGammon(Tesauro,)是通过一百万次以上的和自己对弈来学习其策略的。现在它的水平能与人类的世界冠军相当。类似的技术被应用于许多实际问题其中需要高效地搜索庞大的搜索空间。本书针对机器学习这个领域描述了多种学习范型、算法、理论以及应用。机器学习从本质上是一个多学科的领域。它吸取了人工智能、概率统计、计算复杂性理论、控制论、信息论、哲学、生理学、神经生物学等学科的成果。表归纳了这些学科中影响机器学习的关键思想。本书的素材基于不同学科的成果然而读者不必精通每一个学科。来自这些学科的关键理论将使用非专业的词汇讲解其中不熟悉的术语和概念会在需要时加以介绍。表一些学科和它们对机器学习的影响•人工智能学习概念的符号表示。作为搜索问题的机器学习。作为提高问题求解能力途径的学习。使用先验的知识和训练数据一起引导学习。•贝叶斯方法作为计算假设概率的基础的贝叶斯法则。朴素贝叶斯分类器。估计未观测到变量的值的算法。•计算复杂性理论不同学习任务中固有的复杂性的理论边界以计算量、训练样例数量、出错数量等衡量。•控制论为了优化预定目标学习对各种处理过程进行控制学习预测被控制的过程的下一个状态。•信息论熵和信息内容的度量。学习的最小描述长度方法。编码假设时它的最佳编码和与最佳训练序列的关系。•哲学“奥坎姆的剃刀”(Occam’srazor)①:最简单的假设是最好的。从观察到的数据泛化的理由分析。•心理学和神经生物学实践的幂定律(powerlawofpractice)该定律指出对于很大范围内的学习问题人们的反应速度随着实践次数的幂级提高。激发人工神经网络的学习模式的神经生物学研究。•统计学①译注:也称“吝啬律(LawofParsimony’”或“节约律(LawofEconomy)”主要思想为简单的理论(或假设)优于复杂的因英国哲学家奥坎姆(~)频繁使用这一原则故称为“奥坎姆剃刀”。在估计有限数据样本上的假设精度时出现的误差(例如偏差和方差)的刻画。置信区间统计检验。学习问题的标准描述让我们从几个实际的学习任务开始研究机器学习。根据本书的目的我们给学习一个宽广的定义以使其包括任何计算机程序通过经验来提高某任务处理性能的行为。更准确地讲利用经验改善系统自身的性能定义:对于某类任务T和性能度量P如果一个计算机程序在T(任务)上以P(性能标准)衡量的性能随着经验E而自我完善那么我们称这个计算机程序在从经验E学习。例如对于学习下西洋跳棋①的计算机程序它可以通过和自己下棋获取经验它担负的任务是参与西洋跳棋对弈它的性能用它赢棋的能力来衡量。通常为了很好地定义一个学习问题我们必须明确这样三个特征:任务的种类衡量任务提高的标准经验的来源。西洋跳棋学习问题:•任务T:下西洋跳棋•性能标准P:比赛中击败对手的百分比•训练经验E:和自己进行对弈我们可以用以上方法定义很多学习问题例如学习手写识别、学习自动驾驶机器人汽车。手写识别学习问题:•任务T:识别和分类图像中的手写文字•性能标准P:分类的正确率•训练经验E:已知分类的手写文字数据库机器人驾驶学习问题:•任务T:通过视觉传感器在四车道高速公路上驾驶①译注:为了更好理解本例下面简要介绍一下这种跳棋。棋盘为×方格深色棋格不可着子。可单步行走亦可每步跨对方一子单跳或连跳被跨越的子被杀出局。到达对方底线的子成为王可回向行走(成为王前只可前行)又可隔空格飞行。下图为西洋跳棋棋盘示例(起始状态)。•性能标准P:平均无差错行驶里程(差错由人类的监督裁定)•训练经验E:注视人类驾驶时录制的一系列图像和驾驶指令这里对学习的定义很宽广足以包括大多数惯于被称为“学习”的任务就像我们日常使用的这个词一样。同时它也包括了以非常简明的方式通过经验自我提高的计算机程序。例如一个允许用户更新数据条目的数据库系统也符合我们对学习系统的定义:它根据从数据库更新得到的经验提高它回答数据查询的能力。与其担心这种行为与“学习”这个词日常谈论的非正式含义相混淆我们索性简单地采用我们的科技型定义一类计算机程序通过经验提高的过程。在这个范畴内我们会发现很多问题或多或少需要较复杂的解决办法。这里我们并非要分析“学习”这个单词的日常含义。而是要精确地定义一类囊括我们感兴趣的学习形式的问题探索解决这类问题的方法并理解学习问题的基础结构和过程。设计一个学习系统为了演示一些机器学习的基本设计方法和途径考虑设计一个学习下西洋跳棋的程序。我们的目标是让它进入西洋跳棋世界锦标赛。我们采用最显而易见的标准衡量它的性能:在世界锦标赛上打赢的比赛占总参赛次数的百分比。选择训练方式我们面临的第一个设计问题是选取训练经验的类型使系统从中进行学习。给学习器提供的训练经验对它的成败有重大的影响。一个关键属性是训练经验能否为系统的决策提供直接或间接的反馈。例如对于学习下西洋跳棋系统可以从直接的(direct)训练样例即各种棋盘状态和相应的正确走子中学习。另一种情况它可能仅有间接(indirect)的信息包含很多过去的对弈序列和最终结局。对于后一种情况关于博弈中较早走子的正确性必须从对弈最终的输赢来推断。这时学习器又额外面临一个信用分配(creditassignment)问题也就是考虑每一次走子对最终结果的贡献程度。信用分配可能是一个非常难以解决的问题因为如果后面下得很差那么即使起初的走子是最佳的这盘棋也会输掉。所以通常从直接的训练反馈来学习比间接的简单。训练经验的第二个重要属性是学习器可以在多大程度上控制训练样例序列。例如学习器可能依赖施教者选取棋盘状态和提供每一次的正确移动。或者学习器可能自己提出它认为特别困惑的棋局并向施教者询问正确的走子。或者学习器可以完全控制棋局和(间接的)训练分类就像没有施教者时它和自己对弈进行学习一样。注意对于最后一种情况学习器可能选择以下两种情况中的一种:第一试验它还未考虑过的全新棋局第二在它目前发现的最奏效的路线的微小变化上对弈以磨砺它的技能。后续的章节考虑一些学习框架包括了以下几种情况:训练经验是以超乎学习器控制的随机过程提供的学习器可向施教者提出不同类型的查询以及学习器通过自动探索环境来搜集训练样例。训练经验的第三个重要属性是训练样例的分布能多好地表示实例分布而最终系统的性能P是通过后者来衡量的。一般而言当训练样例的分布和将来的测试样例的分布相似时学习具有最大的可信度。对于我们的西洋跳棋学习性能指标P是该系统在世界锦标赛上赢棋的百分比。如果它的训练经验E仅由和它自己对弈的训练组成便存在一个明显的危险:这个训练可能不能充分地表示该系统以后被测试时的情形。例如学习器可能在训练中从来未遇到过某些非常关键性的棋局而它们又非常可能被人类世界冠军采用。实际上学习的样例通常与最终系统被评估时的样例有一定差异学习器必须能从中进行学习(举例来说世界级的西洋跳棋冠军可能不会有兴趣教一个程序下棋)。这的确是一个问题因为掌握了样例的一种分布不一定会导致对其他的分布也有好的性能。可以看到目前多数机器学习理论都是基于训练样例与测试样例分布一致这一前提。尽管我们需要这样的前提以便得到理论的结果但同样必须记住在实践中这个假设经常是不严格成立的。下面继续进行算法设计我们决定系统将通过和自己对弈来训练。这样的好处是不需要外界的训练者所以可以让系统产生无限多的训练数据只要时间允许。现在有了一个完整的学习任务。西洋跳棋学习问题:•任务T:下西洋跳棋•性能标准P:世界锦标赛上击败对手的百分比•训练经验E:和自己进行对弈为了完成这个学习系统的设计现在需要选择:要学习的知识的确切类型对于这个目标知识的表示一种学习机制选择目标函数下一个设计选择是决定要学习的知识的确切类型以及执行程序怎样使用这些知识。我们从一个对于任何棋局都能产生合法(legal)走子的西洋跳棋博弈程序开始。那么最终的程序仅须学会从这些合法的走子中选择最佳的。这个学习任务代表了一大类任务:合法走子定义了某个先验已知的巨大搜索空间但最佳的搜索策略未知。很多最优化问题都可归于此类例如对于生产过程的调度和控制问题生产中的每一步都很清楚但调度这些步骤的最佳策略未知。为了学习从合法走子中作出选择很明显要学习的信息类型就是一个程序或函数它对任何给定的棋局能选出最好的走法。可称此函数为ChooseMove并用记法ChooseMove:B→M来表示这个函数以合法棋局集合中的棋盘状态作为输入并从合法走子集合中产生某个走子作为输出。在关于机器学习的所有讨论中我们发现可以把对任务T提高性能P的问题简化为学习象ChooseMove这样某个特定的目标函数(targetfunction)的问题。所以目标函数的选择是一个关键的设计问题。尽管在例子中很明显应把ChooseMove作为目标函数但我们会发现学习这个目标函数是非常困难的原因是提供给系统的是间接的训练经验。另外一个可供选择的目标函数是一个评估函数它为任何给定棋局赋予一个数字的评分。可以发现对于本例学习这个目标函数更简单。令这个目标函数为V并用V:B→ℜ来表示V把任何合法的棋局映射到某一个实数值(用ℜ来表示实数集合)。我们打算让这个目标函数V给好的棋局赋予较高的评分。如果系统能够成功地学会这个目标函数V那么它便能使用此函数轻松地找到当前棋局的最佳走法。实现的方法是先产生每一个合法走子对应的所有后续棋局然后使用V来选取其中最佳的后继棋局从而选择最好的走子。对于任意棋局目标函数V的准确值应该是多少呢?当然任何对较好的棋局赋予较高的分数的评估函数都适用。然而最好在那些产生最佳对弈的众多方法中定义一个特定的目标函数V。可以看到这将使得设计一个训练算法变得简单。因此对于集合B中的任意的棋局状态b我们如下定义目标函数V(b):如果b是一最终的胜局那么V(b)=如果b是一最终的负局那么V(b)=如果b是一最终的和局那么V(b)=如果b不是最终棋局那么V(b)=V(b′)其中b′是从b开始双方都采取最优对弈后可达到的终局。然而由于这个定义的递归性它的运算效率不高所以这个定义对于西洋跳棋比赛者不可用。除了无关紧要的前三种终局的情况对于某一个棋盘状态(情况)b要决定它的值V(b)需要向前搜索到达终局的所有路线!由于这个定义不能由西洋跳棋程序高效地运算这个定义被称为不可操作的定义。当前的目标是发现一个可操作的定义V它能够被西洋跳棋程序用来在合理的时间内评估棋局并选取走法。这样这种情况的学习任务被简化成发现一个理想目标函数V的可操作描述。通常要完美地学习这样一个V的可操作的形式是非常困难的。事实上我们经常希望学习算法仅得到目标函数的某个近似(approximation)由于这个原因学习目标函数的过程常被称为函数逼近(functionapproximation)。在当前的讨论中用V来表示程序中实际学习到的函数以区别理想目标函数V。ˆ选择目标函数的表示至此我们已经确定了目标函数V接下来必须选择一个表示被学习程序用来描述要学习的函数V。对此也有很多设计选择。例如可以将表示为一张大表对于每个惟一的棋盘状态b表中有惟一的表项来确定它的状态值Vˆb)。或者可以让程序用一个规则集合来匹配棋局的特征以表示Vˆ或采用一个与预定义棋盘特征有关的二次多项式函数或者用人工神经元网络。通常选择这个描述包含一个重要的权衡过程。一方面我们总希望选取一个非常有表征力的描述以最大可能地逼近理想的目标函数V。另一方面越有表征力的描述需要越多的训练数据使程序能从它表示的多种假设中做出选择。为了简化讨论现在选择一个简单的表示法:对于任何给定的棋盘状态函数V可以通过以下棋盘参数的线性组合来计算:ˆVˆ(ˆzx:棋盘上黑子的数量zx:棋盘上红子的数量zx:棋盘上黑王的数量zx:棋盘上红王的数量zx:被红子威胁的黑子数量(即会在下一次被红吃掉的子)zx:被黑子威胁的红子数量于是学习程序把V(b)表示为一个线性函数ˆVˆ(b)=wwxwxwxwxwxwx其中w到w为数字系数或叫权由学习算法来选择。在决定某一个棋盘状态的分值时w到w决定了不同的棋盘特征的相对重要性而权w为一个附加的常量。概括一下目前为止的设计。我们已经详细阐述了这个学习问题的原型即为它选择一种类型的训练经验、一个要学习的目标函数和这个目标函数的一种表示法。现在的学习任务是:西洋跳棋程序的部分设计•任务T:下西洋跳棋•性能标准P:世界锦标赛上击败对手的百分比•训练经验E:和自己进行训练对弈•目标函数:V:B→ℜ•目标函数的表示:V(b)=wˆwxwxwxwxwxwx前三条是对学习任务的说明后两条制定了为实现这个学习程序的设计方案。注意这个设计的关键作用是把学习西洋跳棋战略的问题简化为学习目标函数描述中系数w到w值的问题。选择函数逼近算法为了学习目标函数V需要一系列训练样例每一个样例描述了特定的棋盘状态b和它的训练值Vˆtrain(b)。换言之每一个训练样例是形式为<bVtrain(b)>的序偶。举例来说下面的训练实例描述了一个黑棋胜利(注意x=表示红棋已经没有子了)的棋盘状态b它的目标函数值Vtrain(b)为。<<x=x=x=x=x=x=>>下文描述了一个过程它先从学习器可得的间接训练经验中导出上面的训练样例然后调整权值wi以最佳拟合这些训练样例。估计训练值根据以上的学习模型学习器可以得到的训练信息仅是对弈最后的胜负。另一方面我们需要训练样例为每个棋盘状态赋予一个分值。给对弈结束时的棋盘状态评分是容易的而要给对弈结束前的大量中间棋局评分就不那么容易了。因为一盘棋的最终输赢未必能说明这盘棋当中的每一个棋盘状态的好或坏。例如即使某个程序输了一盘棋仍会有这样的情况这盘棋前面的棋局应该给予很高的评价失败的原因在于后来糟糕的走法。尽管估计中间棋局训练值具有内在的模糊性但令人惊讶的是有一个简单的方法却取得了良好结果。这种方法对于任何中间棋局b的训练值Vtrain(b)等于V(Successor(b))其中V是学习器采用的对V的近似Successor(b)表示b之后再轮到程序走棋时的棋盘状态(也就是程序走了一步和对手回应一步后的棋局)。ˆˆ这种估计训练值的方法可被归纳为:训练值估计法则Vtrain(b)←V(Successor(b))()ˆ或许这看起来有点离奇只使用当前的来估计训练值这一训练值又被用来更新V。但请注意我们是在用后续棋局Successor(b)的估计值来估计棋局b的值。凭直觉我们可以看到越接近游戏结束的棋局的V越趋向精确。事实上在特定条件下(将在第章讨论)这种基于对后继棋局进行估计的迭代估计训练值的方法已被证明可以近乎完美地收敛到VVˆˆˆtrain估计值。权值调整剩下的事情就是为这个学习算法选择最适合训练样例{<b,Vtrain(b)>}的权wi。第一步必须定义最佳拟合(bestfit)训练数据的含义。一种常用的方法是把最佳的假设(或权向量集合)定义为使训练值和假设V预测出的值间的误差平方E最小。ˆ)(,))(ˆ)((bVbVEtrainbVbtrain−≡∑>∈<训练样例至此我们的目标就是寻找权值(等价地寻找V)使对于观测到的训练数据E值最小化。第章将讨论在什么条件下最小化误差平方和等价于寻找给定观测训练数据下的最可能假设。ˆ已经知道一些算法可以得到线性函数的权使此定义的E最小化。在这里需要一个算法它可以在有了新的训练样例时进一步改进权值并且它对估计的训练数据中的差错有好的健壮性。一个这样的算法被称作最小均方法(leastmeansquares)或叫LMS训练法则。对于每一训练样例它把权值向减小这个训练数据误差的方向略微调整。如第章讨论的那样这个算法可被看作对可能的假设(权值)空间进行随机的梯度下降搜索以使误差平方和E最小化。LMS算法是这样定义的:LMS权值更新法则对于每一个训练样例<bVtrain(b)>•使用当前的权计算V(b)ˆ•对每一个权值wi进行如下更新wi←wiη(Vtrain(b)V(b))xˆi这里η是一个小的常数(比如)用来调整权值更新的幅度。为了直观地理解这个权值更新法则的工作原理请注意当误差(Vtrain(b)(b))为时权不会被改变。当(VVˆtrain(b)V(b))为正时(例如当V(b)太低时)每一个权值会根据其对应特征值增加一定的比例。这会提升V(b)的值而减小误差。注意如果某个参数xˆˆˆi为那么它的值不会因这个误差而改变这样便使只有那些在训练样例的棋局中确实出现的特征的权值才被更新。令人吃惊的是在一定的条件下这种简单的权值调整方法被证明可以收敛到Vtrain值的最小误差平方逼近(就像第章所讨论的)。最终的设计西洋跳棋学习系统的最终设计可以自然地用四个清楚的程序模块来描述这些模块在很多学习系统中是核心组件。这四个模块被归纳在图中它们是:解决给定的任务在此就是对弈西洋跳棋。它把新问题(新一盘棋)的实例作为输入产生一组解答路线(对弈历执行系统(Performancesystem)这个模块是用学会的目标函数来史记录)作为输出。在这里执行系统采用的选择下一步走法的策略是由学到的评估函数Vˆ来决定的。所以我们期待它的性能会随着评估函数的日益准确而提高。插图原书页码:Experim(初始棋局)对弈历史)训练样例entGenerator试验生成器NewProblem(initialgameboard)新问题PerformanceSystem执行系统Solutiontrace(gamehistory)解答路线(Critic鉴定器TrainingexamplesGeneralizer泛化器Hypothesis假设图西洋跳棋学习程序的最终设计鉴定器(Critic)它以对例。如图所示每一个训练样例对应路线中的某个棋盘状态和目标函数给这个样例的评估值Vtrain的它从特定的训练样例中泛化猜测一个一般函数使其能够覆盖这些样例以及样例之外的生成器(ExperimentGenerator)它以当前的假设(当前学到的函数)作为输入输出一个新的问题(例如最初的棋局)供执行系统去探索。它的角色是挑选新的练习问题以使总体来看我们为西洋跳棋程序作的设计就是产生执行系统、鉴定器、泛化器和实验生弈的路线或历史记录作为输入输出目标函数的一系列训练样。在我们的例子中鉴定器对应式给出的训练法则。泛化器(Generalizer)它以训练样例作为输入输出一个假设作为它对目标函数估计。情形。在我们的例子中泛化器对应LMS算法输出假设是用学习到的权值w,,w描述的函数Vˆ。实验整个系统的学习速率最大化。在我们的例子中实验生成器采用了非常简单的策略:它总是给出一个同样的初始棋局来开始新的一盘棋。更完善的策略可能致力于精心设计棋子位置以探索棋盘空间的特定区域。成器的特定实例。很多机器学习系统通常可以用这四个通用模块来刻画。这个评估函数被限制为仅依赖于六个棋盘特征。如果目标函数真的可表示为这些特定参数的线性组合那么程序设计西洋跳棋程序的流程被归纳在图中。这个设计已经在几方面把学习任务限制在较小的范围内。要学习的知识类型被限制为一个单一的线性评估函数。而且学到这个目标函数的可能性很大。反之最多只希望它学到一个合理的近似因为一个程序当然不能学会它根本不能表示的东西。插图原书页码:DetermineTypeofTrainingExperience决定训练经验形式Gamesagainstexperts与专家对弈Gamesagainstself与自己对弈Tableofcorrectmoves正确走子的表格DetermineTargetFunction决定目标函数Board>move棋盘→走子Board>value棋盘→分值DetermineRepresentationofLearnedFunction决定目标函数的表示Polynomial多项式Linearfunctionofsixfeatures六个参数的线性函数Artificialneuralnetwork人工神经网络DetermineLearningAlgorithm决定学习算法Gradientdescent梯度下降Linearprogramming线性规划CompletedDesign完成的设计图西洋跳棋学习程序的设计过程概述我们假定真实函数V的合理的近似确实可被表示为这种形式。那么问题变成这种学习技术是否确保能发现一个合表明对于某些类型的搜索问题在相当严格的前提下这种方法确实收敛到期望的评估函数。很幸运实践经验表明理的近似。第章提供了一种理论分析这种学习评估函数的途径经常是成功的甚至在能被证明的情形之外也是如此。已经设计的程序能学得足够好而击败人类的西洋跳棋冠军吗?或许不能。部分地这是因为Vˆ的线性函数表示太简单以致于不能很好捕捉这种棋的微妙之处。然而如果给与一个更完善的目标函数表示法这种通用的途径事实上可以非常成功。例如Tesauro(,)报告存的“最接近的”情形来匹配新的情况(最近邻算法第章)。或者可以产生大量候选的西洋跳棋程序并让它们相互比赛保留最成功的程序并进一步用模拟进在机器学习方面即对非常大的假设空间进行搜索例如考虑一下上面的西洋跳棋学习程序输出的假设空间。这个假设空间包含所有可由权w到w的不同值的评估函数。于是学习器的任务就是搜索这个大的空间寻找与训练数据最佳拟合的假设。表示法适合于学习不同的目标函数。对于其中的每一种假设表示法对应的学习算法发挥不同内在结构的优势来组织对假设空间的搜搜索空间的内在结构来刻画学习方法。我们也会发现这种观点对于形式化地分析要搜索的假设空间的大小、可利用的训练样例的数量以及一个与训练数据一致的假设能泛化到西洋跳棋例子提出了机器学习方面很多普遍问题。机器学习这门学科和本书的绝大部分都致•从特定的训练数据学习一般的目标函数存在什么样的算法?如果提供了充能最好。•多少训练数据是充足的?怎样找到学习到的假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系?了学习下西洋双陆棋的程序的类似设计方法是学习一个非常类似的棋局评估函数。它的程序使用人工神经元网络表示学到的评估函数它考虑对棋局的完整描述而不是棋盘的几个参数。经历了一百万次以上的自我生成的训练比赛后他的程序能够和一流的人类西洋双陆棋选手一争高下。当然还可能为西洋跳棋学习任务设计很多其他的算法。例如一种可能只简单地存储训练样例然后去寻找保化的方式来培育或变异它们(遗传算法第章)。人类似乎遵循另一种途径寻找学习策略他们分析或向自己解释比赛中碰到的成败的原因(基于解释的学习第章)。上面的设计是这些种类中的一个简单的算法它是为了给我们今后的针对特定类别的任务的学习方法的设计奠定基础。机器学习的一些观点和问题一个有效的观点是机器学习问题经常归结于搜索问题以确定最佳拟合观察到的数据和学习器已有知识的假设。针对拟合权值的LMS算法通过迭代调整权值实现了这个目的每当假设的评估函数预测出一个与训练数据有偏差的值时就对每个权值进行校正。当学习器考虑的假设表示定义了一个连续的参数化的潜在假设空间时这个算法很有效。本书的很多章节给出了对一些基本表示(例如线性函数、逻辑描述、决策树、人工神经元网络)定义的假设空间的搜索算法。这些不同的假设索。自始至终本书都贯穿着这种把学习问题视为搜索问题的看法从而通过搜索策略和学习器探索的未见实例的置信度这三者之间的关系非常有用。机器学习的问题力于回答类似下面的问题:足的训练数据什么样的条件下会使特定的算法收敛到期望的函数?哪个算法对哪些问题和表示的性•学习器拥有的先验知识是怎样引导从样例进行泛化的过程的?当先验知识仅仅是近似正确时它们会有帮助吗?对于选择有用的后续训练经验什么•样的策略最好?这个策略的选择会怎样•种方式系统该试图•和学习目标函数的能力?这本介力的理论结果以及机器学习应用于解决现实问题的例子。只要可能各章的写作都力争与阅读顺序无关。然而一些相互依赖性是不可避免的。如果本书被用作教科书我建议首先完成第一和第二章余下各章基本可以以任意顺序阅读。长度为一个学期的机器学习课程可以包括前七章以及额外的几个最感兴趣的章节。下面简要浏览一下各章。以及梯和对不同学•这一章包括一个应用贝叶•括可能近似正确(ProbablyApproximately•的推理。•泛化的学习方法。•增强学习。这种方法是为了处理来自训练信息中的间接的或每章的结尾包含了所覆盖的主要概念的小结、更新包括数~tommlbookhtml访问到。影响学习问题的复杂性?怎样把学习任务简化为一个或多个函数逼近问题?换一学习哪些函数?这个过程本身能自动化吗?学习器怎样自动地改变表示法来提高表示如何阅读本书书绍了机器学习的主要算法和途径不同学习任务可行性和特定算法能•第章包括基于符号和逻辑表示的概念学习。也讨论了假设的一般到特殊偏序结构以及学习中引入归纳偏置的必要性。•第章包括决策树学习和过度拟合训练数据的问题。这一章也剖析了奥坎姆剃刀该原则建议在与数据一致的假设中选择最短假设。•第章包括人工神经网络的知识特别是研究已久的反向传播算法度下降的一般方法。这一章包含一个详细的基于神经网络的人脸识别实例该例子需要的数据和算法可以在万维网上得到。•第章给出了来自统计和估计理论的基础概念着重于使用有限的样本数据评估假设的精度。这一章包含了用于估计假设精度的置信空间习算法的精度进行比较的方法。第章介绍机器学习的贝叶斯观点。既包括了使用贝叶斯分析刻画非贝叶斯学习算法又包括了直接处理概率的贝叶斯算法。斯分类器来分类文本文档的详细例子所需的数据和软件可以在万维网上得到。第章覆盖了计算学习理论包CorrectPAC)学习模型和出错界限(MistakeBound)学习模型。本章讨论了联合多个学习方法的加权多数(WeightedMajority)算法。第章描述了基于实例的学习方法包括最近邻学习局部加权回归和基于案例•第章讨论了根据生物进化建模的学习算法包括遗传算法和遗传编程。第章覆盖了一组学习规则集合的算法包括学习一阶Horn子句的归纳逻辑编程方法。•第章包含了基于解释的学习即一种使用以前的知识解释观察到的实例然后根据这些解释•第章讨论了把以前的近似知识结合进现有的训练数据中以提高学习精度的方法。在其中符号算法和神经网络算法都有讨论。第章讨论了延迟的反馈。本章前面提及的下棋学习程序是增强学习的一个简单的例子。进一步阅读的参考和习题。其他对章节的据集和算法的实现都可从网址http:wwwcscmuedu小结和补充读物机器学习致力于研究建立能够根据经验自我提高处理性能的计算机程序。本章的要点包括:•学被证明有很大的实用价值。它们在以下方面特别有用:(a)数据挖掘问题即从大量数据中发现可能包含在其中的有价信用贷款的普遍规则)(b)在某些困难的领域中人们可能还不具有开发出高效的算法所需的知识(比如从图像库中识别出人脸)(c)计算•••选择训练经验的类型、要学和其他先验的约束或知识。本书的大部分内容围绕着搜索各有很多关于机器学习最新研究成果的优秀资源可供阅读。相关的杂志包括《机器学习》(MachineLe《美国统计协机器智能学报的年机器习算法在很多应用领域值的规律(例如从患者数据库中分析治疗的结果或者从财务数据中得到机程序必须动态地适应变化的领域(例如在原料供给变化的环境下进行生产过程控制或适应个人阅读兴趣的变化)。机器学习从不同的学科吸收概念包括人工智能概率和统计计算复杂性信息论心理学和神经生物学、控制论、以及哲学。一个完整定义的学习问题需要一个明确界定的任务、性能度量标准以及训练经验的来源。机器学习算法的设计过程中包含许多选择包括习的目标函数、该目标函数的表示形式、以及从训练样例中学习目标函数的算法。•学习的过程即搜索的过程搜索包含可能假设的空间使得到的假设最符合已有的训练样例种假设空间(例如包含数值函数、神经网络、决策树、符号规则的空间)的不同学习方法和理论上这些搜索方法在什么条件下会收敛到最佳假设。arning)《神经计算》(NeuralComputation)《神经网络》(NeuralNetworks)会期刊》(JournaloftheAmericanStatisticalAssociation)和《IEEE模式识别和》(IEEETransactionsonPatternAnalysisandMachineIntelligence)。也有大量会覆盖了机器学习的各个方面包括国际机器学习会议(ICML)神经信息处理系统(NIPS)计算学习理论会议(CCLT)国际遗传算法会议(ICGA)国际知识发现和数据挖掘会议(ICKDD)欧洲机器学习会议(ECML)等。习题给出三种机器学习方法适合的应用三种不适合的应用。挑选本书未提及的应用并对每个应用以一句话来评价。挑选一些本书未提到的学习任务。用英文写一段话非正式地加以描述。再尽可能精确地描述出它的任务、性能衡量标准和训练经验。最后给出要学习的目标函数和它的表示。讨论这个任务设计中考虑的主要折中。证明本章描述的LMS权更新法则采用了梯度下降方法使误差平方最小化。确切地讲像文中那样定义方差E。然后计算E对权wi的导数其中假定与文中定义的一样是一个线性函数。梯度下降是通过与)(ˆbViwE∂∂−比例地更新每个权值实现的。所以必须证明对于所遇到的每一个训练样例LMS训练法则都是按这个比例来改变权值。成图中实验生成器模块可采用其他一些策略。确切地讲考虑实验生成器用下面的策略提出新的棋局:•产生随机的合法的棋局•从前面的对弈中挑选一个棋局然后走一步上次没有走的棋而产生新的棋局•一种你自己设计的策略讨论这些策略的优劣。如果训练样例的数量是固定的哪一个效果最好?假定性能衡量标准是在世界锦标赛上赢棋最多。使用类似于西洋跳棋问题的算法实现一个更简单的tictactoe游戏①。把学习到的函数V表示为自选的棋局参数的线性组合。要训练这个程序可以让它和它的另一个拷贝反复比赛后者使用手工建立的固定评估函数。用图表绘出你的程序胜利的百分比对应于训练次数。ˆ参考文献①译注:该游戏棋盘为X方格双方交互落子首先实现自方三子连一线者胜。第章概念学习和一般到特殊序从特殊的训练样例中归纳出一般函数是机器学习的中心问题。本章介绍概念学习:给定某一类别的若干正例和反例从中获得该类别的一般定义。概念学习也可被看作一个搜索问题它在预定义的假设空间中搜索假设使其与训练样例有最佳的拟合度。多数情形下为了高效的搜索可以利用假设空间中一种自然形成的结构即一般到特殊偏序结构。本章展示了几种概念学习算法并讨论了这些算法能收敛得到正确假设的条件。这里还分析了归纳学习的本质以及任意程序能从训练数据中泛化的理由。介绍许多机器学习问题涉及到从特殊训练样例中得到一般概念。比如人们不断学习的一些一般概念和类别包括:鸟类、汽车、勤奋的学习等。每个概念可被看作一个对象或事件集合它是从更大的集合中选取的子集(如从动物的集合中选取鸟类)或者是在这个较大集合中定义的布尔函数(如在动物集合中定义的函数它对鸟类产生true并对其他动物产生false)。本章考虑的问题是给定一样例集合以及每个样例是否属于某一概念的标注怎样自动推断出该概念的一般定义。这一问题被称为概念学习(conceptlearning)或称从样例中逼近布尔值函数。定义:概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。一个概念学习任务为了良好地理解概念学习考虑一个概念学习的例子目标概念是:“Aldo进行水上运动的日子”。表描述了一系列日子的样例每个样例表示为属性的集合。属性EnjoySport表示这一天Aldo是否乐于进行水上运动。这个任务的目的是基于某天的各属性以预测出该天EnjoySport的值。表目标概念EnjoySport的正例和反例ExampleSkyAirTempHumidityWindWaterForecastEnjoySportSunnyWarmNormalStrongWarmSameYesSunnyWarmHighStrongWarmSameYesRainyColdHighStrongWarmChangeNoSunnyWarmHighStrongCoolChangeYes在这种情况下采取什么样的形式来表示假设呢?可以先考虑一个较为简单的形式即实例的各属性约束的合取式。在这里可令每个假设为个约束的向量这些约束指定了属性Sky、AirTemp、Humidity、Wind、Water和Forecast的值。每个属性可取值为:z由“”表示任意值z明确指定的属性值(如AirTemp=Warm)z由“∅”表示不接受任何值如果某些实例x满足假设h的所有约束那么h将x分类为正例(h(x)=)。比如为判定Aldo只在寒冷和潮湿的日子里进行水上运动(并与其他属性无关)这样的假设可表示为下面的表达式:<,Cold,High,,,>最一般的假设是每一天都是正例可表示为:<,,,,,>而最特殊的假设即每一天都是反例表示为:<∅,∅,∅,∅,∅,∅>综上所述EnjoySport这个概念学习任务需要学习的是使EnjoySport=Yes的日子并将其表示为属性约束的合取式。一般说来任何概念学习任务能被描述为:实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。以这种一般形式定义的EnjoySport概念学习任务见表。表EnjoySport概念学习任务n已知:n实例集X:可能的日子每个日子由下面的属性描述:nSky(可取值为SunnyCloudy和Rainy)nAirTemp(可取值为Warm和Cold)nHumidity(可取值为Normal和High)nWind(可取值为Strong和Weak)nWater(可取值为Warm和Cool)nForecast(可取值为Same和Change)n假设集H:每个假设描述为个属性SkyAirTempHumidityWindWater和Forecast的值约束的合取。约束可以为“”(表示接受任意值)“∅”(表示拒绝所有值)或一特定值。n目标概念c:EnjoySport:X→{,}n训练样例集D:目标

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/49

机器学习中文版

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利