Exact learning of unordered tree patterns from queries
Thomas R. Amoth, Paul Cull, Prasad V. Tadepalli · 1999
We consider learning tree patterns from queries extending our preceding work [Amoth, Cull, & Tadepalli, 1998] . The instances in this paper are unordered trees with nodes labeled by constant identifiers. The concepts are tree patterns and unions of tree patterns (unordered forests) with leaves labeled with constants or variables. A tree pattern matches any tree with its variables replaced with constant subtrees. A negative result for learning with equivalence and membership/subset queries is shown for unordered trees where a successful match requires the number of children in the pattern and instance to be the same. Unordered trees and forests are shown to be learnable with an alternative matching semantics that allows an instance to have extra children at each node. 1 INTRODUCTION Many applications in mathematics and language processing represent data more naturally as trees (or as unions of these) than as vectors of features. Tree patterns also provide more information than simple s...