期刊
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 78, 期 5, 页码 1481-1495出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2011.12.026
关键词
PAC learning; Classification; Agnostic learning
资金
- 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)
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据