An Empirical Comparison of Cost Functions in Inductive Logic Programming
This work addresses a key question in inductive logic programming for researchers and practitioners, but it is incremental as it compares existing cost functions without introducing new ones.
The paper tackled the problem of selecting appropriate cost functions in inductive logic programming by empirically comparing the generalisation error of optimal hypotheses learned under seven standard cost functions, finding that minimising training error or description length performed best overall across over 20 domains and 1000 tasks.
Recent inductive logic programming (ILP) approaches learn optimal hypotheses. An optimal hypothesis minimises a given cost function on the training data. There are many cost functions, such as minimising training error, textual complexity, or the description length of hypotheses. However, selecting an appropriate cost function remains a key question. To address this gap, we extend a constraint-based ILP system to learn optimal hypotheses for seven standard cost functions. We then empirically compare the generalisation error of optimal hypotheses induced under these standard cost functions. Our results on over 20 domains and 1000 tasks, including game playing, program synthesis, and image reasoning, show that, while no cost function consistently outperforms the others, minimising training error or description length has the best overall performance. Notably, our results indicate that minimising the size of hypotheses does not always reduce generalisation error.