机器学习 第2章概念学习和一般到特殊序 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 1 机器学习 第2章 概念学习和一般到特殊序
提纲 概念学习 给定某一类别的若干正例和反例,从中获得该类别 的一般定义。 ·搜索的观点 在预定义的假设空间中搜索假设,使其与训练样例 有最佳的拟合 利用假设空间的偏序结构 算法收敛到正确假设的条件 归纳学习的本质,从训练数据中泛化的理由 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏 2
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 2 提纲 • 概念学习 – 给定某一类别的若干正例和反例，从中获得该类别 的一般定义。 • 搜索的观点 – 在预定义的假设空间中搜索假设，使其与训练样例 有最佳的拟合。 – 利用假设空间的偏序结构 • 算法收敛到正确假设的条件 • 归纳学习的本质，从训练数据中泛化的理由
简介 ·许多机器学习涉及到从特殊训练样例中得到 般概念。 概念,可被看作一个对象或事件集合,它是从 更大的集合中选取的子集,或在这个较大集合 中定义的布尔函数。 概念学习问题的定义 给定一个样例集合以及每个样例是否属于某个概念 的标注,怎样推断出该概念的一般定义。又称从样 例中逼近布尔函数 概念学习是指从有关某个布尔函数的输入输出训练 样例中推断出该布尔函数 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 3 简介 • 许多机器学习涉及到从特殊训练样例中得到一 般概念。 • 概念，可被看作一个对象或事件集合，它是从 更大的集合中选取的子集，或在这个较大集合 中定义的布尔函数。 • 概念学习问题的定义 – 给定一个样例集合以及每个样例是否属于某个概念 的标注，怎样推断出该概念的一般定义。又称从样 例中逼近布尔函数。 – 概念学习是指从有关某个布尔函数的输入输出训练 样例中推断出该布尔函数
概念学习任务 个例子 目标概念,Aldo进行水上运动的日子,表示 为布尔函数 Enjoy Sport 任务目的,基于某天的各属性,预测 EnjoySport的值 个样例集,每个样例表示为属性的集合 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 4 概念学习任务 • 一个例子 – 目标概念，Aldo进行水上运动的日子，表示 为布尔函数EnjoySport – 任务目的，基于某天的各属性，预测 EnjoySport的值 – 一个样例集，每个样例表示为属性的集合
概念学习任务(2) 表2-1目标概念 Enjoy Sport的训练样例 Example Sky AirTemp Humidity Wind Water Forecast Enjoy Sport Sunny Warm Normal Strong Warm Same Ye Sunny Warm Strong W arm Yes 234 Cold High Strong W arm Change Sunny W Strong Cool Change Ye 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 5 概念学习任务（2） 4 Sunny Warm High Strong Cool Change Yes 3 Rainy Cold High Strong Warm Change Yes 2 Sunny Warm High Strong Warm Same Yes 1 Sunny Warm Normal Strong Warm Same Yes Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 表2-1 目标概念EnjoySport的训练样例
概念学习任务(3) 表示假设的形式 个简单的形式,实例的各属性约束的合取式 令每个假设为6个约束(或变量)的向量,每个约 束对应一个属性可取值范围,为 ·?任意本属性可接受的值 ·明确指定的属性值 ￠不接受任何值 假设的例子 ?,?,?,2?,? ∥/所有的样例都是正例 ∥/所有的样例都是反例 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 概念学习任务（3） • 表示假设的形式 – 一个简单的形式，实例的各属性约束的合取式 – 令每个假设为6个约束（或变量）的向量，每个约 束对应一个属性可取值范围，为 • ？任意本属性可接受的值 • 明确指定的属性值 • 不接受任何值 – 假设的例子 • • // 所有的样例都是正例 • // 所有的样例都是反例
概念学习任务(4) Enjoy Sport概念学习任务 已知 实例集Ⅹ 每个实例x由6个属性描述,每个属性的取值范围已确定 假设集H 每个假设h描述为6个属性的取值约束的合取 目标概念c 个布尔函数,变量为实例 训练样例集D ·目标函数(或目标概念)的正例和反例 求解 H中的一假设h,使对于X中任意x,h(x)=c(x) 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 概念学习任务（4） EnjoySport概念学习任务 • 已知 – 实例集X • 每个实例x由6个属性描述，每个属性的取值范围已确定 – 假设集H • 每个假设h描述为6个属性的取值约束的合取 – 目标概念c • 一个布尔函数，变量为实例 – 训练样例集D • 目标函数（或目标概念）的正例和反例 • 求解 – H中的一假设h，使对于X中任意x，h(x)=c(x)
术语定义 实例x 实例集Ⅹ 概念 目标概念c 训练样例x 训练样例集D 正例,目标概念成员 反例,非目标概念成员 假设h 假设集H 机器学习的目标就是寻找一个假设h,使得对所有的h,都有h(x)=c(x) 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 术语定义 • 实例x • 实例集X • 概念 • 目标概念c • 训练样例x • 训练样例集D • 正例，目标概念成员 • 反例，非目标概念成员 • 假设h • 假设集H 机器学习的目标就是寻找一个假设h，使得对所有的h，都有h(x)=c(x)
纳学习假设 什么是归纳学习? 从特殊的样例得到普遍的规律 归纳 只能保证输出的假设能与训练样例相拟合 归纳假设的一个基本假定 对于未见实例最好的假设就是与训练数据最佳拟合的假设 归纳学习假设 任一假设如果在足够大的训练样例集中很好地逼近目标函数,它也 能在未见实例中很好地逼近目标函数。 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 9 归纳学习假设 • 什么是归纳学习？ – 从特殊的样例得到普遍的规律 • 归纳 – 只能保证输出的假设能与训练样例相拟合 • 归纳假设的一个基本假定 – 对于未见实例最好的假设就是与训练数据最佳拟合的假设 • 归纳学习假设 – 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也 能在未见实例中很好地逼近目标函数
作为搜索的概念学习 概念学习可以看作一个搜索的过程 搜索范围:假设的表示所隐含定义的整个空 间 搜索目标:能够最好地拟合训练样例的偎设 当假设的表示形式选定后,那么就隐含 地为学习算法确定了所有假设的空间 例子 EnjoySportI的假设空间 2003.12.18 机器学习-概念学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-概念学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 作为搜索的概念学习 • 概念学习可以看作一个搜索的过程 – 搜索范围：假设的表示所隐含定义的整个空 间 – 搜索目标：能够最好地拟合训练样例的假设 • 当假设的表示形式选定后，那么就隐含 地为学习算法确定了所有假设的空间 • 例子EnjoySport的假设空间