SPECTRE (SPECialization by TRansformation and Elimination)
is an empirical ILP system that can
handle large example sets very efficiently.
It was used successfully in the construction of DeNOx, a
system for controlling emissions of nitrogen oxides from a combined
heating and power plant in Stockholm, Sweden.
Given sets of positive and negative examples and an overly general
initial theory, that is, a theory which covers all positive and some of the
negative examples, SPECTRE specialises an overly general initial
theory in order to find a hypothesis which entails all positive examples
but no negative examples.
SPECTRE employs a divide-and-conquer technique to specialize an
overly general hypothesis.
Specialisation of the theory is performed by combining clause
removal with the transformation rule unfolding. Briefly, the algorithm
works as follows. When SPECTRE finds
a clause that covers a negative example and no positive examples, it
removes the clause. When it finds a clause that covers both negative and
positive examples, it unfolds the clause. For unfolding a clause, a literal
of the clause is selected and the clause is resolved with all
clauses in the theory with heads unifying with the selected
literal. Then, the clause is replaced by the resulting resolvents. The
choice of which literal to unfold upon is made such that the entropy of
the resolvents is minimized.
The resulting hypothesis consists of those clauses that cover
positive examples only.
SPECTRE uses the overly general theory as a declarative bias that
not only restricts what predicate symbols may occur in bodies of learned
clauses, but also how these can be invoked. Specialised clauses defining
the target predicate can only contain literals which occur in the initial
target predicate definition or in clauses resolving with the initial or
intermediate target predicate definitions. Therefore, the initial theory
is crucial for the success of the induction.
SPECTRE assumes that the
target predicate is non-recursive, i.e., the target predicate is not allowed
to appear in bodies of clauses. Background predicates, however, may be
recursive. SPECTRE provides a graphical interface. No system
parameters need to be set.
References
H. Boström and P. Idestam-Almquist.
Specialization of logic programs by pruning SLD-trees.
In S. Wrobel, editor, Proceedings of the 4th International
Workshop on Inductive Logic Programming, volume 237 of GMD-Studien,
pages 31-48. Gesellschaft für Mathematik und Datenverarbeitung
MBH, 1994.