Lecture
Boosting (from the English boosting) — a compositional machine learning meta-algorithm, used mainly to reduce bias, as well as variance, in supervised learning. It is also defined as a family of machine learning algorithms that convert weak learning algorithms into strong ones .
Boosting is a machine learning method that is used to build a strong ensemble model by combining weak learning models, such as decision trees or regression models. Boosting is based on the idea of sequentially training models, where each new model tries to correct the errors of the previous models.
The main principle of boosting is to sequentially train models on weighted or changing training data, focusing on the objects on which the previous models performed poorly. As a result, the models, taken together, form a strong composition of models that handles the prediction task better than the individual models.
Some of the popular boosting algorithms include:
AdaBoost (Adaptive Boosting): It uses weighting of the training data so that the models focus on the objects on which the previous models made mistakes. The object weights are updated at each iteration to take the previous errors into account.
Gradient Boosting: It works by training models on the residuals of the previous models. Each new model tries to reduce the residuals of the previous models, which leads to an improvement in the quality of the predictions.
XGBoost (Extreme Gradient Boosting): This is an optimized version of gradient boosting that uses a number of optimizations and heuristics to improve the performance and accuracy of the models.
LightGBM: This is another efficient implementation of gradient boosting that has high speed and good scalability. It uses data compression and other optimizations to speed up model training.
Boosting algorithms are widely used to solve classification and regression problems, as well as for ranking and other machine learning tasks. They have high predictive power and are among the most powerful algorithms in the field of machine learning.
Boosting is based on a question raised by Kearns and Valiant (1988, 1989): «Can a set of weak learning algorithms create a strong learning algorithm?». A weak learning algorithm is defined as a classifier that is only weakly correlated with the correct classification (it can label examples better than random guessing). Unlike a weak algorithm, a strong learning algorithm is a classifier that correlates well with the correct classification.
Robert Schapire's affirmative answer in a 1990 paper to Kearns and Valiant's question was of great significance for machine learning theory and statistics, and led to the creation of a wide range of boosting algorithms .
The boosting hypothesis concerned the process of tuning a weak learning algorithm to obtain strong learning. Informally, the question is whether the existence of an efficient learning algorithm whose output is a hypothesis that is only slightly better than random guessing (that is, weak learning) implies the existence of an efficient algorithm that produces a hypothesis of arbitrary accuracy (that is, strong learning) . Algorithms that quickly obtain such a hypothesis have become known simply as «boosting». The «arcing» algorithm of Freund and Schapire (Adaptive Resampling and Combining), as a general technique, is more or less synonymous with boosting
While boosting is not algorithmically restricted, most boosting algorithms consist of iteratively training weak classifiers with the goal of assembling them into a strong classifier. When they are added, they are usually assigned weights in some way, which are usually related to their training accuracy. After a weak classifier is added, the weights are recalculated, which is known as «reweighting». Misclassified input data get a larger weight, while correctly classified instances lose weight[nb 1]. This way, subsequent weak learning focuses more on the examples where previous weak learners produced an incorrect classification.
There are many boosting algorithms. The original algorithms proposed by Robert Schapire (recursive majority gate formulation) and Yoav Freund (boost-by-majority) were not adaptive and could not fully exploit the advantage of weak learners. Schapire and Freund then developed AdaBoost (Adaptive Boosting) — an adaptive boosting algorithm that won the prestigious Gödel Prize.
Only algorithms that can be proven to be boosting algorithms in the probably approximately correct learning formulation can accurately be called boosting algorithms. Other algorithms that are similar in spirit to boosting algorithms are sometimes called «leveraging algorithms», although they are also sometimes incorrectly called boosting algorithms .
The main difference between many boosting algorithms lies in the methods for determining the weight coefficients of the training data points and hypotheses. The AdaBoost algorithm is very popular and historically the most significant, since it was the first algorithm that could adapt to weak learning. The algorithm is often used as a basic introduction to boosting algorithms in machine learning courses at universities . There are many recently developed algorithms, such as LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost, and others. Many boosting algorithms fall under the AnyBoost model, which shows that boosting performs gradient descent in function space using a convex loss function.
Illustration demonstrating the intuition of a boosting algorithm consisting of parallel learners and a weighted dataset.
Given images containing various objects known in the world, a classifier can be trained based on them to automatically classify objects in future unknown images. Simple classifiers built on some feature of an object's image usually turn out to be ineffective at classification. Using boosting methods for object classification is a way of combining weak classifiers in a special way to improve overall classification ability.
Feature classification is a typical computer vision problem, where it is determined whether an image contains a certain category of objects or not. The idea is closely related to recognition, identification, and detection. Classification for object detection usually includes feature extraction, training a classifier, and applying the classifier to new data. There are many ways to represent an object category, for example by shape analysis, using the «bag of words» model, using local descriptors such as SIFT, and so on. Examples of supervised classifiers are naive Bayes classifiers, support vector machines, Gaussian mixtures, and neural networks. However, research has shown that object categories and their location in images can also be discovered using unsupervised learning
Recognizing object categories in images is a difficult problem in computer vision, especially when the number of categories is large. This is a consequence of the high intra-class variability and the need to generalize different concepts within a class. Objects in the same category can look completely different. Even the same object can look dissimilar from different viewpoints, at a different scale, or under different lighting. Background noise and partial occlusions also add difficulty to recognition . People are able to recognize thousands of types of objects, while most existing object recognition systems are trained to recognize only a few, for example human faces, cars, simple objects, etc. . Research into increasing the number of categories and the ability to add new categories is being actively pursued, and although the general problem has not yet been solved, detectors for a large number of categories (up to hundreds and thousands) have been developed. This is achieved, in particular, through feature sharing and boosting.
The AdaBoost package can be used for face recognition as an example of binary classification. The two categories are faces and background. The general algorithm looks as follows:
After boosting, a classifier built from 200 features can achieve a 95% successful recognition rate with 
false positive recognition errors .
Another application of boosting for binary classification is a system that recognizes pedestrians using motion and appearance patterns . This work is the first to combine motion information and appearance as features for detecting a moving person. The work adopts an approach similar to the Viola—Jones object detection model.
Compared to binary classification, multiclass classification looks for common features that can be shared by categories at the same time. They turn out to be more general, similar to a feature like "edge". During training, classifiers for each category can be trained jointly. Compared to separate training, such training has better generalizability, requires less training data, and needs fewer features to achieve the required result.
The main operation of the algorithm is similar to the binary case. The difference is that the joint training error measure can be defined in advance. During each iteration, the algorithm selects a single-feature classifier (features that can be jointly classified are encouraged). This can be done by converting the multiclass classification into a binary one (one set of categories / the rest of the categories) or by introducing a penalty for categories that have no features recognized by the classifier .
In the paper «Sharing visual features for multiclass and multiview object detection», A. Torralba and co-authors used GentleBoost for boosting and showed that, if the training data is limited, learning with shared features works much better than without sharing. Also, for a given level of performance, the total number of features required (and hence the classifier's running time) for feature sharing detection grows roughly logarithmically with the number of classes, that is, more slowly than linearly, which is observed in the case without sharing. Similar results are shown in the paper «Incremental learning of object detectors using a visual alphabet», although for boosting the authors used AdaBoost.
Boosting algorithms can be based on convex or non-convex optimization algorithms. Convex algorithms, such as AdaBoost and LogitBoost, can «crash» due to random noise, since they cannot learn basic and learnable combinations of weak hypotheses . This limitation was pointed out by Long and Servedio in 2008. However, in 2009 several authors demonstrated that boosting algorithms based on non-convex optimization, such as BrownBoost, can be trained from noisy data, and the underlying Long-Servedio classifier can be learned for a dataset.
Comments