Lecture 2_Concept Learning 机器学习概论 教学课件.pptVIP

Lecture 2:- Concept Learning 邓志鸿 北京大学信息科学技术学院 回顾 课程简介 机器学习简介 课程内容介绍 简介 学习策略 归纳 (Induction) 从特定训练样本中获取一般的概念 例如人们获取“苹果”、“汽车”等概念 概念定义 定义在对象集合上的布尔函数 Bf: x ? {-1, 1}, x ? {动物} 基础知识 An Example 假定Table 1记录小王同学根据天气情况决定是否游泳的相关数据。 推断出“在什么样的天气条件下小王同学会去游泳” 基础知识 假定 概念（知识）是由属性及其上约束的合取（交）表示。 以Table 1为例，概念可由五元组表示，其中每个元组的值分别对应Sky、AirTemp、Humidity、Wind和Water五个属性的约束（即在取值上面的限制） 对每个属性，约束限制可为： ？：表示可取任何值； 该属性值域中的某个特定值； ? ：任何值都不能取。 概念h=Sunny, ?, ?, Strong, ? 如果一个实例x满足h对属性取值的约束，则h判定x是一个正样本，即h(x)＝1（Yes）；否则则h判定x是一个负样本，即h(x)＝－1（No）。 考虑Table 1中的例子，对比概念h对实例的判断结果与实际结果（Swim的取值）？ H：所有概念的集合 基础知识 概念学习 Task：从概念空间中找到一个概念，这个概念对任何实例决策属性的判断与实例决策属性的真实取值一致。 形式化（以Table 1为例） 给定 实例空间（集合）X：可能的天数，每天由Sky、AirTemp、Humidity、Wind和Water等五个属性描述。 Sky：Sunny, Cloudy, Rainy； AirTemp：Warm, Cold; Humidity ：Normal, High; Wind ：Strong, Weak; Water ：Warm, Cool. 概念空间H：所有由上述五个属性上约束的合取表示的概念 目标概念c： Swimming:X－{-1,1} // 客观存在，但我们不知道 训练样本集合D: 目标函数的正样本和负样本 寻找 H中的一个概念h满足： h(x)= c(x) for all x in X 基础知识 归纳学习公理 在足够大的训练样本上与目标函数（概念）很好拟和的概念，在未观察到的数据上也与目标函数拟和的很好。 Why 学习的任务是对所有实例而言， h(x)和c(x)的取值要一样，但是关于c的信息只是在训练样本中出现。因此，对c的描述是不完全的。 归纳学习最多只能保证获取的概念在训练集合上与目标概念一致。 如何学习概念 学习概念的过程实质是一个有哪些信誉好的足球投注网站的过程 在概念空间中找一个与目标概念在训练样本上保持一致的概念。 Easy or not 穷举法 遍历概念空间，对每个概念，看其是否在训练样本上与目标概念保持一致。如找到一个一致的概念则停止有哪些信誉好的足球投注网站。 概念空间大小？ 概念空间中概念的个数，即概念空间的基数。 概念空间基数 以Table 1为例 实例空间： 3x2x2x2x2：共48个不同实例 概念空间 5x4x4x4x4：共1280个“不同概念” 显然包含一个?或多个?的概念实质是等价的 ??? 4x3x3x3x3+1：共325个不同概念 实例 A1, A2, …, Ak 个属性，属性Ai有ni个取值 Questions 实例空间 概念空间 概念空间特性 General-to-Specific Ordering Examples h1 = Sunny, ?, ?, Strong, ? h2 = Sunny, ?, ?, ?, ? Satisfies Relation: ? x (? X) and h (? D)，称x 满足（satisfies） h当且仅当 h(x)=1 More_general_than_or_equal_to Relation (?g ): 给定两个概念hi和hj，称hj ?g hi当且仅当对任何实例x ，如果x满足hi则x必定满足hj。 形式化定义：（? x ? X）hi(x) =1 ? hj(x) =1 。 ?g 在概念空间上定义了一个偏序（partial order） 偏序关系：自反，反对称和传递 对在概念空间中有哪些信誉好的足球投注网站满足要求的概念非常有用。 Other Relations More_general_than (?g ) More_specific_than_or_equal_to (?g ) More_specific_than (?g ) Find-S：第一个概念学习算法 利用?g关系进行有哪些信誉好的足球投注网站 从最特化的概念开始，每当遇到不能覆盖的正样本，就泛化该概念，使其能够覆盖上述正样本。 特殊?一般 算法描述 1. 初始化h为概念空间H中最特化的概念