机器学习

In computer science, computational learning theory (or just learning theory) is a subfield of
artificial intelligence devoted to studying the design and analysis of machine learning algorithms. In
computational learning theory, probably approximately correct learning (PAC learning) is a framework
for mathematical analysis of machine learning algorithms. It was proposed in 1984 by Leslie Valiant.
In this framework, the learner (that is, the algorithm) receives samples and must select a
hypothesis from a certain class of hypotheses. The goal is that, with high probability (the “probably”
part), the selected hypothesis will have low generalization error (the “approximately correct” part). In
this section we first give an informal definition of PAC-learnability. After introducing a few nore notions,
we give a more formal, mathematically oriented, definition of PAC-learnability. At the end, we mention
one of the applications of PAC-learnability.
PAC-learnability
To define PAC-learnability we require some specific terminology and related notations.


Let X be a set called the instance space which may be finite or infinite. For example, X may be
the set of all points in a plane.
A concept class C for X is a family of functions c : X  {0; 1}. A member of C is called a concept.
A concept can also be thought of as a subset of X. If C is a subset of X, it defines a unique
function μc : X  {0; 1} as follows:



A hypothesis h is also a function h : X  {0; 1}. So, as in the case of concepts, a hypothesis can
also be thought of as a subset of X. H will denote a set of hypotheses.
We assume that F is an arbitrary, but fixed, probability distribution over X.
Training examples are obtained by taking random samples from X. We assume that the samples
are randomly generated from X according to the probability distribution F.
Now, we give below an informal definition of PAC-learnability.
Definition (informal)
Let X be an instance space, C a concept class for X, h a hypothesis in C and F an arbitrary, but fixed,
probability distribution. The concept class C is said to be PAC-learnable if there is an algorithm A which,
for samples drawn with any probability distribution F and any concept c Є C, will with high probability
produce a hypothesis h Є C whose error is small.
Examples
To illustrate the definition of PAC-learnability, let us consider some concrete examples .
Example
Figure : An axis-aligned rectangle in the Euclidean plane
21



Let the instance space be the set X of all points in the Euclidean plane. Each point is represented
by its coordinates (x; y). So, the dimension or length of the instances is 2.
Let the concept class C be the set of all “axis-aligned rectangles” in the plane; that is, the set of
all rectangles whose sides are parallel to the coordinate axes in the plane (see Figure).
Since an axis-aligned rectangle can be defined by a set of inequalities of the following form
having four parameters

a ≤ x ≤ b, c ≤ y ≤ d
the size of a concept is 4.
We take the set H of all hypotheses to be equal to the set C of concepts, H = C.
Given a set of sample points labeled positive or negative, let L be the algorithm which outputs the
hypothesis defined by the axis-aligned rectangle which gives the tightest fit to the positive examples
(that is, that rectangle with the smallest area that includes all of the positive examples and none of the
negative examples) (see Figure bleow).
Figure : Axis-aligned rectangle which gives the tightest fit to the positive examples
It can be shown that, in the notations introduced above, the concept class C is PAC-learnable by the
algorithm L using the hypothesis space H of all axis-aligned rectangles.