Learning definable hypotheses on trees
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning MSO-definable hypotheses on string
We study the classification problems over string data for hypotheses specified by formulas of monadic second-order logic MSO. The goal is to design learning algorithms that run in time polynomial in the size of the train…
General ClassificationLearning first-order definable concepts over structures of small degree
We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some background structure. We show that within this framework, concepts defined by first-orde…
BIG-bench Machine LearningGraph neural networks and MSO
We give an alternative proof for the existing result that recurrent graph neural networks working with reals have the same expressive power in restriction to monadic second-order logic MSO as the graded modal substitutio…
TranslationA necessary and sufficient condition for two relations to induce the same definable set family
In Pawlak rough sets, the structure of the definable set families is simple and clear, but in generalizing rough sets, the structure of the definable set families is a bit more complex. There has been much research work …
Bayesian Verification under Model Uncertainty
Machine learning enables systems to build and update domain models based on runtime observations. In this paper, we study statistical model checking and runtime verification for systems with this ability. Two challenges …
model