A Parallel Mixture of SVMs for Very Large Scale Problems

By Ronan Collobert, Samy Bengio, Yoshua Bengio. 2001

465 citations recorded by the source corpus.

Support vector machines (SVMs) are 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 hundred thousand examples with SVMs. This article 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 data set. Experiments on a large benchmark data set (Forest) yielded significant time improvement (time complexity appears empirically to locally grow linearly with the number of examples). In addition, and surprisingly, a significant improvement in generalization was observed.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer (2017, background): “Different types of expert architectures hae been proposed such as SVMs (Collobert et al., 2002), Gaussian Processes (Tresp, 2001; Theis & Bethge, 2015; Deisenroth & Ng, 2015), Dirichlet Processes (Shahbaba & Neal, 2009), and deep networks.”
Fast Inference of Mixture-of-Experts Language Models with Offloading (2023, background): “Since then, many different MoE variants emerged, including mixture of SVM models (Collobert et al., 2002), Dirichlet processes (Shahbaba & Neal, 2009) and various neural networks.”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “, 2009); and a dense one, Covtype (Collobert et al., 2002), with statistics listed in the table below.”
ASAGA: Asynchronous Parallel SAGA (2016, background): “, 2009); and a dense one, Covtype (Collobert et al., 2002), with statistics listed in the table below.”
FrugalML: How to Use ML Prediction APIs More Accurately and Cheaply (2020, methodology): “Substantial research has focused on developing gate function models, such as SVMs [27, 56], Gaussian Process [28, 55], and neutral networks [47, 46].”
Localized multiple kernel learning (2008, methodology): “For example, Collobert et al. (2001) define such a procedure which learns an independent SVM for each subset and reassigns instances to subsets by training a gating model with a cost function.”
Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach (2014, methodology): “The dataset consists of 581,012 points, of which we pick n = 400, 000 as a training set, following the maximum training size in (Collobert et al., 2002).”
Combining SVMs with Various Feature Selection Strategies (2006, background): “Problem covtype2 is also from the UCI repository but is transformed to two classes [11].”
On Markov chain Monte Carlo methods for tall data (2015, methodology): “We consider the dataset covtype.binary described in Collobert et al. (2002).”
Infinite Markov-Switching Maximum Entropy Discrimination Machines (2013, methodology): “To address this issue, recently, a mixture-of-experts (Collobert et al., 2002; Fu et al., 2010; Zhu et al., 2011) model was proposed that uses a set of SVM classifiers, each one trained to perform modeling in a coherent subregion of the observations space.”
Residual Mixture of Experts (2022, unknown): “Various of expert architectures are proposed [10, 12, 43, 48, 51].”
Text detection and recognition in images and video frames (2004, unknown): “Support vector machine (SVMs) SVMs are a technique motivated by statistical learning theory which have shown their ability to generalize well in high-dimensional spaces [24,25], such as those spanned by the texture patterns of characters.”
Laplace Propagation (2003, methodology): “In the following we show that SVM chunking [4] and parallel SVM training [2] can be found to be special cases of LP.”
A Variance Reduced Stochastic Newton Method (2015, methodology): “We apply least-square regression on the binary version of the cov dataset (Collobert et al., 2002).”
Parallel Support Vector Machines: The Cascade SVM (2004, background): “Parallelizations have been proposed by splitting the problem into smaller subsets and training a network to assign samples to different subsets [9].”
Learning to Compose Topic-Aware Mixture of Experts for Zero-Shot Video Captioning (2018, methodology): “Then MoE has been applied to various machine learning algorithms (Jordan and Jacobs 1994; Collobert, Bengio, and Bengio 2003), such as SVMs (Collobert, Bengio, and Bengio 2002), Gaussian Processes (Tresp 2001), and deep networks (Ahmed, Baig, and Torresani 2016; Gu et al. 2018).”