May 19
Filip Zelezny
Post-Doc, University of Wisconsin - Madison, Department of Biostatistics and Medical Informatics

Randomized Search Strategies for Efficient ILP

Abstract: The volume of the clause subsumption lattice that
needs to be explored when constructing a first-order theory explaining a
set of examples is typically very large in non-trivial real-life tasks.
This is one of the most important reasons why Inductive Logic Programming
(ILP, a family of methods aiming at completing the above goal) has often been
referred to as inefficient.
Inspired by randomized strategies designed to significantly improve search
efficiency w.r.t exhaustive methods in the problems of propositional
satisfiability, we adapted and tested several randomized search methods
in the ILP system Aleph; namely the techniques of stochastic clause selection,
GSAT, WalkSAT, and randomized rapid restarts.
The presentation will cover the principles of the adaptation and results
on several non-trivial learning problems, focusing on the predictive
accuracy achieved by each method and time consumed thereby. Comparison
will be made to the standard exhaustive breadth-first search strategy as
implemented in Aleph.

Keywords: Machine Learning, Inductive Logic Programming, Efficiency,
Randomized Search