Interactive Learning of Classifiers and Other Structures

on YouTube ↗01h 31m

" summary

Interactive learning studies when an algorithm queries labels or other feedback adaptively and what guarantees that yields: active learning can cut label needs from ~1/ε to ~log(1/ε) in ideal cases but needs care to avoid biased sampling, so mellow active learning uses conservative queries and a disagreement coefficient to prove consistency. Graph-based active annotation finds cut edges by midpoint queries; linear/UCB bandits drive interactive image search and captioning experiments showing roughly 2–3× and ~5× reductions in labeling effort respectively.

AI-written summary · about

" chapters (36)

1. 0:00Introduction to active learning
2. 1:20Defining active learning
3. 3:36Explanation-based learning
4. 6:03Interactive unsupervised learning
5. 8:43Theoretical questions
6. 10:45Heuristics and challenges
7. 13:56Sampling bias problem
8. 16:07Addressing bias
9. 18:46Benefits of active learning
10. 22:12Query strategies
11. 25:12Mellow active learning
12. 30:10Analysis of mellow scheme
13. 32:43Disagreement coefficient
14. 36:15Linear separators
15. 37:24Practical active learning
16. 40:01Margin-based learning
17. 41:52Active annotation
18. 43:51Graph-based annotation
19. 46:46Active annotation algorithm
20. 49:33Practical challenges
21. 52:02Bandits for active learning
22. 54:47Stochastic bandit problem
23. 58:54Bandit algorithms
24. 1:00:54Bandit algorithms analysis
25. 1:03:37UCB algorithm details
26. 1:07:06Regret bounds analysis
27. 1:09:14Bandit performance
28. 1:12:32Algorithm parameterization
29. 1:15:53Non-adaptive strategies
30. 1:16:43Cartoon caption contest
31. 1:19:27Structured bandits
32. 1:21:47Linear bandits
33. 1:23:30Image search application
34. 1:25:52Search results
35. 1:26:31Future directions
36. 1:28:21Discussion and Q&A

" related talks

• 37mActive Teaching, Human LearningVincent D Warmerdam · PyData Eindhoven 2023
• 39mActive learning in the interactive python environmentJan Freyberg · PyData London 2019
• 43mBeyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active LearningKamalika Chaudhuri · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 30mActive Learning and Human-in-the-Loop Machine LearningLukas Biewald · Data By the Bay 2016
• 58mLabeling a Data Set Using Sublinearly Many QueriesSanjoy Dasgupta · Sublinear Algorithms and Nearest-Neighbor Search
• 25mConfidence-Based Active LearningKamalika Chaudhuri · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 51mEfficient Deep Learning with Humans in the LoopZachary Lipton · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 18mActive Learning for Neurosymbolic Program SynthesisIşıl Dillig, Osbert Bastani, Celeste Barnaby, Jocelyn Qiaochu Chen, Ramya Ramalingam · PLDI 2026