Learning Discriminant Rules as a Minimal Saturation Search

摘要

It is well known that for certain relational learning problems, traditional top-down search falls into blind search. Recent works in Inductive Logic Programming about phase transition and crossing plateau show that no general solution can face to all these difficulties. In this context, we introduce the notion of "minimal saturation" to build non-blind refinements of hypotheses in a bidirectional approach. We present experimental results of this approach on some benchmarks inspired by constraint satisfaction problems. These problems can be specified in first order logic but most existing ILP systems fail to learn a correct definition, especially because they fall into blind search.