Advertisement
English transcript
PATRICK WINSTON: Ladies and gentlemen, the Romanian
national anthem.
I did not ask you to stand, because I didn't play it as a
symbol of Romanian national identity.
But rather, to celebrate the end of the Cold War, which
occurred about the time that you were born.
Before that, no one came to MIT from Eastern Europe.
But since that time, we've been blessed by having in our
midst Lithuanians, Estonians, Poles, Czecs, Slovaks,
Bulgarians, Romanians, Slovenians, Serbs, and all
sorts of people from regions of the world
formally excluded to us.
Believe me, you are all welcome in our house.
Almost all, that is to say.
Because you may recall that Romania is the traditional
home of vampires.
And since the end of the Cold War, vampires have had new
vectors for emerging from their traditional places and
penetrating into the world at large.
You may have vampire in your suite, or on your floor.
And it's important to know how to recognize them, and take
the necessary precautions.
So if you have this concern, I would expect that the first
thing you would do would be to look at some data concerning
the characteristics of vampires.
So there's a little database of samples of individuals who
have been determined to be vampires and not vampires.
And our task today--
and what you'll understand how to do by the end of the hour--
is to use data like this to build a recognition mechanism
that would help you to identify whether someone is a
vampire or an ordinary person.
So this is a little different from the kind of problem we
worked with neural nets.
Right?
So what's the most conspicuous difference between this data
set and anything you could think to work on with nearest
neighbors, which we studied last time.
Katie, do you have any thoughts about why it would be
difficult to use nearest neighbors with data like this?
The question mark is there because this is MIT, and a lot
of people are completely nocturnal.
So you can't tell whether they cast a shadow or not.
We want to take that into account.
So what's different about this from the
electrical cover data set?
STUDENT: [INAUDIBLE]
PATRICK WINSTON: Could you use the nearest neighbor technique
to identify vampires with this data?
STUDENT: [INAUDIBLE]
PATRICK WINSTON: So obviously--
Yes, Lana?
STUDENT: [INAUDIBLE]
STUDENT: You cannot really quantify--
PATRICK WINSTON: Oh, that's the problem.
This is not numerical data.
This is symbolic.
So we're not saying that your ability to
cast a shadow is 0.7.
You either cast a shadow, down cast a
shadow, or we can't tell.
It's a symbolic result.
So problem number one we have to face with data of this kind
is that it's not numeric.
And there are other characteristics, as well.
For example, it's not clear that all of these
characteristics actually matter.
So some characteristics don't matter.
And a corollary to that is that some characteristics do
matter, but they only matter part of the time.
And finally, there's the matter of cost.
Some of these tests may be more expensive to
perform than others.
For example, if you wanted to determine whether someone
casts a shadow, you'd have to go to the trouble of getting
up during daylight.
That might be an expensive operation for you.
You'd have to go find some garlic and ask them to eat it.
That might be expensive.
So some of these tests might be expensive
relative to other tests.
But once you realize that we are talking in terms of tests,
and not a vector of real values, then
what you do is clear.
You build yourself a little tree of tests.
So who knows how this problem will turn out?
But you can imagine a situation where you have one
test up here which might have three outcomes.
And one but only one of those outcomes might require you to
perform another test.
And only when you've created the tree of tests that look
like this are you finished.
So given this set of tests and a set of samples, the question
becomes, how do you arrange the tests in a tree like that
so as to do the identification that you want to do?
So since we're talking about identification, it's not
surprising that this kind of tree is called an
identification tree.
And there's a tendency-- and I may slip into it myself-- to
call this a decision tree.
But a decision tree is a label for something else.
This is an identification tree.
And the task is to create a good one.
So what is a good one versus a not so good one?
What characteristic would you like for a decision tree--
for an identification trade to have, if you're going to call
it good identification tree?
What do you think, Krishna?
What would be a good characteristic?
STUDENT: Maybe the minimum number of levels?
PATRICK WINSTON: Yeah.
He said minimum number of levels.
What's another way you could say what a good one is?
Each test costs something, right?
So what's another way of thinking about what a good
tree would look like?
STUDENT: Minimum cost.
PATRICK WINSTON: The minimum cost.
And if they all have the same cost, then it's
the number of tests.
So overall, what you like is a small tree
rather than a big one.
So you might be able to take your sample data and divide it
up, so that at the bottom of the tree, at the leaves, all
of the sets that are produced by the tests are uniform,
homogeneous.
We'd like that tree to be the simplest possible tree you can
find, not some big complicated one that also divides up all
the data into uniform subsets.
By uniform subset--
at the bottom of the tree, you have all of the vampires
together, and all the non-vampires together.
So you'd like a small tree.
So why not just go all the way and do British Museum, and
calculate all possible trees?
Well, you can do that, but it's one of those NP problems.
And as you know, NP problems suck in general.
And so you don't want to do that.
You want to have some kind of heuristic mechanism for
building a small tree.
And we want a small tree because--
Why do we want a small tree?
Because of the cost.
but there's another, more important reason why we want a
small tree.
Let me give you a hint.
It's Occam's Razor.
The simplest explanation is often the best explanation.
So if you have a big, complicated explanation,
that's probably less good than a simple, small explanation.
Occam's Razor.
Spelled so many ways it doesn't matter how I spell it.
And that's good, because I can't spell.
So how are we going to go about finding the best
possible arrangement of those four tests
in a tree like that?
Well, step one will be to see what each test
does with the data.
And by the way, before I go a step further, you know and I
know that this is a sample data set that's very small,
suitable for classroom manipulation.
You'd never bet your life on a data set this small.
We use it only for classroom illustration.
But imagine that these rows are multiplied by 10.
So instead of eight samples, you've got 80.
Then you might begin to believe the
results that are produced.
So I'm just going to pretend that each one of those
represents 10 other samples that I
haven't bothered to show.
But we can work with this one in the classroom, because it's
pretty small.
And we can say, well, what does this shadow test do?
Well, the shadow test divides the sample population into
three groups.
There's the I Don't Know group of people who are nocturnal.
There are the people who do cast the
shadow, the Yes people.
And the people who do not cast a shadow, the No people.
So if I look at those rows up there and see which ones are
vampires, it looks to me that if there's no shadow cast--
there's only one that doesn't cast a shadow--
and that is a vampire.
So that's a plus over there.
Vampire.
Now, if we look at the ones who do cast a shadow, all
those are not vampires.
They're all OK.
And now there're 8.
Three are vampires.
So that means that two of these must be vampires.
And I've got three, four, five, six so far.
So there must be two left.
So that's the way the shadow test divides up the data.
Now let's do garlic.
Vampires traditionally don't eat garlic.
I don't know why.
So we look at the garlic test, and we see
that all of the Nos--
well, there're three Yeses, and they all
produce a No answer.
So if somebody eats garlic, they're not vampires.
That means the three vampires must be over here.
Then there are two left.
So that's what the garlic test does.
See what we're trying to do?
We're trying to look at all these tests to see which one
we like best on the basis of how it divides up the data.
So now we've got complexion.
And there are three choices for this.
You can have an average complexion.
But a lot of vampires, in my experience, are rather pale.
So pale is a possibility.
And then the other option is that just after gorging
themselves with blood, they tend to get a
little red in the face.
So we'll have a ruddy over here.
Once again, we have to go back to our data set to see how
this test divides things up.
So there are three ruddies, and one's a No, one's a No,
and one's a Yes.
So two Nos and a Yes.
Two Nos and a Yes.
Now we can try for pale complexion people.
There are only two of those.
A No and a No.
That must mean that there are two pluses over here, because
there are three vampires altogether.
Two, four, six, seven, eight, nine.
Eight, sorry.
Eight.
Only eight.
Just one more to go, and that's the accent.
Historically, vampires go to great length to protect their
accent and not betray their origins.
But nevertheless, we can expect that if
they've just arrived--
if they're just in from
Transylvania, part of Romania--
they may still have an accent.
So there's a normal, some still have a heavy accent, and
some persist in having odd accents.
So let's see.
Accent.
Four of them, right at the top, have no accent.
Two Nos and a Yes.
Heavy accent.
Three of those.
A Yes and two Nos.
That means we must have a plus here.
3, 6, plus and a minus.
So we can look at this data and say, well, what will be
the best test to use?
And the best test to use would surely be the one that
produces sets here, at the bottom of the branches, that
correspond to the outcomes of the test.
We're looking for a test that produces homogeneous groups.
So just for the sake of illustration, I'm going to
suppose that we're going to judge the quality of the test
by how many sample individuals it put into a homogeneous set.
So ideally, we'd like a test that will put all the vampires
in one group and all the ordinary people in another
group right off the bat.
But there are no such tests.
But we can add up the number of sample individuals who are
put in to at least homogeneous sets.
So when we do that, this guy has 3 in a
homogeneous set here.
A fourth.
But these are not a homogeneous set.
So the overall score for this guy will be 4.
This one, well, not quite as good.
It only puts 3 individuals in a homogeneous set.
This one here, 2 individuals into a homogeneous set.
Everybody else is all mixed up with some
other kind of person.
And over here, how many samples are in
a homogeneous set?
0.
So on the basis of this analysis, you would conclude
that the ordering of the test with respect to their quality
is left to right.
So the best test must be the shadow test.
So let's pick the shadow test first, see what
we can do with that.
If we pick the shadow test first, then we have this
arrangement.
We have question mark, and we have Yes, casts a shadow, and
No, doesn't.
We have 3 minuses here.
We have a plus here.
And unfortunately, over here, we have plus,
plus, minus, minus.
So we need another test to divide that group up.
Yes.
STUDENT: How did you get the 4 on the shadow test again?
Why was it 4?
PATRICK WINSTON: Well, if I look at the
data and I see who--
the question is, what about that shadow test?
If you look at the shadow test, and you say, well, there
are 4 question marks.
And if we look and see what kind of people belong to those
4 question marks, there are 2 vampires and 2 non-vampires.
That's why it's 2 pluses and 2 minuses.
STUDENT: No, I understand that.
The question is, how did you get to the score of 4?
PATRICK WINSTON: Oh, yeah.
The question is how did I get this number 4?
It has nothing to do this, because this is a mixed set.
In fact, I've got three guys in a homogeneous set here, and
one guy in a homogeneous set here, and I'm
just adding them up.
STUDENT: OK.
PATRICK WINSTON: So very simple classroom illustration.
Wouldn't work in practice.
Yes.
STUDENT: How do you adjust this for larger data sets
where it's unlikely you're going to have any [INAUDIBLE]?
PATRICK WINSTON: The question is, how do I adjust this for
larger data sets?
You're one step ahead.
Trust me, I'll be doing large data sets in a moment.
I just want to get the idea across.
And I don't want there to be any thought that the method we
use for larger data sets has got anything magic about it.
OK, so we're off and running.
And now we have to pick a test that will divide
those four guys up.
So we're going to have to work this a little harder, and
repeat the analysis we did there.
But at least it'll be simpler, because now we're only
considering 4 samples, not 8.
Just the 4 samples that we still have to divide up that
have come down that left branch.
So I have the shadow test.
It has 3 outcomes.
We have the garlic test.
It has 2 outcomes.
Yes and No.
We have the complexion test.
There's 3 outcomes.
Average, pale, and ruddy.
And we have finally the accent test.
And that comes out to be either normal, heavy, or odd.
And now, it's a little awkward to figure out what the results
are for this data set as shown.
So let me just strike out.
The ones that we're no longer concerned with, and limit our
analysis to the samples for which the outcome of the
shadow test is a question mark.
This is exactly the four people we still need to
separate, right?
So switching colors, keeping the color the same.
We actually don't want to do the shadow
test anymore, right?
Because we've already done that.
There's no point in doing that again.
We don't have to look at that.
It's already done all the division of data that it can.
So the garlic test.
Well, let's see.
Garlic.
2 Yeses, 2 Nos.
The Yeses produce Nos and the Nos produce Yeses.
So if the person does eat garlic, they're OK.
And if they don't eat garlic, bad news-- they're vampires.
Well, that looks like a pretty good test.
But just for the sake of working it all out, let's try
the others.
Complexion.
2 Ruddies, a Yes, and a No.
1 pale, and that's a No.
And we must have 1 average, and sure enough, that's a Yes.
Now we can do accent, the one on the far right, and look at
how that measures up against the people who are still under
consideration as samples.
Accent.
Let's see.
2 Nones, a Yes and a No.
No Heavies.
2 Odds, a Yes and a No.
All right.
So now we can do the same thing we did before, and just
say, for sake of classroom illustration, how many
individuals are put into a homogeneous sets.
And here we have 4.
And here we have 2.
And here we have 0.
So plainly, the garlic test is the test of choice.
So we go back over here, and we've completed the work that
we needed to do.
So that's the garlic test.
And that produces 2 pluses.
Let's see.
Eats garlic, Yes.
Eats garlic, No.
I guess the pluses go over here like so.
And these are the two ordinary people.
And we're done with our task.
And now you can quickly run off and put this into your
PDA, and forever be protected against the possibility that
one of those vampires got out in the flood of people that
came in from Eastern Europe.
Except what do we do a large data set?
Well, the trouble is, a large data set's
not likely to produce--
if you have a large data set, no test is likely to put
together any homogeneous set right off.
So you never get started.
Everything would be 0.
Every test would say, oh it doesn't put anybody into
homogeneous sets.
So you're screwed.
You need some other, more sophisticated way of measuring
how disordered this data is.
Or how disordered these sets are that you find at the
bottom of the tree branches.
That's what you need.
You need a way of measuring disorder of these sets that
you find at the bottom of these branches, so you can
find a kind of overall quality to the test based on your
measurement of disorder.
Now, the first heuristic of a good life is, when you have a
problem to solve, ask somebody who knows the answer.
It's the least amount of work.
It's not even as hard going to Google.
So who would you ask about ways of
measuring disorder in sets?
There are two possible answers.
STUDENT: You could just do entropy.
PATRICK WINSTON: What?
STUDENT: Find the entropy of the set.
PATRICK WINSTON: Who studies entropy?
STUDENT: Probability.
PATRICK WINSTON: What kind of classes?
STUDENT: Physics.
STUDENT: Thermodynamics.
PATRICK WINSTON: Thermodynamics!
The thermodynamicists are good at measuring disorder, because
that's what thermodynamics is all about.
Entropy increasing over time, and all that sort of stuff.
There's another equally good answer.
STUDENT: Statisticians?
PATRICK WINSTON: Statisticians.
Perhaps, but it's not the second best answer.
It's actually not even the best answer.
That's the best answer.
What's your name?
STUDENT: Leo.
PATRICK WINSTON: Oh, yeah.
[LAUGHTER]
PATRICK WINSTON: Leonardo has got his finger on it.
The information theorists are pretty good at measuring
disorder, because that's what information is all about, too.
So we might as well borrow a mechanism for measuring the
disorder of a set from those information theory guys.
So what we're going to do is exactly that.
Let's put it over here, so we'll have it handy when we
want to try to measure those things.
The gospel according to information theorists is that
the disorder, D, or some set is equal to-- now let's
suppose that this is a set of binary values.
So we have positives and then we have negatives.
Pluses and minuses.
But pluses, they don't go very well in an algebraic equation,
because they might be confused with adding.
So I'm going to say P and N. And then it'll be the total,
which is P plus N. We only have two choices,
positive and negative.
So the disorder of set, according those guys, is equal
to minus the number of positives over the total
number, times the log to the base 2 of the positives over
the total, minus the negatives over the total, times the log
2 of the negatives over the total.
Those negatives look a little worrisome, because you think,
well, maybe this thing can go negative.
But that's not going to be true, right?
Because these ratios are all less than 1, and the logarithm
of something that's less than 1 is negative.
So we're OK.
So that's a lovely way of measuring disorder.
And then we ought to draw a graph of what
that curve looks like.
And what we're going to graph it against is the ratio of
positives to the total number.
So that's going to be an axis where we go from 0 to 1.
So let's just find a couple of useful values.
And by the way, it pays to pay attention to these curves,
because if you pay attention to this stuff, you can work
the quiz questions on this very rapidly.
Otherwise, we see people getting out their calculators
and quickly becoming both lost and screwed.
OK so let's see.
Let's suppose that the number of positives is equal to the
number of negatives.
So we've got a completely mixed-up set.
It has no bias in either direction.
So in that case, if P over T is equal to 1/2, then this is
equal to minus 1/2, times the logarithm of 1/2.
And I guess, since they're both the same, we
can multiply by two.
And what's that value?
[INAUDIBLE], what does that calculate out to?
STUDENT: Minus [INAUDIBLE]
PATRICK WINSTON: Minus [INAUDIBLE].
Well, with a minus sign, you just turn the argument upside
down, so it's log(2).
So what's log(2)?
Logarithm of base 2 of 2?
1!
So this whole thing is--
STUDENT: 1.
PATRICK WINSTON: 1.
So [INAUDIBLE], in her soft way, says, well, let's see.
2 times 1/2.
That cancels out.
The minus, that flips the arguments so it's log to the
base 2 of 2, and that's 1.
So this whole thing, You work out the algebra,
it gives you 1.
So that's cool.
So right here in the middle where they're equal, we
…
national anthem.
I did not ask you to stand, because I didn't play it as a
symbol of Romanian national identity.
But rather, to celebrate the end of the Cold War, which
occurred about the time that you were born.
Before that, no one came to MIT from Eastern Europe.
But since that time, we've been blessed by having in our
midst Lithuanians, Estonians, Poles, Czecs, Slovaks,
Bulgarians, Romanians, Slovenians, Serbs, and all
sorts of people from regions of the world
formally excluded to us.
Believe me, you are all welcome in our house.
Almost all, that is to say.
Because you may recall that Romania is the traditional
home of vampires.
And since the end of the Cold War, vampires have had new
vectors for emerging from their traditional places and
penetrating into the world at large.
You may have vampire in your suite, or on your floor.
And it's important to know how to recognize them, and take
the necessary precautions.
So if you have this concern, I would expect that the first
thing you would do would be to look at some data concerning
the characteristics of vampires.
So there's a little database of samples of individuals who
have been determined to be vampires and not vampires.
And our task today--
and what you'll understand how to do by the end of the hour--
is to use data like this to build a recognition mechanism
that would help you to identify whether someone is a
vampire or an ordinary person.
So this is a little different from the kind of problem we
worked with neural nets.
Right?
So what's the most conspicuous difference between this data
set and anything you could think to work on with nearest
neighbors, which we studied last time.
Katie, do you have any thoughts about why it would be
difficult to use nearest neighbors with data like this?
The question mark is there because this is MIT, and a lot
of people are completely nocturnal.
So you can't tell whether they cast a shadow or not.
We want to take that into account.
So what's different about this from the
electrical cover data set?
STUDENT: [INAUDIBLE]
PATRICK WINSTON: Could you use the nearest neighbor technique
to identify vampires with this data?
STUDENT: [INAUDIBLE]
PATRICK WINSTON: So obviously--
Yes, Lana?
STUDENT: [INAUDIBLE]
STUDENT: You cannot really quantify--
PATRICK WINSTON: Oh, that's the problem.
This is not numerical data.
This is symbolic.
So we're not saying that your ability to
cast a shadow is 0.7.
You either cast a shadow, down cast a
shadow, or we can't tell.
It's a symbolic result.
So problem number one we have to face with data of this kind
is that it's not numeric.
And there are other characteristics, as well.
For example, it's not clear that all of these
characteristics actually matter.
So some characteristics don't matter.
And a corollary to that is that some characteristics do
matter, but they only matter part of the time.
And finally, there's the matter of cost.
Some of these tests may be more expensive to
perform than others.
For example, if you wanted to determine whether someone
casts a shadow, you'd have to go to the trouble of getting
up during daylight.
That might be an expensive operation for you.
You'd have to go find some garlic and ask them to eat it.
That might be expensive.
So some of these tests might be expensive
relative to other tests.
But once you realize that we are talking in terms of tests,
and not a vector of real values, then
what you do is clear.
You build yourself a little tree of tests.
So who knows how this problem will turn out?
But you can imagine a situation where you have one
test up here which might have three outcomes.
And one but only one of those outcomes might require you to
perform another test.
And only when you've created the tree of tests that look
like this are you finished.
So given this set of tests and a set of samples, the question
becomes, how do you arrange the tests in a tree like that
so as to do the identification that you want to do?
So since we're talking about identification, it's not
surprising that this kind of tree is called an
identification tree.
And there's a tendency-- and I may slip into it myself-- to
call this a decision tree.
But a decision tree is a label for something else.
This is an identification tree.
And the task is to create a good one.
So what is a good one versus a not so good one?
What characteristic would you like for a decision tree--
for an identification trade to have, if you're going to call
it good identification tree?
What do you think, Krishna?
What would be a good characteristic?
STUDENT: Maybe the minimum number of levels?
PATRICK WINSTON: Yeah.
He said minimum number of levels.
What's another way you could say what a good one is?
Each test costs something, right?
So what's another way of thinking about what a good
tree would look like?
STUDENT: Minimum cost.
PATRICK WINSTON: The minimum cost.
And if they all have the same cost, then it's
the number of tests.
So overall, what you like is a small tree
rather than a big one.
So you might be able to take your sample data and divide it
up, so that at the bottom of the tree, at the leaves, all
of the sets that are produced by the tests are uniform,
homogeneous.
We'd like that tree to be the simplest possible tree you can
find, not some big complicated one that also divides up all
the data into uniform subsets.
By uniform subset--
at the bottom of the tree, you have all of the vampires
together, and all the non-vampires together.
So you'd like a small tree.
So why not just go all the way and do British Museum, and
calculate all possible trees?
Well, you can do that, but it's one of those NP problems.
And as you know, NP problems suck in general.
And so you don't want to do that.
You want to have some kind of heuristic mechanism for
building a small tree.
And we want a small tree because--
Why do we want a small tree?
Because of the cost.
but there's another, more important reason why we want a
small tree.
Let me give you a hint.
It's Occam's Razor.
The simplest explanation is often the best explanation.
So if you have a big, complicated explanation,
that's probably less good than a simple, small explanation.
Occam's Razor.
Spelled so many ways it doesn't matter how I spell it.
And that's good, because I can't spell.
So how are we going to go about finding the best
possible arrangement of those four tests
in a tree like that?
Well, step one will be to see what each test
does with the data.
And by the way, before I go a step further, you know and I
know that this is a sample data set that's very small,
suitable for classroom manipulation.
You'd never bet your life on a data set this small.
We use it only for classroom illustration.
But imagine that these rows are multiplied by 10.
So instead of eight samples, you've got 80.
Then you might begin to believe the
results that are produced.
So I'm just going to pretend that each one of those
represents 10 other samples that I
haven't bothered to show.
But we can work with this one in the classroom, because it's
pretty small.
And we can say, well, what does this shadow test do?
Well, the shadow test divides the sample population into
three groups.
There's the I Don't Know group of people who are nocturnal.
There are the people who do cast the
shadow, the Yes people.
And the people who do not cast a shadow, the No people.
So if I look at those rows up there and see which ones are
vampires, it looks to me that if there's no shadow cast--
there's only one that doesn't cast a shadow--
and that is a vampire.
So that's a plus over there.
Vampire.
Now, if we look at the ones who do cast a shadow, all
those are not vampires.
They're all OK.
And now there're 8.
Three are vampires.
So that means that two of these must be vampires.
And I've got three, four, five, six so far.
So there must be two left.
So that's the way the shadow test divides up the data.
Now let's do garlic.
Vampires traditionally don't eat garlic.
I don't know why.
So we look at the garlic test, and we see
that all of the Nos--
well, there're three Yeses, and they all
produce a No answer.
So if somebody eats garlic, they're not vampires.
That means the three vampires must be over here.
Then there are two left.
So that's what the garlic test does.
See what we're trying to do?
We're trying to look at all these tests to see which one
we like best on the basis of how it divides up the data.
So now we've got complexion.
And there are three choices for this.
You can have an average complexion.
But a lot of vampires, in my experience, are rather pale.
So pale is a possibility.
And then the other option is that just after gorging
themselves with blood, they tend to get a
little red in the face.
So we'll have a ruddy over here.
Once again, we have to go back to our data set to see how
this test divides things up.
So there are three ruddies, and one's a No, one's a No,
and one's a Yes.
So two Nos and a Yes.
Two Nos and a Yes.
Now we can try for pale complexion people.
There are only two of those.
A No and a No.
That must mean that there are two pluses over here, because
there are three vampires altogether.
Two, four, six, seven, eight, nine.
Eight, sorry.
Eight.
Only eight.
Just one more to go, and that's the accent.
Historically, vampires go to great length to protect their
accent and not betray their origins.
But nevertheless, we can expect that if
they've just arrived--
if they're just in from
Transylvania, part of Romania--
they may still have an accent.
So there's a normal, some still have a heavy accent, and
some persist in having odd accents.
So let's see.
Accent.
Four of them, right at the top, have no accent.
Two Nos and a Yes.
Heavy accent.
Three of those.
A Yes and two Nos.
That means we must have a plus here.
3, 6, plus and a minus.
So we can look at this data and say, well, what will be
the best test to use?
And the best test to use would surely be the one that
produces sets here, at the bottom of the branches, that
correspond to the outcomes of the test.
We're looking for a test that produces homogeneous groups.
So just for the sake of illustration, I'm going to
suppose that we're going to judge the quality of the test
by how many sample individuals it put into a homogeneous set.
So ideally, we'd like a test that will put all the vampires
in one group and all the ordinary people in another
group right off the bat.
But there are no such tests.
But we can add up the number of sample individuals who are
put in to at least homogeneous sets.
So when we do that, this guy has 3 in a
homogeneous set here.
A fourth.
But these are not a homogeneous set.
So the overall score for this guy will be 4.
This one, well, not quite as good.
It only puts 3 individuals in a homogeneous set.
This one here, 2 individuals into a homogeneous set.
Everybody else is all mixed up with some
other kind of person.
And over here, how many samples are in
a homogeneous set?
0.
So on the basis of this analysis, you would conclude
that the ordering of the test with respect to their quality
is left to right.
So the best test must be the shadow test.
So let's pick the shadow test first, see what
we can do with that.
If we pick the shadow test first, then we have this
arrangement.
We have question mark, and we have Yes, casts a shadow, and
No, doesn't.
We have 3 minuses here.
We have a plus here.
And unfortunately, over here, we have plus,
plus, minus, minus.
So we need another test to divide that group up.
Yes.
STUDENT: How did you get the 4 on the shadow test again?
Why was it 4?
PATRICK WINSTON: Well, if I look at the
data and I see who--
the question is, what about that shadow test?
If you look at the shadow test, and you say, well, there
are 4 question marks.
And if we look and see what kind of people belong to those
4 question marks, there are 2 vampires and 2 non-vampires.
That's why it's 2 pluses and 2 minuses.
STUDENT: No, I understand that.
The question is, how did you get to the score of 4?
PATRICK WINSTON: Oh, yeah.
The question is how did I get this number 4?
It has nothing to do this, because this is a mixed set.
In fact, I've got three guys in a homogeneous set here, and
one guy in a homogeneous set here, and I'm
just adding them up.
STUDENT: OK.
PATRICK WINSTON: So very simple classroom illustration.
Wouldn't work in practice.
Yes.
STUDENT: How do you adjust this for larger data sets
where it's unlikely you're going to have any [INAUDIBLE]?
PATRICK WINSTON: The question is, how do I adjust this for
larger data sets?
You're one step ahead.
Trust me, I'll be doing large data sets in a moment.
I just want to get the idea across.
And I don't want there to be any thought that the method we
use for larger data sets has got anything magic about it.
OK, so we're off and running.
And now we have to pick a test that will divide
those four guys up.
So we're going to have to work this a little harder, and
repeat the analysis we did there.
But at least it'll be simpler, because now we're only
considering 4 samples, not 8.
Just the 4 samples that we still have to divide up that
have come down that left branch.
So I have the shadow test.
It has 3 outcomes.
We have the garlic test.
It has 2 outcomes.
Yes and No.
We have the complexion test.
There's 3 outcomes.
Average, pale, and ruddy.
And we have finally the accent test.
And that comes out to be either normal, heavy, or odd.
And now, it's a little awkward to figure out what the results
are for this data set as shown.
So let me just strike out.
The ones that we're no longer concerned with, and limit our
analysis to the samples for which the outcome of the
shadow test is a question mark.
This is exactly the four people we still need to
separate, right?
So switching colors, keeping the color the same.
We actually don't want to do the shadow
test anymore, right?
Because we've already done that.
There's no point in doing that again.
We don't have to look at that.
It's already done all the division of data that it can.
So the garlic test.
Well, let's see.
Garlic.
2 Yeses, 2 Nos.
The Yeses produce Nos and the Nos produce Yeses.
So if the person does eat garlic, they're OK.
And if they don't eat garlic, bad news-- they're vampires.
Well, that looks like a pretty good test.
But just for the sake of working it all out, let's try
the others.
Complexion.
2 Ruddies, a Yes, and a No.
1 pale, and that's a No.
And we must have 1 average, and sure enough, that's a Yes.
Now we can do accent, the one on the far right, and look at
how that measures up against the people who are still under
consideration as samples.
Accent.
Let's see.
2 Nones, a Yes and a No.
No Heavies.
2 Odds, a Yes and a No.
All right.
So now we can do the same thing we did before, and just
say, for sake of classroom illustration, how many
individuals are put into a homogeneous sets.
And here we have 4.
And here we have 2.
And here we have 0.
So plainly, the garlic test is the test of choice.
So we go back over here, and we've completed the work that
we needed to do.
So that's the garlic test.
And that produces 2 pluses.
Let's see.
Eats garlic, Yes.
Eats garlic, No.
I guess the pluses go over here like so.
And these are the two ordinary people.
And we're done with our task.
And now you can quickly run off and put this into your
PDA, and forever be protected against the possibility that
one of those vampires got out in the flood of people that
came in from Eastern Europe.
Except what do we do a large data set?
Well, the trouble is, a large data set's
not likely to produce--
if you have a large data set, no test is likely to put
together any homogeneous set right off.
So you never get started.
Everything would be 0.
Every test would say, oh it doesn't put anybody into
homogeneous sets.
So you're screwed.
You need some other, more sophisticated way of measuring
how disordered this data is.
Or how disordered these sets are that you find at the
bottom of the tree branches.
That's what you need.
You need a way of measuring disorder of these sets that
you find at the bottom of these branches, so you can
find a kind of overall quality to the test based on your
measurement of disorder.
Now, the first heuristic of a good life is, when you have a
problem to solve, ask somebody who knows the answer.
It's the least amount of work.
It's not even as hard going to Google.
So who would you ask about ways of
measuring disorder in sets?
There are two possible answers.
STUDENT: You could just do entropy.
PATRICK WINSTON: What?
STUDENT: Find the entropy of the set.
PATRICK WINSTON: Who studies entropy?
STUDENT: Probability.
PATRICK WINSTON: What kind of classes?
STUDENT: Physics.
STUDENT: Thermodynamics.
PATRICK WINSTON: Thermodynamics!
The thermodynamicists are good at measuring disorder, because
that's what thermodynamics is all about.
Entropy increasing over time, and all that sort of stuff.
There's another equally good answer.
STUDENT: Statisticians?
PATRICK WINSTON: Statisticians.
Perhaps, but it's not the second best answer.
It's actually not even the best answer.
That's the best answer.
What's your name?
STUDENT: Leo.
PATRICK WINSTON: Oh, yeah.
[LAUGHTER]
PATRICK WINSTON: Leonardo has got his finger on it.
The information theorists are pretty good at measuring
disorder, because that's what information is all about, too.
So we might as well borrow a mechanism for measuring the
disorder of a set from those information theory guys.
So what we're going to do is exactly that.
Let's put it over here, so we'll have it handy when we
want to try to measure those things.
The gospel according to information theorists is that
the disorder, D, or some set is equal to-- now let's
suppose that this is a set of binary values.
So we have positives and then we have negatives.
Pluses and minuses.
But pluses, they don't go very well in an algebraic equation,
because they might be confused with adding.
So I'm going to say P and N. And then it'll be the total,
which is P plus N. We only have two choices,
positive and negative.
So the disorder of set, according those guys, is equal
to minus the number of positives over the total
number, times the log to the base 2 of the positives over
the total, minus the negatives over the total, times the log
2 of the negatives over the total.
Those negatives look a little worrisome, because you think,
well, maybe this thing can go negative.
But that's not going to be true, right?
Because these ratios are all less than 1, and the logarithm
of something that's less than 1 is negative.
So we're OK.
So that's a lovely way of measuring disorder.
And then we ought to draw a graph of what
that curve looks like.
And what we're going to graph it against is the ratio of
positives to the total number.
So that's going to be an axis where we go from 0 to 1.
So let's just find a couple of useful values.
And by the way, it pays to pay attention to these curves,
because if you pay attention to this stuff, you can work
the quiz questions on this very rapidly.
Otherwise, we see people getting out their calculators
and quickly becoming both lost and screwed.
OK so let's see.
Let's suppose that the number of positives is equal to the
number of negatives.
So we've got a completely mixed-up set.
It has no bias in either direction.
So in that case, if P over T is equal to 1/2, then this is
equal to minus 1/2, times the logarithm of 1/2.
And I guess, since they're both the same, we
can multiply by two.
And what's that value?
[INAUDIBLE], what does that calculate out to?
STUDENT: Minus [INAUDIBLE]
PATRICK WINSTON: Minus [INAUDIBLE].
Well, with a minus sign, you just turn the argument upside
down, so it's log(2).
So what's log(2)?
Logarithm of base 2 of 2?
1!
So this whole thing is--
STUDENT: 1.
PATRICK WINSTON: 1.
So [INAUDIBLE], in her soft way, says, well, let's see.
2 times 1/2.
That cancels out.
The minus, that flips the arguments so it's log to the
base 2 of 2, and that's 1.
So this whole thing, You work out the algebra,
it gives you 1.
So that's cool.
So right here in the middle where they're equal, we
…