2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 8章 基于实例的学习
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
已知一系列的训练样例，许多学习方法为目标函数建立起明确的一般化描述，
基于实例的学习方法只是简单地把训练样例存储起来，从这些实例中泛化的工作被推迟到必须分类新的实例时
每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
概述（ 2）
基于实例的学习方法包括：
– 假定实例可以表示成欧氏空间中的点
最近邻法
局部加权回归法
– 对实例采用更复杂的符号表示
基于案例的推理
基于实例的学习方法有时被称为消极学习法，它把处理工作延迟到必须分类新的实例时
这种延迟的学习方法有一个优点：不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介
基于实例的学习方法的学习过程只是简单地存储已知的训练数据，当遇到新的查询实例时，一系列相似的实例从存储器中取出，用来分类新的查询实例
与其他方法相比，基于实例的学习方法的一个关键差异是：可以为不同的待分类查询实例建立不同的目标函数逼近
许多技术不建立目标函数在整个实例空间上的逼近，
只建立局部逼近，并将其用于与新实例邻近的实例
这样做的好处是：有时目标函数很复杂，但具有不太复杂的局部逼近描述
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
简介（ 2）
基于案例的学习（基于实例的学习的一种）使用复杂的符号表示法来描述实例，也按照这种方式确定邻近实例
基于实例的方法的不足：
– 分类新实例的开销可能很大。
几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。如何有效地索引训练样例是一个重要的问题
– 当从存储器中检索相似的训练样例时，一般考虑实例的所有属性，如果目标概念仅依赖于很多属性中的几个，那么真正最“相似”的实例之间可能相距甚远
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
简介（ 3）
k-近邻算法和它的几个变体
局部加权回归法，这是一种建立目标函数的局部逼近的学习方法，被看作 k-近邻算法的一般形式
径向基函数网络，它为基于实例的学习算法和神经网络学习算法提供了一个有趣的桥梁
基于案例的推理，这是一种使用符号表示和基于知识的推理的方法
消极学习方法和积极学习方法之间的差异
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
k-近邻算法
k-近邻算法是最基本的基于实例的学习方法
k-近邻算法假定所有的实例对应于 n维空间 Rn
中的点，任意的实例表示为一个特征向量
<a1(x),...,an(x)>
根据欧氏距离定义实例的距离。两个实例 xi和 xj
的距离 d(xi,xj)定义为
在最近邻学习中，目标函数值可以是离散的也可以是连续的，本节先考虑离散的情况。
nr jrirji xaxaxxd 1 2)()(),(
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
k-近邻算法（ 2）
考虑离散目标函数 f,Rn?V,V={v1,...,vs}
表 8-1逼近离散值函数 f,Rn?V的 k-近邻算法
– 训练算法
将每个训练样例 <x,f(x)>加入到列表 training_examples
– 分类算法
给定一个要分类的查询实例 xq
– 在 training_examples中选出最靠近 xq的 k个实例，并用 x1...xk表示
– 返回
– 其中
ki iVvq xfvxf 1 ))(,(m a xa r g)(
ba baba 01),(?
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图
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
k-近邻算法（ 4）
离散的 k-近邻算法作简单修改后可用于逼近连续值的目标函数。即计算 k个最接近样例的平均值，而不是计算其中的最普遍的值，为逼近 f,Rn?R，计算式如下：
k
xfxf k
i iq 1
)()(?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
距离加权最近邻算法
对 k-近邻算法的一个改进是对 k个近邻的贡献加权，越近的距离赋予越大的权值，比如：
为了处理查询点 xq恰好匹配某个训练样例 xi，从而导致
d(xq,xi)2为 0的情况，令这种情况下的 等于 f(xi)，如果有多个这样的训练样例，我们使用它们占多数的分类
也可以用类似的方式对实值目标函数进行距离加权，
用下式替代表 8-1中的计算式,wi的定义与前相同
ki iiVvq xfvwxf 1 ))(,(m a xa r g)( 2),( 1 iqi xxdw?
)(qxf?
k
i
i
k
i
ii
q
w
xfw
xf
1
1
)(
)(?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
距离加权最近邻算法（ 2）
k-近邻算法的所有变体都只考虑 k个近邻用以分类查询点，如果使用按距离加权，那么可以允许所有的训练样例影响 xq的分类，因为非常远的实例的影响很小
考虑所有样例的唯一不足是会使分类运行得更慢
如果分类一个新实例时，考虑所有的训练样例，
我们称为全局法；如果仅考虑靠近的训练样例，
称为局部法
当式子 8.4应用于全局法时，称为 Shepard法
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
对 k-近邻算法的说明
距离加权的 k-近邻算法对训练数据中的噪声有很好的健壮性，通过取 k个近邻的加权平均，可以消除孤立的噪声样例的影响
k-近邻的归纳偏置是：一个实例的分类 xq与在欧氏空间中它附近的实例的分类相似
k-近邻方法的一个实践问题：维度灾害
– 许多学习方法，比如决策树方法，选择部分属性作出判断，
而 k-近邻方法中实例间的距离是根据实例的所有属性计算的
– 实例间距离会被大量的不相关属性所支配，可能导致相关属性的值很接近的实例相距很远
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
对 k-近邻算法的说明（ 2）
维度灾害的解决方法：对属性加权，相当于按比例缩放欧氏空间中的坐标轴，缩短对应不太相关的属性的坐标轴，拉长对应更相关属性的坐标轴
每个坐标轴应伸展的数量可以通过交叉验证的方法自动决定，具体做法如下：
– 假定使用因子 zj伸展第 j个根坐标轴，选择各个 zj的值，使得学习算法的真实分类错误率最小化
– 这个真实错误率可以使用交叉验证来估计
– 可以多次重复这个处理过程，使得加权因子的估计更加准确
另一种更强有力的方法是从实例空间中完全消除最不相关的属性，等效于设置某个缩放因子为 0
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
对 k-近邻算法的说明（ 3）
k-近邻算法的另外一个实践问题：如何建立高效的索引。
k-近邻算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算
已经开发了很多对存储的训练样例进行索引的方法，
以便能高效地确定最近邻
kd-tree把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的节点内，通过测试新查询 xq的选定属性，树的内部节点把查询 xq排列到相关的叶结点
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
术语解释
来自统计模式识别领域的术语
– 回归：逼近一个实数值的目标函数
– 残差：逼近目标函数时的误差
– 核函数：一个距离函数，用来决定每个训练样例的权值，就是使 wi=K(d(xi,xq))的函数 K
)()( xfxf
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
局部加权回归
前面描述的最近邻方法可以被看作在单一的查询点
x=xq上逼近目标函数 f(x)
局部加权回归是上面方法的推广，它在环绕 xq的局部区域内为目标函数 f建立明确的逼近
局部加权回归使用附近的或距离加权的训练样例来形成对 f的局部逼近
例如，使用线性函数、二次函数、多层神经网络在环绕 xq的邻域内逼近目标函数
局部加权回归的名称解释
– 局部：目标函数的逼近仅仅根据查询点附近的数据
– 加权：每个训练样例的贡献由它与查询点间的距离加权得到
– 回归：表示逼近实数值函数的问题
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
局部加权回归（ 2）
给定一个新的查询实例 xq，局部加权回归的一般方法是：
– 建立一个逼近,使 拟合环绕 xq的邻域内的训练样例
– 用 计算 的值
– 删除 的描述
f? f?
f?
)(? qxff?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
局部加权线性回归
使用如下形式的线性函数来逼近 xq邻域的目标函数 f
第 4章我们讨论了梯度下降方法，在拟合以上形式的线性函数到给定的训练集合时，它被用来找到使误差最小化的系数 w0...wn，当时我们感兴趣的是目标函数的全局逼近，即得到的梯度下降训练法则是
)(...)()(? 110 xawxawwxf nn
Dx xfxfE 2))(?)((21
Dx jj xaxfxfw )())(?)((?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
局部加权线性回归（ 2）
三种重新定义误差准则 E，以着重于拟合局部训练样例，记为 E(xq)
– 只对在 k个近邻上的误差平方最小化
– 使整个训练样例集合 D上的误差平方最小化，但对每个训练样例加权，权值为关于相距 xq距离的某个递减函数 K
– 综合 1和 2
个近 邻的 kxxq
q
xfxfxE 21 ))(?)((21)(
Dx qq xxdKxfxfxE )),(())(?)((21)( 22
个近 邻的 kxx qq
q
xxdKxfxfxE )),(())(?)((21)( 22
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
局部加权线性回归（ 3）
准则 2或许最令人满意，但所需的计算量随着训练样例数量线性增长
准则 3很好地近似了准则 2，并且具有如下优点：计算开销独立于训练样例总数，
仅依赖于最近邻数 k
对应准则 3的梯度下降法则是
个近 邻的 kxx jqi q xaxfxfxxdKw )())(?)() ) (,((?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
局部加权回归的说明
大多数情况下，通过一个常量、线性函数或二次函数来局部逼近目标函数，更复杂的函数形式不太常见，原因是：
– 对每个查询实例用更复杂的函数来拟合，其代价十分高昂
– 在足够小的实例空间子域上，使用这些简单的近似已能很好地模拟目标函数
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
径向基函数
径向基函数是另一种实现函数逼近的方法，它与距离加权回归和人工神经网络都有着紧密联系
待学习的假设是一个以下形式的函数
xu是 X中一个实例，核函数 Ku(d(xu,x))被定义为随距离
d(xu,x)的增加而减小,k是用户提供的常量，用来指定要包含的核函数的数量
尽管 是对 f(x)的全局逼近，但来自每个 Ku(d(xu,x))项的贡献被局部化到点 xu附近的区域
一种很常见的做法是选择每个核函数 Ku(d(xu,x))为高斯函数（表示正态分布的函数）
ku uuu xxdKwwxf 10 )),(()(?
)(?xf
),(2 1 22)),(( xxduu uuexxdK
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
径向基函数（ 2）
Hartman et al.1990指出，式子 8.8的函数形式能够以任意小的误差逼近任何函数，只要以上高斯核的数量足够大，并且可以分别指定每个核的宽度
图 8-2径向基函数网络（ RBF），式子 8.8给出的函数可以看作是描述了一个两层的网络，第一层计算不同的
Ku(d(xu,x))，第二层计算第一层单元值的线性组合
给定了目标函数的训练样例集合，一般分两个阶段来训练 RBF网络
– 决定隐藏单元的数量 k，并通过定义核函数中心点和方差来定义每个隐藏单元
– 使用式子 8.5给出的全局误差准则来训练权值 wu，使网络拟合训练数据程度最大化
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
径向基函数（ 3）
已经提出了几种方法来选取适当的隐藏单元或核函数的数量
– 为每一个训练样例 <xi,f(xi)>分配一个高斯核函数，
中心点设为 xi，所有高斯函数的宽度可被赋予同样的值
RBF网络学习目标函数的全局逼近，其中每个训练样例
<xi,f(xi)>都只在 xi的邻域内影响 的值
这种核函数的一个优点是允许 RBF网络精确地拟合训练数据
对于任意 m个训练样例集合，合并 m个高斯核函数的权值
w0...wm，可以被设置为使得对于每个训练样例 <xi,f(xi)>都满足
)(? ixf
)()(? ii xfxf?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
径向基函数（ 4）
– 选取一组数量少于训练样例数量的核函数，这种方法更有效，特别是训练样例数量巨大时
核函数分布在整个实例空间 X上，它们中心之间有均匀的间隔
或者也可以非均匀地分布核函数中心，特别是在实例本身在 X上非均匀分布的时候
– 可以随机选取训练样例的一个子集作为核函数的重心，从而对实例的基准分布进行采样
– 或者可以标识出实例的原始聚类，然后以每个聚类为中心加入一个核函数
把训练实例拟合到混合高斯,6.12.1节讨论的 EM算法提供了一种从 k个高斯函数的混合中选择均值，以最佳拟合观察到实例的方法
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
径向基函数（ 5）
总而言之，用多个局部核函数的线性组合表示的径向基函数网络提供了一种目标函数的全局逼近
仅当输入落入某个核函数的中心和宽度所定义的区域时，这个核函数的值才是不可忽略的
RBF网络可以被看作目标函数的多个局部逼近的平滑线性组合
RBF网络的一个优点是，与反向传播算法训练的前馈网络相比，它的训练更加高效，这是因为 RBF网络的输入层和输出层可以被分别训练
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
基于案例的推理
k-近邻算法和局部加权回归具有三个共同的关键特性：
– 消极学习方法
– 通过分析相似的实例来分类新的查询实例，而忽略与查询极其不同的实例
– 实例表示为 n维欧氏空间中的实数点
基于案例的推理（ CBR）满足前 2个原则，但不满足第 3个
CBR使用更丰富的符号描述来表示实例，用来检索实例的方法也更加复杂
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
基于案例的推理（ 2）
CBR已被用于解决很多问题
– 根据数据库中存储的以前的设计图纸，来进行机械设备的总体设计
– 根据以前的裁决来对新的法律案件进行推理
– 通过对以前的相似问题的解决方案的复用或合并，
解决规划和调度问题
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
基于案例的推理（ 3）
一个例子,CADET系统采用基于案例的推理来辅助简单机械设备的总体设计（图 8-3）
– 条件
使用一个数据库，其中包含大约 75个以前的设计或设计片断
内存中每一个实例是通过它的结构和定性的功能来表示的，新的设计问题通过所要求的功能和结构来表示
– 方法
给定新设计问题的功能说明,CADET从它的案例库中搜索存储的案例，使它的功能描述和新设计问题相匹配
– 如果发现了一个精确的匹配，表明某个存储案例精确地实现了所要求的功能，那么可以返回这个案例作为新设计问题的建议方案
– 否则,CADET可能找到匹配所需功能的不同子图的案例
在两个功能图间搜索同构子图，以发现一个案例的某部分，使它匹配更多的案例
加工原始的功能说明图，产生等价的子图以匹配更多的案例
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
基于案例的推理（ 4）
通过检索匹配不同子图的多个案例，有时可以拼接得到整个设计
但是，从多个检索到的案例产生最终方案的过程可能很复杂
– 为了合并存储案例中检索到的部分，可能需要从头设计系统的各个部分，也可能需要回溯以前的设计子目标，从而丢弃前面检索到的案例
CADET合并和自适应已检索到案例并形成最终设计的能力有限，它主要依赖用户来做自适应阶段的处理
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
基于案例的推理（ 5）
CADET的问题框架
– 在 CADET中每个存储的训练样例描绘了一个功能图以及实现该功能的结构
– 实例空间定义为所有功能图的空间，目标函数 f映射到实现这些功能的结构
– 每个存储训练样例 <x,f(x)>是一个序偶，描述某个功能图 x和实现 x的结构 f(x)
– 系统通过学习训练样例，以输出满足功能图查询输入 xq的结构 f(xq)
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
基于案例的推理（ 6）
CADET系统区别于 k-近邻方法的一般特征
– 实例（或称案例）可以用丰富的符号描述表示，因此可能需要不同于欧氏距离的相似性度量
– 检索到的多个案例可以合并形成新问题的解决方案，合并案例的过程与 k-近邻方法不同，依赖于知识推理而不是统计方法
– 案例检索、基于知识的推理、问题求解是紧密耦合在一起的
概括而言，基于案例的推理是一种基于实例的学习方法，在这个方法中
– 实例可以是丰富的关系的描述
– 案例检索和合并过程可能依赖于知识推理和搜索密集的问题求解方法
一个研究课题：改进索引案例的方法
– 句法相似度量仅能近似地指出特定案例与特定问题的相关度，而不能捕捉其他难点，比如多个设计片断的不兼容性
– 发现这些难点后，可以回溯，并且可用来改进相似性度量
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
对消极学习和积极学习的评价
本章考虑了三种消极学习方法,k-近邻、局部加权回归、基于案例的推理
本章考虑了一种积极学习方法：学习径向基函数网络的方法
消极方法和积极方法的差异：
– 计算时间的差异
消极算法在训练时需要较少的计算，但在预测新查询的目标值时需要更多的计算时间
– 对新查询的分类的差异（归纳偏置的差异）
消极方法在决定如何从训练数据 D中泛化时考虑查询实例 xq
积极方法在见到 xq之前，就完成了泛化
– 核心观点：消极学习可以通过很多局部逼近的组合表示目标函数，积极学习必须在训练时提交单个的全局逼近
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
对消极学习和积极学习的评价
（ 2）
使用多个局部逼近的积极方法，可以产生与消极方法的局部逼近同样的效果吗？径向基函数网络是对这个目标的尝试
RBF学习方法是在训练时提交目标函数全局逼近的积极方法，然而，一个 RBF网络把这个全局函数表示为多个目标局部核函数的线性组合
RBF学习方法创建的局部逼近不能达到像消极学习方法中那样特别针对查询点
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
小结
基于实例的学习方法推迟处理训练样例，直到必须分类一个新查询实例时才进行。它们不必形成一个明确的假设来定义整个实例空间上的完整目标函数，而是对每个查询实例形成一个不同的目标函数局部逼近
基于实例的方法的优点：通过一系列不太复杂的局部逼近来模拟复杂目标函数，而且不会损失训练样例中蕴含的任何信息
基于实例的方法的主要的实践问题：
– 分类新实例的效率
– 难以选择用来检索相关实例的合适的距离度量
– 无关特征对距离度量的负作用
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
小结（ 2）
k-近邻假定实例对应于 n维欧氏空间中的点，一个新查询的目标函数值是根据 k个与其最近的训练样例的值估计得到
局部加权回归法是 k-近邻方法的推广，为每个查询实例建立一个明确的目标函数的局部逼近，逼近方法可以基于常数、线性函数、二次函数等这类简单的函数形式，也可以基于核函数
径向基函数网络是一类由空间局部化核函数构成的人工神经网络，可被看作是基于实例的方法和神经网络方法的结合
基于案例的推理使用复杂的逻辑描述而不是欧氏空间中的点来表示实例。给定实例的符号描述，已经提出了许多方法将训练样例映射成新实例的目标函数值
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
补充读物
k-近邻算法
– Cover & Hart1967提出了早期的理论结果
– Duda & Hart1973提供了一个很好的概述
– Bishop1995讨论了 k-近邻算法以及它与概率密度估计的关系
– Atkeson et al.1997对局部加权回归方法给出了一个非常好的纵览
– Atkeson et al.1997b给出了这些方法在机器人控制方面的应用
径向基函数
– Bishop1995提供了一个全面讨论
– Powell1987和 Poggio & Girosi1990给出了其他论述
基于案例的推理
– Kolodner1993提供了基于案例的推理的一般介绍
机器学习第 8章 基于实例的学习
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
已知一系列的训练样例，许多学习方法为目标函数建立起明确的一般化描述，
基于实例的学习方法只是简单地把训练样例存储起来，从这些实例中泛化的工作被推迟到必须分类新的实例时
每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
概述（ 2）
基于实例的学习方法包括：
– 假定实例可以表示成欧氏空间中的点
最近邻法
局部加权回归法
– 对实例采用更复杂的符号表示
基于案例的推理
基于实例的学习方法有时被称为消极学习法，它把处理工作延迟到必须分类新的实例时
这种延迟的学习方法有一个优点：不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介
基于实例的学习方法的学习过程只是简单地存储已知的训练数据，当遇到新的查询实例时，一系列相似的实例从存储器中取出，用来分类新的查询实例
与其他方法相比，基于实例的学习方法的一个关键差异是：可以为不同的待分类查询实例建立不同的目标函数逼近
许多技术不建立目标函数在整个实例空间上的逼近，
只建立局部逼近，并将其用于与新实例邻近的实例
这样做的好处是：有时目标函数很复杂，但具有不太复杂的局部逼近描述
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
简介（ 2）
基于案例的学习（基于实例的学习的一种）使用复杂的符号表示法来描述实例，也按照这种方式确定邻近实例
基于实例的方法的不足：
– 分类新实例的开销可能很大。
几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。如何有效地索引训练样例是一个重要的问题
– 当从存储器中检索相似的训练样例时，一般考虑实例的所有属性，如果目标概念仅依赖于很多属性中的几个，那么真正最“相似”的实例之间可能相距甚远
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
简介（ 3）
k-近邻算法和它的几个变体
局部加权回归法，这是一种建立目标函数的局部逼近的学习方法，被看作 k-近邻算法的一般形式
径向基函数网络，它为基于实例的学习算法和神经网络学习算法提供了一个有趣的桥梁
基于案例的推理，这是一种使用符号表示和基于知识的推理的方法
消极学习方法和积极学习方法之间的差异
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
k-近邻算法
k-近邻算法是最基本的基于实例的学习方法
k-近邻算法假定所有的实例对应于 n维空间 Rn
中的点，任意的实例表示为一个特征向量
<a1(x),...,an(x)>
根据欧氏距离定义实例的距离。两个实例 xi和 xj
的距离 d(xi,xj)定义为
在最近邻学习中，目标函数值可以是离散的也可以是连续的，本节先考虑离散的情况。
nr jrirji xaxaxxd 1 2)()(),(
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
k-近邻算法（ 2）
考虑离散目标函数 f,Rn?V,V={v1,...,vs}
表 8-1逼近离散值函数 f,Rn?V的 k-近邻算法
– 训练算法
将每个训练样例 <x,f(x)>加入到列表 training_examples
– 分类算法
给定一个要分类的查询实例 xq
– 在 training_examples中选出最靠近 xq的 k个实例，并用 x1...xk表示
– 返回
– 其中
ki iVvq xfvxf 1 ))(,(m a xa r g)(
ba baba 01),(?
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图
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
k-近邻算法（ 4）
离散的 k-近邻算法作简单修改后可用于逼近连续值的目标函数。即计算 k个最接近样例的平均值，而不是计算其中的最普遍的值，为逼近 f,Rn?R，计算式如下：
k
xfxf k
i iq 1
)()(?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
距离加权最近邻算法
对 k-近邻算法的一个改进是对 k个近邻的贡献加权，越近的距离赋予越大的权值，比如：
为了处理查询点 xq恰好匹配某个训练样例 xi，从而导致
d(xq,xi)2为 0的情况，令这种情况下的 等于 f(xi)，如果有多个这样的训练样例，我们使用它们占多数的分类
也可以用类似的方式对实值目标函数进行距离加权，
用下式替代表 8-1中的计算式,wi的定义与前相同
ki iiVvq xfvwxf 1 ))(,(m a xa r g)( 2),( 1 iqi xxdw?
)(qxf?
k
i
i
k
i
ii
q
w
xfw
xf
1
1
)(
)(?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
距离加权最近邻算法（ 2）
k-近邻算法的所有变体都只考虑 k个近邻用以分类查询点，如果使用按距离加权，那么可以允许所有的训练样例影响 xq的分类，因为非常远的实例的影响很小
考虑所有样例的唯一不足是会使分类运行得更慢
如果分类一个新实例时，考虑所有的训练样例，
我们称为全局法；如果仅考虑靠近的训练样例，
称为局部法
当式子 8.4应用于全局法时，称为 Shepard法
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
对 k-近邻算法的说明
距离加权的 k-近邻算法对训练数据中的噪声有很好的健壮性，通过取 k个近邻的加权平均，可以消除孤立的噪声样例的影响
k-近邻的归纳偏置是：一个实例的分类 xq与在欧氏空间中它附近的实例的分类相似
k-近邻方法的一个实践问题：维度灾害
– 许多学习方法，比如决策树方法，选择部分属性作出判断，
而 k-近邻方法中实例间的距离是根据实例的所有属性计算的
– 实例间距离会被大量的不相关属性所支配，可能导致相关属性的值很接近的实例相距很远
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
对 k-近邻算法的说明（ 2）
维度灾害的解决方法：对属性加权，相当于按比例缩放欧氏空间中的坐标轴，缩短对应不太相关的属性的坐标轴，拉长对应更相关属性的坐标轴
每个坐标轴应伸展的数量可以通过交叉验证的方法自动决定，具体做法如下：
– 假定使用因子 zj伸展第 j个根坐标轴，选择各个 zj的值，使得学习算法的真实分类错误率最小化
– 这个真实错误率可以使用交叉验证来估计
– 可以多次重复这个处理过程，使得加权因子的估计更加准确
另一种更强有力的方法是从实例空间中完全消除最不相关的属性，等效于设置某个缩放因子为 0
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
对 k-近邻算法的说明（ 3）
k-近邻算法的另外一个实践问题：如何建立高效的索引。
k-近邻算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算
已经开发了很多对存储的训练样例进行索引的方法，
以便能高效地确定最近邻
kd-tree把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的节点内，通过测试新查询 xq的选定属性，树的内部节点把查询 xq排列到相关的叶结点
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
术语解释
来自统计模式识别领域的术语
– 回归：逼近一个实数值的目标函数
– 残差：逼近目标函数时的误差
– 核函数：一个距离函数，用来决定每个训练样例的权值，就是使 wi=K(d(xi,xq))的函数 K
)()( xfxf
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
局部加权回归
前面描述的最近邻方法可以被看作在单一的查询点
x=xq上逼近目标函数 f(x)
局部加权回归是上面方法的推广，它在环绕 xq的局部区域内为目标函数 f建立明确的逼近
局部加权回归使用附近的或距离加权的训练样例来形成对 f的局部逼近
例如，使用线性函数、二次函数、多层神经网络在环绕 xq的邻域内逼近目标函数
局部加权回归的名称解释
– 局部：目标函数的逼近仅仅根据查询点附近的数据
– 加权：每个训练样例的贡献由它与查询点间的距离加权得到
– 回归：表示逼近实数值函数的问题
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
局部加权回归（ 2）
给定一个新的查询实例 xq，局部加权回归的一般方法是：
– 建立一个逼近,使 拟合环绕 xq的邻域内的训练样例
– 用 计算 的值
– 删除 的描述
f? f?
f?
)(? qxff?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
局部加权线性回归
使用如下形式的线性函数来逼近 xq邻域的目标函数 f
第 4章我们讨论了梯度下降方法，在拟合以上形式的线性函数到给定的训练集合时，它被用来找到使误差最小化的系数 w0...wn，当时我们感兴趣的是目标函数的全局逼近，即得到的梯度下降训练法则是
)(...)()(? 110 xawxawwxf nn
Dx xfxfE 2))(?)((21
Dx jj xaxfxfw )())(?)((?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
局部加权线性回归（ 2）
三种重新定义误差准则 E，以着重于拟合局部训练样例，记为 E(xq)
– 只对在 k个近邻上的误差平方最小化
– 使整个训练样例集合 D上的误差平方最小化，但对每个训练样例加权，权值为关于相距 xq距离的某个递减函数 K
– 综合 1和 2
个近 邻的 kxxq
q
xfxfxE 21 ))(?)((21)(
Dx qq xxdKxfxfxE )),(())(?)((21)( 22
个近 邻的 kxx qq
q
xxdKxfxfxE )),(())(?)((21)( 22
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
局部加权线性回归（ 3）
准则 2或许最令人满意，但所需的计算量随着训练样例数量线性增长
准则 3很好地近似了准则 2，并且具有如下优点：计算开销独立于训练样例总数，
仅依赖于最近邻数 k
对应准则 3的梯度下降法则是
个近 邻的 kxx jqi q xaxfxfxxdKw )())(?)() ) (,((?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
局部加权回归的说明
大多数情况下，通过一个常量、线性函数或二次函数来局部逼近目标函数，更复杂的函数形式不太常见，原因是：
– 对每个查询实例用更复杂的函数来拟合，其代价十分高昂
– 在足够小的实例空间子域上，使用这些简单的近似已能很好地模拟目标函数
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
径向基函数
径向基函数是另一种实现函数逼近的方法，它与距离加权回归和人工神经网络都有着紧密联系
待学习的假设是一个以下形式的函数
xu是 X中一个实例，核函数 Ku(d(xu,x))被定义为随距离
d(xu,x)的增加而减小,k是用户提供的常量，用来指定要包含的核函数的数量
尽管 是对 f(x)的全局逼近，但来自每个 Ku(d(xu,x))项的贡献被局部化到点 xu附近的区域
一种很常见的做法是选择每个核函数 Ku(d(xu,x))为高斯函数（表示正态分布的函数）
ku uuu xxdKwwxf 10 )),(()(?
)(?xf
),(2 1 22)),(( xxduu uuexxdK
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
径向基函数（ 2）
Hartman et al.1990指出，式子 8.8的函数形式能够以任意小的误差逼近任何函数，只要以上高斯核的数量足够大，并且可以分别指定每个核的宽度
图 8-2径向基函数网络（ RBF），式子 8.8给出的函数可以看作是描述了一个两层的网络，第一层计算不同的
Ku(d(xu,x))，第二层计算第一层单元值的线性组合
给定了目标函数的训练样例集合，一般分两个阶段来训练 RBF网络
– 决定隐藏单元的数量 k，并通过定义核函数中心点和方差来定义每个隐藏单元
– 使用式子 8.5给出的全局误差准则来训练权值 wu，使网络拟合训练数据程度最大化
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
径向基函数（ 3）
已经提出了几种方法来选取适当的隐藏单元或核函数的数量
– 为每一个训练样例 <xi,f(xi)>分配一个高斯核函数，
中心点设为 xi，所有高斯函数的宽度可被赋予同样的值
RBF网络学习目标函数的全局逼近，其中每个训练样例
<xi,f(xi)>都只在 xi的邻域内影响 的值
这种核函数的一个优点是允许 RBF网络精确地拟合训练数据
对于任意 m个训练样例集合，合并 m个高斯核函数的权值
w0...wm，可以被设置为使得对于每个训练样例 <xi,f(xi)>都满足
)(? ixf
)()(? ii xfxf?
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
径向基函数（ 4）
– 选取一组数量少于训练样例数量的核函数，这种方法更有效，特别是训练样例数量巨大时
核函数分布在整个实例空间 X上，它们中心之间有均匀的间隔
或者也可以非均匀地分布核函数中心，特别是在实例本身在 X上非均匀分布的时候
– 可以随机选取训练样例的一个子集作为核函数的重心，从而对实例的基准分布进行采样
– 或者可以标识出实例的原始聚类，然后以每个聚类为中心加入一个核函数
把训练实例拟合到混合高斯,6.12.1节讨论的 EM算法提供了一种从 k个高斯函数的混合中选择均值，以最佳拟合观察到实例的方法
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
径向基函数（ 5）
总而言之，用多个局部核函数的线性组合表示的径向基函数网络提供了一种目标函数的全局逼近
仅当输入落入某个核函数的中心和宽度所定义的区域时，这个核函数的值才是不可忽略的
RBF网络可以被看作目标函数的多个局部逼近的平滑线性组合
RBF网络的一个优点是，与反向传播算法训练的前馈网络相比，它的训练更加高效，这是因为 RBF网络的输入层和输出层可以被分别训练
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
基于案例的推理
k-近邻算法和局部加权回归具有三个共同的关键特性：
– 消极学习方法
– 通过分析相似的实例来分类新的查询实例，而忽略与查询极其不同的实例
– 实例表示为 n维欧氏空间中的实数点
基于案例的推理（ CBR）满足前 2个原则，但不满足第 3个
CBR使用更丰富的符号描述来表示实例，用来检索实例的方法也更加复杂
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
基于案例的推理（ 2）
CBR已被用于解决很多问题
– 根据数据库中存储的以前的设计图纸，来进行机械设备的总体设计
– 根据以前的裁决来对新的法律案件进行推理
– 通过对以前的相似问题的解决方案的复用或合并，
解决规划和调度问题
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
基于案例的推理（ 3）
一个例子,CADET系统采用基于案例的推理来辅助简单机械设备的总体设计（图 8-3）
– 条件
使用一个数据库，其中包含大约 75个以前的设计或设计片断
内存中每一个实例是通过它的结构和定性的功能来表示的，新的设计问题通过所要求的功能和结构来表示
– 方法
给定新设计问题的功能说明,CADET从它的案例库中搜索存储的案例，使它的功能描述和新设计问题相匹配
– 如果发现了一个精确的匹配，表明某个存储案例精确地实现了所要求的功能，那么可以返回这个案例作为新设计问题的建议方案
– 否则,CADET可能找到匹配所需功能的不同子图的案例
在两个功能图间搜索同构子图，以发现一个案例的某部分，使它匹配更多的案例
加工原始的功能说明图，产生等价的子图以匹配更多的案例
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
基于案例的推理（ 4）
通过检索匹配不同子图的多个案例，有时可以拼接得到整个设计
但是，从多个检索到的案例产生最终方案的过程可能很复杂
– 为了合并存储案例中检索到的部分，可能需要从头设计系统的各个部分，也可能需要回溯以前的设计子目标，从而丢弃前面检索到的案例
CADET合并和自适应已检索到案例并形成最终设计的能力有限，它主要依赖用户来做自适应阶段的处理
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
基于案例的推理（ 5）
CADET的问题框架
– 在 CADET中每个存储的训练样例描绘了一个功能图以及实现该功能的结构
– 实例空间定义为所有功能图的空间，目标函数 f映射到实现这些功能的结构
– 每个存储训练样例 <x,f(x)>是一个序偶，描述某个功能图 x和实现 x的结构 f(x)
– 系统通过学习训练样例，以输出满足功能图查询输入 xq的结构 f(xq)
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
基于案例的推理（ 6）
CADET系统区别于 k-近邻方法的一般特征
– 实例（或称案例）可以用丰富的符号描述表示，因此可能需要不同于欧氏距离的相似性度量
– 检索到的多个案例可以合并形成新问题的解决方案，合并案例的过程与 k-近邻方法不同，依赖于知识推理而不是统计方法
– 案例检索、基于知识的推理、问题求解是紧密耦合在一起的
概括而言，基于案例的推理是一种基于实例的学习方法，在这个方法中
– 实例可以是丰富的关系的描述
– 案例检索和合并过程可能依赖于知识推理和搜索密集的问题求解方法
一个研究课题：改进索引案例的方法
– 句法相似度量仅能近似地指出特定案例与特定问题的相关度，而不能捕捉其他难点，比如多个设计片断的不兼容性
– 发现这些难点后，可以回溯，并且可用来改进相似性度量
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
对消极学习和积极学习的评价
本章考虑了三种消极学习方法,k-近邻、局部加权回归、基于案例的推理
本章考虑了一种积极学习方法：学习径向基函数网络的方法
消极方法和积极方法的差异：
– 计算时间的差异
消极算法在训练时需要较少的计算，但在预测新查询的目标值时需要更多的计算时间
– 对新查询的分类的差异（归纳偏置的差异）
消极方法在决定如何从训练数据 D中泛化时考虑查询实例 xq
积极方法在见到 xq之前，就完成了泛化
– 核心观点：消极学习可以通过很多局部逼近的组合表示目标函数，积极学习必须在训练时提交单个的全局逼近
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
对消极学习和积极学习的评价
（ 2）
使用多个局部逼近的积极方法，可以产生与消极方法的局部逼近同样的效果吗？径向基函数网络是对这个目标的尝试
RBF学习方法是在训练时提交目标函数全局逼近的积极方法，然而，一个 RBF网络把这个全局函数表示为多个目标局部核函数的线性组合
RBF学习方法创建的局部逼近不能达到像消极学习方法中那样特别针对查询点
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
小结
基于实例的学习方法推迟处理训练样例，直到必须分类一个新查询实例时才进行。它们不必形成一个明确的假设来定义整个实例空间上的完整目标函数，而是对每个查询实例形成一个不同的目标函数局部逼近
基于实例的方法的优点：通过一系列不太复杂的局部逼近来模拟复杂目标函数，而且不会损失训练样例中蕴含的任何信息
基于实例的方法的主要的实践问题：
– 分类新实例的效率
– 难以选择用来检索相关实例的合适的距离度量
– 无关特征对距离度量的负作用
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
小结（ 2）
k-近邻假定实例对应于 n维欧氏空间中的点，一个新查询的目标函数值是根据 k个与其最近的训练样例的值估计得到
局部加权回归法是 k-近邻方法的推广，为每个查询实例建立一个明确的目标函数的局部逼近，逼近方法可以基于常数、线性函数、二次函数等这类简单的函数形式，也可以基于核函数
径向基函数网络是一类由空间局部化核函数构成的人工神经网络，可被看作是基于实例的方法和神经网络方法的结合
基于案例的推理使用复杂的逻辑描述而不是欧氏空间中的点来表示实例。给定实例的符号描述，已经提出了许多方法将训练样例映射成新实例的目标函数值
2003.12.18 机器学习 -基于实例的学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
补充读物
k-近邻算法
– Cover & Hart1967提出了早期的理论结果
– Duda & Hart1973提供了一个很好的概述
– Bishop1995讨论了 k-近邻算法以及它与概率密度估计的关系
– Atkeson et al.1997对局部加权回归方法给出了一个非常好的纵览
– Atkeson et al.1997b给出了这些方法在机器人控制方面的应用
径向基函数
– Bishop1995提供了一个全面讨论
– Powell1987和 Poggio & Girosi1990给出了其他论述
基于案例的推理
– Kolodner1993提供了基于案例的推理的一般介绍
