Convexity, Classification, and Risk Bounds
Speaker: Prof Peter Bartlett, University of California, Berkeley
When: 2003-08-15 11:00:00
Venue: 78-420
Host: Prof Tom Downs
Abstract:Many successful classification algorithms, including the support
vector machine and boosting, can be viewed as minimum contrast
methods that minimize a convex surrogate of the 0-1 loss
function. The convexity makes these algorithms computationally
efficient. The use of a surrogate, however, has statistical
consequences that must be balanced against the computational virtues
of convexity. To study these issues, we provide a general
quantitative relationship between the risk as assessed using the 0-1
loss and the risk as assessed using any nonnegative surrogate loss
function. We show that this relationship gives nontrivial upper
bounds on excess risk under the weakest possible condition on the
loss function: that it satisfy a pointwise form of Fisher
consistency for classification. The relationship is based on a
simple variational transformation of the loss function that is easy
to compute in many applications. We also present a refined version
of this result in the case of low noise. Finally, we present
applications of our results to the estimation of convergence rates
for a variety of classifiers and commonly used loss functions.
(joint work with Michael I. Jordan and Jon D. McAuliffe)
Biography:Peter Bartlett is a professor in the Division of Computer Science
and Department of Statistics at the University of California at
Berkeley. He is the co-author, with Martin Anthony, of the book
Learning in Neural Networks: Theoretical Foundations, has edited
three other books, and has co-authored more than one hundred papers
in the areas of machine learning and statistical learning theory. He
has served as an associate editor of the journals Machine Learning,
Mathematics of Control Signals and Systems, the Journal of Machine
Learning Research, and the Journal of Artificial Intelligence
Research, as a member of the editorial boards of Machine Learning
and the Journal of Artificial Intelligence Research, and as a member
of the steering committees of the Conference on Computational
Learning Theory and the Algorithmic Learning Theory Workshop. He has
consulted to a number of corporations, including General Electric
and Telstra. In 2001, he was awarded the Malcolm McIntosh Prize for
Physical Scientist of the Year, for his work in statistical learning
theory. He was a Miller Institute Visiting Research Professor in
Statistics and Computer Science at U.C. Berkeley in Fall 2001, and a
fellow, senior fellow and professor in the Research School of
Information Sciences and Engineering at the Australian National
University's Institute for Advanced Studies (1993-2003), and he has
an adjunct position in the Department of Computer Science and
Electrical Engineering at the University of Queensland. His research
interests include machine learning, statistical learning theory, and
adaptive control.
Type: Festival of Doubt
Contact:Prof Tom Downs, seminar host (td@itee.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)