33
29
2.5.4 候选消除学习法
• 候选消除：候选消除算法通过使用极大一 般成员（G）和极大特殊成员（S）来表示 变型空间。
30
表2-5 使用变型空间的候选消除算法（正例和反例同时影响S和G）
将G集合初始化为H中极大一般假设 例 表2-1 将S集合初始化为H中极大特殊假设 对每个训练样例d，进行以下操作： 如果d是一正例 从G中移去所有与d不一致的假设 对S中每个与d不一致的假设s 从S中移去s 把s的所有的极小泛化式h加入到S中，其中h满足 h与d一致，而且G的某个成员比h更一般 从S中移去所有这样的假设：它比S中另一假设更一般 如果d是一个反例 从S中移去所有与d不一致的假设 对G中每个与d不一致的假设g 从G中移去g 把g的所有的极小特化式h加入到G中，其中h满足 h与d一致，而且S的某个成员比h更特殊 从G中移去所有这样的假设：它比G中另一假设更特殊
24
Step3.第2个训练样例（仍为正例）使该算 法进一步将h泛化: h←<Sunny, Warm, ?, Strong, Warm, Same> Step4.第3个训练样例是一个反例，h不变 …… 依次对比样例，直到最后h泛化为： h←<Sunny, Warm, ?, Strong, ?, ?>
25
困惑
• 学习过程是否收敛到了正确的目标概念？-无法确定收敛到了目标概念 • 为什么要用极大特殊假设？--若有多个与训 练样例一致的假设，Find-S只能找到极大 特殊假设。 • 训练样例是否相互一致？ --数据含噪 • 若有多个极大特殊假设呢？--选择
26
2.5变型空间和候选消除算法
h2=<Sunny, ?, ?, ?, ?, ?>
22
2.4 FIND-S: 寻找极大特殊假设
表2-3 Find-S算法 1.将h初始化为H中最特殊假设; 2.对每个正例x; 对h的每个属性约束ai 如果 x满足ai ,那么不做任何事 否则将h中ai替换为x满足的紧邻的更一般 约束 3.输出假设h.
3
第一讲 机器学习的基本概念 第1章 引言
什么是机器学习？ 为什么进行机器学习？ 如何利用机器学习解决问题？
4
什么是机器学习？
直观地理解： 机器（计算机）的自我学习。 例： 计算机能从医疗记录中学习，获取治疗新疾 病的最有效方法； 住宅管理系统分析住户的用电模式，以降低 能源消耗。
5
为什么进行机器学习？
机器学习及进化计算
授课：徐琴珍 学时：36
1
主要教材及参考书目
教材：《机器学习》, Tom M. Mitchell著，曾 华军，张银奎 等译，机械工业出版社。 参考书目： • 贝叶斯方法，Tomas Leonaard, 机械工业出 版社。 • 进化计算， 王正志，薄涛，国防科技大学出版社。 • 神经网络设计，Martin T. Hangan等，机械工 业出版社。
一些术语及其表示(1)： • 一致：一个假设h与训练样例集合D一致 (consistent)，当且仅当对D中每一个样 例<x,c(x)>，h(x)=c(x)。
Consistent(h,D)≡(<x,c(x)> ∈ D) h(x)=c(x)
27
一些术语及其表示(2)： • 变型空间: 关于假设空间H和训练样例集D 的变型空间(version space)，标记为
VSH,D，是H中与训练样例D一致的所有假
设构成的子集。
VSH,D≡{h∈H | Consistent (h,D) }
28
2.5.2列表后消除算法
• List-Then-Eliminate: 列出变型空间的 其所有成员. • 特点: 繁琐。
表2-4 列表后消除算法
1.变型空间VersionSpace←包含H中所有假设的列表 2.对每个训练样例<x, c(x)> 从变型空间中移除所有h(x)≠c(x)的假设h 3.输出VersionSpace中的假设列表
31
深圳公司注册
编辑：vbgfhyrtgrdb99658
32
2.7归纳偏置
• 无偏学习器的无用性： 学习器如果不对目标概念的形式做预先的 假定，它从根本上无法对未见实例进行分 类。 因此，归纳学习需要某种形式的预先假定， 或称为归纳偏置（Inductive bias）
13
如何设计学习系统？(2)
② 选择目标函数 学习任务目标函数目标函数的逼近 V: Feature statictarget output ③ 选择目标函数的表示 与学习机制有关：加权方式，推理方式等
14
如何设计学习系统？(3)
④ 选择函数逼近算法(学习机制) I. 估计训练值 II. 调整权值(或调整规则等)
包括人工智能、概率统计、信息论、神经 生物学等学科的发展为机器学习提供了丰 富的素材； 不断增长的在线（实时）数据量；
可以有效地利用计算机的计算性能；
产业发展的推动；
机器学习适用的三大领域:
6
机器学习适用的三大领域
• 数据挖掘：用历史数据提高决策能力。 例：医疗数据诊断知识(data knowledge)
Sunny Warm
术语定义
Find-S例
19
2.2.2 归纳学习假设
归纳学习假设: 任一假设如果在足够大的训练样例集中很好 地逼近目标函数，它也能在未见实例中很 好地逼近目标函数。
20
2.3作为搜索的概念学习
• 概念学习的过程即搜索的过程 • 搜索范围：假设表示(H)所隐含定义的整个 空间。 • 搜索目标:寻找能最好地拟合训练样例的假 设h。 • 学习算法不同，假设空间搜索的策略也不 同。
18
表2-1目标概念EnjoySport的正例和反例
Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 2 3 4 Sunny Warm Normal Strong Warm Same Sunny Warm Rainy Cold High High High Strong Warm Same Strong Warm Change Strong Cool Change Yes Yes No Yes
21
More general than or equal to
定义：令hj 和hk 为在X上定义的布尔函数。 定义一个more-general-than-or-
equal-to关系，记做≥g。称hj≥g hk当且
仅当(x∈X) [( hk (x) =1)→( hj (x) =1)] 例：h1=<Sunny, ?, ?, Strong, ?, ?>
• 人们无法手工操作实现，而应用软件却可 以。 例: 自动驾驶；语音识别 • 个性定制程序。 例：掌握用户兴趣的新闻广播员
7
典型的数据挖掘实例
数据：
• 给定9714个病历记录，每条记录描述了怀
孕及生产的信息 • 每条病历记录包含215个特征
8
数据特征
Patient103 time=1 Age: 23 FirstPregnancy: no Anemia: no PreviousPrematureBirth: no Diabetes: no Ultrasound: ? Elective C−Section: ? Emergency C−Section: ? ... Patient103 time=2 Age: 23 FirstPregnancy: no Anemia: no PreviousPrematureBirth: no Diabetes: YES Ultrasound: abnormal Emergency C−Section: ? Elective C−Section: no ... ... Patient103 time=n Age: 23 FirstPregnancy: no Anemia: no PreviousPrematureBirth: no Diabetes: no Elective C−Section: no Ultrasound: ? Emergency C−Section: Yes ...
11
如何设计学习系统？(1)
① 选择训练经验 a) 训练经验能否为系统的决策提供直接或间 接的反馈 ？(特征抽取、选择？) b) 学习器可以在多大程度上控制训练样例序 列 ?(能否在线学习？) c) 训练样例的分布能多好地表示实例分布?
12
例：手写字体的识别学习问题
• 要学习的知识的确切类型 • 对于这个目标知识的表示 • 一种学习机制
要求预测： • 未来病历中需要紧急剖腹产的病人
9
如何利用机器学习解决问题
• 学习问题的标准描述（Section 1.1） • 设计学习系统（Section 1.2)
10
什么是学习问题？
定义： • 对于某类任务T 和性能度量P ，如果一个 计算机程序在T 上以P 衡量的性能随着经 验E 而自我完善，那么我们称这个计算机 程序在从经验E 学习。（例：水果分类, 手 写字体的识别，机器人驾驶） 广义理解： • 任何计算机程序通过经验来提高某任务处 理性能的行为 。
23
• 例：学习器的一系列训练样例如表2-1所示， 则FIND-S的学习过程为： Step1.将h初始化为H中最特殊假设： h←<, , , , , > Step2.与表2-1中第一个训练样例对比，每 个属性都被替换成能拟合该例的值约束。 h←<Sunny, Warm, Normal, Strong, Warm, Same>
15
学习过程的设计流程
决定训练经验类型 决定目标函数
决定目标函数的表示 选择学习方法 完成设计
16
第2章 概念学习和一般到特殊序
• 机器学习的中心问题： 从特殊的训练样例中归纳出一般函数（一 般概念）。 • 在两分类问题中，概念学习的定义为： 从有关某个布尔函数的输入输出训练样例中， 推断出该布尔函数 。