A Guided Tour Through Hypothesis Spaces in ILP

Abstract

In spite of the desirable properties of using Horn logic as hypothesis language, the expressivness leads to huge hypothesis spaces containing up to millions of hypotheses for even simple learning problems. Controlling hypothesis spaces by biases requires knowledge on the effects and applicability of biases in different domains. This knowledge can be gained experimentally by comparing the size of hypothesis spaces with respect to the language bias and the application domain. This approach contrasts theoretical comparisons of the complexity where the results are very general and small bias variations mostly cannot be considered. In order to yield more detailed information on small bias variations and to compare the results independently of systems, their implementations and additional more or less hidden biases, we use MILES-CTL for the experiments. As application domains, we selected a function-free domain including family relations and a non-function-free domain including list-processing programs.