文摘
工作集分解方法的选择是一个重要的一步训练最小二乘支持向量机(二)。在这篇文章中,一个新技术的选择工作集序列最小优化- (SMO)类型提出了分解方法。通过新方法,我们可以选择一个方向达到最优的收敛条件。一个简单的渐近收敛证明新算法。实验对比表明,新方法的分类精度不是很大程度上不同于现有的方法,但比现有的训练速度更快。
1。介绍
在分类问题中,我们考虑一组训练样本,也就是说,输入向量连同相应的类标签。我们的任务是找到一个确定性的函数,它最能代表输入向量之间的关系和类标签。在机器学习分类或预测的问题,采用支持向量机(SVM)在许多应用程序中,因为它精度高(1- - - - - -4]。支持向量机需要一个二次规划问题的解决方案。另一个成功的机器学习方法是最小二乘支持向量机(二)5]。而不是解决支持向量机的二次规划问题,得到一组线性方程的解决方案二。有很多提议算法训练二:Suykens等人提出了一个基于共轭梯度(CG)算法的迭代算法(6];费雷拉等人提出了一个梯度系统,可以训练回归模型(7有效);蔡教授介绍了高效计算大型最小平方支持向量机分类器(8];朱等人重心算法的效率提高了使用一个线性方程组(减少9];Keerthi和Shevade扩展序列最小优化(SMO)算法来解决线性方程组在回归模型的最大违反对(MVP)被选为工作集(10];基于SMO算法的概念,和薄熙来等人提出了一种改进的工作集方法选择使用功能获得(FG) [11];剑等人设计了一种多重核学习算法为二凸规划(12];等等。这些数值算法计算有吸引力。实证对比表明,SMO算法比CG更高效的大规模数据集。
支持向量机的训练速度快,SMO算法是一个重要的实践者和许多其他的提议得到的目标在文献中。最初,普拉特提出两个启发式,导致有点笨重的选择(13]。之后,Keerthi等人介绍了一双违反的概念来表示两个系数导致违反马双重的最优性条件,和作者建议选择总是最违反他们的一对,即最大违反对(MVP) [14]。最后,风扇等人提出了一个二阶的选择,通常会导致更快的训练比MVP规则(15]。通过上述改进,我们可以减少SMO算法的计算代价,虽然有重复选择一些具体更新模式序列最小优化。他们被称为训练周期。巴贝罗等人研究了它们的存在从几何的角度来看16]。他们指出,培训周期可以部分倒在一个向量更新给更好的优化方向。训练周期的想法可以减少迭代次数和内核操作SMO算法。
灵感来自巴贝罗et al。16),我们呈现单一定向SMO算法二,缩写为SD-SMO算法。在优化过程中,一种自适应选择目标函数,和单一定向步骤给出了拉格朗日因子,它可以减少训练周期和进一步减少迭代次数和内核操作SMO算法。实验表明,培训时间为二SD-SMO算法可以显著减少,和它有一个测试精度不很大程度上不同于传统的SMO算法。
本文的其余部分有以下结构。在下一节中,简要回顾了生物。节3SD-SMO算法提供了回归模型,从理论上证明了改进算法的收敛性。基于标准的数据集,计算实验描述并给出了改进算法的有效性4。最后,部分5致力于结束语。
2。回归模型
在本节中,我们简明回顾生物的基本原则。给定一个训练数据集点与输入数据
在原始重量的空间里,一个线性分类器在新的空间采用以下形式:
权重向量可能是无限维的;因此,使用(1)找到的解决方案是不可能的。为了解决这个问题,我们将计算模型的对偶空间而不是原始的空间。让,没有偏见的简单的问题被认为是本文的摘要Keerthi和Shevade10]。简单问题的拉格朗日 在哪里拉格朗日因子和被称为支持值。Karush-Kuhn-Tucker(马)的最优性条件
消除后和,我们可以获得以下线性系统: 在哪里,,是内核矩阵。通过求解线性系统(6),得到;因此,为生物极大地简化了问题。得到的回归模型估计函数
核函数的选择有几种可能性:(线性回归模型);(多项式回归模型的程度);(RBF回归模型);(MLP为生物)。在这种情况下,我们关注的是续集的RBF回归模型的选择。求解大型线性系统的时候,我们应该应用迭代方法(6),它是由焦et al。17]。收敛的速度取决于矩阵的条件数(6)。这是选择的影响在RBF回归模型。在下一节中,我们将讨论SMO算法的版本,给SD-SMO算法收敛性的证明。
3所示。SMO和SD-SMO算法回归模型
解决回归问题的矩阵(6)通常是完全致密和存储可能太大。分解方法的设计目的是处理困难,看到焦et al。17]。与其他优化算法更新整个拉格朗日因子向量在每一个迭代过程,分解算法修改的一个子集每个迭代。我们表示工作集的子集。SMO算法开发的(10)作为分解方法解决双重生物配方中出现的问题。在每个迭代中,SMO算法限制只有两个元素。因为问题(4没有偏见的术语),SMO可以简化优化只有一个元素在一个迭代。通过用马条件(5)到拉格朗日(4),对偶问题是最大化目标函数如下: 在哪里,如果和否则。
SMO算法(8)是勾勒出在以下。
算法1。SMO算法(8)如下。(1)集并找到作为初始可行解。(2)如果停止标准是满意,停止。如果没有,找到一个元素的工作集。定义和和是subvectors对应于和,分别。(3)解决下面的子问题的变量: 在哪里是一个矩阵的排列吗。(4)集的最优解(9),。集回到步骤。
为了找到工作集,我们通常认为马条件是否违反了。马条件对偶问题(8),这导致,。如果我们定义 马的最优性条件是违反是否存在索引点这样。SMO算法(8)达到最优的收敛过程,尽管。
一个简单的例子是图所示1。
每个迭代更新,因为只有一个组件分解方法可以相当昂贵,患有慢收敛。出于这个原因,许多研究人员改进SMO算法。例如,陈等人改进SMO算法通过收缩和缓存技术18];巴贝罗等人提出了一个cycle-breaking加速度的SVM训练(16];和林等人提供了支持向量机参数序列最小优化(19]。
如前所述,巴贝罗等人在16),SMO算法cycle-related问题的不是免费的。对所有在工作集中搜寻所选,如果优化的步骤(或)在一个方向每迭代周期的数量SD-SMO算法将减少。我们现在SD-SMO配方回归训练过程中的细节。
定义
然后,马最优条件违反了如果存在任何索引点这样。
SD-SMO算法通过优化只有一个在每个迭代和其他保持固定的,也就是说,调整sign-invariable一步(或每个迭代)如下:
的更新引起的变化作为 和;因此,的函数值将会改变。在每个迭代中,我们需要确定的标志不是变量,也就是说,如果(或)0,那么(或)0。作为的增加,(或)保持不变。
一个简单的例子是图所示2。
获得最优的步骤和迭代的终止条件,我们定义作为
因为作为,。因此,让它可以写成
最优步是通过最大化作为 和最优步骤能引起的变化吗作为
因此我们可以选择索引的最大价值和更新由(12)和(16)。假设和,然后是一个递减序列。事实上,正如,。因此可以用作迭代算法的终止准则 在哪里是一个积极的常数。SD-SMO算法的流程图所示算法2。
算法2。SD-SMO算法(8)如下。(1)集并选择这样(或)为所有。(2)如果满足(18),停止。如果不是,选择(3)更新使用和(12)。(4)而(),,回到步骤。
一个理论SD-SMO算法在以下的属性。
定理3。序列由SD-SMO生成算法收敛于全局最优解(8)。
证明。根据的定义并结合(16)和(17),下列方程是:
正定内核函数此外,,得到以下方程:
平等(20.)的收益率是一个递减序列。在一起我们有,是收敛的。应用(20.),我们得到了收敛于作为。
自()是一个正定二次型,是一个正定二次型。因此,一组是一个紧集。谎言在这个集合中,所以这是一个有界序列。让任何收敛的子序列的极限点,。对所有,。根据的定义,。不平等(18)的收益率;此外,对所有,。而,所以,。马的条件,是全局最优的解决方案(8)。自是严格凸(8)有一个独特的全球解决方案,我们表示它。假设不收敛。然后,对所有,存在无限子集这样对所有,。因为,尽管是一个紧集,有一个收敛的子序列。不失一般性,我们假设其限制。因此,。自是全局最优的解决方案(8),这个矛盾是唯一的全局最优解。定理的证明。
4所示。数值实验
框架下的算法2,我们进行实验来检查是否使用SD-SMO是否真的比使用SMO在这一节中。有两种技术工作集选择SMO-type分解方法。前者是一阶SMO (FO-SMO)算法,后者是二阶SMO (SO-SMO)算法对二分类器(20.];也就是说,前者使用一阶信息实现快速收敛,后者使用二阶信息。两组实验已经完成为了比较SD-SMO与上述两个算法。是在MATLAB中实现所有方法和个人电脑上执行与英特尔(R)的核心(TM) i3 2.53 GHz处理器,2.00 gb的内存,和Windows 7操作系统。对所有算法,优化过程终止时最大范围内违反马条件。为简单起见,我们只考虑高斯内核构建回归模型。
4.1。与一阶SD-SMO SMO的比较
在本节中,我们比较与一阶SMO SD-SMO四个基准数据集评估该方法的性能。我们比较这两种方法的计算成本,衡量的迭代的数量。的例子引入Keerthi和Shevade10使用)。数据集用于此目的是香蕉、形象、波形和拼接。为每个数据集的价值是由5倍交叉验证小随机子集。
在第一个实验中,我们各不相同在一个小范围内,因为非常小的和大的价值观通常是小的利益。我们尝试以下九个价值观:,。在表1计算成本与四个数据集的函数给出了优化过程时终止。
作为比较的基础,表1显示了一阶SMO的计算成本和SD-SMO算法在不同的参数值。对于一阶SMO算法,计算成本的增加而增加。而对于SD-SMO算法,它并非如此。例如,看到的计算成本SD-SMO香蕉和波形数据集。从表1,我们可以看到SD-SMO算法的迭代次数比一阶SMO的小得多,尤其是对图像数据集。
为了进一步展示SD-SMO算法的性能表2和3给出了。表报告培训时间和一阶SMO的泛化性能和SD-SMO算法四个基准数据集。泛化性能是由一个独立的测试集的分类精度为每个数据集。
从表2和3,我们可以看到,这两种方法的泛化能力可比,但SD-SMO算法的训练时间短于一阶SMO算法。例如,在图像数据集的情况下,一阶SMO算法的训练时间和最好的泛化性能是41.6108秒。它代表了相当于十倍的成本SD-SMO算法。图像数据集与SD-SMO算法的分类精度是0.963,和它几乎等于一个一阶SMO算法。在结果的有效性和可行性提出SD-SMO SMO算法优于一阶回归模型。
4.2。与二阶SD-SMO SMO的比较
对该方法的性能进行进一步的探索,我们比较与二阶SD-SMO SMO的第二组实验数据集《泰坦尼克号》,心,乳腺癌,甲状腺,皮马人(可在[21])。我们使用中提供的数据集(21)来证明该方法的良好的泛化性能。在表4迭代次数和执行时间/实验报告。误分类率也报道在表4。
这些数据可以看出,最好使用SD-SMO癌症,皮马人,《泰坦尼克号》。结果在表4显示的最大改进SD-SMO发生《泰坦尼克号》。因此,这是进一步的证据之前的观察,对大规模问题SD-SMO优于二阶SMO。
最后一组的实验旨在确定如何SMO算法尺度对大规模数据集时使用不同的工作集的选择。为了验证这一点,我们使用数据集a8a covtype。二进制数越来越多的可用模式(22]。
在图3,我们策划a8a的结果,和covtype。二进制与,,分别。可以看出,线性扩展的迭代次数与训练集的大小。注意,SD-SMO需要更少的迭代收敛,如预期。并为covtype减少更大。二进制文件,因为它更大的价值。在任何情况下,比例是线性的在这两种情况下。
(一)
(b)
5。结论
在本文中,一个新的算法,也就是说,SD-SMO提议。它可以用来为二分类器训练,选择工作集及其理论上证明了渐近收敛。SMO配方基础上,单面融合的路径是有效地使用我们的方法。的迭代次数和内核操作SD-SMO SMO算法比传统的算法,新算法提供了更快的收敛速度。仿真实验已经进行四个基准数据集。实证对比证明SD-SMO算法更有效的计算时间比一阶和二阶SMO,同时没有巨大差异的准确性。
确认
作者要感谢处理编辑和匿名评论者的建设性的评论,导致论文的显著改善。这部分工作是由中国国家自然科学基金支持下批准号51174236。