Learning with Noisy Labels

The study of binary classification problems with noisy labels has a
long history. Soon after the introduction of the noise-free PAC model, Angluin
and Laird (1988) proposed the random classification noise model where each label
is flipped independently with some (small) probability before being revealed to
the learner. In a separate thread, researchers have investigated the use of convex
surrogates, such the hinge loss used by SVMs and the exponential loss used by
Adaboost, for the non-convex 0-1 loss. Surprisingly, little attention has been
paid to the study of convex surrogates under the random classification noise model.
I will talk about two approaches for modifying a convex surrogate so that it
still works when labels are noisy. The first approach is based on unbiased
estimators of the surrogate loss. The second approach relies on a connection
between learning with noisy labels and weighted 0-1 loss minimization. Our
results lend theoretical justification to popular heuristics such as biased
SVMs and weighted logistic regression.

During the talk, I will point a few open problems of possible interest to the
theoretical CS community: What to do when the unbiased estimator approach yields
non-convex optimization problems? What to do when labels are adversarially, not
randomly, flipped?

(Based on joint work with N. Nagarajan, I. S. Dhillon and P. Ravikumar that's
going to presented at NIPS 2013.)

Ambuj Tewari is with the Department of Statistics and the
Department of Electrical Engineering and Computer Science at the University of
Michigan, Ann Arbor. He has served on senior program committees of the
conferences Algorithmic Learning Theory (ALT), Conference on Learning Theory
(COLT), and Neural Information Processing Systems (NIPS). His papers have
received the student paper award (2005) and the best paper award (2011) at COLT.
He received his M.A. in Statistics (2005) and Ph.D. in Computer Science (2007)
from the University of California at Berkeley where his advisor was Peter
Bartlett. He was a research assistant professor in Toyota Technological
Institute at Chicago (2008-2010), an assistant professor (part-time) in the
Department of Computer Science, University of Chicago (2008-2010), and a
post-doctoral fellow in the Institute for Computational Engineering and
Sciences, University of Texas at Austin (2010-2012). He has also been a Visiting
Researcher at Microsoft Research, Redmond. His research interests are in
statistical learning theory, online learning, optimization, and reinforcement
learning.