A Theory of the Learnable

Inside the paper

The problem

A theory of learning needs to specify what information a learner receives, how accurate its answer must be and how much computation is allowed. Without such a model, claims that a class of concepts can be learned are hard to compare.

The idea

Define a learning protocol and ask which classes of concepts can be learned efficiently with controlled error and confidence. Analyze concrete classes of Boolean expressions within that framework.

How it works

• Represent an object by a vector of Boolean attributes and a concept by a predicate that labels such vectors.
• Give the learner access to examples drawn from a fixed distribution and, in the protocol, an oracle that can answer suitable questions about a concept.
• Require an efficient procedure to output a hypothesis whose error is small with high probability, across the allowed concepts and distributions.
• For bounded clause-size expressions, eliminate candidate clauses inconsistent with positive examples to form a hypothesis.

What it showed

The paper gives learning procedures and guarantees for bounded CNF expressions and certain DNF classes under the stated protocols. It also discusses computational obstacles for more general Boolean expressions.

Read it for

Start with Sections 2 and 3 for the protocol and learnability definition, then Section 5 for a concrete algorithm. Section 4 supplies a probabilistic bound used in the analysis and can be revisited after the example.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.