On the minimum number of logical clauses inferred from examples (Q1919787)

The paper is devoted to the problem of inductive inference (learning), where examples are classified as positive or negative. The issue is to determine a Boolean expression which classifies all the positive and negative examples correctly. The objective of the paper is to determine a lower bound on the number of clauses in the conjunctive normal form (CNF) or in the disjunctive normal form (DNF) which are needed to correctly classify a given set of examples. In addition, efficient approaches are derived which can effectively partition the input data into smaller groups before processing by a learning algorithm. In this way, large learning problems can be solved more efficiently. A sufficient and necessary condition of existence of a CNF clause which accepts all the given positive examples and rejects two given negative examples is stated (in Theorem 2). Theorem 2 motivates the construction of a graph, called the rejectability graph (R-graph). Nodes of the R-graph correspond to negative examples, an edge connects two negative examples if there is a clause which rejects both negative examples and accepts all positive examples. The R-graph provides the means for establishing a lower bound on the number of CNF (or DNF) clauses which can be inferred from positive and negative examples. A theorem states a lower bound (the minimum clique cover) on the minimum number of clauses required to reject all the negative examples in \(E^{-}\), while accepting all the positive examples in \(E^{+}\). The R-graph also provides an effective way for partitioning the original data and, thus, solve large scale learning problems. Furthermore, the rejectability graph suggests a time efficient approach for decomposing the original problem into a sequence of smaller problems and still infer a compact Boolean expression from the partial solutions of the smaller problems. Two learning algorithms are discussed. The first is a greedy approach based on a branch-and-bound algorithm (developed by Triantaphyllou). The second approach is based on formulating a satisfiability problem and then solving it by an interior point method. A report on computational experiments is given in the paper.