On the learnability of Boolean formulae

Published 1 January 1987Open access

Michael Kearns, M. Li, Leonard Pitt, Leslie G. Valiant

Citations293

TL;DR

The 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, and to employ the distribution-free model of learning.

Abstract

Article Free Access Share on On the learnability of Boolean formulae Authors: M. Kearns Harvard University Harvard UniversityView Profile , M. Li Harvard University Harvard UniversityView Profile , L. Pitt University of Illinois University of IllinoisView Profile , L. Valiant Harvard University Harvard UniversityView Profile Authors Info & Claims STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingJanuary 1987 Pages 285–295https://doi.org/10.1145/28395.28426Online:01 January 1987Publication History 157citation769DownloadsMetricsTotal Citations157Total Downloads769Last 12 Months62Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Keywords

Computer Science

A theory of the learnable

4,242 Citations1984Leslie G. Valiant

This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.

Information and ComputationLearning regular sets from queries and counterexamples

2,115 Citations1987Dana Angluin

A learning algorithm L* is described that correctly learns any regular set from any minimally adequate Teacher in time polynomial in the number of states of the minimum dfa for the set and the maximum length of any counterexample provided by the Teacher.

Journal of Computer and System SciencesFast probabilistic algorithms for hamiltonian circuits and matchings

586 Citations1979Dana Angluin, Leslie G. Valiant

Journal of the ACMComputational limitations on learning from examples

532 Citations1988Leonard Pitt, Leslie G. Valiant

It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP, and relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.

View PDF

Machine LearningLearning decision lists

355 Citations1987Ronald L. Rivest

This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples, and strictly increases the set of functions known to be polynomially learnable, in the sense of Valiant (1984).

Journal of the ACMThe Complexity of Near-Optimal Graph Coloring

326 Citations1976M. R. Garey, David S. Johnson

It is proved that even coming close to khgr;(G) with a fast algorithm is hard, and it is shown that if for some constant r < 2 and constant d there exists a polynomial-time algorithm A which guarantees A(G).

View PDF

Elsevier eBooksGRAPH COLORING ALGORITHMS††This research was supported in part by the Advanced Research Projects Agency of the Department of Defense under contract SD-302 and by the National Science Foundation under contract GJ-446.

226 Citations1972David W. Matula, George Marble +1 more

This chapter describes the concept of sequential colorings is formalized and certain upper bounds on the minimum number of colors needed to color a graph, the chromatic number x(G), and shows that the recursive-smallest-vertex-degree-last-ordering-with-interchange coloring algorithm will color any planar graph in five or fewer colors.

Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

170 Citations1986Anselm Blumer, Andrzej Ehrenfeucht +2 more

It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.

National Conference on Artificial IntelligenceQuantifying the inductive bias in concept learning (extended abstract)

21 Citations1986David Haussler

It is shown that the notion of bias in inductive concept learning can be quantified in a way that directly relates to learning performance, and that this quantitative theory of bias can provide guidance in the design of effective learning algorithms.

A new approximate graph coloring algorithm

20 Citations1982Avi Wigderson

A simple and efficient coloring algorithm which guarantees-&-Agrave; (G)-&-le;x(G)n (equation), a considerable improve over the current bounds is presented.

View PDF