支持向量网络论文原文-Vapnik-论文翻译 | In Web3

摘要：
- 支持向量网络是一种新的用于二类分类问题的学习机。这个机器(方法)概念地实现了以下想法：非线性的输入向量被映射到高维度的特征空间。在这个特征空间中找出一个线性决策超平面。决策超平面的特殊属性可以保证学习机的强泛化能力。这个支持向量网路的思想在训练资料严格线性可分的情况下已被实现。现在我们来谈一下在训练资料非线性可分的情况下的结果。
- 支持向量网络的高泛化能力是利用多项式输入转换。我们同样比较了支持向量网络和和其他经典的学习算法在OCR(光学字符识别)这个基准上的表现。
关键字：
- 模式识别，有效的学习算法，神经网络，径向基函数分类器，多类分类器

简介

60多年前R.A. Fisher(Fisher, 1936)提出了模式识别的第一个算法。有两个服从正态分布的模型，和，n维向量X，其中均值向量分别是m1和m2，方差分别是和，最后得到的最优解(贝叶斯)是一个二次规划函数：
若果，那么上式化简为一个线性函数：
要解式子(1)中的二次规划函数，必须有个自由参数。要解式子(2)中线性函数仅仅要n个自由参数。观测量的数量小(比如说小于个)估算个参数是不可靠的。因此Fisher推荐，即使是在的情况下，仍然对线性判别函数(2)使用以下的形式：
上式中的是一个常量。Fisher另外推荐了当两个分布不是服从正态的时候，利用一个线性决策函数。
模式识别的算法最开始就和线性决策超平面的构建有关。
在1962年Rosenblatt(Rosenblatt, 1962)发明了一种新型的学习机：感知机或者神经网络。感知机包含多个相连的神经元，每个神经元实现一个分离超平面，所以整个感知机实现了分段的线性分离超平面。见图Fig.1。
在Rosenblatt时期还没有算法通过调整网络的权值来最小化向量集的错误。根据其他权值的固定值，输入向量被非线性地转换到特征空间Z中,在单元的最后一层。在这个空间中一个线性决策函数被构造：
通过调节从第i层隐藏层到输出单元的的权值以最小化在整个训练资料上的一些误差。根据Rosenblatt的方法的结果来看，决策规则的构造再一次联系到信息超平面的构造，在某些空间上。
第一次出现一个算法允许通过调整神经网络的权值来最小化属于模式识别问题的向量集的局部误差是在1986年,(Rumelhart, Hinton & Williams, 1986, 1987; Parker, 1985; LeCun 1985)因为那个时候发现了反向传播算法。它的解法是一个轻微修改的神经元的数学模型。所以，神经网络实现了“分段线性类型”的决策函数。
在本文中，我们构造一个新型的学习机(方法)，所谓的“支持向量网络”。支持向量网络实现了一下想法：它通过一些事先选择好的非线性的映射规则把输入向量映射到高维度的特征空间Z。在这个空间当中，通过一些特殊属性来构造线性决策超平面来保证网络的高泛化能力。
例子：要求得二次多项式的决策超平面，可以创建一个特征空间Z，它有 N= 个坐标形式：
上面的方法中有两个新的问题：一个是概念上的，一个是技术上的。概念上的问题是怎么才能找到一个推广能力较好的分离超平面：特征空间的维数将会很大，而且并不是所有的可分离训练资料的超平面都有很好的推广能力。然后技术上的问题是面对如此高维的空间，怎么简化计算量：在一个200维德空间中构造一个4次方或者5次方的多项式可能需要构造一个数以数以亿计的维数的空间。
概念上的问题在1965(Vapnik, 1982)被解决了，鉴于为线性可分的类寻找最佳化的分离超平面这个case.这里定义的最佳化的超平面是两个可分的向量中寻找最大的分类间隔，看Fig.2.被证明说要构造这样一个最佳化的超平面只需要很少的训练数据，这些数据就被称为支撑向量，它们是用来决定间隔的。资料表明，如果训练资料被一个最佳化的超平面完美无误地分离，那么在测试例子中预测新数据的误差期望值等于支持向量的数量的期望值和训练向量的数量的比：
注意到这个约束并没有明显的包含可分空间的维数。这个约束遵循这个规则的：如果构造最佳化的超平面包含的支持向量的数量越少，那么这个模型的泛化能力就越高–即使是在无穷的维数空间中。在Section 5我们会通过一个实际生活问题说明上面(5)式子的比值可以低到0.03，而且这个最佳化超平面在数以亿计的维数的特征空间中的推广能力很好。
让
作为空间中最佳化超平面的表示。我们会把特征空间中的最佳化超平面的权值写成支持向量的线性组合式
特征空间中的线性决策函数会相应地变成以下形式：
表示的是再特征空间中的支持向量zi和z的点积。决策函数能够被描述为一个两层的网络。(Fig.3.)
然而，即使最佳化超平面的推广能力比较好，但是关于怎样处理高维度空间的技术的问题还没解决。在1992年(Boser, Guyon, & Vapnik, 1992)，构造决策函数的操作顺序是可以互换的：我们可以先比较输入空间中的两个向量(比如，计算它们的点积，或者一些距离测量)对结果的值做非线性转换，而不是拿特征空间中两个点积的向量做非线性的转换。这样促成了更多分类的决策超平面的构造，例如，任意次方的多项式决策超平面。我们把这种类型的学习机叫做支持向量网络。
支持向量网络的技巧当初是为了毫无误差地找到更精准的分类训练数据的超平面。在这篇文章当中，我们对支持向量网络进行拓展，拓展到当不能毫无误差的进行分类数据的情况下也能使用。在这种情形之下，我们把支持向量网络当成一种新的学习机。一种像神经网络一样更强大更通用的学习机。在Section 5我们会对在一个高维空间(维度256)，多项式次方高达7的情形下，支持向量网络的泛化能力还能有多好进行说明。这种学习机的表现可以与那些经典的学习机(像线性分类器，k邻近分类器和神经网络等)相媲美。Section 2，3和4主要讲算法的推导和它的一些属性的讨论。关于推导的细节请看附录部分。

最佳化超平面

在这个section当中，让我们来回顾一下0误差分离训练资料的最佳化超平面的方法(Vapnik, 1982).而在下一个section，我们介绍软间隔的记号，它允许在分类的过程当中存在误差。

最佳超平面算法

训练模式的标签集
被认为是线性可分的，如果向量W和标量b满足以下不等式条件：
被认为说是对(8)中的所有的训练集都是有效的。然后把(9)中的不等式写成一下形式：
最佳化超平面是：
它是唯一一个把训练资料分离出最大间隔：它保证了两个不同类别的训练向量映射在方向上的距离是最大的。回顾Fig.2.这个距离表示如下：
最佳化超平面是使得(12)中距离最大的参数。它符合(12)和(10)的约束
这就是说最佳化超平面在符合(10)式当中的约束的条件下是唯一一个可以最小化的.所以构造最佳化超平面的问题就是一个二次规划问题。
当中的向量学术上被称为支持向量。在附录A.1中，我们说明了能够决定最佳化超平面的向量可以写成一个训练向量的线性组合形式：
(14)中当.因为仅仅是符合支持向量(看附录)，(14)当中的表达式是的简写形式。我们也说明了要找参数的向量：
必须要解决以下的二次规划问题：
其中满足的约束条件是：
其中是一个维的单位向量，是一个维的标签向量，是一个带元素的对称的矩阵
(16)当中的不等式描述的是非负象限。所以我们在(17)的约束条件下最大化(15)中的二次规划式。
当(8)中的训练资料可以0误差的分离时，我们同样在附录中进行了说明，(15)中的最大值，对和(13)中的最大间隔的关系：
对于某些和大的常量，不等式
是合理的，有一个可以断言的是所有的可分离训练资料(8)的超平面都满足
如果(8)中的训练资料不能被一个超平面分离，那么两个模式类别之间的间隔将会非常小，导致函数的值非常大。在约束条件(16)和(17)下最大化函数(15)的值，其中一个达到最大值时(这种情况是其中一个通过最大间隔构建了一个超平面)，或者其中一个找到了最大值超过了给定的常量(这种情况是训练资料的分离超平面比还要大是不可能的)。
在约束条件(16)和(17)下最大化函数(15)的问题很有效地通过以下模式解决。把训练资料合理的分成多个不大的部分。首先利用第一部分的训练资料来解决二次规划的问题。对于这样的处理会有两种可能的结果：这部分的训练资料不能找打一个可分离的超平面(这样的话整个资料也是找不到可分离的超平面的)，或者在第一部分的训练资料中就找到了最佳化的分离超平面。
如果是在第一部分的训练资料中就找到了分离超平面，我们把它称作向量，让它来最大化函数(15).在向量当中有一些值是等于0的。它们对应于这部分资料的非支持向量。创建一个新的训练资料集，其中包含第一部分资料的支持向量和第二部分资料的那些不符合约束(10)的向量，其中是由决定的。在这个新的资料集当中创造了一个新的函数和这个函数在处达到最大。然后重复这样的做法，覆盖到所有的训练资料中，不断增加新的解法向量，如果找不到0误差的分离超平面，或者对所有训练资料可以构造一个最佳化分离超平面.请注意，在这个过程当中，函数的值是单调递增的，因为越来越多的训练向量被划分为最佳化，导致两个类别之间的分隔越来越小。

软间隔超平面

考虑到那种不能0误差的把训练资料分离的情况。这样的话，我们想说要达到误差的最小化来分离资料。要正式地表达这个，让我们先引入一些非负变量
我们现在最小化函数
其中，约束于
足够小，函数(21)描述的是训练错误的个数。
最小化(21)，我们要找出一些最小的训练错误的子集：
如果这些误差资料不包含在训练资料中，那么训练资料就可以毫无误差的进行分离，并且在两个类别之间找到一个超平面。
这个想法可以正式的表达为：最小化函数
约束条件为(22)和(23)，其中是一个单调的凸函数，是一个常量。
足够大的和足够小的，在约束条件(22)和(23)下的最小化函数(24)的向量和常数，可以决定一个超平面，这个超平面是最小化在训练集上的错误个数和把剩余的元素利用最大间隔进行分离。
注意到，在训练集上构造一个能够最小化错误数的超平面是一个正常的NPC问题(因不能用多项式算法而使问题无法解决的；非完全多项式).为避免我们的问题出现NPC问题，我们设定