"On the Minimum Number of Logical Clauses Inferred from Examples"

Computers and Operations Research, 1996, Vol. 23, No. 8, pp. 783-799.

Evangelos Triantaphyllou and Allen L. Soyster

Scope and Purpose:
One of the critical challenges in learning a set of rules (logical clauses) is to derive a very small number of rules, which still satisfy the pertinent requirements. These requirements are derived from positive (successes) and negative examples (failures). The present paper uses some graph theoretic approaches in establishing ways for partitioning large learning problems and also determining bounds on the minimum number of rules derivable from given sets of positive and negative examples.

Given two sets of positive and negative examples, the inductive inference problem is to infer a small set of logical clauses which appropriately classify the examples. A graph theoretic approach is used to establish a lower limit on the minimum number of required clauses. Furthermore, the findings of this paper reveal methods for partitioning the original data and thus solving efficiently large scale problems.

Download this paper as a PS (PostScript) file (size = 2,585 KB).

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

Return to Dr. Triantaphyllou's Homepage.