Scaling Up Kernel SVM on Limited Resources: A Low-Rank Linearization Approach

Area of Science:

• Machine Learning
• Computational Science

Background:

• Kernel Support Vector Machines (SVMs) excel at nonlinear classification but are computationally intensive for large datasets due to numerous support vectors.
• Linear SVMs are scalable but limited to linearly separable data.

Purpose of the Study:

• To develop a scalable approach for kernel SVMs on resource-limited systems.
• To bridge the gap between the high accuracy of kernel SVMs and the efficiency of linear SVMs.

Main Methods:

• Proposed a novel low-rank linearized SVM approach.
• Transformed nonlinear SVM to linear SVM using an approximate empirical kernel map derived from kernel low-rank decompositions.
• Analyzed the theoretical gap between approximate and optimal rank-k kernel maps, guiding Nyström approximation sampling.
• Extended the method to semisupervised metric learning for improved low-rank embedding with partially labeled data.

Main Results:

• The proposed method inherits the representational power of kernel SVMs and the efficiency of linear SVMs.
• Experimental results show improved robustness and a better trade-off between model representability and scalability compared to state-of-the-art algorithms for large-scale SVMs.

Conclusions:

• Low-rank linearized SVM offers an effective solution for large-scale nonlinear classification problems.
• The approach provides a practical method to leverage kernel methods on limited computational resources.