ON THE LEARNABILITY OF BOOLEAN FORMULAE.

Michael Kearns; Ming Li; Leonard Pitt; Leslie Valiant

doi:10.1145/28395.28426

ON THE LEARNABILITY OF BOOLEAN FORMULAE.

Michael Kearns, Ming Li, Leonard Pitt, Leslie Valiant

Research output: Contribution to journal › Conference article › peer-review

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 language	English (US)
Pages (from-to)	285-295
Number of pages	11
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/28395.28426
State	Published - 1987
Externally published	Yes

ASJC Scopus subject areas

Software

Online availability

10.1145/28395.28426

Library availability

Discover UIUC Full Text

Cite this

@article{8b1c3a41ff644546842c689585cf4f36,

title = "ON THE LEARNABILITY OF BOOLEAN FORMULAE.",

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.",

author = "Michael Kearns and Ming Li and Leonard Pitt and Leslie Valiant",

year = "1987",

doi = "10.1145/28395.28426",

language = "English (US)",

pages = "285--295",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery",

}

TY - JOUR

T1 - ON THE LEARNABILITY OF BOOLEAN FORMULAE.

AU - Kearns, Michael

AU - Li, Ming

AU - Pitt, Leonard

AU - Valiant, Leslie

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023545078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023545078&partnerID=8YFLogxK

U2 - 10.1145/28395.28426

DO - 10.1145/28395.28426

M3 - Conference article

AN - SCOPUS:0023545078

SN - 0734-9025

SP - 285

EP - 295

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

ER -

ON THE LEARNABILITY OF BOOLEAN FORMULAE.

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this