《机器学习基于实例的学习ppt课件》由会员分享，可在线阅读，更多相关《机器学习基于实例的学习ppt课件（46页珍藏版）》请在金锄头文库上搜索。
1、资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 第第8章章 基于实例的学习基于实例的学习8.18.1简介简介8.2 k8.2 k一近邻算法一近邻算法8.38.3局部加权回归局部加权回归8.48.4径向基函数径向基函数8.58.5基于案例的推理基于案例的推理8.68.6对消极学习和积极学习的评论对消极学习和积极学习的评论8.78.7小结和补充读物小结和补充读物2024/8/301资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 8.1简介（简介
2、（1/3）n思想：思想：基于实例的学习方法基于实例的学习方法先把训练样例存储起来。泛化的先把训练样例存储起来。泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。此把一个目标函数值赋给新实例。n基于实例的学习方法有时被称为基于实例的学习方法有时被称为消极消极(lazy)(lazy)学习法，因为它学习法，因为它们把处理工作延迟到必须分类新的实例时。与其相对的方法称们把处理工作延迟到必须分类新的实例时
3、。与其相对的方法称为积极的（为积极的（eager)eager)。n延迟的或消极的学习方法有一个延迟的或消极的学习方法有一个关键的优点关键的优点，即它们不是在，即它们不是在整个实例空间上一次性地估计目标函数，而是针对每个待分类整个实例空间上一次性地估计目标函数，而是针对每个待分类新实例作出局部的和相异的估计。新实例作出局部的和相异的估计。2024/8/302资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.1简介（简介（2/3）n基于实例的学习方法基于实例的学习方法包括最近邻法包括最近邻法(nearest (neare
4、st neighbor NN)neighbor NN) 和局部加权回归和局部加权回归(locally (locally weighted regression LWR)weighted regression LWR)法法，它们都假定实，它们都假定实例可以被表示为欧氏空间中的点。例可以被表示为欧氏空间中的点。n基于实例的学习方法基于实例的学习方法还包括基于案例的推理还包括基于案例的推理(case-based reasoning CBR(case-based reasoning CBR）它对实例采用）它对实例采用更复杂的符号表示。更复杂的符号表示。2024/8/303资金是运动的价值，资金的价值是
5、随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 8.1简介（简介（3/3）n基于实例方法的基于实例方法的一个不足一个不足是，分类新实例的开销可能很大。是，分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以如何到训练样例时。所以如何有效地索引训练样例有效地索引训练样例，以减少查询时，以减少查询时所需的计算是一个重要的实践问题。所需的计算是一个重要的实践问题。n第二个不足第二个不足是是( (尤其对于最近邻法尤其对于最近邻法) )，当从存储器中检索相似
6、，当从存储器中检索相似的训练样例时，它们一般考虑实例的的训练样例时，它们一般考虑实例的所有属性所有属性。如果目标概念。如果目标概念仅依赖于很多属性中的几个时，那么真正最仅依赖于很多属性中的几个时，那么真正最“相似相似”的实例之的实例之间很可能相距甚远间很可能相距甚远。2024/8/304资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 8.2 k一近邻算法（一近邻算法（1/5）nk k一近邻算法一近邻算法假定假定所有的实例对应于所有的实例对应于n n维空间维空间R Rn n中的点。中的点。n一个实例的一个实例的最近邻最
7、近邻是根据是根据标准欧氏距离标准欧氏距离定义的。即把任意实定义的。即把任意实例例x x表示为下面的表示为下面的特征向量特征向量: : a (x) 其中其中,a,ar r(x)(x)表示实例表示实例x x的第的第r r个属性值。个属性值。那么，两个实例那么，两个实例x xi i和和x xj j 间的距离间的距离定义为定义为d(xd(xi i,x,xj j) )，其中，其中: :2024/8/305资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值逼近离散值函数逼近离散值函数 的的k-近邻算法近邻算法 KNN训练算法训练算法
8、: : 对于每个训练样例对于每个训练样例，把这个样例加人列表，把这个样例加人列表training_examplestraining_examples。分类算法分类算法: :n给定一个要分类的查询实例给定一个要分类的查询实例x xq q。n在在training _ examplestraining _ examples中中选出最靠近选出最靠近x xq q的的k k个实例个实例，并用，并用x x1 1，x xk k表示。表示。n返回返回 其中，如果其中，如果a=b,a=b,那么那么 (a(a，b)=lb)=l，否则，否则 (a(a，b)=0b)=0。 就是距离就是距离x xq q最近的最近的k k
9、个训练样例中个训练样例中最普遍的最普遍的分分f f值。值。 2024/8/306资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2 k一近邻算法（一近邻算法（2/5） 下图图解了一种简单情况下的下图图解了一种简单情况下的k k一近邻算法一近邻算法，在这里实例是，在这里实例是二维空间中的点，目标函数具有布尔值。正反训练样例用二维空间中的点，目标函数具有布尔值。正反训练样例用“+ +”和和“- -”分别表示。图中也画出了一个查询点分别表示。图中也画出了一个查询点x xq q 。1 1一近邻算法一近邻算法把把x xq q
10、分类为正例，然而分类为正例，然而5 5一近邻算法一近邻算法把把x xq q分类为反例。分类为反例。2024/8/307资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2 k一近邻算法（一近邻算法（3/5） k-k-近邻算法隐含考虑的近邻算法隐含考虑的假设空间假设空间H H的特性的特性: :nk-k-近邻算法近邻算法并不形成关于目标函数并不形成关于目标函数f f的明确的一般假的明确的一般假设设。它仅在需要时计算每个新查询实例的分类。它仅在需要时计算每个新查询实例的分类。n隐含的一般函数隐含的一般函数是什么是什么? ?
11、或者说，如果保持训练样例或者说，如果保持训练样例不变，并用不变，并用X X中的每个可能实例查询算法，会得到什么中的每个可能实例查询算法，会得到什么样的分类样的分类? ?2024/8/308资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2 k一近邻算法（一近邻算法（4/5） 下图画出了下图画出了1 1一近邻算法一近邻算法在整个实例空间上导致的决策面形在整个实例空间上导致的决策面形状。状。决策面是围绕每个训练样例的凸多边形的合并。决策面是围绕每个训练样例的凸多边形的合并。对于每个对于每个训练样例，多边形指出了一个查询
12、点集合，它的分类完全由相训练样例，多边形指出了一个查询点集合，它的分类完全由相应训练样例决定。在这个多边形外的查询点更接近其他的训练应训练样例决定。在这个多边形外的查询点更接近其他的训练样例。这种类型的图经常被称为这个训练样例集合的样例。这种类型的图经常被称为这个训练样例集合的VoronoiVoronoi图图（梯森多边形）。（梯森多边形）。2024/8/309资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2 k一近邻算法（一近邻算法（5/5） 对对k k一近邻算法作简单的修改，它可被用于一近邻算法作简单的修改，它
13、可被用于逼近逼近连续值连续值的目标函数。让算法计算的目标函数。让算法计算k k个最接近样例的个最接近样例的平平均值均值，而不是计算其中的最普遍的值。更精确地讲，而不是计算其中的最普遍的值。更精确地讲，为了逼近一个实值目标函数为了逼近一个实值目标函数 ，我们使用公我们使用公式式: :2024/8/3010资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.1距离加权最近邻算法距离加权最近邻算法（1/3） 对对k k一近邻算法的一个一近邻算法的一个改进改进是对是对k k个近邻的贡献加权个近邻的贡献加权，根据它们，根据它
14、们相对查询点相对查询点x xq q的距离，将较大的权值赋给较近的近邻。的距离，将较大的权值赋给较近的近邻。n在在逼近离散目标函数的算法中逼近离散目标函数的算法中，可以根据每个近邻与，可以根据每个近邻与x xq q的距离平的距离平方的倒数加权这个近邻的方的倒数加权这个近邻的“选举权选举权”: : 当当x xq q=x=xi i ，将导致分母，将导致分母d(xd(xq q x xi i) )2 2为为0 0，此时令，此时令 。如果。如果有多个这样的训练样例，我们使用它们中占多数的分类。有多个这样的训练样例，我们使用它们中占多数的分类。2024/8/3011资金是运动的价值，资金的价值是随时间变化而
15、变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.1距离加权最近邻算法距离加权最近邻算法（2/3）n对对实值目标函数实值目标函数进行距离加权，用下式：进行距离加权，用下式： 其中，其中，w wi i的定义与前式中相同。注意该式中的分母是一个常量，的定义与前式中相同。注意该式中的分母是一个常量，它将不同权值的贡献归一化它将不同权值的贡献归一化( (例如，它保证如果对所有的训练样例如，它保证如果对所有的训练样例例x xi i，f(xf(xi i) )c c，那么，那么， 。2024/8/3012资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，
16、随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.1距离加权最近邻算法距离加权最近邻算法（3/3）n注意注意，以上，以上k k一近邻算法的所有变体都只考虑一近邻算法的所有变体都只考虑k k个近邻个近邻用以分用以分类查询点。可以考虑类查询点。可以考虑所有的所有的训练样例影响训练样例影响 的分类，的分类，因为非常远的实例对其影响很小。考虑所有样例的惟一因为非常远的实例对其影响很小。考虑所有样例的惟一不足不足是会使分类运行得更慢。是会使分类运行得更慢。n如果分类一个新的查询实例时考虑所有的训练样例，我们称如果分类一个新的查询实例时考虑所有的训练样例，我们称它为它为全局全局(glob
17、al)(global)法法。n如果仅考虑最靠近的训练样例，我们称它为如果仅考虑最靠近的训练样例，我们称它为局部局部(local)(local)法法。n当式当式(8.4)(8.4)（前式）的法则被应用为全局法时，它被称为（前式）的法则被应用为全局法时，它被称为ShepardShepard法法。2024/8/3013资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.2对对k-近邻算法的说明（近邻算法的说明（1/6）n 按距离加权的按距离加权的k k一近邻算法是一种非常有效的一近邻算法是一种非常有效的归纳推归纳推理理方
18、法。方法。它对训练数据中的噪声有很好的健壮性它对训练数据中的噪声有很好的健壮性，而，而且当给定足够大的训练集合时也非常有效。且当给定足够大的训练集合时也非常有效。注意注意，通，通过取过取k k个近邻的加权平均，可以消除孤立的噪声样例的个近邻的加权平均，可以消除孤立的噪声样例的影响。影响。nk k一近邻算法的一近邻算法的归纳偏置对应于假定归纳偏置对应于假定: :一个实例的分类一个实例的分类x xq q与在欧氏空间中它附近的实例的分类相似与在欧氏空间中它附近的实例的分类相似。2024/8/3014资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金
19、就是原有资金的时间价值8.2.2对对k-近邻算法的说明（近邻算法的说明（2/6）n应用应用k k一近邻算法的一个一近邻算法的一个实践问题是实践问题是，实例间的距离，实例间的距离是根据实例的所有属性是根据实例的所有属性( (也就是包含实例的欧氏空间也就是包含实例的欧氏空间的所有坐标轴的所有坐标轴) )计算的。计算的。n考虑把考虑把k k一近邻算法应用到这样一个问题一近邻算法应用到这样一个问题: : 每个实例每个实例由由2020个属性描述，但在这些属性中个属性描述，但在这些属性中仅有仅有2 2个与它的分个与它的分类有关类有关。在这种情况下，这两个相关属性的值一致。在这种情况下，这两个相关属性的值一
20、致的实例可能在这个的实例可能在这个2020维的实例空间中相距很远。结维的实例空间中相距很远。结果，依赖这果，依赖这2020个属性的相似性度量会个属性的相似性度量会误导误导k k一近邻算一近邻算法的分类。法的分类。2024/8/3015资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.2对对k-近邻算法的说明（近邻算法的说明（3/6）n近邻间的距离会被大量的不相关属性所支配。这种近邻间的距离会被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题，有时被称为由于存在很多不相关属性所导致的难题，有时被称为维
21、度灾难维度灾难(curse of dimensionality)(curse of dimensionality)最近邻方法对最近邻方法对这个问题特别敏感。这个问题特别敏感。n解决解决维度问题维度问题的的一个有趣的方法一个有趣的方法是，当计算两个实是，当计算两个实例间的距离时，例间的距离时，对每个属性加权对每个属性加权。这相当于。这相当于按比例缩按比例缩放欧氏空间中的坐标轴放欧氏空间中的坐标轴，缩短对应于不太相关的属性，缩短对应于不太相关的属性的坐标轴，拉长对应于更相关的属性的坐标轴。每个的坐标轴，拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的量可以通过坐标轴应伸展的量可以通过交叉验证交叉
22、验证的方法自动决定。的方法自动决定。2024/8/3016资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.2对对k-近邻算法的说明（近邻算法的说明（4/6）具体做法如下：具体做法如下：n首先首先，假定，假定使用加权因子使用加权因子z zj j，伸展，伸展( (乘乘) )第第j j个根坐标轴，选择个根坐标轴，选择z zj j的各个值的各个值z z1 1 z zn n ，以使学习算法的真实分类错误率最小化。，以使学习算法的真实分类错误率最小化。n其次其次，这个真实错误率可以使用交叉验证来估计。，这个真实错误率可以使
23、用交叉验证来估计。n交叉验证交叉验证: :随机选取现有数据的一个子集作为训练样例，然后随机选取现有数据的一个子集作为训练样例，然后决定决定z z1 1 z zn n 的值使剩余样例的分类错误率最小化。通过多次的值使剩余样例的分类错误率最小化。通过多次重复这个处理过程，可以使加权因子的估计更加准确。这种伸重复这个处理过程，可以使加权因子的估计更加准确。这种伸展坐标轴以优化展坐标轴以优化k k一近邻算法的过程，提供了一种一近邻算法的过程，提供了一种抑制无关属抑制无关属性影响性影响的机制的机制。2024/8/3017资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，
24、其增值的这部分资金就是原有资金的时间价值8.2.2对对k-近邻算法的说明（近邻算法的说明（5/6）另外一种更强有力的方法另外一种更强有力的方法n从实例空间中完全从实例空间中完全消除最不相关的属性消除最不相关的属性。这等效于设置某个缩。这等效于设置某个缩放因子放因子z zj j为为0 0。注意，上面的两种方法都可以被看作以某个常量因子伸展坐标注意，上面的两种方法都可以被看作以某个常量因子伸展坐标轴。轴。n另外一种可选的做法另外一种可选的做法是使用一个在实例空间上是使用一个在实例空间上变化的值变化的值伸展坐伸展坐标轴。这样增加了标轴。这样增加了算法重新定义距离度量的自由度算法重新定义距离度量的自由
25、度，然而也增，然而也增加了过度拟合的风险。所以，局部伸展坐标轴的方法是不太常加了过度拟合的风险。所以，局部伸展坐标轴的方法是不太常见的。见的。2024/8/3018资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.2对对k-近邻算法的说明（近邻算法的说明（6/6）n应用应用k k一近邻算法的另外一个一近邻算法的另外一个实践问题是实践问题是如何建立高如何建立高效的索引效的索引。因为。因为k k一近邻算法推迟所有的处理，直到接一近邻算法推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大收到一个新的查
26、询，所以处理每个新查询可能需要大量的计算。量的计算。n一种索引方法一种索引方法是是kd-treekd-tree，它把实例存储在树的叶结，它把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的结点内。通点内，邻近的实例存储在同一个或附近的结点内。通过测试新查询过测试新查询x xq q的选定属性，就可以把查询的选定属性，就可以把查询x xq q排列到相排列到相关的叶结点。关的叶结点。2024/8/3019资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.2.3术语注解n回归回归(Regression)(Regress
27、ion)的含义是的含义是逼近逼近一个实数值的目标一个实数值的目标函数。函数。n残差残差(Residual)(Residual)是逼近目标函数时的是逼近目标函数时的误差误差n核函数核函数(Kernel function)(Kernel function)是一个是一个距离函数距离函数，它用来，它用来决定每个训练样例的权值。换句话说，核函数就是使决定每个训练样例的权值。换句话说，核函数就是使 w wi i=K(d(x=K(d(xi i,x,xq q)的函数的函数K K。2024/8/3020资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有
28、资金的时间价值8.3局部加权回归（局部加权回归（1/2）n最近邻方法最近邻方法可以被看作可以被看作在单一的查询点在单一的查询点x= xx= xq q上逼近目标函数上逼近目标函数f(x)f(x)。（没有明确的目标函数，只有目标值）。（没有明确的目标函数，只有目标值）n局部加权回归局部加权回归是最近邻方法的推广。是最近邻方法的推广。它在环绕它在环绕x xq q的局部区域的局部区域内为目标函数内为目标函数f f建立建立明确的明确的逼近逼近。使用附近的或距离加权的训。使用附近的或距离加权的训练样例来形成这种对练样例来形成这种对f f的的局部逼近局部逼近。n可以使用线性函数、二次函数、多层神经网络或者其
29、他函数可以使用线性函数、二次函数、多层神经网络或者其他函数形成在环绕形成在环绕x xq q的邻域内逼近目标函数。的邻域内逼近目标函数。n“局部加权回归局部加权回归”名称中，名称中，“局部局部”是指目标函数的逼近仅是指目标函数的逼近仅仅根据查询点附近的数据仅根据查询点附近的数据; ; “加权加权”是指每一个训练样例的贡是指每一个训练样例的贡献是由它与查询点间的距离加权的献是由它与查询点间的距离加权的; ; “回归回归”表示逼近实数值表示逼近实数值函数。函数。2024/8/3021资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时
30、间价值8.3局部加权回归（局部加权回归（2/2） 给定一个新的查询实例，给定一个新的查询实例，局部加权回归的一般方局部加权回归的一般方法法是：是：n建立建立一个逼近一个逼近 ，使，使 拟合环绕拟合环绕x xq q的邻域内的训练样的邻域内的训练样例。例。( (可以使用归纳学习等方法）可以使用归纳学习等方法）n然后然后用这个逼近来计算用这个逼近来计算 的值，也就是为查询实例的值，也就是为查询实例估计的目标值输出。估计的目标值输出。n然后然后， 的描述被的描述被删除删除，因为对于每一个独立的查询实，因为对于每一个独立的查询实例都会计算不同的局部逼近。例都会计算不同的局部逼近。2024/8/3022资
31、金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.3.1局部加权线性回归局部加权线性回归(1/3) 使用如下形式的使用如下形式的线性函数线性函数来逼近来逼近x xq q邻域的目标函数邻域的目标函数f:f:a ai i(x)(x)表示实例表示实例x x的第的第i i个属性值。个属性值。 梯度下降方法中，感兴趣的是梯度下降方法中，感兴趣的是目标函数的全局逼近目标函数的全局逼近。权值选。权值选择方法是使训练集合择方法是使训练集合D D上的上的误差平方和最小化误差平方和最小化，即，即: :根据这个误差定义，我们得出了以下根据这
32、个误差定义，我们得出了以下梯度下降训练法则梯度下降训练法则: :2024/8/3023资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.3.1局部加权线性回归局部加权线性回归(2/3) 修改这个过程来推导出修改这个过程来推导出局部逼近局部逼近方法是方法是: :重新定义误差准则重新定义误差准则E E以着重于拟合局部训练样例。下面给出了以着重于拟合局部训练样例。下面给出了三种可能的误差准则三种可能的误差准则。1)1)只对在只对在k k个近邻上的误差平方最小化个近邻上的误差平方最小化: :2)2)使整个训练样例集合使整个训
33、练样例集合D D上的误差平方最小化，但对每个训练样例上的误差平方最小化，但对每个训练样例加权，权值为关于相距加权，权值为关于相距x xq q距离的某个递减函数距离的某个递减函数K:K:3)3)综合综合1 1和和2:2:2024/8/3024资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.3.1局部加权线性回归局部加权线性回归(3/3) 使用上面的准则使用上面的准则3 3，并使用与第，并使用与第4 4章相同的推理方式重新推章相同的推理方式重新推导梯度下降法则，可以得到以下导梯度下降法则，可以得到以下训练法则训练法则:
34、 : 注意注意，这个新的法则和全局逼近给出的法则的，这个新的法则和全局逼近给出的法则的差异差异是是: :n实例实例x x对权值更新的贡献现在乘上了一个对权值更新的贡献现在乘上了一个距离惩罚项距离惩罚项K( d(xK( d(xq q，x)x)n仅对仅对k k个最邻近的训练实例的误差求和个最邻近的训练实例的误差求和。2024/8/3025资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.3.2局部加权回归的说明n上面考虑了使用一个线性函数在查询实例上面考虑了使用一个线性函数在查询实例x xq q的邻域内逼近的邻域内逼近f
35、 f。n在局部加权回归的文献中，在在局部加权回归的文献中，在对训练样例距离加权对训练样例距离加权方面，还有方面，还有很多其他可选方法，还有很多目标函数局部逼近方法。很多其他可选方法，还有很多目标函数局部逼近方法。n通常使用通常使用一个常量、线性函数或二次函数一个常量、线性函数或二次函数来局部逼近目标函数，来局部逼近目标函数，一般不使用更复杂的函数，原因是一般不使用更复杂的函数，原因是: :(1)(1)对每个查询实例用更复杂的函数来拟合，其代价十分高昂对每个查询实例用更复杂的函数来拟合，其代价十分高昂; ;(2)(2)在足够小的实例空间子域上，使用这些简单的近似已能很好地在足够小的实例空间子域上
36、，使用这些简单的近似已能很好地模拟目标函数。模拟目标函数。2024/8/3026资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.4径向基函数（径向基函数（1/7） 在使用在使用径向基函数径向基函数方法中，最常用所待学习的假设是一方法中，最常用所待学习的假设是一个以下形式的函数个以下形式的函数: : 其中，每个其中，每个x xu u是是X X中一个实例，中一个实例，核函数核函数K K（ d(xd(xu u，x)x)被定义被定义为随距离为随距离d(xd(xu u，x) x) 的增大而减小。这里的的增大而减小。这里的k
37、k是用户提供的常是用户提供的常量，用来指定要包含的核函数的数量。量，用来指定要包含的核函数的数量。尽管尽管 是对是对f(x)f(x)的的全局逼近全局逼近，但来自每个，但来自每个K Ku u(d(x(d(xu,u,x) x) 项的贡献被局部化到点项的贡献被局部化到点x xu u附近的区域。附近的区域。2024/8/3027资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 一种很一种很常见的做法常见的做法是选择每个核函数是选择每个核函数K Ku u（d(xd(xu u，x)x)为高斯函数为高斯函数, ,高斯函数的中心点为高
38、斯函数的中心点为x xu u，方差是，方差是 。每个核函数每个核函数K Ku u（d(xd(xu u，x)x)取为高斯函数时，函数：取为高斯函数时，函数：能够以任意小的误差逼近任何函数能够以任意小的误差逼近任何函数，只要高斯的核数量，只要高斯的核数量足够大，并且可以分别制定每个核的宽度。足够大，并且可以分别制定每个核的宽度。8.4径向基函数（径向基函数（2/7）2024/8/3028资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.4径向基函数（径向基函数（3/7）函数：函数：可以被看作是可以被看作是描述了一个两层的
39、网络：描述了一个两层的网络：第一层计算不同的第一层计算不同的K Ku u（d(xd(xu u，x) x) 第二层计算第一层单元值的线性组合。第二层计算第一层单元值的线性组合。2024/8/3029资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.4径向基函数（径向基函数（4/7） 输入输入第一步选取第一步选取x xu u和和 ，按下式计算：，按下式计算： 使用使用 ，训练训练w wu u：下图画出了一个径向基函数下图画出了一个径向基函数(RRF)(RRF)网络的例子。网络的例子。2024/8/3030资金是运动的价值
40、，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.4径向基函数（径向基函数（5/7） 人们已经提出了几种方法来人们已经提出了几种方法来选取适当的隐藏单元或者说核函选取适当的隐藏单元或者说核函数的数量数的数量。n第一种方法第一种方法是为每一个训练样例是为每一个训练样例 x)分配一个高斯分配一个高斯核函数，此高斯核函数的中心点被设为核函数，此高斯核函数的中心点被设为x xi i。所有高斯函数的宽。所有高斯函数的宽度度 2 2可被赋予同样的值。可被赋予同样的值。n选择核函数的一个选择核函数的一个优点优点是它允许是它允许RBFRBF网络精确
41、地拟合训练数据。网络精确地拟合训练数据。即，对于任意即，对于任意m m个训练样例集合，合并个训练样例集合，合并m m个高斯核函数的权值个高斯核函数的权值w w0 0 w wm m可以被设置为使得对于每一个训练样例可以被设置为使得对于每一个训练样例 x)都满都满足足 ，此时也可以有，此时也可以有m m个输出。个输出。 2024/8/3031资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.4径向基函数（径向基函数（6/7）n第二种方法第二种方法是选取一组是选取一组数量少于训练样例数量数量少于训练样例数量的核函数。这种的
42、核函数。这种方法在训练样例的数量巨大的时候比第一种方法更有效。方法在训练样例的数量巨大的时候比第一种方法更有效。核函数被分布在整个实例空间核函数被分布在整个实例空间X X上上，它们的中心之间有均匀的，它们的中心之间有均匀的间隔。间隔。或者，或者，也可以非均匀地分布核函数中心，特别是在实例本身在也可以非均匀地分布核函数中心，特别是在实例本身在X X上非均匀分布的时候。上非均匀分布的时候。或者或者，先求出训练样例的原始聚类，然后以每个聚类为中心加，先求出训练样例的原始聚类，然后以每个聚类为中心加入一个核函数。入一个核函数。第第6.12.16.12.1节讨论的节讨论的EMEM算法算法提供了一种从提供
43、了一种从k k个高斯函数的混合中个高斯函数的混合中选择均值，以最佳拟合观测到实例的方法。选择均值，以最佳拟合观测到实例的方法。2024/8/3032资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.4径向基函数（径向基函数（7/7）n用多个局部核函数的线性组合用多个局部核函数的线性组合表示的径向基函数网络提供了表示的径向基函数网络提供了一种目标函数的一种目标函数的全局逼近全局逼近。仅当输入。仅当输入x x落入某个核函数的中心落入某个核函数的中心和宽度所定义的区域内时，这个核函数的值才是不可忽略的。和宽度所定义的区域内
44、时，这个核函数的值才是不可忽略的。因此，因此，RBFRBF网络可以被看作目标函数的多个局部逼近的平滑线网络可以被看作目标函数的多个局部逼近的平滑线性组合性组合。nRBFRBF网络的一个网络的一个重要优点重要优点是，与反向传播算法训练的前馈网是，与反向传播算法训练的前馈网络相比，它的训练更加高效。这是因为络相比，它的训练更加高效。这是因为RBFRBF网络的输入层和输网络的输入层和输出层可以被出层可以被分别分别训练。训练。nRBFRBF网络是一种网络是一种积极的积极的学习方法。学习方法。2024/8/3033资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值
45、的这部分资金就是原有资金的时间价值8.5基于案例的推理（基于案例的推理（1/6）nk k一近邻算法一近邻算法和和局部加权回归局部加权回归都是基于实例的方法，它们具有都是基于实例的方法，它们具有三个共同的三个共同的关键特性关键特性。第一第一，是，是消极学习消极学习方法，都把在训练数据之外的泛化推迟至遇方法，都把在训练数据之外的泛化推迟至遇到一个新的查询实例时才进行。到一个新的查询实例时才进行。第二第二，通过，通过分析相似的实例分析相似的实例来分类新的查询实例，而忽略与查来分类新的查询实例，而忽略与查询极其不同的实例。询极其不同的实例。第三第三，把，把实例表示实例表示为为n n维欧氏空间中的实数点
46、。维欧氏空间中的实数点。n基于案例的推理基于案例的推理(case-based reasoning, CBR) (case-based reasoning, CBR) 基于前两个原基于前两个原则，但不包括第则，但不包括第3 3个原则。在个原则。在CBRCBR中，一般使用更丰富的符号描中，一般使用更丰富的符号描述来表示实例述来表示实例; ;相应地，用来检索实例的方法也更加复杂。相应地，用来检索实例的方法也更加复杂。2024/8/3034资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.5基于案例的推理（基于案例的推理（2
47、/6） 考虑基于案例的推理系统的一个例子考虑基于案例的推理系统的一个例子。2024/8/3035资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.5基于案例的推理（基于案例的推理（3/6） 2024/8/3036资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.5基于案例的推理（基于案例的推理（4/6） 给定新设计问题的功能说明，给定新设计问题的功能说明，CADETCADET从它的案例库中搜索存储从它的案例库中搜索存储的案例，使它的功能描述
48、和新设计问题相匹配。的案例，使它的功能描述和新设计问题相匹配。n如果发现了一个如果发现了一个精确的匹配精确的匹配，那么可以返回这个案例作为新设计，那么可以返回这个案例作为新设计问题的建议方案。问题的建议方案。n如果如果没有发现精确的匹配没有发现精确的匹配，CADETCADET可能找到匹配所需功能的不同可能找到匹配所需功能的不同子图的案例。使它匹配设计规格说明的相应部分。通过检索子图的案例。使它匹配设计规格说明的相应部分。通过检索匹配匹配不同子图的多个案例不同子图的多个案例，有时可以拼接得到整个设计。，有时可以拼接得到整个设计。n一般来说，一般来说，从多个检索到的案例产生最终方案从多个检索到的案
49、例产生最终方案的过程可能很复杂。的过程可能很复杂。需要从头设计系统的各个部分，也可能需要回溯以前的设计子目需要从头设计系统的各个部分，也可能需要回溯以前的设计子目标，从而丢弃前面检索到的案例。标，从而丢弃前面检索到的案例。n系统还可以根据领域或一般知识系统还可以根据领域或一般知识加工原始的功能说明图加工原始的功能说明图，产生，产生等等价的子图价的子图以匹配更多的案例。如：以匹配更多的案例。如：A BA B重写为：重写为：A x BA x B2024/8/3037资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.5基于
50、案例的推理（基于案例的推理（5/6）基于案例的推理系统与基于案例的推理系统与k k一近邻方法的一近邻方法的区别区别: :n实例或案例可以用丰富的符号描述表示实例或案例可以用丰富的符号描述表示，就像，就像CADETCADET中使用中使用的功能图。这需要不同于欧氏距离的相似性度量，比如两个功的功能图。这需要不同于欧氏距离的相似性度量，比如两个功能图的最大可共享子图的大小。能图的最大可共享子图的大小。n检索到的多个案例可以合并形成新问题的解决方案检索到的多个案例可以合并形成新问题的解决方案。这与。这与k k一近邻方法相似一近邻方法相似多个相似的案例用来构成对新查询的回答。多个相似的案例用来构成对新查
51、询的回答。然而，合并多个检索到的案例的过程与然而，合并多个检索到的案例的过程与k k一近邻有很大不同，一近邻有很大不同，它它依赖于知识推理，依赖于知识推理，而不是统计方法。而不是统计方法。n案例检索、基于知识的推理和问题求解间是紧密藕合在一起案例检索、基于知识的推理和问题求解间是紧密藕合在一起的的。例如。例如CADETCADET系统在尝试找到匹配的案例过程中，它使用有系统在尝试找到匹配的案例过程中，它使用有关物理感应的一般知识重写了功能图。关物理感应的一般知识重写了功能图。案例检索和合并过程依案例检索和合并过程依赖于知识推理和搜索密集的问题求解方法。赖于知识推理和搜索密集的问题求解方法。202
52、4/8/3038资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.5基于案例的推理（基于案例的推理（6/6）n目前关于基于案例的推理研究的一个目前关于基于案例的推理研究的一个课题课题是改进索引案例的是改进索引案例的方法。方法。n基于案例的推理基于案例的推理中心问题是中心问题是句法相似度量句法相似度量( (例如，功能图之间例如，功能图之间的子图同构的子图同构) )仅能近似地指出特定案例与特定问题的相关度。仅能近似地指出特定案例与特定问题的相关度。n当当CBRCBR系统试图复用检索到的案例时，它可能遇到系统试图复用检索到
53、的案例时，它可能遇到句法相似度句法相似度量量中没有捕捉到的难点。中没有捕捉到的难点。n此时，此时，CBRCBR系统可回溯系统可回溯搜索另外的案例搜索另外的案例以适应现有的案例，或以适应现有的案例，或者者求助于其他的问题求解方法求助于其他的问题求解方法。2024/8/3039资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.6对消极学习和积极学习的评论对消极学习和积极学习的评论(1/4)n三种消极学习三种消极学习(lazy learning)(lazy learning)方法方法: :k k一近邻算法一近邻算法、局部加
54、权回归局部加权回归和和基于案例的推理基于案例的推理。之所以称这些。之所以称这些方法是方法是消极的消极的，是因为它们延迟了如何从训练数据中泛化的决，是因为它们延迟了如何从训练数据中泛化的决策，直到遇到一个新的查询案例时才进行。策，直到遇到一个新的查询案例时才进行。n一种积极学习方法一种积极学习方法: :学习学习径向基函数网络径向基函数网络的方法。之所以称这种方法是的方法。之所以称这种方法是积极的积极的(eager)(eager)，是因为它在见到新的查询之前就做好了泛化的工作，是因为它在见到新的查询之前就做好了泛化的工作在训练时提交了定义其目标函数逼近的网络结构和权值。在训练时提交了定义其目标函数
55、逼近的网络结构和权值。n根据同样的理解，本书其他章节讨论的所有其他算法都是积极根据同样的理解，本书其他章节讨论的所有其他算法都是积极学习算法学习算法( (例如，反向传播算法、例如，反向传播算法、C4.5 )C4.5 )。2024/8/3040资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.6对消极学习和积极学习的评论对消极学习和积极学习的评论(2/4)n在算法能力方面在算法能力方面，消极方法和积极方法有重要，消极方法和积极方法有重要两种差异两种差异: :计算时间的差异和对新查询的分类差异。计算时间的差异和对新查询的
56、分类差异。在计算时间方面在计算时间方面：消极方法在训练时一般需要较少的计算，：消极方法在训练时一般需要较少的计算，但在预测新查询的目标值时需要更多的计算时间。积极方法但在预测新查询的目标值时需要更多的计算时间。积极方法正好相反。正好相反。在新查询的分类方面在新查询的分类方面：消极方法消极方法在决定如何从训练数据在决定如何从训练数据D D中中泛化时考虑查询实例泛化时考虑查询实例x xq q；积极方法积极方法不能做到这一点，因为在不能做到这一点，因为在见到查询实例见到查询实例x xq q前，它们已经选取了对目标函数的前，它们已经选取了对目标函数的( (全局全局) )逼逼近。近。2024/8/304
57、1资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.6对消极学习和积极学习的评论对消极学习和积极学习的评论(3/4)n对学习器的泛化精度的影响对学习器的泛化精度的影响如果要求消极的和积极的学习器采用同一个假设空间如果要求消极的和积极的学习器采用同一个假设空间H H，那么答，那么答案是肯定的。案是肯定的。消极的学习器消极的学习器可以通过很多局部逼近的组合可以通过很多局部逼近的组合( (隐含地隐含地) )表示目标表示目标函数。函数。积极的学习器积极的学习器必须在训练时提交单个的全局逼近。必须在训练时提交单个的全局逼近。积
58、极学习和消极学习之间的积极学习和消极学习之间的差异差异意味着对目标函数的全局逼近意味着对目标函数的全局逼近和局部逼近的差异。和局部逼近的差异。2024/8/3042资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.6对消极学习和积极学习的评论对消极学习和积极学习的评论(4/4)n使用多个局部逼近的积极方法（如使用多个局部逼近的积极方法（如RBF)RBF)，可以产生与消极方，可以产生与消极方法（局部加权回归）的局部逼近同样的效果吗法（局部加权回归）的局部逼近同样的效果吗? ? 消极学习方法消极学习方法可以对于每一个查询
59、实例选择不同的假设可以对于每一个查询实例选择不同的假设( (或或目标函数的局部逼近目标函数的局部逼近) )。使用同样假设空间的使用同样假设空间的积极方法积极方法是更加受限制的，因为它们必是更加受限制的，因为它们必须提交一个覆盖整个实例空间的单一假设。须提交一个覆盖整个实例空间的单一假设。当然，积极的方法可以使用合并了多个局部逼近的假设空间，当然，积极的方法可以使用合并了多个局部逼近的假设空间，就像就像RBFRBF网络可以被看作是对这个目标的尝试。网络可以被看作是对这个目标的尝试。RBFRBF学习方法是学习方法是在训练时提交目标函数全局逼近的积极方法。在训练时提交目标函数全局逼近的积极方法。20
60、24/8/3043资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.7小结小结 (1)n基于实例的学习方法基于实例的学习方法不同于其他的函数逼近方法，因为它们推不同于其他的函数逼近方法，因为它们推迟处理训练样例，直到必须分类一个新查询实例时才进行。因迟处理训练样例，直到必须分类一个新查询实例时才进行。因此，不必形成一个明确的假设来定义整个实例空间上的完整目此，不必形成一个明确的假设来定义整个实例空间上的完整目标函数。而是对每个查询实例形成一个不同的目标函数局部逼标函数。而是对每个查询实例形成一个不同的目标函数局部逼近
61、。近。n基于实例的方法的优点基于实例的方法的优点包括包括: :通过一系列不太复杂的局部逼近通过一系列不太复杂的局部逼近来模拟复杂目标函数却不会损失训练样例中蕴含的任何信息来模拟复杂目标函数却不会损失训练样例中蕴含的任何信息( (因因为样例本身被直接地存储起来为样例本身被直接地存储起来) )。n基于实例的方法的基于实例的方法的主要的实践问题包括主要的实践问题包括: :分类新实例的效率分类新实例的效率( (所所有的处理都在查询期进行而不是事先准备好有的处理都在查询期进行而不是事先准备好););难以选择用来检难以选择用来检索相关实例的合适的索相关实例的合适的距离度量距离度量( (特别是当实例是用复杂
62、的符号表特别是当实例是用复杂的符号表示描述的时候示描述的时候););无关特征无关特征对距离度量的负作用。对距离度量的负作用。2024/8/3044资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.7小结小结 (2)nk k一近邻一近邻是用来逼近实数值或离散值目标函数的基于实例是用来逼近实数值或离散值目标函数的基于实例算法，它假定实例对应于算法，它假定实例对应于n n维欧氏空间中的点。一个新查询维欧氏空间中的点。一个新查询的目标函数值是根据的目标函数值是根据k k个与其最近的训练样例的值估计得到个与其最近的训练样例的值
63、估计得到的。的。n局部加权回归法局部加权回归法是是k k一近邻方法的推广，在这种方法中，一近邻方法的推广，在这种方法中，为每个查询实例建立一个明确的目标函数的局部逼近为每个查询实例建立一个明确的目标函数的局部逼近。目。目标函数的局部逼近可以基于像常数、线性函数或二次函数标函数的局部逼近可以基于像常数、线性函数或二次函数这样的大量的函数形式，也可以基于空间局部化的核函数这样的大量的函数形式，也可以基于空间局部化的核函数。2024/8/3045资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值8.7小结小结 (3)n径向基函
64、数径向基函数(RBF)(RBF)网络网络是一类由空间局部化核函数构成的人工是一类由空间局部化核函数构成的人工神经网络。它可被看作是基于实例的方法神经网络。它可被看作是基于实例的方法( (每个核函数的影响是每个核函数的影响是被局部化的被局部化的) )和神经网络方法和神经网络方法( (在训练期形成了对目标函数的全在训练期形成了对目标函数的全局逼近，而不是在查询期形成的局部逼近局逼近，而不是在查询期形成的局部逼近) )的混合。径向基函数的混合。径向基函数网络已被成功地应用到很多课题，假定空间局部的影响是很合网络已被成功地应用到很多课题，假定空间局部的影响是很合理的。理的。n基于案例的推理基于案例的推理也是一种基于实例的学习方法，但这种方法使也是一种基于实例的学习方法，但这种方法使用复杂的逻辑描述而不是欧氏空间中的点来表示实例。给定实用复杂的逻辑描述而不是欧氏空间中的点来表示实例。给定实例的符号描述，人们已经提出了大量的方法用于把训练样例映例的符号描述，人们已经提出了大量的方法用于把训练样例映射成新实例的目标函数值。基于案例的推理方法已经应用到很射成新实例的目标函数值。基于案例的推理方法已经应用到很多实际问题中，比如，模拟法律推理以及在复杂的生产和运输多实际问题中，比如，模拟法律推理以及在复杂的生产和运输规划问题中引导搜索。规划问题中引导搜索。2024/8/3046
