Maximum Margin Coresets for Active and Noise Tolerant Learning
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.
Last modified: Tue Sep 19 16:02:55 CDT 2006