Skip to main content
Loading Explore guides…
Decision Trees · Acedra
Home
Explore
Computer Science
Decision Trees
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
255 segments
Copy
Hide video
0:00
Okay it's about that time, let's go ahead and get started. So in the past many lectures now, not even just the last lecture, we've been building up a lot of neural nets. So first, I think around lecture six, we introduced neural nets: we'd built on linear regression and logistic regression, we built up to neural nets where we transformed the features and then we developed convolutional
0:25
neural nets not too long after that as a way to deal with vision style problems. Then we developed recurrent neural nets not too long after that as a way to deal with things with an inherent, maybe,
0:39
time structure or recursion structure, something that you might see in language, for instance, where you're building up words and so I think at this point, you could really reasonably think based on the structure of the course that the whole course is building up to neural nets and neural nets are like the epitome of machine learning and that's all you should ever use for every machine learning problem and part of that sentence is correct. So there's a very real
1:02
sense in which it's natural to build neural nets from things like logistic regression,
1:07
they add extra elements like learning features. It's natural to build convolutional neural nets and recurrent neural nets from when we've learned about neural nets and these are certainly super important methods, they've really revolutionized a lot of applications especially in things like vision. We might use a lot of these ideas in maybe natural language processing but what's incorrect about my previous statement is that you should use these on every machine learning problem.
1:36
It's more realistic to think that what we're doing is we're building a toolbox and these are part of that toolbox. They're very useful and an important part but there are other aspects of that toolbox. So just because we did linear regression and logistic regression first doesn't mean that only silly people use them. Absolutely people use them all the time to this day and to great effect and we're going to see today some more elements, some more
1:58
machine learning tools that should probably be in your toolbox as you go forward. In particular, if you care about interpretability, decision trees are a really important part of your toolbox and if you care purely about predictive performance, then ensembles and random forests are really important parts of your toolbox, so we'll spend some time talking about each of these methods today.
2:20
Okay so first let me just spend a little time hopefully convincing you that predictive performance isn't everything, that there are things that we really do care about beyond pure predictive performance or perhaps we just need to rethink what we mean by predictive performance. But an example of this I think is very timely it's election audits. So if you looked in the news very recently, but here's actually an article from back in October even before the election,
2:47
election audits are a very important item that people are talking about. 46 states, at least according to this article in October, have some auditing regime in place to just double check if there is some kind of user error or some kind of technical glitch or whatever, but this isn't a new idea of auditing elections. So here's a paper from 2008 that's been very influential actually. The article, the news article on the left, was
3:15
talking to Philip Stark who wrote this article in 2008 and has been doing a lot of work in election auditing. And I'll also mention Ron Rivest in our department, he’s at MIT, and has also been doing a lot of work in election auditing. It's a pretty cool area and gets into some math. But here's a quote that I really want to excerpt from this 2008 article which is “the choices that this researcher made, he made them to simplify the exposition and implementation;
3:41
his methods needed to be transparent to be adopted as part of the election process and to inspire public confidence. He thought about using methods that are more familiar to data analysts and they might be more efficient (in fact, they probably are), but because of their complexity, they'd likely meet resistance from elections officials and voting rights groups.” And so I think this is a nice explanation of why we sometimes need methods that maybe don't reach
4:08
the absolute peak of something like predictive performance or some other notion of goodness. Well it might be that we just need to explain them to people and I think it's not just that everybody's being silly and we should all accept neural nets as our new overlords. There are plenty of reasons that we should want these good explanations. I mean one is that there are reasons to be skeptical
4:30
of methods you don't understand. So lots of folks right now seem to say they have machine learning solutions and maybe they're selling snake oil sometimes and so if you're not a machine learning expert being able to distinguish between those items might require some kind of interpretability. But it's not just about whether you have expertise or not. Even if you're a machine learning expert,
4:49
you probably actually care about interpretability. So here, here's an example you can read in this paper of a case where machine learning experts ran neural nets and also more interpretable models on this problem where they were interested in what is the risk of death from pneumonia from patients. So this was in a medical context and the interpretable model had a very clear step: if the patient… Once they got all of their methods out, they have the neural net and it's like “okay,
5:18
here I have a neural net. What do I do with this?” But the interpretable model very clearly and precisely stated “hey, if somebody is a patient with asthma and pneumonia at the same time, then they have lower risk of death from pneumonia.” And so that's the thing that, even if you don't have a lot of medical expertise but certainly if you do have medical expertise, you might think that seems pretty silly that somebody who has asthma would probably be at
5:44
higher risk for pneumonia. And because they have this interpretable model, they could say “hey, something is going on here, that's a little bit weird, let's dig into it more” and, in fact, it turned out the reason that was this was happening was that the patients with asthma and pneumonia were being admitted to the ICU because they were deemed to be such high risk. They got aggressive care that decreased their risk of dying and so this is an example of something that you've seen
6:06
earlier in the semester: Simpson’s paradox. So you might want to check when that thing is going on and now you are aware already from the semester of Simpson's paradox, but now you have an ability, maybe if you have an interpretable model, to see that that might be happening. Another nice thing about interpretable models is that there's less room for human error. So if you look at Malcolm
6:28
Gladwell's “Blink” book, there's an example of Dr. Brendan Reilly, the chairman of the Department of Medicine at Cook County Hospital in Chicago. He was facing resource shortfalls (they have lots of poor patients that they're treating) and they needed a way to diagnose heart attacks in patients that were presenting with chest pains, who came in and had chest pains. It was quick and accurate and so they end up using exactly the method we're about to talk about, a decision tree,
6:50
but here you could say they care about predictive performance, like they care about accurately diagnosing each person who comes in, but the problem is that the machine learning method isn't exactly the method that they're using. They're using a person using the machine learning method and so that's not the kind of thing that you're testing when you're testing cross validation, when you're looking at test set error. That's actually an extra element of the system
7:14
beyond the pure method and so that's a reason, at least on the face of it, if you can't do more that you might care about something that's very simple to use so humans don't mess it up when they're using it. Okay, so a lot of reasons to care about interpretability, about things beyond predictive performance. It doesn't even just have to be interpretability although that's what I've been focusing on here. But even if you only care about predictive performance, you
7:37
should care about today's lecture, you should care about trees, because trees are part of the things that have the best predictive performance in many cases. So if you look at this Kaggle (Kaggle is a subsidiary of Google LLC but it also runs machine learning competitions among other things) and there was this magazine that recently in March did an interview with a Kaggle master ranked 19th
7:59
in the global Kaggle competitions leaderboard and what's interesting is they say what's his toolkit. And if you look at these algorithms in his toolkit, lightgbm, xgboost, catboost, these are all ensembles of trees. And so while neural nets can be really useful again for things like vision and NLP and so on, the reality is for a lot of the data that you're going to encounter, ensembles of trees are basically the thing that really does the best in terms of predictive performance.
8:29
Okay so at this point, hopefully, you're motivated to hear about what is a tree and what is an ensemble of trees and so that's what we're gonna do today.
8:38
Okay, so let's start with what is the decision tree. Well decision tree is basically just a presentation of a series of decisions in a tree. So let's let's start with that and then we'll nail down exactly what it is. So let's say that I have someone coming in,
8:53
maybe they came in with a heart attack. And we know after the first 24 hours whether they've had a heart attack, they've been in the hospital over 24 hours, and now we want to assess their risk in order to decide on their follow-up treatment. And so here is a tree that people actually in the early days of decision trees presented, which is the following series of decisions. So first we asked, let's look at a particular type of blood pressure, systolic blood pressure over the last
9:19
24 hours, and asked: did it really dip down very low? Was it always greater than or equal to 91? So we have two choices: either yes or no. So if no, if it was, if it did dip down below 91, then this patient is considered high risk. If yes, then we're going to ask another question. The question is: is their patient age greater than or equal to 65? And a patient who is a bit older might be riskier, so if this patient has an age less than 65,
9:49
then we might just consider them low risk at this point, they're probably going to be okay.
9:53
But if they're greater than 65, we have yet another question. We're going to ask: is sinus tachycardia present? For the purposes of this lecture, let's just say that this is a medical thing that you can measure and you can check and you can check if it's present. It either is or it isn't. If it is not, then this patient is low risk. If it is, this patient is high risk. And so here is just a series of decisions, a series of yes or no questions that, even if you don't have
10:17
medical expertise, if you're provided with the appropriate data, you can just go through these and answer them. Okay so this is a nice little flowchart, but it's maybe not clear in this form how it relates to everything we've talked about in the class. So let's turn this into something that we can actually talk about in the words and the phrasing and the terminology of this class. Okay,
10:39
so let's imagine in real life we have a bunch of data. You can imagine each individual who walks in and is around for 24 hours after a heart attack is a data point and we have various features associated with those individuals like the date that they were admitted, their age, their height, their weight, was sinus tachycardia present , and the minimum systolic blood pressure over 24 hours,
11:00
and maybe their latest diastolic blood pressure, and maybe even there were some other features.
11:05
Okay. So actually, we can see each of these internal nodes in this tree as being some kind of cut or split on one of these features. So in particular, minimum systolic blood pressure over 24 hours, that's actually our sixth feature in this case. So we can write this as x_6 >= 91. Is this true? We'll go to the right-hand child if it's false, we'll go to the left-hand child. Okay, we can do the same thing with age. Age is our second feature
11:36
so we can actually rewrite this as x_2 >= 65. If it's true, then we'll go to the right hand child. If it's false we'll go to the left-hand child. Is sinus tachycardia present? Well this depends on how we encode this. A typical way that we might encode, as we've seen, a binary variable, binary classes is either 0 or 1 or -1 or 1. Either case, 1 is probably going to be the yes and so we'll ask: is x_5 >= 1? And so here, now, we have our decision tree
12:09
in terms of our features. Now typically, what we do here is we do some kind of classification or regression. Hopefully it's clear that this looks like classification, that we're trying to classify into two classes: high or low risk and so we might give them labels. A typical thing we've done in this class is give them labels like 0 or 1 or -1 or 1 and so here we're doing that: we're having 1 be high risk and -1 be low risk and so here we are, so we can change this into
12:36
our labels. And so at this point, basically, we have created a classifier or, in general, a predictor. And so let's just double check that that's true, that in fact this is a classifier. Oh and before we do that, let's finish up saying what exactly is the decision tree, what counts as a decision tree? Well it's going to be a binary tree with internal nodes and leaves. The internal nodes, each one of them, is going to be defined by a dimension index j and a
13:05
split value s. So for instance, if I look at this node, so this is one of the internal nodes (I've color coded the internal nodes here as being white and the leaves as being green), so this is an internal node. It has a dimension index that we're splitting on, that's j. In this case, j is 6. It has a split value s that we're splitting on. In this case, that split value is 91. And then it has
13:27
two child notes and each one of them can either be internal or leaf nodes. And then the leaf nodes,
13:35
so this one's a leaf node, this one's an internal node. Now the leaf nodes are defined just by their label. So we get to a leaf node, that's the end. It's not going to have any children but it does have some kind of label and that's what we're going to predict at that label.
13:50
Okay so as we said, this is a classification tree. This is doing classification as its form of decision. And now, we can say that we have defined a classifier just like we've done in the past for logistic regression, for neural nets, for any of the things that we've been looking at.
14:07
And let's just check that that's true. So here, let's suppose we have a data point that comes in. So a person comes into the hospital. That person has a bunch of features associated with them, again: the date, the age, the height, the weight, is sinus tachycardia present, systolic blood pressure, latest diastolic blood pressure. And now we're going to ask ourselves: how would we classify this data point? So in order to check “what does this predictor look like” on
14:35
our particular data point, we're basically going to run through the decision tree. So first, we're going to ask: is x6, is the sixth feature for this data point, greater than or equal to 91.
14:47
So here's the sixth feature. In this case, it's 115, so it's greater than or equal to 91, so we say yes. So now we go to the next decision:
14:57
is x_2 >= 65? Is the person older than 65? And we check this person's age, it's 49, they're not older than 65, so we go to no. And now we're to a leaf and so as soon as we get to a leaf, that is our prediction. In this case, it's -1: we say this person is low risk.
15:18
Okay so this is a classification tree. We can use it to make classifications. You'll notice that it does not have to use absolutely every feature. We're going to see later that, actually, features can repeat too, we can have things like that, but it is a binary tree of decisions, a finite binary tree of decisions, that eventually gives us some kind of classifier. And of course, we can do the same thing for regression, it doesn't
15:41
have to just be classification, so let's take a look at a regression tree. So here, instead of a medical example, let's have an example that we actually visited way back when we were talking about neural nets. So here our example could be: when am I going to run? Where and how much am I going to go for a run? And maybe my two features that I use to decide this are temperature and precipitation. So how cold is it and is it raining, how much is it precipitating out there?
16:12
And my label could be kilometers run. Okay so what are we gonna do here?Sso we're gonna again start with the decision, say in this case, x_2 >= 0.3? Basically, is there a lot of precipitation? In which case, we'll go to yes. Or is there not so much precipitation? In which case we'll go to no.
16:34
Okay well if there's a lot of precipitation, maybe it turns out that I just go inside and I go on the treadmill and I don't want to run as much and so I run, let's say three kilometers.
16:44
If there's not so much precipitation, I'm gonna ask: is it cool? So we'll have x_1 >= -5 and maybe I say if it's cold, so if there's a no here, then again I'm gonna go on the treadmill. I'm not gonna run maybe as long, maybe it'll be two kilometers. If it's yes, maybe I'll ask is it warm, is it way too warm? Is x_1 >= 33? So if it's very warm or if, first, if it's in intermediate temperature,
17:11
so it's not too cold and it's not too hot, maybe I'll go outside and I'll run and I'll run a good five kilometers. But if it's very warm, I don't feel like doing anything and so maybe I'll just run 0. So in this case, what's different between a regression and a classification tree, we're seeing that in the regression, all the decisions and the intermediate part are totally the same as before, the only difference is the labels are real valued now. So this is like the difference
17:34
between regression and classification, in general, that you have a predictor that's real valued instead of a predictor that's just one class or the other or multiple classes is also fine.
17:47
Okay, so something to note here and this is not specific to regression or classification, this is generally true for these decision trees, that the tree itself defines an axis-aligned partition of the feature space. So let's dig into what all of those words mean by first seeing what happens when we use this tree.
18:08
Okay so first, when we get to the root node, first we have all of the feature space. So in this case, that's x_1 > 0. Sorry, x_1 is any value because we can have any value in degrees Celsius. I mean technically speaking there's a lower limit to that but basically all the allowable degrees Celsius. Then x_2 has to be greater than zero because it's precipitation. Can't usually have negative precipitation. And so we have some whole feature space that's here in orange.
18:47
Okay so now we're going to look at the first split here. So the first split is saying: let's look at x_2 >= 0.3. And so what we're doing with this feature space is we're saying, “hey, we're going to split it into two parts with a line.” So this is x_2 = 0.3, the line. There's a part where x_2 is greater >= 0.3, in which case we go
19:12
to the right child and there's a part where x_2 < 0.3, in which case we go to the left child.
19:20
Okay, now in this case, when we go to the left child, there's actually another decision, another split. And so when we're splitting, you can really think of the split as being applied to this feature space. We're actually making a split in this feature space. So in particular here, now what we're going to do is we're going to take only the space where x_2 < 0.3
19:40
and we're going to split it with x_1 = -5. So you'll notice this line only applies when x_2 < 0.3. It's like we've already restricted ourselves to the x_2 < 0.3 space. And on one side we have x_1 < -5 and on the other side we have x_1 >= -5.
20:00
Okay so now, again, we say: where are we in the space right now, moving down this regression tree?
20:07
And then I'm going to finish this up and then I'll do the question. So then we have our x_1 >= 33 split. So again, we're going to split up our space so we have x_1 = 33 on one side, we'll have x_1 < 33 but it also conforms to all of the other constraints we've imposed so far. So this is the set right here where x_2 < 0.3, x_1 > -5 and x_1 < 33 and on this side, we have the same two first set of constraints and then x_1 > 33. Okay so the question is: how could regression trees
20:49
generate labels with a continuous number when we have a binary split node? And so what's happening is that the binary split node is just partitioning the space as we're seeing here but the continuous value that you actually say is your regressor, that you actually say is my prediction at a particular point, is the value in the leaf node and so here I've got kind of lazy and I put those values as 3, 2, 5 and 0. If I had been slightly less lazy, I could make them more obviously
21:19
real valued, like maybe sometimes I run 3.2 kilometers and sometimes I run 5.1 kilometers, but the idea of regression is just that you are predicting a continuous value and so as long as you are allowing a continuous value in your leaf nodes, you are doing regression. Another way to think about that is what's happening in regression is that, for every value in your feature space, you are predicting a continuous value and so what we're actually seeing here in this little plot
21:53
that I put in the lower right hand corner, is our feature space and if you think of this as being a three-dimensional plot where the y label is coming out of the slides at you, then this would actually be, you could have that y label and then you would have your regression values which, in the case of orange is 3, in the case of red is 2, in the case of blue is 5, and in the case of purple is
22:22
0 and so if we could imagine rotating that and then you would actually see this step function that we're predicting and so the difference with classification is just that you're only allowing,
22:33
in the case of two value classification, those two values, but if you were doing three value of classification, multi-class classification, you wouldn't be putting that on a y-axis, you would be saying it's like a, b and c is what you're predicting and you wouldn't just plot those on the same thing because as we saw before having this is back in lecture three with our features, we saw that having multi-classes isn't the same as having an ordering like 1,
22:55
2, 3 because there's no ordering on those classes and see that's where I think you can really see that there's a difference in what you do with the classification and regression.
23:07
Now that being said, I think this observation about the binary split node is key because it tells you that we're really doing a simple type of regression: we're not getting a really different
23:19
prediction from one point to the next, we're really doing a step function as our regression. Now I said in the beginning of this slide or earlier in the slide, I would say, what is an axis aligned partition. So let me just say that now. So a partition is when you have a bunch of mutually exclusive and exhaustive sets. That is to say the sets are all separate, they don't overlap, and when you take their union, they all become the
23:43
whole space. And so that's what we're seeing here is that we've taken up the space of x_1 and x_2, our feature space, and we divided it up. That's all you're doing, the partition: you're dividing it up into little subspaces and so we have basically four here is what we've done and each one of those we're going to predict something different. Now two things that are worth noting about this one, this is why we end up getting this step function because we're just,
24:06
in this case, predicting a constant value. Now you don't have to do that in regression trees, you could do something else at the nodes, but here we're just going to do a constant value.
24:14
The other thing to notice is that these are axis aligned by our choice of splits. Our splits are we take one dimension and we split it a particular value and so we're always going to get these lines as our dividers that are parallel to one of our axes like x_1 or x_2 in this case. Again, that's something that you could try to go beyond, but that one's a lot harder to go beyond in a reasonable way that actually gives you useful predictions but it is something that you can do.
24:44
Great okay. So now, we've talked about two different types of decision trees: we've talked about classification trees, we've talked about regression trees and, in a way, you can think of what we've done so far as describing the forward mode of these. We talked, when we were talking about neural nets, about the forward run of the model and then going backwards through it and so here what we're doing is we're saying, “hey, if I have a decision tree and I have a data point,
25:15
I can tell you the prediction, I know how to do that and we've talked through that now.”
25:21
Okay and that's step one of our familiar pattern. So at this point, hopefully this is becoming so old as to be boring (you totally know the familiar pattern and you're really familiar with it), so step one: we have to choose how to predict a label. So if we're given a set of features and a predictor, which is defined by parameters, and we'll say in a moment what is a natural way to think about parameters here, but given features and parameters, we know how to predict a label. So
25:51
we just saw that with decision trees: we looked through an example and the medical example of “suppose I have a data point, what'll I do to predict whether this person is high risk or low risk?” We could do the same thing here: if I have a day that is 20 degrees Celsius and there's zero precipitation, I can go to the top. I say there's zero precipitation, so I go to no. It's 20 degrees celsius so I'll go all the way down to the bottom and I'll say I'm gonna run
26:15
five kilometers. Okay so we know how to predict a label given a set of features and parameters. The next thing that we do is we choose a loss, a loss between our guess and our actual label. So we'll just do that in a moment of course. That will depend on whether we're doing regression or classification, that will depend on what type of thing we're doing with regression and classification, but it's something that we'll choose and
26:36
then finally we somehow choose parameters by trying to minimize the training loss.
26:43
Okay so what are the parameters here? Well the parameters are typically the thing that describes
26:50
what is our predictor and so, in this case, we have a bunch of unknowns. We want to say, for each internal node, what is the split dimension.
27:00
We want to say for each internal node what is the split value. So again, for x_2 >= 0.3, the split dimension is 2, the split value is 0.3, so those together will define what's going on at that internal node, what am I going to do, how am I going to make my decision. But I also need to say: what are the two children notes? Is there one leaf and one internal node? Is there one internal node
27:23
and one leaf in the other direction? Are there two leafs? Are there two internal nodes? These are all possibilities and we need to say which it is and then for each leaf node we have to say the label. So what we're gonna do in a moment is we're going to come up with a waym once we've chosen a loss, to choose all of these parameters by trying to minimize the training loss.
27:42
Now something that's worth noting here that's a bit different from things we've done in the past, hopefully immediately different if you think back to linear regression or logistic regression, but actually really different from most of the things we've done, is that the parameters here don't have a fixed dimension. So as soon as I make an internal node, if that has two children that are internal nodes, now I suddenly have a bunch more parameters.
28:02
And if they have internal nodes as children, now I have a bunch more parameters. In fact, you can get more and more parameters this way so that's a bit different than what we've done in the past.
28:13
Okay so let's suppose that I'm going to do regression, I'm going to choose to do regression
28:18
and I'm going to choose squared error loss because that's a really natural thing that I might do for regression. Well hey, squared error loss, we've talked before about how if I were doing
28:29
something with squared error loss, I might try to set up everything in my problem so that's all differentiable and run gradient descent or stochastic gradient descent. And that's just not going to happen here. So a couple of things to note. One, we certainly haven't talked about how you would do gradient descent or stochastic gradient descent if you don't have a fixed dimension parameter. That sounds like it might be hard.
28:52
Two, this is definitely a super not differentiable structure. So if I'm trying to decide whether to add an internal node or not, that's at least, on the face of it, not differentiable, that's just a very discreet decision and so it's really not clear that I could apply something like gradient descent or stochastic gradient descent which really relies on there being differentiability in all of my parameters, that my loss, my overall objective is
29:16
differentiable in all my parameters. And so we're going to have to think about what could we do.
29:20
Well, we could go back to our roots. Way back at the very beginning of this class, we used a heuristic, the perceptron. We don't always have to use gradient descent and stochastic gradient descent, I mean even when they're available, we don't always have to use them. And so in this case, we're going to look at a heuristic. It's going to have two parts: we're going to build up a tree, we're going to think of it
29:43
as growing the tree, and then we're going to prune it back, so take away parts of the tree. This is a particular way, it's a very classical way to build the decision tree. I kind of want to emphasize that just like many things we've talked about in this class, this is not the only way to make one, there are definitely other ways you can make a decision tree and I think, in some ways, what's really important to understand is the simplicity of the ultimate decision tree that you get
30:08
is very useful, it's very understandable, it's the kind of thing that you could present to somebody who's an expert in another area who isn't an expert in machine learning. You could have an extremely smart medical practitioner and that doesn't mean that they know about neural nets so this is something you can easily talk about with them. If you're serving on a jury and you're participating in your civic duty on a jury, a tree is something that you could explain
30:32
to your fellow jury members. And so that simplicity is separate from what we choose to learn it and now we're going to talk about here's an algorithm that you might use to learn it but again not the only thing you could do. Okay so again we're going to talk about these two steps: building it up and putting it back. Okay so let's first start by talking about building a decision tree and as just a motivating example, let's imagine that we have some toy data over here
31:04
and it is running times based on the, again, temperature and precipitation. So x_1 is the temperature. It's very cold, maybe I'm not running. When it's very warm, I'm not running. And then, x_2 is the precipitation. When it's precipitating a lot, I'm not running, but when you get that nice temperature and there's not a lot of precipitation, then I'm running and maybe it's something like five kilometers. And we're gonna think of this
31:29
as a regression problem. Again, if I put a little more time into this, these could be numbers like, realistically, I might run like 5.2 kilometers or 4.9 kilometers. So you can think of these as being values that really do vary continuously and we're trying to learn a regression tree.
31:45
Okay so if we're trying to learn a regression, again a really natural loss is squared error loss. So let's just go ahead with squared error loss for the moment. It depends on what you're trying to do in general and it's not always the right choice for regression but for here it's certainly convenient and we might just go ahead with it. So let's suppose we're building a regression tree with squared error loss. Okay so we're going to build our tree
32:07
and it's going to take two inputs: one, it's going to take a collection of data indices. What do I mean by that? Well the first thing that we're always going to do when we run BuildTree is we're going to run it on our training data. And so here “I”, the collection of indices that we put in, will be the indices of our training data: training data point 1, 2 up to n, assuming we have n training data points. Now why would we bother making that an input to BuildTree?
32:34
Well the problem is we're going to be doing it recursively later with just a subset of the data and so that's why we want to make that an input. We'll see that that's important as we go along.
32:44
Okay next we have k. So k is going to be a hyper parameter of this algorithm. It's going to be the minimum number of points that we allow in a tree branch or in a leaf. So basically, as soon as we get down to two points, we're gonna stop, we're gonna say we're done. We're not gonna go down to allowing a leaf with just, say, one point in it.
33:14
According to the algorithm we're about to build up, I think it's actually the maximum number that we're gonna allow. I take that back yeah. Okay the point is we're not going beyond two. Okay so our first question: because we're not going beyond two points, we're not letting ourselves have more than two points in a branch, we're going to ask ourselves, “okay, is the number of data points that we're looking at right now greater than or equal to 2?”
33:40
Okay, wellm let's start asking that. This is a real question for the chat. I'm looking at the number of data points when I run this. I'm gonna run exactly BuildTree 1 to n on the dataset that I have right here. So this is a dataset that I'm illustrating with the 0s and 5s. I'm gonna run this BuildTree. What is the number of data indices? So that absolute value “I” means the number of things in the set. So I'm asking, for the chat,
34:14
what is the absolute value of “I” here? What are the number of things in the set of indices?
34:22
Okay I'm getting great answers from both directions. So some people are answering in full generality, which is great. In that case, the answer is n: there are clearly n things in this index set. And if you did answer in full generality, I'll ask you to also think about what is the number n for this particular dataset that we're illustrating here?
34:49
Great, so just to recap: in this dataset, just to be really clear about how I'm labeling things, so I'm at a particular x_1 and x_2 point. If there's a point, I'll put a number and that number is the regression number. So it's like, oh, at this data point I ran it's the label: I ran zero kilometers at this data point, I ran five kilometers and so the answer which many of you are getting correctly is 11 because there are 11 data points that I'm plotting here.
35:15
And so I'm going to check, in this case, is 11 <= 2 and it is not and so I would skip this if statement and the first time I run this BuildTree for this dataset but let's ask what would happen if I did happen to have actually only 2 points and we'll fill it in.
35:35
Okay so if I only had two points, if I were making myself a leaf, well what happens at a leaf? At a leaf, we just make a label. We just say what's the label that I'm going to have? What's the predictor that I'm going to return for this little area? It'll turn out to be like that little partition element that we saw before, this little block of space in our feature set. Okay so we're going to have to set y hat somehow. How are we going to set y hat, where y hat is our
35:58
label, it is what we predict in this little area? Well remember, our goal here—I mean this is going to be a heuristic method—but our goal is to minimize the loss and, in particular, the loss or the error, the thing that we want to minimize here, is going to be the sum of the losses over the data points in this little set. So we have a sum over data indices in the tiny little set that
36:23
we're looking at right now. I mean by construction it's tiny because it had fewer data points than k
36:29
and then we're going to have the loss for that data point. And so something that you should do is either immediately think that you have already solved this problem earlier in the course or, even better, solve it again right now and by right now I mean if you don't immediately think of the solution, do this later on your own time. But you should convince yourself that the y hat that minimizes this loss is the average of the
36:54
y's of the training data here. So this is a great exercise if maybe you're getting a little rusty on this from earlier in the course, but make sure you convince yourself that I'm trying to minimize the squared error loss on this subset of data, then I'm going to take the average of that subset and that'll be if I have to do a constant prediction that that'll be the best thing I can do.
37:18
Okay so now, I know what I'm going to use for my label in this leaf: it's going to be the average of the data points that fall into this leaf.
37:28
Okay so now let's think about what happens if I didn't get down to, say, two data points or if I didn't get down to, in general, k data points which is certainly what happens the first time I start building this tree.
37:39
Okay in that case, I'm gonna have to make some kind of split, that's what happens in our internal nodes. I've decided I'm not making a leap so I'm gonna have to make an internal node and that internal node does a split and so that split, remember, has a dimension and it has a value and so, for instance, the dimension in this case, in this toy example we have here, could either be 1 or it could be 2, there's the only dimensions that I have. I'm basically go through all my
38:04
feature dimensions and consider each one of them in turn. Okay well let's suppose that I choose x_1
38:11
and I choose a split value that's maybe slightly negative. This is what my split would look like. Or maybe I could choose a different split value or maybe I could choose one over here. Any of these would be totally fine. Okay so here's an issue: if I have a for loop over every data dimension, that's fine because there are usually d data dimensions, that's a finite number, we're all good. If I have a for loop over every possible split value and these
38:37
are continuous dimensions, I have an uncountable for loop and that's bad, that's not something that I could do on my computer and so that seems like a problem that we're going to have to resolve and basically I'm just going to come back to in a moment but hopefully you can think to yourself why is this bad. We couldn't have a for loop over an uncountable infinity or any infinity really.
39:01
Okay so let's suppose for the moment that somebody just gave us our split dimension j and our split value s and go forward with that and then we'll come back and resolve this issue of how could we deal with the fact that we have, seemingly, an uncountable infinity of split values.
39:17
Okay so somebody just gave us, they said “hey, we're going to take x_1 and we're going to split on a particular value s.”
39:26
Okay what does that do? Well it divides my data into two parts. So for instance, if this were my… So if I chose x_1, so if my j was 1 and my split value, s, was where this line intersects the x_1 axis, then I would have two sides: I have the side where x_j >= s,
39:51
so I'm going to call all the data indices on that side I+ and I have the side where
39:58
x_j < s and so I'm going to call all the data indices on that side I-. Okay so here's a question for you, again, for the chat: suppose I do this absolute value around I-, that is to say I say how many data indices are in I- for this split? How many are there?
40:32
Okay it's looking mostly pretty good. Let's just walk through what we do here. So remember I- is the collection of data indices for data points where x_j < s so that's what we're seeing on the left side of the split here in that orange rectangle and if we look at the number of data points in that orange rectangle, it's 2, and so we're gonna have two data indices in I-.
40:59
If we look at I+, we're gonna say how many data indices are in I+ and you can count them up. In this case, it'll be the things where x_j >= s, in this case it's 9 data points and as should be the case, 9 + 2 = 11, our total number of data points.
41:16
Okay so that's what I+ and I- are doing: they're just saying, what are the data indices on one side or the other? And now what we're going to do is we're going to consider,
41:26
instead of just having one constant value that we predict for this entire space, breaking into a prediction on one side, which we'll call y+ and a prediction on the other side, which we'll call y-. So on the I- data, we'll predict y-. On the I+ data, we'll predict y+.
41:44
And then what we want to do is we want to minimize the error. So this looks, I think, complicated at first but it is literally just the error that we wrote before which is for every data point in I,
41:56
we take the squared error loss and we add it up. It just so happens that every data point and I either is in I+ or it's in I-, it's only one or the other, and so we can break that sum over everything and I into a sum over I+ and a sum over I- and then we just have the squared error loss.
42:17
Okay again, just like we did above, you can actually convince yourself that we don't need to do anything fancy to solve for y+ and y- to minimize this error because, remember, we want to minimize the loss, we want to minimize the error and once we have j and once we have s, we can just solve for the y+ and the y- that minimize them. You can convince yourself that, again, those will just be the averages. So this is much like what we saw in the part above. Now
42:44
we're just saying what we're going to do is over I+, we're going to predict the average of the training data in I+ and over I-, we're going to predict the average of the training data and I-.
42:55
Okay so that means if we have a split j, so if we have a split dimension j, and we have a value s, then we know how to get the best predictions.
43:04
Now we have to choose the split dimension j and the value s and so what we can do is we can say, “hey, for this split dimension j and this split value s, what's the error? What's the loss?” And then we'll choose, over all the different j's and s's, what is the error or what is the minimizing error? How do we get the smallest loss? And we can do that by just calculating E_j,s for each j and s
43:28
and then looking at which one is minimizing. Now remember, we had this issue though where we said, “ah, there's technically an infinity of values, in fact, an uncountable infinity of values where we could split and so what are we going to do?” Okay, so let's look up at our plot again up here and remember this line, this yellow line, is a possible split. So here's a different possible split, here's a possible split. And with this possible split, we're saying, “hey, we're
43:57
going to put everything on the left-hand side into one prediction bin and and predict the average of those things, we're going to put everything on the right-hand side into another prediction bin and predict the average of those things.” So if I change my split from this to this, between these two options, so oops here's even three options, if I change my split between these two options,
44:19
do my predictions change on the two sides?” This is a question for the chat: yes or no? If I change between these two splits or even these three splits, do my predictions change?
44:37
Great, everybody's saying no. Fantastic. We're all on the same page. The observation here is that, while technically my predictions that a new data point might change with these splits, my predictions that the training data do not: they don't change at all
44:53
because these splits are between two training data points and so I'm not changing anything about how the training data gets categorized and I might think to myself, well in that sense, those splits are completely equivalent to me because all I know about is the training data. I'm just going to say, “hey, those don't have any real difference.”
45:12
Now there's a whole bunch of splits that are between two data points. In fact, again, an uncountable infinity of things. So all of these splits are between two data points so I might ask myself, “well, I gotta choose something. How do I choose between them?” One option is to choose the most central of them. Say, I'm gonna average the two x_1 values of the two data points and just allow a split straight between them. That's one choice. But the basic observation that we
45:36
want to make is that, because all these splits are somehow equivalent on the training data,
45:41
I don't really have a way to choose between them so I'm just going to try one of them, I'm not going to try every single one of them and try to compute the error every time because I know I'm going to get the same error, the same training error in this case. And so instead of going over every split dimension and every split value s which would be literally impossible to do,
46:01
what we're going to do is we're going to go over every split dimension j
46:05
and then maybe something like one split value roughly per data point. So we might say, maybe, we'll do a split value everywhere that it could make a difference, everywhere that there is a unique training data loss and that'll be about on the order of the number of data points. I say about on the order because you might do different things at the edges, you might have two data points that have exactly the same x_1 value,
46:27
but roughly you only have to do something roughly on the order of the data.
46:33
Okay so now, we've reduced this to a problem that you can actually solve, we're going to try maybe something like the central values between every two data points. And so finally we have a finite number of split dimension values j
46:48
and split values s that we're going to try and because we have a finite number of them, we can look at the error or the loss on every one of them and we can say which choice minimized that error or that loss and that's where we're going to split.
47:08
Okay so finally, so what we did up top was we said if we had a small enough number of data points,
47:14
then we were going to make ourselves a node, it happened to be a leaf node, and that leaf node's going to have a label. Here we said, okay, we didn't have a very small number of points, so we're going to make ourselves an internal node, not a leaf node but an internal node. And so let's think back what defines an internal node. We've said this a couple of times already but now we're going to start getting really precise. One internal node is defined by a split dimension,
47:41
a split value, and it's two children. And so here, what we're going to do once we found the best split dimension and the best split value, is we're going to return that best split dimension,
47:56
we're going to return that best split value, and then we're going to build the children. So the left child, let's think how would you build a left child. Well, you're basically going to recursively do the same thing on the data points in the left side of the split.
48:12
So in particular, we're going to BuildTree on a set of indices that are now smaller than the original indices we put in. We put in our indices I and then what we did, was we found a split described by j* and s*. We're gonna take all the indices on the left side of that split and build a tree with them and then we're gonna, on the other side, take all the indices on the right side of the split and we're gonna build the tree with them. And the reason now that this is
48:38
I_j*,s* is because we chose a particular split, described by j* and s* and so we technically, in some sense, computed these I’s for every single j and s, but now we're saying, “ah, this is the particular j* and s* that we chose. It's the particular split dimension and the particular value and so that's what we're going to use to split going forward.” And so you can see, in this sense, this is a greedy algorithm because it only uses the information that
49:07
we have right now and it tries to minimize the loss immediately even if that might not be the best thing in a long-term sense and by long term, I mean over multiple splittings into the future.
49:25
Okay so let's run through an example of doing this. Let's build a tree for this data that we have on the slide. So we start by saying we're going to BuildTree with all the data indices, 1 to n. As you observed earlier, and in fact, here is 11. And so we're going to build over the indices 1, 2, 3, 4, 5 up to 11. And let's suppose we chose our k to be 2, that's that's how many data points that we're going to allow in a leaf.
49:56
Okay, so first thing we're going to do is we're going to walk into this BuildTree algorithm and we're going to start making ourselves some kind of node.
50:05
We first decide whether it's going to be a leaf node, if we finally made it to a leaf node, or if this is an internal node. As we observed, 11 is not less than or equal to 2. And so in this case, we will not be building a leaf node, we'll be building an internal node. So we'll go to the internal node building center. Okay so over here, we're going to look at every possible dimension,
50:26
again that's every dimension of our feature space, in this case x_1 and x_2, and we're gonna look at every possible split value, every possible split value that could even give us a different loss, a different error, and so really we're just going to look at something like, maybe, between each two data points. Okay so we do that, we find maybe the split value that is particularly good here, and we're going to start building our node.
50:51
So what makes our node? Well the first thing is what was the split dimension and value that we found? Maybe it was this one. So here, maybe we found x_2 >= 0.28 is a good split. And so on one hand, we have x_2 < 0.28 (so when it's not too much precipitation) and on the other hand, we have x_2 >= 0.28 (when there is a lot of precipitation). So that's the split that we've done and if you kind of look at it, this seems like probably a reasonable first split to have
51:25
done for this data: it chops off the most things that you can that are unique in an axis-lined way.
51:33
Okay so we made this internal node and so it's going to have two children, it's going to have a left tree and it's going to have a right tree.
51:44
And the thing to notice here is we're going to start by making the left tree,
51:47
just in the way that this pseudo code runs.
51:52
Okay so let's talk about how would we build this. Well, we BuildTree on the indices that fell into that region. So in this case, hopefully, you can see there are going to be eight indices that fell into that region, there are eight data points that are in that region and so we're going to ask: is 8 <= 2? It is not, so we're going to build ourselves an internal node and it's going to have a cut off, maybe in this case, it happens to be 7.2 and so that might look
52:22
like the following: so we have our left hand side and our right hand side from that split
52:29
and now what we have to do, again, is start by building tree for the left hand side.
52:37
Okay what is that going to look like? Well again, we go up to BuildTree and we ask: is the number of indices less than or equal to two? This is a question for you in the chat” is the number of indices less than or equal to two?
52:59
Awesome, a lot of great things here: yes! It equals two. And so technically, 2 <= 2 and that's like the relevant thing that we're interested in here. And so, in fact, we will make a leaf node at this point. And so let's go ahead and do that. What does our leaf node look like? Well, we're going to take the average of the data points at this point. That's going to be our prediction.
53:26
Another question for the chat: what is the average of the data points in this region?
53:38
Great. Yes. As you've observed, this should be a particularly straightforward average because both data points are zero, the answer is zero. In reality, probably, they would be very slightly different from zero, but this is one that's easier to do some math with and so the answer is zero. So we'll make that the label at this leaf. Okay, so now, we go to our right hand BuildTree and maybe we find that a particularly good split is between all these 5s and all these 0s.
54:07
So on the right hand side, we have the 5s, on the left-hand side we have these 0s. Again this looks like our “we don't run when it's too hot, we run when it's a reasonable temperature” kind of split. Okay, so now we're going to build our left hand tree. And something you'll notice is that even though everything is 5, even though we have this great regressor for everything, that's not our decision about whether to make a set of leaves. The set of leaves,
54:36
whether to make a leaf, our decision is the number of things in this partition element or “is the number of indices less than or equal to two” and it is not and so we're gonna do another split
54:49
okay. So maybe we happen to split here into some 5s on one side and 5s on the other side. In this case, all the splits are equivalent. There's nothing that's better, and so you have to have some kind of tie breaker and maybe this is just where the tie breaker fell and so we'll predict 5 on this side, we'll predict 5 on this side because that's going to be the average and then we'll go back up to making our left hand leaf up here and maybe we'll predict 0
55:11
over here and then we finally get to our original left hand leaf, you can see that we're doing a depth first kind of thing here, and in this case, again, we're going to have to divide because there were three data points and so maybe we'll have one side with one data point and one side with two.
55:29
Okay so we have created a tree, we have built a decision tree by doing this. We kept going until we got down to a very small number of data points in each league.
55:45
Okay so now, let's take a look at this decision tree.
55:50
Again, what it's doing is it's creating a predictor, it's creating a function of the
55:58
features and you can see that, you can imagine that it's popping out of the slide at you in the y-axis and it's 0 over a lot of this area and then it's 5 in certain areas and it's basically a step function: it's a step function that we have predicted.
56:12
Now an observation that we could make here is, well, we didn't have to keep splitting. I mean, at some point, we actually had like zero error and so why would we keep splitting? Maybe we should stop splitting at zero error. Maybe even better ideas for regularization purposes, we could do something like stop splitting after our error gets quite low. Maybe we should just check if our error is too high or not. A related question here is: is overfitting an issue?
56:41
And if you think about it, what we're doing here is we're getting down until we have two data points and then we're fitting them as perfectly as possible. You can imagine if k is one, then you get down until you have one data point and then you just predict exactly that data point’s value because the average of one data point is one and so it certainly seems like it would be easy to overfit in this case and so, again, how about we regularize by stopping splitting after our
57:07
error gets low? What if we do that? Well just an observation about what could go wrong there. So we're going to pursue this idea of stopping splitting when there's no or a small change in loss. Just an observation of what could go wrong is let's look at this example: suppose, instead, that I run when it's really warm and there's rain or I run when it's really cold and there's no rain. This doesn't seem entirely implausible. This could be a way that somebody decides to run
57:39
and suppose that I wanted to use a decision tree, a regression tree, to learn that.
57:44
Well, at least if my data were perfectly arranged like this and actually we did see some data back in the features lecture, back in lecture three, that actually could be arranged like this just due to the way that we encode features, you're going to see that let's try a first split with this. Suppose we're building a tree.
58:03
We go to our first split. We say, “hey, we have our set of indices, there are four indices, and we're going to try every possible split and there is literally no split that improves the error
58:18
in this case, everything is just as good as if you had just this whole region and you were looking at that.” And so if we stopped when there was no change in loss or a small change in loss, we'd stop right here. And yet, if we made a split, pretty much any split that was between data points here, and then we made another split, we'd get a perfect predictor and it would be fantastic and it would do really well. Now if these things are moved around a little bit,
58:46
the idea changes slightly, but the idea is still there that, somehow, there's this issue of if you stop splitting when your error is very low, it can be very short-sighted. Kind of the issue is that we're doing these axis align splits and so it might take a few to actually get to a good point rather than just a single one, like a single one might not represent the thing that you care about.
59:12
So from that perspective, we were greedy when we were building this tree but maybe we don't want to be greedy in stopping building the tree which is what would happen if we stopped when there was no change in loss or small change in loss and instead, an idea that was pretty influential when it was introduced and continues to be used to this day, is to build the tree, to grow the tree with this algorithm, but then prune it back. And so
59:37
I'm just going to briefly go over what that might look like. Again, I wouldn't get too obsessed with any particular way of building or learning a tree, but I think there are some general ideas here that are important to keep in mind about what can you get from a tree, what kinds of structures can you look at, and how you have to be aware about how you're learning it.
59:59
Okay so let's talk about how to regularize. Now you can think about this as being encased in some kind of objective. Certainly this is something that we've talked about in other cases throughout our course that we have some objective that we're interested in optimizing and typically it looks like the following: it looks like a loss over the training data
1:00:20
plus some kind of constant times a regularizer and usually the regularizer is a penalty, it penalizes having some more complicated model. It makes you pay for that more complicated model, it makes you say that the loss was really worth it and so we've seen this before for logistic regression, for linear regression. A lot of times, our regularizer has been this squared error loss or this squared error or sorry I should say just a squared size thing, like if we have a theta, we're
1:00:52
taking this squared penalty on the theta. And here, we're going to look at something a little bit different. So here we want to think: what are our choices for our tree? Well, training loss,
1:01:04
that's pretty straightforward. We already said that we cared about squared error loss for our training loss and so we can just write squared error loss for the training loss, so that'll be straightforward, the concept’s easy to put in, but what do we want to penalize? And I think, at least based on our discussions that we've had so far just now, a natural thing to penalize is bigger trees, bigger more complex trees and so
1:01:25
we might say our penalty is going to be on trees that have more leaves. If you have more leaves, you have to pay for that somehow with training loss, you have to have a better training loss.
1:01:36
Okay so here's a way to express that: let's just walk through the elements of this formula.
1:01:41
So first, we're just going to say what is the name of our objective? In this case, we'll call it c, it'll be a function of T. So T is the tree that we learn, it's the predictor that we learn, and alpha will be the constant that trades off the penalty and the training loss. Often in the past we call this gamma.
1:02:01
Okay so first, we have the training loss. So there's nothing new here: we're just summing over all the data points that we have, we're looking at the loss between our guess which is the predictor T applied to the features for this data point, the i-th feature, and our actual which is the actual label for these data points, the y^(i),
1:02:22
and we have our alpha that trades off our penalty and our training loss. And here, we're saying the thing that we're penalizing is the number of leaves so we're preferring, we're trying to express our preference, for trees that have fewer number of leaves.
1:02:39
Okay so what would happen if we looked at our tree over here
1:02:42
and we did this trade off? Let's start... Oh and let's call this the cost complexity of a tree T. So this is often what it's called, it's again very similar to the objectives we've seen before.
1:02:53
Okay so let's look at our tree over here. In particular, if we had our whole tree, it describes this whole space with a bunch of partitions in it, but let's look specifically at this little subtree down here at the bottom, so the sub tree that's defined by the x_1 >= 18.3 split and its two children, the 5s. This seems like a useless subtree: it's not doing anything. If we didn't have this subtree, if we just had a single leaf that predicted 5, it would do exactly as well
1:03:24
and so if you look at this cost complexity and you look at alpha = 0, then there's no way to decide between this full tree and the tree where this subtree is replaced by a single leaf.
1:03:38
But as soon as you increase alpha just a tiny bit, it could literally be any slightly positive value of alpha, anything whatsoever that is slightly positive, suddenly it's not worth it to have this tree because you are taking a hit of an extra leaf and you could reduce that by getting rid of this subtree and so as soon as you have this very slightly positive alpha, it is better to replace this subtree with just a single node, with just a single leaf, because
1:04:12
that'll be one fewer leaves and so you'll reduce the cost complexity at no hit to the training loss
1:04:19
and you'll notice that this is the same over here: so here we have a case where there's a subtree, this internal node and it's two children, where there's no change in the loss, the training loss, if we reduce this to just a single node and so if all we cared about was training loss, then these would be completely equivalent trees, but as soon as we have this penalty and as soon as we have a tiny little bit of alpha,
1:04:45
then it's better to just get rid of that subtree and replace it with a leaf.
1:04:53
Okay so the idea of pruning is basically to just keep doing this. So with pruning, what we do is that you can imagine slowly increasing alpha. So here we increase it a little bit beyond zero, we can slowly increase it, and as you increase it, eventually, certain sub trees are not worth it
1:05:10
and you can get rid of those subtrees one at a time as they become not worth it and you'll end up having a finite sequence of trees until you get to the root. Eventually nothing will be worth it and it would be better to just have a single constant thing that you predict. And once you have this sequence of trees you can run cross-validation on it to find the best tree.
1:05:29
Okay but the idea here, I think the really key idea to get, is that this can perform a lot better having the ability to have a little bit of a longer, less greedy procedure to create these trees can perform a lot better than if you just stop making the tree when it seems like you're not getting any benefit from it in a particular step.
1:05:54
Okay so at this point, we know a way to create a decision tree. Again, I want to emphasize that it's not the only way. In fact, I think there's some really interesting work going on in terms of trying to have the interpretability of decision trees with the flexibility of other methods so you could try to have your very powerful method that performs really great in terms of predictive performance and then what you can do is you can try to have a tree
1:06:19
that represents the information in that even if it takes a little bit of a hit
1:06:24
in terms of understanding and so there are lots of things that we can do here, trees are really interesting nonetheless. Oh before I move on I'll just get this question from Discourse: how do we choose the value k or should we just make it pretty small to get a large tree and then prune? Basically these are both great ideas so a typical thing that people might do is that they might get their very large tree and then prune and then the pruning aspect, you don't have to
1:06:45
care too much about k. You might still care about k just from a computational perspective. So if you think about your k as being 1, you're gonna have to make a ton of splits in a very large dataset to put everything into its own little bucket and so it might be just easier and faster to use a larger k, so that's a consideration as well. So basically there are multiple considerations even
1:07:08
beyond our usual ones like prediction error but also just speed and ease of use but absolutely, yeah, you can just make a relatively small k and then prune back to do the regularization.
1:07:19
Okay, another thing that you can do (you can think about this as regularization,
1:07:26
you can think about this as just doing better)
1:07:30
is you can ensemble. So just as we just talked about, maybe, we could choose a really small k and then we could make this really big tree and then prune back, you could also truly choose a really small k and then ensemble and that'll do some regularization for you. It also just will turn out that this is a good idea, period, to increase the performance of your method.
1:07:50
Okay so we, in particular, again, just when we started off, we said we're going to talk about decision trees in terms of interpretation. Now we're going to talk about ensembling in terms of predictive performance. The general idea here is that using multiple machine learning predictors even if they don't seem individually really great will typically make a much better predictor. So you see this everywhere. So if you look at the Netflix prize back in the day,
1:08:13
not only did all the top teams use ensembles but literally one of the team names was “The Ensemble” so good advertising for ensembles there. If you look at basically any other competition, this tends to be the case. So the Makridakis competition is a competition that happens regularly on time series data. They looked at 100,000 time series in their competition and no individual method ever did that well, but when you have these big ensembles of lots of methods,
1:08:39
some of which included neural nets but that wasn't the only method, you got these great performances and, of course, it's not all just about competitions. I mean, in some sense, the point of competitions is to prepare us to do things that really matter in the real world and if you look at the forecast that people are using for both cases and deaths in COVID-19 right now, the CDC, for instance, is reporting an ensemble forecast and so there's just this, generally,
1:09:05
sense that ensembles are giving us really the best predictive performance when we care about predictive performance. Okay, so there are a lot of ways to do ensembling. We're going to talk about one of them. So, in fact, I mentioned in the beginning, these Kaggle competitions and the things that people are doing there. It turns out that's actually a different type of ensembling, boosting, and I encourage you to check that out if you're interested in that direction. We're
1:09:30
going to talk about bagging, and from this, we're going to get a sense of what an ensemble does.
1:09:35
Okay, so this is just one of multiple ways to make and use an ensemble. Bagging stands for bootstrap aggregating, which doesn't really make much sense right now, but hopefully we'll make a bit more sense at the end of this slide because then I'll say what that means.
1:09:49
Okay so what we're going to do is we're going to take our training data
1:09:53
and we don't have to be doing trees right now, we could be doing just about anything,
1:09:58
and we're going to create a bunch of fake datasets from our original dataset. In particular, B fake datasets. And the way that we're going to make these fake datasets is, for every b, we're going to draw a new dataset by sampling with replacement from our original dataset. So what does this look like? So in our original dataset (you can think of our original dataset as a bunch of color billiard balls in a bowl, so there's a yellow ball,
1:10:27
there's a green ball, there's an orange ball, there's a blue ball, and there's a purple ball)
1:10:33
and then what we're going to do, is we're going to stick our hand into the bowl, pull out a billiard ball and that'll be the first data point in our new dataset.
1:10:42
So we choose each one of these five data points, in this case, with equal probability. Now the width replacement part is where we take the ball that we're holding and we put it back in and then we shuffle it up again, we choose from every possible point again with equal probability.
1:10:59
If we were doing without replacement, every time we took one of these balls out, we would put it over here outside of the ball and then we would draw a new ball and there would be fewer balls every time. In this case, there's the same number of billiard balls and so we can keep doing this: we can draw our third data point in our new dataset, our fourth data point. Of course we're gonna get some, probably, it's very likely, that we're gonna get some repeats because we're just
1:11:22
putting it back in and we're drawing from the same distribution. In this case, it turns out we got three repeats and so we'll say that this is our new dataset and it has its own indexing. It just so happens that a lot of its data points are the same as the other one and so here, what I'm going to do is I'm going to change this to be our new dataset and indicated by (x tilde)_1, (y tilde)_1. So we have the first data point, our new dataset, the second data point, our new dataset,
1:11:48
the third data point, our new dataset, and so far. But you'll notice, the first, fourth, and fifth data points are the same and two and three are different. Okay and so what we're gonna do
1:12:00
is we're gonna make this new dataset B different times.
1:12:07
And the trade-off with B is that the more B, you get better in some sense, but eventually it's just computationally difficult and you stop getting as many benefits, so that's the trade-off for B. We're going to make all these different datasets and for every one of these datasets, we're going to train a new predictor and because the datasets are random, because they're different every time, we imagine that our predictor is going to be slightly different
1:12:30
and what do I mean by predictor? This is like we're going to make some regressor. Maybe in regression, we'll have a different set of predictions for new, this is a function of the features, what is the prediction? We make it a new feature, so that's what that function is.
1:12:46
Okay and then finally, what we do is we combine the wisdom of all of these different predictors. We imagine each of these different predictors is pretty good at something and we're going to return some combination of all of their information. So for regression, a typical thing that we might do is we might average over all of them. So we're going to return a final predictor, so this (f hat)_bag is like what we actually return at the end of the day and it's the
1:13:10
average of all those individual predictors on the little different datasets that we did.
1:13:17
For classification, you can do something similar: you can take the predictor at a point as being the class with the highest vote count with some way to deal with ties, but basically at every point, for every one of your B classifiers, you're going to have some classification, it's going to say what class it thinks it is and so you can do a voting across them and say which which one's getting the most votes.
1:13:42
Okay this is a super simple idea. All we did was we randomized our data slightly and then we got this way better predictor almost for free. I mean you have to run some extra things, but you just have a bunch of these predictors and you already had some way to make predictors and so now you're just running a bunch of these fake datasets and so this is bootstrap aggregating and it is surprisingly effective. You can have some pretty
1:14:03
bad predictors as long as they're just slightly good, they're better than chance. This can be really, really effective. Okay so why is it called bootstrap aggregating?
1:14:12
The bootstrap part is making all these little fake datasets by sampling with replacement B times.
1:14:20
This is an idea that is not at all specific to trees. It's not even specific to bagging. It's actually an extremely general and surprisingly powerful idea for how simple it is. I mean maybe I shouldn't say surprisingly: some of the simplest ideas are some of the most powerful, but that's the bootstrap part and then the aggregating part is when we aggregate it all together at the end and we take all of these different predictors and we make them into one
1:14:45
super predictor. It's like if you took the power rangers together and you made them into Megazord, this is what's happening right here.
1:14:54
Okay so that's bootstrap aggregating. There's nothing that is specific about trees here: you could do this with any favorite predictor. In fact, there's reason to think that neural nets actually, individually, are kind of unstable. Like you can get really different results if you just change things slightly about your setup or change things slightly about the data and so you could put them all together if you wanted to in this, you could do a lot of things with bagging. But of
1:15:18
course, one of the things you can do with bagging or wouldn't fit quite so well into this lecture, is bag trees, bag decision trees, and so that is so popular that it's given a special name,
1:15:30
a name that you are likely to encounter in life which is random forests. At least if your life is full of machine learning, you're likely to encounter this. Okay, so random forest is basically bagging with decision trees with a little bit of extra randomness. It's not exactly bagging decision trees and I'll point out where the extra randomness comes in.
1:15:50
Okay so let's just briefly talk through a random forest.
1:15:55
So random forest, you do the same thing: it's just bagging and so what we're going to do, is we're going to go through all these B different bags basically. In each one of them, we draw a new dataset with replacement from our original data. So that's just like bagging, nothing has changed from bagging. Okay here's the part where we make this about trees instead of a general regressor. So when we're doing general bagging, this could be any predictor. Now,
1:16:20
we're just speaking specifically about trees. We're going to build a tree on the random dataset by recursively repeating a number of steps until the node size k is reached.
1:16:35
Okay, so first... Now here's the part that's different from both bagging and decision trees: we're going to select m features uniformly at random without replacement from the d features. So we didn't do this when we were doing random forest before, when we were doing decision trees before. If this were just bag decision trees, we wouldn't have this part. This is like extra randomness and
1:16:56
it turns out to be useful to decrease correlation between the different trees you're learning from. Okay but you're going to select these m random features, the subset of your d features,
1:17:07
and now you're going to do the usual decision tree thing. So instead of going over all the features like we did when we were making decision trees before, you just go over the subset but you still pick the best split dimension and the best split value among the m features instead of the total d features.
1:17:25
And then you build two children. So everything here is basically bagging and then we do trees and there's just this little extra randomness here. Okay and finally, just as in bagging, we return the average for regression or some kind of top vote for classification.
1:17:46
So why is it called random forest? Well it's clearly random because we have multiple sources of randomness: so there's the randomness in making the different datasets, there's also the randomness in choosing the feature subsets. It's a forest because you make B different trees and so you have a whole bunch of trees, B of them. Each tree defines a predictor and then you average over all of those predictors to get your final predictor, your final regressor
1:18:15
that you're going to return, and so the forest is just because it's literally a bunch of trees.
1:18:21
Okay and so to recap: the bagging part was that we drew all these different datasets and then we averaged them over for regression or voted for classification at the end,
1:18:31
the trees part was that we chose trees as our predictor.
1:18:36
So we could have chosen something else with bagging, it's not specific to trees, but here we chose to use trees and then the extra randomness was that we didn't just use any features as we would normally for trees where we consider all the features, we just concern ourselves with these m uniformly at random features. Okay so at this point,
1:18:58
we have accomplished some of our goals. Our goals were to try out, to see: could we come up with methods that were useful for interpretability that weren't purely focused on predictive performance? And decision trees, I think, are certainly that. If we go back to our tree that we saw at the beginning, again, the hardest part I think, in some sense, about this tree is understanding the medical terminology, it's not understanding how to use this machine learning predictor. This is
1:19:24
something that, I think, you could tell family members who don't have machine learning background about, this is something you can tell juries about, this is something you can tell medical experts about, this is something that you can talk to people about, whereas I think it's a lot harder to explain what's the output of neural nets, for instance. Conversely, with decision trees, we're not going to have as much predictive power. I mean,
1:19:44
they're just not as flexible as some of the models that we've seen elsewhere. With random forest, we can get that predictive power. Even though it's built from these tiny decision tree blocks, you actually get a huge amount of flexibility by having this ability to average over a lot of decision trees but you lose, basically, the interpretability of decision trees because you're not just making this simple series of decisions anymore,
1:20:08
you're making tons of them and what does it mean to average over tons of these decisions? It's not as clear and so you get a real trade-off and it depends on what you're trying to do. Okay great. Then I hope you all have a great break. I think we won't see each other for a couple of weeks but I hope you enjoy the Thanksgiving break and I'll catch you at the next lecture.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat