>> Alright, so back to boosting, Michael. So as
you recall the little teaser I left you with last
time, is that it appears that boosting does not
always over-fit. And a little graph. That's true, but it
doesn't seem to over-fit in the ways that we
would normally expect it to over-fit. And in particular we'd
see a, you know, an error line on training And
what we expect to see is a testing line that
would, you know, hue pretty closely and then start to
get bad. But what actually happens is that instead, this
little bit at the end where you get over fitting
seems to instead. Just keep doing well. In fact, getting better
and better and better. And I promised you an explanation
for why that was. So, given what we talked about
with support vector machines, and what we spent most of
our time thinking about, what do you think the answer is?
>>
Well I, I don't think I would have asked again if I, had
a thought about it. But you mean You want me to connect it
to support vector machines, somehow. Well the, the thing that was fighting over
fitting in support vector machines, was
trying to focus on maximum margin classifiers.
>> Here, let me, let me try to explain to you
why it is that you don't have this problem with With
overfitting at least not in the, in the typical way as
you keep applying it over and over again like you do
with something like neural networks. And it really boils down
to noticing that we've been ignoring some information. So, what we
normally keep track of is error. So error on say
a training set is just, you know, the The probability that
you're going to come up with an incorrect answer or
come up with an answer that disagrees with your training set.
and that's a very natural thing to think about and it
makes a lot of sense. But there's also something else that
is actually captured inside of boosting and captured by a lot of learning
algorithms we haven't been taking advantage
of, and that's the notion of confidence.
So confidence is not just whether you got it right or wrong. It's
how strongly you believe in a particular answer that you given. Make sense?
>> Yes, a lot of the algorithms we talked
indirectly have something like that. So, like in a nearest
neibhbor method, if you are doing five nearest neighbor
and all five of the neighbor agree, that seems different
than the case with vote one way and two vote the other.
>> Right. And in fact, that's a really good example. If you think of that in
terms of regression Then you could say something
like the variance, between them is sort of
a stand in for confidence. Low variance means
everyone agrees, high variance means, there's some major
disagreement. Okay. So what does that mean in
the boosting case? Well as you recall, the final
output of the boosted classifier is given by a very simple formula.
And here's the equation here that h of x is equal to the sine of
the sum over all of the weak hypothesis that you've gotten of alpha
times h. So the weighted average of all of the hypothesis, right? And
you just simply, if it's positive you produce a plus
one. And if it's it negative you produce a minus and
if it's exactly zero you don't know what to do
so you just. Produces zero. Just throw up your hands. So
I'm going to make a tiny change to this formula, Michael. Just, just for
the purpose of sort of, explanation, that
doesn't change the fundamental answer. And I'm
just going to take exactly this equation as it is. And I'm going to divide
it, by the weights that we use. Now what does that end up doing?
>> Okay, so the weights. I'm getting a.
There's Alphas in the SVM's too, so I'm
getting a little confused. So that I'm. I
think these Alphas all have to be non-negative.
>> Right.
>> But they kind of like this support vector values, in that
there could be zero, if, if that hypothesis isn't come into play?
>> Well, but they want in that case, the, the
alpha is always set to be the natural log of something.
>> Oh, oh, oh, and also these alphas are applied to hypothesis whereas
the alphas in the, in the SVM settings were being applied to data points.
>> That's right. So, unfortunately in machine
learning, people in, invent things separately and
re-use notation. Alpha's an easy Greek character to draw, so people use
it all the time. But here, remember, alpha's the measure of how good
a particular weak hypothesis was, and since it has to do better
than chance, it works out that it will always be greater than zero.
>> Gotcha, okay. So this, this normalization factor,
this denominator doesn't, it's just a constant with respect
to x, the input. So it won't actually change
the answer. So it really is the same answer
as we had before, just a different way of writing it.
>> Right. And what it ends up doing like
often is the case in these situations, is it
normalizes the output. So it turns out that this
value. Inside here is always going to be between minus
one and plus one. Okay? But otherwise it doesn't
change anything about what we've been doing for boosting. So
you might ask why did I go through the
trouble of normalizing it between minus one and plus one?
>> Why indeed?
>> Well it's makes it easier for me to draw
what I want to draw next. So, we know that the
output of this little bit inside the sign function is
always going to be between minus one and plus one. Let's
imagine that I take some particular data point x and
I pass it through this function, I'm going to get some
value between minus one and plus one. And let's just
say for the sake of the argument, it ends up here.
Okay?
>> Is that an x or a plus?
>> That's a plus.
>> Okay. So it's a positive example and it's near plus one.
>> Right.
>> So this would be something that the algorithm is getting correct.
>> Yes, and it's not just getting it correct,
but it is very confident. In its correctness. because it
gave it a very high value. By contrast there
could have been another positive that ends up around here.
>> Hmm.
>> So it gets it correct but it doesn't have a lot
of confidence so to speak in its correct answer because it's very
near to zero. So that's the difference between error and confidence. Because
for example I could also have a plus value way over here.
So I am very, very confident in my very, very incorrect answer.
>> Mm.
>> So this is my daughter, for example.
[LAUGH] She's very confident whether she's right or
wrong. [LAUGH] Okay. And so now imagine there's
lots of little points like this. And if
you're doing well, you would expect that, you
know, very, very often you're going to be
correct. And so you end up shoving all
the positives over here to the right, and all
the negatives over here to the left. And it would be really nice if you were
sort of confident in all of them. Okay,
so does this make sense, Michael as a picture,
>> Oh yeah.
>> What, what might be going on? Absolutely.
>> Okay, good. So now I want you to imagine that we've
been going through these, these training
examples, and we've gotten very, very good
training error. In fact, let's imagine that
we have negative training error. I'm [LAUGH]
>> Wow.
>> In fact, let's imagine that we have no
training error at all. So we, we label everything correctly.
So then the picture would look just a little
bit different We're going to have all the pluses on one
side, and all the minuses on the other. But
we keep on training, we keep adding more and more
weak learners into the mix. So here's what ends up
happening in practice, right? What ends up happening in practice
is, you have to do some kind of distribution
on the hard examples. And the hard examples are
going to be the one that are very near the
boundary. So as you add more and more of these
weak learners what seems to happen in practice is
that these pluses that are near the boundary and these
minuses that are near the boundary just start moving
farther and farther away from the boundary. So, this minus
starts drifting and drifting and drifting until it's all the way over
here, this minus starts drifting and drifting and drifting untili it's all the
way over here. And the same happens for the pluses. And as
you keep going and you keep going, what ends up happening is that
your error stays the same. It doesn't change at all, however your
confidence keeps going up and up and up and up and up. Which
has the effect, if you'll look at this little drawing over here of
moving the pluses all around over here, so they're all in a bunch,
and the minuses are on the other side.
So what does that look like to you, Michael?
>> This picture?
>> Yeah.
>> I mean that there's a, there's a
big gap between the left most plus and the
right most minus. Which, you know, in the
context of this lecture reminds me of a margin.
>> That's exactly right. Basically what ends up
happening is that as you add more and more
weak learners here the boosting out rhythm ends
up becoming more and more confident in its answers
which it's getting correct. And therefore effectively ends up creating a
bigger and bigger margin. And what do we know about large margins?
>> Large margins tend to minimize over fitting.
>> That's exactly right. So it, counter intuitively, as we create
more and more of these hypotheses, which you would think would
make something more and more complicated, it turns out that you
end up with something smoother, less likely to overfit and ultimately,
less complicated. So the reason boosting tends to do well and tends to avoid
over fitting even as you add more and more learners is that you're increasing
the margin. And there you go. And if you look in the reading that
we gave the students there's actually a
detailed descritpion about this in a proof.
>> Cool.
>> Okay. So, there you go, Michael.
Do you think, then, that boosting never overfits?
>> [SOUND] Never seems like such a strong word.
I mean, the story that you told says that it's going to try
to separate those things out, but I guess I guess it doesn't have
to be able to do that. I mean, it could be that
for example all the weak learners
are I dunno very unconfident very inconsistent.
>> Hm. Okay, well you know, maybe, maybe it's worthwhile to
take a little diversion here to take a five second quiz.
>> I think it's worth the time.
>> Done!