 | This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(September 2023) (Learn how and when to remove this message) |
| Part of a series on |
| Machine learning anddata mining |
|---|
Learning with humans |
Model diagnostics |
Inmachine learning (ML),boosting is anensemble learning method that combines a set of less accurate models (called "weak learners") to create a single, highly accurate model (a "strong learner"). Unlike other ensemble methods that build models in parallel (such asbagging), boosting algorithms build models sequentially. Each new model in the sequence is trained to correct the errors made by its predecessors. This iterative process allows the overall model to improve its accuracy, particularly by reducingbias.[1] Boosting is a popular and effective technique used insupervised learning for bothclassification andregression tasks.[2]
The theoretical foundation for boosting came from a question posed byKearns andValiant (1988, 1989):[3][4] "Can a set of weak learners create a single strong learner?" A weak learner is defined as aclassifier that performs only slightly better than random guessing, whereas a strong learner is a classifier that is highly correlated with the true classification.Robert Schapire's affirmative answer to this question in a 1990 paper led to the development of practical boosting algorithms.[5][6] The first such algorithm was developed by Schapire, withFreund and Schapire later developingAdaBoost, which remains a foundational example of boosting.[7]
While boosting is not algorithmically constrained, most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are weighted in a way that is related to the weak learners' accuracy. After a weak learner is added, the data weights are readjusted, known as "re-weighting". Misclassified input data gain a higher weight and examples that are classified correctly lose weight.[note 1] Thus, future weak learners focus more on the examples that previous weak learners misclassified.
There are many boosting algorithms. The original ones, proposed byRobert Schapire (arecursive majority gate formulation),[8] andYoav Freund (boost by majority),[9] were notadaptive and could not take full advantage of the weak learners. Schapire and Freund then developedAdaBoost, an adaptive boosting algorithm that won the prestigiousGödel Prize.
Only algorithms that are provable boosting algorithms in theprobably approximately correct learning formulation can accurately be calledboosting algorithms. Other algorithms that are similar in spirit[clarification needed] to boosting algorithms are sometimes called "leveraging algorithms", although they are also sometimes incorrectly called boosting algorithms.[9]
The main variation between many boosting algorithms is their method ofweightingtraining data points andhypotheses.AdaBoost is very popular and the most significant historically as it was the first algorithm that could adapt to the weak learners. It is often the basis of introductory coverage of boosting in university machine learning courses.[10] There are many more recent algorithms such asLPBoost, TotalBoost,BrownBoost,xgboost, MadaBoost,LogitBoost,CatBoost and others. Many boosting algorithms fit into the AnyBoost framework,[9] which shows that boosting performsgradient descent in afunction space using aconvexcost function.
Given images containing various known objects in the world, a classifier can be learned from them to automaticallyclassify the objects in future images. Simple classifiers built based on someimage feature of the object tend to be weak in categorization performance. Using boosting methods for object categorization is a way to unify the weak classifiers in a special way to boost the overall ability of categorization.[citation needed]
Object categorization is a typical task ofcomputer vision that involves determining whether or not an image contains some specific category of object. The idea is closely related with recognition, identification, and detection. Appearance based object categorization typically containsfeature extraction,learning aclassifier, and applying the classifier to new examples. There are many ways to represent a category of objects, e.g. fromshape analysis,bag of words models, or local descriptors such asSIFT, etc. Examples ofsupervised classifiers areNaive Bayes classifiers,support vector machines,mixtures of Gaussians, andneural networks. However, research[which?] has shown that object categories and their locations in images can be discovered in anunsupervised manner as well.[11]
The recognition of object categories in images is a challenging problem incomputer vision, especially when the number of categories is large. This is due to high intra class variability and the need for generalization across variations of objects within the same category. Objects within one category may look quite different. Even the same object may appear unalike under different viewpoint,scale, andillumination. Background clutter and partial occlusion add difficulties to recognition as well.[12] Humans are able to recognize thousands of object types, whereas most of the existingobject recognition systems are trained to recognize only a few,[quantify] e.g.human faces,cars, simple objects, etc.[13][needs update?] Research has been very active on dealing with more categories and enabling incremental additions of new categories, and although the general problem remains unsolved, several multi-category objects detectors (for up to hundreds or thousands of categories[14]) have been developed. One means is byfeature sharing and boosting.
AdaBoost can be used for face detection as an example ofbinary categorization. The two categories are faces versus background. The general algorithm is as follows:
After boosting, a classifier constructed from 200 features could yield a 95% detection rate under afalse positive rate.[15]
Another application of boosting for binary categorization is a system that detects pedestrians usingpatterns of motion and appearance.[16] This work is the first to combine both motion information and appearance information as features to detect a walking person. It takes a similar approach to theViola-Jones object detection framework.
Compared with binary categorization,multi-class categorization looks for common features that can be shared across the categories at the same time. They turn to be more genericedge like features. During learning, the detectors for each category can be trained jointly. Compared with training separately, itgeneralizes better, needs less training data, and requires fewer features to achieve the same performance.
The main flow of the algorithm is similar to the binary case. What is different is that a measure of the joint training error shall be defined in advance. During each iteration the algorithm chooses a classifier of a single feature (features that can be shared by more categories shall be encouraged). This can be done via convertingmulti-class classification into a binary one (a set of categories versus the rest),[17] or by introducing a penalty error from the categories that do not have the feature of the classifier.[18]
In the paper "Sharing visual features for multiclass and multiview object detection", A. Torralba et al. usedGentleBoost for boosting and showed that when training data is limited, learning via sharing features does a much better job than no sharing, given same boosting rounds. Also, for a given performance level, the total number of features required (and therefore the run time cost of the classifier) for the feature sharing detectors, is observed to scale approximatelylogarithmically with the number of class, i.e., slower thanlinear growth in the non-sharing case. Similar results are shown in the paper "Incremental learning of object detectors using a visual shape alphabet", yet the authors usedAdaBoost for boosting.
Boosting algorithms can be based onconvex or non-convex optimization algorithms. Convex algorithms, such asAdaBoost andLogitBoost, can be "defeated" by random noise such that they can't learn basic and learnable combinations of weak hypotheses.[19][20] This limitation was pointed out by Long & Servedio in 2008. However, by 2009, multiple authors demonstrated that boosting algorithms based on non-convex optimization, such asBrownBoost, can learn from noisy datasets and can specifically learn the underlying classifier of the Long–Servedio dataset.
Arcing [Boosting] is more successful than bagging in variance reduction
The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners
Schapire (1990) proved that boosting is possible. (Page 823)
