1 00:00:00,590 --> 00:00:03,450 So in order to come to the Information Gain we first we 2 00:00:03,450 --> 00:00:05,780 need to define the concept of Entropy. 3 00:00:05,780 --> 00:00:09,290 An Entropy, the way we can think about it is called, 4 00:00:09,290 --> 00:00:13,590 what is the smallest possible number of bits, on average, 5 00:00:13,590 --> 00:00:18,280 that we have to transmit or enc, symbol to encode, such that. 6 00:00:18,280 --> 00:00:23,290 Such that if we get a symbol that is drawn from the distribution of X. 7 00:00:23,290 --> 00:00:24,350 Right, so the idea is, 8 00:00:24,350 --> 00:00:29,440 in some sense, how much noises, or how much bubbly, is the distribution X? 9 00:00:29,440 --> 00:00:32,290 So the idea is, how do we measure the entropy? 10 00:00:32,290 --> 00:00:36,720 We say the entropy of a given distribution X is simply 11 00:00:36,720 --> 00:00:41,220 minus summation of all the possible values this distribution takes. 12 00:00:41,220 --> 00:00:45,400 The probability of it taking the jth value log the, again, 13 00:00:45,400 --> 00:00:47,670 the probability of taking the jth value. 14 00:00:47,670 --> 00:00:49,300 And the intuition is very simple, right. 15 00:00:49,300 --> 00:00:52,850 If I have a distribution that has high entropy, 16 00:00:52,850 --> 00:00:56,910 this means that the probability distribution of X is uniform, right. 17 00:00:56,910 --> 00:01:00,430 In some sense, it's boring, it's like everything is flat, 18 00:01:00,430 --> 00:01:02,100 everything has the same probability. 19 00:01:02,100 --> 00:01:04,050 So if I would create a histogram. 20 00:01:04,050 --> 00:01:08,570 The histogram of this distribution would be just right into this kind of flat line. 21 00:01:08,570 --> 00:01:12,640 For example, the distributions of low entropy they, they are interesting. 22 00:01:12,640 --> 00:01:14,530 They have many peaks, right. 23 00:01:14,530 --> 00:01:19,230 So the idea here is that if I plot the histogram of a distribution with low 24 00:01:19,230 --> 00:01:23,510 entropy, this distribution would have a high peak and the rest would be very low. 25 00:01:23,510 --> 00:01:24,530 Right, so in some sense, 26 00:01:24,530 --> 00:01:28,940 if our distribution has very high entropy, it's very hard to guess the value of X. 27 00:01:28,940 --> 00:01:30,810 And if our distribution has very low entropy, 28 00:01:30,810 --> 00:01:35,000 then it's very easy to guess what's the value of X. 29 00:01:35,000 --> 00:01:35,850 So, for example, 30 00:01:35,850 --> 00:01:40,620 here at the bottom, imagine I have a distribution of dots on the plane. 31 00:01:40,620 --> 00:01:42,460 For example, here on the, 32 00:01:42,460 --> 00:01:47,000 on the right where I have these dots kind of uniformly spread throughout this space. 33 00:01:47,000 --> 00:01:50,750 This is the condition of high entropy because for me it's very hard to guess 34 00:01:50,750 --> 00:01:55,430 where the dots are, but in, in the case on the left where I have all the dots in one 35 00:01:55,430 --> 00:01:59,760 part of the space, it's very easy for me to guess a location of a dot, right? 36 00:01:59,760 --> 00:02:02,290 So if this is the case, of the low entropy. 37 00:02:02,290 --> 00:02:06,720 So basically the idea is that entropy measures, entropy measure tells us 38 00:02:06,720 --> 00:02:10,860 how uniform or how spread out or how boring is a given distribution? 39 00:02:10,860 --> 00:02:12,590 And if the entropy is low, 40 00:02:12,590 --> 00:02:16,320 then the distribution is very peaked, kind of it always takes the same value. 41 00:02:16,320 --> 00:02:21,470 So the distributions that have low entropy are very, in some sense, easy to guess. 42 00:02:21,470 --> 00:02:22,380 Right? So, 43 00:02:22,380 --> 00:02:27,214 now that we have the concept of entropy let me, let me give you an example. 44 00:02:27,214 --> 00:02:31,950 So, imagine that I want to predict value, value Y but I'm given input X. 45 00:02:31,950 --> 00:02:36,010 In particular imagine that X is the College Major, and 46 00:02:36,010 --> 00:02:39,160 Y is whether the person Likes Gladiator or not. 47 00:02:39,160 --> 00:02:42,290 Right? So my data is a set of X,Y first where X 48 00:02:42,290 --> 00:02:43,310 is the major. 49 00:02:43,310 --> 00:02:46,320 Y is better the person like the gladiator or not. 50 00:02:46,320 --> 00:02:49,880 So now I could start asking okay, what are some entropies in this case? 51 00:02:49,880 --> 00:02:53,520 For example imagine that I want to ask, what is the entropy of Y? 52 00:02:53,520 --> 00:02:59,860 Right, computing the entropy of Y is, is easy, my Y takes two values yes or no. 53 00:02:59,860 --> 00:03:03,820 So first I need to ask, what is the probability of Y taking the value yes? 54 00:03:03,820 --> 00:03:07,170 Then, I need to say if this is one half, 55 00:03:07,170 --> 00:03:10,350 so four out of eight cases is yes, so it's one high. 56 00:03:10,350 --> 00:03:13,070 Time, 1/2 times log base2 1/2. 57 00:03:13,070 --> 00:03:16,340 And then I also need to say how often does the val, 58 00:03:16,340 --> 00:03:21,480 the value Y take the the other value, don't know value, so it's 1 minus 1.5 in 59 00:03:21,480 --> 00:03:26,550 this case, so it's another 1/2 times log base 2 of 1 half. 60 00:03:26,550 --> 00:03:32,890 So overall, the entropy of of Y is 1/2. 61 00:03:32,890 --> 00:03:37,200 In a similar way I could also go and compute the entropy of X. 62 00:03:37,200 --> 00:03:41,050 X here takes three different values, right? 63 00:03:41,050 --> 00:03:44,150 Math, History, CS and that's it. 64 00:03:44,150 --> 00:03:49,080 So now here I would say what fraction of times does, does the X take value of Math? 65 00:03:50,190 --> 00:03:53,630 Take those probabilities multiplied with the log. 66 00:03:53,630 --> 00:03:56,180 How, what fraction of times does this, does it take value CS and 67 00:03:56,180 --> 00:03:59,730 what fraction of times does it take a value of history? 68 00:03:59,730 --> 00:04:03,450 So that's the idea of how we compute entropies on a given data set. 69 00:04:03,450 --> 00:04:07,950 So now that I discussed, how do we compute to the entropy? 70 00:04:07,950 --> 00:04:13,640 Now we can introduce the, the concept of specific conditional entropy. 71 00:04:13,640 --> 00:04:16,490 So the idea here, the way we write this is the following we say. 72 00:04:16,490 --> 00:04:20,840 What is the entropy of Y given X takes a particular value v. 73 00:04:20,840 --> 00:04:27,260 So this is the entropy of Y, among only those records for which X has value v. 74 00:04:27,260 --> 00:04:28,580 Right? So in, in, for 75 00:04:28,580 --> 00:04:33,890 example, if I can ask what's the entropy of Y, given that X takes the value Math? 76 00:04:33,890 --> 00:04:34,920 So what would this mean is, 77 00:04:34,920 --> 00:04:39,970 I only go select the roles for which X takes value Math. 78 00:04:39,970 --> 00:04:44,720 I see that half of them have value yes, and half of them have value no. 79 00:04:44,720 --> 00:04:49,640 So using the same calculation as we just did on the previous slide, the value is 1. 80 00:04:49,640 --> 00:04:56,000 For example, I can ask, what's the entropy of Y given that X is majored in history. 81 00:04:56,000 --> 00:05:01,330 So I'm taking all the history entries, here they are, both of them have value no. 82 00:05:01,330 --> 00:05:04,850 So the, this is a completely boring distribution, right. 83 00:05:04,850 --> 00:05:08,280 Everything is the same all the time, so historians don't like 84 00:05:10,150 --> 00:05:14,740 Gladiator, which I can kind of conclude based on this small, small example. 85 00:05:14,740 --> 00:05:18,290 similarly, I could also compute the entropy of Y, so 86 00:05:18,290 --> 00:05:20,980 whether somebody will like Gladiator based on whether they. 87 00:05:22,390 --> 00:05:24,560 Majored from Computer Science. 88 00:05:24,560 --> 00:05:28,580 So now this is what we just did is specific conditional entropy and 89 00:05:28,580 --> 00:05:29,990 the reason why it's called specific, 90 00:05:29,990 --> 00:05:34,640 is because we are conditioning on X given or taking a particular value v. 91 00:05:35,810 --> 00:05:41,930 We can generalize this concept and call, and define the conditional entropy. 92 00:05:41,930 --> 00:05:45,560 The way we compute conditional entropy is very simple. 93 00:05:45,560 --> 00:05:50,340 All we do is we just go over the domain of a given variable X with saying what is 94 00:05:50,340 --> 00:05:55,100 the probability of X taking this variable value times the entropy of 95 00:05:55,100 --> 00:05:56,660 Y given X, right? 96 00:05:56,660 --> 00:06:01,210 So this is the entropy of Y given X, and simply the. 97 00:06:01,210 --> 00:06:05,020 Weighted average specific condition of entropy of Y, 98 00:06:05,020 --> 00:06:09,560 where weights are the probability or freshen of times X takes a given value Y. 99 00:06:10,750 --> 00:06:15,100 So, let's look at a simple example of conditional entropy. 100 00:06:15,100 --> 00:06:18,640 The idea here is to say that conditional entropy of Y given X, 101 00:06:18,640 --> 00:06:22,430 is the average specific conditional entropy of Y, we have formula. 102 00:06:22,430 --> 00:06:26,060 So for example if I take my input data table here on the left, 103 00:06:26,060 --> 00:06:29,450 I can create the, the conditional entropy table. 104 00:06:29,450 --> 00:06:34,020 Where my goal is to compute what is entropy of Y given X, so for 105 00:06:34,020 --> 00:06:38,400 every value of X, I need to compute what is P of X, I have it here. 106 00:06:38,400 --> 00:06:41,650 And then, for every, for every value of X, I also need to 107 00:06:41,650 --> 00:06:46,140 compute what is the what this the entropy of Y, for that given value of X. 108 00:06:46,140 --> 00:06:49,100 I get the stable, and then I just do the weighted summation, and 109 00:06:49,100 --> 00:06:54,300 I would find that the, the entropy of Y given X, in our case, would be 0.5. 110 00:06:54,300 --> 00:06:57,940 So now that we have kind of built all the machinery, 111 00:06:57,940 --> 00:07:00,910 we are now ready to talk about the Information Gain. 112 00:07:00,910 --> 00:07:04,190 An Information Gain, what it tells us is the following. 113 00:07:04,190 --> 00:07:06,780 It tells us that, it tells us if we want to transmit Y, 114 00:07:06,780 --> 00:07:13,040 how many bits would we save on average if both ends would know X? 115 00:07:13,040 --> 00:07:15,510 Right, so the idea is, what is, 116 00:07:15,510 --> 00:07:19,750 is basically the difference between what is the entropy of Y. 117 00:07:19,750 --> 00:07:24,520 And what is the entropy of Y, given that we already know X, right? 118 00:07:24,520 --> 00:07:28,930 The bigger the difference, the more X tells us about Y. 119 00:07:28,930 --> 00:07:32,380 Right, so Y is the, the, our class. 120 00:07:32,380 --> 00:07:36,030 We see what is our entropy of Y, and then we say, 121 00:07:36,030 --> 00:07:40,700 how much will this entropy decrease if I go and tell you X ahead of time? 122 00:07:40,700 --> 00:07:44,120 And, for example, in going back to our, to our case, 123 00:07:44,120 --> 00:07:49,240 to our data table, we already know the entropy of Y equals 1, we all, 124 00:07:49,240 --> 00:07:55,456 already know the entropy of Y given X equals .5 so the information gain of Y. 125 00:07:55,456 --> 00:07:58,520 Given X is 0.5. 126 00:07:58,520 --> 00:08:02,910 So basically the idea is that in our case what we will do is we will for 127 00:08:02,910 --> 00:08:06,420 every feature X sub i, X sub i, we will go and 128 00:08:06,420 --> 00:08:12,640 compute what is the information gain of Y given X sub i? 129 00:08:12,640 --> 00:08:18,120 We will then rank our features by the, by the decreasing information gain. 130 00:08:18,120 --> 00:08:21,380 And we want to pick features, that have high information gain, right? 131 00:08:21,380 --> 00:08:24,490 That tell us a lot about the value of Y. 132 00:08:25,560 --> 00:08:29,930 So, just to give you an example how to think about this, imagine we are trying to 133 00:08:29,930 --> 00:08:33,920 predict whether someone is going to live past 80 years, right? 134 00:08:33,920 --> 00:08:35,660 So we have this prediction problem where we say, 135 00:08:35,660 --> 00:08:38,280 are you going to live more than 80 years or not? 136 00:08:38,280 --> 00:08:40,880 And imagine that using some historical data the, 137 00:08:40,880 --> 00:08:45,530 the information gains we would compute on it would be something as follows. 138 00:08:45,530 --> 00:08:48,800 If I say probability, what is the information gain of 139 00:08:48,800 --> 00:08:52,970 long life given hair color, here the information gain is very low. 140 00:08:52,970 --> 00:08:57,360 Basically, hair color doesn't tell us much about the probability, 141 00:08:57,360 --> 00:09:00,350 how long is someone going to live? 142 00:09:00,350 --> 00:09:06,660 For example, we see that whether somebody is smoking, or what is someone's gender. 143 00:09:06,660 --> 00:09:10,970 Tells us much more about how long somebody is going to leave. 144 00:09:10,970 --> 00:09:15,240 For example, given that Social Security Numbers in the United States are random, 145 00:09:15,240 --> 00:09:20,340 so how much do, last four digits of Social Security Number tell us about how 146 00:09:20,340 --> 00:09:24,410 long is somebody going to leave, it basically, they don't tell us anything. 147 00:09:24,410 --> 00:09:29,040 So the whole idea about information gain is that it tells us how much information 148 00:09:29,040 --> 00:09:35,170 about the target variable Y is, is stored or contained in X. 149 00:09:35,170 --> 00:09:40,200 So basically the attribute Y that has high value of information gain, 150 00:09:40,200 --> 00:09:45,950 is the attribute on which we want to split when creating a decision tree. 151 00:09:45,950 --> 00:09:46,450 In our case.