2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 1章 引言
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
什么是机器学习什么是机器学习计算机程序如何随着经验积累自动提高性能系统自我改进的过程历史成功应用学习识别人类讲话学习驾驶车辆学习分类新的天文结构学习对弈西洋双陆棋
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
相关学科
人工智能
计算复杂性理论
控制论
信息论
统计学
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
学习问题的标准描述
定义
– 如果一个计算机针对某类任务 T的用 P衡量的性能根据经验 E来自我完善，那么我们称这个计算机程序在从经验 E中学习，针对某类任务 T，它的性能用 P
来衡量。
西洋跳棋学习问题的解释
– E，和自己下棋
– T，参与比赛
– P，比赛成绩（或赢棋能力，击败对手的百分比）
手写识别学习问题
机器人驾驶学习问题
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
学习问题的标准描述（ 2）
定义太宽泛
– 甚至包括了以非常直接的方式通过经验自我提高的计算机程序
实际的机器学习问题往往比较复杂
– 定义一类问题
– 探索解决这类问题的方法
– 理解学习问题的基本结构和过程
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
设计一个学习系统
基本设计方法和学习途径
（以西洋跳棋为例）
– 选择训练经验
– 选择目标函数
– 选择目标函数的表示
– 选择函数逼近算法
– 最终设计
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
设计一个学习系统
西洋跳棋学习问题
– 任务 T，下西洋跳棋
– 性能标准 P，击败对手的百分比
– 训练经验 E，和自己进行训练对弈
学习系统需要选择
– 要学习的知识的确切类型
– 对于这个目标知识的表示
– 一种学习机制
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
选择训练经验
第一个关键属性，训练经验能否为系统的决策提供直接或间接的反馈
第二个重要属性，学习器在多大程度上控制样例序列
第三个重要属性，训练样例的分布能多好地表示实例分布，通过样例来衡量最终系统的性能
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
选择目标函数
目标函数 ChooseMove
– ChooseMove,B?M，接受合法棋局集合中的棋盘状态作为输入，并从合法走子集合中选择某个走子作为输出
问题转化
– 我们把提高任务 T的性能 P的问题转化（或简化）为学习像 ChooseMove这样某个特定的目标函数
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
选择目标函数（ 2）
ChooseMove的评价
– 学习问题很直观地转化成这个函数
– 这个函数的学习很困难，因为提供给系统的是间接训练经验
另一个目标函数 V
– 一个评估函数,V,B?R,它为任何给定棋局赋予一个数值评分,给好的棋局赋予较高的评分
– 优点，学习简单
V的应用
– 根据 V能够轻松地找到当前棋局的最佳走法。
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
选择目标函数（ 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开始双方都采取最优对弈后可达到的终局
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
选择目标函数（ 4）
上面设计的缺陷
– 递归定义
– 运算效率低
– 不可操作
简评
– 学习任务简化成发现一个理想目标函数 V的可操作描述。
– 通常要完美地学习这样一个 V的可操作的形式是非常困难的。
– 一般地，我们仅希望学习算法得到近似的目标函数
V’，因此学习目标函数的过程常称为函数逼近。
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
选择目标函数的表示
函数的表示
– 一张大表，对于每个唯一的棋盘状态，表中有唯一的表项来确定它的状态值
– 规则集合
– 二项式函数
– 人工神经网络
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
选择目标函数的表示（ 2）
重要的权衡过程
– 一方面，我们总希望选区一个非常有表现力的描述，以最大可能地逼近理想的目标函数
– 另一方面，越有表现力的描述需要越多的训练数据，使程序能从它表示的多种假设中选择
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
选择目标函数的表示（ 3）
一个简单的表示法，对于任何给定的棋盘状态，
函数 V可以通过以下棋盘参数的线性组合来计算。
– x1，黑子的数量
– x2，红子的数量
– x3，黑王的数量
– x4，红王的数量
– x5，被红子威胁的黑子数量
– x6，被黑子威胁的红子数量
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
选择目标函数的表示（ 4）
目标函数
– V(b)=w0+w1x1+w2x2+…+w6x6
– 其中,w0…w6 是权值，表示不同棋局特征的相对重要性
至此，问题转化为学习目标函数中的系数（即权值）
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
选择函数逼近算法
每个训练样例表示成二元对
– <b,Vtrain(b)>
– b是棋盘状态,Vtrain(b)是训练值
– 比如,<<x1=0,x2=0,x3=1,x4=0,x5=0,x6=0>,100>
训练过程
– 从学习器可得到的间接训练经验中导出上面的训练样例
– 调整系数 wi，最佳拟合这些训练样例
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
选择函数逼近算法（ 2）
估计训练值
– 困难处
– 一个简单的方法,Vtrain(b)=V’(Successor(b))
调整权值
– 最佳拟合的定义，比如误差平方和最小
– 寻找算法，比如最小均方法,LMS Least
Mean Squares
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
最终设计实验生成器执行系统 泛化器鉴定器新问题解答路线假设训练样例
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
最终设计（ 2）
执行系统
– 用学会的目标函数来解决给定的任务
鉴定器
– 以对弈的路线或历史记录作为输入，输出目标函数的一系列训练样例。
泛化器
– 以训练样例为输入，产生一个输出假设，作为它对目标函数的估计。
实验生成器
– 以当前的假设作为输入，输出一个新的问题，供执行系统去探索。
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
西洋跳棋学习的更多讨论
图 1-2
第 13章理论上的保证
– 这种学习技术是否确保发现一个非常接近的近似。
更复杂的目标函数
其他学习算法
– 最近邻算法，存储训练样例，寻找保存的最接近的情形来匹配新的情况
– 遗传算法，产生大量候选的西洋跳棋程序，让它们相互比赛，保留最成功的程序并进一步用模拟进化的方式来培育或变异它们
– 基于解释的学习，分析每次成败的原因
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
机器学习的一个观点
一个有效的观点
– 机器学习问题归结于搜索问题
本书给出了对一些基本表示定义的假设空间的搜索算法
通过搜索策略和搜索空间的内在结构来刻画学习方法
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
机器学习的问题
存在什么样的算法能从特定的训练数据学习一般的目标函数呢？
如果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛到期望的函数？哪个算法对哪些问题和表示的性能最好？
多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系？
学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知识仅仅是近似正确时，它们会有帮助吗？
关于选择有效的后验训练经验，什么样的策略最好？这个策略的选择会如何影响学习问题的复杂性。
怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，
系统该试图学习哪些函数？这个过程本身能自动化吗？
学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
全书内容简介
第 2章，基于符号和逻辑表示的概念学习
第 3章，决策树
第 4章，人工神经网络
第 5章，统计和估计理论的基础概念
第 6章，贝叶斯理论
第 7章，计算学习
第 8章，基于实例的学习
第 9章，遗传算法
第 10章，规则学习
第 11章，基于解释的学习
第 12章，近似知识与现有数据的结合
第 13章，增强学习
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
小结和补充读物
定义
涉及学科
完整过程
搜索的观点
相关杂志、会议、国际组织
机器学习第 1章 引言
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
什么是机器学习什么是机器学习计算机程序如何随着经验积累自动提高性能系统自我改进的过程历史成功应用学习识别人类讲话学习驾驶车辆学习分类新的天文结构学习对弈西洋双陆棋
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
相关学科
人工智能
计算复杂性理论
控制论
信息论
统计学
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
学习问题的标准描述
定义
– 如果一个计算机针对某类任务 T的用 P衡量的性能根据经验 E来自我完善，那么我们称这个计算机程序在从经验 E中学习，针对某类任务 T，它的性能用 P
来衡量。
西洋跳棋学习问题的解释
– E，和自己下棋
– T，参与比赛
– P，比赛成绩（或赢棋能力，击败对手的百分比）
手写识别学习问题
机器人驾驶学习问题
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
学习问题的标准描述（ 2）
定义太宽泛
– 甚至包括了以非常直接的方式通过经验自我提高的计算机程序
实际的机器学习问题往往比较复杂
– 定义一类问题
– 探索解决这类问题的方法
– 理解学习问题的基本结构和过程
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
设计一个学习系统
基本设计方法和学习途径
（以西洋跳棋为例）
– 选择训练经验
– 选择目标函数
– 选择目标函数的表示
– 选择函数逼近算法
– 最终设计
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
设计一个学习系统
西洋跳棋学习问题
– 任务 T，下西洋跳棋
– 性能标准 P，击败对手的百分比
– 训练经验 E，和自己进行训练对弈
学习系统需要选择
– 要学习的知识的确切类型
– 对于这个目标知识的表示
– 一种学习机制
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
选择训练经验
第一个关键属性，训练经验能否为系统的决策提供直接或间接的反馈
第二个重要属性，学习器在多大程度上控制样例序列
第三个重要属性，训练样例的分布能多好地表示实例分布，通过样例来衡量最终系统的性能
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
选择目标函数
目标函数 ChooseMove
– ChooseMove,B?M，接受合法棋局集合中的棋盘状态作为输入，并从合法走子集合中选择某个走子作为输出
问题转化
– 我们把提高任务 T的性能 P的问题转化（或简化）为学习像 ChooseMove这样某个特定的目标函数
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
选择目标函数（ 2）
ChooseMove的评价
– 学习问题很直观地转化成这个函数
– 这个函数的学习很困难，因为提供给系统的是间接训练经验
另一个目标函数 V
– 一个评估函数,V,B?R,它为任何给定棋局赋予一个数值评分,给好的棋局赋予较高的评分
– 优点，学习简单
V的应用
– 根据 V能够轻松地找到当前棋局的最佳走法。
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
选择目标函数（ 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开始双方都采取最优对弈后可达到的终局
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
选择目标函数（ 4）
上面设计的缺陷
– 递归定义
– 运算效率低
– 不可操作
简评
– 学习任务简化成发现一个理想目标函数 V的可操作描述。
– 通常要完美地学习这样一个 V的可操作的形式是非常困难的。
– 一般地，我们仅希望学习算法得到近似的目标函数
V’，因此学习目标函数的过程常称为函数逼近。
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
选择目标函数的表示
函数的表示
– 一张大表，对于每个唯一的棋盘状态，表中有唯一的表项来确定它的状态值
– 规则集合
– 二项式函数
– 人工神经网络
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
选择目标函数的表示（ 2）
重要的权衡过程
– 一方面，我们总希望选区一个非常有表现力的描述，以最大可能地逼近理想的目标函数
– 另一方面，越有表现力的描述需要越多的训练数据，使程序能从它表示的多种假设中选择
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
选择目标函数的表示（ 3）
一个简单的表示法，对于任何给定的棋盘状态，
函数 V可以通过以下棋盘参数的线性组合来计算。
– x1，黑子的数量
– x2，红子的数量
– x3，黑王的数量
– x4，红王的数量
– x5，被红子威胁的黑子数量
– x6，被黑子威胁的红子数量
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
选择目标函数的表示（ 4）
目标函数
– V(b)=w0+w1x1+w2x2+…+w6x6
– 其中,w0…w6 是权值，表示不同棋局特征的相对重要性
至此，问题转化为学习目标函数中的系数（即权值）
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
选择函数逼近算法
每个训练样例表示成二元对
– <b,Vtrain(b)>
– b是棋盘状态,Vtrain(b)是训练值
– 比如,<<x1=0,x2=0,x3=1,x4=0,x5=0,x6=0>,100>
训练过程
– 从学习器可得到的间接训练经验中导出上面的训练样例
– 调整系数 wi，最佳拟合这些训练样例
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
选择函数逼近算法（ 2）
估计训练值
– 困难处
– 一个简单的方法,Vtrain(b)=V’(Successor(b))
调整权值
– 最佳拟合的定义，比如误差平方和最小
– 寻找算法，比如最小均方法,LMS Least
Mean Squares
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
最终设计实验生成器执行系统 泛化器鉴定器新问题解答路线假设训练样例
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
最终设计（ 2）
执行系统
– 用学会的目标函数来解决给定的任务
鉴定器
– 以对弈的路线或历史记录作为输入，输出目标函数的一系列训练样例。
泛化器
– 以训练样例为输入，产生一个输出假设，作为它对目标函数的估计。
实验生成器
– 以当前的假设作为输入，输出一个新的问题，供执行系统去探索。
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
西洋跳棋学习的更多讨论
图 1-2
第 13章理论上的保证
– 这种学习技术是否确保发现一个非常接近的近似。
更复杂的目标函数
其他学习算法
– 最近邻算法，存储训练样例，寻找保存的最接近的情形来匹配新的情况
– 遗传算法，产生大量候选的西洋跳棋程序，让它们相互比赛，保留最成功的程序并进一步用模拟进化的方式来培育或变异它们
– 基于解释的学习，分析每次成败的原因
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
机器学习的一个观点
一个有效的观点
– 机器学习问题归结于搜索问题
本书给出了对一些基本表示定义的假设空间的搜索算法
通过搜索策略和搜索空间的内在结构来刻画学习方法
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
机器学习的问题
存在什么样的算法能从特定的训练数据学习一般的目标函数呢？
如果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛到期望的函数？哪个算法对哪些问题和表示的性能最好？
多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系？
学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知识仅仅是近似正确时，它们会有帮助吗？
关于选择有效的后验训练经验，什么样的策略最好？这个策略的选择会如何影响学习问题的复杂性。
怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，
系统该试图学习哪些函数？这个过程本身能自动化吗？
学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
全书内容简介
第 2章，基于符号和逻辑表示的概念学习
第 3章，决策树
第 4章，人工神经网络
第 5章，统计和估计理论的基础概念
第 6章，贝叶斯理论
第 7章，计算学习
第 8章，基于实例的学习
第 9章，遗传算法
第 10章，规则学习
第 11章，基于解释的学习
第 12章，近似知识与现有数据的结合
第 13章，增强学习
2003.12.18 机器学习 -引言 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
小结和补充读物
定义
涉及学科
完整过程
搜索的观点
相关杂志、会议、国际组织
