Abstract
Kernel Support Vector Machine (SVM) delivers state-of-the-art results in non-linear classification, but the need to maintain a large number of support vectors poses a challenge in large-scale training and testing. In contrast, linear SVM is much more scalable even on limited computing resources, but the learned model cannot capture non-linear concepts. To scale up kernel SVM on limited resources, we propose a low-rank linearization approach that transforms a non-linear SVM to a linear one via a novel, approximate empirical kernel map computed from efficient low-rank approximation of kernel matrices. We call it LLSVM (Low-rank Linearized SVM). Our algorithm inherits the high efficiency of linear SVMs and the rich representability of kernel classifiers. Evaluation against large-scale linear and kernel SVMs on several truly large datasets shows that the proposed method achieves a better tradeoff between scalability and model representability.
The Scalability Bottleneck in Kernel SVMs
Kernel SVMs are powerful tools for non-linear classification, yet they suffer from the "curse of kernelization." While linear SVMs can scale to millions of data points using modern solvers, they often fail to capture complex, non-linear patterns. Kernel methods address this by mapping data into high-dimensional spaces, but this requires computing and storing an $n \times n$ kernel matrix. As datasets grow, the number of support vectors typically increases, leading to significant computational and memory overhead. For instance, training a standard kernel SVM on millions of samples can take days even on high-performance clusters, making it impractical for users with limited resources like standard desktop PCs.
Methodology: Low-rank Linearized SVM (LLSVM)
The LLSVM approach bridges the gap between non-linear representability and linear scalability through a two-step transformation:
- Low-Rank Linearization: The authors demonstrate that a kernel SVM can be mathematically reformulated as a linear SVM by decomposing the kernel matrix. Since exact decomposition is computationally prohibitive ($O(n^3)$), LLSVM utilizes the Nyström method. It selects a small set of $k$ "landmark" points—optimized via fast k-means clustering—to generate an approximate, low-dimensional empirical kernel map. This projects the data into a $k$-dimensional linear space where $k \ll n$.
- Fast Linear Optimization: With the data explicitly mapped, the problem is solved using Selective Block Minimization (SBM), a state-of-the-art linear SVM solver designed for out-of-core learning, allowing it to handle datasets larger than the available RAM.
Experimental Results
The LLSVM algorithm was evaluated on several large-scale datasets, including IJCNN, webspam, covType, and Ncheckerboard. The results highlight a superior balance between efficiency and accuracy:
- Massive Scalability: On the 8-million sample
mnist8m-bdataset, standard kernel solvers failed to complete within 24 hours. LLSVM successfully trained in 22 hours with a 2.59% error rate on a standard PC. On the noisyNcheckerboard(800k samples), LLSVM achieved a 0.59% error rate in just 429 seconds. - Improved Accuracy over Linear Models: LLSVM significantly outperformed linear SVMs where non-linearity is crucial. For the
covTypedataset, the error rate dropped from 23.75% (linear SVM) to 14.95% (LLSVM). - Efficient Inference: By reducing the model to a linear form based on $k$ landmark points, LLSVM offers drastically faster prediction times compared to traditional kernel SVMs that rely on a large number of support vectors.
Conclusion
LLSVM provides a practical framework for training high-performance non-linear classifiers on large datasets using modest hardware. By shifting the computational burden from the SVM optimizer to an efficient matrix approximation step, it enables the use of kernel methods in scenarios previously reserved for linear models. Future work includes exploring parallelization and extending the linearization framework to semi-supervised learning and metric learning tasks.
Summary updated