机器学习基于实例的学习课件

1、2022/10/41 第8章 基于实例的学习8.1简介8.2 k一近邻算法8.3局部加权回归8.4径向基函数8.5基于案例的推理8.6对消极学习和积极学习的评论8.7小结和补充读物2022/10/42 8.1简介（1/3）思想：基于实例的学习方法先把训练样例存储起来。泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。基于实例的学习方法有时被称为消极(lazy)学习法，因为它们把处理工作延迟到必须分类新的实例时。与其相对的方法称为积极的（eager)。延迟的或消极的学习方法有一个关键的优点，即它们不是在

2、整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计。2022/10/438.1简介（2/3）基于实例的学习方法包括最近邻法(nearest neighbor NN) 和局部加权回归(locally weighted regression LWR)法，它们都假定实例可以被表示为欧氏空间中的点。基于实例的学习方法还包括基于案例的推理(case-based reasoning CBR）它对实例采用更复杂的符号表示。2022/10/44 8.1简介（3/3）基于实例方法的一个不足是，分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样

3、例时。所以如何有效地索引训练样例，以减少查询时所需的计算是一个重要的实践问题。第二个不足是(尤其对于最近邻法)，当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。2022/10/45 8.2 k一近邻算法（1/5）k一近邻算法假定所有的实例对应于n维空间Rn中的点。一个实例的最近邻是根据标准欧氏距离定义的。即把任意实例x表示为下面的特征向量: 其中,ar(x)表示实例x的第r个属性值。那么，两个实例xi和xj 间的距离定义为d(xi,xj)，其中:2022/10/478.2 k一近邻算法（2/5）

4、下图图解了一种简单情况下的k一近邻算法，在这里实例是二维空间中的点，目标函数具有布尔值。正反训练样例用“+”和“-”分别表示。图中也画出了一个查询点xq 。1一近邻算法把xq分类为正例，然而5一近邻算法把xq分类为反例。2022/10/488.2 k一近邻算法（3/5） k-近邻算法隐含考虑的假设空间H的特性:k-近邻算法并不形成关于目标函数f的明确的一般假设。它仅在需要时计算每个新查询实例的分类。隐含的一般函数是什么?或者说，如果保持训练样例不变，并用X中的每个可能实例查询算法，会得到什么样的分类?2022/10/4108.2 k一近邻算法（5/5） 对k一近邻算法作简单的修改，它可被用于逼

5、近连续值的目标函数。让算法计算k个最接近样例的平均值，而不是计算其中的最普遍的值。更精确地讲，为了逼近一个实值目标函数 ，我们使用公式:2022/10/4118.2.1距离加权最近邻算法（1/3） 对k一近邻算法的一个改进是对k个近邻的贡献加权，根据它们相对查询点xq的距离，将较大的权值赋给较近的近邻。在逼近离散目标函数的算法中，可以根据每个近邻与xq的距离平方的倒数加权这个近邻的“选举权”: 当xq=xi ，将导致分母d(xq xi)2为0，此时令 。如果有多个这样的训练样例，我们使用它们中占多数的分类。2022/10/4128.2.1距离加权最近邻算法（2/3）对实值目标函数进行距离加权，

6、用下式： 其中，wi的定义与前式中相同。注意该式中的分母是一个常量，它将不同权值的贡献归一化(例如，它保证如果对所有的训练样例xi，f(xi)c，那么， 。2022/10/4148.2.2对k-近邻算法的说明（1/6） 按距离加权的k一近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声有很好的健壮性，而且当给定足够大的训练集合时也非常有效。注意，通过取k个近邻的加权平均，可以消除孤立的噪声样例的影响。k一近邻算法的归纳偏置对应于假定:一个实例的分类xq与在欧氏空间中它附近的实例的分类相似。2022/10/4158.2.2对k-近邻算法的说明（2/6）应用k一近邻算法的一个实践问题是，实

7、例间的距离是根据实例的所有属性(也就是包含实例的欧氏空间的所有坐标轴)计算的。考虑把k一近邻算法应用到这样一个问题: 每个实例由20个属性描述，但在这些属性中仅有2个与它的分类有关。在这种情况下，这两个相关属性的值一致的实例可能在这个20维的实例空间中相距很远。结果，依赖这20个属性的相似性度量会误导k一近邻算法的分类。2022/10/4178.2.2对k-近邻算法的说明（4/6）具体做法如下：首先，假定使用加权因子zj，伸展(乘)第j个根坐标轴，选择zj的各个值z1 zn ，以使学习算法的真实分类错误率最小化。其次，这个真实错误率可以使用交叉验证来估计。交叉验证:随机选取现有数据的一个子集作

8、为训练样例，然后决定z1 zn 的值使剩余样例的分类错误率最小化。通过多次重复这个处理过程，可以使加权因子的估计更加准确。这种伸展坐标轴以优化k一近邻算法的过程，提供了一种抑制无关属性影响的机制。2022/10/4188.2.2对k-近邻算法的说明（5/6）另外一种更强有力的方法从实例空间中完全消除最不相关的属性。这等效于设置某个缩放因子zj为0。注意，上面的两种方法都可以被看作以某个常量因子伸展坐标轴。另外一种可选的做法是使用一个在实例空间上变化的值伸展坐标轴。这样增加了算法重新定义距离度量的自由度，然而也增加了过度拟合的风险。所以，局部伸展坐标轴的方法是不太常见的。2022/10/4198

9、.2.2对k-近邻算法的说明（6/6）应用k一近邻算法的另外一个实践问题是如何建立高效的索引。因为k一近邻算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算。一种索引方法是kd-tree，它把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的结点内。通过测试新查询xq的选定属性，就可以把查询xq排列到相关的叶结点。2022/10/4208.2.3术语注解回归(Regression)的含义是逼近一个实数值的目标函数。残差(Residual)是逼近目标函数时的误差核函数(Kernel function)是一个距离函数，它用来决定每个训练样例的权值。换句话说，核函数

10、就是使 wi=K(d(xi,xq)的函数K。2022/10/4218.3局部加权回归（1/2）最近邻方法可以被看作在单一的查询点x= xq上逼近目标函数f(x)。（没有明确的目标函数，只有目标值）局部加权回归是最近邻方法的推广。它在环绕xq的局部区域内为目标函数f建立明确的逼近。使用附近的或距离加权的训练样例来形成这种对f的局部逼近。可以使用线性函数、二次函数、多层神经网络或者其他函数形成在环绕xq的邻域内逼近目标函数。“局部加权回归”名称中，“局部”是指目标函数的逼近仅仅根据查询点附近的数据; “加权”是指每一个训练样例的贡献是由它与查询点间的距离加权的; “回归”表示逼近实数值函数。202

11、2/10/4228.3局部加权回归（2/2） 给定一个新的查询实例，局部加权回归的一般方法是：建立一个逼近 ，使 拟合环绕xq的邻域内的训练样例。(可以使用归纳学习等方法）然后用这个逼近来计算 的值，也就是为查询实例估计的目标值输出。然后， 的描述被删除，因为对于每一个独立的查询实例都会计算不同的局部逼近。2022/10/4248.3.1局部加权线性回归(2/3) 修改这个过程来推导出局部逼近方法是:重新定义误差准则E以着重于拟合局部训练样例。下面给出了三种可能的误差准则。1)只对在k个近邻上的误差平方最小化:2)使整个训练样例集合D上的误差平方最小化，但对每个训练样例加权，权值为关于相距xq

12、距离的某个递减函数K:3)综合1和2:2022/10/4258.3.1局部加权线性回归(3/3) 使用上面的准则3，并使用与第4章相同的推理方式重新推导梯度下降法则，可以得到以下训练法则: 注意，这个新的法则和全局逼近给出的法则的差异是:实例x对权值更新的贡献现在乘上了一个距离惩罚项K( d(xq，x)仅对k个最邻近的训练实例的误差求和。2022/10/4278.4径向基函数（1/7） 在使用径向基函数方法中，最常用所待学习的假设是一个以下形式的函数: 其中，每个xu是X中一个实例，核函数K（ d(xu，x)被定义为随距离d(xu，x) 的增大而减小。这里的k是用户提供的常量，用来指定要包含的

13、核函数的数量。尽管 是对f(x)的全局逼近，但来自每个Ku(d(xu,x) 项的贡献被局部化到点xu附近的区域。2022/10/428 一种很常见的做法是选择每个核函数Ku（d(xu，x)为高斯函数,高斯函数的中心点为xu，方差是 。每个核函数Ku（d(xu，x)取为高斯函数时，函数：能够以任意小的误差逼近任何函数，只要高斯的核数量足够大，并且可以分别制定每个核的宽度。8.4径向基函数（2/7）2022/10/4298.4径向基函数（3/7）函数：可以被看作是描述了一个两层的网络：第一层计算不同的Ku（d(xu，x) 第二层计算第一层单元值的线性组合。2022/10/4308.4径向基函数（4

14、/7） 输入第一步选取xu和 ，按下式计算： 使用 ，训练wu：下图画出了一个径向基函数(RRF)网络的例子。2022/10/4318.4径向基函数（5/7） 人们已经提出了几种方法来选取适当的隐藏单元或者说核函数的数量。第一种方法是为每一个训练样例分配一个高斯核函数，此高斯核函数的中心点被设为xi。所有高斯函数的宽度2可被赋予同样的值。选择核函数的一个优点是它允许RBF网络精确地拟合训练数据。即，对于任意m个训练样例集合，合并m个高斯核函数的权值w0 wm可以被设置为使得对于每一个训练样例都满足 ，此时也可以有m个输出。 2022/10/4328.4径向基函数（6/7）第二种方法是选取一组数

15、量少于训练样例数量的核函数。这种方法在训练样例的数量巨大的时候比第一种方法更有效。核函数被分布在整个实例空间X上，它们的中心之间有均匀的间隔。或者，也可以非均匀地分布核函数中心，特别是在实例本身在X上非均匀分布的时候。或者，先求出训练样例的原始聚类，然后以每个聚类为中心加入一个核函数。第6.12.1节讨论的EM算法提供了一种从k个高斯函数的混合中选择均值，以最佳拟合观测到实例的方法。2022/10/4338.4径向基函数（7/7）用多个局部核函数的线性组合表示的径向基函数网络提供了一种目标函数的全局逼近。仅当输入x落入某个核函数的中心和宽度所定义的区域内时，这个核函数的值才是不可忽略的。因此，

16、RBF网络可以被看作目标函数的多个局部逼近的平滑线性组合。RBF网络的一个重要优点是，与反向传播算法训练的前馈网络相比，它的训练更加高效。这是因为RBF网络的输入层和输出层可以被分别训练。RBF网络是一种积极的学习方法。2022/10/4348.5基于案例的推理（1/6）k一近邻算法和局部加权回归都是基于实例的方法，它们具有三个共同的关键特性。第一，是消极学习方法，都把在训练数据之外的泛化推迟至遇到一个新的查询实例时才进行。第二，通过分析相似的实例来分类新的查询实例，而忽略与查询极其不同的实例。第三，把实例表示为n维欧氏空间中的实数点。基于案例的推理(case-based reasoning,

17、 CBR) 基于前两个原则，但不包括第3个原则。在CBR中，一般使用更丰富的符号描述来表示实例;相应地，用来检索实例的方法也更加复杂。2022/10/4358.5基于案例的推理（2/6） 考虑基于案例的推理系统的一个例子。2022/10/4368.5基于案例的推理（3/6） 2022/10/4378.5基于案例的推理（4/6） 给定新设计问题的功能说明，CADET从它的案例库中搜索存储的案例，使它的功能描述和新设计问题相匹配。如果发现了一个精确的匹配，那么可以返回这个案例作为新设计问题的建议方案。如果没有发现精确的匹配，CADET可能找到匹配所需功能的不同子图的案例。使它匹配设计规格说明的相应

18、部分。通过检索匹配不同子图的多个案例，有时可以拼接得到整个设计。一般来说，从多个检索到的案例产生最终方案的过程可能很复杂。需要从头设计系统的各个部分，也可能需要回溯以前的设计子目标，从而丢弃前面检索到的案例。系统还可以根据领域或一般知识加工原始的功能说明图，产生等价的子图以匹配更多的案例。如：A B重写为：A x B2022/10/4388.5基于案例的推理（5/6）基于案例的推理系统与k一近邻方法的区别:实例或案例可以用丰富的符号描述表示，就像CADET中使用的功能图。这需要不同于欧氏距离的相似性度量，比如两个功能图的最大可共享子图的大小。检索到的多个案例可以合并形成新问题的解决方案。这与k

19、一近邻方法相似多个相似的案例用来构成对新查询的回答。然而，合并多个检索到的案例的过程与k一近邻有很大不同，它依赖于知识推理，而不是统计方法。案例检索、基于知识的推理和问题求解间是紧密藕合在一起的。例如CADET系统在尝试找到匹配的案例过程中，它使用有关物理感应的一般知识重写了功能图。案例检索和合并过程依赖于知识推理和搜索密集的问题求解方法。2022/10/4398.5基于案例的推理（6/6）目前关于基于案例的推理研究的一个课题是改进索引案例的方法。基于案例的推理中心问题是句法相似度量(例如，功能图之间的子图同构)仅能近似地指出特定案例与特定问题的相关度。当CBR系统试图复用检索到的案例时，它可

20、能遇到句法相似度量中没有捕捉到的难点。此时，CBR系统可回溯搜索另外的案例以适应现有的案例，或者求助于其他的问题求解方法。2022/10/4408.6对消极学习和积极学习的评论(1/4)三种消极学习(lazy learning)方法:k一近邻算法、局部加权回归和基于案例的推理。之所以称这些方法是消极的，是因为它们延迟了如何从训练数据中泛化的决策，直到遇到一个新的查询案例时才进行。一种积极学习方法:学习径向基函数网络的方法。之所以称这种方法是积极的(eager)，是因为它在见到新的查询之前就做好了泛化的工作在训练时提交了定义其目标函数逼近的网络结构和权值。根据同样的理解，本书其他章节讨论的所有其

21、他算法都是积极学习算法(例如，反向传播算法、C4.5 )。2022/10/4418.6对消极学习和积极学习的评论(2/4)在算法能力方面，消极方法和积极方法有重要两种差异:计算时间的差异和对新查询的分类差异。在计算时间方面：消极方法在训练时一般需要较少的计算，但在预测新查询的目标值时需要更多的计算时间。积极方法正好相反。在新查询的分类方面：消极方法在决定如何从训练数据D中泛化时考虑查询实例xq；积极方法不能做到这一点，因为在见到查询实例xq前，它们已经选取了对目标函数的(全局)逼近。2022/10/4428.6对消极学习和积极学习的评论(3/4)对学习器的泛化精度的影响如果要求消极的和积极的学

22、习器采用同一个假设空间H，那么答案是肯定的。消极的学习器可以通过很多局部逼近的组合(隐含地)表示目标函数。积极的学习器必须在训练时提交单个的全局逼近。积极学习和消极学习之间的差异意味着对目标函数的全局逼近和局部逼近的差异。2022/10/4438.6对消极学习和积极学习的评论(4/4)使用多个局部逼近的积极方法（如RBF)，可以产生与消极方法（局部加权回归）的局部逼近同样的效果吗? 消极学习方法可以对于每一个查询实例选择不同的假设(或目标函数的局部逼近)。使用同样假设空间的积极方法是更加受限制的，因为它们必须提交一个覆盖整个实例空间的单一假设。当然，积极的方法可以使用合并了多个局部逼近的假设空间，就像RBF网络可以被看作是对这个目标的尝试。RBF学习方法是在训练时提交目标函数全局逼近的积极方法。2022/10/4448.7小结 (1)基于实例的学习方法不同于其他的函数逼近方法，因为它们推迟处理训练样例，直到必须分类一个新查询实例