Modularity in Query-Based Concept Learning

Benjamin Caulfield, Sanjit A. Seshia
Proceedings of the International Conference on Neuro-symbolic Systems, PMLR 288:721-744, 2025.

Abstract

We define and study the problem of modular concept learning, which is learning a concept that is a cross-product (i.e., Cartesian product) of component concepts. The theory of concept learning provides a framework for analyzing algorithms for inductive synthesis of programs and systems, which involves synthesis from examples and queries. Modular concept learning is important for systems that can be broken into subsystems that each act independently of the other. We analyze this problem with respect to different types of queries that are made to an oracle, formalized as an oracle interface. We show that if a given oracle interface cannot directly answer questions about the components, learning can be difficult, even when the components are easy to learn with the same type of oracle queries. Specifically, we show that learning from membership, equivalence, or subset queries is hard. However, these problems become tractable when oracles are given a positive example and are allowed to ask membership queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v288-caulfield25a, title = {Modularity in Query-Based Concept Learning}, author = {Caulfield, Benjamin and Seshia, Sanjit A.}, booktitle = {Proceedings of the International Conference on Neuro-symbolic Systems}, pages = {721--744}, year = {2025}, editor = {Pappas, George and Ravikumar, Pradeep and Seshia, Sanjit A.}, volume = {288}, series = {Proceedings of Machine Learning Research}, month = {28--30 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v288/main/assets/caulfield25a/caulfield25a.pdf}, url = {https://proceedings.mlr.press/v288/caulfield25a.html}, abstract = {We define and study the problem of modular concept learning, which is learning a concept that is a cross-product (i.e., Cartesian product) of component concepts. The theory of concept learning provides a framework for analyzing algorithms for inductive synthesis of programs and systems, which involves synthesis from examples and queries. Modular concept learning is important for systems that can be broken into subsystems that each act independently of the other. We analyze this problem with respect to different types of queries that are made to an oracle, formalized as an oracle interface. We show that if a given oracle interface cannot directly answer questions about the components, learning can be difficult, even when the components are easy to learn with the same type of oracle queries. Specifically, we show that learning from membership, equivalence, or subset queries is hard. However, these problems become tractable when oracles are given a positive example and are allowed to ask membership queries.} }
Endnote
%0 Conference Paper %T Modularity in Query-Based Concept Learning %A Benjamin Caulfield %A Sanjit A. Seshia %B Proceedings of the International Conference on Neuro-symbolic Systems %C Proceedings of Machine Learning Research %D 2025 %E George Pappas %E Pradeep Ravikumar %E Sanjit A. Seshia %F pmlr-v288-caulfield25a %I PMLR %P 721--744 %U https://proceedings.mlr.press/v288/caulfield25a.html %V 288 %X We define and study the problem of modular concept learning, which is learning a concept that is a cross-product (i.e., Cartesian product) of component concepts. The theory of concept learning provides a framework for analyzing algorithms for inductive synthesis of programs and systems, which involves synthesis from examples and queries. Modular concept learning is important for systems that can be broken into subsystems that each act independently of the other. We analyze this problem with respect to different types of queries that are made to an oracle, formalized as an oracle interface. We show that if a given oracle interface cannot directly answer questions about the components, learning can be difficult, even when the components are easy to learn with the same type of oracle queries. Specifically, we show that learning from membership, equivalence, or subset queries is hard. However, these problems become tractable when oracles are given a positive example and are allowed to ask membership queries.
APA
Caulfield, B. & Seshia, S.A.. (2025). Modularity in Query-Based Concept Learning. Proceedings of the International Conference on Neuro-symbolic Systems, in Proceedings of Machine Learning Research 288:721-744 Available from https://proceedings.mlr.press/v288/caulfield25a.html.

Related Material