Learning logic programs with structured background knowledge

The efficient learnability of restricted classes of logic programs is studi ed in the PAC framework of computational learning theory, We develop the pr oduct homomorphism method, which gives polynomial PAC learning algorithms f or a nonrecursive Horn clause with function-free ground background knowledg e, if the background knowledge satisfies some structural properties. The me thod is based on a characterization of the concept that corresponds to the relative least general generalization of a set of positive examples with re spect to the background knowledge. The characterization is formulated in te rms of products and homomorphisms. In the applications this characterizatio n is turned into an explicit combinatorial description, which is then trans lated into the language of nonrecursive Horn clauses, We show that a nonrec ursive Horn clause is polynomially PAC-learnable if there is a single binar y background predicate and the ground atoms in the background knowledge for m a forest. If the ground atoms in the background knowledge form a disjoint union of cycles then the situation is different, as the shortest consisten t hypothesis may have exponential size. In this case polynomial PAC-learnab ility holds if a different representation language is used. We also conside r the complexity of hypothesis finding for multiple clauses in some restric ted cases. (C) 2001 Elsevier Science B,V. All rights reserved.