Learning Using Local Membership Queries

Pranjal Awasthi, Vitaly Feldman, Varun Kanade
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:398-431, 2013.

Abstract

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: \beginenumerate \item 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. \item The class of polynomial-sized decision trees is polynomial time learnable under product distributions using O(log(n))-local queries. \item The class of polynomial size DNF formulas is learnable under the uniform distribution using O(log(n))-local queries in time n^O(log(log(n))). \item In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model. \endenumerate

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Awasthi13, title = {Learning Using Local Membership Queries}, author = {Awasthi, Pranjal and Feldman, Vitaly and Kanade, Varun}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {398--431}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Awasthi13.pdf}, url = {https://proceedings.mlr.press/v30/Awasthi13.html}, abstract = {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: \beginenumerate \item 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. \item The class of polynomial-sized decision trees is polynomial time learnable under product distributions using O(log(n))-local queries. \item The class of polynomial size DNF formulas is learnable under the uniform distribution using O(log(n))-local queries in time n^O(log(log(n))). \item In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model. \endenumerate} }
Endnote
%0 Conference Paper %T Learning Using Local Membership Queries %A Pranjal Awasthi %A Vitaly Feldman %A Varun Kanade %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Awasthi13 %I PMLR %P 398--431 %U https://proceedings.mlr.press/v30/Awasthi13.html %V 30 %X 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: \beginenumerate \item 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. \item The class of polynomial-sized decision trees is polynomial time learnable under product distributions using O(log(n))-local queries. \item The class of polynomial size DNF formulas is learnable under the uniform distribution using O(log(n))-local queries in time n^O(log(log(n))). \item In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model. \endenumerate
RIS
TY - CPAPER TI - Learning Using Local Membership Queries AU - Pranjal Awasthi AU - Vitaly Feldman AU - Varun Kanade BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Awasthi13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 398 EP - 431 L1 - http://proceedings.mlr.press/v30/Awasthi13.pdf UR - https://proceedings.mlr.press/v30/Awasthi13.html AB - 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: \beginenumerate \item 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. \item The class of polynomial-sized decision trees is polynomial time learnable under product distributions using O(log(n))-local queries. \item The class of polynomial size DNF formulas is learnable under the uniform distribution using O(log(n))-local queries in time n^O(log(log(n))). \item In addition we prove a number of results relating the proposed model to the traditional PAC model and the PAC+MQ model. \endenumerate ER -
APA
Awasthi, P., Feldman, V. & Kanade, V.. (2013). Learning Using Local Membership Queries. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:398-431 Available from https://proceedings.mlr.press/v30/Awasthi13.html.

Related Material