| Description |
The algorithm RDT basically performs a complete search through a
subspace of the hypothesis language of clauses. The subspace results
from syntactical restrictions chosen by the user.
The complete search for consistent clauses does not only
- guarantee finding a single clause within the search space,
if such a clause exists (task of concept learning).
- But it also can be used for finding all clauses in the
(restricted) hypothesis language, which makes RDT well suited
for the characterization task of inductive logic programming.
To perform a complete search, pruning is restricted to cases, where
- a general clause does not cover a positive example, so any more
specific clause cannot be consistent with the example set, or
- a specific clause covers a negative example, so each more general
example will do as well.
The search strategy of RDT is top-down induction of horn clauses
with rule schemes directing the search. A rule scheme is a clause
with at least one predicate variable. Predicate variables are mapped
to predicate symbols by substitutions Σ, similar to usual variable
substitution, but with the additional restriction that mappings have
to be injective, so different predicate variables cannot be replaced by
the same predicate symbol.
For rule schemes we can define the "more general than" relation as
follows:
Let RS and RS´ be rule schemes. Then RS is more general than
RS´ if and only if there are substitutions Σ and σ so that
RSΣσ ⊆ RS´.
The search starts with the shortest and therefore most general rule
schemes / clauses that only have to be refined by adding literals, if
a clause covers positive and negative examples. Redundant literals
cannot be added by this strategy.
|
