使用误差中心基准最优化方式的支持向量机的快速训练(一)

外文资料译文

使用误差中心基准最优化方式的支持向量机的
快速训练

L. Meng,Q. H. Wu。
电机工程和电子学学院，利物浦大学，利物浦， L69 3GJ 英国

 摘要: 这篇文章为支持向量机 (SVM) 训练提出一个新算法，这个算法是基于由现在的机器引起的误差中心束来训练一部机器的。从各种不同的训练组合的实验中展现出新的运算法则刻度的计算时间与训练组合大小几乎成线性关系，因此与二次规划标准(QP)技术相比可被提供于更大的训练组合。
keywords: 支持矢量机器, 二次规画, 模式分类, 机器了解。
1 引言
 在统计学理论中基于最近的进展，支持向量机 (SVMs) 组成一个勇于式样分类的学习系统的新团体。训练一个支持向量机相当于解决一个有着密集矩阵的二次规划的问题。二次规划标准的解决需要这个矩阵的所有储存而且他们的效率在于他们的稀疏程度,他向有着大的训练组合设定的支持向量机训练提出申请。
 被 Vapnik 和他的队被提倡的支持向量机, 是一新的模式分类和非线性回归技术.(参看【1】,【2】,和【3】)
 由于线性分离的问题,一个支持向量机是一个从有最大值的一组反面样本中分离出一组正面样本的超平面。虽然简单直观, 但是这个最大值的观点实际上开拓了在统计学理论中的结构风险最小化（SRM）原则【4】. 因此，所了解的机器不仅有最小的经验风险还有好的推广的能力。
 对于非线性可分离的问题,在分类超平面被建立之前输入一个非线性映射 ，而这个分类超平面将训练样本从输入空间传送到比较高维的特征空间。分类超平面是建立在特征空间的。他在输入空间产生一个非线性决定边界。这个决定边界是由在特征空间的处于分类超平面的映射点组成的。非线性映射运用模式可分离定理通过【5】被一致运用.一个复杂的存在于一个高维非线性空间的模式分类问题比在一个低维空间更有可能是线性分离的。
 对于支持向量机, 分类决定函数的新的样本被定义为: 
指一个分类样本, 指相符合的特征向量，和b分别指常向量和分类超平面的截距，向量和常量b是最优参数。
 w和b的优化相当于优化一个服从于一些线性约束的目标函数,。目标函数联合支持向量机优化是一个凸二次函数而且因此最佳化问题没有最大限度的限制。许多变量的二次函数的优化问题在优化理论方面被很好理解并且大多数与之接近的标准能直接应用于支持向量机的训练。然而，大多数二次规划标准技术需要在目标函数里面二次型的全部储存空间。他们或者仅仅适合一些小问题或者仅仅适合二次型非常稀疏的假设，也就是说大多数的二次型元素是零。不幸地是，对于一个支持向量机佳化问题这不事实，问题中二次型方程不仅仅是密集的而且有一个在训练组合中随着数据点二次增长的能力。为了有1000个或者更多样本的训练任务，存储器的需求将会超过百兆字节因此这是不可能碰到的。这禁止了对于有大的训练组织问题的二次规划标准技术的申请。一个替代方案在需要时每一次会重新计算二次型。但是这变得非常的昂贵因为二次规划技术是重复的并且在每次的重复中需要对二次型进行计算。
 如此的思路产生了支持矢量机器的一个新的训练算法的设计。在这篇文章中被推荐的.算法是概念性的简单事情，一般很快而且比标准的二次规划技术有更大规模的资产。
2 在支持向量机训练中的最优化问题
 给一个训练样本的，其中是模仿一个输入样本所属于的目标响应指示,结合训练一个支持向量机的最佳化问题能被写成如下：
OP1:
 限制条件           
 其中间隙被两个超平面所限定而且通过来测量，是允许间隙出现误差的松弛变量，C是一个与有一些间隙误差的宽大间隙交换的参数。当时，机器被称为一个固定间隙支持向量机因为所有的训练样本必须放在边缘外部，是不允许有划分误差的。否则，机器被成为一个可变间隙支持向量机。
    通过引入拉格朗日乘子和和拉格朗日函数
因此要对拉格朗日函数关于求最小值并且要对拉各朗日函数关于的最大值，其中我们有

并且OP1的二重形式如下：

其中定义为在特征空间中的两个向量的内积并被称为核函数。核函数的使用允许一个支持向量机，没有以前明确的特征空间的描述，他的运用限制了在特征空间的分类超平面和在那个空间的分类向量这样的详细描述特征向量的计算负担没有增加。
    OP2本质上是一个二次规划问题因为他有下面的形式：
     
其中矩阵Q是二次型。对于支持向量机的训练，他被定义为
    由【6】和【7】得Karush―Kuhn―Tucker(KKT)条件是对一组变量达到最优得最优化问题得充分必要条件。对于问题OP1运用（KKT）条件，我们知道最优解决必须要满足
     
和    
包含   
       
 方程式（9）以及方程式（8）和（10）显示出只有那些在间隙边界上的而不是那些处在变化的样本是符合要求的 。方程（8）表明对于符合等于零的所有样本必须要被正确的分类并且放在间隙以外。方程（10）表明具有符合的间隙误差要等于上面的受约束的C。此外，方程（7）显示非零的松弛变量只有当时存在而且所有的间隙误差都要受到惩罚。
3 误差中心基准最优化
   一个二次规划问题的大小取决于二次型Q。在支持向量机训练中，矩阵Q的大小是，其中表示训练数据点的个数。如所描述的，有一个为明确存储Q的标准解决技术的必要条件，但是在支持向量机训练中禁止运用标准二次规划去计算有大量数据组的支持向量机的训练。
    考虑到这些，通过【8】一个新的支持向量机训练的技术产生了。基本的想法是去压缩最初的训练组然后训练一个关于由最近压缩群中心所组成的一个工作组的机器。在每次重复中压缩通过分离每个将一个支持向量作为它的中心的群为两个附属群来进行更新。因为这个新的算法从由群中心所组成的工作组中摘取分类信息，所以被称为中心基准最优算法。关于各种训练组的试验已经显示出采用中心基准最优化方法的训练时间比标准技术所用的时间要少的多。对于大的训练任务，中心基准最优化算法能将所用的时间少于用标准技术所用时间的1/150。
    可惜的是，虽然一个最优边界能够通过中心基准最优化的方法找到，但是产生决定边界的最优化不能对每一次运行有所保证。（参看Fig.1(a)和Fig.1(b)进行比较）。这是因为一个k方式计算法已被运用于分离中心基准最优化方法。这个算法的上升性质使他在不同的最优化限制方面变得容易捕捉到。不管产生的决定边界有不精确和多样性，中心基准的快速性展现了中心基准算法的巨大潜力,它