An ILP Method Based on Instance Graph

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Student Abstracts

Learning systems that express theories in first-order logic must ensure that the theories are executable and, in particular, they do not lead to infinite recursion. We introduce instance graph H(R,E), which is a type of directed hypergraph, and instance order to clarify the relationship between a (recursive) ruleset R and the instance space E of the corresponding target predicate. Based on these concepts, we put forward a new ILP algorithm, FOILBIG, which guarantees executability of learned rulesets, and does not substantially raise computational complexity compared to FOIL. FOILBIG has no restriction of ordering, and hence makes it possible to complete more learning tasks in ILP context. The method based on instance graph could also be used by any learning system that grows elements from ground facts by repeated specialization. FOILBIG has been implemented roughly and preliminary experiments show that it can solve problems beyond the scope of FOIL. In addition, unlike the method used by FOIL, our method can be extended to Multiple Predicate Learning with the extension of instance graph.