The Relationship Between Agnostic Selective Classification, Active Learning and the Disagreement Coefficient
Authors: Roei Gelbhart, Ran El-Yaniv
JMLR 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The main result of this paper 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 coefficient; and (iii) an exponential speedup for a new disagreement-based active learner called Active-ILESS. We prove that Active-ILESS, despite being very similar to Oracular CAL Hsu (2010), exhibits an improved label complexity, in comparison to that proved for Oracular CAL. Our second and main contribution is to show a complete equivalence between (i) selective classification with a fast R rejection rate, (ii) an AL algorithm, Active-ILESS, with an R exponential speedup, and (iii) the existence of an f with a disagreement coefficient bounded by polylog(1/r). This is illustrated in Figure 1, where the blue errors indicate the equivalence relationships we prove in this paper, and the red arrow indicates a previously known result (Hsu, 2010; Hanneke, 2007), and can also be deduced from the other arrows. |
| Researcher Affiliation | Academia | Roei Gelbhart EMAIL Department of Computer Science Technion Israel Institute of Technology Ran El-Yaniv EMAIL Department of Computer Science Technion Israel Institute of Technology |
| Pseudocode | Yes | Strategy 1 Agnostic Low-Error Selective Strategy (LESS) Input: Sample set of size m, Sm, Confidence level δ Hypothesis class F with VC dimension d Output: A selective classifier (h, g) ... Strategy 2 Improved Low-Error Selective Strategy (ILESS) Input: Sample set of size m, Sm, Confidence level δ Hypothesis class F with VC dimension d Output: A selective classifier (h, g) ... Strategy 3 Agnostic Low-Error Active Learning Strategy (Active-ILESS) Input: ϵ and/or m depending on the desired termination condition (error or labeling budget, respectively) Confidence level δ Hypothesis class F with VC dimension d An unlabeled input sequence sampled i.i.d from PX,Y: x1, x2, x3, . . . Output: A classifier ˆf ... Strategy 4 Batch Improved Low-Error Selective Strategy (Batch-ILESS) Input: Sample set of size m, Sm, Confidence level δ Hypothesis class F with VC dimension d Output: A selective classifier (h, g) |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | A learning problem is specified via a hypothesis class F and an unknown probability distribution PX,Y. The paper deals with theoretical analysis of algorithms under abstract distributions and hypothesis classes, not specific datasets. |
| Dataset Splits | No | The paper does not mention any specific datasets used for empirical evaluation, and therefore does not provide dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental results or the hardware used to obtain them. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not provide details on experimental setup, hyperparameters, or training configurations. |