7.4 Decision Tree Learning | Choosing a split : Information Gain --[Machine Learning | Andrew Ng]
 When building a decision tree, the way we'll decide what feature to split on at a node will be based on what choice of feature reduces entropy the most. Reduces entropy or reduces impurity or maximizes purity. In decision tree learning, the reduction of entropy is called information gain. Let's take a look in this video at how to compute information gain and therefore choose what feature to use to split on at each node in your decision tree. Let's use the example of deciding what feature to use at the root node of the decision tree we're building just now for recognizing cats versus not cats. If we had split using the ear shape feature at the root node, this is what we would have gotten. Five examples on the left and five on the right. And on the left, we would have four out of five cats. The P1 would be equal to four fifths or 0.8. And on the right, one out of five are cats. So P1 is equal to one fifth or 0.2. If you apply the entropy formula from the last video to this left subset of data and this right subset of data, we find that the degree of impurity on the left is entropy of 0.8, which is about 0.72. And on the right, the entropy of 0.2 turns out also to be 0.72. So this would be the entropy at the left and right sub branches if we were to split on the ear shape feature. One other option would be to split on the face shape feature. If we'd done so, then on the left, for the seven examples would be cats. So P1 is four sevenths. And on the right, one third are cats. So P1 on the right is one third. And the entropy of four sevenths and the entropy of one third are 0.99 and 0.92. So the degree of impurity in the left and right node seems much higher, 0.99 and 0.92 compared to 0.72 and 0.72. Finally, the third possible choice of feature to use at the root node would be the whiskers feature, in which case you split based on whether whiskers are present or absent. In this case, P1 on the left is three quarters, P1 on the right is two sixths, and the entropy values are as follows. So the key question we need to answer is, given these three options of a feature to use at the root node, which one do we think works best? It turns out that rather than looking at these entropy numbers and comparing them, it would be useful to take a weighted average of them. And here's what I mean. If there's a node with a lot of examples in it with high entropy, that seems worse than if there was a node with just a few examples in it with high entropy. Because entropy as a measure of impurity is worse if you have a very large and impure data set compared to just a few examples in a branch of a tree that is very impure. So the key decision is, of these three possible choices of features to use at the root node, which one do we want to use? Consider with each of these splits is two numbers, the entropy on the left sub-branch and the entropy on the right sub-branch. And in order to pick from these, we like to actually combine these two numbers into a single number. So we can just pick of these three choices, which one does best. And the way we're going to combine these two numbers is by taking a weighted average. Because how important it is to have low entropy in say the left or right sub-branch, also depends on how many examples went into the left or right sub-branch. Because if there are a lot of examples in say the left sub-branch, then it seems more important to make sure that that left sub-branch's entropy value is low. So in this example, we have five of the 10 examples went to the left sub-branch. So we can compute the weighted average as five out of 10 times the entropy of 0.8. And then after that, five of the 10 examples also went to the right sub-branch plus five tens times the entropy of 0.2. Now for this example in the middle, the left sub-branch had received seven out of 10 examples. And so we're going to compute seven tens times the entropy of 0.57 plus the right sub-branch had three out of 10 examples, so plus three tens times entropy of 0.33 or one-third. And finally, on the right, we'll compute four tens times entropy of 0.75 plus six tens times entropy of 0.33. And so the way we will choose to split is by computing these three numbers and picking whichever one is lowest because that gives us the left and right sub-branch's with the lowest average weighted entropy. In the way that decision trees are built, we're actually going to make one more change to these formulas to stick to the convention in decision tree building, but it won't actually change the outcome, which is rather than computing this weighted average entropy, we're going to compute the reduction in entropy compared to if we hadn't split at all. So if we go to the root node, remember that at the root node, we had started off with all 10 examples in the root node with five cats and five dogs. And so at the root node, we had P1 equals five tens of 0.5. And so the entropy of the root node, entropy of 0.5 was actually equal to one. This was maximum impurity because it was five cats and five dogs. So the formula that we're actually going to use for choosing a split is not this weighted entropy at the left and right sub-branch's. Instead is going to be the entropy at the root node, which is entropy of 0.5, then minus this formula. And in this example, if you work out the math, it turns out to be 0.28. For the face shape example, we can compute entropy of the root node, entropy of 0.5 minus this, which turns out to be 0.03. And for whiskers, compute that, which turns out to be 0.12. These numbers that we just calculated, 0.28, 0.03, and 0.12, these are called the information gain. And what it measures is the reduction in entropy that you get in your tree resulting from the making a split. Because the entropy was originally one at the root node, and by making the split, you end up with a lower value of entropy. And the difference between those two values is a reduction in entropy, and that's 0.28 in the case of splitting on the ear shape. So why do we bother to compute reduction in entropy rather than just entropy at the left and right sub-branch's? It turns out that one of the stopping criteria for deciding when to not bother to split any further is if the reduction in entropy is too small, in which case you could decide you're just increasing the size of the tree unnecessarily and risking overfitting by splitting and just decide to not bother if the reduction in entropy is too small below a threshold. In this particular example, splitting on ear shape results in the biggest reduction in entropy, 0.28 is bigger than 0.03 or 0.12, and so we would choose to split on the ear shape feature at the root node. On the next slide, let's give a more formal definition of information gain. And by the way, one additional piece of notation that we'll introduce also in the next slide is these numbers, 5 tens and 5 tens, I'm going to call this w left, because that's the fraction of examples that went to the left branch, and I'm going to call this w right, because that's the fraction of examples that went to the right branch, whereas for this middle example w left would be 7 tens and w right would be 3 tens. So let's now write down the general formula for how to compute information gain. Using the example of splitting on the ear shape feature, let me define p1 left to be equal to the fraction of examples in the left subtree that have a positive label that are cats, and so in this example p1 left would be equal to 4 fifths, and also let me define w left to be the fraction of examples out of all the examples at the root node that went to the left sub branch, and so in this example w left would be 5 tens. Similarly, let's define p1 right to be of all the examples in the right branch, the fraction that are positive examples, and so of one out of five of these examples being cats that would be one fifth, and similarly w right is 5 tens, the fraction of examples that went to the right sub branch, and let's also define p1 root to be the fraction of examples that are positive in the root node. So in this case this would be 5 tens or 0.5. Information gain is then defined as the entropy of p1 root, so what's the entropy at the root node, minus that weighted entropy calculation that we had on the previous slide, minus w left, this would be 5 tens in the example, times the entropy applied to p1 left, that's entropy on the left sub branch, plus w right, the fraction of examples that went to the right branch, times entropy of p1 right, and so with this definition of entropy you can calculate the information gain associated with choosing any particular feature to split on in the node, and then out of all the possible features you could choose to split on, you can then pick the one that gives you the highest information gain, and that will result in hopefully increasing the purity of your subsets of data that you get on the left and right sub branches of your decision tree, and that will result in choosing a feature to split on that increases the purity of your subsets of data in both the left and right sub branches of your decision tree. Now that you know how to calculate information gain or reduction in entropy, you know how to pick a feature to split on at a node. Let's put all the things we've talked about together into the overall algorithm for building a decision tree given a training set. Let's go see that in the next video.
[{"start": 0.0, "end": 7.3, "text": " When building a decision tree, the way we'll decide what feature to split on at a node"}, {"start": 7.3, "end": 12.56, "text": " will be based on what choice of feature reduces entropy the most."}, {"start": 12.56, "end": 17.44, "text": " Reduces entropy or reduces impurity or maximizes purity."}, {"start": 17.44, "end": 23.080000000000002, "text": " In decision tree learning, the reduction of entropy is called information gain."}, {"start": 23.080000000000002, "end": 28.12, "text": " Let's take a look in this video at how to compute information gain and therefore choose"}, {"start": 28.12, "end": 32.84, "text": " what feature to use to split on at each node in your decision tree."}, {"start": 32.84, "end": 38.32, "text": " Let's use the example of deciding what feature to use at the root node of the decision tree"}, {"start": 38.32, "end": 43.400000000000006, "text": " we're building just now for recognizing cats versus not cats."}, {"start": 43.400000000000006, "end": 49.92, "text": " If we had split using the ear shape feature at the root node, this is what we would have"}, {"start": 49.92, "end": 51.84, "text": " gotten."}, {"start": 51.84, "end": 54.92, "text": " Five examples on the left and five on the right."}, {"start": 54.92, "end": 59.2, "text": " And on the left, we would have four out of five cats."}, {"start": 59.2, "end": 64.6, "text": " The P1 would be equal to four fifths or 0.8."}, {"start": 64.6, "end": 66.84, "text": " And on the right, one out of five are cats."}, {"start": 66.84, "end": 70.48, "text": " So P1 is equal to one fifth or 0.2."}, {"start": 70.48, "end": 76.96000000000001, "text": " If you apply the entropy formula from the last video to this left subset of data and"}, {"start": 76.96000000000001, "end": 82.72, "text": " this right subset of data, we find that the degree of impurity on the left is entropy"}, {"start": 82.72, "end": 87.24, "text": " of 0.8, which is about 0.72."}, {"start": 87.24, "end": 95.28, "text": " And on the right, the entropy of 0.2 turns out also to be 0.72."}, {"start": 95.28, "end": 102.0, "text": " So this would be the entropy at the left and right sub branches if we were to split on"}, {"start": 102.0, "end": 104.42, "text": " the ear shape feature."}, {"start": 104.42, "end": 109.2, "text": " One other option would be to split on the face shape feature."}, {"start": 109.2, "end": 115.18, "text": " If we'd done so, then on the left, for the seven examples would be cats."}, {"start": 115.18, "end": 117.32000000000001, "text": " So P1 is four sevenths."}, {"start": 117.32000000000001, "end": 120.36, "text": " And on the right, one third are cats."}, {"start": 120.36, "end": 123.44, "text": " So P1 on the right is one third."}, {"start": 123.44, "end": 130.92000000000002, "text": " And the entropy of four sevenths and the entropy of one third are 0.99 and 0.92."}, {"start": 130.92000000000002, "end": 137.24, "text": " So the degree of impurity in the left and right node seems much higher, 0.99 and 0.92"}, {"start": 137.24, "end": 140.20000000000002, "text": " compared to 0.72 and 0.72."}, {"start": 140.20000000000002, "end": 145.08, "text": " Finally, the third possible choice of feature to use at the root node would be the whiskers"}, {"start": 145.08, "end": 150.28, "text": " feature, in which case you split based on whether whiskers are present or absent."}, {"start": 150.28, "end": 156.24, "text": " In this case, P1 on the left is three quarters, P1 on the right is two sixths, and the entropy"}, {"start": 156.24, "end": 159.92000000000002, "text": " values are as follows."}, {"start": 159.92000000000002, "end": 164.68, "text": " So the key question we need to answer is, given these three options of a feature to"}, {"start": 164.68, "end": 170.28, "text": " use at the root node, which one do we think works best?"}, {"start": 170.28, "end": 179.64000000000001, "text": " It turns out that rather than looking at these entropy numbers and comparing them, it would"}, {"start": 179.64000000000001, "end": 183.04000000000002, "text": " be useful to take a weighted average of them."}, {"start": 183.04000000000002, "end": 185.24, "text": " And here's what I mean."}, {"start": 185.24, "end": 191.56, "text": " If there's a node with a lot of examples in it with high entropy, that seems worse than"}, {"start": 191.56, "end": 195.88, "text": " if there was a node with just a few examples in it with high entropy."}, {"start": 195.88, "end": 201.12, "text": " Because entropy as a measure of impurity is worse if you have a very large and impure"}, {"start": 201.12, "end": 208.72, "text": " data set compared to just a few examples in a branch of a tree that is very impure."}, {"start": 208.72, "end": 214.68, "text": " So the key decision is, of these three possible choices of features to use at the root node,"}, {"start": 214.68, "end": 217.88, "text": " which one do we want to use?"}, {"start": 217.88, "end": 222.79999999999998, "text": " Consider with each of these splits is two numbers, the entropy on the left sub-branch"}, {"start": 222.79999999999998, "end": 225.68, "text": " and the entropy on the right sub-branch."}, {"start": 225.68, "end": 230.12, "text": " And in order to pick from these, we like to actually combine these two numbers into a"}, {"start": 230.12, "end": 231.12, "text": " single number."}, {"start": 231.12, "end": 235.92, "text": " So we can just pick of these three choices, which one does best."}, {"start": 235.92, "end": 240.88, "text": " And the way we're going to combine these two numbers is by taking a weighted average."}, {"start": 240.88, "end": 247.76, "text": " Because how important it is to have low entropy in say the left or right sub-branch, also"}, {"start": 247.76, "end": 252.84, "text": " depends on how many examples went into the left or right sub-branch."}, {"start": 252.84, "end": 257.71999999999997, "text": " Because if there are a lot of examples in say the left sub-branch, then it seems more"}, {"start": 257.71999999999997, "end": 263.2, "text": " important to make sure that that left sub-branch's entropy value is low."}, {"start": 263.2, "end": 269.76, "text": " So in this example, we have five of the 10 examples went to the left sub-branch."}, {"start": 269.76, "end": 275.44, "text": " So we can compute the weighted average as five out of 10 times the entropy of 0.8."}, {"start": 275.44, "end": 281.52, "text": " And then after that, five of the 10 examples also went to the right sub-branch plus five"}, {"start": 281.52, "end": 286.68, "text": " tens times the entropy of 0.2."}, {"start": 286.68, "end": 294.34, "text": " Now for this example in the middle, the left sub-branch had received seven out of 10 examples."}, {"start": 294.34, "end": 304.22, "text": " And so we're going to compute seven tens times the entropy of 0.57 plus the right sub-branch"}, {"start": 304.22, "end": 312.6, "text": " had three out of 10 examples, so plus three tens times entropy of 0.33 or one-third."}, {"start": 312.6, "end": 321.04, "text": " And finally, on the right, we'll compute four tens times entropy of 0.75 plus six tens times"}, {"start": 321.04, "end": 324.6, "text": " entropy of 0.33."}, {"start": 324.6, "end": 330.76000000000005, "text": " And so the way we will choose to split is by computing these three numbers and picking"}, {"start": 330.76, "end": 337.12, "text": " whichever one is lowest because that gives us the left and right sub-branch's with the"}, {"start": 337.12, "end": 340.84, "text": " lowest average weighted entropy."}, {"start": 340.84, "end": 344.92, "text": " In the way that decision trees are built, we're actually going to make one more change"}, {"start": 344.92, "end": 350.56, "text": " to these formulas to stick to the convention in decision tree building, but it won't actually"}, {"start": 350.56, "end": 356.88, "text": " change the outcome, which is rather than computing this weighted average entropy, we're going"}, {"start": 356.88, "end": 362.48, "text": " to compute the reduction in entropy compared to if we hadn't split at all."}, {"start": 362.48, "end": 367.64, "text": " So if we go to the root node, remember that at the root node, we had started off with"}, {"start": 367.64, "end": 372.24, "text": " all 10 examples in the root node with five cats and five dogs."}, {"start": 372.24, "end": 379.15999999999997, "text": " And so at the root node, we had P1 equals five tens of 0.5."}, {"start": 379.15999999999997, "end": 385.96, "text": " And so the entropy of the root node, entropy of 0.5 was actually equal to one."}, {"start": 385.96, "end": 390.09999999999997, "text": " This was maximum impurity because it was five cats and five dogs."}, {"start": 390.09999999999997, "end": 395.08, "text": " So the formula that we're actually going to use for choosing a split is not this weighted"}, {"start": 395.08, "end": 399.08, "text": " entropy at the left and right sub-branch's."}, {"start": 399.08, "end": 405.76, "text": " Instead is going to be the entropy at the root node, which is entropy of 0.5, then minus"}, {"start": 405.76, "end": 408.76, "text": " this formula."}, {"start": 408.76, "end": 413.44, "text": " And in this example, if you work out the math, it turns out to be 0.28."}, {"start": 413.44, "end": 419.4, "text": " For the face shape example, we can compute entropy of the root node, entropy of 0.5 minus"}, {"start": 419.4, "end": 424.08, "text": " this, which turns out to be 0.03."}, {"start": 424.08, "end": 430.64, "text": " And for whiskers, compute that, which turns out to be 0.12."}, {"start": 430.64, "end": 436.88, "text": " These numbers that we just calculated, 0.28, 0.03, and 0.12, these are called the information"}, {"start": 436.88, "end": 438.04, "text": " gain."}, {"start": 438.04, "end": 443.4, "text": " And what it measures is the reduction in entropy that you get in your tree resulting from the"}, {"start": 443.4, "end": 445.12, "text": " making a split."}, {"start": 445.12, "end": 453.03999999999996, "text": " Because the entropy was originally one at the root node, and by making the split, you"}, {"start": 453.03999999999996, "end": 455.67999999999995, "text": " end up with a lower value of entropy."}, {"start": 455.67999999999995, "end": 461.2, "text": " And the difference between those two values is a reduction in entropy, and that's 0.28"}, {"start": 461.2, "end": 464.28, "text": " in the case of splitting on the ear shape."}, {"start": 464.28, "end": 470.96, "text": " So why do we bother to compute reduction in entropy rather than just entropy at the left"}, {"start": 470.96, "end": 472.59999999999997, "text": " and right sub-branch's?"}, {"start": 472.6, "end": 477.44, "text": " It turns out that one of the stopping criteria for deciding when to not bother to split any"}, {"start": 477.44, "end": 482.64000000000004, "text": " further is if the reduction in entropy is too small, in which case you could decide"}, {"start": 482.64000000000004, "end": 487.40000000000003, "text": " you're just increasing the size of the tree unnecessarily and risking overfitting by splitting"}, {"start": 487.40000000000003, "end": 493.8, "text": " and just decide to not bother if the reduction in entropy is too small below a threshold."}, {"start": 493.8, "end": 499.12, "text": " In this particular example, splitting on ear shape results in the biggest reduction in"}, {"start": 499.12, "end": 506.08, "text": " entropy, 0.28 is bigger than 0.03 or 0.12, and so we would choose to split on the ear"}, {"start": 506.08, "end": 509.8, "text": " shape feature at the root node."}, {"start": 509.8, "end": 514.92, "text": " On the next slide, let's give a more formal definition of information gain."}, {"start": 514.92, "end": 519.24, "text": " And by the way, one additional piece of notation that we'll introduce also in the next slide"}, {"start": 519.24, "end": 526.36, "text": " is these numbers, 5 tens and 5 tens, I'm going to call this w left, because that's the fraction"}, {"start": 526.36, "end": 531.44, "text": " of examples that went to the left branch, and I'm going to call this w right, because"}, {"start": 531.44, "end": 536.16, "text": " that's the fraction of examples that went to the right branch, whereas for this middle"}, {"start": 536.16, "end": 540.9, "text": " example w left would be 7 tens and w right would be 3 tens."}, {"start": 540.9, "end": 548.42, "text": " So let's now write down the general formula for how to compute information gain."}, {"start": 548.42, "end": 554.84, "text": " Using the example of splitting on the ear shape feature, let me define p1 left to be"}, {"start": 554.84, "end": 561.84, "text": " equal to the fraction of examples in the left subtree that have a positive label that are"}, {"start": 561.84, "end": 569.1800000000001, "text": " cats, and so in this example p1 left would be equal to 4 fifths, and also let me define"}, {"start": 569.1800000000001, "end": 574.84, "text": " w left to be the fraction of examples out of all the examples at the root node that"}, {"start": 574.84, "end": 581.24, "text": " went to the left sub branch, and so in this example w left would be 5 tens."}, {"start": 581.24, "end": 589.16, "text": " Similarly, let's define p1 right to be of all the examples in the right branch, the"}, {"start": 589.16, "end": 593.4, "text": " fraction that are positive examples, and so of one out of five of these examples being"}, {"start": 593.4, "end": 600.48, "text": " cats that would be one fifth, and similarly w right is 5 tens, the fraction of examples"}, {"start": 600.48, "end": 608.48, "text": " that went to the right sub branch, and let's also define p1 root to be the fraction of"}, {"start": 608.48, "end": 612.6, "text": " examples that are positive in the root node."}, {"start": 612.6, "end": 619.36, "text": " So in this case this would be 5 tens or 0.5."}, {"start": 619.36, "end": 626.48, "text": " Information gain is then defined as the entropy of p1 root, so what's the entropy at the root"}, {"start": 626.48, "end": 633.36, "text": " node, minus that weighted entropy calculation that we had on the previous slide, minus w"}, {"start": 633.36, "end": 639.12, "text": " left, this would be 5 tens in the example, times the entropy applied to p1 left, that's"}, {"start": 639.12, "end": 645.6800000000001, "text": " entropy on the left sub branch, plus w right, the fraction of examples that went to the"}, {"start": 645.6800000000001, "end": 654.6800000000001, "text": " right branch, times entropy of p1 right, and so with this definition of entropy you can"}, {"start": 654.6800000000001, "end": 661.2, "text": " calculate the information gain associated with choosing any particular feature to split"}, {"start": 661.2, "end": 666.32, "text": " on in the node, and then out of all the possible features you could choose to split on, you"}, {"start": 666.32, "end": 672.88, "text": " can then pick the one that gives you the highest information gain, and that will result in"}, {"start": 672.88, "end": 678.96, "text": " hopefully increasing the purity of your subsets of data that you get on the left and right"}, {"start": 678.96, "end": 684.0, "text": " sub branches of your decision tree, and that will result in choosing a feature to split"}, {"start": 684.0, "end": 691.56, "text": " on that increases the purity of your subsets of data in both the left and right sub branches"}, {"start": 691.56, "end": 693.76, "text": " of your decision tree."}, {"start": 693.76, "end": 698.6, "text": " Now that you know how to calculate information gain or reduction in entropy, you know how"}, {"start": 698.6, "end": 701.84, "text": " to pick a feature to split on at a node."}, {"start": 701.84, "end": 707.24, "text": " Let's put all the things we've talked about together into the overall algorithm for building"}, {"start": 707.24, "end": 709.84, "text": " a decision tree given a training set."}, {"start": 709.84, "end": 714.6, "text": " Let's go see that in the next video."}]