[talks] I Mukherjee preFPO

Melissa Lawson mml at CS.Princeton.EDU
Tue Nov 9 16:35:35 EST 2010

Indraneel Mukherjee will present his preFPO on Tuesday November 16 at 2PM in Room 402. 
The members of his committee are:  Rob Schapire, advisor; Yoav Freund (UCSD) and David 
Blei, readers; Moses Charikar and Philippe Rigollet (ORFE), nonreaders.  Everyone is
to attend his talk.  His abstract and reading list follow below.

Title: Results on Boosting:


Boosting is a highly popular off-the-shelf machine learning algorithm.
Yet its understanding is incomplete. In this thesis, we study two
theoretical questions related to boosting.

In the first project, we study boosting algorithms for multiclass
classification. Boosting combines weak classifiers to form highly
accurate predictors. Although the case of binary classification is
well understood, in the multiclass setting, the "correct" requirements
on the weak classifier, or the notion of the most efficient boosting
algorithms are missing. In this paper, we create a broad and general
framework, within which we make precise and identify the optimal
requirements on the weak-classifier, as well as design the most
effective, in a certain game-theoretic sense, boosting algorithms that
assume such requirements.

Secondly, we consider the problem of learning to predict as well as
the best in a group of experts making continuous predictions, which is
related to finding the optimal boosting algorithm with confidence
rated weak-learners. We propose a new master strategy that achieves
the best possible performance when the number of experts is
sufficiently high. Our ideas are based on drifting games, a
generalization of boosting and on-line learning algorithms. A
surprising consequence of our work is that continuous experts are only
as powerful as experts making binary or no prediction in each round.

More information about the talks mailing list