TR#: | MSC-2017-30 |

Class: | MSC |

Title: | The Relationship Between Agnostic Selective Classication, Active Learning and the Disagreement Coecient |

Authors: | Roei Gelbhart |

Supervisors: | Ran El-Yaniv |

Currently accessibly only within the Technion network | |

Abstract: | A selective classier (f; g) comprises a classication function f and a binary selection function g, which determines if the classier abstains from prediction, or uses f to predict. The classier is called pointwise-competitive if it classies each point identically to the best classier in hindsight (from the same class), whenever it does not abstain. The quality of such a classier is quantied by its rejection mass, dened 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 classier (and ~O hides logarithmic factors). Pointwise-competitive selective (PCS) classiers 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 classier 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