Advertisement
English transcript
The following content is provided under a Creative
Commons license.
Your support will help MIT OpenCourseWare
continue to offer high quality educational resources for free.
To make a donation or view additional materials
from hundreds of MIT courses, visit MIT OpenCourseWare
at ocw.mit.edu.
PROFESSOR: Good morning, everyone.
Today, we're going to talk about boosting.
Boosting is pretty awesome, and it's not as hard
as it might seem.
It's actually pretty easy, as long as you do it right.
So let's take a look at this boosting problem.
Just like with ID trees, you may have
noticed there's the ID tree problem where there's a graph,
and all of the tests are x and y-axis tests on that graph.
And then there's the ID tree problem
where there are a lot of crazy different classifiers
about characteristics that are discrete.
And then all of the sort of ID tree stumps, if you will,
are built out of those discrete qualities.
This is an example of a boosting problem
of the second type with a bunch of discrete qualities,
like evil, emo, transforms, sparkly.
And it has an numerical quality number of romantic interests.
So it's one of basically the two kinds
of boosting problems that you might see.
And now, there is the two-axis Cartesian problem.
A good example of that is the hours
of sleep versus coffee problem, which I, for one, am planning
on doing in tutorial on Monday so that you guys sort of get
a sense of both types of problems.
This one looks big.
I think it looks-- I mean, it has ten different vampires
or non-vampires to classify.
It has a whole bunch of possible classifiers.
But if you do it right, you can do it fast.
So here's the prompt for the problem.
Let's see.
After graduating MIT, you get a job
working for Van Helsing and Sommers,
a famous vampire-hunting consulting agency.
Gabriel Van Helsing, one of the two founders,
once attended several 6.034 lectures as a guest,
and he remembers Professor Winston's
vampire identification tree lecture.
He assigns you the task of creating
a superior classifier for vampires
by using boosting on the following data.
So we've got the ID number, which
we can use to just write things out in shorthand.
We've got the name of several vampires and non-vampires.
Then you see whether they're a vampire or not.
That's whether their classification
is a plus or minus for the quality of vampire.
After that, there's a bunch of possible ways
to classify whether they're a vampire or not.
There's whether or not they're evil, whether or not
they're emo, whether or not they transform,
and whether or not they're sparkly, as well
as the number of romantic interests that they have.
So for instance, on the one hand,
you have Dracula, who's evil, but he's not emo.
He can transform into a bat or a cloud of mist.
He does not sparkle, and he has five romantic interests--
those three vampire chicks at the beginning, Wilhelmina
Murray, and Lucy Westenra.
So on the other hand, you have Squall Leonhart,
who's the protagonist of Final Fantasy VII, is extremely emo
and doesn't have any of the other characteristics.
And he's not a vampire.
However, he's a nice counterexample
for a possible rule that all emo people
are vampires because he's very, very emo,
and he's not a vampire.
So how will we go about tackling this problem with boosting?
Well, there's a whole bunch of different classifiers.
And if you think this is all of them--
like evil, emo, transforms, sparkly.
romantics interests, and true-- it's actually only half
of them.
The other half are the opposite versions,
but we'll ignore them for now.
So if you look at these, you can probably
figure out what they mean-- evil equals
yes means vampire is what we're saying here--
except maybe true.
You might be saying, why is there one that just says true?
The one that just says true says that everybody is a vampire.
You might think, oh, that sucks.
But it's not that bad since seven of the 10 samples
are vampires.
The key, crucial thing about boosting
is that for any possible classifier,
like classifying on the evil dimension-- which actually
sounds like some kind of weird place
that you'd go in a comic book.
But classifying on the emo dimension or whatever,
as long as it's not a 50-50 split of the data,
you're guaranteed to be able to use it
in some way for boosting.
If there is a 50-50 split, it's like flipping a coin,
so it's useless.
Because if you had some other thing,
like gender equals male or female--
and let's say that was 50-50.
It's not.
But let's say it was 50-50 between vampire
and non-vampire-- it's a useless classifier
because it would be just the same as flipping a coin.
You'd get no information.
Now, you might say, wait a minute.
What about classifiers that get worse than 50-50?
What about them?
Might not they be even worse than a 50-50 classifier?
I claim a classifier that gets less than 50-50
is still better than a classifier that
gets exactly a 50-50 split.
Is there a question?
AUDIENCE: Yeah.
In the ID tree example, somebody said you used 50-50 classifiers
and played around.
And after you already produced the elements per set,
then you only used 50-50 classifiers [INAUDIBLE]
per set.
PROFESSOR: So the question is, in the ID tree example,
you might use 50-50 classifiers in later rounds
if, for instance, there's a 50-50 classifier
except for that most of the things off of that side
have been already removed.
Let's say there's 20 data points,
and there's a classifier that splits it 10 and 10.
And it gets half plus half minus on both sides.
But all the pluses from the right side
have been removed by some other classifier.
You might use it.
That's true.
But in boosting, you will never use something
that's a 50-50 classifier.
You never use something that has exactly a 50-50 chance
of being correct.
Because if it has a 50-50 chance of being correct, it's useless.
And if it has a 50-50 chance of-- no, sorry.
Let me specify again.
You'll never use something that has
a 50-50 chance of giving you the right answer given the weights.
That's very, very important.
And that may be what your question was getting at.
As I'm about to show you and as Patrick told you
in the lecture, in later rounds of boosting,
you change the weights of each of the 10 data points.
At first, you start with all weights being 1/10.
The weights have add up to 1.
In this case, you never, ever choose
a classifier that gets five of them right and five of them
wrong.
In the later rounds, you'll never, ever
choose a classifier that gets half of the weight
wrong-- exactly half of the weight wrong.
But half of the weight may not be half of the data points.
So it's possible to choose a classifier that
gets half of the data points wrong if it doesn't
get half of the weight wrong.
And that's similar to an ID tree when you've already
gotten things right before.
Because you'll see that the weight is going to go
to the ones you got wrong.
So I'm not saying that you should throw out
right away anything that gets five of the points wrong.
Hell, you shouldn't even throw out right away something that
gets seven of the points wrong.
It's possible-- possible-- that you can get seven of the points
wrong, or getting less than half of the weight
wrong if those other three points are really, really
annoying to get right.
And we'll see that later on.
But for insight, at every step along the way,
we're willing to choose any classifier that
doesn't get 50-50.
However, we want to choose the classifier that gets
the most of the weight right.
By most of the weight, at first, we
mean most of the points right.
Later, we will mean exactly what I said-- most of the weight.
And if you don't understand that, it's sometimes
hard to get it right away when Patrick just
lectures through it, introduces a new concept.
If you don't understand that, you'll
see what I mean when we go through, all right?
So my point I was making before is, what about things
that get less than half of the weight right?
Well, those are always OK because you can just flip them
around, use their inverse, and that gets more than half
of the weight right.
It's sort of like-- yeah, it's sort
of like my girlfriend always tells me
that she is more than 50% likely to choose the wrong direction
when you're trying to go between two places, which
I'm kind of skeptical of.
But I said, if that's really true,
then we can just go wherever you didn't say to go,
and we'll be more likely to go the right way.
So you're actually really good at finding the place
that we want to go.
And then she's like, no, that won't work.
Because then I'll know that you're going to do that,
and I'll double say the wrong way.
And then you'll go the wrong way again.
But that not withstanding, you can see you
can apply the same concept to boosting.
And that's why underneath of this,
I have all the opposite versions of all these tests.
So what should we be doing to solve this problem more
quickly?
First, let's figure out which data points are misclassified
by each of these classifiers.
In other words, if we say all the evil things are vampires
and all the non-evil things are not vampires,
what do we get wrong?
And if we do that for every classifier,
then that'll make it faster later on.
Because later on, we're going to go through classifiers,
and we're going to have to add up the ones they got wrong.
So this chart over here is going to be extremely useful.
And on the test that this appeared in,
they even made you fill it in to help yourself out.
So let's see.
If we said that all the evil equals yes are vampires
and all the evil equals no are not vampires,
then-- I'll do the first one for you.
So we get all of the non-vampires
correct because they are all evil equals no.
But unfortunately, we get Angel, Edward Cullen, Saya Otonashi,
and Lestat de Lioncourt wrong because they are vampires,
and they're evil equals no.
Apparently, Lestat is iffy.
But I never read those books, and the Wikipedia article
said that in the end, he wasn't that evil.
So there we go.
Evil equals yes misclassifies 2, 3, 4, and 5.
All right, so let's try emo equals yes.
I'll have someone else do it.
So let's see if you guys got it.
So if we say that all the emo people are vampires
and all the non-emo people are not vampires,
what do we get wrong?
AUDIENCE: 1, 6, 7, 9.
PROFESSOR: 1, 6, 7, 9-- that's exactly right, and fast.
Good.
We get 1, 6, 7, and 9 wrong.
1, 6, and 7 are wrong because they are not emo,
but they're vampires.
9 is wrong because Squall is emo, and he is not a vampire.
Good.
OK, what if we said that exactly the transforming characters are
vampires and the ones that do not transform are not vampires?
Which ones will we get wrong?
AUDIENCE: [INAUDIBLE].
PROFESSOR: Transforms is the next one over.
AUDIENCE: All of the ones [INAUDIBLE].
PROFESSOR: So which ones would we
get wrong if we said that said transforms yes were vampires
and transforms no were not vampires?
AUDIENCE: We'd get 8 wrong.
PROFESSOR: We'd definitely 8 wrong
because she's not a vampire.
AUDIENCE: [INAUDIBLE].
PROFESSOR: Well, no.
It's actually on there.
AUDIENCE: And 3 and 4 we'd also get wrong.
PROFESSOR: Yep.
AUDIENCE: As well as 5.
PROFESSOR: Yes, exactly.
OK.
Oh, man.
You didn't see the chart.
You were just like, hmmm.
You saw the left.
You just said, hm, which one of these
are the transforming characters?
OK, that's pretty hardcore.
AUDIENCE: [LAUGHTER].
PROFESSOR: But yeah, 3, 4, 5, and 8.
No, no, it's definitely given to you.
That would be like the worst test
ever for international students.
Ah, if you don't know these ten characters as vampires,
you lose.
All right, so what about that sparkly
equals yes is a vampire, and if it's not sparkly,
it's not a vampire?
This is guaranteed not to go well.
What do you think it's going to get wrong?
AUDIENCE: For sparkly?
PROFESSOR: Yeah, sparkly equals yes are the only vampires.
AUDIENCE: [INAUDIBLE] wrong.
Angel's going to be wrong.
Saya-- so 1, 2, 4, 5, 6, 7, and 8.
PROFESSOR: And 8-- yes, that's right.
It gets 1, 2, 4, 5, 6, 7, and 8 wrong.
That's pretty awful.
But dammit, it gets Edward Cullen right.
And he's hard to get correct due to the fact
that he's not very much like a vampire.
He's more of a superhero who says he's a vampire.
OK, so next, number of romantic interest greater than two.
So if they have more than two romantic interest,
they're a vampire.
And otherwise, they're not a vampire.
So which ones would that get wrong?
Hm?
AUDIENCE: 3 and 10.
PROFESSOR: Just 3 and 10, that's right.
Because Circe had Odysseus.
She had Telemachus.
Actually, she had that guy she turned into a woodpecker.
She had that other guy who was a sea god who
caused her to turn Scylla into the nine-headed thing,
and probably at least one other person.
So Circe it gets wrong.
And it also gets Edward Cullen wrong because he only has one.
So 3 and 10.
You can tell I thought about this problem
when I was writing it up.
I wrote this one.
All right, number of romantic interest greater than four.
So it's a little bit different this time.
Now you have to have at least four romantic interests--
or actually, greater than four, but there
are none that are exactly four-- to be classified as a vampire.
Which ones do you think it's going to get wrong?
AUDIENCE: 3, 4, 10.
PROFESSOR: Yup, it is going to get 3, 4, and 10 wrong.
Because now, you run into the fact
that Saya has that blond [INAUDIBLE] guy, Haji, and Kai.
So the last of the positive ones-- because I claim I
can derive all the negative ones if you guys give me
the positive ones.
The last of the positive ones is everybody's a vampire.
Who does that get wrong?
AUDIENCE: 8, 9, 10.
PROFESSOR: Yes, OK.
Now, I can derive all the negative ones
from this without a sweat.
Evil equals no-- well, it's 1, 6, 7, 8, 9, 10
without looking at the chart.
Raise your hand if you see why it's 1, 6, 7, 8, 9, 10
without looking at the chart.
Raise your hand if you don't.
Nobody, OK-- wait.
One hand.
OK, I saw another one back there too later.
They were just more tentative.
OK, it's the complement of A because A is
evil equals yes is a vampire.
It gets 2, 3, 4, and 5 wrong.
So therefore, evil equals no is a vampire is guaranteed
to get all the opposite ones.
AUDIENCE: Oh, we could have looked at that too?
PROFESSOR: Yeah, we're looking here,
but we're not looking at the big chart there.
AUDIENCE: You can look at any?
PROFESSOR: Oh, yeah.
If you can't look at anything, then you're
screwed-- unless not only are you as hardcore as this guy,
but you've also memorized the numbers.
All right, so emo equals no is going to be 2, 3, 4, 5, 8, 10.
Transforms equals no is 1, 2, 6, 7, 9, 10.
Sparkle equals no is 3, 9, 10.
Romantic interest less than two is everything except 3 and 10--
1, 2, 4, 5, 6, 7, 8, 9.
1, 2, 5, 6, 7, 8, 9.
And then finally, everything but 8, 9, and 10, so 1, 2, 3, 4, 5,
6, 7.
All right, so when we started off,
we know what everything gets wrong.
I then make a bold claim, because there
are n of these, which is 14.
I make the claim that there are only six
that, in your wildest dreams, you would ever possibly
even consider using ever.
And the rest, you would never, ever use.
Question?
AUDIENCE: Yeah, I just have a question about the number
of romantic interests.
PROFESSOR: Yes.
AUDIENCE: You negated it without an equals on either side.
PROFESSOR: That's true.
That works only because there are [INAUDIBLE] 2 or 4.
But it should have been negated with a less than or equal.
I'm copying off of the quiz.
But yes.
I noticed that this morning when I was putting myself
through my pace.
I'm like, there's not a less than or equal to.
Wait a minute.
And then, oh, wait.
It doesn't have any 2's or 4's.
Actually, I don't remember writing them all
as 5's and 3's.
It's possible that somebody else in the post-editing process
changed them all to be about the same number,
and then changed the less than or equal tos
to be less confusing.
It's possible I had Circe at 4, and there was an equal
to somewhere.
And they were like, forget it.
Because I can't think of the fifth romantic interest
for her.
So yes, normally, you would have to negate it
with an equal to sign, but there happened
to not be any things that are equal to 4 or 2 here.
So they get away with it this time.
But it's good practice.
So I'm claiming that in our wildest dreams,
we'd only ever want to use six of these ever.
And the other eight, forget it.
So let's see.
I will call on people at random to-- the first people obviously
are getting it really easy-- to tell me
which of these you think that you might ever want to use.
Give me one you might ever want to use.
AUDIENCE: E.
PROFESSOR: Why, E?
Of course.
That's the best one.
Yes, that's one that you might ever want to use.
I'll circle the ones that you might ever want to use.
E-- it only gets 3 and 10 wrong.
That's amazing.
It's like the best class of [INAUDIBLE].
OK, so give me another one that you might ever want to us.
AUDIENCE: F.
PROFESSOR: F. Let's see.
F-- F is great.
It only gets three wrong.
Do people agree that you would ever want to use F?
AUDIENCE: No.
PROFESSOR: Everyone's saying no.
Why not?
AUDIENCE: It's like E, except worse.
PROFESSOR: It's like E, except worse.
It's guaranteed at every step, no matter
what the weights are, to have a worse accuracy than E.
It is definitely good.
If E wasn't around, it would be one of our best classifiers
of all.
But actually, F is not one of the six.
This is why I had them write on the test that there were six,
because people might not have found all six.
Because people who did figure out not to include F
might not have figured out to include some of the ones
you want to include.
So--
AUDIENCE: I don't understand why you can't use F.
PROFESSOR: Why you can't use F, OK.
So we start off with 1/10 weight for all our data points.
But let's say during our time of boosting
that all ten of the data points have now different weights.
So we'll call whatever the weight of 3
is, which you're going to get wrong-- you want
to minimize the error, right?
So that weight of 3, which goes into the error of the E, is x.
The weight of 10 can be y.
So if you're thinking of choosing 3,
you know you're-- oh, sorry.
If you're thinking of choosing E, your error is x plus y.
AUDIENCE: Sure.
PROFESSOR: If you're thinking of choosing F,
your error is x plus y plus z, where z is the error of 4.
And since you're never going to have a negative weight,
x plus y plus z is always greater than x plus y.
AUDIENCE: You can't choose something
without the 3 and the 10 anymore because you already chose E.
PROFESSOR: That's-- yes, you would probably choose something
that didn't get the three and the ten wrong.
But you would certainly never choose F ever
because it's always worse than E. In fact, this is exactly
the process that will allow you to find the correct six.
And by "will," I mean "can."
And by "can," I mean, let's see if you guys get it.
Give me another one of the six that you might keep.
AUDIENCE: K.
PROFESSOR: K is the claim-- sparkly.
K, I'm going to say will lose for the same reason
as F. It's 3, 9, and 10.
It's essentially similar to 3, 4, and 10.
So-- oh, by the way, we should not
be only going for the ones with the fewest incorrect.
You need to be going for ones that do not have something
that is strictly better.
In this case, 3 and 10 wrong is strictly
better than getting 3, 9, and 10 wrong.
Question?
AUDIENCE: Oh, I was going to say transform.
PROFESSOR: You were going to say transform.
You are going to be correct.
Transforms is one of the ones we need, C. 3, 4, 5
and 8-- there's nothing down here that gets fewer
than those wrong.
There's nothing that gets us 3, 4, 5 wrong, for instance.
Yeah, there's no way to get 3, 4 wrong without getting either
10 wrong, or 5 and 8 wrong.
AUDIENCE: So why is the 8 like that?
PROFESSOR: What?
AUDIENCE: Why not G?
PROFESSOR: Why not G?
Why not?
Why not G?
Let's include G, too.
AUDIENCE: Oh.
We don't have to do it all?
PROFESSOR: We need six.
No, I just said give me any, and someone gave me
the easiest one, E. Question?
AUDIE
…
Commons license.
Your support will help MIT OpenCourseWare
continue to offer high quality educational resources for free.
To make a donation or view additional materials
from hundreds of MIT courses, visit MIT OpenCourseWare
at ocw.mit.edu.
PROFESSOR: Good morning, everyone.
Today, we're going to talk about boosting.
Boosting is pretty awesome, and it's not as hard
as it might seem.
It's actually pretty easy, as long as you do it right.
So let's take a look at this boosting problem.
Just like with ID trees, you may have
noticed there's the ID tree problem where there's a graph,
and all of the tests are x and y-axis tests on that graph.
And then there's the ID tree problem
where there are a lot of crazy different classifiers
about characteristics that are discrete.
And then all of the sort of ID tree stumps, if you will,
are built out of those discrete qualities.
This is an example of a boosting problem
of the second type with a bunch of discrete qualities,
like evil, emo, transforms, sparkly.
And it has an numerical quality number of romantic interests.
So it's one of basically the two kinds
of boosting problems that you might see.
And now, there is the two-axis Cartesian problem.
A good example of that is the hours
of sleep versus coffee problem, which I, for one, am planning
on doing in tutorial on Monday so that you guys sort of get
a sense of both types of problems.
This one looks big.
I think it looks-- I mean, it has ten different vampires
or non-vampires to classify.
It has a whole bunch of possible classifiers.
But if you do it right, you can do it fast.
So here's the prompt for the problem.
Let's see.
After graduating MIT, you get a job
working for Van Helsing and Sommers,
a famous vampire-hunting consulting agency.
Gabriel Van Helsing, one of the two founders,
once attended several 6.034 lectures as a guest,
and he remembers Professor Winston's
vampire identification tree lecture.
He assigns you the task of creating
a superior classifier for vampires
by using boosting on the following data.
So we've got the ID number, which
we can use to just write things out in shorthand.
We've got the name of several vampires and non-vampires.
Then you see whether they're a vampire or not.
That's whether their classification
is a plus or minus for the quality of vampire.
After that, there's a bunch of possible ways
to classify whether they're a vampire or not.
There's whether or not they're evil, whether or not
they're emo, whether or not they transform,
and whether or not they're sparkly, as well
as the number of romantic interests that they have.
So for instance, on the one hand,
you have Dracula, who's evil, but he's not emo.
He can transform into a bat or a cloud of mist.
He does not sparkle, and he has five romantic interests--
those three vampire chicks at the beginning, Wilhelmina
Murray, and Lucy Westenra.
So on the other hand, you have Squall Leonhart,
who's the protagonist of Final Fantasy VII, is extremely emo
and doesn't have any of the other characteristics.
And he's not a vampire.
However, he's a nice counterexample
for a possible rule that all emo people
are vampires because he's very, very emo,
and he's not a vampire.
So how will we go about tackling this problem with boosting?
Well, there's a whole bunch of different classifiers.
And if you think this is all of them--
like evil, emo, transforms, sparkly.
romantics interests, and true-- it's actually only half
of them.
The other half are the opposite versions,
but we'll ignore them for now.
So if you look at these, you can probably
figure out what they mean-- evil equals
yes means vampire is what we're saying here--
except maybe true.
You might be saying, why is there one that just says true?
The one that just says true says that everybody is a vampire.
You might think, oh, that sucks.
But it's not that bad since seven of the 10 samples
are vampires.
The key, crucial thing about boosting
is that for any possible classifier,
like classifying on the evil dimension-- which actually
sounds like some kind of weird place
that you'd go in a comic book.
But classifying on the emo dimension or whatever,
as long as it's not a 50-50 split of the data,
you're guaranteed to be able to use it
in some way for boosting.
If there is a 50-50 split, it's like flipping a coin,
so it's useless.
Because if you had some other thing,
like gender equals male or female--
and let's say that was 50-50.
It's not.
But let's say it was 50-50 between vampire
and non-vampire-- it's a useless classifier
because it would be just the same as flipping a coin.
You'd get no information.
Now, you might say, wait a minute.
What about classifiers that get worse than 50-50?
What about them?
Might not they be even worse than a 50-50 classifier?
I claim a classifier that gets less than 50-50
is still better than a classifier that
gets exactly a 50-50 split.
Is there a question?
AUDIENCE: Yeah.
In the ID tree example, somebody said you used 50-50 classifiers
and played around.
And after you already produced the elements per set,
then you only used 50-50 classifiers [INAUDIBLE]
per set.
PROFESSOR: So the question is, in the ID tree example,
you might use 50-50 classifiers in later rounds
if, for instance, there's a 50-50 classifier
except for that most of the things off of that side
have been already removed.
Let's say there's 20 data points,
and there's a classifier that splits it 10 and 10.
And it gets half plus half minus on both sides.
But all the pluses from the right side
have been removed by some other classifier.
You might use it.
That's true.
But in boosting, you will never use something
that's a 50-50 classifier.
You never use something that has exactly a 50-50 chance
of being correct.
Because if it has a 50-50 chance of being correct, it's useless.
And if it has a 50-50 chance of-- no, sorry.
Let me specify again.
You'll never use something that has
a 50-50 chance of giving you the right answer given the weights.
That's very, very important.
And that may be what your question was getting at.
As I'm about to show you and as Patrick told you
in the lecture, in later rounds of boosting,
you change the weights of each of the 10 data points.
At first, you start with all weights being 1/10.
The weights have add up to 1.
In this case, you never, ever choose
a classifier that gets five of them right and five of them
wrong.
In the later rounds, you'll never, ever
choose a classifier that gets half of the weight
wrong-- exactly half of the weight wrong.
But half of the weight may not be half of the data points.
So it's possible to choose a classifier that
gets half of the data points wrong if it doesn't
get half of the weight wrong.
And that's similar to an ID tree when you've already
gotten things right before.
Because you'll see that the weight is going to go
to the ones you got wrong.
So I'm not saying that you should throw out
right away anything that gets five of the points wrong.
Hell, you shouldn't even throw out right away something that
gets seven of the points wrong.
It's possible-- possible-- that you can get seven of the points
wrong, or getting less than half of the weight
wrong if those other three points are really, really
annoying to get right.
And we'll see that later on.
But for insight, at every step along the way,
we're willing to choose any classifier that
doesn't get 50-50.
However, we want to choose the classifier that gets
the most of the weight right.
By most of the weight, at first, we
mean most of the points right.
Later, we will mean exactly what I said-- most of the weight.
And if you don't understand that, it's sometimes
hard to get it right away when Patrick just
lectures through it, introduces a new concept.
If you don't understand that, you'll
see what I mean when we go through, all right?
So my point I was making before is, what about things
that get less than half of the weight right?
Well, those are always OK because you can just flip them
around, use their inverse, and that gets more than half
of the weight right.
It's sort of like-- yeah, it's sort
of like my girlfriend always tells me
that she is more than 50% likely to choose the wrong direction
when you're trying to go between two places, which
I'm kind of skeptical of.
But I said, if that's really true,
then we can just go wherever you didn't say to go,
and we'll be more likely to go the right way.
So you're actually really good at finding the place
that we want to go.
And then she's like, no, that won't work.
Because then I'll know that you're going to do that,
and I'll double say the wrong way.
And then you'll go the wrong way again.
But that not withstanding, you can see you
can apply the same concept to boosting.
And that's why underneath of this,
I have all the opposite versions of all these tests.
So what should we be doing to solve this problem more
quickly?
First, let's figure out which data points are misclassified
by each of these classifiers.
In other words, if we say all the evil things are vampires
and all the non-evil things are not vampires,
what do we get wrong?
And if we do that for every classifier,
then that'll make it faster later on.
Because later on, we're going to go through classifiers,
and we're going to have to add up the ones they got wrong.
So this chart over here is going to be extremely useful.
And on the test that this appeared in,
they even made you fill it in to help yourself out.
So let's see.
If we said that all the evil equals yes are vampires
and all the evil equals no are not vampires,
then-- I'll do the first one for you.
So we get all of the non-vampires
correct because they are all evil equals no.
But unfortunately, we get Angel, Edward Cullen, Saya Otonashi,
and Lestat de Lioncourt wrong because they are vampires,
and they're evil equals no.
Apparently, Lestat is iffy.
But I never read those books, and the Wikipedia article
said that in the end, he wasn't that evil.
So there we go.
Evil equals yes misclassifies 2, 3, 4, and 5.
All right, so let's try emo equals yes.
I'll have someone else do it.
So let's see if you guys got it.
So if we say that all the emo people are vampires
and all the non-emo people are not vampires,
what do we get wrong?
AUDIENCE: 1, 6, 7, 9.
PROFESSOR: 1, 6, 7, 9-- that's exactly right, and fast.
Good.
We get 1, 6, 7, and 9 wrong.
1, 6, and 7 are wrong because they are not emo,
but they're vampires.
9 is wrong because Squall is emo, and he is not a vampire.
Good.
OK, what if we said that exactly the transforming characters are
vampires and the ones that do not transform are not vampires?
Which ones will we get wrong?
AUDIENCE: [INAUDIBLE].
PROFESSOR: Transforms is the next one over.
AUDIENCE: All of the ones [INAUDIBLE].
PROFESSOR: So which ones would we
get wrong if we said that said transforms yes were vampires
and transforms no were not vampires?
AUDIENCE: We'd get 8 wrong.
PROFESSOR: We'd definitely 8 wrong
because she's not a vampire.
AUDIENCE: [INAUDIBLE].
PROFESSOR: Well, no.
It's actually on there.
AUDIENCE: And 3 and 4 we'd also get wrong.
PROFESSOR: Yep.
AUDIENCE: As well as 5.
PROFESSOR: Yes, exactly.
OK.
Oh, man.
You didn't see the chart.
You were just like, hmmm.
You saw the left.
You just said, hm, which one of these
are the transforming characters?
OK, that's pretty hardcore.
AUDIENCE: [LAUGHTER].
PROFESSOR: But yeah, 3, 4, 5, and 8.
No, no, it's definitely given to you.
That would be like the worst test
ever for international students.
Ah, if you don't know these ten characters as vampires,
you lose.
All right, so what about that sparkly
equals yes is a vampire, and if it's not sparkly,
it's not a vampire?
This is guaranteed not to go well.
What do you think it's going to get wrong?
AUDIENCE: For sparkly?
PROFESSOR: Yeah, sparkly equals yes are the only vampires.
AUDIENCE: [INAUDIBLE] wrong.
Angel's going to be wrong.
Saya-- so 1, 2, 4, 5, 6, 7, and 8.
PROFESSOR: And 8-- yes, that's right.
It gets 1, 2, 4, 5, 6, 7, and 8 wrong.
That's pretty awful.
But dammit, it gets Edward Cullen right.
And he's hard to get correct due to the fact
that he's not very much like a vampire.
He's more of a superhero who says he's a vampire.
OK, so next, number of romantic interest greater than two.
So if they have more than two romantic interest,
they're a vampire.
And otherwise, they're not a vampire.
So which ones would that get wrong?
Hm?
AUDIENCE: 3 and 10.
PROFESSOR: Just 3 and 10, that's right.
Because Circe had Odysseus.
She had Telemachus.
Actually, she had that guy she turned into a woodpecker.
She had that other guy who was a sea god who
caused her to turn Scylla into the nine-headed thing,
and probably at least one other person.
So Circe it gets wrong.
And it also gets Edward Cullen wrong because he only has one.
So 3 and 10.
You can tell I thought about this problem
when I was writing it up.
I wrote this one.
All right, number of romantic interest greater than four.
So it's a little bit different this time.
Now you have to have at least four romantic interests--
or actually, greater than four, but there
are none that are exactly four-- to be classified as a vampire.
Which ones do you think it's going to get wrong?
AUDIENCE: 3, 4, 10.
PROFESSOR: Yup, it is going to get 3, 4, and 10 wrong.
Because now, you run into the fact
that Saya has that blond [INAUDIBLE] guy, Haji, and Kai.
So the last of the positive ones-- because I claim I
can derive all the negative ones if you guys give me
the positive ones.
The last of the positive ones is everybody's a vampire.
Who does that get wrong?
AUDIENCE: 8, 9, 10.
PROFESSOR: Yes, OK.
Now, I can derive all the negative ones
from this without a sweat.
Evil equals no-- well, it's 1, 6, 7, 8, 9, 10
without looking at the chart.
Raise your hand if you see why it's 1, 6, 7, 8, 9, 10
without looking at the chart.
Raise your hand if you don't.
Nobody, OK-- wait.
One hand.
OK, I saw another one back there too later.
They were just more tentative.
OK, it's the complement of A because A is
evil equals yes is a vampire.
It gets 2, 3, 4, and 5 wrong.
So therefore, evil equals no is a vampire is guaranteed
to get all the opposite ones.
AUDIENCE: Oh, we could have looked at that too?
PROFESSOR: Yeah, we're looking here,
but we're not looking at the big chart there.
AUDIENCE: You can look at any?
PROFESSOR: Oh, yeah.
If you can't look at anything, then you're
screwed-- unless not only are you as hardcore as this guy,
but you've also memorized the numbers.
All right, so emo equals no is going to be 2, 3, 4, 5, 8, 10.
Transforms equals no is 1, 2, 6, 7, 9, 10.
Sparkle equals no is 3, 9, 10.
Romantic interest less than two is everything except 3 and 10--
1, 2, 4, 5, 6, 7, 8, 9.
1, 2, 5, 6, 7, 8, 9.
And then finally, everything but 8, 9, and 10, so 1, 2, 3, 4, 5,
6, 7.
All right, so when we started off,
we know what everything gets wrong.
I then make a bold claim, because there
are n of these, which is 14.
I make the claim that there are only six
that, in your wildest dreams, you would ever possibly
even consider using ever.
And the rest, you would never, ever use.
Question?
AUDIENCE: Yeah, I just have a question about the number
of romantic interests.
PROFESSOR: Yes.
AUDIENCE: You negated it without an equals on either side.
PROFESSOR: That's true.
That works only because there are [INAUDIBLE] 2 or 4.
But it should have been negated with a less than or equal.
I'm copying off of the quiz.
But yes.
I noticed that this morning when I was putting myself
through my pace.
I'm like, there's not a less than or equal to.
Wait a minute.
And then, oh, wait.
It doesn't have any 2's or 4's.
Actually, I don't remember writing them all
as 5's and 3's.
It's possible that somebody else in the post-editing process
changed them all to be about the same number,
and then changed the less than or equal tos
to be less confusing.
It's possible I had Circe at 4, and there was an equal
to somewhere.
And they were like, forget it.
Because I can't think of the fifth romantic interest
for her.
So yes, normally, you would have to negate it
with an equal to sign, but there happened
to not be any things that are equal to 4 or 2 here.
So they get away with it this time.
But it's good practice.
So I'm claiming that in our wildest dreams,
we'd only ever want to use six of these ever.
And the other eight, forget it.
So let's see.
I will call on people at random to-- the first people obviously
are getting it really easy-- to tell me
which of these you think that you might ever want to use.
Give me one you might ever want to use.
AUDIENCE: E.
PROFESSOR: Why, E?
Of course.
That's the best one.
Yes, that's one that you might ever want to use.
I'll circle the ones that you might ever want to use.
E-- it only gets 3 and 10 wrong.
That's amazing.
It's like the best class of [INAUDIBLE].
OK, so give me another one that you might ever want to us.
AUDIENCE: F.
PROFESSOR: F. Let's see.
F-- F is great.
It only gets three wrong.
Do people agree that you would ever want to use F?
AUDIENCE: No.
PROFESSOR: Everyone's saying no.
Why not?
AUDIENCE: It's like E, except worse.
PROFESSOR: It's like E, except worse.
It's guaranteed at every step, no matter
what the weights are, to have a worse accuracy than E.
It is definitely good.
If E wasn't around, it would be one of our best classifiers
of all.
But actually, F is not one of the six.
This is why I had them write on the test that there were six,
because people might not have found all six.
Because people who did figure out not to include F
might not have figured out to include some of the ones
you want to include.
So--
AUDIENCE: I don't understand why you can't use F.
PROFESSOR: Why you can't use F, OK.
So we start off with 1/10 weight for all our data points.
But let's say during our time of boosting
that all ten of the data points have now different weights.
So we'll call whatever the weight of 3
is, which you're going to get wrong-- you want
to minimize the error, right?
So that weight of 3, which goes into the error of the E, is x.
The weight of 10 can be y.
So if you're thinking of choosing 3,
you know you're-- oh, sorry.
If you're thinking of choosing E, your error is x plus y.
AUDIENCE: Sure.
PROFESSOR: If you're thinking of choosing F,
your error is x plus y plus z, where z is the error of 4.
And since you're never going to have a negative weight,
x plus y plus z is always greater than x plus y.
AUDIENCE: You can't choose something
without the 3 and the 10 anymore because you already chose E.
PROFESSOR: That's-- yes, you would probably choose something
that didn't get the three and the ten wrong.
But you would certainly never choose F ever
because it's always worse than E. In fact, this is exactly
the process that will allow you to find the correct six.
And by "will," I mean "can."
And by "can," I mean, let's see if you guys get it.
Give me another one of the six that you might keep.
AUDIENCE: K.
PROFESSOR: K is the claim-- sparkly.
K, I'm going to say will lose for the same reason
as F. It's 3, 9, and 10.
It's essentially similar to 3, 4, and 10.
So-- oh, by the way, we should not
be only going for the ones with the fewest incorrect.
You need to be going for ones that do not have something
that is strictly better.
In this case, 3 and 10 wrong is strictly
better than getting 3, 9, and 10 wrong.
Question?
AUDIENCE: Oh, I was going to say transform.
PROFESSOR: You were going to say transform.
You are going to be correct.
Transforms is one of the ones we need, C. 3, 4, 5
and 8-- there's nothing down here that gets fewer
than those wrong.
There's nothing that gets us 3, 4, 5 wrong, for instance.
Yeah, there's no way to get 3, 4 wrong without getting either
10 wrong, or 5 and 8 wrong.
AUDIENCE: So why is the 8 like that?
PROFESSOR: What?
AUDIENCE: Why not G?
PROFESSOR: Why not G?
Why not?
Why not G?
Let's include G, too.
AUDIENCE: Oh.
We don't have to do it all?
PROFESSOR: We need six.
No, I just said give me any, and someone gave me
the easiest one, E. Question?
AUDIE
…