let me try supposed to step back a
little bit and first describe what
exactly we've been doing in the last
lectures so remember we were studying
the problem of statistical learning
where we're assuming that the data that
we observe come from some distribution
in a iie manner and we're going to be
tested with respect to some loss
function on the same distribution right
then with respect to a random draw from
the same distribution so let's say 1/2
is algorithm that we proposed that's
loops of the data and outputs a function
right so that's a function that we
learned with data and what we do is we
look at the expected loss where the
capital L already has the expectation
over a and then we take expectation with
respect to the 1/2 with respect to the
data and then what we would like to do
of course is to try to guarantee that
this is small where if star is the base
the best possible function the process
that's our dream
and we would like to show that this is
goes down with M right as you get more
and more data you get closer and closer
in terms of prediction
okay so in the first lecture we saw that
this goal in general is not possible you
cannot do anything about it no matter
how you really say anything so let's say
this is the space of all distribution
distributions and you cannot say that
you're all written such as deep neural
network will work for any distribution
okay on the other hand as soon as we
start making restrictions to the space
of probabilities then you start getting
more and more interesting results
however unlike the possible statistics
or a Bayesian approach where you will
try to model the distribution of the
data here we're modeling something about
the solutions typically such as a margin
now if you take kind of a very small set
of distributions the easy problems so
these are the easy problems so let's say
this is all all distributions these are
somehow easy and I'm going to put them
in quotes because I'm never gonna define
it because I don't know if you're in an
easy case if you make an assumption
about a set of distributions and that's
an easy assumption and by the way this
is not like that a single fixed set I'm
just saying that you make an assumption
that's restrictive enough that will make
it possible for you to
to prove something right then you could
get this going down with em and we saw
an example of that with a hyperplane
deliver the perceptron under the margin
assumption we've got a nice easy
consequence of as a consequence this was
lecture number two in my part we've got
a 1 over N rate times 1 over M Squared
under the assumption that data in the
population are linearly separable by a
margin gap right and this was a strong
assumption so somehow that restricted
the set of probability distributions to
be a nice easy I'm being hand waving
here now if you make an assumption about
your population that's not as easy that
doesn't make the problem so easy then
you get into this bias variance
trade-off in other words if this is your
set of distributions then you can't
attack this directly so what they mean
by that is somehow if you try to attack
this directly then you're working with a
set of functions which are effective
solutions under these it's just too
large so you cannot control the
fluctuations or the size of that
expected maximum over that class so in
fact a good way to think about the
bias-variance tradeoff is it is needed
when you don't have such string
stringent assumptions and the assumption
is weak enough that you are you really
cannot attack the problem all at once
they have to split it into two parts and
one way to split it is expected l of F
hat n minus L of F Plus this is a kind
of appliance variance decomposition but
the only stochastic part is this part
right well it's this one so the bias
variance is the composition is needed if
the class where F star lives is somehow
too difficult to large does that make
sense say if the problem is easy you
don't actually need the by experiencing
you just do let's say perceptron right
that was an easy problem there is no
bias-variance tradeoff in that problem
if you do least squares in a finite
dimensional case so d dimension of the
problem is less than and the number of
data points then unless you're trying to
get a very precise result about some
other properties if you're just looking
at the Z over N type of result for the
sample complexity of these squares then
it's an easy problem so you don't need
the bias-variance decomposition so again
the bias-variance decomposition comes
about because you cannot control the
stochastics that's why we split we split
it in such a way that hopefully you
couldn't you can control this bird and
somehow this is called approximation
error so understand this part and of
course you want to ideally you want to
balance these does that make sense
okay so we've been doing in the last
four lectures is analyzing this term on
me now what happens to this term
well you can say let's just hope it's
small you don't wanna if you don't want
to dig into approximation here in how
one class of functions approximates
another class of functions then you
don't you just leave it and then you say
I'm just gonna deal with this term then
the result you get is only as good as
that class right so you you do as well
as the best you could have done with
that class of functions and now we
looked at the particular method for
constructing F hat n and let's just take
the minimum minimum loss over the class
so if if it's erm then we have an upper
bound of n minus expected empirical
three terms the composition if you
remember and two of the three terms then
were negative so we drop them so we can
we get to this at this point we said you
know it's it's biased we know that this
is a this is a biased estimator of that
and so we don't really know what to do
and now the analysis diverges you could
consider the worst case over F so just
say so the first one is uniform
deviations
if we're going to replace this with a
further upper bond of expected max over
F&F of L of f - that's one approach
second approach is going to be based on
stability and compression so we're going
to perhaps we're gonna do compression
today compression approach compression
set stability privacy so these are all
the different ways you could try to
attack this term to limit the bias of
this of this estimator of things okay
so again I would like to stress the fact
that if capital F becomes larger we have
less and less ability to control these
deviations and so at some point we
cannot do it anymore
so in some sense you have to choose the
bias and variance carefully so that you
can control that expected maximum in
this approach and the uniform deviations
approach and to understand the uniform
deviations what we did is we just gather
a very simple upper bound again twice an
expectation so this is expectation over
the data this is twice expectation over
data off now expectation over Epsilon's
max over f of 1 over and some of epsilon
i may be a loss function and these are
called Rademacher averages
and the nice thing here is that you can
indeed you can indeed calculate this
quantity for many interesting classes
and therefore you get an understanding
of deviations okay any questions about
this general layout so other than yeah
yeah so you can study stability well
he's still for stability you still need
to a close relative your these squares
it effectively restricts this but it
doesn't do so ammeter which really
controls implicitly and I don't know who
cannot go again these squares you
decompose into bias variance in a
slightly different way not like that and
again one is a stochastic turn very much
but if you take nearest neighbors for
instance it doesn't it doesn't go
through deviations
we're gonna lecture on local rules such
as dangerous
well competing parson windows local
polynomial approximation questions okay
yeah I think one key kind of message
that I really want you to take with you
is with the end when you analyze a
learning problem you end up with a
stochastic term
just because you've you have empirical
data that what you want is something on
the population you want a prediction a
lot of sound right and in relating these
two you end up with a term that you may
or may not be able to bow and kind of
the larger is the class over which you
have to look at the empirical minus
expected one it is the the kind of the
more difficult it becomes at some point
you cannot control it right because
there are too many too many possible
explanations of your data right there
are too many explanations and so you
don't know which one to choose it's it's
okay so in understanding this kind of
easy versus maybe non easy problems one
can try to to summarize the difficulty
of this class F by some notions such as
the VC dimension and you've probably
you've heard probably that there is a
big conundrum that VC dimension of
neural networks is the number of it's
related to the number of units number of
neurons but typically you take a neural
network that is over current Rises has
many more neurons than data right and so
if you look at the EC type of approach
you say well it can't work because the
the complexity of the class F is too
large so you can you shouldn't be able
to control these but then there is often
another aspect of the problem such as
the margin that mitigates this
dependence of the number of neurons so
what I'm gonna do now today is a lot of
the classical margin a large margin
analysis that is applicable to neural
networks as well and as you will see the
number of neurons are the dimension will
not explicitly appear in those dirty
okay any questions okay so today large
analysis
for a classification
so one one result which I may be
mentioned in passing but I didn't to
much time on it but if you look at a
class GE so who does not know what the
VC dimension is okay okay it's some let
me not let's just say you've got a class
of functions that map Z to
let's say you ll say down F F of Z in
plus minus one then either VC dimension
of F is finite or VC dimension of F is
it okay so that's a like a litmus test
whether the class is simple enough or
it's not okay
so then then when you look at Rademacher
averages of G projected onto c1 through
Z then now this is a subset of patterns
of plus and minuses that you can realize
on these data okay remember the picture
is the class of functions now of course
they're binary now so they're only plus
minus one but if you put all the
possible on c1 this function is plus
minus ones and then as you put all these
patterns together then for a VC class
this would be upper bounded by something
like square root of the C of F
and for a non AC class so this is for a
for a finite VC and for non fine either
exists Z 1 through Zn such that this
complexity is is one so you cannot it
doesn't go to 0 right so somehow VC
dimension is easy is it first of all
it's a loose notion right why is it the
loose notion if it's small if it's
finite then it does control averages but
if it's not small there exists some data
points on which you cannot control the
Rademacher averages but who cares who
cares about the existence of these
points maybe they're rare doesn't
necessarily preclude you from it's not
the lower bound
ok so this is a three minute
introduction to Rankine theory
I'm not going to say anything more
except so what I would like to do is I
would like to
I remember Tommy wanted to some point to
get rid of VC theory all together but
typically when you're implementing a
classifier you don't just work with some
abstract class of functions which you
give you binary ballot outcomes it's
kind of unwieldy to have a a classifier
that just directly gives you plus minus
one so what do you typically do is you
have some class of functions which are
real valid X maps to a program in real
and then you gather and then in this
induces a class of classifiers given by
the Sun so let's go i M is the induced
class of X maps to sign
and this arguably this is the typical
situation typically you just have you're
working with some real valid class and
then just take a sign so for instance
with hyperplanes we took a real value
that's the product of W on the X and
then you just look at the sign is
positive on this side and and the whole
point now of today's lecture is to say
if you do this from this class of
functions then you're being perhaps
overly pessimistic you can do you can do
better and you can do better because of
this market analysis okay so what is the
margin well you can have a hard margin
which is there exists an F in your class
of functions such that for any index I
why I times f of X I is at least yeah
and so the picture for that is
is that you have F defines a classifier
at separating boundary and their pluses
here and there - is here and there's a
no-man's land
right
does that make sense
so you don't have any other several
examples and it's going to be a fixed
set of functions and we're going to be
choosing from this set of functions so
our algorithm will minimize something
over this class of functions
it may be empirical risk minimization so
just minimize some some loss
ideally in what I'm going to say you
would like to minimize the loss and
maximize margin
now this picture is a little bit
misleading because so if this is a
boundary the way that I drew is just a
geometric margin that the distance to
the decision boundary is at least at
least gap but the way that I wrote it is
it's just the in terms of the values
it's at least gamma which really now
depends on the Lipschitz properties of f
if f is very steep then you can move a
little bit in the X space and already
satisfy the margin right so translating
this to a notion of a geometric more
than distance to the boundary requires
understanding the Lucas properties of
the function okay
okay so that's a hard margin what is a
soft margin there exists an F in F such
that the proportion so one over m times
the cardinality of the set i such that
weii f of X I is less than gamma is
small
now this is something you can try to
check in practice you've trained your
neural network you look at how many how
many data points maybe they were
correctly classified but not correct not
quite correct enough
Cardinals are just counting just go
through go through all the points and
check if it's less than gamma no I don't
so this is a this is a yes let me put it
on cones
okay yes question
this is in the south
um
so we're hoping is that our problem
somehow is simple enough that one of
members of our class of functions let's
say neural network
a not only separates the data but it
separates the data with a mark that's
our hope that's what we're gonna call
easy
that's our notion of okay maybe maybe
it's not easy like a small easier that I
drew but today is to show that if you
are willing to believe that was a neural
network can separate your data and not
have too many mistakes then this VC
analysis is zero then I can I can just
tell you a sample just based on the
rather more averages of the class has
nothing to do with ABCD and therefore
the number of neurons in the neural
network is irrelevant so this whole
organization stories are relevant ok
and the proof is I mean I distilled it
to essentially three lines if you can
bear with me three lines we're gonna be
I'm going to do it in expectation just
because things are simpler in
expectation typically I would write
things with high probability of
something always right it's nice in
expectation you couldn't at home high
probability result so I'm going to look
at the indicator loss as a function of Y
times f of X so when Y times f of X is
negative you make a mistake the mistake
of one that's the indicator loss so the
black is black is indicator that Y times
f of X
I'm going to propose two more losses two
more loss functions one is going to be
let me put gamma here one is going to go
like this
I'm it should be in the same level one
but I'm just drawing visualization and
then it's going to slow down and then
it's gonna stay at zero okay so this one
I'm gonna call it feet of Y f of X and
that is zero if y f of X it's going to
be one if y f of X 0 and it's going to
be 1 minus s over gamma when y f of X
zero
this is best right
okay is that okay I just put down the
formula for for this transition so let
me call it a ramp ramp loss
so it kind of looks like a round and
then I'm gonna I'm gonna have a and not
yet another the third one I'm gonna put
it like that and I'm gonna continue
until gamma and then draw and continue
at zero and then I'm going to call a
sigh sigh of Y X would be the indicator
that y FX
okay
okay so I can define L C of F to be well
you know as before it's expected
expected P of Y f of X when x and y are
drawn from the distribution P right
I'm going to use black and same thing
with a sigh
and and the empirical right let me do it
here
the empirical let's say sigh if you can
distinguish from like five from sigh
roughly it's going to be 1 over n sum of
and actually let me write it out and I'm
gonna write it out as a indicator that's
why I f of X I is less than gamma so
what's the meaning this is f so what's
the meaning of empirical with respect to
sigh of f
in words
for function f it's the proportion
when the margin is less than counter
right it's exactly what I rolled here
this is exactly so I'm hoping that in my
class F there is one function or more
such that the L hat F side is small
right so I got captured by by prior
knowledge like that and there are only a
few proportion is small of the margin
mistakes again a margin mistake is when
this if this is let's say gamma if this
grad moves into this region that's that
indicator of a gamma mistake right it's
a common mistake even before it crosses
the decision boundary force it's on if
it's on the wrong side of the decision
boundary it's for sure a mistake but
this will count even if you are not
confident enough it will it will count
against you reduce the prediction and
you said 0.1 yes you're correct but
don't confident enough sorry
so the nice thing about the these three
functions is that they dominate each
other in an obvious
so they dominated each other in the
sense that the indicator is less than P
is less than side right point wise you
can see it from the picture but it also
means that for any F things like this
happen so zero one loss of F is upper
bounded by P is upper bounded by side
and the same thing for the dribble and
this is the indicator right there zero
one indicator loss so empirical of apt
less than
of f+ them sigh ok any questions about
of this their positives
I just positivity it's not even that
important here okay
now if I look at the expected maximum
over F in F of L P of F minus L hat P
I'm looking at how empirical quantities
relate to expected quantities but I'm
looking specifically at the thieve loss
function right at this at the ramp
the ramp was fun the green one now
because this guy is lower bounded by 0 1
and this guy is upper bounded by the
sigh I can lower bound this by expected
max of 0 1 F minus L side
I'm not putting parentheses but it's a
max over
this step is clear
how about now
we need to understand this quantity and
my claim is that this is upper bounded
by well the first step what do we do how
do we have our bomb different deviations
we do the synchronization lemma and we
get twice the averages of class twice
expected our hat of P of T of f is just
the loss function composed with every
function and F but P is Lucius it's 1
over gamma Lucius right the slope of
that transition the slope of the ramp is
1 over gamma so we can get rid of the P
by one of the properties that you saw
before whenever this is upper bounded by
two over gamma expected our hat off by
the way I'm not I'm not writing
projected onto the data but it's to be
understood right that these are it that
way that these are rather market
averages evaluated at the data now these
are evaluated at both x and y but now we
get rid of the fee there is only x y y
washes away y goes away actually for the
same reason
now this holds for maximum of a function
of the class so it holds for all the
functions so no matter what algorithm
you're gonna use if the algorithm
chooses from F let's say you work with
linear functions the algorithm chooses
from F this will apply to your algorithm
that's the beauty about taking the max
it will apply to any data dependence
algorithm that learns from the data
works for all functions at the same time
chosen from that and so once that you
have F hat M chooses or learns but takes
the others in F then what we can
conclude is the margin Bob and we're
done
so there's a margin bound the bound says
for that F hat that takes values in F
they expected out-of-sample zero one
loss - the empirical expected empirical
empirical side loss is bounded by two
over gamma that's it
okay
or I can put in I can break this term to
the other side if this is a bit more
pleasant now what's the meaning of this
if the Rademacher averages of the class
are nicely behaving so you can control
the capacity of your model which is you
have to have that and gamma is not too
small you don't choose 0 for your gamma
and the number of margin mistakes is not
too bad then you have a guarantee that
the expected performance on the new
sample is that's it it's a one line
really one line that's the highlight of
large margin theory that was explaining
the good performance of support vector
machines or it's one way to explain
performance of support vector machines
this was method that was used before
deep paths
you couldn't compute the same things for
deep nets and there are papers showing
what is the expected number of margin
mistakes with a gamma margin and what is
the complexity of the class of model so
20 years ago when what people looked at
support vector machines that map your
problem into our KHS reproducing kernel
over space and that they do
classification and dust in that space
the decision boundary is kind of
creating and it's an infinite
dimensional space so people first said
well VC Theory cannot explain this
because there are too many parameters
the model is over parametrized you can
have
generalization bond right hopefully this
reminds you of something it's exactly
the same thing that people now say about
the neural nets so one of the answers is
well the VC dimension does not give it
enter here it's irrelevant for the
market analysis even be an infinite
dimensional VC class the market bound is
still is still there and gave it gave a
justification to methods that try to
maximize the margin in the data this is
a justification to to try to mean him to
try to minimize this right I mean once
you see this bound you say okay I'm
gonna go after this I don't want to do
just empirical risk minimization with
this year one was I want to minimize the
margin sorry maximize the margin as well
I want to have a decision boundary that
not only correctly separates the data
but also goes through kind of like a
minnow right
lower bound on the complexity of the
model but I don't really know what how
do I don't really know then I would have
to quantify this so there are a couple
of things that I swept under the carpet
one thing that I swept under the carpet
is you can get this result in high
probability just as in hyper guilt over
the draw of the data right so why is
that nice because it because then the
statement is like this so a high
probability statement high probability
statement with probability at least 1
minus Delta L is upper bounded by L hat
side plus 2 over gamma r f+ and there
are some there are some terms that go as
low 1 over delta / it ok so then then it
really is about the interpretation we're
discussing this is other day so what's
the interpretation of these results it
says of course you've got a data set in
front of you right you you don't really
draw the data stuff but you'd have to
give this mindset that my dataset came
from the population as an independent
this population of let's say images and
I know that with probability 1 minus
Delta the statement is correct and
therefore I'm confident that my data set
is 1 of the 1 minus Delta 1 so I'm
confident that the statement is correct
that makes sense if I'm confident then
ok because I have a guarantee that the
out-of-sample performance of my method
is is controlled by margin mistakes plus
some complexity our example if you
observe in the data that you've got
small number of margin mistakes
maximizing mark oh right okay so another
thing that I swept onto the carpet is
that this method if I were to minimize
gamma margin mistakes my method better
known with gammas but in fact I can once
I have the hyper bill system I can take
a Union bound over all gammas so in fact
I can make a statement for Olga with the
margin is I can optimize after those and
then they optimize over this gap because
the statement will work for any gap so
that's going to be a separate class so I
I'm not telling you how to actually
let's do it for this is a good point I
can I erase this for for by the way for
a large margin theory of classification
and took a lot of years there's a lot
you can read more on Iran
okay so this is a side so we talked
about things like Rademacher averages of
a bowl in n dimensions with respect to
let's say L - so it's just a spear a
bull in dimension if you remember we saw
that is just a 1 over squared right but
what I'm telling you here is that I need
to take a class out and let's say F is a
class of functions X maps to W X where W
is now constrained in mountain or okay
and let's say for simplicity all that x
i's are bounded by 1 as well all the
data lives inside table now I need to
talk about Rademacher averages of F
projected onto X 1 through X M now this
is a pole but these objects live in the
dimensional space so WX r d
now what is the meaning of this this is
just a you know I think one W and then
they available on x1 expand and then I
take another WWE prime and I evaluated
prime and then I keep going over the
different w's and these are all the
different vectors but again
do I get a fool
there is no rotational symmetry so it
can't be a ball as there's something
else so what kind of object is as I
enumerate all these vectors over all the
different w's what is this
actually I'll leave it to you I don't
know what this is as you try to
enumerate over all the W's in the bowl
but I don't want to stress this
difference one is I know what my values
are constrained like and the other one
is I know what my parameters are
constrained like okay and I want you to
understand this difference what I'm
looking for this is the important object
not that one this was just an exercise
this is the important object and it's
actually not too clear what the shape of
this is because you have to go again
through all the W's and look at the
vectors obtained by evaluating every w1
this equals x1 is the problem clear when
you have these points on the sphere
right and now you take 1w and then you
project everything onto this direction
right that's the meaning of the
inner products right and now you've got
some values and that's the vector now
and I will rotate the vector and there
you get a different projection and so as
you rotate what kind of projections
Optimus spectra can you realize
so the thing is that you don't have to
actually explicitly describe this
projection right our hand off of this F
this particular half well let's just
write it out it's a expected epsilon 1
epsilon M max over W of norm one of sum
of epsilon I W X I that is the
definition I just wrote down the
definition except instead of writing
first writing out what the definition of
F is and then putting it in that that's
the same right is it wrong clear that is
the same thing right because as I go
over the different double use I'm
looking at correlation of the random
signs and the values of the function on
my data
that's my richness of
but let's write it out oh this isn't in
here right so you can take W out
yes can i I mean the product I can take
the W so that's expected epsilon max W
by one W times some epsilon I by the way
I'm I didn't normalize so this is M
times X I yes anytime you have a maximum
over W times something you're itching to
to the water not necessarily kernels but
just to write it as super what's the do
L to
that's it right and now I can do the
thing that I did last time which is put
a square on it everyone sees this right
now put put a square and take square
root nothing changed and then I buy
Yongsan I take the square root out
this is a very useful trick right now
what happens to the cross terms when I
open up this square the first terms are
zero in expectation right because they
have epsilon a epsilon J X I times XJ so
what remains is just the epsilon I
squared which is 1 times X I norm
squared right which is the most one so
the sum from 1 to N of 1 is just N and
there is square root outside so that's
equal to it's it's it's it's upper
bounded because of this and if I were to
normalize by 1 over n then Rademacher
averages will be 1 over square of M so
in this case this is bounded by 1 over
I just / it deceptively looks the same
as this one but for wrong reasons it's
just a coincidence in particular if I
had a one-goal here remember what was
this number was for l1 was 1 over m
right if I define my class of functions
where it W the parameters are bounded by
l1 you know one more then it makes sense
to bound these by everything because
then the product of them by cauchy
schwarz
is bounded by 1 and so the function
values are normalized to be between
minus 1 and 1 in that case this is this
is a 1 norm and the dual 12 one is
infinity so I'm looking at L infinity of
a random vector of a sum of random
vectors so it's the largest ordinate
after I add up and random vectors now
the the maximum over a coordinate
behaves like scores of log right so
that's very different from a 1 over N
you can work it out at home or maybe I
put it in that at some point and in the
slides but I didn't give you enough
detail
so it's just by accident that we got the
same the same result now here's the
punchline let's go back so forget about
the l1 case let's go back to this one
let's take of perceptrons
what is it perceptron it's a hyper plane
whose normal is bounded by one in the l2
sense
so that's exactly this fast so
perceptron is actually working okay now
of course when you have a perceptron you
go away to make a prediction you anyway
would normalize it doesn't matter how
well this important is that the W star
the one that gives you the gaba margin
is normal that's where this constraint
comes in right that's your prior
knowledge about the problem I think that
there's going to be a vector W star
which will give me so what result are we
gonna get for a perceptron
so let's see implication for perceptron
so the class f is this class and we get
expected l01 of f hat which is really
our but this will work for any iranian
hyperplane is upper bounded by the
number of grammar mistakes plus 2 over
gamma times that is what I just erased
it 1 over square
if I have a hyperplane that completely
separates the data by the way this will
hold for for any for any learning method
with values in F which is this class for
any method that chooses a hyperplane I
can guarantee the future performance of
this hyperplane is at most the number of
gamma mistakes
it makes plus 1 over square root of n +
1 over gamma right so what we've done
now is we've extended perceptron beyond
the what's called the realizable case
where there is a hard margin right now
this can be a soft margin there could be
a number of mistakes but if you've got
this number relatively small then you've
got a good guarantee for future
yeah really I've had em except I didn't
want to say that as you see because I
didn't want because I've had them
depends on the data and the sex vacation
so right so if I have my F hat n is is
is when the one had this function on the
other hand that's it's something that I
learned from the data and this
expectation I didn't want to say here
for any F hat
yes thank you thank you but this high
probability will also it may be better
to write the high probability statement
okay do we recover the perceptron result
that we got in the first lecture so
there it was separable and therefore
this was zero expectations so with
probability at at least one minus Delta
for any learning method with values in F
this holds and then there is something
which I'm not going to specify
so that's that's the guarantee so if I
observe no mistakes which was the case
when I ran perceptron convergence right
this was the second consequence in our
lecture this is zero and so I get
out-of-sample performance for the
perceptron is bounded by 1 over gamma
times 1 over square development did we
gather did we recover the result we had
what was the result we had for the final
hyperplane yes
in fact it was one we're gonna square
because that's the number of mistakes if
you remember how we got that result when
we got a square and 1 over N it was
twice faster than what we've got here so
this result works without this hard
assumption of linear separability it
works under a soft margin right which is
more natural probably yes occasionally
you get cats which look like dogs and
we're gonna kind of a larger sample
complexity if you set this to epsilon
you get sample complexity is like 1 over
epsilon squared rather than 1 arrest so
that was so one could get a result that
would recover that perceptron result but
that's it's much more difficult so I'm
not gonna
any questions questions
so again the point here is that the
these hyperplanes could be in a
dimensional space where it is very high
and in particular T is the number of
neurons if you think of a hyper plane as
a one layer neural network it seems like
I have everything a hyper plane is a one
layer getting one layer neural network
without the and D the dimension is just
the number of units in that later right
so as you see he never appears here
right so the even the premise that the
neural network generalization has to
depend on the number of units in the
neural network is not true a result
without without the number of units for
one layer of course what more layers is
gonna be more complicated questions yes
yes it's so right so this is kind of
like a posteriori result right it says
in a train your model and you look at
the margin distribution pick the best
gamma you can but balances this and that
and that will give you a guarantee on
the out-of-sample performance
so in the original 2002 paper by
Kochanski panchenko there is some
analysis that looks at theoretically at
the empirical margin distributions
papers called empirical heartland
distributions
it looks at them theoretically and how
they relate to the population market any
other questions so the question is
should I start the compression
okay should I describe something else
some other result in neural networks
right right so one thing that Tommy is
saying let me repeat this is we've got
this we've got this - which is this
Rademacher averages and that's a way to
understand classes of functions with
which you're working if you're working
with neural nets okay the way that you
compute this is you upper bounded you
see how we got upper bounds on this you
are per bounded by some more and we
restricted the weights of our one layer
we restricted that norm to be one and in
the same way we'll see that you can you
can say that all neural networks with
bounded norms of the weight matrices we
can we can get a result but this is not
the only way to proceed right I'm just
showing you one path to getting
generalization bounds performance there
are other methods in particular I will
describe at least stability compression
you know differential privacy type of
thing for random
right right okay elaborate on this so I
should do this came out from the
discussion that Friday you know why do
we do this actually what's the point of
these bounds this was one of the
comments I mean it's a good comment
right like what is the practical
implication beyond the pure joy of
understanding that you put something on
the population that you don't know right
like this is what I want right and I've
just proved that this is small so
there's certain pure joy but beyond this
like what what are the algorithmic
implications of this right and and so
one implication is that whatever would
get as a complexity you can use to
regularize the problem and that should
be a proper way to regularize you can't
just minimize over all functions in the
universe right you have to have some
kind of prior
yeah algorithm has to be has to contain
some regularization so I understand did
you understand what kind of capacity can
be used to regularize the problem so for
instance as you can see by controlling
the norm of the vectors you've got a
very nice one over the court the fan is
essentially the best you can hope for
that's like if you've got two two
functions which are different than now
that's already one over square defense
so having a oh oh and l2 and getting the
same for the price of you know so it
tells you that l2 can serve as a as a
certain of regularizer and in fact you
can relate these Rademacher averages to
what should be the penalty how do should
you do tune of regularization with l2
norm that's essentially what it is right
typical regularization is your in our
case with the coefficients and that
comes out as a proper way to regularize
a problem but now when you talk about
neural networks now maybe it's a product
of norms of the norms of the weights of
the layers for instance right so that
could be now a regularizer
that's meaningful even in tracking
momentum in practice so these go hand in
hand you you understand the complexity
and how how controls the these empirical
fluctuations that can easily view you
see something on the data but this is
something else in the sample and
understanding was complexity tells you
how to regularize the problem right so
there are things like path sgt is one
example where you you take that
complexity and you actually penalize
your neural network training with that
complexity and you can already see it
here like if I kept it let's say I kept
it here as a B right so the norm of the
W is bounded by V right this is B and
then it would be just B times B and this
would be P right so here I would have a
here I would have two times but in fact
by working a little bit harder even you
can replace the l2 norm of the W here W
have you have to work a bit harder but
that is possible so this suggests that
you should be optimizing so you minimize
margin loss and complexity of the model
as this extends the kernels yes you you
put
you put K of X I here and then this
becomes square root of K and so if you
have a it's the same but it's hard if
all the approaches family cannot say
that like either something
ah sure if I understood correctly if
none of your approaches work it doesn't
mean that the result is not true yeah
okay
happy to answer questions