IC Colloquium : Algorithms for Learning using Local Queries
Event details
| Date | 31.03.2014 |
| Hour | 16:15 › 17:30 |
| Location | |
| Category | Conferences - Seminars |
By : Varun Kanade, UC Berkeley
IC Faculty candidate
Abstract
The probably approximately correct (PAC) learning setting introduced by Valiant (1984) is a theoretical framework for studying automated learning from examples. The membership query model (MQ) is an extension, where the learning algorithm is allowed to construct its own examples and ask a (possibly human) oracle for labels. A rich theory has been developed in this framework, connecting learning to other areas of theoretical computer science, including complexity, cryptography, and the analysis of boolean functions.
There are two main shortcomings that make this theory less relevant in practice:
(i) Many algorithms only have guarantees under the uniform distribution
(ii) Membership query algorithms ask queries that appear nonsensical to humans
In this talk, I will present work that makes progress on both these fronts. We define a notion of local membership queries, where the learning algorithm is allowed to construct queries only through small modifications to examples received as part of the training set. We consider a class of smooth distributions, far more general than the uniform distribution, and show that the class of decision trees can be learned with local membership queries.
I will present a few other results and some directions for future work.
(Based on joint work with P. Awasthi and V. Feldman)
Biography
Varun Kanade is currently a Simons Postdoctoral Fellow at the University of California, Berkeley. He obtained his Ph.D. from Harvard University under the guidance of Prof. Leslie Valiant. He received his B.Tech. from the Indian Institute of Technology, Bombay. His research interests are in learning theory, but also more broadly in machine learning, theoretical computer science and evolutionary biology.
More information
IC Faculty candidate
Abstract
The probably approximately correct (PAC) learning setting introduced by Valiant (1984) is a theoretical framework for studying automated learning from examples. The membership query model (MQ) is an extension, where the learning algorithm is allowed to construct its own examples and ask a (possibly human) oracle for labels. A rich theory has been developed in this framework, connecting learning to other areas of theoretical computer science, including complexity, cryptography, and the analysis of boolean functions.
There are two main shortcomings that make this theory less relevant in practice:
(i) Many algorithms only have guarantees under the uniform distribution
(ii) Membership query algorithms ask queries that appear nonsensical to humans
In this talk, I will present work that makes progress on both these fronts. We define a notion of local membership queries, where the learning algorithm is allowed to construct queries only through small modifications to examples received as part of the training set. We consider a class of smooth distributions, far more general than the uniform distribution, and show that the class of decision trees can be learned with local membership queries.
I will present a few other results and some directions for future work.
(Based on joint work with P. Awasthi and V. Feldman)
Biography
Varun Kanade is currently a Simons Postdoctoral Fellow at the University of California, Berkeley. He obtained his Ph.D. from Harvard University under the guidance of Prof. Leslie Valiant. He received his B.Tech. from the Indian Institute of Technology, Bombay. His research interests are in learning theory, but also more broadly in machine learning, theoretical computer science and evolutionary biology.
More information
Practical information
- Informed public
- Free
- This event is internal
Contact
- Tania Epars