Learning Theory

Theorems that characterize classes of learning problems or

specific algorithms in terms of computational complexity
or sample complexity, i.e. the number of training examples
CS 391L: Machine Learning: necessary or sufficient to learn hypotheses of a given
Computational Learning Theory accuracy.
Complexity of a learning problem depends on:
Size or expressiveness of the hypothesis space.
Accuracy to which target concept must be approximated.
Probability with which the learner must produce a successful
hypothesis.
Raymond J. Mooney Manner in which training examples are presented, e.g. randomly or
by query to an oracle.
University of Texas at Austin
1 2

Types of Results Learning in the Limit

Learning in the limit: Is the learner guaranteed to Given a continuous stream of examples where the learner
converge to the correct hypothesis in the limit as the predicts whether each one is a member of the concept or
number of training examples increases indefinitely? not and is then is told the correct answer, does the learner
Sample Complexity: How many training examples are eventually converge to a correct concept and never make a
needed for a learner to construct (with high probability) a mistake again.
highly accurate concept? No limit on the number of examples required or
Computational Complexity: How much computational computational demands, but must eventually learn the
resources (time and space) are needed for a learner to concept exactly, although do not need to explicitly
construct (with high probability) a highly accurate recognize this convergence point.
concept? By simple enumeration, concepts from any known finite
High sample complexity implies high computational complexity, hypothesis space are learnable in the limit, although
since learner at least needs to read the input data. typically requires an exponential (or doubly exponential)
Mistake Bound: Learning incrementally, how many number of examples and time.
training examples will the learner misclassify before Class of total recursive (Turing computable) functions is
constructing a highly accurate concept. not learnable in the limit.

3 4

Learning in the Limit vs.

Unlearnable Problem
PAC Model
NN)
Identify the function underlying an ordered sequence of natural
numbers (t: , guessing the next number in the sequence and Learning in the limit model is too strong.
then being told the correct value. Requires learning correct exact concept
For any given learning algorithm L, there exists a function t(n) that it
cannot learn in the limit. Learning in the limit model is too weak
Given the learning algorithm L as a Turing machine:
Allows unlimited data and computational resources.
D L h(n)
PAC Model
Construct a function it cannot learn:
Only requires learning a Probably Approximately
<t(0),t(1),t(n-1)>

Example Trace
Oracle: 1 3 6 11
t(n)

..
{ L

h(n) + 1
Correct Concept: Learn a decent approximation most of
the time.
Requires polynomial sample complexity and
computational complexity.
Learner: 0 2 5 10
natural

odd int
pos int

h: h(n)=h(n-1)+n+1
5 6

1
 Cannot Learn Exact Concepts Cannot Learn Even Approximate Concepts
from Limited Data, Only Approximations from Pathological Training Sets
Positive
Positive

Learner Classifier Learner Classifier

Negative Negative

Negative
Positive Positive
Negative

7 8

PAC Learning Formal Definition of PAC-Learnable

Consider a concept class C defined over an instance space
The only reasonable expectation of a learner X containing instances of length n, and a learner, L, using a
is that with high probability it learns a close hypothesis space, H. C is said to be PAC-learnable by L
using H iff for all cC, distributions D over X, 0<<0.5,
approximation to the target concept. 0<<0.5; learner L by sampling random examples from
distribution D, will with probability at least 1 output a
In the PAC model, we specify two small hypothesis hH such that errorD(h) , in time polynomial
in 1/, 1/, n and size(c).
parameters, and , and require that with
Example:
probability at least (1 ) a system learn a X: instances described by n binary features
concept with error at most .

C: conjunctive descriptions over these features
H: conjunctive descriptions over these features
L: most-specific conjunctive generalization algorithm (Find-S)
size(c): the number of literals in c (i.e. length of the conjunction).

9 10

Issues of PAC Learnability Consistent Learners

The computational limitation also imposes a A learner L using a hypothesis H and training data
polynomial constraint on the training set size, D is said to be a consistent learner if it always
since a learner can process at most polynomial outputs a hypothesis with zero error on D
data in polynomial time. whenever H contains such a hypothesis.
How to prove PAC learnability:
First prove sample complexity of learning C using H is
By definition, a consistent learner must produce a
polynomial. hypothesis in the version space for H given D.
Second prove that the learner can train on a Therefore, to bound the number of examples
polynomial-sized data set in polynomial time. needed by a consistent learner, we just need to
To be PAC-learnable, there must be a hypothesis bound the number of examples needed to ensure
in H with arbitrarily small error for every concept that the version-space contains no hypotheses with
in C, generally CH. unacceptably high error.

11 12

2
 -Exhausted Version Space Proof
The version space, VSH,D, is said to be -exhausted iff every Let Hbad={h1,hk} be the subset of H with error > . The VS
hypothesis in it has true error less than or equal to . is not -exhausted if any of these are consistent with all m
In other words, there are enough training examples to examples.
guarantee than any consistent hypothesis has error at most . A single hi Hbad is consistent with one example with
One can never be sure that the version-space is -exhausted, probability:
but one can bound the probability that it is not. P (consist (hi , e j )) (1 )
Theorem 7.1 (Haussler, 1988): If the hypothesis space H is
finite, and D is a sequence of m1 independent random A single hi Hbad is consistent with all m independent random
examples for some target concept c, then for any 0 1, examples with probability:
the probability that the version space VSH,D is not - P (consist (hi , D )) (1 ) m
exhausted is less than or equal to:
The probability that any hi Hbad is consistent with all m
|H|em examples is:
P (consist ( H bad , D )) = P (consist (h1 , D) consist ( hk , D)) L
13 14

Proof (cont.) Sample Complexity Analysis

Since the probability of a disjunction of events is at most Let be an upper bound on the probability of not
the sum of the probabilities of the individual events: exhausting the version space. So:
P (consist ( H bad , D )) H bad (1 ) m P(consist ( H bad , D )) H e m

e m
H
Since: |Hbad| |H| and (1)m em, 0 1, m 0

m ln(
P (consist ( H bad , D)) H e m
)
H

/
Q.E.D m ln
(flip inequality)
H
H
m ln /


1
m ln + ln H /
15 16

Sample Complexity Result Sample Complexity of Conjunction Learning

Therefore, any consistent learner, given at least: Consider conjunctions over n boolean features. There are 3n of these
since each feature can appear positively, appear negatively, or not
1 appear in a given conjunction. Therefore |H|= 3n, so a sufficient
ln + ln H /

number of examples to learn a PAC concept is:

1 n 1
examples will produce a result that is PAC. ln + ln 3 / = ln + n ln 3 /

Just need to determine the size of a hypothesis space to
Concrete examples:
instantiate this result for learning specific classes of
==0.05, n=10 gives 280 examples
concepts. =0.01, =0.05, n=10 gives 312 examples
This gives a sufficient number of examples for PAC ==0.01, n=10 gives 1,560 examples
learning, but not a necessary number. Several ==0.01, n=50 gives 5,954 examples
approximations like that used to bound the probability of a Result holds for any consistent learner, including FindS.
disjunction make this a gross over-estimate in practice.

17 18

3
 Sample Complexity of Learning
Other Concept Classes
Arbitrary Boolean Functions

L
Consider any boolean function over n boolean features such as the k-term DNF: Disjunctions of at most k unbounded
hypothesis space of DNF or decision trees. There are 22^n of these, so a conjunctive terms: T1 T2 Tk
sufficient number of examples to learn a PAC concept is: ln(|H|)=O(kn)

L L L
1 1 k-DNF: Disjunctions of any number of terms each limited to
+ ln 22 / = ln + 2 n ln 2 /
n
ln
at most k literals: (( L1 L2 Lk ) ( M 1 M 2 M k )
ln(|H|)=O(nk )
Concrete examples:
L
k-clause CNF: Conjunctions of at most k unbounded
==0.05, n=10 gives 14,256 examples disjunctive clauses: C1 C2 Ck
==0.05, n=20 gives 14,536,410 examples ln(|H|)=O(kn)
==0.05, n=50 gives 1.561x1016 examples

L L L
k-CNF: Conjunctions of any number of clauses each limited
to at most k literals: ((L1 L2 Lk ) (M 1 M 2 M k )
ln(|H|)=O(nk )

Therefore, all of these classes have polynomial sample

19
complexity given a fixed value of k. 20

Basic Combinatorics Counting Computational Complexity of Learning

dups allowed dups not allowed However, determining whether or not there exists a k-term DNF or k-
clause CNF formula consistent with a given training set is NP-hard.
order relevant samples permutations
Therefore, these classes are not PAC-learnable due to computational
order irrelevant selections combinations complexity.
samples permutations selections combinations There are polynomial time algorithms for learning k-CNF and k-DNF.
Construct all possible disjunctive clauses (conjunctive terms) of at
Pick 2 from aa ab aa ab
most k literals (there are O(nk ) of these), add each as a new constructed
{a,b} ab ba ab
feature, and then use FIND-S (FIND-G) to find a purely conjunctive
ba bb
(disjunctive) concept in terms of these complex features.
bb

n + k 1
Expanded
(n + k 1)! Data for Construct all k-CNF
k - samples : n k k - selections : = disj. features data with O(nk) Find-S
k
k-CNF formula
k!(n 1)! concept with k literals new features
n!
k - permutatio ns : n n!
(n k )! k - combinatio ns : =
k k!( n k )! Sample complexity of learning k-DNF and k-CNF are O(nk)
Training on O(nk) examples with O(nk) features takes O(n2k) time
All O(nk) 21 22

Enlarging the Hypothesis Space to Make

Probabilistic Algorithms
Training Computation Tractable
However, the language k-CNF is a superset of the language k-term- Since PAC learnability only requires an
DNF since any k-term-DNF formula can be rewritten as a k-CNF approximate answer with high probability, a
formula by distributing AND over OR. probabilistic algorithm that only halts and returns
Therefore, C = k-term DNF can be learned using H = k-CNF as the a consistent hypothesis in polynomial time with a
hypothesis space, but it is intractable to learn the concept in the form high-probability is sufficient.
of a k-term DNF formula (also the k-CNF algorithm might learn a
close approximation in k-CNF that is not actually expressible in k-term However, it is generally assumed that NP
DNF). complete problems cannot be solved even with
Can gain an exponential decrease in computational complexity with only a high probability by a probabilistic polynomial-
polynomial increase in sample complexity. time algorithm, i.e. RP NP.
Data for k-CNF Therefore, given this assumption, classes like k-
k-CNF
k-term DNF Approximation
concept
Learner term DNF and k-clause CNF are not PAC
learnable in that form.
Dual result holds for learning k-clause CNF using k-DNF as the
hypothesis space.
23 24

4
 Infinite Hypothesis Spaces Shattering Instances
The preceding analysis was restricted to finite hypothesis A hypothesis space is said to shatter a set of instances iff
spaces. for every partition of the instances into positive and
Some infinite hypothesis spaces (such as those including negative, there is a hypothesis that produces that partition.
real-valued thresholds or parameters) are more expressive For example, consider 2 instances described using a single
than others. real-valued feature being shattered by intervals.
Compare a rule allowing one threshold on a continuous feature x y +
(length<3cm) vs one allowing two thresholds (1cm<length<3cm).
_ x,y
Need some measure of the expressiveness of infinite x y
hypothesis spaces. y x
The Vapnik-Chervonenkis (VC) dimension provides just x,y
such a measure, denoted VC(H).
Analagous to ln|H|, there are bounds for sample
complexity using VC(H).

25 26

Shattering Instances (cont) VC Dimension

But 3 instances cannot be shattered by a single interval. An unbiased hypothesis space shatters the entire instance space.
x y z + The larger the subset of X that can be shattered, the more
_ x,y,z expressive the hypothesis space is, i.e. the less biased.
x y,z The Vapnik-Chervonenkis dimension, VC(H). of hypothesis
y x,z space H defined over instance space X is the size of the largest
x,y z finite subset of X shattered by H. If arbitrarily large finite
x,y,z subsets of X can be shattered then VC(H) =
y,z x
z x,y If there exists at least one subset of X of size d that can be
Cannot do x,z y shattered then VC(H) d. If no subset of size d can be
shattered, then VC(H) < d.
Since there are 2m partitions of m instances, in order for H For a single intervals on the real line, all sets of 2 instances can
to shatter instances: |H| 2m. be shattered, but no set of 3 instances can, so VC(H) = 2.
Since |H| 2m, to shatter m instances, VC(H) log2 |H|
27 28

VC Dimension Example VC Dimension Example (cont)

Consider axis-parallel rectangles in the real-plane, i.e. No five instances can be shattered since there can be at
conjunctions of intervals on two real-valued features. most 4 distinct extreme points (min and max on each of the
Some 4 instances can be shattered.
2 dimensions) and these 4 cannot be included without
including any possible 5th point.

Some 4 instances cannot be shattered: Therefore VC(H) = 4

Generalizes to axis-parallel hyper-rectangles (conjunctions
of intervals in n dimensions): VC(H)=2n.

29 30

5
 Conjunctive Learning
Upper Bound on Sample Complexity with VC
with Continuous Features
Using VC dimension as a measure of expressiveness, the Consider learning axis-parallel hyper-rectangles,
following number of examples have been shown to be conjunctions on intervals on n continuous features.
sufficient for PAC Learning (Blumer et al., 1989). 1.2 length 10.5 2.4 weight 5.7
1 2 13 Since VC(H)=2n sample complexity is
4 log 2 + 8VC ( H ) log 2

1 2 13
4 log 2 + 16n log 2

Compared to the previous result using ln|H|, this bound has Since the most-specific conjunctive algorithm can easily
some extra constants and an extra log2(1/) factor. Since find the tightest interval along each dimension that covers
VC(H) log2 |H|, this can provide a tighter upper bound on all of the positive instances (fmin f fmax) and runs in
the number of examples needed for PAC learning. linear time, O(|D|n), axis-parallel hyper-rectangles are
PAC learnable.

31 32

Sample Complexity Lower Bound with VC Analyzing a Preference Bias

There is also a general lower bound on the minimum number of Unclear how to apply previous results to an algorithm with a
examples necessary for PAC learning (Ehrenfeucht, et al., preference bias such as simplest decisions tree or simplest DNF.
1989): If the size of the correct concept is n, and the algorithm is
Consider any concept class C such that VC(H)2 any learner L guaranteed to return the minimum sized hypothesis consistent
and any 0<<1/8, 0<<1/100. Then there exists a distribution D with the training data, then the algorithm will always return a
and target concept in C such that if L observes fewer than: hypothesis of size at most n, and the effective hypothesis space
1 1 VC (C ) 1
is all hypotheses of size at most n.
max log 2 , All hypotheses
32 c Hypotheses of
examples, then with probability at least , L outputs a size at most n
hypothesis having error greater than .
Ignoring constant factors, this lower bound is the same as the Calculate |H| or VC(H) of hypotheses of size at most n to
upper bound except for the extra log2(1/ ) factor in the upper determine sample complexity.
bound.
33 34

Computational Complexity and Occams Razor Result

Preference Bias (Blumer et al., 1987)
However, finding a minimum size hypothesis for most Assume that a concept can be represented using at most n
languages is computationally intractable. bits in some representation language.
If one has an approximation algorithm that can bound the size Given a training set, assume the learner returns the
of the constructed hypothesis to some polynomial function, f(n), consistent hypothesis representable with the least number
of the minimum size n, then can use this to define the effective of bits in this language.
hypothesis space. Therefore the effective hypothesis space is all concepts
All hypotheses
representable with at most n bits.
c Hypotheses of
size at most n Since n bits can code for at most 2n hypotheses, |H|=2n, so
Hypotheses of size sample complexity if bounded by:
1 1
at most f(n). ln + ln 2n / = ln + n ln 2 /

However, no worst case approximation bounds are known for
practical learning algorithms (e.g. ID3). This result can be extended to approximation algorithms
that can bound the size of the constructed hypothesis to at
most nk for some fixed constant k (just replace n with nk)
35 36

6
 Interpretation of Occams Razor Result COLT Conclusions
Since the encoding is unconstrained it fails to The PAC framework provides a theoretical framework for
analyzing the effectiveness of learning algorithms.
provide any meaningful definition of simplicity.
The sample complexity for any consistent learner using
Hypothesis space could be any sufficiently small some hypothesis space, H, can be determined from a
space, such as the 2n most complex boolean measure of its expressiveness |H| or VC(H), quantifying
bias and relating it to generalization.
functions, where the complexity of a function is
If sample complexity is tractable, then the computational
the size of its smallest DNF representation complexity of finding a consistent hypothesis in H governs
Assumes that the correct concept (or a close its PAC learnability.
approximation) is actually in the hypothesis space, Constant factors are more important in sample complexity
than in computational complexity, since our ability to
so assumes a priori that the concept is simple. gather data is generally not growing exponentially.
Does not provide a theoretical justification of Experimental results suggest that theoretical sample
Occams Razor as it is normally interpreted. complexity bounds over-estimate the number of training
instances needed in practice since they are worst-case
upper bounds.
37 38

COLT Conclusions (cont)

Additional results produced for analyzing:
Learning with queries
Learning with noisy data
Average case sample complexity given assumptions about the data
distribution.
Learning finite automata
Learning neural networks
Analyzing practical algorithms that use a preference bias is
difficult.
Some effective practical algorithms motivated by
theoretical results:
Boosting
Support Vector Machines (SVM)

39