Efficient Learning of Horn Formulas over Finite Totally Ordered Domains

Abstract

One of the core activities in learning is the synthesis of concepts and their relationships by generalizing from positive and negative samples. Information hidden in data becomes explicit, relations emerge that provide insights and serve as explanations. Nowadays, machine learning is able to process large quantities of data and to build models that classify new data with such a success that the algorithms are termed ‘intelligent’. With most approaches, though, the models are black boxes: It is usually difficult to explain why a model classifies data in a particular way.

Our work is an approach to machine learning that provides explanations. We present algorithms that construct if-then rules (Horn clauses) from samples and counter-samples. We generalize results for binary data to finite totally-ordered domains by relying on literals of the form x ≥ d and x ≤ d, with x and d being domain variables and constants, respectively. This way we avoid the need to binarize data over such domains, which usually entails an increase in variables and output that is hard to interpret. We present both an offline and an online algorithm. In the first case, the positive and negative samples are known from the outset, while in the second case the samples arrive one by one and lead to incremental changes to the formula.

Both algorithms are linear in the number of positive and negative samples as well as in the number of variables, while the size of the resulting formula does not depend on the number of positive samples. Besides analyzing the asymptotic complexity, we use a C++ implementation to evaluate the algorithms on some datasets. We conclude with a discussion of various extensions.