- 相关推荐
使用误差中心基准最优化方式的支持向量机的快速训练(一)
外文资料译文
使用误差中心基准最优化方式的支持向量机的
快速训练
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方式计算法已被运用于分离中心基准最优化方法。这个算法的上升性质使他在不同的最优化限制方面变得容易捕捉到。不管产生的决定边界有不精确和多样性，中心基准的快速性展现了中心基准算法的巨大潜力,它用于有大量训练组的支持向量机最优化问题的快速解决。
通过观察Fig.1(b),失去支持向量的状态或者在内或者在间隙的误差的一边。而且因为他们没有被包括在最后的训练中，他们的匹配是零。KKT条件表明结合零的样本必须能被正确的分类并且要放在间隙的外测。通过这个得到启发，已经对中心基准最优化进行了修改。现在，通过分离那些符合KKT条件的样本，每一个群被分离成为了两个附属群并且这样被放在了外部或者是放在来自那些违反KKT条件的当前间隙和放在内部或者是放在当前间隙的误差的一边。一方面，如果在最初的至少一个群违反KKT条件的训练组有一些样本，他们将被分离。另一方面，程序要反复到在最初的违反KKT条件的训练组没有样本为止。因为KKT条件是解决最优化问题的必要充分条件，所以通过这个算法被找到的解决最优化问题的方法是能够保证的。另一方面，这个新的算法建立了利用一组群中点的支持向量机。这里，我们将违反KKT条件的样本指作间隙误差。为了在每次重复中进一步减少二次规划问题的数量，仅仅是需要将间隙误差的群被包括在支持向量机训练中。剩余的群是通过在先前的重复中找到的支持向量来描述的。此外，他还能通过一个大的二次规划问题在一系列小的二次规划附属问题中被解除的【10】来被证明。如果至少一个违反KKT条件的样本被加到先前附属问题的样本中，那么每一步将会简化所有的目标函数并且支持一个可施行的遵守所有条件的解决方法。因此，一个总是加在至少一个违反样本的二次规划附属问题的结果将会被保正会趋于一致。考虑到这个结果，为了确保它在目标函数中的绝对改进以及因此使之集中，则新的计算要将一个误差中心置于仅仅假设它违反了KKT条件的工作组。否则，在那个大多数违反KKT条件的群中的样本将会被置于就如它的群所描述的工作组。因为大多数工作组的样本误差群的中心（先前重复的支持向量必须是误差群的中心），这个新的算法被称为误差中心基准最优化算法（ECO）。ECO的执行步骤列在表1中。
Fig.1利用中心基准最优化算法找到两个可能的决定边界。那些点是确定的样本并且星状物是不确定的点。群的中心被绘制成一些大点。实线表示的是决定边界。在虚线中间的空间是间隙。在（b）中，在包含剩余支持向量的群中的样本被小框所标记。
表1 误差中心基准的最优化算法的执行步骤
给一个训练组S，将每一个S的模本看成是一个群
将工作组S初始化为这这两个群的中心
重复
在S上训练支持向量机
将S设置为支持向量
对于S的每个群
通过确认间隙误差，将最近的群分解成两个附属群， 也就是说，他们违反了KKT条件。如果误差群的中心违反了KKT条件，将中点加到S中。否则，将违反KKT条件的最坏点的样本加到S中。
直到没有新的间隙误差被找到。
S表示通过决定函数两个模本被分类的一个训练组。
S表示包括在附属支持训练中的样本组。
表示中心被定义成的S的第r个群。
【使用误差中心基准最优化方式的支持向量机的快速训练(一)】相关文章：
基于子空间和模糊支持向量机的说话人识别03-07
快速消费品配送中心选择优化的模型与算法03-25
配送中心管理优化探讨03-20
金融对产业结构调整和优化的支持03-22
挖掘机的选型和使用03-07
有限状态机的VHDL优化设计03-07
基于大气物理模型的快速视觉优化去雾算法03-17
物流配送中心优化方案探讨03-07