the value of loss function is less than the value at that point), in the fewest steps. Thus AdaBoost algorithms perform either Cauchy (find with the steepest gradient, choose to minimize test error) or Newton (choose some target point, find that brings closest to that point) optimization of training error. Example algorithm (Discrete AdaBoost) With: Samples Desired outputs Initial weights set to Error function Weak learners For in : Choose : Find weak learner that minimizes , the weighted sum error for misclassified points Choose Add to ensemble: Update weights: for in Renormalize such that (Note: It can be shown that 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 , the probability that is in the positive class. Friedman, Hastie and Tibshirani derive an analytical minimizer for for some fixed (typically chosen using weighted least squares error): . 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 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 with respect to where That is is the Newton–Raphson approximation of the minimizer of the log-likelihood error at stage , and the weak learner is chosen as the learner that best approximates by weighted least squares. As p approaches either 1 or 0, the value of becomes very small and the z term, which is large for misclassified samples, can become 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 w Gentle AdaBoost While previous boosting algorithms choose greedily, minimizing the overall test error as much as possible at each step, GentleBoost features a bounded step size. is chosen to minimize , and no further coefficient is applied. Thus, in the case where a weak learner exhibits perfect classification performance, GentleBoost chooses exactly equal to , while steepest descent algorithms try to set . Empirical observations about the good performance of GentleBoost appear to back up Schapire and Singer's remark that allowing excessively large values of can lead to poor generalization performance. Early Termination A