Learning rules from examples in rule-based systems via mathematical programming
Evangelos Triantaphyllou, Allen L. Soyster, Soundar Rajan Tirupatikumara · 1990
Consider a logical system with N entities which assume binary values of either TRUE (1) or FALSE (0). There are 2$\sp{\rm N}$ vectors, each with N components, of this type. Even with a modest value of N, e.g. N = 50, the number of such vectors exceeds one quadrillion. We assume that an expert exists which ascertain whether a particular vector (observation) such as (1,1,0,0,1,0,$\...$,1) actually or not. Further, we assume that a sampling of m observations has resulted in h instances which the expert has classified as can occur and m-h instances which cannot occur. We call these positive and negative examples, respectively. The objective of this research is to infer a set of logical rules for the entire system based upon the m, and possibly, additional sample observations. In this research a highly efficient branch-and-bound approach is developed that determines short (in length) logical expressions in conjunctive normal form (CNF) or disjunctive normal form (DNF). These logical expressions have the characteristic of accepting all the positive examples, while rejecting all the negative examples. Some theoretical results on the minimum number of clauses in the previous CNF or DNF expressions are also provided. Furthermore, another problem that is examined is how to generate the next example that best refines a logical expression that was determined by positive and negative examples. Finally, the issue of deciding whether two logical expressions are equivalent or not is also examined by solving a small number of satisfiability problems.