机器学习：引言.ppt

2003.12.18 机器学习-引言 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 相关学科 人工智能 计算复杂性理论 控制论 信息论 统计学 学习问题的标准描述 定义 如果一个计算机针对某类任务T的用P衡量的性能根据经验E来自我完善，那么我们称这个计算机程序在从经验E中学习，针对某类任务T，它的性能用P来衡量。 西洋跳棋学习问题的解释 E，和自己下棋 T，参与比赛 P，比赛成绩（或赢棋能力，击败对手的百分比） 手写识别学习问题 机器人驾驶学习问题 学习问题的标准描述（2） 定义太宽泛 甚至包括了以非常直接的方式通过经验自我提高的计算机程序 实际的机器学习问题往往比较复杂 定义一类问题 探索解决这类问题的方法 理解学习问题的基本结构和过程 设计一个学习系统 基本设计方法和学习途径 （以西洋跳棋为例） 选择训练经验 选择目标函数 选择目标函数的表示 选择函数逼近算法 最终设计 设计一个学习系统 西洋跳棋学习问题 任务T，下西洋跳棋 性能标准P，击败对手的百分比 训练经验E，和自己进行训练对弈 学习系统需要选择 要学习的知识的确切类型 对于这个目标知识的表示 一种学习机制 选择训练经验 第一个关键属性，训练经验能否为系统的决策提供直接或间接的反馈 第二个重要属性，学习器在多大程度上控制样例序列 第三个重要属性，训练样例的分布能多好地表示实例分布，通过样例来衡量最终系统的性能 选择目标函数 目标函数ChooseMove ChooseMove: B?M，接受合法棋局集合中的棋盘状态作为输入，并从合法走子集合中选择某个走子作为输出 问题转化 我们把提高任务T的性能P的问题转化（或简化）为学习像ChooseMove这样某个特定的目标函数 选择目标函数（2） ChooseMove的评价 学习问题很直观地转化成这个函数 这个函数的学习很困难，因为提供给系统的是间接训练经验 另一个目标函数V 一个评估函数，V: B?R，它为任何给定棋局赋予一个数值评分，给好的棋局赋予较高的评分 优点，学习简单 V的应用 根据V能够轻松地找到当前棋局的最佳走法。 选择目标函数（3） V的设计，对于集合B中的任意棋局b，V(b)定义如下 如果b是一最终的胜局，那么V(b)=100 如果b是一最终的负局，那么V(b)=-100 如果b是一最终的和局，那么V(b)=0 如果b不是最终棋局，那么V(b)=V(b’)，其中b’是从b开始双方都采取最优对弈后可达到的终局 选择目标函数（4） 上面设计的缺陷 递归定义 运算效率低 不可操作 简评 学习任务简化成发现一个理想目标函数V的可操作描述。 通常要完美地学习这样一个V的可操作的形式是非常困难的。 一般地，我们仅希望学习算法得到近似的目标函数V’，因此学习目标函数的过程常称为函数逼近。 选择目标函数的表示 函数的表示 一张大表，对于每个唯一的棋盘状态，表中有唯一的表项来确定它的状态值 规则集合 二项式函数 人工神经网络 选择目标函数的表示（2） 重要的权衡过程 一方面，我们总希望选区一个非常有表现力的描述，以最大可能地逼近理想的目标函数 另一方面，越有表现力的描述需要越多的训练数据，使程序能从它表示的多种假设中选择 选择目标函数的表示（3） 一个简单的表示法，对于任何给定的棋盘状态，函数V可以通过以下棋盘参数的线性组合来计算。 x1，黑子的数量 x2，红子的数量 x3，黑王的数量 x4，红王的数量 x5，被红子威胁的黑子数量 x6，被黑子威胁的红子数量 选择目标函数的表示（4） 目标函数 V(b)=w0+w1x1+w2x2+…+w6x6 其中，w0…w6是权值，表示不同棋局特征的相对重要性 至此，问题转化为学习目标函数中的系数（即权值） 选择函数逼近算法 每个训练样例表示成二元对 b，Vtrain(b) b是棋盘状态，Vtrain(b)是训练值 比如，x1=0,x2=0,x3=1,x4=0,x5=0,x6=0,100 训练过程 从学习器可得到的间接训练经验中导出上面的训练样例 调整系数wi，最佳拟合这些训练样例 选择函数逼近算法（2） 估计训练值 困难处 一个简单的方法，Vtrain(b)=V’(Successor(b)) 调整权值 最佳拟合的定义，比如误差平方和最小 寻找算法，比如最小均方法，LMS Least Mean Squares 最终设计 最终设计（2） 执行系统 用学会的目标函数来解决给定的任务 鉴定器 以对弈的路线或历史记录作为输入，输出目标函数的一系列训练样例。 泛化器 以训练样例为输入，产生一个输出假设，作为它对目标函数的估计。 实验生成器 以当前的假设作为输入，输出一个新的问题，供执行系统去探索。 西洋跳棋学习的更多讨论 图1-2 第13章理论上的保证 这种学习技术是否确保发现一个非常接近的近