Learning Disjunction of Conjunctions

Abstract

The question of wheth e r concepts expressible as disjun ctio ns of conjunctions can be learn e d from examples in polynomial time is investigated . Positive results are shown for significant subclasses that allow not only propositional predicates but also some relations . The algorithms are extend e d so as to be provably tolerant to a certain quantifiable error rate in the examples data . It is further shown that under certain restrictions on these subclasses th e l ear ning algorithms ar e well suited to implementation on neural networks of threshold elements. The possible importance of disjunctions of conjunctions as a knowledge repr ese ntation stems from th e observations that on the one hand humans appear t o like using it , and , on the other, that there is circumstantial evidence that significantly larger classes may not be learnable in polynomial time . An NP-completeness result corroborating the latter is also presented.