QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines
QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines
复制标题
DOI：
--
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
D. Hush;P. Kelly;C. Scovel;Ingo Steinwart
中科院分区：
文献类型：
--
作者：
D. Hush;P. Kelly;C. Scovel;Ingo Steinwart
我们描述多项式时间算法，产生近似的解决方案，保证精度的一类QP问题，用于设计的支持向量机分类器。这些算法采用了两个阶段的过程，其中第一阶段产生一个近似的解决方案，一个双QP问题和第二阶段映射这个近似的对偶解决方案的近似原始解。对于第二阶段，我们描述了一个O（nlog n）的算法，该算法将精度为（2（2Km）1/2+8（λ）1/2）-2 λ ep 2的近似对偶解映射到精度为ep的近似原始解，其中n是数据样本的数量，Kn是数据上的最大核值，λ > 0是SVM正则化参数。对于第一阶段，我们提出了新的结果分解算法和描述新的分解算法，保证精度和运行时间。特别地，对于τ-率证明分解算法，我们建立了τ = 1/（n-1）的最优性.此外，我们扩展了Simon（2004）的τ = 1/（n-1）算法，形成了两个新的复合算法，它们也达到了List和Simon（2005）的τ = 1/（n-1）迭代界，但在实践中产生了更快的运行时间。我们还利用这些算法的τ率证明属性，以产生新的停止规则，计算效率高，并保证指定的精度的近似对偶解。此外，对于对应于标准分类问题的双QP问题，我们描述了Simon和复合算法的迭代次数的上限为O（n）的操作条件。对于同一个问题，我们还描述了一般的条件，匹配的下界存在于任何分解算法，使用工作集的大小为2。对于Simon和复合算法，我们还建立了第一阶段的总体运行时间的O（n2）界。结合第一和第二阶段给出了O（n2（ck + 1））的总运行时间，其中ck是执行内核评估的计算的上限。伪代码是一个完整的算法，输入精度EP，并产生一个近似的解决方案，满足这个精度在低阶多项式时间。实验来说明新的停止规则，并比较西蒙和复合分解算法。
We describe polynomial--time algorithms that produce approximate solutions with guaranteed accuracy for a class of QP problems that are used in the design of support vector machine classifiers. These algorithms employ a two--stage process where the first stage produces an approximate solution to a dual QP problem and the second stage maps this approximate dual solution to an approximate primal solution. For the second stage we describe an O(n log n) algorithm that maps an approximate dual solution with accuracy (2(2Km)1/2+8(λ)1/2)-2 λ ep2 to an approximate primal solution with accuracy ep where n is the number of data samples, Kn is the maximum kernel value over the data and λ > 0 is the SVM regularization parameter. For the first stage we present new results for decomposition algorithms and describe new decomposition algorithms with guaranteed accuracy and run time. In particular, for τ-rate certifying decomposition algorithms we establish the optimality of τ = 1/(n-1). In addition we extend the recent τ = 1/(n-1) algorithm of Simon (2004) to form two new composite algorithms that also achieve the τ = 1/(n-1) iteration bound of List and Simon (2005), but yield faster run times in practice. We also exploit the τ-rate certifying property of these algorithms to produce new stopping rules that are computationally efficient and that guarantee a specified accuracy for the approximate dual solution. Furthermore, for the dual QP problem corresponding to the standard classification problem we describe operational conditions for which the Simon and composite algorithms possess an upper bound of O(n) on the number of iterations. For this same problem we also describe general conditions for which a matching lower bound exists for any decomposition algorithm that uses working sets of size 2. For the Simon and composite algorithms we also establish an O(n2) bound on the overall run time for the first stage. Combining the first and second stages gives an overall run time of O(n2(ck + 1)) where ck is an upper bound on the computation to perform a kernel evaluation. Pseudocode is presented for a complete algorithm that inputs an accuracy ep and produces an approximate solution that satisfies this accuracy in low order polynomial time. Experiments are included to illustrate the new stopping rules and to compare the Simon and composite decomposition algorithms.