Boosting, margins, and dynamics

Boosting algorithms are currently used for a wide variety of statistical learning tasks, such as document classification and optical character recognition. Freund and Schapire's 1997 "AdaBoost" algorithm is the most popular boosting algorithm, due to its excellent performance on many types of data and fast rate of convergence.; A strong indicator of the generalization ability of a boosted classifier is the value of the margin it achieves; large margin classifiers often achieve a low probability of error on test data. Thus, it is important to study the convergence properties of boosting algorithms, namely, whether they converge to maximum margin solutions. In empirical studies, AdaBoost seems to achieve maximum margins, and in theoretical studies, AdaBoost has been proven to achieve large margins; thus the margin theory somewhat accounts for AdaBoost's remarkable ability to generalize. The question we address in this thesis is whether AdaBoost provably converges to a maximum margin solution.; In order to understand AdaBoost's convergence properties, we look toward its dynamics. We simplify AdaBoost to reveal a nonlinear iterated map and analyze its behavior in specific cases. We find stable cycles for these cases, which can explicitly be used to solve for AdaBoost's output. Thus, we find the key to answering the question of whether AdaBoost always maximizes the margin---a set of examples in which AdaBoost's convergence can be completely understood.; By considering low-dimensional cases, we show that AdaBoost does not always converge to a maximum margin solution, answering the question stated above. Our results suggest that AdaBoost is a much richer system than previously thought; the margin theory only partially explains its strong generalization ability. This study also provides a method of analyzing AdaBoost's convergence of margins via its beautiful cyclic dynamics.; Since AdaBoost does not necessarily maximize the margin, and since the margin is a strong indicator of an algorithm's generalization ability, we introduce two coordinate boosting algorithms that maximize the margin. Both algorithms perform well empirically and are as easy to implement as AdaBoost. We prove that both algorithms possess a polynomial-time convergence rate.