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.
||SPECialization by TRansformation and Elimination
|References:||Boström and Idestam-Almquist 1994|
New features of SPECTRE 3.0 include:
- The search strategy is optional (Divide-and-Conquer (DAC),
Separate-and-Conquer (SAC) or Reconsider-and-Conquer (RAC)
- Pruning techniques have been included (pre-pruning for DAC,
incremen tal reduced error pruning for SAC and RAC, and post-pruning
by clause removal)
- Automatic discretisation of continuous values
- the user can specify a set of methods to be tested by setting
parameters regarding search strategy, pre- and post-pruning methods
- the user can specify any number of experiments to be run,
including variations in background predicates as well as the fraction
of the examples to use for training and testing
- results from the experiments can be output both in the form of
comparative statistics as well as the actual hypothesis produced
(together with statistics on the performance on training and test
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
- Bostrom H. and Asker L., "Combining Divide-and-Conquer and
Separate-and-Conquer for Efficient and Effective Rule Induction",
Proceedings of the Ninth International Workshop on Inductive
Logic Programming, LNAI Series 1634, Springer (1999).
back to index