Journal
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume 78, Issue 5, Pages 1481-1495Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2011.12.026
Keywords
PAC learning; Classification; Agnostic learning
Funding
- NSF [SES-0734780, CCF-0746550]
- NSF CAREER award
- SLOAN Fellowship
- IST Programme of the European Community under the PASCAL2 Network of Excellence
- Israel Science Foundation
- United States-Israel Binational Science Foundation (BSF)
Ask authors/readers for more resources
It is well known that in many applications erroneous predictions of one type or another must be avoided. In some applications, like spam detection, false positive errors are serious problems. In other applications, like medical diagnosis, abstaining from making a prediction may be more desirable than making an incorrect prediction. In this paper we consider different types of reliable classifiers suited for such situations. We formalize the notion and study properties of reliable classifiers in the spirit of agnostic learning (Haussler, 1992; Kearns, Schapire, and Sellie, 1994), a PAC-like model where no assumption is made on the function being learned. We then give two algorithms for reliable agnostic learning under natural distributions. The first reliably learns DNFs with no false positives using membership queries. The second reliably learns halfspaces from random examples with no false positives or false negatives, but the classifier sometimes abstains from making predictions. (C) 2012 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available