基于实例的学习-机器学习_基于实例的机器学习

k-近邻法

这个算法假定所有的实例对应于 n 维欧氏空间${\Re }^n$ 中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例 x 表示为下面的特征向量：
$$<a_1(x)，a_2(x)，\dots ,a_n(x)>$$
那么两个实例 $x_i$ 和 $x_j$间的距离定义为 $d(x_i,x_j)$，其中：
$$d(x_i,x_j)=\sqrt{\sum _{r=1}^n(a_r(x_i)-a_r(x_j){)}^2}$$

算法

对前面的 k-近邻算法作简单的修改后，它就可被用于逼近连续值的目标函数。我们让算法计算 k 个最接近样例的平均值，我们只要把算法中的公式替换为：
$$\hat{f}(x_q)\leftarrow \frac{{\sum }_{i=1}^{k}f(x_i)}{k}$$

距离加权最近邻算法

对 k-近邻算法的一个显而易见的改进是对 k 个近邻的贡献加权，根据它们相对查询点$x_q$ 的距离，将较大的权值赋给较近的近邻。
例如，逼近离散目标函数的算法中，我们可以根据每个近邻与 $x_q$ 的距离平方的倒数加权这个近邻的“选举权”。方法是通过用下面算法中的公式来实现：
$$\hat{f}(x_q)\leftarrow argmax\sum _{i=1}^k{w}_i\delta (v,f(x_i))$$
其中：
$$w_i=\frac{1}{d(x_q,x_i{)}^2}$$
为了处理查询点 $x_q$ 恰好匹配某个训练样例 $x_i$，从而导致分母为 0 的情况，我们令这种情况下的 $\hat{f}(x_q)$等于 $f(x_i)$。
我们也可以用类似的方式对连续目标函数进行距离加权：
$$\hat{f}(x_q)\leftarrow \frac{{\sum }_{i=1}^k{w}_{i}f(x_i)}{{\sum }_{i=1}^k{w}_i}$$

对k-近邻算法的说明

按距离加权的 k-近邻算法是一种非常有效的归纳推理方法。 它对训练数据中的噪声有很好的鲁棒性。通过取 k 个近邻的加权平均，可以消除孤立的噪声样例的影响。

k-近邻算法的归纳偏置是什么呢？
它的归纳偏置对应于假定：一个实例的分类 $x_q$ 最相似于在欧氏空间中它附近的实例的分类。

应用 k-近邻算法的一个实践问题：
实例间的距离是根据实例的所有属性计算的。这与那些只选择全部实例属性的一个子集的方法不同，例如决策树学习系统。

为了理解这种策略的影响，考虑把 k-近邻算法应用到这样一个问题：每个实例由 20 个属性描述，但在这些属性中仅有 2 个与它的分类是有关。在这种情况下，这两个相关属性的值一致的实例可能在这个 20 维的实例空间中相距很远。这种由于存在很多不相关属性所导致的难题，有时被称为维度灾难（ curse of dimensionality）。最近邻方法对这个问题特别敏感。

解决该问题的一个有趣的方法是，当计算两个实例间的距离时对每个属性加权。这相当于按比例缩放欧氏空间中的坐标轴，缩短对应于不太相关属性的坐标轴，拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的数量可以通过交叉验证的方法自动决定。
另外一种更强有力的方法是从实例空间中完全消除最不相关的属性——留一法的交叉验证。m 个训练实例的集合以各种可能方式被分成 m-1 个实例的训练集合和 1 个实例的测试集合。

应用 k-近邻算法的另外一个实践问题是如何建立高效的索引。一种索引方法是 kd-tree，它把实例存储在树的叶结点内，邻近的实例存储在同一个或附近的结点内。通过测试新查询 xq 的选定属性，树的内部结点把查询 xq 排列到相关的叶结点。

术语注解

回归（Regression）的含义是逼近一个实值目标函数。
残差（Residual）是逼近目标函数时的误差 fˆ (x)- f(x)。
核函数（Kernel function）是一个距离函数，它用来决定每个训练样例的权值。换句话说，核函数就是使 $w_i=K(d(x_i,x_q))$的函数 K。

局部加权回归

局部加权回归使用附近的或距离加权的训练样例来形成这种对 f 的局部逼近。

之所以叫“局部”是因为目标函数的逼近仅仅根据查询点附近的数据，之所以叫“加权”是因为每一个训练样例的贡献是由它与查询点间的距离加权的，之所以叫“回归”是因为统计学习界广泛使用这个术语来表示逼近实数值函数的问题。

给定一个新的查询实例 $x_q$，局部加权回归的一般方法是建立一个逼近 $\hat{f}$ ，使 $\hat{f}$拟合环绕 $x_q$ 的邻域内的训练样例。然后用这个逼近来计算 $\hat{f}(x_q)$的值，也就是为查询实例估计的目标值输出。然后 $\hat{f}$ 的描述被删除，因为对于每一个独立的查询实例都会计算不同的局部逼近。

局部加权线性回归

下面，我们先考虑局部加权回归的一种情况，即使用如下形式的线性函数来逼近 $x_q$ 邻域的目标函数 f：
$$\hat{f}(x)=w_0+w_1{a}_1(x)+\cdots +w_n{a}_n(x)$$
误差$E(x_q)$:
$$E(x_q)=\frac{1}{2}\sum _{x\in x_q的k个近邻}(f(x)-\hat{f}(x){)}^{2}K(d(x_q,x))$$
权值为关于相距 $x_q$ 距离的某个递减函数 K。
重新推导梯度下降法则，可以得到以下训练法则：
$$∆w_i=\eta \sum _{x\in x_q的k个近邻}K(d(x_q,x))(f(x)-\hat{f}(x))a_j(x)$$

径向基函数

另一种函数逼近的方法是使用径向基函数。在这种方法中，待学习的假设是一个以下形式的函数，
$$\hat{f}(x)=w_0+\sum _{u=1}^k{w}_u{K}_u(d(x_u,x))\text{\hspace{1em}(3.1)}$$
其中每个 $x_u$是 X 中一个实例，核函数 $K_u(d(x_u,x))$被定义为随距离 $d(x_u,x)$的增大而减小。
一种很常见的做法是选择高斯函数（Gaussian function）作为每个核函数$K_u(d(x_u,x))$，高斯函数的中心点为 $x_u$，方差是${\sigma }_u^2$ 。
$$K_u(d(x_u,x))=e^{-\frac{1}{2{\sigma }_u^2}{d}^2(x_u,x)}$$
公式（3.1） 给出的函数可以被看作是描述了一个两层的网络， 第一层计算不同的 $K_u(d(x_u,x))$，第二层计算第一层单元值的线性组合。

给定了目标函数的训练样例集合，一般分两个阶段来训练 RBF 网络。
首先，决定隐藏单元的数量 k，并通过选取用来定义核函数$K_u(d(x_u,x))$的 $x_u$、 ${\sigma }_u^2$ 值定义每个隐藏单元。
第二，使用式（3.2）给出的全局误差准则来训练权值 $w_u$，使网络拟合训练数据程度最大化。因为核函数在第二阶段是保持不变的，所以线性权值 $w_u$ 可以被非常高效地训练得到。
$$E=\frac{1}{2}\sum _{x\in D}(f(x)-\hat{f}(x){)}^2\text{\hspace{1em}(3.2)}$$

人们已经提出了几种方法来选取适当的隐藏单元或者说核函数的数量。
一种方法是为每一个训练样例$<x_i,f(x_i)>$分配一个高斯核函数，此高斯函数的中心点被设为 $x_i$。所有高斯函数的宽度${\sigma }^2$ 可被赋为同样的值。这样选择核函数的一个优点是它允许RBF 网络精确地拟合训练数据。
第二种方法是选取一组数量少于训练样例数量的核函数。 这种方法可以比第一种方法更有效，特别是在训练样例的数量巨大的时候。我们可以标识出实例的原始聚类然后以每个聚类为中心加入一个核函数。

RBF网络的一个关键优点是，与反向传播算法训练的前馈网络相比，它的训练更加高效。这是因为 RBF 网络的输入层和输出层可以被分别训练。

对消极学习和积极学习的评论

在这一章中我们考虑了两种消极学习（lazy learning）方法： k-近邻算法、局部加权回归。之所以称这些方法是消极的，是因为它们延迟了如何从训练数据中泛化的决策，直到遇到一个新的查询。
本章讨论了一种积极学习方法：学习径向基函数网络的方法。之所以称这种方法是积极的，是因为它在见到新的查询之前就做好了泛化的工作——在训练时提交了定义其目标函数逼近的网络结构和权值。
根据同样的理解，本书其他章节讨论的所有其他算法都是积极学习算法。

差异

(1)计算时间的差异：
消极方法在训练时一般需要较少的计算，但在预测新查询的目标值时需要更多的计算时间。

(2)归纳偏置的差异：
消极方法在决定如何从训练数据 D 中泛化时考虑查询实例 $x_q$。
积极方法不能做到这一点，因为在见到查询实例 $x_q$ 前，它们已经选取了对目标函数的（全局）逼近。
这个区别会影响学习器的泛化精度。

消极的学习器可以通过很多局部逼近的组合（隐含地）表示目标函数，然而积极的学习器必须在训练时提交单个的全局逼近。因此积极学习的和消极学习之间的差异意味着对目标函数的全局逼近和局部逼近的差异。