The learning challenge
Goal
There is some underlying function that captures
an input-output relationship which we would like to estimate
Assumption
We do not know , but we get to observe example input-
output pairs which are generated independently at random
– we draw according to some unknown distribution and get
to observe the pair
– we draw according to some unknown distribution and get
to observe the pair , where represents
“noise” with an unknown distribution
– we draw pairs according to some unknown joint
distribution
A first model of learning
Let’s restrict our attention to binary classification
– our labels belong to (or )
We observe the data
where each
Suppose we are given a list of possible hypotheses
From the training data , we would like to select the best
possible hypothesis from
Example
Empirical risk
Recall from last time our definition of risk and its empirical
counterpart
Risk:
Empirical risk:
In our definition of we make use of the indicator
function
The empirical risk gives us an estimate of the true
risk , and from the law of large numbers we know that
as
Empirical risk minimization (ERM)
We want to choose a hypothesis from that achieves a
small risk
Since is supposed to be a good estimate of ,
an incredibly natural (and common) strategy is to pick
Aside:
The risk in ERM
As we discussed last time, as long as we have enough data,
for any particular hypothesis , we expect
However, if is very large, then we can also expect that
there are some for which
Thus, what can we say about ?
• We know that is as small as it can be
– this could be because is small
– or, it could be because for some
• Which explanation is more likely?
– it depends… just how large is ?
Confidence bounds
We would like to be able to give quantitative answers to
questions along the lines of:
If we are deciding between hypotheses, how much data do
we need (how large does need to be) to ensure that
for some that we define in advance
Asymptotic results like the law of large numbers and the
central limit theorem do not give us answers to these
questions
Instead, we need nonasymptotic results about
Too much randomness?
Our goal is ultimately to show how to make
by setting appropriately
What is random here?
– the training data
– , because each depends on
– , because it depends on
In order to tease all of this apart, let’s begin by going back to
just a single hypothesis and studying
Bounding the error
We want to calculate
Note that is a random variable
– we have
where the are Bernoulli random variables
– thus, is a Binomial random variable
– since , we have that
Deviation from the mean
Thus, an equivalent way to think about our problem is that
we would like to calculate
and this is just asking about the probability that a Binomial
random variable will deviate from it’s mean by more than
If represents the cumulative distribution function (CDF)
of our binomial random variable, then we can write
Bounding the deviation
Unfortunately, the CDF we are interested in is given by
This has no nice closed form expression, and is rather
unwieldy to work with and doesn’t give us much intuition
Instead of calculating the probability exactly, it is enough to
get a good bound of the form
or equivalently
Concentration inequalities
An inequality of the form
tell us how a particular random variable (in this case )
concentrates around its mean
There are a number of different concentration inequalities
that give us various bounds along these lines
We will start with a very simple one, and then build up to a
stronger result
Markov’s inequality
The simplest of these results is Markov’s inequality
Let be any nonnegative random variable.
Then for any ,
This is cool on its own, but can be leveraged
to say even more since for any strictly nonotonically
increasing (nonnegative-valued) function
Chebyshev’s inequality
As an example, Chebyshev’s inequality
states that for any random variable ,
Proof.
Note that is a nonnegative
random variable. Thus we can apply
Markov’s inequality to obtain
Proof of Markov (Part 1)
There is a simple proof of Markov if you know the (super
useful!) fact that for any nonnegative random variable
Proof.
Note that we can write
Thus
Proof of Markov (Part 2)
We can visualize this result as
Thus, we can immediate see that we must have
and hence
Hoeffding’s inequality
Chebyshev’s inequality gives us the kind of result we are
after, but it is too loose to be of practical use
Hoeffding’s inequality assumes a bit more about our random
variable beyond having finite variance, but gets us a much
tighter and more useful result:
Let be independent bounded random variables,
i.e., random variables such that for all
Let . Then for any , we have
Chernoff’s bounding method
To prove this result, we will use a similar approach as in
Chebyshev’s inequality
To begin consider only the upper tail inequality:
(Markov)
(Independence)
Hoeffding’s Lemma
It is not obvious, but it is also not too hard to show, that
The proof uses convexity and then gets a bound using a
Taylor series expansion
Plugging this in, we obtain that for any , we have
By setting , we have
Putting it all together
Thus we have proven that
An analogous argument proves
Combined, these give
Special case: Binomials
If the are Bernoulli random variables, then is a
Binomial random variable and Hoeffding’s inequality becomes
Finally going back to our original problem, this means that
Hoeffding yields the bound
Multiple hypotheses
Thus, after much effort, we have that for a particular
hypothesis ,
However, we are ultimately interested in , not just a single
hypothesis
One way to argue that is to ensure
that simultaneously for all
Equivalently, we can try to bound the probability that any
hypothesis has an empirical risk that deviates from its
mean by more than
Formal statement
We can express this mathematically as
We can bound this using something called the union bound
Union bound
Union bound For any sequence of events
The events in our case are given by
Final result
Interpretation
We went through all of this work to show that
linearly exponentially
increasing decreasing
When can we be confident that ?
Note that
As long as isn’t too big ( ) then we can be
reasonably confident that
Are we learning yet?
It’s not quite enough to have
Ideally, we would like to have
Note that if , then implies
that
The learning problem
1. Can we ensure that is close to ?
2. Can we make small enough?