University of Illinois Urbana-Champaign

Maximum Margin Coresets for Active and Noise Tolerant Learning

Har-Peled, Sariel; Roth, Dan; Zimak, Dav A.

Content Files
Maximum Margin Coresets for Active and Noise Tolerant Learning.pdf

Permalink

https://hdl.handle.net/2142/11268

Description

Title
Maximum Margin Coresets for Active and Noise Tolerant Learning
Author(s)
  • Har-Peled, Sariel
  • Roth, Dan
  • Zimak, Dav A.
Issue Date
2006-10
Keyword(s)
computer science
Date of Ingest
2009-04-21T19:11:23Z
Abstract
We study the problem of learning large margin halfspaces 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 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.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11268
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY