TL;DR
This paper introduces a novel "bottom-up" method to simplify Support Vector Machines (SVMs) by reducing the number of support vectors (SVs) without sacrificing predictive accuracy. The approach iteratively replaces pairs of similar SVs with a single, representative vector, leading to significantly faster inference times and more interpretable models.
What Problem Does This Paper Address?
Support Vector Machines (SVMs) are powerful tools for classification and regression, known for their excellent generalization capabilities. However, a major drawback of SVMs is their computational cost during the testing phase. This cost is directly proportional to the number of support vectors (SVs) in the trained model. When a new data point is classified, it must be compared against every SV using kernel calculations. For datasets with many SVs, this process can become prohibitively slow, hindering their deployment in real-time applications. Existing "reduced set" methods aim to address this by approximating the original SVM with a smaller set of "reduced vectors," but these methods often suffer from computational complexity, numerical instability, and a tendency to get trapped in local minima during optimization.
Methods
The paper proposes a new "bottom-up" simplification method that iteratively replaces two nearest support vectors (SVs) belonging to the same class with a single, newly constructed vector. This approach contrasts with previous methods that often started by approximating the entire SV set with a single vector and then incrementally added more.
The core of the method involves finding an optimal replacement vector in the feature space. For Gaussian RBF kernels, this involves finding the unique maximum point of a one-variable function on the interval (0,1), which is significantly simpler than the multi-variable optimization problems in prior work. This process is repeated until a desired level of simplification is achieved, controlled by a "Maximum Marginal Difference" (MMD) threshold. The authors also propose a method to recompute the coefficients of the reduced set to ensure optimal performance.
Datasets
The paper evaluates its method on several benchmark datasets:
- USPS handwritten digit recognition database: Used extensively for demonstrating reduction rates and accuracy trade-offs.
- MNIST database of handwritten digits: Used for further evaluation.
- StatLog collection datasets: Including DNA, Letter Recognition, Satimage, and Shuttle, to assess performance across diverse applications.
Key Insights and Ideas
- "Bottom-up" simplification is effective: Instead of trying to approximate the whole solution at once, iteratively merging similar SVs proves to be a more efficient and stable strategy.
- Geometric interpretation of SV simplification: The method leverages the idea that if two forces (representing SVs) are similar, they can be replaced by a single equivalent force without significantly altering the equilibrium of the system (the decision hyperplane).
- One-variable optimization is key: Reducing the complex multi-variable optimization problem to finding the maximum of a one-variable function dramatically simplifies the computation and avoids local minima issues.
- "Meaningful" reduced vectors: The method tends to produce reduced vectors that are more representative of specific classes or patterns, potentially offering better interpretability than vectors from other methods.
- MMD as a controllable trade-off: The Maximum Marginal Difference (MMD) provides a tunable parameter to balance the degree of simplification against potential loss in predictive accuracy.
Key Results
- Significant SV reduction: The proposed method achieved substantial reductions in the number of SVs across various datasets. For instance, on the USPS dataset, reductions of over 90% were reported with minimal loss in accuracy (e.g., 91.3% reduction with 0.2% accuracy loss for polynomial kernels).
- Preservation of generalization performance: Despite significant simplification, the method largely preserved the predictive accuracy of the original SVMs.
- Efficiency gains: The simplification process is computationally less expensive than previous methods, and the resulting simplified models lead to much faster inference times. For example, a speed-up rate of 3.4 to 18.2 times was observed on StatLog datasets.
- Reproducibility: The method's deterministic nature (due to the unique maximum point of the one-variable function) makes results easily reproducible.
Limitations and Future Work
- Computational cost of Phase 2: While Phase 1 (iterative simplification) is efficient, the optional Phase 2 optimization (to further refine coefficients) can be computationally expensive, involving a multivariate optimization problem.
- Selection heuristic: The paper suggests that selecting the two closest SVs of the same class is a good heuristic for simplification. However, the paper acknowledges that other heuristics might exist and could be explored.
- Future work: The authors suggest that other approximation methods could be combined with their reduced set approach for even greater speed-ups in the test phase. They also imply that the "meaningful" nature of the reduced vectors could be further exploited.
Summary updated