[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM 1984 pp1134-1142.

@Article{valiant1984,
  author = 	 "L. G. Valiant",
  title = 	 "A theory of the Learnable",
  journal = 	 "Communications of the ACM",
  year = 	 "1984",
  pages = 	 "1134-1142"
}

Author of the summary: Samuel R. Collins, 1999, scollins@cc.gatech.edu

Cite this paper for:

• Learning
• Inductive learning from previously classified training examples
• Computational models for learning

Summary:

• This paper is concerned with the precise computational models of the learning phenomenon. It is restricted to skills that consist of recognizing whether a concept (or predicate) is true or not for given data. A concept has been learned if a program for recognizing it has been deduced.
• A learning machine consists:
• Learning protocol - specifies the manner in which the information is obtained from the outside world
• Deductive procedure - the mechanism by which a correct recognition algorithm for the concept to be learned is deduced

• The learning protocols considered in this paper allow two kinds of information supply.

1. EXAMPLES - Produces positive examples that exemplify the concept to be learned
2. ORACLE - When presented with data, it well the learner whether or not the data positively exemplify the concept

• Concepts are represented as Boolean functions of a set of propositional variables.
• The deduction procedure, in each case, outputs an expression that closely approximates the expression to be learned.

A Learning Protocol for Boolean Functions:

• Consider t Boolean variables p₁… p_t each can take the value true or false.
• A vector is an assignment to each of the variables of a value from {0, 1, *}

The * denotes undetermined

• A Boolean function F becomes a concept F if its domain is extended to the set of all vectors as follows: For a vector v, F(v) = 1 if and only if F(w) = 1 for all the vectors w that agree with v on all variables for which v is determined.
• The learning protocol:

1. EXAMPLES: This has no inputs. It gives as output a vector v such that F(v)=1. For each such v, the probability that v is output on any single cell is D(v).
2. ORACLE( ): On vector v, as input it outputs 1 or 0 according to whether F(v) = 1 or 0.

• In a real system an Oracle may be a human expert, a database of past observations, some deduction system, or a combination of these.

Learnability:

A class X of a program is learnable with respect to a given learning protocol if and only if there exists an algorithm A (the deduction procedure) invoking the protocol with the following properties.

The algorithm runs in time polynomial in an adjustable parameter h, in the various paramaters that quantify the size of the program to be learned, and in the number of variables t.
For all vectors v, g(v) = 1 implies that f(v) = 1, and the sum of D(v) over all v such that f(v) = 1, but g(v) != 1 is at most h^-1

Conclusions:

• The positive conclusion of this paper is that there are specific classes of concepts that are learnable in polynomial time using learning protocols of the kind described above.

1. Conjunctive normal form expressions with a bounded number of literals in each clause
2. Monotone disjunctive normal form from expressions
3. Arbitrary expressions in which each variable occurs just once

Summary author's notes:

• none

Cognitive Science Summaries Webmaster:

Last modified: Thu Apr 15 11:07:19 EDT 1999