On Exact Learning of Unordered Tree Patterns
On Exact Learning of Unordered Tree Patterns
复制标题
无序树模式的精确学习
DOI：
10.1023/a:1010971904477
复制
发表时间：
2001
期刊：
影响因子：
7.5
通讯作者：
Prasad Tadepalli
中科院分区：
文献类型：
--
作者：
Thomas R. Amoth;P. Cull;Prasad Tadepalli
在信息提取和符号数学等许多任务中，树模式是表示规则和假设的自然候选者。树型模式是一棵带有标记节点的树，其中一些叶子可能被标记为变量，而树实例没有变量。如果对变量进行一致的替换，允许将子树映射到实例的匹配子树，则树模式匹配实例。树木模式的有限联合称为森林。在本文中，我们研究了在子树无序的情况下，查询树模式的可学习性。可学习性由匹配语义决定，匹配语义由从模式子树到实例子树的映射类型定义。我们首先证明，当子树之间的映射是一对一到上时，无论学习器的计算能力如何，无序的树模式和森林都不能从等价查询和子集查询中精确地学习。树和森林模式可以从一对一映射的等价查询和成员查询中学习。最后，我们通过描述一类包含非递归单谓词Horn子句的称为子句树的树模式，将学习树模式的问题与归纳逻辑规划联系起来，并表明该类可以从等价查询和成员查询中学习。
Tree patterns are natural candidates for representing rules and hypotheses in many tasks such as information extraction and symbolic mathematics. A tree pattern is a tree with labeled nodes where some of the leaves may be labeled with variables, whereas a tree instance has no variables. A tree pattern matches an instance if there is a consistent substitution for the variables 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 study the learnability of tree patterns from queries when the subtrees are unordered. The learnability is determined by the semantics of matching as defined by the types of mappings from the pattern subtrees to the instance subtrees. We first show that unordered tree patterns and forests are not exactly learnable from equivalence and subset queries when the mapping between subtrees is one-to-one onto, regardless of the computational power of the learner. Tree and forest patterns are learnable from equivalence and membership queries for the one-to-one into mapping. Finally, we connect the problem of learning tree patterns to inductive logic programming by describing a class of tree patterns called Clausal trees that includes non-recursive single-predicate Horn clauses and show that this class is learnable from equivalence and membership queries.