You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 35.171.0.0/16 has been blocked (disabled) by ‪JJMC89‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider or colocation provider. To prevent abuse, web hosts and colocation providers may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host or colocation provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a colocation provider's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a colocation web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host or colocation provider (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host or colocation provider.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and requests should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 05:20, 2 December 2024.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪Jon Kolbert‬. The reason given is Open proxy/Webhost: See the help page if you are affected .
- Start of block: 05:38, 21 February 2024
- Expiry of block: 05:38, 21 February 2029
Your current IP address is 35.171.169.55. The blocked range is 35.171.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((short description|Adaptive boosting based classification algorithm))
'''AdaBoost''', short for ''Adaptive [[Boosting (meta-algorithm)|Boosting]]'', is a [[statistical classification]] [[meta-algorithm]] formulated by [[Yoav Freund]] and [[Robert Schapire]] in 1995, who won the 2003 [[Gödel Prize]] for their work. It can be used in conjunction with many other types of learning algorithms to improve performance. The output of the other learning algorithms ('weak learners') is combined into a weighted sum that represents the final output of the boosted classifier. Usually, AdaBoost is presented for [[binary classification]], although it can be generalized to multiple classes or bounded intervals on the real line.<ref>((Citation |last1=Freund |first1=Yoav |title=A ((as written|desi|cion-theoretic [sic])) generalization of on-line learning and an application to boosting |date=1995 |url=http://dx.doi.org/10.1007/3-540-59119-2_166 |series=Lecture Notes in Computer Science |pages=23–37 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-540-59119-1 |access-date=2022-06-24 |last2=Schapire |first2=Robert E.|doi=10.1007/3-540-59119-2_166 ))</ref><ref>((Cite journal |last1=Hastie |first1=Trevor |last2=Rosset |first2=Saharon |last3=Zhu |first3=Ji |last4=Zou |first4=Hui |date=2009 |title=Multi-class AdaBoost |journal=Statistics and Its Interface |volume=2 |issue=3 |pages=349–360 |doi=10.4310/sii.2009.v2.n3.a8 |issn=1938-7989|doi-access=free ))</ref>

AdaBoost is adaptive in the sense that subsequent weak learners are tweaked in favor of those instances misclassified by previous classifiers. In some problems it can be less susceptible to the [[overfitting (machine learning)|overfitting]] problem than other learning algorithms. The individual learners can be weak, but as long as the performance of each one is slightly better than random guessing, the final model can be proven to converge to a strong learner.

Although AdaBoost is typically used to combine weak base learners (such as [[Decision stump|decision stumps]]), it has been shown that it can also effectively combine strong base learners (such as deep [[Decision tree|decision trees]]), producing an even more accurate model.<ref>((cite journal |last1=Wyner |first1=Abraham J. |last2=Olson |first2=Matthew |last3=Bleich |first3=Justin |last4=Mease |first4=David |title=Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers |journal=Journal of Machine Learning Research |date=2017 |volume=18 |issue=48 |pages=1–33 |url=http://jmlr.org/papers/v18/15-240.html |access-date=17 March 2022))</ref>

Every learning algorithm tends to suit some problem types better than others, and typically has many different parameters and configurations to adjust before it achieves optimal performance on a dataset. AdaBoost (with [[Decision tree learning|decision trees]] as the weak learners) is often referred to as the best out-of-the-box classifier.<ref>((cite arXiv |last1=Kégl|first1=Balázs|title=The return of AdaBoost.MH: multi-class Hamming trees |eprint=1312.6086 |date=20 December 2013|class=cs.LG))</ref><ref>((cite web|last1=Joglekar|first1=Sachin|title=adaboost – Sachin Joglekar's blog|url=https://codesachin.wordpress.com/tag/adaboost/|website=codesachin.wordpress.com|access-date=3 August 2016))</ref> When used with decision tree learning, information gathered at each stage of the AdaBoost algorithm about the relative 'hardness' of each training sample is fed into the tree growing algorithm such that later trees tend to focus on harder-to-classify examples.

==Training==
AdaBoost refers to a particular method of training a boosted classifier. A boosted classifier is a classifier of the form
<math display="block">F_T(x) = \sum_{t=1}^T f_t(x)</math>
where each <math>f_t</math> is a weak learner that takes an object <math>x</math> as input and returns a value indicating the class of the object. For example, in the two-class problem, the sign of the weak learner's output identifies the predicted object class and the absolute value gives the confidence in that classification. Similarly, the <math>t</math>-th classifier is positive if the sample is in a positive class and negative otherwise.

Each weak learner produces an output hypothesis <math>h</math> which fixes a prediction <math>h(x_i)</math> for each sample in the training set. At each iteration <math>t</math>, a weak learner is selected and assigned a coefficient <math>\alpha_t</math> such that the total training error <math>E_t</math> of the resulting <math>t</math>-stage boosted classifier is minimized.

<math display="block">E_t = \sum_i E[F_{t-1}(x_i) + \alpha_t h(x_i)]</math>

Here <math>F_{t-1}(x)</math> is the boosted classifier that has been built up to the previous stage of training and <math>f_t(x) = \alpha_t h(x)</math> is the weak learner that is being considered for addition to the final classifier.

===Weighting===
At each iteration of the training process, a weight <math>w_{i,t}</math> is assigned to each sample in the training set equal to the current error <math>E(F_{t-1}(x_i))</math> on that sample. These weights can be used in the training of the weak learner. For instance, decision trees can be grown which favor the splitting of sets of samples with large weights.

==Derivation==
This derivation follows Rojas (2009):<ref>((cite web |last1=Rojas |first1=Raúl |author1-link=Raúl Rojas |title=AdaBoost and the super bowl of classifiers a tutorial introduction to adaptive boosting. |url=http://www.inf.fu-berlin.de/inst/ag-ki/adaboost4.pdf |publisher=Freie University, Berlin |format=Tech. Rep. |date=2009))</ref>

Suppose we have a data set <math>\{(x_1, y_1), \ldots, (x_N, y_N)\}</math> where each item <math>x_i</math> has an associated class <math>y_i \in \{-1, 1\}</math>, and a set of weak classifiers <math>\{k_1, \ldots, k_L\}</math> each of which outputs a classification <math>k_j(x_i) \in \{-1, 1\}</math> for each item. After the <math>(m-1)</math>-th iteration our boosted classifier is a linear combination of the weak classifiers of the form:
<math display="block">C_{(m-1)}(x_i) = \alpha_1k_1(x_i) + \cdots + \alpha_{m-1}k_{m-1}(x_i),</math>
where the class will be the sign of <math>C_{(m-1)}(x_i)</math>. At the <math>m</math>-th iteration we want to extend this to a better boosted classifier by adding another weak classifier <math>k_m</math>, with another weight <math>\alpha_m</math>:
<math display="block">C_{m}(x_i) = C_{(m-1)}(x_i) + \alpha_m k_m(x_i)</math>

So it remains to determine which weak classifier is the best choice for <math>k_m</math>, and what its weight <math>\alpha_m</math> should be. We define the total error <math>E</math> of <math>C_m</math> as the sum of its [[Loss functions for classification|exponential loss]] on each data point, given as follows:
<math display="block">E = \sum_{i=1}^N e^{-y_i C_m(x_i)} = \sum_{i=1}^N e^{-y_i C_{(m-1)}(x_i)}e^{-y_i \alpha_m k_m(x_i)} </math>

Letting <math>w_i^{(1)} = 1</math> and <math>w_i^{(m)} = e^{-y_i C_{m-1}(x_i)}</math> for <math>m > 1</math>, we have:
<math display="block">E = \sum_{i=1}^N w_i^{(m)}e^{-y_i\alpha_m k_m(x_i)}</math>

We can split this summation between those data points that are correctly classified by <math>k_m</math> (so <math>y_i k_m(x_i) = 1</math>) and those that are misclassified (so <math>y_i k_m(x_i) = -1</math>):
<math display="block">\begin{align}
E &= \sum_{y_i = k_m(x_i)} w_i^{(m)}e^{-\alpha_m} + \sum_{y_i \neq k_m(x_i)} w_i^{(m)}e^{\alpha_m} \\
&= \sum_{i=1}^N w_i^{(m)}e^{-\alpha_m} + \sum_{y_i \neq k_m(x_i)} w_i^{(m)}\left(e^{\alpha_m} - e^{-\alpha_m}\right)
\end{align}</math>

Since the only part of the right-hand side of this equation that depends on <math>k_m</math> is <math display="inline">\sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math>, we see that the <math>k_m</math> that minimizes <math>E</math> is the one that minimizes <math display="inline">\sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math> [assuming that <math>\alpha_m > 0</math>], i.e. the weak classifier with the lowest weighted error (with weights <math>w_i^{(m)} = e^{-y_i C_{m-1}(x_i)}</math>).

To determine the desired weight <math>\alpha_m</math> that minimizes <math>E</math> with the <math>k_m</math> that we just determined, we differentiate:
<math display="block">\frac{d E}{d \alpha_m} = \frac{d (\sum_{y_i = k_m(x_i)} w_i^{(m)}e^{-\alpha_m} + \sum_{y_i \neq k_m(x_i)} w_i^{(m)}e^{\alpha_m}) }{d \alpha_m}</math>

Luckily the minimum occurs when setting this to zero, then solving for <math>\alpha_m</math> yields:
<math display="block">\alpha_m = \frac{1}{2}\ln\left(\frac{\sum_{y_i = k_m(x_i)} w_i^{(m))){\sum_{y_i \neq k_m(x_i)} w_i^{(m)))\right)</math>

((Math proof|drop=hidden|
<math display="block">\frac{d E}{d \alpha_m} = -\sum_{y_i = k_m(x_i)} w_i^{(m)}e^{-\alpha_m} + \sum_{y_i \neq k_m(x_i)} w_i^{(m)}e^{\alpha_m} = 0</math>
because <math>e^{-\alpha_m}</math> does not depend on <math>i</math>
<math display="block">e^{-\alpha_m} \sum_{y_i = k_m(x_i)} w_i^{(m)} = e^{\alpha_m} \sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math>
<math display="block">-\alpha_m + \ln\left( \sum_{y_i = k_m(x_i)} w_i^{(m)} \right) = \alpha_m + \ln\left(\sum_{y_i \neq k_m(x_i)} w_i^{(m)} \right) </math>
<math display="block">-2\alpha_m =  \ln\left( \dfrac{\sum_{y_i \neq k_m(x_i)} w_i^{(m))){\sum_{y_i = k_m(x_i)} w_i^{(m))) \right) </math>
<math display="block">\alpha_m = - \dfrac{1}{2} \ln\left( \dfrac{\sum_{y_i \neq k_m(x_i)} w_i^{(m))){\sum_{y_i = k_m(x_i)} w_i^{(m))) \right) </math>
<math display="block">\alpha_m = \dfrac{1}{2} \ln\left( \dfrac{\sum_{y_i = k_m(x_i)} w_i^{(m))){\sum_{y_i \neq k_m(x_i)} w_i^{(m))) \right) </math>
))

We calculate the weighted error rate of the weak classifier to be <math>\epsilon_m = \frac{\sum_{y_i \neq k_m(x_i)} w_i^{(m))){\sum_{i=1}^N w_i^{(m)))</math>, so it follows that:
<math display="block">\alpha_m = \frac{1}{2}\ln\left( \frac{1 - \epsilon_m}{\epsilon_m}\right)</math>
which is the negative logit function multiplied by 0.5. Due to the convexity of <math>E</math> as a function of <math>\alpha_m</math>, this new expression for <math>\alpha_m</math> gives the global minimum of the loss function.

Note: This derivation only applies when <math>k_m(x_i) \in \{-1, 1\}</math>, though it can be a good starting guess in other cases, such as when the weak learner is biased (<math>k_m(x) \in \{a,b\}, a \neq -b</math>), has multiple leaves (<math>k_m(x) \in \{a,b,\dots,n\}</math>) or is some other function <math>k_m(x) \in \mathbb{R}</math>.

Thus we have derived the AdaBoost algorithm: At each iteration, choose the classifier <math>k_m</math>, which minimizes the total weighted error <math display="inline">\sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math>, use this to calculate the error rate <math>\epsilon_m = \frac{\sum_{y_i \neq k_m(x_i)} w_i^{(m))){\sum_{i=1}^N w_i^{(m)))</math>, use this to calculate the weight <math>\alpha_m = \frac{1}{2}\ln\left( \frac{1 - \epsilon_m}{\epsilon_m}\right)</math>, and finally use this to improve the boosted classifier <math>C_{m-1}</math> to <math>C_{m} = C_{(m-1)} + \alpha_m k_m</math>.

==Statistical understanding of boosting==
((Refimprove section|date=May 2016))
Boosting is a form of linear [[Regression analysis|regression]] in which the features of each sample <math>x_i</math> are the outputs of some weak learner <math>h</math> applied to <math>x_i</math>.

While regression tries to fit <math>F(x)</math> to <math>y(x)</math> as precisely as possible without loss of generalization, typically using [[least squares|least square]] error <math>E(f) = (y(x) - f(x))^2</math>, whereas the AdaBoost error function <math>E(f) = e^{-y(x)f(x)}</math> takes into account the fact that only the sign of the final result is used, thus <math>|F(x)|</math> can be far larger than 1 without increasing error. However, the exponential increase in the error for sample <math>x_i</math> as <math>-y(x_i)f(x_i)</math> increases, resulting in excessive weights being assigned to outliers.

One feature of the choice of exponential error function is that the error of the final additive model is the product of the error of each stage, that is, <math>e^{\sum_i -y_i f(x_i)} = \prod_i e^{-y_i f(x_i)}</math>. Thus it can be seen that the weight update in the AdaBoost algorithm is equivalent to recalculating the error on <math>F_t(x)</math> after each stage.

There is a lot of flexibility allowed in the choice of loss function. As long as the loss function is [[monotonic function|monotonic]] and [[continuously differentiable function|continuously differentiable]], the classifier is always driven toward purer solutions.<ref name="fht"/> Zhang (2004) provides a loss function based on least squares, a modified [[Huber loss function]]:
<math display="block">\phi(y,f(x)) = \begin{cases}
-4y f(x)  & \text{if }y f(x) < -1, \\
(y f(x) - 1)^2 &\text{if } -1 \le y f(x) \le 1. \\
0 &\text{if } y f(x) > 1
\end{cases}</math>

This function is more well-behaved than LogitBoost for <math>f(x)</math> close to 1 or -1, does not penalise ‘overconfident’ predictions (<math>y f(x) > 1</math>), unlike unmodified least squares, and only penalises samples misclassified with confidence greater than 1 linearly, as opposed to quadratically or exponentially, and is thus less susceptible to the effects of outliers.

==Boosting as gradient descent==
((Main article|Gradient boosting))
Boosting can be seen as minimization of a [[convex function|convex]] loss function over a [[convex set]] of functions.<ref>((cite journal |first=T. |last=Zhang |title=Statistical behavior and consistency of classification methods based on convex risk minimization |journal=Annals of Statistics |volume=32 |issue=1 |pages=56–85 |year=2004 |doi=10.1214/aos/1079120130 |jstor=3448494 |doi-access=free ))</ref> Specifically, the loss being minimized by AdaBoost is the exponential loss
<math display="block">\sum_i \phi(i,y,f) = \sum_i e^{-y_i f(x_i)},</math>
whereas LogitBoost performs logistic regression, minimizing
<math display="block">\sum_i \phi(i,y,f) = \sum_i \ln\left(1+e^{-y_i f(x_i)}\right).</math>

In the gradient descent analogy, the output of the classifier for each training point is considered a point <math>\left(F_t(x_1), \dots, F_t(x_n)\right)</math> in n-dimensional space, where each axis corresponds to a training sample, each weak learner <math>h(x)</math> corresponds to a vector of fixed orientation and length, and the goal is to reach the target point <math>(y_1, \dots, y_n)</math> (or any region where the value of loss function <math>E_T(x_1, \dots, x_n)</math> is less than the value at that point), in the fewest steps. Thus AdaBoost algorithms perform either [[gradient descent|Cauchy]] (find <math>h(x)</math> with the steepest gradient, choose <math>\alpha</math> to minimize test error) or [[Newton's method|Newton]] (choose some target point, find <math>\alpha h(x)</math> that brings <math>F_t</math> closest to that point) optimization of training error.

==Example algorithm (Discrete AdaBoost)==
With:
* Samples <math>x_1 \dots x_n</math>
* Desired outputs <math>y_1 \dots y_n, y \in \{-1, 1\}</math>
* Initial weights <math>w_{1,1} \dots w_{n,1}</math> set to <math>\frac{1}{n}</math>
* Error function <math>E(f(x), y, i) = e^{-y_i f(x_i)}</math>
* Weak learners <math>h\colon x \rightarrow \{-1, 1\}</math>
For <math>t</math> in <math>1 \dots T</math>:
* Choose <math>h_t(x)</math>:
** Find weak learner <math>h_t(x)</math> that minimizes <math>\epsilon_t</math>, the weighted sum error for misclassified points <math>\epsilon_t = \sum^n_{\stackrel{i=1}{h_t(x_i)\neq y_i)) w_{i,t} </math>
** Choose <math>\alpha_t = \frac{1}{2} \ln \left(\frac{1-\epsilon_t}{\epsilon_t}\right)</math>
* Add to ensemble:
** <math>F_t(x) = F_{t-1}(x) + \alpha_t h_t(x)</math>
* Update weights:
** <math>w_{i,t+1} = w_{i,t} e^{-y_i \alpha_t h_t(x_i)}</math> for <math>i</math> in <math>1 \dots n</math>
** Renormalize <math>w_{i,t+1}</math> such that <math>\sum_i w_{i,t+1} = 1</math>
**(Note: It can be shown that <math>\frac{\sum_{h_{t+1}(x_i) = y_i} w_{i,t+1)){\sum_{h_{t+1}(x_i) \neq y_i} w_{i,t+1)) = \frac{\sum_{h_t(x_i) = y_i} w_{i,t)){\sum_{h_t(x_i) \neq y_i} w_{i,t))</math> at every step, which can simplify the calculation of the new weights.)

==Variants==

===Real AdaBoost===
The output of decision trees is a class probability estimate <math>p(x) = P(y=1 | x)</math>, the probability that <math>x</math> is in the positive class.<ref name="fht">((cite journal | citeseerx = 10.1.1.51.9525 | title = Additive Logistic Regression: A Statistical View of Boosting | first1 = Jerome | last1 = Friedman | first2 = Trevor | last2 = Hastie | first3 = Robert | last3 = Tibshirani | journal = Annals of Statistics | year = 1998| volume = 28 | page = 2000 ))</ref> Friedman, Hastie and Tibshirani derive an analytical minimizer for <math>e^{-y\left(F_{t-1}(x)+f_t(p(x))\right)}</math> for some fixed <math>p(x)</math> (typically chosen using weighted least squares error):
:<math>f_t(x) = \frac{1}{2} \ln\left(\frac{x}{1-x}\right)</math>.
Thus, rather than multiplying the output of the entire tree by some fixed value, each leaf node is changed to output half the [[logit]] transform of its previous value.

===LogitBoost===
((Main article|LogitBoost))
LogitBoost represents an application of established [[logistic regression]] techniques to the AdaBoost method. Rather than minimizing error with respect to y, weak learners are chosen to minimize the (weighted least-squares) error of <math>f_t(x)</math> with respect to
<math display="block">z_t = \frac{y^* - p_t(x)}{2 p_t(x)(1 - p_t(x))},</math>
where
<math display="block">p_t(x) = \frac{e^{F_{t-1}(x))){e^{F_{t-1}(x)}+e^{-F_{t-1}(x))),</math>
<math display="block">w_t = p_t(x)(1 - p_t(x))</math>
<math display="block">y^* = \frac{y+1} 2.</math>

That is <math>z_t</math> is the [[Newton–Raphson]] approximation of the minimizer of the log-likelihood error at stage <math>t</math>, and the weak learner <math>f_t</math> is chosen as the learner that best approximates <math>z_t</math> by weighted least squares.

As p approaches either 1 or 0, the value of <math>p_t(x_i)(1 - p_t(x_i))</math> becomes very small and the ''z'' term, which is large for misclassified samples, can become [[numerical instability|numerically unstable]], due to machine precision rounding errors. This can be overcome by enforcing some limit on the absolute value of ''z'' and the minimum value of&nbsp;''w''

===Gentle AdaBoost===
While previous boosting algorithms choose <math>f_t</math> greedily, minimizing the overall test error as much as possible at each step, GentleBoost features a bounded step size. <math>f_t</math> is chosen to minimize <math display="inline">\sum_i w_{t,i} (y_i-f_t(x_i))^2</math>, and no further coefficient is applied. Thus, in the case where a weak learner exhibits perfect classification performance, GentleBoost chooses <math>f_t(x) = \alpha_t h_t(x)</math> exactly equal to <math>y</math>, while steepest descent algorithms try to set <math>\alpha_t = \infty</math>. Empirical observations about the good performance of GentleBoost appear to back up Schapire and Singer's remark that allowing excessively large values of <math>\alpha</math> can lead to poor generalization performance.<ref name="ss">((cite journal |last1=Schapire |first1=Robert |last2=Singer |first2=Yoram |year=1999 |title=Improved Boosting Algorithms Using Confidence-rated Predictions |pages=80–91 |citeseerx=10.1.1.33.4002))</ref><ref name="fs">((cite web | url = http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf | title = A Short Introduction to Boosting | last1 = Freund | last2 = Schapire | year = 1999 | postscript = : ))</ref>

===Early Termination===
A technique for speeding up processing of boosted classifiers, early termination refers to only testing each potential object with as many layers of the final classifier necessary to meet some confidence threshold, speeding up computation for cases where the class of the object can easily be determined. One such scheme is the object detection framework introduced by Viola and Jones:<ref>((cite journal | citeseerx = 10.1.1.10.6807 | title = Rapid Object Detection Using a Boosted Cascade of Simple Features | first1 = Paul | last1 = Viola | first2 = Robert | last2 = Jones | year = 2001))</ref> in an application with significantly more negative samples than positive, a cascade of separate boost classifiers is trained, the output of each stage biased such that some acceptably small fraction of positive samples is mislabeled as negative, and all samples marked as negative after each stage are discarded. If 50% of negative samples are filtered out by each stage, only a very small number of objects would pass through the entire classifier, reducing computation effort. This method has since been generalized, with a formula provided for choosing optimal thresholds at each stage to achieve some desired false positive and false negative rate.<ref>((cite journal | title = Optimizing cascade classifiers. | last1 = McCane | first1 = Brendan | first2 = Kevin | last2 = Novins | first3 = Michael | last3 = Albert | year = 2005))</ref>

In the field of statistics, where AdaBoost is more commonly applied to problems of moderate dimensionality, [[early stopping]] is used as a strategy to reduce [[overfitting]].<ref>((cite book|author1=Trevor Hastie |author2=Robert Tibshirani |author3=Jerome Friedman |title=The Elements of Statistical Learning: Data Mining, Inference, and Prediction|year=2009|publisher=Springer|location=New York|isbn=978-0-387-84858-7|url=http://statweb.stanford.edu/~tibs/ElemStatLearn/download.html|edition=2nd))</ref> A validation set of samples is separated from the training set, performance of the classifier on the samples used for training is compared to performance on the validation samples, and training is terminated if performance on the validation sample is seen to decrease even as performance on the training set continues to improve.

===Totally corrective algorithms===
For steepest descent versions of AdaBoost, where <math>\alpha_t</math> is chosen at each layer ''t'' to minimize test error, the next layer added is said to be ''maximally independent'' of layer ''t'':<ref>((cite book | title = Adaboost with Totally Corrective Updates for Fast Face Detection | first1 = Jan | last1 = Šochman | first2 = Jiří | last2 = Matas | isbn=978-0-7695-2122-0 | year = 2004))</ref> it is unlikely to choose a weak learner ''t+1'' that is similar to learner ''t''. However, there remains the possibility that ''t+1'' produces similar information to some other earlier layer. Totally corrective algorithms, such as [[LPBoost]], optimize the value of every coefficient after each step, such that new layers added are always maximally independent of every previous layer. This can be accomplished by backfitting, [[linear programming]] or some other method.

===Pruning===
Pruning is the process of removing poorly performing weak classifiers to improve memory and execution-time cost of the boosted classifier. The simplest methods, which can be particularly effective in conjunction with totally corrective training, are weight- or margin-trimming: when the coefficient, or the contribution to the total test error, of some weak classifier falls below a certain threshold, that classifier is dropped. Margineantu & Dietterich<ref>((cite journal | citeseerx = 10.1.1.38.7017 | title = Pruning Adaptive Boosting | first1 = Dragos | last1 = Margineantu | first2 = Thomas | last2 = Dietterich | year = 1997))</ref> suggested an alternative criterion for trimming: weak classifiers should be selected such that the diversity of the ensemble is maximized. If two weak learners produce very similar outputs, efficiency can be improved by removing one of them and increasing the coefficient of the remaining weak learner.<ref>((cite journal | title = On the Boosting Pruning Problem | first1 = Christino | last1 = Tamon | first2 = Jie | last2 = Xiang | year = 2000))</ref>

==See also==
* [[Bootstrap aggregating]]
* [[CoBoosting]]
* [[BrownBoost]]
* [[Gradient boosting]]
* ((slink|Multiplicative weight update method|AdaBoost algorithm))

==References==
((reflist))

==Further reading==
((refbegin))
* ((cite journal | citeseerx = 10.1.1.32.8918 | title = A decision-theoretic generalization of on-line learning and an application to boosting | journal = Journal of Computer and System Sciences | volume = 55 | pages = 119–139 | year = 1997 | postscript = : | doi = 10.1006/jcss.1997.1504 | last1 = Freund | first1 = Yoav | last2 = Schapire | first2 = Robert E )) original paper of Yoav Freund and Robert E.Schapire where AdaBoost is first introduced.
* ((cite journal | url = http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/colt08.pdf | title = On the margin explanation of boosting algorithm. | first = Zhihua | last = Zhou | journal = In: Proceedings of the 21st Annual Conference on Learning Theory (COLT'08) | pages = 479–490 | year = 2008 )) On the margin explanation of boosting algorithm.
* ((cite journal | url = http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/aij13marginbound.pdf | title = On the doubt about margin explanation of boosting | first = Zhihua | last = Zhou | journal = Artificial Intelligence |  volume = 203 | issue = 2013 | pages = 1–18 | year = 2013 | bibcode = 2010arXiv1009.3613G | arxiv = 1009.3613 | doi = 10.1016/j.artint.2013.07.002 | s2cid = 2828847 )) On the doubt about margin explanation of boosting.
((refend))


((DEFAULTSORT:AdaBoost))
[[Category:Classification algorithms]]
[[Category:Ensemble learning]]

Pages transcluded onto the current version of this page (help):

AdaBoost (edit)
Template:Ambox (view source) (template editor protected)
Template:As written (view source) (semi-protected)
Template:Citation (view source) (protected)
Template:Cite arXiv (view source) (template editor protected)
Template:Cite book (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Cite web (view source) (protected)
Template:Main (view source) (template editor protected)
Template:Main article (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:Math proof (view source) (semi-protected)
Template:Math proof/styles.css (view source) (semi-protected)
Template:More citations needed (view source) (template editor protected)
Template:More citations needed section (view source) (template editor protected)
Template:Not a typo (view source) (template editor protected)
Template:Pagetype (view source) (protected)
Template:Refbegin (view source) (template editor protected)
Template:Refbegin/styles.css (view source) (template editor protected)
Template:Refend (view source) (template editor protected)
Template:Refimprove section (view source) (template editor protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:Section link (view source) (template editor protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Template:Sic (view source) (template editor protected)
Template:Slink (view source) (extended confirmed protected)
Template:Sp (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Format link (view source) (template editor protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:Section link (view source) (template editor protected)
Module:String (view source) (protected)
Module:Unsubst (view source) (protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to AdaBoost.

Retrieved from "https://en.wikipedia.org/wiki/AdaBoost"