Maximum margin coresets for active and noise tolerant learning

Sariel Har-Peled, Dan Roth, Dav Zimak

Research output: Contribution to journalConference article

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 languageEnglish (US)
Pages (from-to)836-841
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - Dec 1 2007
Event20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India
Duration: Jan 6 2007Jan 12 2007

    Fingerprint

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this