2017/03/19 by Roei Gelbhart, Gelbhart, Roei, Ran El‐Yaniv +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Topic Modeling
paper · pdf · doi:10.48550/arxiv.1703.06536
openalex publication_date 2017/03/19 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
A selective classifier (f,g) comprises a classification function f and a\nbinary selection function g, which determines if the classifier abstains from\nprediction, or uses f to predict. The classifier is called\npointwise-competitive if it classifies each point identically to the best\nclassifier in hindsight (from the same class), whenever it does not abstain.\nThe quality of such a classifier is quantified by its rejection mass, defined\nto be the probability mass of the points it rejects. A "fast" rejection rate is\nachieved if the rejection mass is bounded from above by O(1/m) where m is the\nnumber of labeled examples used to train the classifier (and O hides\nlogarithmic factors). Pointwise-competitive selective (PCS) classifiers are\nintimately related to disagreement-based active learning and it is known that\nin the realizable case, a fast rejection rate of a known PCS algorithm (called\nConsistent Selective Strategy) is equivalent to an exponential speedup of the\nwell-known CAL active algorithm.\n We focus on the agnostic setting, for which there is a known algorithm called\nLESS that learns a PCS classifier and achieves a fast rejection rate (depending\non Hanneke's disagreement coefficient) under strong assumptions. We present an\nimproved PCS learning algorithm called ILESS for which we show a fast rate\n(depending on Hanneke's disagreement coefficient) without any assumptions. Our\nrejection bound smoothly interpolates the realizable and agnostic settings. The\nmain result of this paper is an equivalence between the following three\nentities: (i) the existence of a fast rejection rate for any PCS learning\nalgorithm (such as ILESS); (ii) a poly-logarithmic bound for Hanneke's\ndisagreement coefficient; and (iii) an exponential speedup for a new\ndisagreement-based active learner called ActiveiLESS.\n