"Generating Logical Expressions from Positive and Negative Examples Via a Branch-and-Bound Approach"

Computers and Operations Research, 1994, Vol. 21, No. 2, pp. 185-197.

by E. Triantaphyllou, A.L. Soyster, and S.R.T. Kumara

Consider a logical system with N entities which assume binary values of either TRUE (1) or FALSE (0). There are 2N 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 can ascertain whether a particular vector (observation) such as (1,1,0,0,1,0,...,1) is allowable or not. This "expert" can be a human expert or an unknown system whose rules have to be inferred. Further, we assume that a sampling of m observations has resulted in M1 instances which the "expert" has classified as allowable and M2 = m - M1 instances which are not allowable. We call these instances 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.

The proposed algorithm in this paper is based on a highly efficient branch and bound formulation. This algorithm configures a sequence of logical clauses in conjunctive normal form (CNF), that when are taken together, accept all the positive examples and reject all the negative examples. Some computational results indicate that the proposed approach can process problems that involve hundreds of positive and negative examples in a few CPU seconds and with small memory requirements.

Key Words:
Learning from examples, conjunctive normal form (CNF), satisfiability problem, branch-and-bound search.

Download this paper as a PS (PostScript) file (size = 1,825 KB).

Download this paper as a PDF file (size = 1,410 KB).

Return to Dr. Triantaphyllou's Homepage.