Learning logic programs with structured background knowledge

Tamás Horváth

doi:10.1016/S0004-3702(01)00062-5

Learning logic programs with structured background knowledge

2001-05-01

13

PRE

AI

DOI：10.1016/S0004-3702(01)00062-5

Original

Original request for help

Save

Abstract

En 中文

The efficient learnability of restricted classes of logic programs is studied in the PAC framework of computational learning theory, We develop the product homomorphism method, which gives polynomial PAC learning algorithms for a nonrecursive Horn clause with function-free ground background knowledge, if the background knowledge satisfies some structural properties. The method is based on a characterization of the concept that corresponds to the relative least general generalization of a set of positive examples with respect to the background knowledge. The characterization is formulated in terms of products and homomorphisms. In the applications this characterization is turned into an explicit combinatorial description, which is then translated into the language of nonrecursive Horn clauses, We show that a nonrecursive Horn clause is polynomially PAC-learnable if there is a single binary background predicate and the ground atoms in the background knowledge form a forest. If the ground atoms in the background knowledge form a disjoint union of cycles then the situation is different, as the shortest consistent hypothesis may have exponential size. In this case polynomial PAC-learnability holds if a different representation language is used. We also consider the complexity of hypothesis finding for multiple clauses in some restricted cases. (C) 2001 Elsevier Science B,V. All rights reserved.

Keywords:

computational learning theory

PAC learning

concept learning

inductive logic programming

VC-dimension

Learning logic programs with structured background knowledge

Abstract

AI Summary

Journal

Organization