Author name cluster

Steffen van Bergerem

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

CSL Conference 2025 Conference Paper

On the VC Dimension of First-Order Logic with Counting and Weight Aggregation

Steffen van Bergerem
Nicole Schweikardt

We prove optimal upper bounds on the Vapnik-Chervonenkis density of formulas in the extensions of first-order logic with counting (FOC_1) and with weight aggregation (FOWA_1) on nowhere dense classes of (vertex- and edge-)weighted finite graphs. This lifts a result of Pilipczuk, Siebertz, and Toruńczyk [Michał Pilipczuk et al. , 2018] from first-order logic on ordinary finite graphs to substantially more expressive logics on weighted finite graphs. Moreover, this proves that every FOC_1 formula and every FOWA_1 formula has bounded Vapnik-Chervonenkis dimension on nowhere dense classes of weighted finite graphs; thereby, it lifts a result of Adler and Adler [Hans Adler and Isolde Adler, 2014] from first-order logic to FOC_1 and FOWA_1. Generalising another result of Pilipczuk, Siebertz, and Toruńczyk [Michał Pilipczuk et al. , 2018], we also provide an explicit upper bound on the ladder index of FOC_1 and FOWA_1 formulas on nowhere dense classes. This shows that nowhere dense classes of weighted finite graphs are FOC_1-stable and FOWA_1-stable.

Details

CSL Conference 2025 Conference Paper

The Parameterized Complexity of Learning Monadic Second-Order Logic

Steffen van Bergerem
Martin Grohe
Nina Runde

Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in monadic second-order logic (MSO). We show that the problem of learning an MSO-definable concept from a training sequence of labeled examples is fixed-parameter tractable on graphs of bounded clique-width, and that it is hard for the parameterized complexity class para-NP on general graphs. It turns out that an important distinction to be made is between 1-dimensional and higher-dimensional concepts, where the instances of a k-dimensional concept are k-tuples of vertices of a graph. For the higher-dimensional case, we give a learning algorithm that is fixed-parameter tractable in the size of the graph, but not in the size of the training sequence, and we give a hardness result showing that this is optimal. By comparison, in the 1-dimensional case, we obtain an algorithm that is fixed-parameter tractable in both.

Details

Highlights Conference 2024 Conference Abstract

Learning Aggregate Queries Defined by First-Order Logic with Counting

Steffen van Bergerem

In the logical framework introduced by Grohe and Turán (TOCS 2004) for Boolean classification problems, the instances to classify are tuples from a logical structure, and Boolean classifiers are described by parametric models based on logical formulas. This is a specific scenario for supervised passive learning, where classifiers should be learned based on labelled examples. Existing results in this scenario focus on Boolean classification. This paper presents learnability results beyond Boolean classification. We focus on multiclass classification problems where the task is to assign input tuples to arbitrary integers. To represent such integer-valued classifiers, we use aggregate queries specified by an extension of first-order logic with counting terms called FOC1. Our main result shows the following: given a database of polylogarithmic degree, within quasi-linear time, we can build an index structure that makes it possible to learn FOC1-definable integer-valued classifiers in time polylogarithmic in the size of the database and polynomial in the number of training examples. This is joint work with Nicole Schweikardt.

Details

CSL Conference 2021 Conference Paper

Learning Concepts Described By Weight Aggregation Logic

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-order logic that allows to aggregate weights of tuples, compare such aggregates, and use them to build more complex formulas. We provide locality properties of fragments of this logic including Feferman-Vaught decompositions and a Gaifman normal form for a fragment called FOW₁, as well as a localisation theorem for a larger fragment called FOWA₁. This fragment can express concepts from various machine learning scenarios. Using the locality properties, we show that concepts definable in FOWA₁ over a weighted background structure of at most polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear time preprocessing.

Details