Induction of 2-clause Recursive Logic Programs Using Minimal Multiple Generalization and Forced Simulation

概要

論文の詳細を見る
The aim of Inductive Logic Programming (ILP) is to investigate methods of induction of logic programs given a set of examples and background knowledge. In this paper we present a method to induce 2-clause recursive logic programs using minimal multiple generalization (2-mmg) and forced simulation. Initially, the examples covered by the base and recursive clauses are separated by the 2-mmg algorithm. In the next step, the recursive program is induced using the information contained in the background knowledge and the method of forced simulation. Logic programs are an alternative approach to represent many computational problems. In this frame-work a problem is expressed in a logic language and search for solutions is executed using a sound and complete logic inference method (for example, the resolution rule). Such solutions are called positive in-stances of the problem. We say that the logic program P, which represents the problem, logically implies the positive examples (denoted as P ⊨ E^+). A correct logic program cannot derive negative instances, and we denote this condition as P ⋀ E^- 〓 □. Basically, ILP systems need to invert the logical implication, i. e. try to find a logic program which entails the positive examples and is consistent with negative examples. To illustrate this problem, let's consider the problem of appending two lists. In Prolog language texbooks we can find the following program to solve the problem : append([], List, List). append([Head|Tail1], List2, [Head|Tail3]) : -append(Tail1, List2, Tail3). This program is an example of recursive logic program. Some possible positive instances (in ILP framework they are also called positive examples, E^+) are : append([], [], []). append([2], [1], [2, 1]). append([1], [], [1]). append([], [1], [1]). append([1, 2], [3, 4], [1, 2, 3, 4]). Negative examples of append would be : append([], [1], []). append([1], [2], [2, 1]). append([1, 2], [3], [1, 2, 3, 4]). Using these positive and negative examples, an ILP system would induce the above Prolog program. To induce a logic program from examples we can take the positive examples and generalize them (bottom-up method) or choose a logic program from a valid set and verify if it entails the positive examples (top-down method). Both approaches present, the problem of combinatorial explosion of alternatives to choose during search for solution, making induction a hard problem to solve. For this reason, current ILP systems make use of syntatic biases plus some additional "hints" to make the problem tractable.
一般社団法人情報処理学会の論文
1995-03-15

Induction of 2-clause Recursive Logic Programs Using Minimal Multiple Generalization and Forced Simulation

スポンサーリンク

概要

著者

関連論文

スポンサーリンク