Learning first-order definable concepts over structures of small degree

2017-01-19 · Martin Grohe, Martin Ritzert

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.

📄 PDF Abstract BibTeX arXiv:1701.05487

Code (0)

등록된 구현이 없습니다.

Tasks

BIG-bench Machine Learning

Learning Concepts Definable in First-Order Logic with Counting

2019-09-09 · Steffen van Bergerem

We study Boolean classification problems over relational background structures in the logical framework introduced by Grohe and Tur\'an (TOCS 2004). It is known (Grohe and Ritzert, LICS 2017) that classifiers definable i…

General Classification PAC learning

Learning Concepts Described by Weight Aggregation Logic

2020-09-22 · Steffen van Bergerem, Nicole Schweikardt

We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of first-ord…

Granule Description based on Compound Concepts

2021-10-29 · Jianqin Zhou, Sichun Yang, Xifeng Wang, Wanquan Liu

Concise granule descriptions for definable granules and approaching descriptions for indefinable granules are challenging and important issues in granular computing. The concept with only common attributes has been inten…

Object

Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

2026-06-29 · Clemens Kinn, Philipp Petersen arxiv

We study binary classification problems whose decision sets are given by definable sets in o-minimal expansions of the real field. Motivated by cell decomposition of definable sets, we introduce traceable sets as a class…

Binary Classification

Learning MSO-definable hypotheses on string

2017-08-27 · Martin Grohe, Christof Löding, Martin Ritzert

We study the classification problems over string data for hypotheses specified by formulas of monadic second-order logic MSO. The goal is to design learning algorithms that run in time polynomial in the size of the train…

General Classification