So in order to come to
the Information Gain we first we
need to define the concept of Entropy.
An Entropy,
the way we can think about it is called,
what is the smallest possible
number of bits, on average,
that we have to transmit or enc,
symbol to encode, such that.
Such that if we get a symbol that is
drawn from the distribution of X.
Right, so the idea is,
in some sense, how much noises, or
how much bubbly, is the distribution X?
So the idea is,
how do we measure the entropy?
We say the entropy of a given
distribution X is simply
minus summation of all the possible
values this distribution takes.
The probability of it taking
the jth value log the, again,
the probability of taking the jth value.
And the intuition is very simple, right.
If I have a distribution
that has high entropy,
this means that the probability
distribution of X is uniform, right.
In some sense, it's boring,
it's like everything is flat,
everything has the same probability.
So if I would create a histogram.
The histogram of this distribution would
be just right into this kind of flat line.
For example, the distributions of low
entropy they, they are interesting.
They have many peaks, right.
So the idea here is that if I plot
the histogram of a distribution with low
entropy, this distribution would have a
high peak and the rest would be very low.
Right, so in some sense,
if our distribution has very high entropy,
it's very hard to guess the value of X.
And if our distribution
has very low entropy,
then it's very easy to guess
what's the value of X.
So, for example,
here at the bottom, imagine I have
a distribution of dots on the plane.
For example, here on the,
on the right where I have these dots kind
of uniformly spread throughout this space.
This is the condition of high entropy
because for me it's very hard to guess
where the dots are, but in, in the case on
the left where I have all the dots in one
part of the space, it's very easy for
me to guess a location of a dot, right?
So if this is the case,
of the low entropy.
So basically the idea is that entropy
measures, entropy measure tells us
how uniform or how spread out or
how boring is a given distribution?
And if the entropy is low,
then the distribution is very peaked,
kind of it always takes the same value.
So the distributions that have low entropy
are very, in some sense, easy to guess.
Right?
So,
now that we have the concept of entropy
let me, let me give you an example.
So, imagine that I want to predict value,
value Y but I'm given input X.
In particular imagine that
X is the College Major, and
Y is whether the person Likes Gladiator or
not.
Right?
So my data is a set of X,Y first where X
is the major.
Y is better the person
like the gladiator or not.
So now I could start asking okay,
what are some entropies in this case?
For example imagine that I want to ask,
what is the entropy of Y?
Right, computing the entropy of Y is,
is easy, my Y takes two values yes or no.
So first I need to ask, what is
the probability of Y taking the value yes?
Then, I need to say if this is one half,
so four out of eight cases is yes,
so it's one high.
Time, 1/2 times log base2 1/2.
And then I also need to say
how often does the val,
the value Y take the the other value,
don't know value, so it's 1 minus 1.5 in
this case, so it's another 1/2
times log base 2 of 1 half.
So overall, the entropy of of Y is 1/2.
In a similar way I could also go and
compute the entropy of X.
X here takes three different values,
right?
Math, History, CS and that's it.
So now here I would say what fraction of
times does, does the X take value of Math?
Take those probabilities
multiplied with the log.
How, what fraction of times does this,
does it take value CS and
what fraction of times does
it take a value of history?
So that's the idea of how we compute
entropies on a given data set.
So now that I discussed,
how do we compute to the entropy?
Now we can introduce the, the concept
of specific conditional entropy.
So the idea here, the way we write
this is the following we say.
What is the entropy of Y given
X takes a particular value v.
So this is the entropy of Y, among only
those records for which X has value v.
Right?
So in, in, for
example, if I can ask what's the entropy
of Y, given that X takes the value Math?
So what would this mean is,
I only go select the roles for
which X takes value Math.
I see that half of them have value yes,
and half of them have value no.
So using the same calculation as we just
did on the previous slide, the value is 1.
For example, I can ask, what's the entropy
of Y given that X is majored in history.
So I'm taking all the history entries,
here they are, both of them have value no.
So the, this is a completely
boring distribution, right.
Everything is the same all the time,
so historians don't like
Gladiator, which I can kind of conclude
based on this small, small example.
similarly, I could also
compute the entropy of Y, so
whether somebody will like
Gladiator based on whether they.
Majored from Computer Science.
So now this is what we just did is
specific conditional entropy and
the reason why it's called specific,
is because we are conditioning on X
given or taking a particular value v.
We can generalize this concept and call,
and define the conditional entropy.
The way we compute conditional
entropy is very simple.
All we do is we just go over the domain
of a given variable X with saying what is
the probability of X taking this
variable value times the entropy of
Y given X, right?
So this is the entropy of Y given X,
and simply the.
Weighted average specific
condition of entropy of Y,
where weights are the probability or
freshen of times X takes a given value Y.
So, let's look at a simple
example of conditional entropy.
The idea here is to say that
conditional entropy of Y given X,
is the average specific conditional
entropy of Y, we have formula.
So for example if I take my input
data table here on the left,
I can create the,
the conditional entropy table.
Where my goal is to compute what
is entropy of Y given X, so for
every value of X, I need to compute
what is P of X, I have it here.
And then, for every, for
every value of X, I also need to
compute what is the what this the entropy
of Y, for that given value of X.
I get the stable, and
then I just do the weighted summation, and
I would find that the, the entropy of
Y given X, in our case, would be 0.5.
So now that we have kind
of built all the machinery,
we are now ready to talk
about the Information Gain.
An Information Gain,
what it tells us is the following.
It tells us that,
it tells us if we want to transmit Y,
how many bits would we save on
average if both ends would know X?
Right, so the idea is, what is,
is basically the difference
between what is the entropy of Y.
And what is the entropy of Y,
given that we already know X, right?
The bigger the difference,
the more X tells us about Y.
Right, so Y is the, the, our class.
We see what is our entropy of Y,
and then we say,
how much will this entropy decrease
if I go and tell you X ahead of time?
And, for example,
in going back to our, to our case,
to our data table, we already know
the entropy of Y equals 1, we all,
already know the entropy of Y given X
equals .5 so the information gain of Y.
Given X is 0.5.
So basically the idea is that in our
case what we will do is we will for
every feature X sub i,
X sub i, we will go and
compute what is the information
gain of Y given X sub i?
We will then rank our features by the,
by the decreasing information gain.
And we want to pick features,
that have high information gain, right?
That tell us a lot about the value of Y.
So, just to give you an example how to
think about this, imagine we are trying to
predict whether someone is going
to live past 80 years, right?
So we have this prediction
problem where we say,
are you going to live more
than 80 years or not?
And imagine that using
some historical data the,
the information gains we would compute
on it would be something as follows.
If I say probability,
what is the information gain of
long life given hair color,
here the information gain is very low.
Basically, hair color doesn't tell
us much about the probability,
how long is someone going to live?
For example, we see that whether somebody
is smoking, or what is someone's gender.
Tells us much more about how
long somebody is going to leave.
For example, given that Social Security
Numbers in the United States are random,
so how much do, last four digits of
Social Security Number tell us about how
long is somebody going to leave,
it basically, they don't tell us anything.
So the whole idea about information gain
is that it tells us how much information
about the target variable Y is,
is stored or contained in X.
So basically the attribute Y that
has high value of information gain,
is the attribute on which we want to
split when creating a decision tree.
In our case.