Learnability and definability in trees and similar structures
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.
probably approximately correct (PAC) learning
scientific article; zbMATH DE number 2130949