A Parallel Mixture of SVMs for Very Large Scale Problems

Ronan Collobert, Samy Bengio, Yoshua Bengio

Support Vector Machines (SVMs) are powerhouses of machine learning, renowned for their strong generalization capabilities. However, they have a significant scaling problem. The training complexity of a standard SVM is at least quadratic ($O(N^2)$) relative to the number of training examples ($N$). While an SVM is highly effective for 10,000 examples, scaling up to 1,000,000 examples causes training time to become astronomical. This "quadratic barrier" has historically locked SVMs out of the very large-scale problems that define modern data science.

To overcome this, researchers have proposed a parallelizable Conditional Mixture of SVMs. By dividing large datasets into smaller subsets and using a neural network "gater" to coordinate specialized SVM experts, this approach achieves near-linear training complexity and, surprisingly, can even yield better accuracy than a single global model.

The Divide-and-Conquer Architecture

Instead of training one massive SVM on an entire dataset, the proposed architecture relies on a divide-and-conquer strategy:

  1. The Experts and the Gater: The model consists of $M$ "experts" (each a small SVM) and one "gater" (a Multi-Layer Perceptron neural network). For any given input, the gater decides which expert's prediction should carry the most weight.
  2. Parallel Training: The training set is initially split into $M$ random subsets. Each SVM expert is trained only on its assigned subset. Because these subsets are small, training is incredibly fast and "embarrassingly parallel," making it ideal for modern multi-core clusters.
  3. Intelligent Re-assignment: After initial training, the gater learns to minimize overall error by identifying which expert performs best on which types of data. Data points are then reassigned to the experts that handle them best. The process loops back to re-train the experts on these new, specialized subsets.

By keeping the size of the subsets constant as the total dataset grows (simply by increasing the number of experts), the training time for the experts scales linearly ($O(N)$) rather than quadratically.

Visualizing the Mixture on Datasets

The researchers evaluated their approach across several distinct problems, starting with an artificial 2D non-linear classification task. This toy problem perfectly visualizes how the gater combines simple linear experts to create complex decision boundaries that a single linear or Gaussian SVM might struggle to optimize efficiently.

Comparison of decision boundaries: (a) Linear SVM, (b) Gaussian SVM, and (c) Mixture of two linear SVMs.

Beyond toy problems, the model was tested on two massive real-world datasets:

  • UCI Forest Cover Type: A large-scale dataset with over 500,000 examples and 54 features, modified into a binary classification problem.
  • Numbers95: A speech recognition database containing roughly 540,000 frames, where the task was to distinguish between silence and non-silence frames using 135 input features.

Key Insights and Performance Leaps

The quantitative results highlight a massive leap in efficiency. On the Forest dataset, the mixture was roughly 13x faster on a single CPU and 44x faster when parallelized across 50 CPUs.

Model Dataset Test Error Time (1 CPU) Time (50 CPUs)
Single SVM Forest 16.76% 3231 mins N/A
Gated SVM Mixture Forest 9.28% 237 mins 73 mins
Single SVM Speech 7.57% 6787 mins N/A
Gated SVM Mixture Speech 7.32% 851 mins 65 mins

Linear Scaling and Specialization: The most significant finding is that training time appears to grow linearly with the number of examples. The iterative loop of reassigning data points allows experts to specialize in specific regions of the input space, making the "mixture" far more capable than the sum of its parts.

Surprising Generalization: On the Forest dataset, the mixture didn't just run faster; it performed significantly better (9.28% test error) than a single global SVM (16.76%). This suggests that for highly complex datasets, a committee of local specialists can outperform one global generalist. The architecture's performance is closely tied to the number of experts and the complexity of the gater, as seen in the validation error landscape.

Validation error as a function of the number of hidden units in the gater and the number of experts.

Limitations and Future Work

While the experts scale linearly, the gater is trained on the whole dataset. If the gater's training time grows too quickly, it could eventually become the new bottleneck for multi-million example datasets. Furthermore, in this study, all experts shared the same hyper-parameters. Tuning these individually for each expert could yield even better results. Finally, while empirical convergence was rapid (often within 5 iterations), providing theoretical guarantees for the gater's training time remains an open area for future exploration.

Summary updated

Abstract

Support Vector Machines (SVMs) are currently the state-of-the-art models for many classification problems but they suffer from the complexity of their train(cid:173) ing algorithm which is at least quadratic with respect to the number of examples. Hence, it is hopeless to try to solve real-life problems having more than a few hundreds of thousands examples with SVMs. The present paper proposes a new mixture of SVMs that can be easily implemented in parallel and where each SVM is trained on a small subset of the whole dataset. Experiments on a large benchmark dataset (Forest) as well as a difficult speech database, yielded significant time improvement (time complexity appears empirically to locally grow linearly with the number of examples) . In addition, and that is a surprise, a significant improvement in generalization was observed on Forest.
BibTeX
@article{collobert2002parallel,
  author = {Ronan Collobert and Samy Bengio and Yoshua Bengio},
  title = {{A Parallel Mixture of SVMs for Very Large Scale Problems}},
  journal = {Neural Computation},
  year = {2002},
  doi = {10.1162/089976602753633402},
}
Figure