Labeling a Data Set Using Sublinearly Many Queries
summary
Classic uncertainty heuristics are provably inconsistent — they can converge to the wrong classifier even with infinite labels. The alternative active annotation formulation requires producing a fully labeled dataset with (ε,δ) guarantees while minimizing human queries. Graph-based label propagation fills unlabeled points by solving the Laplacian least-squares (random-walk probabilities), but can fail; a shortest-path cut-edge strategy identifies boundary edges with O(k log Δ) queries, yielding label complexity ~ n^{1−1/d} under smoothness. Hierarchical cluster sampling (random samples per cluster) and richer feedback like weak rules or highlighted features (Snorkel-style) cut queries dramatically and can make previously hard classes learnable.
AI-written summary · about
chapters (10)
- 0:00Introduction to active learning
- 2:34Practical vs theoretical gaps
- 5:56Failings of standard heuristics
- 9:49Formalizing active learning
- 13:56Active annotation approach
- 19:14Graph-based methods
- 28:46Cut-edge identification
- 35:56Statistical rates and complexity
- 44:37Cluster-based strategies
- 50:08Future directions and feedback
related talks
43mBeyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning
01h 31mInteractive Learning of Classifiers and Other Structures
33mWeak supervision: a new paradigm for unreliable data
01h 00mKnow When You Know: Handling Adversarial Data by Abstaining
30mActive Learning and Human-in-the-Loop Machine Learning
51mEfficient Deep Learning with Humans in the Loop
39mActive learning in the interactive python environment
51mHow to Predict When Estimation is Hard: Algorithms for Learning on Graphs