Maximum Margin Coresets for Active and Noise Tolerant Learning
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.
Cite
Text
Har-Peled et al. "Maximum Margin Coresets for Active and Noise Tolerant Learning." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Har-Peled et al. "Maximum Margin Coresets for Active and Noise Tolerant Learning." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/harpeled2007ijcai-maximum/)BibTeX
@inproceedings{harpeled2007ijcai-maximum,
title = {{Maximum Margin Coresets for Active and Noise Tolerant Learning}},
author = {Har-Peled, Sariel and Roth, Dan and Zimak, Dav},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {836-841},
url = {https://mlanthology.org/ijcai/2007/harpeled2007ijcai-maximum/}
}