On the minimum number of logical clauses inferred from examples
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.
- scientific article; zbMATH DE number 1054681
- A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions
- A Relationship Between CNF and DNF Systems Derivable from Examples
- Learning conjunctions of Horn clauses
- Generating logical expressions from positive and negative examples via a branch-and-bound approach
- A branch and bound algorithm for the maximum clique problem
- A branch and bound algorithm for the maximum clique problem
- A continuous approach to inductive inference
- A fast algorithm for the maximum weight clique problem
- A Relationship Between CNF and DNF Systems Derivable from Examples
- A theory of the learnable
- An exact algorithm for the maximum clique problem
- An interior point algorithm to solve computationally difficult set covering problems
- Computational experience with an interior point algorithm on the satisfiability problem
- Computational limitations on learning from examples
- Finding maximum cliques in arbitrary and in special graphs
- Generating logical expressions from positive and negative examples via a branch-and-bound approach
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3637904 (Why is no real title available?)
- scientific article; zbMATH DE number 956841 (Why is no real title available?)
- Inference of a minimum size Boolean function from examples by using a new efficient branch-and-bound approach
- Logic-based decision support. Mixed integer model formulation
- Modeling and integer programming techniques applied to propositional calculus
- Some results and experiments in programming techniques for propositional logic
- The maximum clique problem
- Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
- Generating logical expressions from positive and negative examples via a branch-and-bound approach
- scientific article; zbMATH DE number 1054681 (Why is no real title available?)
- A Relationship Between CNF and DNF Systems Derivable from Examples
- Logic classification and feature selection for biomedical data
- A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions
This page was built for publication: On the minimum number of logical clauses inferred from examples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1919787)
