SPECTRE

System:	SPECTRE
Version:	1.0
Further specification:	SPECialization by TRansformation and Elimination
Pointers:	http://www.dsv.su.se/ML/
Code:	SICStus Prolog
References:	Boström and Idestam-Almquist 1994

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.

New developments

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

Experimental design:

• 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 examples)

References

1. 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.
2. 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