Boosting is a machine-learning method based on combining many carefully trained weak prediction rules into a single, highly accurate classifier. Boosting has both a rich theory and a record of empirical success, for instance, to face detection and spoken-dialogue systems.
The theory of boosting is broadly connected to other research fields, but has only been fully developed for the simplest learning problems. Nevertheless, in practice, boosting is commonly applied in settings where the theory lags well behind. We do not know if such practical methods are truly best possible; even for binary classification, it is not clear how to best exploit what is known about how boosting operates. New challenges will demand an even greater widening of the foundations of boosting.
The goal of this project is to develop broad theoretical insights and versatile algorithmic principles. The aim is to study game-theoretically how to design the most efficient and effective boosting algorithms possible.
Research on boosting is spread over many years. across multiple publications and disciplines. To organize this body of work, a significant activity of this project is the completion of a book on boosting which will provide a valuable resource for students and researchers of diverse backgrounds and interests.
Boosting has historically had a major impact on areas outside machine learning, such as statistics, computer vision, and speech and language processing. Thus, there is a strong potential for work at its foundations to have a broad impact on these other research and application areas as well.
This project focused on a widely-used set of machine learning methods called "boosting", an approach based on the idea of combining many carefully trained weak prediction rules into a single, highly accurate classifier. Our objective was to develop theoretical insights and algorithmic principles with the aim of broadening the practical applicability of such methods. A game-theoretic approach was especially central to this project. The results of this project have helped to clarify central properties of boosting methods regarding how and why they work. They have led especially to an entirely new understanding of how these methods can be used for multiclass problems (where we are trying to classify among many possible classes). More broadly, this research shed light on other methods related to boosting, including so-called online learning algorithms where we were able to derive some techniques with very favorable theoretical and practical properties that do not depend on demanding assumptions as had been the case with previous methods. Part of this project also focused on applying boosting methods to human EEG/MEG brain activity with the intention of understanding in precise detail the timing of simple acts of will in the brain. A book on boosting was completed and published with partial support from this grant. A graduate course at Princeton was also developed on this same topic. This grant supported three graduate students and one masters student.