Abstract
Training Support Vector Machines (SVMs) on large-scale datasets has traditionally been limited by $O(m^3)$ time and $O(m^2)$ space complexities. This paper presents the Core Vector Machine (CVM), a novel approach that reformulates the SVM training problem as a Minimum Enclosing Ball (MEB) problem in computational geometry. By leveraging "core-sets"—small subsets of data that approximate the entire set's geometry—the CVM achieves linear training time and memory requirements that are independent of the total number of training samples. Empirical evaluations on datasets with up to one million points show that CVM provides a scalable solution for massive kernel-based learning tasks.
Introduction
The power of Support Vector Machines (SVMs) is often offset by their poor scalability. As the number of training examples $m$ grows, the computational cost of solving the underlying Quadratic Programming (QP) problem becomes prohibitive. Standard solvers like LIBSVM, while highly optimized, still struggle with datasets in the millions due to the "curse of the kernel matrix." The Core Vector Machine (CVM) addresses this by shifting the optimization perspective from algebraic to geometric.
Methods: The Minimum Enclosing Ball Problem
The core innovation of the CVM is the realization that L2-norm SVM training is mathematically equivalent to finding the Minimum Enclosing Ball (MEB) in a high-dimensional feature space. The MEB is the smallest sphere that contains all data points.
The Core-Set Algorithm
To solve the MEB problem efficiently, the authors utilize an iterative core-set algorithm. A core-set is a small subset of points such that the MEB of the core-set, when expanded by a factor of $(1+\epsilon)$, contains all points in the original dataset. The algorithm proceeds as follows:
- Initialize with a small core-set.
- Identify the point furthest from the current ball's center.
- Update the core-set and recompute the MEB.
- Terminate when all points are within the $(1+\epsilon)$ boundary.
Crucially, the size of the core-set depends only on the approximation parameter $\epsilon$ and is independent of both the number of data points $m$ and the dimensionality of the feature space.
Probabilistic Speedup
To further enhance efficiency, the authors employ a probabilistic sampling strategy. Instead of scanning the entire dataset to find the absolute furthest point in each iteration, they sample a small constant number of points (e.g., 59). This ensures that with high probability (95%), they find a point that is among the furthest 5%, maintaining the algorithm's convergence properties while drastically reducing per-iteration costs.
Experimental Evaluation
The authors compared CVM against established solvers like LIBSVM, RSVM, and SimpleSVM across several datasets:
- Checkerboard: A synthetic dataset scaled to 1 million points.
- Forest Cover Type: A real-world dataset with ~522,000 patterns.
- UCI Adult: A standard benchmark with ~32,000 patterns.
Key Results
The experiments confirmed the theoretical advantages of the CVM. On the 1-million-point checkerboard dataset, CVM completed training in under 13 seconds on standard hardware, demonstrating clear linear scaling where other methods failed or slowed down significantly.
As shown in the figures above:
- CPU Time: CVM maintains nearly constant or linear training time as the dataset size increases, while other methods exhibit super-linear growth.
- Sparsity: The number of Support Vectors (SVs) found by CVM remains relatively constant (the "core-set size"), leading to faster inference during testing.
- Accuracy: Despite the $(1+\epsilon)$ approximation, CVM maintains testing error rates comparable to exact solvers.
Conclusion
The Core Vector Machine represents a significant leap in scaling kernel methods. By adopting a geometric core-set approach, it bypasses the traditional bottlenecks of SVM training. While highly optimized heuristics may still be faster for small datasets, CVM is the superior choice for "very large" datasets where traditional methods become computationally infeasible. Future work includes extending this framework to Support Vector Regression and other kernel-based algorithms.
Summary updated