第一章-引言(机器学习)

1、1机器学习第1章 引言2自我介绍 张伟，东北大学信息学院教授。 电子邮箱： 3机器学习简介 “机器学习”一般被定义为一个系统自我改进的过程。 从最初的基于神经元模型以及函数逼近论的方法研究，到以符号演算为基础的学习, 至最新的统计学习的兴起，机器学习一直都在相关学科的实践应用中起着主导作用。 研究人员们借鉴了各个学科的思想来发展机器学习，但关于机器学习问题的实质究竟是什么尚无定论尚无定论。不同的机器学习方法也各有优缺点，只在其适用的领域内才有良好的效果。 机器学习算法在很多应用领域被证明有很大的实用价值：（a）数据挖掘问题；（b）在某些人们可能还不具有开发出高效的算法所需的知识（比如，从图像库

2、中识别出人脸）。 因此，以枚举的方法描述机器学习中的各个理论和算法可能是最合适的途径。 4机器学习简介 机器学习一书正是以枚举的方式来介绍机器学习的。其主要涵盖了目前机器学习中各种最实用的理论和算法，包括概念学习、决策树、神经网络、贝叶斯学习、遗传算法、SVM学习等。 对每一个主题，作者不仅进行了十分详尽和直观的解释，还给出了实用的算法流程。在卡内基梅隆卡内基梅隆 CMU等许多大学，本书都被作为机器学习课程的教材。 本书的作者Tom MMitchell在机器学习领域享有盛名。他是卡内基梅隆大学的教授。他还是美国人工智能协会(AAAI)的主席，并且是机器学习杂志和国际机器学习年会(ICML)的创

3、始人。 本课程的目的：使学生掌握基本的机器学习算法，能够应用解决于文本分类等实际问题.激发兴趣,期末考试。 5什么是机器学习什么是机器学习计算机程序如何随着经验积累自动提高性能，即系统自我改进的过程1。历史上成功应用学习识别人类讲话(Sphinx系统)学习驾驶车辆(ALVINN系统)学习分类新的天文结构学习对弈西洋双陆棋6相关学科人工智能人工智能学习概念的符号表示。作为搜索问题的机器学习。作为提高问题求解能力途径的学习。使用先验的知识和训练数据一起引导学习。(八数码)贝叶斯方法贝叶斯方法作为计算假设概率的基础的贝叶斯法则。朴素贝叶斯分类器。估计未观测到变量的值的算法。计算复杂性理论计算复杂性理

4、论不同学习任务中固有的复杂性的理论边界，以计算量、训练样例数量、出错数量等衡量。控制论控制论为了优化预定目标，学习对各种处理过程进行控制，学习预测被控制的过程的下一个状态。信息论信息论熵是信息内容的度量。学习的最小描述长度方法。编码假设时，它的最佳编码和与最佳训练序列的关系。哲学哲学“奥坎姆的剃刀”（Occams razor）1：最简单的假设是最好的。从观察到的数据泛化的理由分析。 7学习问题的标准描述 定义 如果一个计算机针对某类任务T的用P衡量的性能根据经验E来自我完善，那么我们称这个计算机程序在从经验E中学习2 。 西跳棋学习问题的解释 E，和自己下棋 T，参与比赛 P，比赛成绩（或赢棋

5、能力，击败对手的百分比）8 手写识别学习问题：手写识别学习问题： 任务T：识别和分类图像中的手写文字 性能标准P：分类的正确率 训练经验E：已知分类的手写文字数据库 机器人驾驶学习问题：机器人驾驶学习问题： （link） 任务T：通过视觉传感器在四车道高速公路上驾驶 性能标准P：平均无差错行驶里程（差错由人类的监督裁定） 训练经验E：注视人类驾驶时录制的一系列图像和驾驶指令 9西洋跳棋 译注：为了更好理解本例，下面简要介绍一下这种跳棋。棋盘为88方格，深色棋格不可着子。1、可单步行走，2、亦可每步跨对方一子单跳或连跳，被跨越的子被杀出局。3、到达对方底线的子成为王，可回向行走（成为王前只可前行

6、），又可隔空格飞行。下图为西洋跳棋棋盘示例（起始状态）。10动态下棋11学习问题的标准描述（2） 定义很宽泛 这种行为与“学习”这个词日常谈论的含义相接近。甚至包括了以非常直接的方式通过经验自我提高的计算机程序(如,数据库查询)。需要更加细化。 实际的机器学习问题往往比较复杂，需要设计一个学习系统才能解决此类问题.12设计一个学习系统 基本设计方法和学习途径（以西洋跳棋为例） 选择训练经验 选择目标函数 选择目标函数的表示 选择函数逼近算法 最终设计13设计一个学习系统 西洋跳棋学习问题 任务T，下西洋跳棋 性能标准P，击败对手的百分比 训练经验E，和自己进行训练对弈 细化的设计学习系统首先要

7、选择经验E 明确三个关键属性14选择训练经验 第一个关键属性，训练经验能否为系统的决策提供直接或间接的反馈（间接+信用分配） 第二个重要属性，学习器在多大程度上控制样例序列（完全自我控制，“自我博奕”） 第三个重要属性，训练样例的分布能多好地表示实例分布，通过样例来衡量最终系统的性能（无限逼近） 于是我们的学习任务变成：15设计一个学习系统 西洋跳棋学习问题3 任务T，下西洋跳棋 性能标准P，击败对手的百分比 训练经验E，和自己进行训练对弈 要学习的知识的确切类型 对于这个目标知识的表示 一种学习机制16选择目标函数 目标函数ChooseMove ChooseMove: BM，接受合法棋局集合

8、中的棋盘状态作为输入，并从合法走子集合中选择某个走子作为输出 于是提高P变成学习ChooseMove: 我们把提高任务T的性能P的问题转化（或简化）为学习像ChooseMove这样某个特定的目标函数.17选择目标函数（2） ChooseMove的评价 学习问题很直观地转化成这个函数 这个函数的学习很困难，因为提供给系统的是间接训练经验 另一个目标函数V 一个评估函数，V: BR，它为任何给定棋局赋予一个数值评分，给好的棋局赋予较高的评分 优点: 表示统一, 学习简单 V的应用 根据V能够轻松地找到当前棋局的最佳走法。18选择目标函数（3） V的设计，对于集合B中的任意棋局b，V(b)定义如下

9、如果b是一最终的胜局，那么V(b)=100 如果b是一最终的负局，那么V(b)= -100 如果b是一最终的和局，那么V(b)=0 如果b不是最终棋局，那么V(b)=V(b)，其中b是从b开始双方都采取最优对弈后可达到的终局19选择目标函数（4） 上面设计的分析 递归定义 运算效率低 不可操作(b要决定它的值V（b）需要向前搜索到达终局的所有路线! ) 简评 学习任务简化成发现一个理想目标函数V的可操作描述。 通常要完美地学习这样一个V的可操作的形式是非常困难的。 一般地，我们仅希望学习算法得到近似的目标函数V，因此学习目标函数的过程常称为函数逼近。20选择目标函数的表示 函数的表示 一张大表

10、，对于每个唯一的棋盘状态，表中有唯一的表项来确定它的状态值 规则集合 二项式函数 人工神经网络21选择目标函数的表示（2） 重要的权衡过程 一方面，我们总希望选取一个非常有表现力的描述，以最大可能地逼近理想的目标函数 另一方面，越有表现力的描述需要越多的训练数据，使程序能从它表示的多种假设中选择22选择目标函数的表示（3） 本案例中我们选择一个简单的表示法，对于任何给定的棋盘状态，函数V可以通过以下棋盘参数的线性组合线性组合来计算。 x1，黑子的数量 x2，白子的数量 x3，黑王的数量 x4，白王的数量 x5，被白子威胁的黑子数量 x6，被黑子威胁的白子数量23选择目标函数的表示（4） 目标函

11、数 V(b)=w0+w1x1+w2x2+w6x6 其中，w0w6是权值，表示不同棋局特征的相对重要性 实际, b=(x1,x6), b给定,则x1,x6是常量 至此，问题转化为学习目标函数中的系数（即权值w0w6 ）24选择函数逼近算法 每个训练样例表示成二元对 b是棋盘状态，Vtrain(b)是训练值 比如，,100 训练过程 从学习器可得到的间接训练经验中导出上面的训练样例 调整系数wi，最佳拟合这些训练样例25选择函数逼近算法（3） 有了Vtrain, 怎么求出V? 因为V(b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6 所以,剩下的事情就是选择权权wi使V(b)

12、与训练样例的误差达到最小（拟合）： 调整权值 最佳拟合的定义，常用的最佳是误差平方和最小: 有算法可以得到线性函数的权使此定义的E最小化。2)(,)()(bVbVEtrainbVbtrain训练样例V是是V的近似拟合函的近似拟合函数数(因为因为Vtrain也是也是间接的近似的间接的近似的)26选择函数逼近算法（3） 训练样例集合：， ， ， ， 调整权值 V(b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6 这时，在训练样例集合上，x1,x6都是常数，w0w6是可调整的变量。27选择函数逼近算法（4） 最小均方方法（least mean squares），或叫LMS训练法

13、则： 对于每一训练样例，它把权值向减小这个训练数据误差的方向略为调整。 LMS 权值更新法则权值更新法则对于每一个训练样例 do： 使用当前的权wi计算V(b) 对每一个权值wi进行如下更新 wi wi +(Vtrain(b)-V(b) xi (其推导依据)几何意义28V-train初值V1V2V3V4V15V51V-b01001008596 101.2 103.5102.799.01V-b21001008089.594.3 96.76100.3 100.6V-b41001007581 84.35 86.3693.4299.99假设有直接反馈的情况下，运行梯度下降法的运行假设有直接反馈的情况下

14、，运行梯度下降法的运行结果，约循环结果，约循环51次收敛。次收敛。29选择函数逼近算法（5） 估计训练值 困难处(给对弈结束时的棋盘状态评分是容易的) 一个简单的方法，Vtrain(b)=V(Successor(b) 这个简单的方法是合理的看起来有点离奇，用V来估计训练值Vtrain，而Vtrain又被用来更新V。但请注意，我们是在用后续棋局Successor(b)的V来估计棋局b的值。凭直觉，我们可以看到越接近游戏结束的棋局的越趋向精确。 30估计训练值Vtrain(b)的例子 b4(终局): ，+100, 设此时V的系数为: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w

15、6=5. V(b4) = w0+w1*0+w2*0+w3*1+w4*0+w5*0+w6*0 = 75 b2(中间棋局): ，? , 此时V的系数为: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此时?的训练值Vtrain(b2) = V(successor(b2) = V(b4) = 75 V(b2) = w0+w1*0+w2*1+w3*1+w4*0+w5*0+w6*0 = 80 b0(中间棋局): ，? , 此时V的系数为: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此时?的训练值Vtrain(b0) = V(successor(b0

16、) = V(b2) = 80 V(b0) = w0+w1*1+w2*1+w3*1+w4*0+w5*0+w6*0 = 85b0 (我方一兵一后,对手一兵,我走一步兵)b1(吃我兵)b2 (我走后)b3 (他走兵)b4 (吃他一兵,胜)我方一后,对手一兵我方一后,对手无子31估计训练值Vtrain(b)与V(b)误差 b4(终局): ，+100, 设此时V的系数为: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.error(b4) = Vtrain(b4) - V(b4) = 100 wi*xi = 100-75=25 b2(中间棋局): ，75 , 设此时V的系数为:

17、w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此时?的训练值Vtrain(b2) = 75 error(b2) = Vtrain(b2) - V(b2) = 75 wi*xi = 75-80= -5 b0(中间棋局): ，80 , 设此时V的系数为: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此时?的训练值Vtrain(b0) = V(successor(b0) = V(b2)= w0+w1*0+w2*1+w3*1+w4*0+w5*0+w6*0 = 80 error(b0) = Vtrain(b0) - V(b0) = 80 wi*xi

18、= 80-85= -5b0(我方一兵一后,对手一兵)b1b2b3b4我方一后,对手一兵我方一后,对手无子32选择函数逼近算法（5） 一个调整权值的例子(棋局为b4): 假设当前wi=5（for i=0,1,2,4,5,6）,w3=70则依训练样本，+100，需调整wi如下： Error=100-(5+5*0+5*0+70*1+5*0+5*0+5*0) =25 W3=70+0.1*(25)*1=72.5 其他系数无变化, 即,w0=5, ,w1=5,w2=5,w3=72.5,w4=5,w5=5,w6=5. 于是新的Error=100-(5+5*0+5*0+72.5*1+5*0+5*0+5*0)=

19、22.5 多个样本训练后,这种简单的权值调整方法被证明可以收敛到Vtrain 值的最小误差平方点。计算程序见后页。 33V-train初值V1V2V3V4V15V36V-b0808585.585.279.59299.1V-b2758080.581.1581.991.399V-b41007576.57885.592.599.4w0w1w2w3w4w5w65557055515次循环后51.14-0.638755510010010034V-train初值V1V2V3V4V15V36V-b080.58585.585.279.59299.1V-b276.58080.581.1581.991.399V-b

20、41007576.57885.592.599.4w0w1w2w3w4w5w65557055515次循环后51.14-0.6387555计算程序10010010035设计一个学习系统 基本设计方法和学习途径（以西洋跳棋为例） 选择训练经验 选择目标函数 选择目标函数的表示 选择函数逼近算法 最终设计36设计一个学习系统 西洋跳棋学习问题4 任务T，下西洋跳棋 性能标准P，击败对手的百分比 训练经验E，和自己进行训练对弈：间接反馈，信用分配规则为，Vtrain(b)=V(Successor(b) 知识类型：函数（目标函数：V：B） 目标函数的表示，线形函数：V(b)=w0+w1x1+w2x2+w3

21、x3+w4x4+w5x5+w6x6 一种学习机制: LMS算法。有了以上核心思想，怎么变成一个软件系统？有了以上核心思想，怎么变成一个软件系统？37最终设计实验生成器执行系统泛化器鉴定器新问题解答路线假设训练样例38最终设计（2） 执行系统 用学会的目标函数来解决给定的任务 鉴定器 以对弈的路线或历史记录作为输入，输出目标函数的一系列训练样例。 泛化器 以训练样例为输入，产生一个输出假设，作为它对目标函数的估计。 实验生成器 以当前的假设作为输入，输出一个新的问题，供执行系统去探索。39Design ChoicesDesign Choices29Determine type of traini

22、ng experienceDetermine target functionDetermine representation of learned functionDetermine learning algorithmCompleted designGradient descentLinear programmingpolynomialLinear function of six featuresBoard moveBoard valueGames against expertsGames against selfTable of correct moves40西洋跳棋学习的更多讨论 理论上

23、的保证(如果目标函数真在假设空间中，这种学习技术是否确保发现一个非常接近的近似). 更复杂的目标函数（e.g. ANN） 其他学习算法 最近邻算法，存储训练样例，寻找保存的最接近的情形来匹配新的情况 遗传算法，产生大量候选的西洋跳棋程序，让它们相互比赛，保留最成功的程序并进一步用模拟进化的方式来培育或变异它们 基于解释的学习，分析每次成败的原因41对于有两个权值的线性单元，假设空间H就是w0,w1平面。纵轴表示与固定的训练样例集合相应的权向量假设的误差。箭头显示了该点梯度的相反方向，指出了在w0，w1平面中沿误差曲面最陡峭下降的方向。 BACK42机器学习的一些观点 一个有效的观点 机器学习问

24、题归结于搜索问题 本书给出了对一些基本表示（例如，线性函数、逻辑描述、决策树、人工神经元网络）定义的假设空间的搜索算法。这些不同的假设表示法适合于学习不同的目标函数。 通过搜索策略和搜索空间的内在结构来刻画学习方法43机器学习的问题存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛到期望的函数？哪个算法对哪些问题和表示的性能最好？多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系？学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知识仅仅是近似正确时，它们会有帮助吗？怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系统该试图学习哪些函数？这个过程本身能自动化吗？学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？44全书内容简介第2章，基于符号和逻辑表示的概念学习第3章，决策树第4章，人工神经网络第5章，统计和估计理论的基础概念第6章，贝叶斯理论第7章，计算学习第8章，基于实例的学习第9章，遗传算法第10章，规则学习（we will learn VSM）第11章，基于解释的学习第12章，近似知识与现有数据的结合第13章，增强学习45小结 机器学习算法在很多应用领域被证明有很大的实用价值