Abstract
We study the problem of learning largemargin half-spaces in various settings using coresets and 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 coresets1. 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.
Original language | English (US) |
---|---|
Pages (from-to) | 836-841 |
Number of pages | 6 |
Journal | IJCAI International Joint Conference on Artificial Intelligence |
State | Published - 2007 |
Event | 20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India Duration: Jan 6 2007 → Jan 12 2007 |
ASJC Scopus subject areas
- Artificial Intelligence