第8章 基于实例的学习

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译者：曾华军等讲者：陶晓鹏7k-近邻算法•k-近邻算法是最基本的基于实例的学习方法•k-近邻算法假定所有的实例对应于n维空间Rn中的点，任意的实例表示为一个特征向量a1(x),...,an(x)•根据欧氏距离定义实例的距离。两个实例xi和xj的距离d(xi,xj)定义为•在最近邻学习中，目标函数值可以是离散的也可以是连续的，本节先考虑离散的情况。nrjrirjixaxaxxd12)()(),(2003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏8k-近邻算法（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表示–返回–其中kiiVvqxfvxf1))(,(maxarg)(ˆbababa01),(2003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏9k-近邻算法（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译者：曾华军等讲者：陶晓鹏10k-近邻算法（4）•离散的k-近邻算法作简单修改后可用于逼近连续值的目标函数。即计算k个最接近样例的平均值，而不是计算其中的最普遍的值，为逼近f:RnR，计算式如下：kxfxfkiiq1)()(ˆ2003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏11距离加权最近邻算法•对k-近邻算法的一个改进是对k个近邻的贡献加权，越近的距离赋予越大的权值，比如：•为了处理查询点xq恰好匹配某个训练样例xi，从而导致d(xq,xi)2为0的情况，令这种情况下的等于f(xi)，如果有多个这样的训练样例，我们使用它们占多数的分类•也可以用类似的方式对实值目标函数进行距离加权，用下式替代表8-1中的计算式，wi的定义与前相同kiiiVvqxfvwxf1))(,(maxarg)(2),(1iqixxdw)(qxfkiikiiiqwxfwxf11)()(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的值，使得学习算法的真实分类错误率最小化–这个真实错误率可以使用交叉验证来估计–可以多次重复这个处理过程，使得加权因子的估计更加准确•另一种更强有力的方法是从实例空间中完全消除最不相关的属性，等效于设置某个缩放因子为02003.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，当时我们感兴趣的是目标函数的全局逼近，即得到的梯度下降训练法则是)(...)()(ˆ110xawxawwxfnnDxxfxfE2))(ˆ)((21Dxjjxaxfxfw)())(ˆ)((2003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏20局部加权线性回归（2）•三种重新定义误差准则E，以着重于拟合局部训练样例，记为E(xq)–只对在k个近邻上的误差平方最小化–使整个训练样例集合D上的误差平方最小化，但对每个训练样例加权，权值为关于相距xq距离的某个递减函数K–综合1和2个近邻的kxxqqxfxfxE21))(ˆ)((21)(DxqqxxdKxfxfxE)),(())(ˆ)((21)(22个近邻的kxxqqqxxdKxfxfxE)),(())(ˆ)((21)(222003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏21局部加权线性回归（3）•准则2或许最令人满意，但所需的计算量随着训练样例数量线性增长•准则3很好地近似了准则2，并且具有如下优点：计算开销独立于训练样例总数，仅依赖于最近邻数k•对应准则3的梯度下降法则是个近邻的kxxjqiqxaxfxfxxdKw)())(ˆ)())(,((2003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏22局部加权回归的说明•大多数情况下，通过一个常量、线性函数或二次函数来局部逼近目标函数，更复杂的函数形式不太常见，原因是：–对每个查询实例用更复杂的函数来拟合，其代价十分高昂–在足够小的实例空间子域上，使用这些简单的近似已能很好地模拟目标函数2003.12.18机器学习-基于实例的学习作者：Mitchell译者：曾华军等讲者：陶晓鹏23径向基函数•径向基函数是另一种实现函数逼近的方法，它与距离加权回归和人工神经网络都有着紧