任何被h1划分为正例的实例都会被h2划分为正例， 因此h2比h1更一般
36
假设的一般到特殊序
关系“更一般”的精确定义
任给实例x和假设h，说x满足h，当且仅当h(x)=1 令hj和hk是在X上定义的布尔函数，称hj比hk更一般，
当且仅当(xX)[(hk(x)=1)(hj(x)=1)]
记为hj more_general_than_or_equal_to hk，或hj g hk
机器人驾驶学习问题
任务T：通过视觉传感器在四车道高速公路上驾驶 性能标准P：平均无差错行驶里程（差错由人类的监督裁定） 训练经验E：注视人类驾驶时录制的一系列图像和驾驶指令
12
设计一个学习系统
基本设计方法和步骤
Step1: 明确任务T、性能度量P Step2: 训练经验E Step3: 选择目标函数及其表示 Step4: 选择目标函数的学习算法 Step5: 最终设计
对于集合B中的任意棋局b，V(b)定义如下
如果b是一最终的胜局，那么V(b)=100 如果b是一最终的负局，那么V(b)=-100 如果b是一最终的和局，那么V(b)=0 如果b不是最终棋局，那么V(b)=V(b’)，其中b’是从b开始双方都采取最优对弈后可达到的
终局
问题
递归定义 运算效率低 不可操作
引言：学习智能体
机器学习基本概念
概念学习
概念学习的定义 一个例子 作为搜索问题的概念学习 FIND-S 候选消除算法
25
概念学习问题的定义
什么是概念
许多机器学习涉及到从特殊训练样例中得到一般概念 概念可被看作一个对象或事件集合，它是从更大的集合中选
取的子集，或在这个较大集合中定义的布尔函数
< , , , , , >
// 所有的样例都是反例
30
概念学习任务
形式化描述 已知 实例集X ▪ 每个实例x由6个属性描述，每个属性的取值范围已确定 假设集H ▪ 每个假设h描述为6个属性的取值约束的合取 （∩） 目标概念c ▪ 一个布尔函数，变量为实例，即： c:x->{1,0} 训练样例集D ▪ 目标函数（或目标概念）的正例和反例 求解 H中的一假设h，使对于X中任意x，h(x)=c(x)
另一方面，越有表现力的描述需要越多的训练数据，使程序 能从它表示的多种假设中选择
18
Step3 选择目标函数及其表示
一个简单的表示法
对于任何给定的棋盘状态，函数V可以通过以下棋盘参数的 线性组合来计算。 x1，黑子的数量 x2，红子的数量 x3，黑王的数量 x4，红王的数量 x5，被红子威胁的黑子数量 x6，被黑子威胁的红子数量
8
大纲
引言：学习智能体 机器学习基本概念 概念学习
9
机器学习的成功案例
学习识别人类的讲话
语音识别
学习驾驶车辆
ALVINN
学习分类新的天文结构
学习以世界级的水平对弈西洋双陆棋
TD-Gammon
通过百万次的与自己对弈来学习策略
10
什么是机器学习
什么是机器学习
计算机程序通过经验来提高某种任务处理性能的过 程
把智能体放置在真实环境中而不是写出所有的规则
学习可以修正智能体的决策机制以提高性能
3
待学习的组件
智能体的组件包括
条件-行动规则 世界的演变知识 效用信息 目标 …..
例：训练出租车司机
教官喊刹车 尝试在不同的路面上刹车
6
反馈类型
监督式学习(Supervised learning)
通常要完美地学习V的可操作的形式非常困难
一般地，我们仅希望学习算法得到近似的目标函数V’，因此学习目标函数的过程常称为 函数逼近
17
Step3 选择目标函数及其表示
函数的不同表示方法 状态表 二次多项式函数 神经网络
注意
一方面，我们总希望选区一个非常有表现力的描述，以最大 可能地逼近理想的目标函数
表示假设的形式（目标函数的表示）
实例的各属性约束的合取式
令每个假设为6个约束（或变量）的向量，每个约束对应一 个属性可取值范围
？任意本属性可接受的值
明确指定的属性值
不接受任何值
假设的例子
<?, Cold, High, ?, ?, ?, ?>
// 所有的样例都是正例
3. 输出假设h
39
Find-S：寻找极大特殊假设
Find-S算法在例子EnjoySport上的应用
h<, , , , , > h<Sunny, Warm, Normal, Strong, Warm,
Find-S：寻找极大特殊假设
使用more_general_than偏序的搜索算法
从H中最特殊假设开始，然后在假设覆盖正例失败时将其 一般化
Find-S算法 1. 将h初始化为H中最特殊假设 2. 对每个正例x
– 对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的另一个更一般约束
归纳假设的一个基本假定
对于未见实例最好的假设就是与训练数据最佳拟合的假设
归纳学习假设
任一假设如果在足够大的训练样例集中很好地逼近目标函数， 它也能在未见实例中很好地逼近目标函数。
33
大纲
引言：学习智能体
机器学习基本概念
概念学习
概念学习的定义 一个例子 作为搜索问题的概念学习 FIND-S 候选消除算法
《人工智能》第5章
学习智能体-概念学习
巢文涵
chaowenhan@ G1001/G931 北航计算机学院智能信息研究所 2020年10月25日星期日
大纲
引言：学习智能体 机器学习基本概念 概念学习
2
学习
学习对于未知环境是必要的
设计者缺乏全知
学习作为系统的一种构造方法是有用的
学习的定义
对于某类任务T和性能度量P，如果一个计算机程 序在T上以P衡量的性能随着经验E而自我完善，那 么我们称这个计算机程序在从经验E中学习
11
学习问题的标准描述
西洋跳棋学习问题
任务T：下西洋跳棋 性能标准P：比赛中击败对手的百分比 训练经验E：和自己进行对弈
手写识别学习问题
任务T：识别和分类图像中的手写文字 性能标准P：分类的正确率 训练经验E：已知分类的手写文字数据库
子 学习器可以完全控制棋局和（间接的）训练分类，就像没有施教者时
它和自己对弈进行学习一样
训练样例的分布能多好地表示实例分布
最终系统的性能P是通过后者来衡量的
15
Step3 选择目标函数及其表示
目标函数ChooseMove
ChooseMove: BM
接受合法棋局集合中的棋盘状态作为输入，并从合法走 子集合中选择某个走子作为输出
训练过程
从学习器可得到的间接训练经验中导出上面的训练样例 调整系数wi，最佳拟合这些训练样例
20
Step4 : 选择目标函数逼近算法
调整权值
误差平方和最小
E
(V tra (b i)n V ˆ(b )2)
b,V tra (b)i n训 练样例
算法：最小均方法，LMS Least Mean Squares
目标函数
V(b)=w0+w1x1+w2x2+…+w6x6 其中，w0…w6是权值，表示不同棋局特征的相对重要性 至此，问题转化为学习目标函数中的系数（即权值）
19
Step4 : 选择目标函数逼近算法
每个训练样例表示成二元对
<b，Vtrain(b)> b是棋盘状态，Vtrain(b)是训练值 比如，<<x1=0,x2=0,x3=1,x4=0,x5=0,x6=0>,100>
Aldo进行水上运动的日子，表示为布尔函数EnjoySport
给定一个样例集D
每个样例表示为属性的集合
任务目的
基于某天的各属性，预测EnjoySport的值
28
概念学习任务
Example 1 2 3 4
Sky Sunny Sunny Rainy Sunny
AirTemp Warm Warm Cold Warm
34
作为搜索的概念学习
概念学习可以看作一个搜索的过程
搜索范围：假设的表示所隐含定义的整个空间 搜索目标：能够最好地拟合训练样例的假设
当假设的表示形式选定后，那么就隐含地为学习算法 确定了所有假设的空间
例子EnjoySport的假设空间，如果属性Sky有3种可能的值， 而AirTemp、Humidity、Wind、Water和 Forecast都只有两 种可能值 实例空间X：包含3×2×2×2×2×2=96种不同的实例 假设空间H
问题产生器
以当前的假设作为输入，输出一个新的问题，供执行系统去 探索。
23
小结：设计一个学习系统
基本设计方法和步骤
Step1: 明确任务T、性能度量P Step2: 训练经验E Step3: 选择目标函数及其表示 Step4: 选择目标函数的学习算法 Step5: 最终设计
24
大纲
▪ 包含5×4×4×4×4×4=5120种语法不同的假设 ▪ 由于：包含有符号的假设将每个实例都分类为反例。因此，语义
不同的假设只有1+4×3×3×3×3×3=973个。
35
假设的一般到特殊序
假设的一般到特殊序关系
考虑下面两个假设
h1=<sunny, ?, ?, Strong, ?, ?> h2=<Sunny, ?, ?, ?, ?, ?>
概念学习问题的定义
给定一个样例集合及每个样例是否属于某个概念的标注，怎 样推断出该概念的一般定义，又称从样例中逼近布尔函数
26
大纲