- Diversity, Equity, and Inclusion
- Research News
- Department Life
- Oral History of Cornell CS
- CS 40th Anniversary Booklet
- ABC Book for Computer Science at Cornell by David Gries
- Department Timeline
- Job Postings
- Ithaca Info
- Internal info
- Graduation Information
- Cornell Tech Colloquium
- Student Colloquium
- Fall 2023 Colloquium
- Conway-Walker Lecture Series
- Salton 2023 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University High School Programming Contests 2023
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop
A Framework for Interactive Learning
In many settings, learning algorithms are deployed "in the wild", where their output is used before the classifier has been fully trained. In this online context, a natural model of interaction is Angluin's (1988) Equivalence Query model: the algorithm proposes an output classifier; the user responds with either the feedback that the classifier is correct, or otherwise provides the algorithm with a point that is mislabeled. The algorithm takes this feedback into account in producing a new, potentially very different, classifier, and the process repeats. Angluin (1988) and much subsequent work have shown - among others - that a classifier from a class F can be learned using at most log_2 |F| iterations.
We propose and analyze a generalization of the Equivalence Query model beyond classifiers. The goal is to learn a "model" (e.g., a classifier) from a general class: in each iteration, the algorithm proposes such a model, and is either told that the model is correct, or otherwise is shown a "local correction". The feedback may be probabilistically incorrect (with probability 1-p < 0.5). Some natural classes of "models" to learn (beyond classifiers) are permutations/rankings (useful, e.g., in web search) and clusterings of data items (e.g., for image segmentation).
Our main contribution is to exhibit a natural condition which allows the log_2 |F| bound to carry over to many domains, and to degrade very gracefully as a function of p. Specifically, we show that if there is a (undirected, weighted) graph whose nodes are the models, such that corrections are always the first edge on a shortest path to the (unknown) ground-truth model, then log_2 |F| iterations are enough, and O(log_2 |F|) queries suffice in the presence of noise. This framework recovers as special cases several classical and recent bounds for learning classifiers and clusterings, and implies new bounds for learning a permutation. The algorithm is the natural generalization of Binary Search to undirected weighted graphs, and can be extended to directed graphs under additional conditions.
This talk is based on joint work with Ehsan Emamjomah-Zadeh, from STOC 2016, NIPS 2017, and SODA 2018.