8基于实例的学习

1概述•已知一系列的训练样例，许多学习方法为目标函数建立起明确的一般化描述，•基于实例的学习方法只是简单地把训练样例存储起来，从这些实例中泛化的工作被推迟到必须分类新的实例时•每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例2概述（2）•基于实例的学习方法包括：–假定实例可以表示成欧氏空间中的点•最近邻法•局部加权回归法–对实例采用更复杂的符号表示•基于案例的推理•基于实例的学习方法有时被称为消极学习法，它把处理工作延迟到必须分类新的实例时•这种延迟的学习方法有一个优点：不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计3k-近邻算法•k-近邻算法是最基本的基于实例的学习方法•k-近邻算法假定所有的实例对应于n维空间Rn中的点，任意的实例表示为一个特征向量a1(x),...,an(x)•根据欧氏距离定义实例的距离。两个实例xi和xj的距离d(xi,xj)定义为nrjrirjixaxaxxd12)()(),(4k-近邻算法（2）•考虑离散目标函数f:RnV，V={v1,...,vs}•逼近离散值函数f:RnV的k-近邻算法–训练算法•将每个训练样例x,f(x)加入到列表training_examples–分类算法•给定一个要分类的查询实例xq–在training_examples中选出最靠近xq的k个实例，并用x1...xk表示–返回1ˆ()argmax(,())1(,)0kqivVifxvfxababab其中5k-近邻算法（3）6k-近邻算法（4）•离散的k-近邻算法作简单修改后可用于逼近连续值的目标函数。即计算k个最接近样例的平均值，而不是计算其中的最普遍的值，为逼近f:RnR，计算式如下：kxfxfkiiq1)()(ˆ7距离加权最近邻算法•对k-近邻算法的一个改进是对k个近邻的贡献加权，越近的距离赋予越大的权值，比如：1112()()argmax(,())()1(,)kiikiqiiqkvViiiiqiwfxfxwvfxfxwwdxx或8距离加权最近邻算法（2）•k-近邻算法的所有变体都只考虑k个近邻用以分类查询点，如果使用按距离加权，那么可以允许所有的训练样例影响xq的分类，因为非常远的实例的影响很小•考虑所有样例的唯一不足是会使分类运行得更慢•如果分类一个新实例时，考虑所有的训练样例，我们称为全局法；如果仅考虑靠近的训练样例，称为局部法9对k-近邻算法的说明•距离加权的k-近邻算法对训练数据中的噪声有很好的健壮性，通过取k个近邻的加权平均，可以消除孤立的噪声样例的影响•k-近邻的归纳偏置是：一个实例的分类xq与在欧氏空间中它附近的实例的分类相似•k-近邻方法的一个实践问题：维度灾害–k-近邻方法中实例间的距离是根据实例的所有属性计算的–实例间距离会被大量的不相关属性所支配，可能导致相关属性的值很接近的实例相距很远10对k-近邻算法的说明（2）•维度灾害的解决方法：对属性加权，相当于按比例缩放欧氏空间中的坐标轴，缩短对应不太相关的属性的坐标轴，拉长对应更相关属性的坐标轴•每个坐标轴应伸展的数量可以通过交叉验证的方法自动决定，具体做法如下：–假定使用因子zj伸展第j个根坐标轴，选择各个zj的值，使得学习算法的真实分类错误率最小化–这个真实错误率可以使用交叉验证来估计–可以多次重复这个处理过程，使得加权因子的估计更加准确•另一种更强有力的方法是从实例空间中完全消除最不相关的属性，等效于设置某个缩放因子为011对k-近邻算法的说明（3）•k-近邻算法的另外一个实践问题：如何建立高效的索引。•k-近邻算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量的计算•已经开发了很多对存储的训练样例进行索引的方法，以便能高效地确定最近邻•kd-tree把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的节点内，通过测试新查询xq的选定属性，树的内部节点把查询xq排列到相关的叶结点12局部加权回归•前面描述的最近邻方法可以被看作在单一的查询点x=xq上逼近目标函数f(x)•局部加权回归是上面方法的推广，它在环绕xq的局部区域内为目标函数f建立明确的逼近•局部加权回归使用附近的或距离加权的训练样例来形成对f的局部逼近•例如，使用线性函数、二次函数、多层神经网络在环绕xq的邻域内逼近目标函数•局部加权回归的名称解释–局部：目标函数的逼近仅仅根据查询点附近的数据–加权：每个训练样例的贡献由它与查询点间的距离加权得到–回归：表示逼近实数值函数的问题13局部加权回归（2）•给定一个新的查询实例xq，局部加权回归的一般方法是：–建立一个逼近，使拟合环绕xq的邻域内的训练样例–用计算的值–删除的描述fˆ)(ˆqxffˆfˆfˆ14局部加权线性回归•使用如下形式的线性函数来逼近xq邻域的目标函数f•第4章我们讨论了梯度下降方法，在拟合以上形式的线性函数到给定的训练集合时，它被用来找到使误差最小化的系数w0...wn，当时我们感兴趣的是目标函数的全局逼近，即得到的梯度下降训练法则是)(...)()(ˆ110xawxawwxfnnDxxfxfE2))(ˆ)((21Dxjjxaxfxfw)())(ˆ)((15局部加权线性回归（2）•三种重新定义误差准则E，以着重于拟合局部训练样例，记为E(xq)–只对在k个近邻上的误差平方最小化–使整个训练样例集合D上的误差平方最小化，但对每个训练样例加权，权值为关于相距xq距离的某个递减函数K–综合1和2个近邻的kxxqqxfxfxE21))(ˆ)((21)(DxqqxxdKxfxfxE)),(())(ˆ)((21)(22231ˆ()(()())((,))2qqqxxkExfxfxKdxx的个近邻16局部加权线性回归（3）•准则2或许最令人满意，但所需的计算量随着训练样例数量线性增长•准则3很好地近似了准则2，并且具有如下优点：计算开销独立于训练样例总数，仅依赖于最近邻数k•对应准则3的梯度下降法则是个近邻的kxxjqiqxaxfxfxxdKw)())(ˆ)())(,((17径向基函数18径向基函数（2）•给定了目标函数的训练样例集合，一般分两个阶段来训练RBF网络–决定隐藏单元的数量k，并通过定义核函数中心点和方差来定义每个隐藏单元–使用全局误差准则来训练权值wu，使网络拟合训练数据程度最大化19径向基函数（3）•已经提出了几种方法来选取适当的隐藏单元或核函数的数量–为每一个训练样例xi,f(xi)分配一个高斯核函数，中心点设为xi，所有高斯函数的宽度可被赋予同样的值•RBF网络学习目标函数的全局逼近，其中每个训练样例xi,f(xi)都只在xi的邻域内影响的值•这种核函数的一个优点是允许RBF网络精确地拟合训练数据•对于任意m个训练样例集合，合并m个高斯核函数的权值w0...wm，可以被设置为使得对于每个训练样例xi,f(xi)都满足)(ˆixf)()(ˆiixfxf20径向基函数（4）–选取一组数量少于训练样例数量的核函数，这种方法更有效，特别是训练样例数量巨大时•核函数分布在整个实例空间X上，它们中心之间有均匀的间隔•或者也可以非均匀地分布核函数中心，特别是在实例本身在X上非均匀分布的时候–可以随机选取训练样例的一个子集作为核函数的中心，从而对实例的基准分布进行采样–或者可以标识出实例的原始聚类，然后以每个聚类为中心加入一个核函数»把训练实例拟合到混合高斯，6.12.1节讨论的EM算法提供了一种从k个高斯函数的混合中选择均值，以最佳拟合观察到实例的方法21径向基函数（5）•总而言之，用多个局部核函数的线性组合表示的径向基函数网络提供了一种目标函数的全局逼近•仅当输入落入某个核函数的中心和宽度所定义的区域时，这个核函数的值才是不可忽略的•RBF网络可以被看作目标函数的多个局部逼近的平滑线性组合•RBF网络的一个优点是，与反向传播算法训练的前馈网络相比，它的训练更加高效，这是因为RBF网络的输入层和输出层可以被分别训练22基于案例的推理•k-近邻算法和局部加权回归具有三个共同的关键特性：–消极学习方法–通过分析相似的实例来分类新的查询实例，而忽略与查询极其不同的实例–实例表示为n维欧氏空间中的实数点•基于案例的推理（CBR）满足前2个原则，但不满足第3个•CBR使用更丰富的符号描述来表示实例，用来检索实例的方法也更加复杂23基于案例的推理（2）•CBR已被用于解决很多问题–根据数据库中存储的以前的设计图纸，来进行机械设备的总体设计–根据以前的裁决来对新的法律案件进行推理–通过对以前的相似问题的解决方案的复用或合并，解决规划和调度问题24基于案例的推理（3）•一个例子：CADET系统采用基于案例的推理来辅助简单机械设备的总体设计（图8-3）–条件•使用一个数据库，其中包含大约75个以前的设计或设计片断•内存中每一个实例是通过它的结构和定性的功能来表示的，新的设计问题通过所要求的功能和结构来表示–方法•给定新设计问题的功能说明，CADET从它的案例库中搜索存储的案例，使它的功能描述和新设计问题相匹配–如果发现了一个精确的匹配，表明某个存储案例精确地实现了所要求的功能，那么可以返回这个案例作为新设计问题的建议方案–否则，CADET可能找到匹配所需功能的不同子图的案例»在两个功能图间搜索同构子图，以发现一个案例的某部分，使它匹配更多的案例»加工原始的功能说明图，产生等价的子图以匹配更多的案例2526基于案例的推理（4）•通过检索匹配不同子图的多个案例，有时可以拼接得到整个设计•但是，从多个检索到的案例产生最终方案的过程可能很复杂–为了合并存储案例中检索到的部分，可能需要从头设计系统的各个部分，也可能需要回溯以前的设计子目标，从而丢弃前面检索到的案例•CADET合并和自适应已检索到案例并形成最终设计的能力有限，它主要依赖用户来做自适应阶段的处理27基于案例的推理（5）•CADET的问题框架–在CADET中每个存储的训练样例描绘了一个功能图以及实现该功能的结构–实例空间定义为所有功能图的空间，目标函数f映射到实现这些功能的结构–每个存储训练样例x,f(x)是一个序偶，描述某个功能图x和实现x的结构f(x)–系统通过学习训练样例，以输出满足功能图查询输入xq的结构f(xq)28基于案例的推理（6）•CADET系统区别于k-近邻方法的一般特征–实例（或称案例）可以用丰富的符号描述表示，因此可能需要不同于欧氏距离的相似性度量–检索到的多个案例可以合并形成新问题的解决方案，合并案例的过程与k-近邻方法不同，依赖于知识推理而不是统计方法–案例检索、基于知识的推理、问题求解是紧密耦合在一起的•概括而言，基于案例的推理是一种基于实例的学习方法，在这个方法中–实例可以是丰富的关系的描述–案例检索和合并过程可能依赖于知识推理和搜索密集的问题求解方法•一个研究课题：改进索引案例的方法–句法相似度量仅能近似地指出特定案例与特定问题的相关度，而不能捕捉其他难点，比如多个设计片断的不兼容性–发现这些难点后，可以回溯，并且可用来改进相似性度量29(publishedinTheKnowledgeEngineeringReview,Vol.9No.4,1994)对消极学习和积极学习的评价•本章考虑了三种消极学习方法：k-近邻、局部加权回归、基于案例的推理•本章考虑了一种积极学习方法：学习径向基函数网络的方法•消极方法和积极方法的差异：–计算时间的差异•消极算法在训练时需要较少的计算，但在预测