Incorporating a folding rule into inductive logic programming

1 Introduction

At first glance, it might seem that inductive logic programming (ILP) and logic program transformation (LPT) have opposite objectives. While ILP is interested in generalizing from examples, LPT is careful to preserve correctness. Nevertheless, there are ILP operators, like the intra-construction operator of CIGOL, that do not generalize, and instead reorganize the program so far inferred. This suggests looking at logic program transformation rules to obtain better nongeneralizing operators for ILP.

One LPT rule, called "folding," [Pettorossi and Proietti, 1998] is reminiscent of intra-construction, with some important differences. For example whereas intra-construction produces the definition of a new predicate (i.e. "concept"), folding receives as input such a definition, so that there is a separate, dedicated rule for creating a definition. The reason there is such a separate rule in LPT is that the derivation of efficiently executable programs is closely related to being able to fold using an already-existing definition.

Researchers have developed several reorganizing operators for ILP. Such operators can be found, for instance in the systems devised by Muggleton, Banerji, Ling, and Rouveirol and Puget. We have selected Muggleton's intra-construction as a representative of these operators for performing a comparison with folding. The main ideas of our comparison, however, should carry over to other similar operators.

Throughout, a0 and ✁ denote atoms, and ✂ ✄ and ✂ ☎ denote tuples of atoms (we will assume definite logic programs). Also, msg ✆ ✝ ✟ ✡ ✝ ✌ ✍ denotes the most specific generalization of expressions ✝ ✟ and ✝ ✌ , and " ✑ " denotes equality up to variable renaming.

When used to fold two clauses, the folding rule infers ✆ F✍ from ✆ D ✟ ✍ , ✆ E ✟ ✍ , ✆ D ✌ ✍ , and ✆ E ✌ ✍ :

where ✁ ✣ ✁ ✟ ✙ ✟ ✣ ✁ ✌ ✙ ✌ . In addition, there are some syntactic restrictions for soundness, for which we refer the reader to [Pettorossi and Proietti, 1998]. An application of folding replaces ✆ E✟ ✍ and ✆ E✌ ✍ by ✆ F✍ .

Observe that this rule has the limitation of requiring both clauses to be folded ✆ E ✟ ✍ and ✆ E ✌ ✍ , to have the same head a0 and the same part of the body ✂ ☎ which is not an instance of the bodies of the definition ✆ D ✟ ✍ and ✆ D ✌ ✍ .

On the other hand, folding has the advantage of allowing the clauses ✆ D ✟ ✍ and ✆ D ✌ ✍ to be drawn from a previous program [Pettorossi et al., 1996].

To be able to perform a comparison with intraconstruction, we will assume that intra-construction consists of two parts: first the "invention" of a predicate, and then the clause-reorganization proper. The second part would then be:

where

An application of the second part of intra-construction also replaces ✆ E✟ ✍ and ✆ E✌ ✍ by ✆ F✍ . Compared with folding, not only must the definition clauses be unit clauses, but their argument places must be terms that undo the generalization when resolving ✆ F ✍ with ✆ D ✟ ✍ and ✆ D ✌ ✍ . If we are introducing a new definition, such constraints might not be relevant. If, however, we wish to recognize an already-inferred concept or we are interested in increasing the efficiency of execution of our inferred program, it might be important to be able to relax such limitations.

2 A common extension of folding and intra-construction

As an illustration showing the need for increasing the efficiency of an inferred program, consider the string-matching problem. This problem consists in finding all occurrences (or only one occurrence, if any) of a string called the pattern within another string called the text. Suppose that our pattern is the string a0 a0 ✂ . If we give the following two examples, both of which are a text having an occurrence of this pattern:

we can apply absorption, deriving:

A third example:

allows us to apply absorption again, inferring:

Clauses (1), (2), and (3) can be regarded as representing a finite-state automaton accepting the language ✆ a0 ✌ ✂ ✍ ✎ a0 a0 ✂ . However, these clauses are a nondeterministic program, requiring a quadratic time in the worst case to find an occurrence of the pattern. Note that this program cannot be converted to a deterministic version with intra-construction. A reason is that we would need to be able to apply intraconstruction without inventing a new predicate at every application. (Such already-existing predicates represent edges going backwards in the corresponding automaton.) Allowing the use of already-existing definitions is accompanied by a possible violation of the conditions for intra-construction (i.e. the ✁ ✷ 's may not have the required form).

This limitation suggests using the ordinary folding [Pettorossi and Proietti, 1998] rule as part of the operator repertoire of an ILP system. In fact, [Pettorossi et al., 1996] show how to determinize a program similar to the one we just inferred with absorption (given as specification by the user), where the folding rule plays a central role.

The ordinary folding rule [Pettorossi and Proietti, 1998], however, is not adequate for inductive logic programming: We observed that this rule requires the set of atoms that do not match the bodies of the definition (i.e. a0 and ✂ ☎ ) be the same in each clause to be folded (i.e. ✆ E ✟ ✍ and ✆ E ✌ ✍ ).

Now we give another illustration. Suppose an inductiveinference system has inferred the following description of an arch, where the example arch ✆ ✆ ☎ ✞ ✡ beam ✡ ☎ ✞ ✍ ✍ is not given until later:

column✆ ☎ ✞ ✍ ✓

If we now add the example:

both folding and intra-construction are unable to derive the desired concept from (4) and (5):

Being able to derive the concise version of arch (6) might be important if we have already the same concept under a different name:

We have recently extended the ordinary folding rule so as to overcome these limitations of folding [Rosenblueth, 2005]. Our extension can be viewed as a common generalization of ordinary folding and intra-construction:

where

Here, ✙ ✷ only acts on the variables occurring in ✂ ✄ ✷ , and ✕ ✷ only acts on the variables occurring in ✁ ✷ and not occurring in ✂ ✄ ✷ (i.e. the head-only variables in ✆ D ✷ ✍ ). In addition, we preserve the syntactic conditions on ✙ ✷ developed for ordinary (multiple-clause) folding [Pettorossi and Proietti, 1998].

The main point of our folding rule is the computation of the substitutions ✕ ✷ in such a way that soundness is preserved. We distinguish two kinds of head-only variable instantiation: (a) coverage, taking a function symbol or variable from the substitutions ✗ ✷ , where ✆ a0 ✷ ✡ ✂ ☎ ✷ ✍ ✣ msg ✆ ✆ a0 ✟ ✡ ✂ ☎ ✟ ✍ ✡ ✆ a0 ✌ ✡ ✂ ☎ ✌ ✍ ✍ ✗ ✷ ( ✙ ✣ ✚ ✡ ✜ ), and (b) matching, taking the function symbol from the corresponding position in the clause of the other single-clause folding.

The contributions of this poster over [Rosenblueth, 2005] are (1) the comparison of folding with intra-construction and (2) the development of inductively inferred example programs. We are currently investigating the possibility of embedding our folding rule in CIGOL.