Learning first-order definable concepts over structures of small degree
This provides a theoretical foundation for efficient learning in declarative machine learning settings, though it appears incremental as it builds on existing logical frameworks and PAC learning theory.
The paper tackles the problem of learning concepts defined by first-order formulas over background structures with small degree, showing that such concepts can be learned in polylogarithmic time within the PAC learning framework.
We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some background structure. We show that within this framework, concepts defined by first-order formulas over a background structure of at most polylogarithmic degree can be learned in polylogarithmic time in the "probably approximately correct" learning sense.