Download

R. Collobert, S. Bengio, and Y. Bengio. A Parallel Mixture of SVMs for Very Large Scale Problems. In T.G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, NIPS 14. MIT Press, 2002.

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 training 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

@inproceedings{collobert:2002a,
  author = {R. Collobert and S. Bengio and Y. Bengio},
  title = {A Parallel Mixture of {SVMs} for Very Large Scale Problems},
  booktitle = {Advances in Neural Information Processing Systems, {NIPS} 14},
  year = {2002},
  pages = {633--640},
  editor = {Dietterich, T.G. and Becker, S. and Ghahramani, Z.},
  publisher = {MIT Press}
}

Notes

This is our first paper on Mixture of SVMs. The aim was to use a divide-and-conquer method to break up the SVM complexity and solve large scale classification tasks. While these mixtures do work, they are unfortunately quite difficult to tune, because of the additional hyper-parameters involved in the architecture.

A variant of this paper, with more experiments, has been published in Neural Computation.

An extended version, including more experiments and probabilistic mixtures has been published in IJPRAI and presented at SVM'2002.