Algorithms for Learning with Local Queries: Varun Kanade, UC Berkeley (CS Colloquium)

Starts:
11:00 am on Monday, March 24, 2014
Ends:
12:15 pm on Monday, March 24, 2014
Location:
Hariri Institute
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