Maximum Margin Coresets for Active and Noise Tolerant Learning

Sariel Har-Peled,
Dan Roth,
and Dav Zimak.

We study the problem of learning large margin halfspaces in various
settings using coresets to show that coresets are a widely applicable
tool for large margin learning. A large margin coreset is a subset of
the input data sufficient for approximating the true maximum margin
solution. In this work, we provide a direct algorithm and analysis
for constructing large margin coresets. We show various applications
including a novel coreset based analysis of large margin active
learning and a polynomial time (in the number of input data and the
amount of noise) algorithm for agnostic learning in the presence of
outlier noise. We also highlight a simple extension to multi-class
classification problems and structured output learning.
Postscript,
PDF.
Last modified: Tue Sep 19 16:02:55 CDT 2006