On exact learning of unordered tree patterns

Citation
Tr. Amoth et al., On exact learning of unordered tree patterns, MACH LEARN, 44(3), 2001, pp. 211-243
Citations number
18
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
MACHINE LEARNING
ISSN journal
08856125 → ACNP
Volume
44
Issue
3
Year of publication
2001
Pages
211 - 243
Database
ISI
SICI code
0885-6125(2001)44:3<211:OELOUT>2.0.ZU;2-F
Abstract
Tree patterns are natural candidates for representing rules and hypotheses in many tasks such as information extraction and symbolic mathematics. A tr ee pattern is a tree with labeled nodes where some of the leaves may be lab eled with variables, whereas a tree instance has no variables. A tree patte rn matches an instance if there is a consistent substitution for the variab les that allows a mapping of subtrees to matching subtrees of the instance. A finite union of tree patterns is called a forest. In this paper, we stud y the learnability of tree patterns from queries when the subtrees are unor dered. The learnability is determined by the semantics of matching as defin ed by the types of mappings from the pattern subtrees to the instance subtr ees. We first show that unordered tree patterns and forests are not exactly learnable from equivalence and subset queries when the mapping between sub trees is one-to-one onto, regardless of the computational power of the lear ner. Tree and forest patterns are learnable from equivalence and membership queries for the one-to-one into mapping. Finally, we connect the problem o f learning tree patterns to inductive logic programming by describing a cla ss of tree patterns called Clausal trees that includes non-recursive single -predicate Horn clauses and show that this class is learnable from equivale nce and membership queries.