Lecture
Ensemble methods in statistics and machine learning use several learning algorithms in order to obtain better predictive performance[en] than could be obtained from any of the constituent learning algorithms alone. Unlike a statistical ensemble in statistical mechanics, which is usually infinite, an ensemble of methods in machine learning consists of a specific, finite set of alternative models, but, typically, allows substantially more flexible structures to exist.
Supervised learning algorithms are most often described as performing the task of searching through a hypothesis space to find a suitable hypothesis that makes good predictions for a particular problem. Even if the hypothesis space contains hypotheses that are very well suited for a particular problem, it may be difficult to find a good hypothesis. Ensemble methods combine several hypotheses in the hope of forming a better hypothesis. The term ensemble is usually reserved for methods that generate several hypotheses using the same base learner. The broader term multiple classifier systems also refers to methods that use several hypotheses, but which are not generated using the same learner.
Computing the prediction of an ensemble usually requires more computation than the prediction of a single model, so ensembles can be regarded as a way of compensating for a poor learning algorithm by performing extra computation. Ensemble methods usually use fast algorithms, such as decision trees[en] (for example, random forests), although slow algorithms can also gain advantages from the ensembling technique.
By analogy, the ensembling technique is also used in unsupervised learning scenarios, for example, in consensus-based clustering[en] or in anomaly detection.
An ensemble is itself a supervised learning algorithm, because it can be trained and then used to make predictions. The trained ensemble, therefore, represents a single hypothesis. This hypothesis, however, does not necessarily lie within the hypothesis space of the models from which it is built. Thus, ensembles can have greater flexibility in the functions they can represent. In theory, this flexibility can make them more prone to overfitting the training data than would be the case for an individual model, but, in practice, some ensembling techniques (especially bagging) tend to reduce problems related to overfitting on the training data.
Empirically, ensembles tend to yield better results when there is significant diversity among the models. Many ensemble methods, therefore, try to increase the diversity of the models they combine. Although, perhaps counterintuitively, more random algorithms (such as random decision trees) can be used to obtain stronger ensembles than well-designed algorithms (such as decision trees with entropy reduction). Using different strong-learning algorithms, however, has been shown to be more effective than using techniques that try to simplify the models in order to achieve greater diversity.
While the number of classifiers in an ensemble has a large influence on prediction accuracy, there are only a limited number of papers studying this problem. Determining the ensemble size a priori and the throughput rates of large data streams makes this factor even more critical for online ensemble classifiers. Most statistical tests have been used to determine the appropriate number of components. Relatively recently, a theoretical framework has suggested that there is an ideal number of ensemble classifiers, such that a number of classifiers greater or smaller than this ideal number leads to a degradation in accuracy. This is called the «law of diminishing returns in ensemble construction». This theoretical framework shows that using a number of independent classifiers equal to the number of class labels gives the highest accuracy[10][11].
The Bayes optimal classifier is a classification technique. It is an ensemble of all the hypotheses in the hypothesis space. On average, no other ensemble can outperform it[12]. The naive Bayes optimal classifier is a version that assumes the data are conditionally independent of the class, and performs the computation in a more realistic time. Each hypothesis is given a vote proportional to the probability that the training data would be sampled from the system if that hypothesis were true. To obtain training data of finite size, the vote of each hypothesis is multiplied by the prior probability of that hypothesis. The Bayes optimal classifier can be expressed by the following equation:
,
where 
is the predicted class, 
is the set of all possible classes, 
is the hypothesis class, 
refers to probability, and 
is the training data. As an ensemble, the Bayes optimal classifier represents a hypothesis that does not necessarily belong to . The hypothesis represented by the Bayes optimal classifier, however, is the optimal hypothesis in ensemble space (the space of all possible ensembles consisting only of hypotheses in the space ).
The formula can be rewritten using Bayes' theorem, which states that the posterior probability is proportional to the prior probability:
from which
Bootstrap aggregating, often abbreviated to bagging, gives each model in the ensemble equal weight (vote). To maintain variance, bagging trains each model in the ensemble using a randomly sampled subset of the training set. As an example, the «random forest» algorithm combines random decision trees with bagging to achieve high classification accuracy[13].
Boosting builds the ensemble incrementally, in sequence, by training each new model to emphasize the training instances that previous models classified incorrectly. In some cases, boosting has been shown to give better results than bagging, but it tends to overfit the training data. The most common implementation of boosting is the AdaBoost algorithm, although there are claims that some newer algorithms give better results.
Bayesian parameter averaging (BPA) is an ensembling technique that attempts to approximate the Bayes optimal classifier by sampling from the hypothesis space and combining them using Bayes' law[14]. Unlike the Bayes optimal classifier, the Bayesian parameter averaging model can be implemented in practice. Hypotheses are usually sampled using a Monte Carlo technique, such as MCMC[en]. For example, Gibbs sampling can be used to sample hypotheses that represent the distribution 
. It has been shown that under certain circumstances, when hypotheses are selected in this way and averaged according to Bayes' law, this technique has an expected error that is bounded by twice the expected error of the Bayes optimal classifier[15]. Despite the theoretical soundness of this technique, early work based on experimental data suggested that the method tends to overfit and performs worse than simple ensembling techniques such as bagging[16]. However, these conclusions were based on a misunderstanding of the purpose of Bayesian model averaging for model combination[17]. Moreover, there are significant advantages in both the theory and practice of BMA. Recent rigorous proofs demonstrate the accuracy of BMA for variable selection and estimation under high-dimensional conditions[18] and provide empirical evidence of the essential role of enforcing sparsity in BMA for mitigating overfitting[19].
Bayesian model combination (BMC) is an algorithmic correction to Bayesian model averaging (BMA). Instead of selecting each model for the ensemble individually, the algorithm samples from the space of possible ensembles (with model weights drawn randomly from a Dirichlet distribution with uniform parameters). This modification avoids BMA's tendency to give full weight to a single model. Although BMC is somewhat more computationally expensive than BMA, it has been shown to give substantially better results. On average, BMC results have been shown to be better than both BMA and bagging[20].
Using Bayes' law to compute model weights inevitably involves computing the probability of the data for each model. Usually, none of the models in the ensemble has exactly the same distribution as the training data from which they were generated, so all members correctly obtain a value close to zero. This would work well if the ensemble were large enough to sample the full space of models, but this is rarely feasible. Consequently, each member of the training set causes the ensemble's weight to shift toward the model in the ensemble that is closest to the distribution of the training data. This substantially reduces the need for an overly complex model-selection method.
The possible weights for the ensemble can be represented as lying on a simplex. At each vertex of the simplex, all the weight is assigned to a single model in the ensemble. BMA converges to the vertex that is closest in distribution to the training data. By contrast, BMC converges to the point where this distribution is projected onto the simplex. In other words, instead of selecting the single model closest to the distribution, the method looks for the combination of models closest to the distribution.
BMA results can often be approximated using cross-validation to select a model from a bucket of models. Similarly, BMC results can be approximated using cross-validation to select the best ensemble combination from a random sample of possible weights.
«Bucket of models» is an ensembling technique that uses a model-selection algorithm to obtain the best model for each task. When only a single task is tested, a bucket of models cannot give a better result than the best model in the set, but when run over several tasks, the algorithm generally gives better results than any single model in the set.
The most common approach used for model selection is cross-validation. It is described by the following pseudocode:
For each model in the bucket:
Do c times: (where 'c' is some constant)
Randomly split the training data into two sets: A and B.
Train m on A
Test m on B
Choose the model with the highest average result
Cross-validation can be described as: «run them all on the training set and pick the one that works best»[21].
Gating is a generalization of cross-validation. The method involves training another learning model to decide which of the models in the bucket is best suited to solving the task. A perceptron is often used for gating. It can be used to select the «best» model, or it can be used to obtain a linear weighting of the predictions from each model in the bucket.
When a bucket of models is used with a large set of tasks, it may be desirable to avoid training some models that require a long training time. Landmark learning is a meta-learning approach that seeks to address this problem. It involves training only fast (but inaccurate) algorithms, and then using the performance of these algorithms to determine which of the slow (but accurate) algorithms to select as the best one[22].
Stacking (sometimes called stacked generalization) involves training a learning algorithm to combine the predictions of several other learning algorithms. First, all the other algorithms are trained using the available data, then a combining algorithm is trained to make a final prediction using all the predictions of the other algorithms as an additional input. If an arbitrary combining algorithm is used, then stacking can theoretically represent any ensembling technique described in this article, although, in practice, a logistic regression model is often used as the combining algorithm.
Stacking generally gives better performance than any single one of the trained models[23]. It has been used successfully in both supervised learning tasks (regression[24], classification, and distance learning[25]) and unsupervised learning tasks (density estimation)[26]. It has also been used to estimate the error of bagging[27]. It has been claimed that the method outperformed Bayesian model averaging[28]. Two of the top finishers in the Netflix Prize competition used blending, which can be regarded as a form of stacking[29].
In recent years, owing to the growing computational power that allows large training ensembles to be trained in a reasonable time, the number of applications has been growing ever faster[35]. Some applications of classifier ensembles are given below.
Land cover mapping
Land cover mapping[en] is one of the main applications of Earth observation[en], using remote sensing and geographic data[en] to recognize objects located on the surface of target areas. Typically, target material classes include roads, buildings, rivers, lakes, and vegetation[36]. Several different ensemble learning approaches have been proposed, based on artificial neural networks[37], kernel principal component analysis (KPCA)[38], boosted decision trees[39], random forests[36], and automatic design of multiple classifier systems[40], for the effective recognition of land cover objects.
Change detection
Change detection[en] is an image analysis[en] task consisting in identifying places where land cover has changed over time. Change detection[en] is widely used in fields such as urban growth[en], dynamics of change in forests and vegetation[en], land use, and natural-disaster detection[en][41]. Early applications of classifier ensembles to change detection were developed using majority voting[en], Bayesian averaging[en], and maximum a posteriori estimation[42].
DoS attack
A distributed denial-of-service attack is one of the most threatening cyberattacks that can happen to an internet provider[35]. By combining the output of individual classifiers, a classifier ensemble reduces the overall detection error and separates such attacks from legitimate flash crowds[43].
Malware detection
Classification of malware code, such as computer viruses, network worms, trojans, ransomware, and spyware, using machine learning techniques, is inspired by the task of document categorization[44]. Ensemble learning systems have shown reliable performance in this field
Intrusion detection
An intrusion detection system monitors a computer network or computers to identify intrusion codes, similarly to the process of anomaly detection. Ensemble learning successfully helps such systems reduce the overall number of errors
Face recognition
Face recognition, which has recently become the most popular area of research in pattern recognition, deals with identifying or verifying a person's identity from his/her digital image[49].
Hierarchical ensembles based on the Gabor-Fisher classifier and independent component analysis[en] data-preprocessing techniques are among the early ensembles used in this field
While speech recognition is mainly based on deep learning, since most industry players in this field, such as Google, Microsoft, and IBM, use it as the basis of their speech-recognition technology, speech-based emotion recognition[en] can achieve satisfactory results with ensemble learning
The method has also been used successfully in facial emotion recognition
Fraud detection deals with identifying bank fraud[en], such as money laundering, payment-card fraud, and telecommunications fraud. Fraud detection offers wide scope for research and application of machine learning. Because ensemble learning improves the robustness of normal-behavior modeling, it has been proposed as an effective technique for identifying such cases of fraud and suspicious activity in banking operations in credit-card systems
The accuracy of predicting commercial bankruptcy is a critical issue in financial decision-making, so various classifier ensembles have been proposed for predicting financial crises and financial bankruptcies[en][60]. Also in the task of trade-based manipulation[en], where traders attempt to manipulate stock prices by buying or selling, a classifier ensemble is required to analyze changes in securities-market data and identify symptoms of suspicious stock-price manipulation[en][60].
Classifier systems have been successfully applied in neuroscience, proteomics, and medical diagnosis. Recognition of neurocognitive disorders[en] (i.e., Alzheimer's disease or myotonic dystrophy[en]) similarly relies on data from magnetic resonance imaging
«A bunch of dumb trees learning to fix each other's mistakes»
Today they are used for:
Popular algorithms: Random Forest, Gradient Boosting
Now on to the real grown-up methods. Ensembles and neural networks are our main fighters on the road to the inevitable singularity. Today they give the most accurate results and are used in production by every major company. It's just that everyone talks about neural networks on every corner, while the words «boosting» and «bagging» probably only scare hipsters from TechCrunch.
For all their effectiveness, the idea is almost mockingly simple. It turns out that if you take several not-very-effective learning methods and train them to fix each other's mistakes, the quality of such a system ends up being much higher than that of each method taken separately.
What's more, it's even better when the chosen algorithms are as unstable as possible and swing wildly with the input data. That's why Regression and Decision Trees are more often chosen — they only need one strong anomaly in the data for the whole model to go off the rails. But Bayes and K-NN are never chosen — although they're dumb, they're very stable.
An ensemble can be assembled any way you like, even by randomly tossing classifiers into a bucket and pouring regression over them. Nobody will vouch for the accuracy then, though. That's why there are three proven ways to build ensembles.
Stacking We train several different algorithms and feed their results into the last one, which makes the final decision. Kind of like when girls first poll all their girlfriends before deciding whether to date a guy or not.
The key word is different algorithms, because the same algorithm trained on the same data makes no sense. Which ones — that's up to you, except regression is more often chosen as the decision-making algorithm.
Purely from experience — stacking is rarely used in practice, because the other two methods are usually more accurate.
Bagging Also known as Bootstrap AGGregatING. We train one algorithm many times on random samples from the source data. At the very end, we average the answers.
Data in random samples can repeat. That is, from the set 1-2-3 we can make samples 2-2-3, 1-2-2, 3-1-2, and so on for as long as we like. We train the same algorithm on them several times, and at the end we compute the answer by simple voting.
The most popular example of bagging is the Random Forest algorithm, bagging on trees, which is exactly what's shown in the picture. When you open the camera on your phone and see it outline people's faces in the frame with yellow rectangles — that's most likely their work. A neural network would be too slow in real time, while bagging is ideal, since it can compute its trees in parallel across all the shaders of the video card.
This wild ability to parallelize gives bagging an advantage even over the next method, which works more accurately but only in a single thread. Although you could split it into segments, run several in parallel... ah, who am I teaching, you're not children.
Boosting We train algorithms sequentially, each next one paying special attention to the cases where the previous one made mistakes.
As in bagging, we take samples from the source data, but now not entirely at random. In each new sample we take a portion of the data on which the previous algorithm performed incorrectly. That is, we essentially keep training the new algorithm on the previous one's mistakes.
The upside — furious, even illegal-in-some-countries, classification accuracy that would make every grandma at the front stoop jealous. The downside has already been named — it doesn't parallelize. Although it still works faster than neural networks, which are like loaded dump trucks full of sand compared to nimble boosting.
Need a real-world example of boosting at work — open Yandex and type in a query. Can you hear MatrixNet rumbling through the trees and ranking your results? That's exactly it, Yandex today runs almost entirely on boosting. Not sure about Google.
Today there are three popular boosting methods, whose differences are well covered in the article CatBoost vs. LightGBM vs. XGBoost
Comments