Learning Using Local Membership Queries

author: Pranjal Awasthi, Machine Learning Department, School of Computer Science, Carnegie Mellon University
published: Aug. 9, 2013,   recorded: June 2013,   views: 3533


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We introduce a new model of membership query (MQ) learning, where the learning algorithm is restricted to query points that are close to random examples drawn from the underlying distribution. The learning model is intermediate between the PAC model (Valiant,1984) and the PAC+MQ model (where the queries are allowed to be arbitrary points).

Membership query algorithms are not popular among machine learning practitioners. Apart from the obvious difficulty of adaptively querying labellers, it has also been observed that querying unnatural points leads to increased noise from human labellers (Lang and Baum, 1992). This motivates our study of learning algorithms that make queries that are close to examples generated from the data distribution.

We restrict our attention to functions defined on the n-dimensional Boolean hypercube and say that a membership query is local if its Hamming distance from some example in the (random) training data is at most O(log(n)). We show the following results in this model:

1. The class of sparse polynomials (with coefficients in R) over {0,1}n is polynomial time learnable under a large class of locally smooth distributions using O(log(n))-local queries. This class also includes the class of O(log(n))-depth decision trees.

2. The class of polynomial-sized decision trees is polynomial time learnable under product distributions using O(log(n))-local queries.

3. The class of polynomial size DNF formulas is learnable under the uniform distribution using O(log(n))-local queries in time nO(log(log(n))).

4. In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model.

See Also:

Download slides icon Download slides: colt2013_awasthi_queries_01.pdf (424.1┬áKB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: