Confirmation-guided discovery of first-order rules with Tertius

This paper deals with learning first-order logic rules from data lacking an explicit classification predicate. Consequently, the learned rules are not restricted to predicate definitions as in supervised inductive logic progr amming. First-order logic offers the ability to deal with structured, multi -relational knowledge. Possible applications include first-order knowledge discovery, induction of integrity constraints in databases, multiple predic ate learning, and learning mixed theories of predicate definitions and inte grity constraints. One of the contributions of our work is a heuristic meas ure of confirmation, trading off novelty and satisfaction of the rule. The approach has been implemented in the Tertius system. The system performs an optimal best-first search, finding the k most confirmed hypotheses, and in cludes a non-redundant refinement operator to avoid duplicates in the searc h. Tertius can be adapted to many different domains by tuning its parameter s, and it can deal either with individual-based representations by upgradin g propositional representations to first-order, or with general logical rul es. We describe a number of experiments demonstrating the feasibility and f lexibility of our approach.