7.5 Decision Tree Learning | Putting it together --[Machine Learning | Andrew Ng]
 The information gain criteria lets you decide how to choose one feature to split at one node. Let's take that and use that in multiple places through a decision tree in order to figure out how to build a large decision tree with multiple nodes. Here's the overall process of building a decision tree. Start with all training examples at the root node of the tree and calculate the information gain for all possible features and pick the feature to split on that gives the highest information gain. Having chosen this feature, you would then split the data set into two subsets according to the selected feature and create left and right branches of the tree and send the training examples to either the left or the right branch depending on the value of that feature for that example. And this allows you to have made a split at the root node. After that, you would then keep on repeating the splitting process on the left branch of the tree, on the right branch of the tree and so on and keep on doing that until a stopping criteria is met. Where the stopping criteria can be when a node is 100% a single clause, so one has reached entropy of zero or when further splitting a node will cause the tree to exceed the maximum depth that you have set or if the information gain from an additional split is less than a threshold or if the number of examples in a node is below a threshold. And so you would keep on repeating the splitting process until the stopping criteria that you've chosen which could be one or more of these criteria is met. Let's look at an illustration of how this process will work. We started all of the examples at the root nodes and based on computing information gain for all three features, decide that ear shape is the best feature to split on. Based on that, we create left and right sub branches and send the subset of the data with pointy versus floppy ears to the left and right sub branches. So let me cover up the root node and the right sub branch and just focus on the left sub branch where we have these five examples. Let's see how splitting criteria is to keep splitting until everything in the node belongs to a single clause, so either all cats or all dogs. We will look at this node and see if it meets the splitting criteria and it does not because there is a mix of cats and dogs here. So the next step is to then pick a feature to split on. So we then go through the features one at a time and compute the information gain of each of those features as if this node were the new root node of a decision tree that was trained using just five training examples shown here. So we would compute the information gain for splitting on the whiskers feature, the information gain on splitting on the face shape feature, and it turns out that the information gain for splitting on ear shape will be zero because all of these have the same pointy ear shape. And between whiskers and face shape, face shape turns out to have a highest information gain, so we're going to split on face shape and that allows us to build left and right sub-branches as follows. And then for the left sub-branch here, we check for the stopping criteria and we find that it is all cats, so we stop splitting and build a prediction node that predicts cat and for the right sub-branch, we again check the stopping criteria and we find that it is all dogs and so we stop splitting and have a prediction node. So for the left sub-branch, we check for the criteria for whether or not we should stop splitting and we have all cats here and so the stopping criteria is met and we create a leaf node that makes a prediction of cat and for the right sub-branch, we find that it is all dogs and so we will also stop splitting since we've met the splitting criteria and put a leaf node there that predicts not cat. So having built out this left subtree, we can now turn our attention to building the right subtree. Let me now again cover up the root node and the entire left subtree. To build out the right subtree, we have these five examples here and again, the first thing we do is check if the criteria to stop splitting has been met. The criteria being whether or not all the examples are single class, we've not met the criteria and so we'll decide to keep splitting in this right sub-branch as well. And in fact, the procedure for building the right sub-branch will be a lot like as if you were training a decision tree learning algorithm from scratch where the data set you have comprises just these five training examples. And so again, computing information gain for all of the possible features to split on, you find that the whiskers feature gives the highest information gain. So these are the set of five examples according to whether whiskers are present or absent, check if the criteria to stop splitting are met in the left and right sub-branches here and decide that they are and so you end up with leaf nodes that predict cat and not cat. And so this is the overall process for building the decision tree. Notice that there's an interesting aspect of what we've done, which is after we decided what to split on at the root node, the way we built the left sub-tree was by building a decision tree on a subset of five examples and the way we built the right sub-tree was by again building a decision tree on a subset of five examples. In computer science, this is an example of a recursive algorithm and all that means is the way you build a decision tree at the root is by building other smaller decision trees in the left and the right sub-branches. So recursion in computer science refers to writing code that calls itself and the way this comes up in building a decision tree is you build the overall decision tree by building smaller sub-decision trees and then putting them all together. So that's why if you look at software implementations of decision trees, you see sometimes references to a recursive algorithm. But if you don't feel like you fully understood this concept of recursive algorithms, don't worry about it. You'll still be able to fully complete this week's assignments as well as use libraries to get decision trees to work for yourself. But if you're implementing a decision tree algorithm from scratch, then a recursive algorithm turns out to be one of the steps you'd have to implement. And by the way, you may be wondering how to choose the maximum depth parameter. There are many different possible choices, but some of the open source libraries will have good default choices that you can use. One intuition is the larger the maximum depth, the bigger the decision tree you're willing to build. And this is a bit like fitting a higher degree polynomial or training a larger neural network. It lets the decision tree learn a more complex model, but it also increases the risk of overfitting if it's fitting a very complex function to your data. In theory, you could use cross-validation to pick parameters like the maximum depth where you try out different values to the maximum depth and pick what works best on the cross-validation set. But in practice, the open source libraries have even somewhat better ways to choose this parameter for you. Or another criteria that you can use to decide when to stop splitting is if the information gain from an additional split is less than a certain threshold. So if any feature you split on achieves only a small reduction in entropy or a very small information gain, then you might also decide to not bother. And finally, you can also decide to stop splitting when the number of examples in the node is below a certain threshold. So that's the process for building a decision tree. Now that you've learned the decision tree, if you want to make a prediction, you can then follow the procedure that you saw in the very first video of this week where you take a new example, say a test example, and start at the root and keep on following the decisions down until you get to a leave node, which then makes the prediction. Now that you know the basic decision tree learning algorithm, in the next few videos, I'd like to go into some further refinements of this algorithm. So far, we've only used features that take on two possible values, but sometimes you have a feature that takes on categorical or discrete values, but maybe more than two values. Let's take a look in the next video at how to handle that case.
[{"start": 0.0, "end": 6.88, "text": " The information gain criteria lets you decide how to choose one feature to split at one"}, {"start": 6.88, "end": 7.88, "text": " node."}, {"start": 7.88, "end": 12.72, "text": " Let's take that and use that in multiple places through a decision tree in order to figure"}, {"start": 12.72, "end": 16.44, "text": " out how to build a large decision tree with multiple nodes."}, {"start": 16.44, "end": 20.36, "text": " Here's the overall process of building a decision tree."}, {"start": 20.36, "end": 26.92, "text": " Start with all training examples at the root node of the tree and calculate the information"}, {"start": 26.92, "end": 32.160000000000004, "text": " gain for all possible features and pick the feature to split on that gives the highest"}, {"start": 32.160000000000004, "end": 33.84, "text": " information gain."}, {"start": 33.84, "end": 39.160000000000004, "text": " Having chosen this feature, you would then split the data set into two subsets according"}, {"start": 39.160000000000004, "end": 46.36, "text": " to the selected feature and create left and right branches of the tree and send the training"}, {"start": 46.36, "end": 51.64, "text": " examples to either the left or the right branch depending on the value of that feature for"}, {"start": 51.64, "end": 53.68000000000001, "text": " that example."}, {"start": 53.68, "end": 58.84, "text": " And this allows you to have made a split at the root node."}, {"start": 58.84, "end": 64.2, "text": " After that, you would then keep on repeating the splitting process on the left branch of"}, {"start": 64.2, "end": 70.28, "text": " the tree, on the right branch of the tree and so on and keep on doing that until a stopping"}, {"start": 70.28, "end": 72.12, "text": " criteria is met."}, {"start": 72.12, "end": 79.56, "text": " Where the stopping criteria can be when a node is 100% a single clause, so one has reached"}, {"start": 79.56, "end": 85.48, "text": " entropy of zero or when further splitting a node will cause the tree to exceed the maximum"}, {"start": 85.48, "end": 91.36, "text": " depth that you have set or if the information gain from an additional split is less than"}, {"start": 91.36, "end": 98.96000000000001, "text": " a threshold or if the number of examples in a node is below a threshold."}, {"start": 98.96000000000001, "end": 105.92, "text": " And so you would keep on repeating the splitting process until the stopping criteria that you've"}, {"start": 105.92, "end": 110.44, "text": " chosen which could be one or more of these criteria is met."}, {"start": 110.44, "end": 114.92, "text": " Let's look at an illustration of how this process will work."}, {"start": 114.92, "end": 120.76, "text": " We started all of the examples at the root nodes and based on computing information gain"}, {"start": 120.76, "end": 127.72, "text": " for all three features, decide that ear shape is the best feature to split on."}, {"start": 127.72, "end": 133.2, "text": " Based on that, we create left and right sub branches and send the subset of the data with"}, {"start": 133.2, "end": 138.2, "text": " pointy versus floppy ears to the left and right sub branches."}, {"start": 138.2, "end": 143.2, "text": " So let me cover up the root node and the right sub branch and just focus on the left sub"}, {"start": 143.2, "end": 146.83999999999997, "text": " branch where we have these five examples."}, {"start": 146.83999999999997, "end": 151.79999999999998, "text": " Let's see how splitting criteria is to keep splitting until everything in the node belongs"}, {"start": 151.79999999999998, "end": 155.54, "text": " to a single clause, so either all cats or all dogs."}, {"start": 155.54, "end": 160.06, "text": " We will look at this node and see if it meets the splitting criteria and it does not because"}, {"start": 160.06, "end": 163.28, "text": " there is a mix of cats and dogs here."}, {"start": 163.28, "end": 167.6, "text": " So the next step is to then pick a feature to split on."}, {"start": 167.6, "end": 172.4, "text": " So we then go through the features one at a time and compute the information gain of"}, {"start": 172.4, "end": 180.08, "text": " each of those features as if this node were the new root node of a decision tree that"}, {"start": 180.08, "end": 186.54, "text": " was trained using just five training examples shown here."}, {"start": 186.54, "end": 191.35999999999999, "text": " So we would compute the information gain for splitting on the whiskers feature, the information"}, {"start": 191.35999999999999, "end": 196.56, "text": " gain on splitting on the face shape feature, and it turns out that the information gain"}, {"start": 196.56, "end": 202.66, "text": " for splitting on ear shape will be zero because all of these have the same pointy ear shape."}, {"start": 202.66, "end": 209.32, "text": " And between whiskers and face shape, face shape turns out to have a highest information"}, {"start": 209.32, "end": 214.76, "text": " gain, so we're going to split on face shape and that allows us to build left and right"}, {"start": 214.76, "end": 217.35999999999999, "text": " sub-branches as follows."}, {"start": 217.35999999999999, "end": 222.62, "text": " And then for the left sub-branch here, we check for the stopping criteria and we find"}, {"start": 222.62, "end": 226.92, "text": " that it is all cats, so we stop splitting and build a prediction node that predicts"}, {"start": 226.92, "end": 232.56, "text": " cat and for the right sub-branch, we again check the stopping criteria and we find that"}, {"start": 232.56, "end": 237.44, "text": " it is all dogs and so we stop splitting and have a prediction node."}, {"start": 237.44, "end": 241.84, "text": " So for the left sub-branch, we check for the criteria for whether or not we should stop"}, {"start": 241.84, "end": 248.0, "text": " splitting and we have all cats here and so the stopping criteria is met and we create"}, {"start": 248.0, "end": 253.26, "text": " a leaf node that makes a prediction of cat and for the right sub-branch, we find that"}, {"start": 253.26, "end": 259.76, "text": " it is all dogs and so we will also stop splitting since we've met the splitting criteria and"}, {"start": 259.76, "end": 264.28000000000003, "text": " put a leaf node there that predicts not cat."}, {"start": 264.28000000000003, "end": 269.76, "text": " So having built out this left subtree, we can now turn our attention to building the"}, {"start": 269.76, "end": 270.76, "text": " right subtree."}, {"start": 270.76, "end": 276.59999999999997, "text": " Let me now again cover up the root node and the entire left subtree."}, {"start": 276.59999999999997, "end": 281.2, "text": " To build out the right subtree, we have these five examples here and again, the first thing"}, {"start": 281.2, "end": 286.4, "text": " we do is check if the criteria to stop splitting has been met."}, {"start": 286.4, "end": 291.56, "text": " The criteria being whether or not all the examples are single class, we've not met the"}, {"start": 291.56, "end": 298.2, "text": " criteria and so we'll decide to keep splitting in this right sub-branch as well."}, {"start": 298.2, "end": 302.59999999999997, "text": " And in fact, the procedure for building the right sub-branch will be a lot like as if"}, {"start": 302.59999999999997, "end": 307.68, "text": " you were training a decision tree learning algorithm from scratch where the data set"}, {"start": 307.68, "end": 313.08, "text": " you have comprises just these five training examples."}, {"start": 313.08, "end": 319.15999999999997, "text": " And so again, computing information gain for all of the possible features to split on,"}, {"start": 319.15999999999997, "end": 324.08, "text": " you find that the whiskers feature gives the highest information gain."}, {"start": 324.08, "end": 328.56, "text": " So these are the set of five examples according to whether whiskers are present or absent,"}, {"start": 328.56, "end": 334.71999999999997, "text": " check if the criteria to stop splitting are met in the left and right sub-branches here"}, {"start": 334.71999999999997, "end": 340.36, "text": " and decide that they are and so you end up with leaf nodes that predict cat and not cat."}, {"start": 340.36, "end": 346.64, "text": " And so this is the overall process for building the decision tree."}, {"start": 346.64, "end": 352.44, "text": " Notice that there's an interesting aspect of what we've done, which is after we decided"}, {"start": 352.44, "end": 360.2, "text": " what to split on at the root node, the way we built the left sub-tree was by building"}, {"start": 360.2, "end": 367.08, "text": " a decision tree on a subset of five examples and the way we built the right sub-tree was"}, {"start": 367.08, "end": 372.36, "text": " by again building a decision tree on a subset of five examples."}, {"start": 372.36, "end": 379.48, "text": " In computer science, this is an example of a recursive algorithm and all that means is"}, {"start": 379.48, "end": 385.0, "text": " the way you build a decision tree at the root is by building other smaller decision trees"}, {"start": 385.0, "end": 389.48, "text": " in the left and the right sub-branches."}, {"start": 389.48, "end": 395.6, "text": " So recursion in computer science refers to writing code that calls itself and the way"}, {"start": 395.6, "end": 401.62, "text": " this comes up in building a decision tree is you build the overall decision tree by"}, {"start": 401.62, "end": 407.0, "text": " building smaller sub-decision trees and then putting them all together."}, {"start": 407.0, "end": 412.52, "text": " So that's why if you look at software implementations of decision trees, you see sometimes references"}, {"start": 412.52, "end": 415.68, "text": " to a recursive algorithm."}, {"start": 415.68, "end": 420.16, "text": " But if you don't feel like you fully understood this concept of recursive algorithms, don't"}, {"start": 420.16, "end": 421.16, "text": " worry about it."}, {"start": 421.16, "end": 426.7, "text": " You'll still be able to fully complete this week's assignments as well as use libraries"}, {"start": 426.7, "end": 429.72, "text": " to get decision trees to work for yourself."}, {"start": 429.72, "end": 435.84, "text": " But if you're implementing a decision tree algorithm from scratch, then a recursive algorithm"}, {"start": 435.84, "end": 440.23999999999995, "text": " turns out to be one of the steps you'd have to implement."}, {"start": 440.23999999999995, "end": 444.91999999999996, "text": " And by the way, you may be wondering how to choose the maximum depth parameter."}, {"start": 444.91999999999996, "end": 449.44, "text": " There are many different possible choices, but some of the open source libraries will"}, {"start": 449.44, "end": 453.62, "text": " have good default choices that you can use."}, {"start": 453.62, "end": 459.23999999999995, "text": " One intuition is the larger the maximum depth, the bigger the decision tree you're willing"}, {"start": 459.23999999999995, "end": 460.52, "text": " to build."}, {"start": 460.52, "end": 466.2, "text": " And this is a bit like fitting a higher degree polynomial or training a larger neural network."}, {"start": 466.2, "end": 472.28, "text": " It lets the decision tree learn a more complex model, but it also increases the risk of overfitting"}, {"start": 472.28, "end": 476.08, "text": " if it's fitting a very complex function to your data."}, {"start": 476.08, "end": 481.59999999999997, "text": " In theory, you could use cross-validation to pick parameters like the maximum depth where"}, {"start": 481.59999999999997, "end": 486.56, "text": " you try out different values to the maximum depth and pick what works best on the cross-validation"}, {"start": 486.56, "end": 487.56, "text": " set."}, {"start": 487.56, "end": 492.08, "text": " But in practice, the open source libraries have even somewhat better ways to choose this"}, {"start": 492.08, "end": 493.6, "text": " parameter for you."}, {"start": 493.6, "end": 499.52, "text": " Or another criteria that you can use to decide when to stop splitting is if the information"}, {"start": 499.52, "end": 504.64, "text": " gain from an additional split is less than a certain threshold."}, {"start": 504.64, "end": 510.4, "text": " So if any feature you split on achieves only a small reduction in entropy or a very small"}, {"start": 510.4, "end": 514.78, "text": " information gain, then you might also decide to not bother."}, {"start": 514.78, "end": 519.8199999999999, "text": " And finally, you can also decide to stop splitting when the number of examples in the node is"}, {"start": 519.8199999999999, "end": 521.92, "text": " below a certain threshold."}, {"start": 521.92, "end": 525.36, "text": " So that's the process for building a decision tree."}, {"start": 525.36, "end": 529.36, "text": " Now that you've learned the decision tree, if you want to make a prediction, you can"}, {"start": 529.36, "end": 533.56, "text": " then follow the procedure that you saw in the very first video of this week where you"}, {"start": 533.56, "end": 539.3399999999999, "text": " take a new example, say a test example, and start at the root and keep on following the"}, {"start": 539.3399999999999, "end": 544.68, "text": " decisions down until you get to a leave node, which then makes the prediction."}, {"start": 544.68, "end": 548.92, "text": " Now that you know the basic decision tree learning algorithm, in the next few videos,"}, {"start": 548.92, "end": 552.9599999999999, "text": " I'd like to go into some further refinements of this algorithm."}, {"start": 552.9599999999999, "end": 558.38, "text": " So far, we've only used features that take on two possible values, but sometimes you"}, {"start": 558.38, "end": 563.8399999999999, "text": " have a feature that takes on categorical or discrete values, but maybe more than two values."}, {"start": 563.84, "end": 575.36, "text": " Let's take a look in the next video at how to handle that case."}]