机器学习 第8章基于实例的学习 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 1 机器学习 第8章 基于实例的学习
概述 已知一系列的训练样例,许多学习方法为目标 函数建立起明确的一般化描述, 基于实例的学习方法只是简单地把训练样例存 储起来,从这些实例中泛化的工作被推迟到必 须分类新的实例时 每当学习器遇到一个新的查询实例,它分析这 个新实例与以前存储的实例的关系,并据此把 个目标函数值赋给新实例 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏 2
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 2 概述 • 已知一系列的训练样例，许多学习方法为目标 函数建立起明确的一般化描述， • 基于实例的学习方法只是简单地把训练样例存 储起来，从这些实例中泛化的工作被推迟到必 须分类新的实例时 • 每当学习器遇到一个新的查询实例，它分析这 个新实例与以前存储的实例的关系，并据此把 一个目标函数值赋给新实例
概述(2) 基于实例的学习方法包括: 假定实例可以表示成欧氏空间中的点 ·最近邻法 ·局部加权回归法 对实例采用更复杂的符号表示 基于案例的推理 基于实例的学习方法有时被称为消极学习法,它把处 理工作延迟到必须分类新的实例时 这种延迟的学习方法有一个优点:不是在整个实例空 间上一次性地估计目标函数,而是针对每个待分类新 实例作出局部的和相异的估计 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 3 概述（2） • 基于实例的学习方法包括： – 假定实例可以表示成欧氏空间中的点 • 最近邻法 • 局部加权回归法 – 对实例采用更复杂的符号表示 • 基于案例的推理 • 基于实例的学习方法有时被称为消极学习法，它把处 理工作延迟到必须分类新的实例时 • 这种延迟的学习方法有一个优点：不是在整个实例空 间上一次性地估计目标函数，而是针对每个待分类新 实例作出局部的和相异的估计
简介 基于实例的学习方法的学习过程只是简单地存储已知 的训练数据,当遇到新的查询实例时,一系列相似的 实例从存储器中取出,用来分类新的查询实例 与其他方法相比,基于实例的学习方法的一个关键差 异是:可以为不同的待分类查询实例建立不同的目标 函数逼近 许多技术不建立目标函数在整个实例空间上的逼近, 只建立局部逼近,并将其用于与新实例邻近的实例 这样做的好处是:有时目标函数很复杂,但具有不太 复杂的局部逼近描述 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 4 简介 • 基于实例的学习方法的学习过程只是简单地存储已知 的训练数据，当遇到新的查询实例时，一系列相似的 实例从存储器中取出，用来分类新的查询实例 • 与其他方法相比，基于实例的学习方法的一个关键差 异是：可以为不同的待分类查询实例建立不同的目标 函数逼近 • 许多技术不建立目标函数在整个实例空间上的逼近， 只建立局部逼近，并将其用于与新实例邻近的实例 • 这样做的好处是：有时目标函数很复杂，但具有不太 复杂的局部逼近描述
简介(2) 基于案例的学习(基于实例的学习的一种)使 用复杂的符号表示法来描述实例,也按照这种 方式确定邻近实例 基于实例的方法的不足: 分类新实例的开销可能很大。 ·几乎所有的计算都发生在分类时,而不是在第一次遇到训 练样例时。如何有效地索引训练样例是一个重要的问题 当从存储器中检索相似的训练样例时,一般考虑实 例的所有属性,如果目标概念仅依赖于很多属性中 的几个,那么真正最“相似”的实例之间可能相距 甚远 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 5 简介（2） • 基于案例的学习（基于实例的学习的一种）使 用复杂的符号表示法来描述实例，也按照这种 方式确定邻近实例 • 基于实例的方法的不足： – 分类新实例的开销可能很大。 • 几乎所有的计算都发生在分类时，而不是在第一次遇到训 练样例时。如何有效地索引训练样例是一个重要的问题 – 当从存储器中检索相似的训练样例时，一般考虑实 例的所有属性，如果目标概念仅依赖于很多属性中 的几个，那么真正最“相似”的实例之间可能相距 甚远
简介(3) k近邻算法和它的几个变体 局部加权回归法,这是一种建立目标函数的局 部逼近的学习方法,被看作k-近邻算法的一般 形式 径向基函数网络,它为基于实例的学习算法和 神经网络学习算法提供了一个有趣的桥梁 基于案例的推理,这是一种使用符号表示和基 于知识的推理的方法 消极学习方法和积极学习方法之间的差异 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 简介（3） • k-近邻算法和它的几个变体 • 局部加权回归法，这是一种建立目标函数的局 部逼近的学习方法，被看作k-近邻算法的一般 形式 • 径向基函数网络，它为基于实例的学习算法和 神经网络学习算法提供了一个有趣的桥梁 • 基于案例的推理，这是一种使用符号表示和基 于知识的推理的方法 • 消极学习方法和积极学习方法之间的差异
k-近邻算法 k近邻算法是最基本的基于实例的学习方法 k近邻算法假定所有的实例对应于n维空间Rn 中的点,任意的实例表示为一个特征向量 根据欧氏距离定义实例的距离。两个实例x和x 的距离d(x2x)定义为 dxy)=∑(x)-a( 在最近邻学习中,目标函数值可以是离散的也 可以是连续的,本节先考虑离散的情况。 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 k-近邻算法 • k-近邻算法是最基本的基于实例的学习方法 • k-近邻算法假定所有的实例对应于n维空间Rn 中的点，任意的实例表示为一个特征向量 • 根据欧氏距离定义实例的距离。两个实例xi和xj 的距离d(xi ,xj )定义为 • 在最近邻学习中，目标函数值可以是离散的也 可以是连续的，本节先考虑离散的情况。 ( ) = = − n r i j r i r j d x x a x a x 1 2 ( , ) ( ) ( )
k-近邻算法(2) 考虑离散目标函数fRV,V={V1n,s} 表8-1逼近离散值函数fR→V的k近邻算法 训练算法 将每个训练样例加入到列表 training examples 分类算法 给定一个要分类的查询实例x 在 training examples中选出最靠近x的k个实例,并用x1x表 小 返回f(x)← arg max∑6(,f(x) 其中 (a,b) 0a≠b 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 k-近邻算法（2） • 考虑离散目标函数f: Rn→V，V={v1 ,...,vs} • 表8-1逼近离散值函数f: Rn→V的k-近邻算法 – 训练算法 • 将每个训练样例加入到列表training_examples – 分类算法 • 给定一个要分类的查询实例xq – 在training_examples中选出最靠近xq的k个实例，并用x1 ...xk表 示 – 返回 – 其中 = k i i v V q f x v f x 1 ( ) arg max ( , ( )) ˆ = = a b a b a b 0 1 ( , )
k-近邻算法(3) 表8-1的算法返回值是对fx)的估计,它是距离x最近 的k个训练样例中最普遍的f值,结果与k的取值相关 ·图8-1图解了一种简单情况下的k-近邻算法,实例是二 维空间中的点,目标函数具有布尔值,1-近邻算法把x 分类为正例,5-近邻算法把x分类为反例 k-近邻算法不形成关于目标函数f明确的一般假设, 仅在需要时计算每个新查询实例的分类,但依然可以 问:k近邻算法隐含的一般函数是什么? 图8-1中右图画出了1近邻算法在整个实例空间上导致 的决策面形状。这种图称为训练样例集合的 Voronoi图 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 9 k-近邻算法（3） • 表8-1的算法返回值是对f(xq )的估计，它是距离xq最近 的k个训练样例中最普遍的f值，结果与k的取值相关。 • 图8-1图解了一种简单情况下的k-近邻算法，实例是二 维空间中的点，目标函数具有布尔值，1-近邻算法把xq 分类为正例，5-近邻算法把xq分类为反例 • k-近邻算法不形成关于目标函数f的明确的一般假设， 仅在需要时计算每个新查询实例的分类，但依然可以 问：k-近邻算法隐含的一般函数是什么？ • 图8-1中右图画出了1-近邻算法在整个实例空间上导致 的决策面形状。这种图称为训练样例集合的Voronoi图
k-近邻算法(4) 离散的k-近邻算法作简单修改后可用于 逼近连续值的目标函数。即计算k个最接 近样例的平均值,而不是计算其中的最 普遍的值,为逼近fRR,计算式如下: (x)+令f(x) 2003.12.18机器学习-基于实例的学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-基于实例的学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 k-近邻算法（4） • 离散的k-近邻算法作简单修改后可用于 逼近连续值的目标函数。即计算k个最接 近样例的平均值，而不是计算其中的最 普遍的值，为逼近f: Rn→R，计算式如下： k f x f x k i i q =1 ( ) ( ) ˆ