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