Published on Sat Apr 05 2014

A Compression Technique for Analyzing Disagreement-Based Active Learning

Yair Wiener, Steve Hanneke, Ran El-Yaniv

We introduce a new characterization of the label complexity of disagreement-based active learning. The leading quantity is the version space compression set size. We show new speedup results for two well known active learning algorithms.

0
0
0
Abstract

We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.

Fri Apr 19 2019
Machine Learning
Disagreement-based Active Learning in Online Settings
The aim of the algorithm is to minimize the number of queries and prediction errors over a horizon of length $T. The algorithm can be modified to operate at a different point on the tradeoff curve.
0
0
0
Thu Apr 30 2015
Machine Learning
Hierarchical Subquery Evaluation for Active Learning on a Graph
Expected Error Reduction has been one of the strongest-performing informativeness criteria for active learning. Until now, it has also been prohibitively costly to compute for sizeable datasets. Our algorithm is consistent over multiple runs and achieves high accuracy.
0
0
0
Wed Jan 15 2020
Machine Learning
Noise-tolerant, Reliable Active Classification with Comparison Queries
With the explosion of massive, widely available unlabeled data, finding label and time efficient, robust learning algorithms has become more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label.
0
0
0
Sun Mar 19 2017
Machine Learning
The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficient
A selective classifier (f,g) comprises a classification function f and a binary selection function g. The classifier is called pointwise-competitive if it classifies each point identically to the best classifier in hindsight (from the same class), whenever it does not abstain.
0
0
0
Thu Feb 16 2017
Machine Learning
Dynamic Partition Models
We present a new approach for learning compact and intuitive distributed representations with binary encoding. Rather than summing up expert votes, we employ for each variable the opinion of the most reliable expert. Data points are explained through a partitioning of the variables into expert supports.
0
0
0
Mon Aug 08 2011
Machine Learning
Activized Learning: Transforming Passive to Active with Improved Label Complexity
We prove that, in noise-free classifier learning for VC classes,any passive learning algorithm can be transformed into an active learning algorithm with asymptotically superior label complexity. We also extend these results to active learning in the presence of label noise.
0
0
0