GENERATING LOGICAL EXPRESSIONS FROM POSITIVE AND NEGATIVE EXAMPLES VIA A BRANCH-AND-BOUND APPROACH

Consider a logical system with N entities which assume binary values o f either TRUE (1) or FALSE (0). There are 2(N) vectors, each with N co mponents, of this type. Even when a modest value of N, e.g. N=50, the number of such vectors exceeds one quadrillion. We assume that an 'exp ert' exists which can ascertain whether a particular vector (observati on) such as (1, 1, 0, 0, 1, 0, ..., 1) is allowable or not. This exper t can be a human expert or an unknown system whose rules have to be in ferred. Further, we assume that a sampling of m observations has resul ted in M(1) instances which the expert has classified as allowable and M(2)=m-M(1) instances which are not allowable. We call these instance s positive and negative examples, respectively. The objective of this research is to infer a set of logical rules for the entire system base d upon the m, and possibly, additional sample observations. The propos ed algorithm in this paper is based on an highly efficient branch-and- bound formulation. This algorithm configures a sequence of logical cla uses in conjunctive normal form (CNF), that when are taken together, a ccept all the positive examples and reject all the negative examples. Some computational results indicate that the proposed approach can pro cess problems that involve hundreds of positive and negative examples in a few CPU seconds and with small memory requirements.