Learning first-order definable concepts over structures of small degree

2017/01/19 by Martin Grohe, Martin Ritzert, Grohe, Martin +1
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.1701.05487

openalex publication_date 2017/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Learning Concepts Definable in First-Order Logic with Counting
• Learning Concepts Described by Weight Aggregation Logic
• Enforcing and Discovering Structure in Machine Learning
• Learning MSO-definable hypotheses on string
• Implicitly Learning to Reason in First-Order Logic