Learning disjunction of conjunctions

摘要: The question of whether concepts expressible as disjunctions conjunctions can be learned from examples in polynomial time is investigated. Positive results are shown for significant subclasses that allow not only propositional predicates but also some relations. algorithms extended so to provably tolerant a certain quantifiable error rate the data. It further under restrictions on these learning well suited implementation neural networks threshold elements. possible importance knowledge representation stems observations one hand humans appear like using it andon other, there circumstantial evidence significantly larger classes may learnable time. An NP-completeness result corroborating latter presented.