Learnability of Solutions to Conjunctive Queries: The Full Dichotomy

Hubie Chen, Matthew Valeriote
Proceedings of The 28th Conference on Learning Theory, PMLR 40:326-337, 2015.

Abstract

The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In order to obtain our negative result, we make use of universal-algebraic concepts, and our result is phrased in terms of the varietal property of non-congruence modularity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Chen15a, title = {Learnability of Solutions to Conjunctive Queries: The Full Dichotomy}, author = {Chen, Hubie and Valeriote, Matthew}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {326--337}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Chen15a.pdf}, url = {https://proceedings.mlr.press/v40/Chen15a.html}, abstract = {The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In order to obtain our negative result, we make use of universal-algebraic concepts, and our result is phrased in terms of the varietal property of non-congruence modularity.} }
Endnote
%0 Conference Paper %T Learnability of Solutions to Conjunctive Queries: The Full Dichotomy %A Hubie Chen %A Matthew Valeriote %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Chen15a %I PMLR %P 326--337 %U https://proceedings.mlr.press/v40/Chen15a.html %V 40 %X The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In order to obtain our negative result, we make use of universal-algebraic concepts, and our result is phrased in terms of the varietal property of non-congruence modularity.
RIS
TY - CPAPER TI - Learnability of Solutions to Conjunctive Queries: The Full Dichotomy AU - Hubie Chen AU - Matthew Valeriote BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Chen15a PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 326 EP - 337 L1 - http://proceedings.mlr.press/v40/Chen15a.pdf UR - https://proceedings.mlr.press/v40/Chen15a.html AB - The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In order to obtain our negative result, we make use of universal-algebraic concepts, and our result is phrased in terms of the varietal property of non-congruence modularity. ER -
APA
Chen, H. & Valeriote, M.. (2015). Learnability of Solutions to Conjunctive Queries: The Full Dichotomy. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:326-337 Available from https://proceedings.mlr.press/v40/Chen15a.html.

Related Material