So a fair bit of this paper goes into detail about the technical details and infrastructure. This is commendable, because these details are important in applied work.
The authors devise a method for large-scale supervised classification. Essentially, the data is partitioned between nodes, and each node trains a l2-regularized logistic model on its data using SGD. The individual models are then aggregated into an ensemble. This approach is obvious but non-standard (I'll describe why later).
I believe this methodology is of limited applicability. The experiments are supervised training of sentiment analysis on 100M tweets. But it is simple and fast to do supervised learning over 1B instances on a single box. And there are very few tasks that have >>1B labeled training examples.
In most "large-scale" real-world tasks, there are 10-1M labeled training examples, and 100M to jillions unlabelled training examples. So what we really care about is unsupervised learning (over unlabelled examples) followed by supervised learning (over labelled examples) or semi-supervised learning (over unlabelled and labelled examples). Distributed unsupervised learning is challenging. It is an active research area with only a few results, and a lot of untapped potential.
One claim in the paper is surprising: "As is often the case for many machine learning problems, and confirmed in our experiments (see Section 6), an ensemble of classifiers trained on partitions of a large dataset outperforms a single classifier trained on the entire dataset (more precisely, lowers the variance component in error)." First of all, I'm surprised by the claim "an ensemble of classifiers trained on partitions of a large dataset outperforms a single classifier trained on the entire dataset". It is true that an ensemble (forest) of decision trees is better than a single decision tree. This is like adding another layer in a neural network, and allows more powerful models to be expressed more compactly. But, crucially, an ensemble of linear models is just a linear model. So in fact, there should be no variance reduction in the authors' approach. It should be better to train a single linear model on ALL the data, rather than an ensemble of linear models on subsets of the data. I am surprised that the ensemble of linear models outperforms the single model. Further investigation is needed to understand why. My gut feeling is that there is a problem in his experiment.
tl;dr The machine learning models will have limited impact, because they are purely supervised. But check out the technical details and infrastructure portion of the paper.
* But, crucially, an ensemble of linear models is just a linear model. So in fact, there should be no variance reduction in the authors' approach. *
You are right. But I disagree that " It should be better to train a single linear model on ALL the data " - because its impractical to find the right parameters for your training method. Since this is a large data problem, I assume author's are using a parametric optimization routine? - Hence a practical solution is to learn multiple linear models using different parameters and using different subsets of the data.
What you are talking about is hyperparameter optimization.
For example, in a typical l2-legularized logreg model (like in this paper), there is a single hyperparameter which controls the strength of the regularizer.
What we typically do is train one model for each choice of hyperparameters, perhaps doing a line-search if its a single hyperparameter. This hyperparameter optimization is "embarrassingly parallel", to use a term of art. So if you have multiple machines, each one uses a different hyperparameter and no Hadoop is necessary. I wouldn't be surprised if this approach is over twenty years old. Choosing the hyperparameter over ALL the data and training a linear model of ALL the data should be superior training an ensemble of models over subsets of data, and picking hyperparameters over subsets.
On interesting area of research is when there are many hyperparameters, particularly for non-linear models. For example, in training a deep neural network, there are many hyperparameters, and it becomes prohibitive to do exhaustive hyperparameter selection. Randomization is one good strategy. James Bergstra has done some recent work on improving hyperparameter selection. If you used a smart technique to guide the search within the hyperparameter space, and had one "master" node that gave hyperparameters to the worker nodes, and this master node did the hyperparameter search, that would be a sophisticated and useful technique.
> an ensemble of linear models is just a linear model
Doesn't this depend on how they aggregate the results? In the paper they say that they do majority voting and averaging of the class probabilities, and in both cases the decision surface is not linear (before averaging, in the first case the response of the linear model is passed through a step function, in the second case through a logistic function)
I think what you say is true in a regression setting, if you just average the predictions of the linear models, but here they are talking about classification.
You are right that they are applying a non-linear function (step-function or logistic) to the output of a linear model, and then aggregating. I am not sure if this has equivalent modeling power as a linear model or single logreg model. I suspect it does, but haven't done the math.
I am not aware of results that say that an ensemble of linear or logreg models, trained over partitions of the data, is better than a single linear or logreg model trained over all the data. My understanding was that the opposite was true. Most of the positive results for ensemble methods and bagging are when the base classifier is a decision splits and decision trees, in which case it is clear that the ensemble has more modeling power.
You are correct, it can represent more decision surfaces.
takes off theoretician's hat
In practice, my intuition tells me that aggregating over an ensemble of logreg models trained on subsets of the data is inferior to training a single logreg model over the entire data.
It looks like a linear combination of shifted step functions/logistics. That's a complete set - it can represent any function to arbitrary accuracy. I agree that in practice you won't necessarily get better results, though.
Also check out these slides by John Langford from a recent workshop. The first example is distributed training of a linear model from 17B examples in 70 minutes.
11 comments
[ 6.9 ms ] story [ 40.8 ms ] threadSo a fair bit of this paper goes into detail about the technical details and infrastructure. This is commendable, because these details are important in applied work.
The authors devise a method for large-scale supervised classification. Essentially, the data is partitioned between nodes, and each node trains a l2-regularized logistic model on its data using SGD. The individual models are then aggregated into an ensemble. This approach is obvious but non-standard (I'll describe why later).
I believe this methodology is of limited applicability. The experiments are supervised training of sentiment analysis on 100M tweets. But it is simple and fast to do supervised learning over 1B instances on a single box. And there are very few tasks that have >>1B labeled training examples.
In most "large-scale" real-world tasks, there are 10-1M labeled training examples, and 100M to jillions unlabelled training examples. So what we really care about is unsupervised learning (over unlabelled examples) followed by supervised learning (over labelled examples) or semi-supervised learning (over unlabelled and labelled examples). Distributed unsupervised learning is challenging. It is an active research area with only a few results, and a lot of untapped potential.
One claim in the paper is surprising: "As is often the case for many machine learning problems, and confirmed in our experiments (see Section 6), an ensemble of classifiers trained on partitions of a large dataset outperforms a single classifier trained on the entire dataset (more precisely, lowers the variance component in error)." First of all, I'm surprised by the claim "an ensemble of classifiers trained on partitions of a large dataset outperforms a single classifier trained on the entire dataset". It is true that an ensemble (forest) of decision trees is better than a single decision tree. This is like adding another layer in a neural network, and allows more powerful models to be expressed more compactly. But, crucially, an ensemble of linear models is just a linear model. So in fact, there should be no variance reduction in the authors' approach. It should be better to train a single linear model on ALL the data, rather than an ensemble of linear models on subsets of the data. I am surprised that the ensemble of linear models outperforms the single model. Further investigation is needed to understand why. My gut feeling is that there is a problem in his experiment.
tl;dr The machine learning models will have limited impact, because they are purely supervised. But check out the technical details and infrastructure portion of the paper.
You are right. But I disagree that " It should be better to train a single linear model on ALL the data " - because its impractical to find the right parameters for your training method. Since this is a large data problem, I assume author's are using a parametric optimization routine? - Hence a practical solution is to learn multiple linear models using different parameters and using different subsets of the data.
For example, in a typical l2-legularized logreg model (like in this paper), there is a single hyperparameter which controls the strength of the regularizer.
What we typically do is train one model for each choice of hyperparameters, perhaps doing a line-search if its a single hyperparameter. This hyperparameter optimization is "embarrassingly parallel", to use a term of art. So if you have multiple machines, each one uses a different hyperparameter and no Hadoop is necessary. I wouldn't be surprised if this approach is over twenty years old. Choosing the hyperparameter over ALL the data and training a linear model of ALL the data should be superior training an ensemble of models over subsets of data, and picking hyperparameters over subsets.
On interesting area of research is when there are many hyperparameters, particularly for non-linear models. For example, in training a deep neural network, there are many hyperparameters, and it becomes prohibitive to do exhaustive hyperparameter selection. Randomization is one good strategy. James Bergstra has done some recent work on improving hyperparameter selection. If you used a smart technique to guide the search within the hyperparameter space, and had one "master" node that gave hyperparameters to the worker nodes, and this master node did the hyperparameter search, that would be a sophisticated and useful technique.
[edit: spelling]
Doesn't this depend on how they aggregate the results? In the paper they say that they do majority voting and averaging of the class probabilities, and in both cases the decision surface is not linear (before averaging, in the first case the response of the linear model is passed through a step function, in the second case through a logistic function)
I think what you say is true in a regression setting, if you just average the predictions of the linear models, but here they are talking about classification.
You are right that they are applying a non-linear function (step-function or logistic) to the output of a linear model, and then aggregating. I am not sure if this has equivalent modeling power as a linear model or single logreg model. I suspect it does, but haven't done the math.
I am not aware of results that say that an ensemble of linear or logreg models, trained over partitions of the data, is better than a single linear or logreg model trained over all the data. My understanding was that the opposite was true. Most of the positive results for ensemble methods and bagging are when the base classifier is a decision splits and decision trees, in which case it is clear that the ensemble has more modeling power.
You are correct, it can represent more decision surfaces.
takes off theoretician's hat
In practice, my intuition tells me that aggregating over an ensemble of logreg models trained on subsets of the data is inferior to training a single logreg model over the entire data.
I apologize for being sloppy tho.
"3 Fun Machine Learning Problems for Big Data"
http://people.cs.umass.edu/~mcgregor/stocworkshop/langford.p...