2019/09/24 by Emilie Grienenberger, Martin Ritzert · 1 citation
Computer Science · #cs.AI #cs.LG #cs.LO
paper · pdf · doi:10.4230/lipics.icdt.2019.24
Full version of ICDT 2019 paper
arxiv created 2019/09/24 · arxiv updated 2019/09/25
We study the problem of learning properties of nodes in tree structures. Those properties are specified by logical formulas, such as formulas from first-order or monadic second-order logic. We think of the tree as a database encoding a large dataset and therefore aim for learning algorithms which depend at most sublinearly on the size of the tree. We present a learning algorithm for quantifier-free formulas where the running time only depends polynomially on the number of training examples, but not on the size of the background structure. By a previous result on strings we know that for general first-order or monadic second-order (MSO) formulas a sublinear running time cannot be achieved. However, we show that by building an index on the tree in a linear time preprocessing phase, we can achieve a learning algorithm for MSO formulas with a logarithmic learning phase.