ON THE LEARNABILITY OF BOOLEAN FORMULAE.

Michael Kearns, Ming Li, Leonard Pitt, Leslie Valiant

Research output: Contribution to journalConference article

Abstract

The autors study the computational feasibility of learning boolean expressions from examples. Their goals are to prove results and develop general techniques that shed light on the boundary between the classes of expressions that are learnable in polynomial time and those that are apparently not. They employ the distribution-free model of learning. Their results fall into three categories: closure properties of learnable classes, negative results, and distribution-specific positive results.

Original languageEnglish (US)
Pages (from-to)285-295
Number of pages11
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1987

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'ON THE LEARNABILITY OF BOOLEAN FORMULAE.'. Together they form a unique fingerprint.

  • Cite this