Machine Learning and Natural Language Processing Lab

Master Thesis

Machine Learning in the Phase Transition Framework

Ulrich Rückert, 2002

---

We investigate k-term DNF learning, the task of inducing a propositional DNF formula with at most k terms from a set of positive and negative examples. Though k-term DNF learning is NP-complete, it is at the core of most propositional learning algorithms. The main aim of this thesis is to evaluate stochastic local search algorithms to solve hard k-term DNF learning tasks. As a reference we first design and evaluate a range of systematic search algorithms for the problem. Using those algorithms we can separate soluble from insoluble problem instances and then analyze the problem's average search complexity using the Phase Transition framework. We examine the region of hard problem instances, the so called phase transition, and show that location and extent of this region can be predicted by an equation derived from statistical mechanics. We then evaluate existing stochastic local search algorithms on the hard problem instances from the phase transition region. Our experiments indicate that WalkSAT is able to solve the largest fraction of hard problem instances. Finally, we design and evaluate a range of stochastic local search algorithms searching through the two possible search spaces for k-term DNF learning. A speed-optimized version of a WalkSAT-like search in formula space is able to find solutions to the king-rook-king chess endgame benchmark, which are more compact than the solutions found by a propositional version of the rule learning algorithm FOIL. Supervisors: Prof. Dr. François Bry (Ludwig-Maximilians-Universität München) Prof. Dr. Luc De Raedt (Albert-Ludwigs-Universität Freiburg) Dr. Stefan Kramer (Albert-Ludwigs-Universität Freiburg)