| TR#: | MSC-2017-30 |
| Class: | MSC |
| Title: | The Relationship Between Agnostic Selective Classi cation, Active Learning and the Disagreement Coecient |
| Authors: | Roei Gelbhart |
| Supervisors: | Ran El-Yaniv |
| Currently accessibly only within the Technion network | |
| Abstract: | A selective classi er (f; g) comprises a classi cation function f and a binary selection function g, which determines if the classi er abstains from prediction, or uses f to predict. The classi er is called pointwise-competitive if it classi es each point identically to the best classi er in hindsight (from the same class), whenever it does not abstain. The quality of such a classi er is quanti ed by its rejection mass, de ned to be the probability mass of the points it rejects. A \fast" rejection rate is achieved if the rejection mass is bounded from above by ~O (1=m) where m is the number of labeled examples used to train the classi er (and ~O hides logarithmic factors). Pointwise-competitive selective (PCS) classi ers are intimately related to disagreement-based active learning and it is known that in the realizable case, a fast rejection rate of a known PCS algorithm (called Consistent Selective Strategy) is equivalent to an exponential speedup of the well-known CAL active algorithm. We focus on the agnostic setting, for which there is a known algorithm called LESS that learns a PCS classi er and achieves a fast rejection rate (depending on Hanneke's disagreement coecient) under strong assumptions. We present an improved PCS learning algorithm called ILESS for which we show a fast rate (depending on Hanneke's disagreement coecient) without any assumptions. Our rejection bound smoothly interpolates the realizable and agnostic settings. The main result of this thesis is an equivalence between the following three entities: (i) the existence of a fast rejection rate for any PCS learning algorithm (such as ILESS); (ii) a poly-logarithmic bound for Hanneke's disagreement coecient; and (iii) an exponential speedup for a new disagreement-based active learner called Active-ILESS. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2017/MSC/MSC-2017-30), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the MSC technical reports of 2017
To the main CS technical reports page