Sign in to continue learning
Advanced Learning Algorithms
33 hours 27 mins
Welcome to the final week of this course on advanced learning algorithms. One of the learning algorithms that's very powerful, widely used in many applications, also used by many to win machine learning competitions, is decision trees and tree ensembles. Despite all the successes of decision trees, they somehow haven't received that much attention in academia, and so you may not hear about decision trees nearly that much. But it is a tool well worth having in your toolbox. So in this week, we'll learn about decision trees and you'll see how to get them to work for yourself. Let's dive in. To explain how decision trees work, I'm going to use as a running example this week a cat classification example. You're running a cat adoption center, and given a few features, you want to train a classifier to quickly tell you if an animal is a cat or not. I have here 10 training examples, and associated with each of these 10 examples, we're going to have features regarding the animal's ear shape, face shape, whether it has whiskers, and then the ground truth label that you want to predict is, is this animal a cat? So the first example has pointy ears, a round face, whiskers are present, and it is a cat. The second example has floppy ears, the face shape is not round, whiskers are present, and yes, that is a cat. And so on for the rest of the examples. This data set has five cats and five dogs in it. And the input features, X, are these three columns, and the target output that you want to predict, Y, is this final column of is this a cat or not. In this example, the features X take on categorical values. In other words, the features take on just a few discrete values. Ear shapes are either pointy or floppy, the face shape is either round or not round, and whiskers are either present or absent. And this is a binary classification task, because the labels are also 1 or 0. For now, each of the features, X1, X2, and X3, take on only two possible values. We'll talk about features that can take on more than two possible values, as well as continuous value features later in this week. So what is a decision tree? Here's an example of a model that you might get after training a decision tree learning algorithm on the data set that you just saw. The model that is output by the learning algorithm looks like a tree, and a picture like this is what computer scientists call a tree. If it looks nothing like the biological trees that you see out there to you, it's okay, don't worry about it. We'll go through an example to make sure that this computer science definition of a tree makes sense to you as well. Every one of these ovals or rectangles is called a node in the tree. And the way this model works is if you have a new test example. Here's a cat where the ear shape is pointy, face shape is round, and whiskers are present. The way this model will look at this example and make a classification decision is, we'll start with this example at this topmost node of the tree. This is called the root node of the tree. And we will look at the feature written inside, which is ear shape. Based on the value of the ear shape of this example, we'll either go left or go right. The value of the ear shape of this example is pointy, and so we'll go down the left branch of the tree like so, and end up at this oval node over here. We then look at the face shape of this example, which turns out to be round. And so we will follow this arrow down over here, and the algorithm will make an inference that it thinks this is a cat. And so you get to this node, and the algorithm will make a prediction that this is the cat. What I've shown on this slide is one specific decision tree model. To introduce a bit more terminology, this topmost node in the tree is called the root node. And all of these nodes, that is, all of these oval shapes, but excluding the boxes at the bottom, all of these are called decision nodes. And decision nodes, because they look at a particular feature, and then based on the value of the feature, causes you to decide whether to go left or right down the tree. Finally, these nodes at the bottom, these rectangular boxes, are called leaf nodes, and they make a prediction. If you haven't seen computer scientists' definitions of trees before, it may seem non-intuitive that the root of the tree is at the top, and the leaves of the tree are down at the bottom. Maybe one way to think about this is this is more akin to an indoor hanging plant, which is why the roots are up top, and then the leaves tend to fall down to the bottom of the tree. In this slide, I've shown just one example of a decision tree. Here are a few others. This is a different decision tree for trying to classify cat versus not cat. In this tree, to make a classification decision, you would again start at this topmost root node, and depending on the ear shape of an example, you go either left or right. If the ear shape is pointy, then you look at the whiskers feature, and depending on whether whiskers are present or absent, you go left or right again and classify cat versus not cat. And just for fun, here's a second example of a decision tree, here's a third one, and here's a fourth one. And among these different decision trees, some will do better and some will do worse on the training set or on the cross-validation and the test sets. So the job of the decision tree learning algorithm is, out of all possible decision trees, to try to pick one that hopefully does well on the training set, and that also ideally generalizes well to new data, such as your cross-validation and test sets as well. So it seems like there are a lot of different decision trees one could build for a given application. How do you get an algorithm to learn a specific decision tree based on a training set? Let's take a look at that in the next video.