Learning function-free Horn expressions

作     者：Khardon, R 

作者机构：Univ Edinburgh Div Informat Edinburgh EH9 3JZ Midlothian Scotland 

出 版 物：《MACHINE LEARNING》 (机器学习)

年 卷 期：1999年第37卷第3期

页      面：241-275页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Office of Naval Research, ONR, (N00014-95-1-0550) Army Research Office, ARO, (DAAL03-92-G-0115) Harvard University Engineering and Physical Sciences Research Council, EPSRC, (GR/M21409) 

主　　题：computational learning theory inductive logic programming Horn expressions direct products 

摘      要：The problem of learning universally quantified function free first order Horn expressions is studied. Several models of learning from equivalence and membership queries are considered, including the model where interpretations are examples (Learning from Interpretations), the model where clauses are examples (Learning from Entailment), models where extensional or intentional background knowledge is given to the learner (as done in Inductive Logic Programming), and the model where the reasoning performance of the learner rather than identification is of interest (Learning to Reason). We present learning algorithms for all these tasks for the class of universally quantified function free Horn expressions. The algorithms are polynomial in the number of predicate symbols in the language and the number of clauses in the target Horn expression but exponential in the arity of predicates and the number of universally quantified variables. We also provide lower bounds for these tasks by way of characterising the VC-dimension of this class of expressions. The exponential dependence on the number of variables is the main gap between the lower and upper bounds.