On the learnability of Boolean formulae

By Michael Kearns, Ming Li, Leonard Pitt, Leslie G. Valiant. 1987

We study the computational feasibility of learning boolean expressions from examples. Our 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. The elucidation of this boundary, for boolean expressions and possibly other knowledge representations, is an example of the potential contribution of complexity theory to artificial intelligence. We employ the distribution-free model of learning introduced in /lo]. A more complete discussion and justification of this model can be found in [4,10,11,12]. [4] includes some discussion that is relevant more particularly to infinite representations, such as geometric ones, rather than the finite case of boolean functions. For other recent related work see [1,2,7,&g]. The results of this paper fall into three categories: closure properties of learnable classes, negative results, and distribution-specific positive results. The closure properties are of two kinds. In section 3 we discuss closure under boolean operations on the members of the learnable classes. The assumption that the classes are learnable from positive or negative ex-

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Interpretable Two-level Boolean Rule Learning for Classification (2015, background): “Third, learnability of Boolean formulae is considered in [7] from the perspective of probably approximately correct (PAC) learning.”
Learning decision lists (2004, methodology): “However, it is NP-hard in general to compute the shortest decision list consistent with a given sample S; this result can be derived fl'om the results of Masek (1976) or Kearns et al.”
Learning sparse two-level boolean rules (2016, methodology): “As we overview in Section 2, existing methods are mostly heuristic and/or greedy and there has been limited work on principled yet tractable approaches.”
Learning Decision Lists (1987, result): “However, it is NP-hard in general to compute the shortest decision list consistent with a given sample S; this result can be derived from the results of Masek (1976) or Kearns et al. (1987).”
Efficient noise-tolerant learning from statistical queries (1993, unknown): “, xn (we assume that f is a monotone conjunction without loss of generality [Kearns et al. 1987].”
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution (1994, background): “While a number of algorithms have been developed for learning various subclasses of DNF in a variety of models [46, 34, 7, 3, 30, 4, 2, 11, 38, 18], many of the results for unrestricted DNF have been negative.”
Learnability and the Vapnik-Chervonenkis dimension (1989, methodology): “These notions of polynomial learnability, both closely related to the model introduced in [59] and elaborated in [ 36 ] and [52], are discussed in Sections 3.1 and 3.2, respectively.”
I Computational Complexity (2005, result): “The next result is proven in [9] for the PAC-learning model (in fact, all the results in the table in [9] are also true for the equivalence query model).”
Teachability in computational learning (1990, background): “For example, [1,0] = 0, [3, 0] = 000, and [3,5] = 101.”
On-line Algorithms in Machine Learning (1996, methodology): “The Mistake Bound model is equivalent to the \extended equivalence query" model of Angluin [1], and is known to be strictly harder for polynomialtime algorithms than the PAC learning model of Valiant [34, 22] in which (among other di erences) the adversary is required to select examples from a xed d”
Learning DNF Expressions from Fourier Spectrum (2012, background): “The original problem asks whether polynomial-size DNF expressions are learnable from random examples on points sampled from an unknown distribution.”