So now, we have an intuition of best, and how we
want to split. We've, we've looked over, Michael's proposed, the high-level
algorithm for how we would build a decision tree. And I
think we have enough information now that we can actually do,
a real specific algorithm. So, let's write that down. And the
particular algorithm that Michael proposed is a kind of generic version
of something that's called ID3. So let me write down what
that algorithm is, and we can talk about it. Okay, so here's
the ID3 algorithm. You're simply going to keep looping forever until you've
solved the problem. At each step, you're going to pick the best attribute,
and we're going to define what we mean by best. There are
a couple of different ways we might, we might define best in
a moment. And then, given the best attribute that splits the
data the way that we want, it does all those things that
we talked about, assign that as a decision attribute for node.
And then for each value that the attribute A can take on,
create a descendent of node. Sort the training examples
to those leaves based upon exactly what values they
take on, and if you've perfectly classified your training
set, then you stop. Otherwise, you iterate over each
of those leaves, picking the best attribute in turn
for the training examples that were sorted into that
leaf, and you keep doing that. Building up the
tree until you're done. So that's the ID3 algorithm.
And the key bit that we have to expand upon
in this case, is exactly what it means to have a
best attribute. All right so, what is exactly, what exactly
is it that we mean by best attribute? So, there are
lots of possibilities, that you can come up with. The
one that is most common, and the one I want you
to think about the most, is what's called information gain.
So information gain is simply a mathematical way to capture the
amount of information that i want to gain by
picking particular attribute, funnily enough. But what it
really talks about is the reduction in the
randomness, over the labels that you have with
set of data, based upon the knowing the
value of particular attribute. So the formula's simply
this. The information gain over S and A
where S is the collection of training examples
that you're looking at. And A, as
a particular attribute, is simply defined as the
entropy, with respect to the labels, of
the set of training examples, you have S,
minus, sort of, the expected or average
entropy that you would have over each set
of examples that you have with a particular
value. Does that make sense to you, Michael?
>> So what we're doing, we're picking an attribute and
that attribute could have a bunch of different
values, like true or false, or short, medium, tall?
>> Right.
>> And.
>> And that's represented by v.
>> Okay, each of those is a different v. And then we're
saying okay, for over those leaves, we're going to do this entropy thing again.
>> Mm-hm.
>> And we right. So what, and what is entropy?
>> entropy. So, we'll talk about entropy later on in the class
in some detail and define it exactly and mathematically. And
some of you probably already know what, what entropy is,
but for those of you who don't, it's exactly a
measure of randomness. So if I have a coin, let's
say a two-headed coin. It can be heads or tails,
and I don't know anything about the coin except that
it's probably fair. If I were to flip the coin,
what's the probability that it would end up heads versus tails?
>> A half.
>> It's
a half, exactly, if it's a fair coin it's a half.
Which means that I have no basis, going into flipping the coin,
to guess either way whether it's heads or it's tails. And so
that has a lot of entropy. In fact it has exactly what's
called one bit of entropy. On the other hand, let's imagine
that I have a coin that has heads on both sides. Then,
before I even flip the coin, I already know what the outcome's
going to be. It's going to come up heads. So what's the
probability of it coming up with heads? It's.
>> One.
>> One. So that actually has no
information, no randomness, no entropy whatsoever. And has
zero bits of entropy. So, when I look at this set of examples that I
have, and the set of labels I have, I can count the number that are coming up,
let's say, red x's. Versus the ones that are coming up green o's.
And if those are evenly split, then the entropy of them
is maximal, because if I were to close my eyes and
reach for an instance, I have no way of knowing beforehand
whether I'm more likely to get an x or I'm more likely
to get an o. On the other hand, if I have
all the x's in together, then I already know before I even
reach in that I'm going to end up with an x. So
as I have more of one label than the other the amount
of entropy goes down. That is, I have
more information going in. Does that make sense, Michael?
>> I think so. So, is there, can, maybe we
can say what the formula is for this, or, or?
>> Sure. What is the formula for it? You should remember.
>> It's, if we have, well, I'm not sure what the notation ought to be with
these S's but it has something to do with Log P log, no wait, it's P(log)P.
>> Mm-hm. So the
actual formula for entropy, using the same notation that we're
using for information gain is simply the sum, over all
the possible values that you might see, of the probability
of you seeing that value, times the log of the probability
of you seeing that value, times minus one. And I
don't want to get into the details here. We're going to go
into a lot more details about this later when we
get further on in the class with randomize optimization, where entropy's
going to matter a lot. But for now, I just, you
have, I want you to have the intuition that this
is a measure of information. This is the measure of
randomness in some variable that you haven't seen. It's the likelihood
of you already knowing what you're going to get if you
close your eyes and pick one of the training examples, versus
you not knowing what you're going to get. If you close
your eyes and you picked one of the training examples. Okay?
>> Alright. So, well, so, okay, so then in the practice,
trees that you had given us before, it was the
case that we worked, we wanted to prefer splits that I
guess, made things less random, right? So if things were
all mixed together, the reds and the greens, after the split
if it was all reds on one side and all
greens on the other. Then each of those two sides would
have very, what? They would have very low entropy, even though
when we started out before the split we had high entropy.
>> Right, that's exactly right. So if you, if you remember the,
the, three examples before. One of them, it was the case
that all of the samples went down the left side of
the tree. So the amount of entropy that we had, didn't
change at all. So there was no gain in using that attribute.
In another case, we split the data in half. But in
each case, we had half of the x's and half of the
o's together, on both sides of the split. Which means that
the total amount of entropy actually didn't change at all. Even though
we split the data. And in the final case, the best one, we still split
the data in half, but since all of the x's ended up on one side
and all of the o's ended up on the other side, we had to entropy
or no randomness left whatsoever. And that
gave us the maximum amount of information gain.
>> So is that how we're choosing the
best attribute? The one with the maximum gain?
>> Exactly. So the goal is to maximize over the entropy gain.
And that's the best attribute.