Sparse LSSVM in Primal Using Cholesky Factorization for Large-Scale Problems
Sparse LSSVM in Primal Using Cholesky Factorization for Large-Scale Problems
复制标题
DOI：
10.1109/tnnls.2015.2424684
复制
发表时间：
2016-04
影响因子：
10.4
通讯作者：
Shuisheng Zhou
中科院分区：
文献类型：
--
作者：
Shuisheng Zhou
在支持向量机（SVM）学习中，由对偶LSSVM （D-LSSVM）导出的最小二乘支持向量机（LSSVM）模型由于具有显式解而被广泛使用。该模型的一个明显限制是解决方案缺乏稀疏性，这限制了它无法有效地训练大规模问题。本文利用表征定理导出了原始空间中等价的LSSVM （P-LSSVM）模型，并证明了对于低秩核矩阵问题，P-LSSVM可以在某些稀疏解处精确求解。提出了两种用Cholesky分解寻找P-LSSVM稀疏（近似）解的算法。一种是将核矩阵K近似分解为PPT，通过旋转Cholesky分解得到最佳低秩矩阵P。另一种是基于用秩一更新方案逼近Hessian矩阵的Cholesky分解来求解P-LSSVM。对于线性学习问题，理论分析和实验结果都支持P-LSSVM可以给出所有SVM学习器中最稀疏的解。在一些大规模非线性训练问题上的实验结果表明，基于P-LSSVM的算法可以收敛到非常稀疏解下可接受的测试精度，稀疏度水平<；1%，甚至低至0.01%。因此，我们的算法对于大规模训练问题是一个更好的选择。
For support vector machine (SVM) learning, least squares SVM (LSSVM), derived by duality LSSVM (D-LSSVM), is a widely used model, because it has an explicit solution. One obvious limitation of the model is that the solution lacks sparseness, which limits it from training large-scale problems efficiently. In this paper, we derive an equivalent LSSVM model in primal space LSSVM (P-LSSVM) by the representer theorem and prove that P-LSSVM can be solved exactly at some sparse solutions for problems with low-rank kernel matrices. Two algorithms are proposed for finding the sparse (approximate) solution of P-LSSVM by Cholesky factorization. One is based on the decomposition of the kernel matrix K as PPT with the best low-rank matrix P approximately by pivoting Cholesky factorization. The other is based on solving P-LSSVM by approximating the Cholesky factorization of the Hessian matrix with rank-one update scheme. For linear learning problems, theoretical analysis and experimental results support that P-LSSVM can give the sparsest solutions in all SVM learners. Experimental results on some large-scale nonlinear training problems show that our algorithms, based on P-LSSVM, can converge to acceptable test accuracies at very sparse solutions with a sparsity level <;1%, and even as little as 0.01%. Hence, our algorithms are a better choice for large-scale training problems.