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.
- Interpreting nowhere dense graph classes as a classical notion of model theory
- Containment of monadic Datalog programs via bounded clique-width
- scientific article; zbMATH DE number 2086423 (Why is no real title available?)
- scientific article; zbMATH DE number 7559449 (Why is no real title available?)
- Learning definable hypotheses on trees
- Learning first-order definable concepts over structures of small degree
- On low rank-width colorings
- Model checking on interpretations of classes of bounded local cliquewidth
- Learning concepts described by weight aggregation logic
- Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures
- Learning concepts definable in first-order logic with counting
- Decidability of querying first-order theories via countermodels of finite width
- The parameterized complexity of learning monadic second-order logic
- On the VC dimension of first-order logic with counting and weight aggregation
- Learning aggregate queries defined by first-order logic with counting
- Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
This page was built for publication: Learnability and definability in trees and similar structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705070)
