Language Series Revisited: The Complexity of Hypothesis Spaces in ILP

Irene Weber, B. Tausend, Irene Stahl

Extended abstract published in
Machine Learning: ECML-95, 8th European Conference on Machine Learning, Heraclion, Crete, Greece. Springer, 1995.

Abstract

Restrictions on the number and depth of existential variables as defined in the language series of CLINT [1] are widely used in ILP and expected to produce a considerable reduction in the size of the hypothesis space. In this paper we show that this is generally not the case. The lower bounds we present lead to intractable hypothesis spaces except for toy domains. We argue that the parameters chosen in CLINT are unsuitable for sensible bias shift operations, and propose alternative approaches resulting in the desired reduction of the hypothesis space and allowing for a natural integration of the shift of bias.

  1. De Raedt, Luc. Interactive Theory Revision. Academic Press, London, 1992.
I. Weber / weberi@informatik.uni-stuttgart.de