Modularity in Query-Based Concept Learning
This addresses a theoretical problem in concept learning for AI and machine learning researchers, but it appears incremental as it builds on existing query-based learning frameworks.
The paper tackles the problem of modular concept learning, where a concept is a cross product of components, and shows that learning the whole concept can be reduced to learning the components depending on the oracle interface. It finds that learning from superset queries is easy, but from membership, equivalence, or subset queries is harder, though tractable when oracles use positive examples and membership queries.
We define and study the problem of modular concept learning, that is, learning a concept that is a cross product of component concepts. If an element's membership in a concept depends solely on it's membership in the components, learning the concept as a whole can be reduced to learning the components. We analyze this problem with respect to different types of oracle interfaces, defining different sets of queries. If a given oracle interface cannot answer questions about the components, learning can be difficult, even when the components are easy to learn with the same type of oracle queries. While learning from superset queries is easy, learning from membership, equivalence, or subset queries is harder. However, we show that these problems become tractable when oracles are given a positive example and are allowed to ask membership queries.