Learning logic programs with structured background knowledge (Extended Abstract)

this paper we also use these assumptions. We study the effect of structural assumptions about the background knowledge on learnability. For example, we look at the case when the background knowledge contains facts about a single binary background predicate and the facts given form a forest. ( Another way to put this kind of additional information is that we assume some background knowledge about the background knowledge. ) It can be expected that this kind of restriction can be exploited to give efficient learning algorithms. We note that these restrictions are related to the notion of determinateness that is often used to obtain positive results ( Cohen [2], Dzeroski, Muggleton and Russell [4] ). In particular, having a background knowledge consisting of paths or cycles implies determinateness. On the other hand, in the case of forests the clauses are not necessarily determinate. Another important difference is that we do not assume any bound on depth of the clauses considered. In the case of paths we also obtain a positive result ( for arbitrary distributions ) for learning multiple clause hypotheses. The learning algorithms make use of the fact that least general generalizations can be represented as products. This relationship is already mentioned by Plotkin [15] , [16] and it is used in related contexts for example in Cohen and Hirsch [3] and Frazier and Pitt [5] . It is also discussed further in Tsapara [18]. Using products in the present context is helpful as it makes it possible to apply a combinatorial approach to LGG's. Besides providing efficient algorithms, it also contributes to the understanding of how the LGG operator works, for example by providing interesting examples when the LGG given by Plotkin's algorithm is large but it can be reduced and other ..