7.8 Decision Tree Learning | Regression Trees (optional) --[Machine Learning | Andrew Ng]
 So far, we've only been talking about decision trees as classification algorithms. In this optional video, we'll generalize decision trees to be regression algorithms so that they can predict a number. Let's take a look. The example I'm going to use for this video will be to use the discrete value features that we had previously, that is these features x, in order to predict the weight of the animal y. So just to be clear, the weight here, unlike the previous video, is no longer an input feature. Instead, this is the target output y that we want to predict, rather than trying to predict whether or not an animal is or is not a cat. This is a regression problem because we want to predict a number y. Let's look at what a regression tree will look like. Here I've already constructed a tree for this regression problem, where the root node splits on ear shape, and then the left and right subtrees split on face shape and also face shape here on the right. And there's nothing wrong with a decision tree that chooses to split on the same feature in both the left and right sub-branches. It's perfectly fine if the splitting algorithm chooses to do that. If during training you had decided on these splits, then this node down here would have these four animals with weights 7.2, 8.4, 7.6, and 10.2. This node would have this one animal with weight 9.2 and so on for these remaining two nodes. So the last thing we need to fill in for this decision tree is, if there's a test example that comes down to this node, what is the weight that we should predict for an animal with pointy ears and a round face shape? The decision tree is going to make a prediction based on taking the average of the weights in the training examples down here, and by averaging these four numbers, it turns out you get 8.35. If on the other hand an animal has pointy ears and a not round face shape, then it will predict 9.2 or 9.20 pounds because that's the weight of this one animal down here. And similarly, this would be 17.70 and 9.90. So what this model will do is, given a new test example, follow the decision nodes down as usual until it gets to a leaf node and then predict that value at the leaf node, which I had just computed by taking an average of the weights of the animals that during training had gotten down to that same leaf node. So if you were constructing a decision tree from scratch using this data set in order to predict the weight, the key decision, as you've seen earlier this week, will be how do you choose which feature to split on? Let me illustrate how to make that decision with an example. At the root node, one thing you could do is split on the ear shape, and if you do that, you end up with left and right branches of the tree with five animals on the left and right with the following weights. If you were to choose to split on the face shape, you end up with these animals on the left and right with the corresponding weights that are written below. And if you were to choose to split on whiskers being present or absent, you end up with this. So the question is, given these three possible features to split on at the root node, which one do you want to pick that gives the best predictions for the weight of the animal? When building a regression tree, rather than trying to reduce entropy, which was that measure of impurity that we had for a classification problem, we will instead try to reduce the variance of the weights of the values y at each of these subsets of the data. So if you've seen the notion of variance in other contexts, that's great. This is the statistical and mathematical notion of variance that we'll use in a minute. But if you've not seen how to compute the variance of a set of numbers before, don't worry about it. All you need to know for this slide is that variance informally computes how widely a set of numbers varies. So for this set of numbers, 7.2, 9.2, and so on up to 10.2, it turns out the variance is 1.47. So it doesn't vary that much. Because here, 8.8, 15, 11, 18, and 20, these numbers go all the way from 8.8 all the way up to 20. And so the variance is much larger. Turns out to have a variance of 21.87. And so the way we'll evaluate the quality of this split is we'll compute, same as before, w left and w right as the fraction of examples that went to the left and right branches. And the average variance after the split is going to be 510, which is w left, times 1.47, which is the variance on the left, and then plus 510 times the variance on the right, which is 21.87. So this weighted average variance plays a very similar role to the weighted average entropy that we had used when deciding what split to use for a classification problem. And we can then repeat this calculation for the other possible choices of features to split on. Here in the tree in the middle, the variance of these numbers here turns out to be 27.80. The variance here is 1.37. And so with w left equals 710, and w right is 310. And so with these values, you can compute the weighted variance as follows. Finally, for the last example, if you were to split on the whiskers feature, this is the variance on the left and right. There's w left and w right. And so the weighted variance is this. A good way to choose a split would be to just choose the value of the weighted variance that is lowest. Similar to when we're computing information gain, I'm going to make just one more modification to this equation. Just as for the classification problem, we didn't just measure the average weighted entropy. We measured the reduction in entropy, and that was information gain. For regression tree, we'll also similarly measure the reduction in variance. Turns out, if you look at all of the examples in the training set, all 10 examples, and you compute the variance of all of them, the variance of all the examples turns out to be 20.51. And that's the same value for the root node in all of these, of course, because it's the same 10 examples at the root node. And so what we'll actually compute is the variance of the root node, which is 20.51, minus this expression down here, which turns out to be equal to 8.84. And so at the root node, the variance was 20.51, and after splitting on ear shape, the average weighted variance at these two nodes is 8.84 lower. So the reduction in variance is 8.84. And similarly, if you compute the expression for reduction in variance for this example in the middle, it's 20.51 minus this expression that we had before, which turns out to be equal to 0.64. So this is a very small reduction in variance. And for the whiskers feature, you end up with this, which is 6.22. So between all three of these examples, 8.84 gives you the largest reduction in variance. So just as previously, we would choose the feature that gives you the largest information gain. For regression tree, you would choose the feature that gives you the largest reduction in variance, which is why you choose ear shape as the feature to split on. Having chosen the ear shape feature to split on, you now have two subsets of five examples in the left and right sub-branches. And you would then, again, we say recursively, but you take these five examples and build a new decision tree focusing on just these five examples, again, evaluating different options of features to split on and picking the one that gives you the biggest variance reduction. And similarly, on the right, and you keep on splitting until you meet the criteria for not splitting any further. And so that's it. With this technique, you can get your decision tree to not just carry out classification problems, but also regression problems. So far, we've talked about how to train a single decision tree. It turns out if you train a lot of decision trees, we call this an ensemble of decision trees, you can get a much better result. Let's take a look at why and how to do so in the next video.
[{"start": 0.0, "end": 7.4, "text": " So far, we've only been talking about decision trees as classification algorithms."}, {"start": 7.4, "end": 12.68, "text": " In this optional video, we'll generalize decision trees to be regression algorithms so that"}, {"start": 12.68, "end": 14.46, "text": " they can predict a number."}, {"start": 14.46, "end": 15.46, "text": " Let's take a look."}, {"start": 15.46, "end": 20.64, "text": " The example I'm going to use for this video will be to use the discrete value features"}, {"start": 20.64, "end": 27.84, "text": " that we had previously, that is these features x, in order to predict the weight of the animal"}, {"start": 27.84, "end": 28.84, "text": " y."}, {"start": 28.84, "end": 34.24, "text": " So just to be clear, the weight here, unlike the previous video, is no longer an input"}, {"start": 34.24, "end": 35.24, "text": " feature."}, {"start": 35.24, "end": 41.16, "text": " Instead, this is the target output y that we want to predict, rather than trying to"}, {"start": 41.16, "end": 45.980000000000004, "text": " predict whether or not an animal is or is not a cat."}, {"start": 45.980000000000004, "end": 50.08, "text": " This is a regression problem because we want to predict a number y."}, {"start": 50.08, "end": 54.879999999999995, "text": " Let's look at what a regression tree will look like."}, {"start": 54.88, "end": 60.160000000000004, "text": " Here I've already constructed a tree for this regression problem, where the root node splits"}, {"start": 60.160000000000004, "end": 65.68, "text": " on ear shape, and then the left and right subtrees split on face shape and also face"}, {"start": 65.68, "end": 67.44, "text": " shape here on the right."}, {"start": 67.44, "end": 72.52000000000001, "text": " And there's nothing wrong with a decision tree that chooses to split on the same feature"}, {"start": 72.52000000000001, "end": 75.6, "text": " in both the left and right sub-branches."}, {"start": 75.6, "end": 80.80000000000001, "text": " It's perfectly fine if the splitting algorithm chooses to do that."}, {"start": 80.8, "end": 87.36, "text": " If during training you had decided on these splits, then this node down here would have"}, {"start": 87.36, "end": 93.56, "text": " these four animals with weights 7.2, 8.4, 7.6, and 10.2."}, {"start": 93.56, "end": 101.8, "text": " This node would have this one animal with weight 9.2 and so on for these remaining two"}, {"start": 101.8, "end": 103.84, "text": " nodes."}, {"start": 103.84, "end": 110.16, "text": " So the last thing we need to fill in for this decision tree is, if there's a test example"}, {"start": 110.16, "end": 117.32, "text": " that comes down to this node, what is the weight that we should predict for an animal"}, {"start": 117.32, "end": 122.52, "text": " with pointy ears and a round face shape?"}, {"start": 122.52, "end": 126.8, "text": " The decision tree is going to make a prediction based on taking the average of the weights"}, {"start": 126.8, "end": 131.4, "text": " in the training examples down here, and by averaging these four numbers, it turns out"}, {"start": 131.4, "end": 134.4, "text": " you get 8.35."}, {"start": 134.4, "end": 139.48, "text": " If on the other hand an animal has pointy ears and a not round face shape, then it will"}, {"start": 139.48, "end": 148.44, "text": " predict 9.2 or 9.20 pounds because that's the weight of this one animal down here."}, {"start": 148.44, "end": 154.28, "text": " And similarly, this would be 17.70 and 9.90."}, {"start": 154.28, "end": 160.48, "text": " So what this model will do is, given a new test example, follow the decision nodes down"}, {"start": 160.48, "end": 166.44, "text": " as usual until it gets to a leaf node and then predict that value at the leaf node,"}, {"start": 166.44, "end": 172.88, "text": " which I had just computed by taking an average of the weights of the animals that during"}, {"start": 172.88, "end": 176.56, "text": " training had gotten down to that same leaf node."}, {"start": 176.56, "end": 182.6, "text": " So if you were constructing a decision tree from scratch using this data set in order"}, {"start": 182.6, "end": 188.64, "text": " to predict the weight, the key decision, as you've seen earlier this week, will be how"}, {"start": 188.64, "end": 192.0, "text": " do you choose which feature to split on?"}, {"start": 192.0, "end": 197.0, "text": " Let me illustrate how to make that decision with an example."}, {"start": 197.0, "end": 203.84, "text": " At the root node, one thing you could do is split on the ear shape, and if you do that,"}, {"start": 203.84, "end": 209.08, "text": " you end up with left and right branches of the tree with five animals on the left and"}, {"start": 209.08, "end": 212.44, "text": " right with the following weights."}, {"start": 212.44, "end": 217.64, "text": " If you were to choose to split on the face shape, you end up with these animals on the"}, {"start": 217.64, "end": 221.84, "text": " left and right with the corresponding weights that are written below."}, {"start": 221.84, "end": 228.28, "text": " And if you were to choose to split on whiskers being present or absent, you end up with this."}, {"start": 228.28, "end": 235.92000000000002, "text": " So the question is, given these three possible features to split on at the root node, which"}, {"start": 235.92000000000002, "end": 242.16, "text": " one do you want to pick that gives the best predictions for the weight of the animal?"}, {"start": 242.16, "end": 247.96, "text": " When building a regression tree, rather than trying to reduce entropy, which was that measure"}, {"start": 247.96, "end": 252.64000000000001, "text": " of impurity that we had for a classification problem, we will instead try to reduce the"}, {"start": 252.64000000000001, "end": 261.0, "text": " variance of the weights of the values y at each of these subsets of the data."}, {"start": 261.0, "end": 266.98, "text": " So if you've seen the notion of variance in other contexts, that's great."}, {"start": 266.98, "end": 272.08, "text": " This is the statistical and mathematical notion of variance that we'll use in a minute."}, {"start": 272.08, "end": 278.08, "text": " But if you've not seen how to compute the variance of a set of numbers before, don't"}, {"start": 278.08, "end": 279.08, "text": " worry about it."}, {"start": 279.08, "end": 284.96, "text": " All you need to know for this slide is that variance informally computes how widely a"}, {"start": 284.96, "end": 287.76, "text": " set of numbers varies."}, {"start": 287.76, "end": 294.15999999999997, "text": " So for this set of numbers, 7.2, 9.2, and so on up to 10.2, it turns out the variance"}, {"start": 294.15999999999997, "end": 296.79999999999995, "text": " is 1.47."}, {"start": 296.79999999999995, "end": 298.79999999999995, "text": " So it doesn't vary that much."}, {"start": 298.8, "end": 306.16, "text": " Because here, 8.8, 15, 11, 18, and 20, these numbers go all the way from 8.8 all the way"}, {"start": 306.16, "end": 307.16, "text": " up to 20."}, {"start": 307.16, "end": 309.48, "text": " And so the variance is much larger."}, {"start": 309.48, "end": 313.06, "text": " Turns out to have a variance of 21.87."}, {"start": 313.06, "end": 320.04, "text": " And so the way we'll evaluate the quality of this split is we'll compute, same as before,"}, {"start": 320.04, "end": 326.64, "text": " w left and w right as the fraction of examples that went to the left and right branches."}, {"start": 326.64, "end": 334.59999999999997, "text": " And the average variance after the split is going to be 510, which is w left, times 1.47,"}, {"start": 334.59999999999997, "end": 340.0, "text": " which is the variance on the left, and then plus 510 times the variance on the right,"}, {"start": 340.0, "end": 343.36, "text": " which is 21.87."}, {"start": 343.36, "end": 348.84, "text": " So this weighted average variance plays a very similar role to the weighted average"}, {"start": 348.84, "end": 355.15999999999997, "text": " entropy that we had used when deciding what split to use for a classification problem."}, {"start": 355.16, "end": 361.24, "text": " And we can then repeat this calculation for the other possible choices of features to"}, {"start": 361.24, "end": 362.24, "text": " split on."}, {"start": 362.24, "end": 370.36, "text": " Here in the tree in the middle, the variance of these numbers here turns out to be 27.80."}, {"start": 370.36, "end": 374.84000000000003, "text": " The variance here is 1.37."}, {"start": 374.84000000000003, "end": 379.40000000000003, "text": " And so with w left equals 710, and w right is 310."}, {"start": 379.4, "end": 385.32, "text": " And so with these values, you can compute the weighted variance as follows."}, {"start": 385.32, "end": 390.0, "text": " Finally, for the last example, if you were to split on the whiskers feature, this is"}, {"start": 390.0, "end": 392.4, "text": " the variance on the left and right."}, {"start": 392.4, "end": 394.59999999999997, "text": " There's w left and w right."}, {"start": 394.59999999999997, "end": 397.0, "text": " And so the weighted variance is this."}, {"start": 397.0, "end": 402.03999999999996, "text": " A good way to choose a split would be to just choose the value of the weighted variance"}, {"start": 402.03999999999996, "end": 405.4, "text": " that is lowest."}, {"start": 405.4, "end": 409.64, "text": " Similar to when we're computing information gain, I'm going to make just one more modification"}, {"start": 409.64, "end": 410.64, "text": " to this equation."}, {"start": 410.64, "end": 416.15999999999997, "text": " Just as for the classification problem, we didn't just measure the average weighted"}, {"start": 416.15999999999997, "end": 417.4, "text": " entropy."}, {"start": 417.4, "end": 421.96, "text": " We measured the reduction in entropy, and that was information gain."}, {"start": 421.96, "end": 426.23999999999995, "text": " For regression tree, we'll also similarly measure the reduction in variance."}, {"start": 426.23999999999995, "end": 433.23999999999995, "text": " Turns out, if you look at all of the examples in the training set, all 10 examples, and"}, {"start": 433.24, "end": 438.2, "text": " you compute the variance of all of them, the variance of all the examples turns out to"}, {"start": 438.2, "end": 439.2, "text": " be 20.51."}, {"start": 439.2, "end": 445.44, "text": " And that's the same value for the root node in all of these, of course, because it's the"}, {"start": 445.44, "end": 448.76, "text": " same 10 examples at the root node."}, {"start": 448.76, "end": 455.24, "text": " And so what we'll actually compute is the variance of the root node, which is 20.51,"}, {"start": 455.24, "end": 462.24, "text": " minus this expression down here, which turns out to be equal to 8.84."}, {"start": 462.24, "end": 468.56, "text": " And so at the root node, the variance was 20.51, and after splitting on ear shape, the"}, {"start": 468.56, "end": 475.04, "text": " average weighted variance at these two nodes is 8.84 lower."}, {"start": 475.04, "end": 478.12, "text": " So the reduction in variance is 8.84."}, {"start": 478.12, "end": 484.56, "text": " And similarly, if you compute the expression for reduction in variance for this example"}, {"start": 484.56, "end": 490.32, "text": " in the middle, it's 20.51 minus this expression that we had before, which turns out to be"}, {"start": 490.32, "end": 492.22, "text": " equal to 0.64."}, {"start": 492.22, "end": 495.44000000000005, "text": " So this is a very small reduction in variance."}, {"start": 495.44000000000005, "end": 502.90000000000003, "text": " And for the whiskers feature, you end up with this, which is 6.22."}, {"start": 502.90000000000003, "end": 510.04, "text": " So between all three of these examples, 8.84 gives you the largest reduction in variance."}, {"start": 510.04, "end": 514.9200000000001, "text": " So just as previously, we would choose the feature that gives you the largest information"}, {"start": 514.9200000000001, "end": 516.1600000000001, "text": " gain."}, {"start": 516.1600000000001, "end": 520.6, "text": " For regression tree, you would choose the feature that gives you the largest reduction"}, {"start": 520.6, "end": 526.6, "text": " in variance, which is why you choose ear shape as the feature to split on."}, {"start": 526.6, "end": 535.32, "text": " Having chosen the ear shape feature to split on, you now have two subsets of five examples"}, {"start": 535.32, "end": 538.24, "text": " in the left and right sub-branches."}, {"start": 538.24, "end": 544.4, "text": " And you would then, again, we say recursively, but you take these five examples and build"}, {"start": 544.4, "end": 550.0400000000001, "text": " a new decision tree focusing on just these five examples, again, evaluating different"}, {"start": 550.04, "end": 555.0799999999999, "text": " options of features to split on and picking the one that gives you the biggest variance"}, {"start": 555.0799999999999, "end": 556.4, "text": " reduction."}, {"start": 556.4, "end": 563.0, "text": " And similarly, on the right, and you keep on splitting until you meet the criteria for"}, {"start": 563.0, "end": 565.04, "text": " not splitting any further."}, {"start": 565.04, "end": 566.12, "text": " And so that's it."}, {"start": 566.12, "end": 571.0799999999999, "text": " With this technique, you can get your decision tree to not just carry out classification"}, {"start": 571.0799999999999, "end": 574.92, "text": " problems, but also regression problems."}, {"start": 574.92, "end": 579.12, "text": " So far, we've talked about how to train a single decision tree."}, {"start": 579.12, "end": 583.68, "text": " It turns out if you train a lot of decision trees, we call this an ensemble of decision"}, {"start": 583.68, "end": 587.12, "text": " trees, you can get a much better result."}, {"start": 587.12, "end": 610.12, "text": " Let's take a look at why and how to do so in the next video."}]