高级数字图像处理：模式识别第7章

1、7 稀疏核机7.1 最大边际分类器7.1.1 重叠类分布7.1.2 关系到逻辑回归7.1.3 多类SVM7.14 用于回归的SVM7.1.5 计算学习理论7.2 关联向量机7.2.1 用于回归的RVM7.2.2 稀疏性分析7.2.3 用于分类的RVM练习在上章中，我们探讨了基于非线性核的各种学习算法。这些算法最大的局限之一是核函数必须在所有可能的训练点的和对上估值，它可能在训练时是计算上不可行的，并且可能导致当为新数据点做预测时耗费大量的计算时间。本章中，我们将寻找具有稀疏解的基于核的算法，使得对新输入的预测仅取决于在训练数据点的子集上估值的核函数。 首先，我们来研究支持向量机（SVM）的一些

2、细节，SVM用于求解分类、回归和新成分检测等问题，并在若干年前变得流行。支持向量机的一个重要性质是：模型参数的确定对应于凸优化问题，因此任何局部解也是全局解。因为支持向量机的讨论广泛地使用Langrange乘子，鼓励读者复习在附录E中的关键概念。支持向量机的更多信息可以在Vapnik（1995），Burges（1998），Cristianini 和Shawe-Taylor（2000），Miiller等（2001），Scholkopf和Smola（2002），以及Herbrich（2002）的著作中看到。SVM是一个决策机，因此它不提供后验概率。我们在1.5.4节中已经讨论了确定概率的一些好处。

3、另一个稀疏核方法，被称为关联向量机（RVM），它是建立在Bayesian公式上的，并提供后验概率输出，通常有比SVM更稀疏的解。7.1 最大边缘分类器通过回顾使用如下线性模型的二类分类器问题，我们开始对支持向量机进行相关讨论 （7.1）这里代表一个固定的特征空间变换，且使偏差参数b显式表示。注意，我们将要引入一种以核函数形式表达的对偶表示，这就避免了特征空间里必须显式地起作用。训练数据集由N个输入向量组成，与之相对应的目标值是，其中，新数据点按照的符号进行分类。我们将暂时假定训练数据集在特征空间里是线性可分的，使得按照定义，在和b参数中至少存在一种选择，使得形如（7.1）式函数满足：对的点满足

4、；对的点满足，因此对所有的训练数据点都有。当然，也许存在许多这样准确分离类的解。在4.1.7节，我们详细描述了感知器算法，它能够保证在有限的步骤里找到一个解。但是找到的解将依赖于和b的（任意）初始值选择，以及数据点出现的顺序。如果有多个解，所有的都能准确地对训练数据集进行分类，那么我们尝试找到一个有最小标准误差的解。支持向量机通过边缘概念来解决这一问题，边缘定义为决策边界与任何样本之间的最小距离，如图7.1。图7.1边缘定义为决策边界与最靠近的数据点之间垂直距离，如左图所示。最大化边缘导致决策边界的特殊选择，如右图所示。这个边界的位置由数据点的一个子集决定，即支持向量，这在后面会经常提出。支持

5、向量机中，决策边界会选成是边缘最大化的一个。最大边缘的解受计算学习理论的推动，也称为统计学习理论。但是，对最大边缘起源的一个简单了解，就会发现早在2000年已被Tong和Koller提出，他们考虑了一个基于生成和判别方法混合的分类框架。首先，他们用Parzen密度估计和有着一般参数的高斯核，为每一个类在输入向量的分布上进行建模。连同此类的先验，定义了一个最优的误分类率决策边界。但是，他们不使用此最优化边界，而是通过最小化相对于学习密度模型的错误概率来确定最优超平面。极限时，最优超平面是有最大边缘的一个。这一结果背后的直观感觉是，随着的减小，相对于较远数据点来说，较近点将对超平面的控制逐渐起主要

6、作用。在这个极限上，超平面就独立于那些不是支持向量的数据点了。我们将会在图10.13了解到，对一个简单的线性可分数据集，用Bayesian方法对参数先验分布进行边缘化，可以产生一个决策边界，这个边界位于分离数据点的区域中间。最大边缘的求解有类似的方法。我们再回看一下图4.1，点x到定义的超平面的垂直距离由给出，这里的取（7.1）式的形式。此外，我们只对那些正确分类数据点的解感兴趣，故对所有的来说，。点到决策面的距离公式如下： (7.2)边缘由数据集到最近点的垂直距离给出，我们希望通过优化参数和b来最大化这个距离。因此，最大边缘解可通过解下式得出： (7.3)我们把因子从上的最优解提出去，因为不

7、依赖于。这个优化问题直接求解是十分复杂的，因此我们将它将它转换为一个等价问题，使其更容易解决。为了进行转换，我们注意到，如果进行尺度变换和，由公式给出的任意点到决策面的距离都未改变。我们可以利用这个自由度为离决策面最近的点设 (7.4)在这种情况下，所有数据点都会满足下面的约束条件： ， (7.5)这就是决策超平面的标准化表示。对于等式成立的数据点，约束条件称作有效的，而余下的那些称作无效的。根据定义，至少有一个是有效约束，因为总有一个最近点，且一旦边缘最大化，则至少有两个有效约束。最优化问题仅仅需要我们最大化，也就相当于最小化，所以我们必须要解满足约束条件（7.5）的最优化问题： （7.6）

8、为了以后方便，我们在（7.6）中引入因子1 / 2。这是二次规划问题的一个实例，我们正试图最小化二次函数，以使其满足一组线性不等式约束。看起来偏置参数已经从最优化过程中消失了。然而，它由约束条件隐式确定，因为这需要求通过改变为来补偿改变为。不久我们就会看到这个过程。为了解决此有约束最优化问题，我们引入Lagrange子乘子，以及一个满足约束条件（7.5）的乘子，得到的Lagrange函数为： （7.7）其中。注意，Lagrange乘子项前面的负号，因为我们是对和最小化，对最大化。设关于和的导数等于零，得到下面两个条件： （7.8） （7.9）用上面两个条件消去中的和，然后取最大边缘问题的对偶表

9、示，这里对进行最大化 （7.10）使其满足约束条件： ， （7.11） （7.12）这里的核函数由来定义。这里再次使用了二次规划问题的形式，优化了的二次函数，使其满足一组不等式约束。在7.1.1节中，我们将会讨论此类二次规划问题的解法。有M个变量的二次规划问题的解，通常计算复杂度是。将要讨论对偶公式时，我们将在M个变量上最小化（7.6）的原始优化问题转换成对偶问题（7.10），它有N个变量。对于给定的一组基函数，其个数M小于数据点个数N，这将对对偶问题不利。然而，它允许此模型用核的形式重新表示，因此最大边缘分类器能被有效地应用到特征空间，此特征空间的维数超过了数据点的个数，包括无限特征空间。核

10、公式也解释清楚了核函数是正定的这一约束条件的作用，因为这保证了Lagrangian函数有上界，就可以产生良定的最优化问题。为了用训练模型去对新的数据点分类，我们用式（7.1）来确定的符号。这可用参数的形式来表达，且通过式（7.8）用核函数替换得到： （7.13）在附录E，我们证明了这种形式的有约束最优化问题满足KKT条件，这种情况需要满足下面的三个性质： （7.14） （7.15） （7.16）因此，对于所有的数据点，要么，要么。对于的任何数据点将不会出现在和（7.13）式中，因此在对新的数据点预测时不起作用。剩余的数据点就叫作支持向量，因为它们满足，它们对应于特征空间中最大边缘超平面上的点，

11、如图7.1。这个性质在支持向量机的实用性上非常重要。一旦这个模型被训练，绝大部分数据点可以被剔除，仅保留支持向量。我们已经解决了二次规划问题，并找出了的值，然后由任何支持向量满足可确定阈值参数。用（7.13）式能得出： （7.17）这里的表示支持向量的指数集合。尽管我们能用任意选择的支持向量解关于的方程，然而，一个更稳定的数值求解方法是：首先乘以，利用，然后对这些方程在所有支持向量上求平均值，得出： （7.18）这里的是支持向量的总数。与后面选择的模型相比，我们可以用最小化误差函数的形式来表示最大边缘分类器，加上一个简单的二次正则项，得出： （7.19）这里是一个函数，当时它为0，其它情况下为

12、，同时要保证满足约束条件（7.5）式。注意，只要正则化参数满足，它的精确值毫无作用。图7.2二维空间中取自两个类的综合数据的例子，描绘出了从有高斯核函数的支持向量机得到的常量的轮廓。也描绘了决策边界，边缘边界和支持向量。图7.2显示了一个分类的例子，其结果是用形如（6.23）的高斯核在一个简单的合成数据集训练支持向量机得到的。尽管数据集在二维数据空间上不是线性可分的，但在非线性核函数隐式确定的非线性特征空间上是线性可分的。因此，在最初的数据空间里，训练数据点可以完全分离。这个例子也提供了在SVM中稀疏起源的几何理解。最大边缘超平面通过支持向量的位置来确定的。其它数据点可在不改变决策边界的条件下

13、自由移动（只要它们仍在边缘区域外），因此，这个解将不依赖于这样的数据点。7.1.1 重叠类分布目前为止，我们假定训练数据点在特征空间里是线性可分的。支持向量机的结果将会在原始输入空间中给出训练数据的准确分离，尽管相应的决策边界是非线性的。然而，实际上类条件分布可能是重叠的，在这种情况下，训练数据的准确分离能够导致较差的推广。因此我们需要一种方法来改善支持向量机，以便允许一些训练点可以被误分类。从（7.19）式我们知道，在可分离类的情况下，我们隐式使用一个误差函数：如果一个数据点被误分类，那么它就给出无限的误差；如果数据点被正确分类，那么它就给出零误差。然后对模型参数优化以实现边缘的最大化。现在

14、我们改善这个方法，以便数据点可以在边缘边界的“错误一侧”，但给出一个随到此边界的距离增大而增大的惩罚项。对于随后的优化问题，可以很方便的使惩罚项成为这个距离的线性函数。为了做到这点，我们为每一个训练数据点引入松弛变量，这里的（Bennett，1992；Cortes 和Vapnik，1995）。在正确边缘边界上或其里面的数据点由确定，其他数据点由确定。因此，在决策边界上的一个数据点将有，对于的数据点将会被误分类。准确分类约束条件（7.5）式变成： ， （7.20）这里约束松弛变量满足。满足的数据点是正确分类的，要么在边缘上，要么在边缘的正确一侧。满足的数据点位于边缘的里面，但是在决策边界的正确一

15、侧，满足的那些数据点在决策边界的错误一侧，且是被错分类的，如图7.3。有时这被描述成松弛硬边缘约束，并相应地得到软边缘（soft margin），并且使得一些训练集数据点被误分类。注意，当松弛变量允许重叠类分布时，这个框架仍然对离群值敏感，因为对误分类的惩罚随着而线性增加。 图7.3 松弛变量的图解。带有圆圈的数据点周围是支持向量。当软惩罚点位于边缘边界错误一侧时，我们的目的是最大化边缘。因此我们最小化 （7.21）其中参数控制着松弛变量惩罚和边缘之间的权衡。因为对任何误分类的点都有，它遵从是误分类点数目的上界。因此参数C是类似于（即逆）一个正则化系数，因为它控制了训练误差最小化与控制模型复杂

16、度之间的权衡。在极限时，我们要为可分离数据恢复早期的支持向量机。我们希望最小化（7.21）式使其满足约束（7.20）式和。相应的Lagrange公式是 （7.22）其中和是Lagrange乘子。相应的一组KKT条件如下： （7.23） （7.24） （7.25） （7.26） （7.27） （7.28）其中。现在我们用的定义（7.1）式来最优化，和，得出 （7.29） （7.30） （7.31）使用这些结果从Lagrange公式中消去，和，我们得到对偶Lagrange的形式： （7.32）除了约束条件有些不同，它与可分离的情况是相同的。为了解这些约束条件是什么，我们注意是需要的，因为那是Lag

17、range乘子。此外，（7.31）式和意味着。因此我们必须对（7.32）关于对偶变量最大化，使其满足： （7.33） （7.34）其中，（7.33）称作是箱型约束。这又是一个二次规划的问题。如果将（7.29）代入（7.1）中，我们看到对新数据点的预测也可利用（7.13）式给出。我们现在可以解释这个解。像之前的，数据点的一个子集可能有，这种情况下，它们对预测模型（7.13）没有作用。剩下的数据点就构成支持向量。这些点要求，因此由（7.25）式可知，必须满足 （7.35）如果，（7.31）式意味着，从（7.28）式可知，这要求，因此这些点在边缘上。的点可以在边缘里面，如果时它们就可准确分类，如果则

18、会错误分类。为确定（7.1）式中的参数，我们注意到当时的这些支持向量有，所以，因此将满足 （7.36）一个数值稳定解也由求平均得到 （7.37） 其中M表示有数据点的指数集。Scholkopf（2000）等人提出另一种方法，即支持向量机的等效表述，叫做。这包括最大化 （7.38）使其满足约束： （7.39） （7.40） （7.41）这种方法的优点是代替参数的参数可以理解为：既是边缘误差部分的上界（的点将在边缘边界错误一侧，并且可以、也可以不被误分类），也是支持向量部分的下界。应用于合成的数据集的的例子如图7.4所示。这里应用了高斯核的形式，其中。图7.4 用于二维空间中的不可分数据集的的图释

19、。支持向量用圆圈标出。尽管对新输入点的预测只使用了支持向量，但训练阶段（例如确定参数和）却利用了整个数据集，所以用有效的算法解决二次规划问题是非常重要的。我们首先注意到由（7.10）或（7.32）给出的目标函数是二次的，因此，如果约束条件确定了一个凸区域（它们是线性的结果），那么任何局部最优值也将是全局最优值。采用传统方法直接解二次规划问题通常是不可行的，因为这需要很高的计算量和内存，所以要找到更实际的办法。分块技术（Vapnik，1982）正是利用了如下事实：如果我们删除与零值Lagrange乘子相对应的核函数的行与列，Lagrangian公式保持不变。这使得完整的二次规划问题被分解成一系列

20、较小的问题，其目的是最终确定所有的非零Lagrange算子，并舍弃其余的。分块可通过受保护共轭梯度来实现（Burges，1998）。虽然分块使二次函数矩阵的大小从数据点平方数减少到非零Lagrange算子平方近似数，但实际上内存需求仍过大而不能满足大规模应用。分解的方法（Osunal等人，1996）也解决了一系列较小的二次规划问题，但此设计使每一个分解块都有固定大小，所以此方法可以应用到任意大数据集。然而，它仍然包含二次规划子问题的数值解，这可能会出现问题且代价高昂。其中最流行的一种训练支持向量机的方法叫做序贯最小优化或SMO（Platt，1999）。它对极端限制采用了分块概念，且一次仅考虑两

21、个Lagrange算子。这种情况下，子问题可以解析地解出，从而完全避免数值的二次规划。每一步都选择一对Lagrange乘子给了我们启发。实际中，SMO（序贯最小优化）有一个数据点数量的缩放，根据特定的应用，它介于一次和二次之间。我们已经看到，核函数对应于特征空间的内积，特征空间可以是高维的，甚至无限维的。直接使用核函数形式，而无需特意引入特征空间，可以看出支持向量机在某种程度上避免了维数的影响。然而这并非事实，因为在约束特征空间有效位数的特征值中存在约束条件。只考虑一个简单的二阶多项式核，我们可扩展它的元素 （7.42）因此这个核函数代表了六维特征空间的一个内积，其中从输入空间到特征空间的映射

22、是通过向量函数描述的。然而，这些不同特征的加权系数都有特定形式的约束。因此，原始二维空间的任何点集，都被精确限制处在固定在六维特征空间的一个二维非线性流形中。我们已经强调了一个事实，即支持向量机不提供概率输出，而是提供了新输入向量的分类决策。Veropoulos等（1999）讨论改进SVM，以使其再伪正和伪负误差之间做出权衡。然而，如果我们希望支持向量机作为一个大概率系统的模块，对新的输入，需要类标签的概率预测。为解决这类问题，Platt（2000）提出用逻辑斯蒂S型来拟合先前训练的支持向量机的输出。特别地，所需的条件概率假设是如下的形式 （7.43）这里是（7.1）定义的。参数A和B的值通过

23、最小化互熵误差函数求得的，互熵误差函数是由有一对和值的训练集确定。为了避免严重的过拟合，用于拟合S型函数的数据需要独立于用来训练原始SVM的数据。这个两阶段方法等价于假设SVM的输出，它代表属于类的的对数可能性（log-odds）。由于SVM训练过程不是特别为了支持这个，SVM可以给出后验概率的一个较差逼近(Tipping, 2001)。7.1.2 与逻辑回归的关系仿照可分离的情况，我们可以用正则误差函数最小化的形式，为不可分离分布重新构造SVM。与逻辑回归模型相比，它允许我们强调相似性和差异性。我们已经看到对于在边缘边界正确一侧的数据点，它们满足，所以有，对于剩下的点我们有。因此，目标函数（

24、7.21）可以被写成(相差一个整体的乘数常量)以下形式 （7.44）这里，是铰链误差函数，其定义为 （7.45）其中表示正的部分。之所以称作铰链误差函数，是根据它的形状而来，如图7.5所示。它可以被视为误分类误差的一个近似，例如，我们想使理想的误差函数最小化，这也在图7.5中给出。图7.5 应用于支持向量机的铰链误差函数的图示，以蓝色显示，沿着逻辑回归的误差函数，用因子1/ln2重新调整，所以它通过点（0.1），用红色显示。黑色是误分类误差，绿色是平方误差。当我们在4.3.2节中考虑到逻辑回归模型时，发现此模型与目标变量一起运行相当方便。为了与支持向量机比较，首先我们用目标变量来重写最大似然逻

25、辑回归的表示。为做这些，我们注意到，其中是由（7.1）式给出的，是（4.59）中定义的逻辑斯蒂S型函数。用逻辑斯蒂S型函数的性质，有，因此我们可以写出 （7.46）由此我们可以取似然函数的负对数来构造一个误差函数，以及一个二次正则项，得出下面形式 （7.47）其中 （7.48）为了与其它误差函数相比较，我们可以除以使得误差函数通过点（0,1）。重新调整的误差函数也在图7.5中标出了，我们看到它和支持向量误差函数有相似的形式。关键的区别是，中的平坦区域会产生稀疏解。逻辑斯蒂误差和铰链损失都可看作是对误分类误差的连续逼近。有时用于解决分类问题的另一个连续误差函数是平方误差，它也在图7.5中标出。虽

26、然它具有正确分类的数据点越来越被重视的性质，但是它离正确一侧的决策边界还有很大的距离。以误分类点为代价来增加这些点的权重，如果目的是使误分类率最小化，那么单调递减的误差函数是一个更好的选择。7.1.3多类SVM支持向量机从根本上来说是一个2-类分类器。但实际上，我们经常要处理包括个类的问题。因此，提出组合多个2-类SVM的若干方法，来构造一个多类分类器。一个常用的方法（Vapnik，1998）是构建K个独立SVM，其中第个模型用两种数据来训练，一种是取自类并作为正例的数据，另一种是取自剩余的个类并作为负例的数据。这就是我们所说的一对余方法。但是，在图4.2中我们可以看到，用独立分类器的决策会导

27、致结果的不一致，即一个输入同时被分配给多个类。有时，这个问题可通过对新的输入进行预测来处理： （7.49）不幸的是，这个探索式的方法有一些问题，如不同的分类器是在不同的任务上训练的，也不能保证对不同的分类器实际值将有适当的大小。一对余方法的另一个问题是训练集失调。例如，我们有十个类，每一个类都有相同数量的训练数据点，独立分类器在有90%的负例和10%的正例的数据集上训练，那么这些原始问题将失去对称性。在2001年，Lee等提出了一种改进的一对余方法：调整目标值，使正类目标值是+1，负类目标值为。在1999年，基于最大化从每个类到剩余类的边缘（边缘），Weston和Watkins为同时训练所有K

28、个SVM定义了一个单一的目标函数。然而，这样可能导致训练速度更慢，因为每解决一个超过N个数据点的K个独立最优化问题需花费时间复杂度，但是解决大小为数据点的一个单一最优化问题就需要花费时间复杂度。另一种方法是在所有可能的类对上训练个不同2-类SVM，然后根据哪个类有最高票数来对这些测试点分类，这种方法有时称作一对一算法。我们又在如图4.2中看到这种方法可能会导致分类结果不明确。另外，当K非常大的时候，与一对余相比这种方法明显需要更多的训练时间。同样，要评估测试点，明显需要更多的计算量。图4.2由一组2-类判别式来构建一个k-类判别式会导致模糊区域，如图中绿色所示。左图例子是用两个判别式来区分属于

29、类的点和不属于它的点；右图例子是有三个判别函数，它们每一个都是用来区分一对类和的。上面提到的第二个问题（一对一误分）可以通过把类对组织成有向无环图来缓和（不要和概率图模型相混淆），这就是DAGSVM算法（Platt等，2000）。对于K个类， DAGSVM共有个分类器，为了对一个新的测试点进行分类，仅需要对个类对进行评估，特定分类器的使用取决于通过图的哪一条路径被遍历。基于错误纠正输出码，Dietterich 和 Bakiri在1995年提出了一种关于多类分类的不同方法，2000年Allwein等把这种方法应用于支持向量机。这可以看作是对一对一方法投票方案的推广，其中更一般的类划分被用于独立分

30、类器的训练。这K个类本身代表选定2-类分类器的反应的特定集合，并带有一个可行的编码方案，这将给出对误差的鲁棒性，以及对独立分类器输出中的歧义性的鲁棒性。虽然在多类分类问题中使用SVM仍是一个开放性问题，但在实际中，一对余的方法是应用最广泛的，尽管它有特别的设定化和实际的限制。也有单类SVM，它解决与概率密度估计有关的无监督学习问题。然而，这些方法不是去构造数据密度的模型，而是旨在找出一个密封的高密度区的光滑边界。选择的边界代表密度的一个分位数，也就是说，从分布中得到一个数据点的概率将落在事先给予0和1之间的固定值的区域内。这是一个比估计全密度更受限制的问题，但可能在具体应用中已经足够了。对于这

31、个问题，已经提出了两种用支持向量机来解决的方法。Scholkopf的算法试图找到一个超平面，它分离了所有数据点，除了来自原始训练数据的给定部分v，并且同时也最大化了原始超平面的距离（边缘），而1999年，Tax和Duin在特征空间中寻找最小的球面，它包含除v部分之外所有的数据点。因为内核仅是的函数，所以这两种算法是等价的。7.14 用于回归的SVM 现在我们把支持向量机扩展到回归问题，同时要保留稀疏的性质。在简单的线性回归中，我们通过式（7.50）最小化一个正规化的误差函数。 （7.50）为了获得稀疏解，用一个不敏感函数来代替二次误差函数（Vapnik，1995），如果预测和目标值之间差的绝对

32、值小于时（0），就会得到零误差。举不敏感误差函数的一个简单例子，它与不敏感区域外的误差有一个线性损失，形式为： （7.51）并在图7.6中给出解释。图7.6 -不敏感误差函数图示（红色），其中当超过不敏感区域时，误差是线性递增的，对比的也绘制出二次误差函数（绿色）。因此我们最小化一个由下式给出的正规化误差函数 （7.52） 其中由（7.1）式给出。按照约定的（逆）正则化参数，记为C，出现在误差项之前。如前所述，我们可以通过引入松弛变量来重新描述优化问题。对于每一个数据点，我们现在需要两个松弛变量，其中对应于一个点，它满足，对应于一个点，它满足，这在图7.7中给出解释。图7.7 SVD回归的说明

33、图示。图中绘出了回归曲线和-非敏感“管”，以及松弛变量和的例子。管上方的点有和，管下方的点有和，管内的点有。一个目标点位于“管道”内的条件是，其中。假如松弛变量是非零的，则引入的这些松弛变量将使点位于管道外面，且对应的条件是 （7.53） （7.54）支持向量回归的误差函数可以写成 （7.55）它必须被最小化，来满足与（7.53）和（7.54）中和一样的限制。通过引入Lagrange乘子，来做到这一点，最优化Lagrange算子 （7.56）我们现在用（7.1）式替换，然后分别设Lagrange乘子关于w，b，和的导数为0，得到 （7.57） （7.58） （7.59） （7.60）利用这些结

34、论来消除来自Lagrange乘子的相应变量，我们看到：对偶问题涉及到对和最大化， （7.61）这里我们已经引入了核。再次重申，这是一个约束最大化，为了找到这些约束我们注意到，和都是需要的，因为它们是Lagrange乘子。另外，、以及（7.59）和（7.60），要求和，所以连同条件（7.58）我们有一个框限制 （7.62） （7.63）把（7.57）代入（7.1），我们看到通过式（7.64）可对新输入进行预测， （7.64）这再次被表示在核函数的项里。对应的KKT条件规定了：在解的结果里，对偶变量与约束的乘积必须消失，公式如下： （7.65） （7.66） （7.67） （7.68）从这里我们可

35、以得到一些有用的结果。首先，我们注意到如果，那么系数只能非0，这就意味着数据点或者位于“管道”的上边界（）或者位于上边界上方（）。同样的，非0意味着，并且这样的点必定是位于“管道”的下边界上或者下边界下方。而且，这两个约束和是互不相容的，这可从把它们加在一起很容易地看到，并可注意到和 非负而是严格正的，所以对每个数据点，要么或必须为零。支持向量是(7.64)式给出的那些有助于预测的数据点，换句话说就是那些或者的点。这些点位于“管道”的边界上或者管道外边。管道内所有的点都有。我们再一次得到一个稀疏解，在预测模型（7.64）中必须要估计的项是包含支持向量的那些。通过考虑满足的数据点可以找到参数b，

36、（7.67）式必须有，（7.65）必须满足。利用（7.1）式求解参数b，得到： （7.69）这里我们使用了公式（7.57）。通过考虑满足的数据点，我们能得到一个类似的结果。实际上，最好是平均所有b的这些估计。伴随着分类情况，有一个对于回归支持向量机的公式，在这里调整复杂度的参数有更多直观的解释（Scholkopf等，2000）。特别是，我们固定一个参量，而非固定非敏感区域的宽度，来限制在管道外侧的一小部分点。这包含最大化 （7.70）使其满足约束条件 (7.71) (7.72) (7.73) (7.74)这能证明，至多有个数据点落在非敏感管道的外部，同时至少有个数据点是支持向量，在管道的外面或

37、者内部。图7.8中，用正弦数据集来阐释使用支持向量机解决回归分析问题。这里参数和C已被手工选择。实际上它们的值通常由互确认来决定。图7.8 应用于利用高斯核的正弦合成数据集的回归的图示。预测回归曲线由红线显示，非敏感管对应阴影区域。同样地，数据点由绿色显示，而且它们和支持向量一起由蓝色的圆圈表示。7.1.5 计算学习理论从历史上讲，支持向量机已用称作计算学习理论，有时也叫统计学习理论的理论框架来大量地研究和分析（Anthony和Biggs，1992； Kearns和Vazirani，1994；Vapnik，1995；Vapnik，1998）。这是由valiant（1984）首先提出，他构建了p

38、robably approximately correct或PAC学习框架。PAC框架的目标是：理解给出一个好的推广需要多大的数据集。它同样给出了学习计算成本的范围，尽管我们在这里还不了解。假定一个大小为的数据集是从某个联合分布中得到的，这里是输入变量，代表类标签，而且我们只对“无噪声”情况保持关注，在这里类标签由一些（未知）确定函数确定。在PAC学习中，从基于训练集D的这类函数的一个空间取得的函数，如果它的期望误差率低于某个先验阈值，我们就说它有很好的概括，因此 （7.75）这里是特征函数，期望是关于分布的。左侧的量是一个随机变量，因为它取决于训练集D，而且PAC框架对一个随机取自的数据集D

39、需要（7.75）式成立，概率大于。这里是另一个先验的参数，而且“probably approximately correct”这个术语来自最高概率（大于），误差率小（小于）这样的要求。对给定的模型空间F，以及给定的参数和，PAC学习目标是为满足此准则的数据集的最小大小确定范围。PAC中一个关键的量是Vapnik-Chervonenkis维数或VC维数，它提供了空间函数复杂度的一个测度，而且允许PAC框架扩展到包含无穷个函数的空间。在PAC框架内得到的边界经常被说成是做最坏的情况，因为它们使用任意选择的分布，只要训练和测试样本（独立地）取自相同的分布，且对于属于的任意选择的函数。在现实的机器学习

40、的应用中，我们处理有显著规律的分布，例如在带有相同类标签的输入空间的大区域中。由于缺乏分布形式的假定结果，PAC边界是非常保守的，换句话说，它们过度高估了需要达到给定的概括表现的数据集的大小。对于这个原因，PAC边界只发现很少的实际应用。PAC-Bayesian框架（MCAllester，2003）是为了提高PAC边界的紧密性，它考虑了函数空间F上的一个分布，有点类同于Bayesian处理中的先验。这仍然考虑了的任意可能选择，虽然边界变得更紧密，但仍然是非常保守的。7.2 关联向量机支持向量机已使用在各种各样的分类和回归应用中。然而，它们有很多的局限性，其中一些已在本章指出。实际上，支持向量机

41、的输出代表决策而不是后验概率。同样，SVM最初是为两个类规划的，并且扩展到个类是有问题的。这有个复杂参数或（和回归中的参数一样），必须用诸如交叉验证的支持输出方法来得到。最后，预测被表示为中点在训练数据点且需要正定的核函数的线性组合。这个关联向量机或RVM（Tipping，2001）是回归和分类的Bayesian稀疏核方法，回归和分类有许多共同的支持向量机的特征，同时避免了它的主要限制。此外，它通常产生一些稀疏模型，导致测试数据上的相对更快的性能，同时维持类似的概括误差。与SVM相比我们发现，首先引入RVM的回归形式是更为便利的，然后考虑了分类任务的拓展。7.2.1用于回归的RVM回归的关联向

42、量机是第3章研究的形式的一个线性模型，但带有一个导致稀疏解的改进先验。给定一个输入向量，模型为实值目标变量t定义了一个条件分布，其形式为 （7.76） 这里是噪声精度（噪声方差的倒数），均值由如下形式的线性模型 （7.77）和固定非线性基函数给出，这通常包含一个常数项，所以相应的加权参数代表一个“偏差” 。关联向量机是该模型的一个特殊实例，它是为了反映支持向量机的结构。特别地，基函数由核给定，一个核关联着取自训练集的每一个数据点。一般表达式（7.77）取近似支持向量机的形式 （7.78）这里b是一个偏差参数。这种情况下参数的数目是，具有与SVM的先验模型（7.64）相同的形式，除了系数在这里记

43、作。应该强调随后的分析对任意选择的基函数是有效的，而且概括地讲，我们将处理式（7.77）。与SVM相比，这里没有约束为正定核，基函数也没有与训练数据点的数目和位置相结合。假设给定对输入向量的一组N个观测值，我们通过一个数据矩阵X共同表示，矩阵的第n行是（）。相应的目标值通过给出。因此，似然函数通过下式给出： （7.79）下面我们在参数向量上引入一个先验分布，和第3章一样，我们考虑一个零均值高斯先验。然而，在RVM中关键的不同是我们为每个加权参数引入一个单独的超参数，而不是一个简单的共有超参数。因此加权先验形式如下 （7.80）这里代表相应参数的精度，表示。我们应该看到，当我们关于这些超参数最大

44、化证据时，它们一个有效的部分变成无穷大，相应的加权参数有集中在零值的后验分布。因此，与这些参数相关联的基函数在由模型做出的预测中不起作用，所以这是有效的修剪，产生一个稀疏模型。利用线性回归模型的结果（3.49），我们看到加权的后验分布也是高斯的，其形式如下 （7.81）这里的均值和方差通过下面式子给出： （7.82） （7.83）这里是的设计矩阵，其元素为，且。 和的值由2-型最大似然确定，也被称为证据逼近，这里我们最大化由对加权参数积分得来的边缘似然函数，得到 （7.84）因为这代表两个高斯的卷积，很容易评估给出边缘似然函数的对数形式： （7.85）这里，并且我们已通过下式定义了矩阵C （7

45、.86）现在我们的目标是关于超参数和最大化（7.85）。这仅仅需要对在3.5节中对线性回归模型中的证据近似得到的结果做一个小小的修改。而且，我们能确定两个方法。首先，我们简单地设所需的边缘似然函数的导数为0，得到如下的重估计方程 （7.87） （7.88）这里是（7.82）式定义的先验均值m的第i个元素。量测量相应参数由数据确定的好坏程度，定义如下 （7.89）其中是（7.83）式给出的后验分布的协方差的第个对角元素。因此，学习所得通过选择和的初始值，分别利用（7.82）和（7.83）计算后验分布的均值和协方差，然后利用（7.87）和（7.88）交替重新计算超参数，并用（7.82）和（7.83

46、）重新计算后验分布的均值和协方差，直到满足一个合适的收敛准则。第二种方法是利用EM算法，这将在9.3.4节讨论。这两种求得最大化证据的超参数值的方法形式上是等价的。然而，在数值上，会发现对应于（7.87）和（7.88）的直接最优方法给出了稍微更快的收敛（Tipping，2001）。作为最优化的结果，我们发现超参数的一部分趋向于很大的值（在极限准则下），所以，对应于这些超参数的权重参数有均值和方差都为0的后验分布。因此，这些参数和对应的基函数可从模型中移出，并对新输入的预测不起作用。在形如（7.78）的模型中，与余下的非零权值相对应的输入称为关联向量，因为它们通过自动关联确定机制来认定，类似于一

47、个支持向量机的支持向量。然而，值得强调的是：在概率模型中，通过自动关联确定获得稀疏的机制是很一般的，并适用于可表示为基函数的自适应线性组合的任意模型。求得最大化边缘似然的超参数值和后，我们能为一个新的输入计算的预测分布。利用（7.76）和（7.81），可由下式给出 （7.90）因此令（7.76）给出的带有的预测均值等于后验均值，且预测分布的方差由下式给出 （7.91）这里由（7.83）给出，其中和取为最优值和。这只是在线性回归中得到的常见结果（3.59）。回顾那些局部基函数，线性回归模型的预测方差在没有基函数的输入空间的区域中将会变小。在基函数集中于数据点的关联向量机（RVM)的情形中，当推断

48、数据区域外部时，模型对预测变得越来越确定(Rasmussen 和 Quinonero-Candela， 2005)，这显然是不合要求的。高斯过程回归中的预测分布不受这个问题影响。但是对高斯过程预测的计算消耗明显比一个关联向量机（RVM)高的多。图7.9 与图7.8中回归模型一样，关联向量机回归使用相同的数据集和相同的高斯核函数。关联向量机的预测分布均值用红线显示，标准差预测分布用阴影区显示。同时，数据点用绿色表示，关联向量用蓝圈表示。注意，与图7.8 中的7个支持向量相比，这里只有3个关联向量。图7.9表示用于正弦曲线回归数据集的一个RVM例子。这里噪声精度参数也通过证据最大化来决定。我们发现

49、RVM中关联向量的数目明显小于SVM中支持向量的数目。在大范围的回归和分类任务中，发现RVM给出的模型明显比相对应的支持向量机多一个数量级，导致在处理测试数据时的速度有明显的提高。值得注意的是，与相应的SVM相比，这实现了更大的稀疏，很少或没减少广义误差。与SVM相比，RVM的首要优势是训练包括最优化一个非凸函数，训练时间比支持向量机的长。对于一个有M个基函数的模型，关联向量机要求一个大小为的矩阵的逆，这通常要的计算量。在类-SVM模型（7.78）的特定情况下，我们有M=N+1。我们已经指出，训练支持向量机的方法花费大概的时间。当然，在关联向量机的情况下，我们常常选择少于N+1个基函数来开始。

50、更值得注意的是，在关联向量机中，参数管理复杂度和噪声方差由单一的训练游程自动确定，而在支持向量机中，参数C和（或）一般用交叉验证得到，其中包含多个训练游程。此外，在下一节中，我们将导出一个替代程序来训练关联向量机，这将明显提高训练的速度。7.2.2 稀疏分析我们早就指出自动关联决策机制能使参数的子集趋向于0。现在我们更详细地研究在关联向量机环境下的稀疏机制。在这个过程中，比起上面给出的直接方法，我们将得出一个明显更快的程序来最优化超参数。图 7.10 图为在Bayesian线性回归模型中的稀疏机制，显示一个由给出的目标值的训练集向量，用叉表示，一个基向量的模型，这与目标数据向量不一致。左图我们看到一个模型只有各向同性噪声，所以，对应的，设为最可能的值。右图我们能看到同样的模型，但