@article{e7fe18bd336d459a819346594e2b40c2,
title = "Minimizing the error of linear separators on linearly inseparable data",
abstract = "Given linearly inseparable sets R of red points and B of blue points, we consider several measures of how far they are from being separable. Intuitively, given a potential separator ({"}classifier{"}), we measure its quality ({"}error{"}) according to how much work it would take to move the misclassified points across the classifier to yield separated sets. We consider several measures of work and provide algorithms to find linear classifiers that minimize the error under these different measures.",
keywords = "Classifiers, Error minimizers, Linearly inseparable",
author = "Boris Aronov and Delia Garijo and Yurai Nez-Rodrguez and David Rappaport and Carlos Seara and Jorge Urrutia",
note = "Funding Information: The first author was partially supported by grant No. 2006/194 from the U.S.-Israel Binational Science Foundation , NSA MSP Grant H98230-06-1-0016 , and NSF Grant CCF-08-30691 . The second author was partially supported by project MTM2008-05866-C03-01. The third author was partially supported by project NSERC Postdoctoral Fellow, IRDF. The fourth author was partially supported by an NSERC of Canada Discovery Grant. The fifth author was partially supported by projects MTM2009-07242, Gen Cat DGR2009GR1040, and ESF EUROCORES programme EuroGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306. The sixth author{\textquoteright}s research was supported in part by MTM2006-03909 (Spain) and SEP-CONACYT of M{\'e}xico, Proyecto 80268. ",
year = "2012",
month = jul,
doi = "10.1016/j.dam.2012.03.009",
language = "English (US)",
volume = "160",
pages = "1441--1452",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "10-11",
}