Probably approximately correct learning

Computational learning theory

In theoretical computer science, computational learning theory is a mathematical field related to the analysis of machine learning algorithms.-Overview:Theoretical results in machine learning mainly deal with a type of...

, probably approximately correct learning (PAC learning) is a framework for mathematical analysis of machine learning

Machine learning

Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...

. It was proposed in 1984 by Leslie Valiant

Leslie Valiant

Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...

.

In this framework, the learner receives samples and must select a generalization function (called the hypothesis) from a certain class of possible functions. The goal is that, with high probability (the "probably" part), the selected function will have low generalization error

Generalization error

The generalization error of a machine learning model is a function that measures how far the student machine is from the teacher machine in average over the entire set of possible data that can be generated by the teacher after each iteration of the learning process...

(the "approximately correct" part). The learner must be able to learn the concept given any arbitrary approximation ratio, probability of success, or distribution of the samples

Empirical distribution

Empirical distribution may refer to:* Empirical distribution function* Empirical measure...

.

The model was later extended to treat noise (misclassified samples).

An important innovation of the PAC framework is the introduction of computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

concepts to machine learning. In particular, the learner is expected to find efficient functions (time and space requirements bounded to a polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

of the example size), and the learner itself must implement an efficient procedure (requiring an example count bounded to a polynomial of the concept size, modified by the approximation and likelihood

Likelihood

Likelihood is a measure of how likely an event is, and can be expressed in terms of, for example, probability or odds in favor.-Likelihood function:...

bounds).

Definitions and terminology

In order to give the definition for something that is PAC-learnable, we first have to introduce some terminology.

For the following definitions, two examples will be used. The first is the problem of character recognition given an array of

bits. The other example is the problem of finding an interval that will correctly classify points within the interval as positive and the points outside of the range as negative.

Let

be a set called the instance space or the encoding of all the samples, and each instance have length assigned. In the character recognition problem, the instance space is

. In the interval problem the instance space is

, where

denotes the set of all real numbers.

A concept is a subset

. One concept is the set of all of the bits that encode for the letter "P" in

. An example concept from the second example is the set of all of the numbers between

and

. A concept class
Concept class
A concept over a domain X is a total Boolean function over X. A concept class is a class of concepts. Concept class is a subject of computational learning theory....

is a set of concepts over

. This could be the set of all of the array of bits that are skeletonized 4-connected (width of the font is 1).

Let

be a procedure that draws an example,

, using a probability distribution

and gives the correct label

, that is 1 if

and 0 otherwise.

Say that there is an algorithm

that given access to

and inputs

and

that, with probability of at least

outputs a hypothesis

that has error less than or equal to

with examples drawn from

with the distribution

. If there is such an algorithm for
every concept

, for every distribution

over

, and for all

and

then

is PAC learnable(or distribution-free PAC learnable). We can also say that

is a PAC learning algorithm for

.

An algorithm runs in time

if it draws at most

examples and requires at most

time steps. A concept class is efficiently PAC learnable if it is PAC learnable by an algorithm that runs in time polynomial in

and instance length.

Equivalence

Under some regularity conditions these three conditions are equivalent:

The concept class C is PAC learnable.
The VC dimension
VC dimension
In statistical learning theory, or sometimes computational learning theory, the VC dimension is a measure of the capacity of a statistical classification algorithm, defined as the cardinality of the largest set of points that the algorithm can shatter...

of C is finite.
C is a uniform Glivenko-Cantelli class.

Definitions and terminology

Equivalence

Further reading