Author name cluster

Nina Runde

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.

2 papers

2 author rows

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 2023 Conference Abstract

On Learning MSO-Formulas

Nina Runde

AbstractConsider the following supervised classification problem: given a backgroundstructure with a set of instances X and a training set S ⊆ X × {+, −}, we aimto find a hypothesis h: X → {+, −} from some hypothesis class H, that mapsevery instance to a class. Such a hypothesis is consistent with the training ex-ample when h(x) = c for (x, c) ∈ S. We consider a setup where the backgroundstructure is a relational structure A and an instance v̄ ∈ A^d is a d-tuple ofelements from the universe. We aim to learn a monadic second-order formulaφ(x̄) with |x̄| = d free instance variables, that is consistent with the trainingset. This means, that for every positive example in the training set (v̄, +) ∈ Swe have A |= φ(v̄) and for (v̄, −) ∈ S we have A ⊭ φ(v̄). We call the problemMSO-Learn and for d = 1 we speak of unary-MSO-Learn. We analyze the problem in the context of parameterized complexity and show that it is fixed-parameter tractable for d=1 on structures of bounded tree-width and graphs of bounded clique-width. Furthermore, we give bounds for d>1 in the PAC learning framework. Contributed talk given by Nina Runde

Details