On Learning MSO-Formulas

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

Authors

• Nina Runde

Keywords

No keywords are indexed for this paper.