Top-Down Induction of Horn Clauses

Name	Top-Down Induction of Horn Clauses
Description	In Inductive Logic Programming a common method for finding a horn clause that covers as much instances of a set of positive examples as possible, but does not cover any instance of a set of negative examples is to use a general-to-specific search through a given hypothesis language. General-to-specific search for horn clauses: Given a set of examples, a specific target predicate P and its arity, e.g. 2. Start with a most general horn clause with predicate P in the head. These are the horn clauses with empty bodies and different variables at each component of P, e.g. " P(x, y) ← ". These clauses are most general, because they derive P(x, y) for every possible substitution of x and y. In general there will be negative examples in the example set, which then will be covered by all most general clauses. In this case, the actual horn clause is refined step by step, until no negative example is covered any more. This is done by adding further conditions to the clause's body. Doing so decreases the set of substitutions fulfilling all conditions of the horn clause, so the clause becomes more specific. Depending on the refinement procedure two approaches can be distinguished: The refinement procedure can be guided heuristically, as done by FOIL (not restricted to horn clauses) to construct a clause that covers as many of the yet uncovered positive, but none of the negative examples. Another way is to perform a complete search through a syntactically restricted hypothesis space, which will generally require higher computational efforts. On the other hand, it enables to give guarantees, e.g. that a most general solution in the hypothesis space is found. An algorithm following this approach is RDT.
Dm Step	Concept Learning
Method Type	Method