Learnability and definability in trees and similar structures
type: Item
instance of: scholarly article
title: Learnability and definability in trees and similar structures
zbMATH Open document ID: 1062.03031
author: Martin Grohe
author: Gy. Turán
published in: Theory of Computing Systems
publication date: 2005-01-25T00:00:00Z
review text: The problem of concept learning is to identify an unknown set from a given family of sets. A universe is a nonempty finite set \(A\). A vocabulary \(\tau\) is a finite set of predicates defined on \(A\). A structure is the pair (\(A,\tau\)). An atomic formula is \({x = y}\) or \({R(x_1,\dots ,x_r)}\), where \({R \in \tau}\). Formulas of first-order logic (FO) are built up from atomic formulas using Boolean operations and quantification over individual variables. Monadic-second order logic (MSO) is the extension of FO by monadic predicates \({X(x)}\) defined on \(A\) and quantification over predicate variables. The elements \({b_1,\dots ,b_l}\) from \(A\) in the formula \(\varphi({x_1,\dots ,x_k, b_1,\dots ,b_l})\) are parameters. A concept class is a family \(\mathcal{C} \subseteq 2^V\) of subsets of a set \(V\). Let \({U \subseteq V}\) and \(\mathcal{C} \cap U = \{C \cap U \mid C \in\mathcal{C}\}\). The set \(U\) is shattered by \(\mathcal{C}\) if \(\mathcal{C} \cap U = 2^U\). The Vapnik-Chervonenkis dimension, or VC-dimension VC(\(\mathcal{C}\)) of \(\mathcal{C}\) is the maximum of the sizes of the shattered subsets of \(V\). It is shown: 1) MSO formulas (FO formulas) with parameters have bounded VC-dimension over structures of bounded clique-width (local clique-width); 2) MSO formulas of a fixed size have bounded strong consistency dimension over MSO formulas of a fixed larger size, for labelled finite trees; 3) these bounds imply positive learnability results for Probably Approximately Correct (PAC) learning. The proofs are based on bounds for related definability problems for finite automata over labelled trees.
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 68Q32
Mathematics Subject Classification ID: 03B15
zbMATH DE Number: 2130949
zbMATH Keywords: first-order logic
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: logical predicate structure
zbMATH Keywords: finite automata over trees
zbMATH Keywords: definability
zbMATH Keywords: learnability
zbMATH Keywords: probably approximately correct (PAC) learning
MaRDI profile type: Publication
full work available at URL: s00224-003-1112-8
OpenAlex ID: W1996805091
DOI: 10.1007/S00224-003-1112-8
description: scientific article; zbMATH DE number 2130949