"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
Abstract:
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.
