1 00:00:00,280 --> 00:00:05,480 So, continuing the exploration of large scale machine learning topics today we 2 00:00:05,480 --> 00:00:09,140 will focus on a different algorithm, called the decision tree al, algorithm. 3 00:00:09,140 --> 00:00:13,740 And the idea here is that, instead of modelling the decision space between, 4 00:00:13,740 --> 00:00:17,820 let's say, positive and negative examples using single, single line, we will, 5 00:00:17,820 --> 00:00:21,590 we will learn much more complicated decision boundaries. 6 00:00:21,590 --> 00:00:23,270 And this will allow us doing a, 7 00:00:23,270 --> 00:00:28,310 kind of much more fine grained way to represent the differences between, 8 00:00:28,310 --> 00:00:32,170 let's say, positive and negative examples, if we are talking about classification. 9 00:00:32,170 --> 00:00:35,470 So just to remind you, what we are talking about or thinking about, 10 00:00:35,470 --> 00:00:39,410 is that given, given a given attribute, let's say a wealth of a person, 11 00:00:39,410 --> 00:00:43,750 we want to predict the value of this attribute by the means of 12 00:00:43,750 --> 00:00:48,680 some other features or attributes available, available to us, right. 13 00:00:48,680 --> 00:00:51,460 So in a sense, what we would like to do is, we would like to figure out, 14 00:00:51,460 --> 00:00:56,690 how wealthy is the person, given various other characteristics of this person. 15 00:00:56,690 --> 00:00:59,370 The way we can think about this is, is that we can think of 16 00:00:59,370 --> 00:01:03,340 input attributes as the features that we know about the person. 17 00:01:03,340 --> 00:01:09,560 So, for example, imagine that every person is described by a set of d features x1, 18 00:01:09,560 --> 00:01:11,500 to x sub d. 19 00:01:11,500 --> 00:01:16,020 And then each feature, let's call it j, has a domain o sub j. 20 00:01:16,020 --> 00:01:17,510 Right. When I say a domain, 21 00:01:17,510 --> 00:01:19,560 I mean what is the number of, or 22 00:01:19,560 --> 00:01:23,770 what are all the different values that this feature, or this attribute can take. 23 00:01:23,770 --> 00:01:29,200 For example, if the feature x sub j is a, favorite color of a person, 24 00:01:29,200 --> 00:01:31,280 this would be what we call categorical attribute, 25 00:01:31,280 --> 00:01:35,110 right it can take values red, green, blue and so on. 26 00:01:35,110 --> 00:01:39,910 Another thing for example, would be if I can numerical features in a sense that, 27 00:01:39,910 --> 00:01:42,610 for example if I ask what's the weight of that person or 28 00:01:42,610 --> 00:01:47,160 how old is that person that is, that is nicely a number and, and 29 00:01:47,160 --> 00:01:53,110 a given variable, in this case a feature, would have a domain that is 30 00:01:53,110 --> 00:01:58,110 let's say a non negative real numbers if we are asking about a weight of a person. 31 00:01:58,110 --> 00:02:01,610 And now, of course, the same thing happens to what is the value of y, 32 00:02:01,610 --> 00:02:04,940 which is the value that we want to predict, we will call this 33 00:02:04,940 --> 00:02:10,050 the dependent variable, or this is the thing, the quantity we want to predict. 34 00:02:10,050 --> 00:02:14,200 So, now our idea is, is the following that's kind of we started last time. 35 00:02:14,200 --> 00:02:18,330 We are given a set of data d, we're given, if we are given a set of n we 36 00:02:18,330 --> 00:02:23,680 will call them training examples, x sub, x sub y comma y sub i. 37 00:02:23,680 --> 00:02:28,070 Where basically the idea is that x sub i is a d-dimensional feature vector. 38 00:02:28,070 --> 00:02:29,990 Right? So d, d-dimension's from up here. 39 00:02:29,990 --> 00:02:34,195 And then, y is simply the variable that we want to predict. 40 00:02:34,195 --> 00:02:35,450 An, and, and now, based. 41 00:02:35,450 --> 00:02:37,500 What we want to do is we want to learn the mapping, 42 00:02:37,500 --> 00:02:42,780 that maps the features, of a given person to the, wealth of a given person. 43 00:02:42,780 --> 00:02:43,910 So that is our goal. 44 00:02:43,910 --> 00:02:46,670 And now the question is, how is this function that takes 45 00:02:46,670 --> 00:02:49,770 the feature sentence forming them into the value we want to predict? 46 00:02:49,770 --> 00:02:50,900 How does this function look like? 47 00:02:52,640 --> 00:02:53,180 right? 48 00:02:53,180 --> 00:02:59,840 So the idea will be that basic decision trees is is tree-structure plan that given 49 00:02:59,840 --> 00:03:05,630 a set of variables it wants to test that set of variables, and predict the outcome. 50 00:03:05,630 --> 00:03:09,150 So, to be a bit more concrete, here is an example of a, of a decision tree. 51 00:03:09,150 --> 00:03:10,820 Right? A decision tree is a, 52 00:03:10,820 --> 00:03:14,910 is a tree hierarchical structure where I have two types of nodes. 53 00:03:14,910 --> 00:03:19,790 I have what we will call internal decision nodes, and I have prediction nodes. 54 00:03:19,790 --> 00:03:22,060 Here are, here are the nodes of the hexagons. 55 00:03:22,060 --> 00:03:26,500 And this tree can be you know, as deep as we want, as wide as we want, and so on. 56 00:03:26,500 --> 00:03:31,050 And the important thing here is that, in this tree we have the as I mentioned, 57 00:03:32,210 --> 00:03:37,290 decision nodes, they basically examine the value of a given attribute and ask, 58 00:03:37,290 --> 00:03:39,980 you know, is this predicate satisfied, yes or no? 59 00:03:39,980 --> 00:03:44,960 And then we have the internal the leaf nodes, which we can call decision nodes, 60 00:03:44,960 --> 00:03:49,500 which then say, okay, for this set of examples, let's predict the value. 61 00:03:49,500 --> 00:03:55,415 So, the idea is that the, as I mentioned, internal notes have the split values, 62 00:03:55,415 --> 00:04:00,520 the leaf nodes make predictions and in particular what we will look at 63 00:04:00,520 --> 00:04:05,650 today is only decision nodes that, that are based on binary splits so, 64 00:04:05,650 --> 00:04:09,310 basically every node has at most two children. 65 00:04:09,310 --> 00:04:12,820 So, kind of the, there is a predicate or a condition and 66 00:04:12,820 --> 00:04:15,230 then whether that condition is satisfied or not. 67 00:04:15,230 --> 00:04:17,880 Right? So kind of if condition is satisfied we 68 00:04:17,880 --> 00:04:20,760 go to the left, and if it's not we go to the right. 69 00:04:20,760 --> 00:04:25,010 We will be talking about numerical attributes, and we will 70 00:04:25,010 --> 00:04:30,520 think about regression, which means y will be let's call it a real number. 71 00:04:30,520 --> 00:04:33,290 So this is the setting that we want to talk about. 72 00:04:34,600 --> 00:04:38,370 So, the hard part here is, how do we build the tree? 73 00:04:38,370 --> 00:04:39,794 Right. 74 00:04:39,794 --> 00:04:42,630 now, the easy part is, how do we make a prediction? 75 00:04:42,630 --> 00:04:45,210 So, making a prediction is very easy, right? 76 00:04:45,210 --> 00:04:48,590 And so given that somebody, that we already built a tree, given our 77 00:04:48,590 --> 00:04:53,470 training example, we want to predict what is the y value for that training example. 78 00:04:53,470 --> 00:04:57,300 So the idea is that we want to take this x sub, x sub i and 79 00:04:57,300 --> 00:05:00,170 kind of drop it throughout throughout the tree and 80 00:05:00,170 --> 00:05:05,640 see which which prediction node it ends, it ends in and then predict that value. 81 00:05:05,640 --> 00:05:09,190 For example, imagine that I have a particular trend, 82 00:05:09,190 --> 00:05:10,900 example that comes in here. 83 00:05:10,900 --> 00:05:12,460 I can first evaluate, right? 84 00:05:12,460 --> 00:05:14,640 Is the first feature of this training example. 85 00:05:14,640 --> 00:05:16,960 Is it, does it have value less than v1? 86 00:05:16,960 --> 00:05:20,530 If the answer is yes, I move to the left. 87 00:05:20,530 --> 00:05:25,030 I end up in the prediction node, and my predicted value is 0.42. 88 00:05:25,030 --> 00:05:29,080 If the condition is not satisfied, and the answer is no to my, 89 00:05:29,080 --> 00:05:32,880 to my condition, I would move to the right, and I would keep kind of 90 00:05:32,880 --> 00:05:37,390 moving down the tree until somewhere I would hit my prediction node, and 91 00:05:37,390 --> 00:05:40,050 I would make a prediction for that case. 92 00:05:40,050 --> 00:05:41,050 Right? So the idea is that 93 00:05:41,050 --> 00:05:45,100 basically every node examines one, individual feature. 94 00:05:45,100 --> 00:05:48,760 Looks at it and then makes a decision is the condition satisfied or not, and 95 00:05:48,760 --> 00:05:51,972 then kind of moves either to the left branch or to the ri, to the right branch. 96 00:05:53,390 --> 00:05:57,250 So, to have an idea of what decision trees are really doing and 97 00:05:57,250 --> 00:06:00,280 what kind of interesting decision surfaces they can find, 98 00:06:00,280 --> 00:06:02,920 let's look at this simple two dimensional example. 99 00:06:02,920 --> 00:06:06,820 Where I have set of data points in this two dimensional space, and 100 00:06:06,820 --> 00:06:08,470 imagine we want to do classification. 101 00:06:08,470 --> 00:06:11,700 We want to, we want to separate pluses from minuses. 102 00:06:11,700 --> 00:06:15,540 So the way, the decision tree building procedure would would start is 103 00:06:15,540 --> 00:06:18,330 that given this kind of, training data set. 104 00:06:18,330 --> 00:06:22,640 We want to go and recursively kind of split this space into smaller and 105 00:06:22,640 --> 00:06:27,620 smaller pieces, such that each individual region in this space is 106 00:06:27,620 --> 00:06:32,210 uniformly populated by either all pluses or, or, or all minuses. 107 00:06:32,210 --> 00:06:37,300 So, for example, what we could do is, is to say first we have our first node 108 00:06:37,300 --> 00:06:41,230 in the decision tree, and we want to decide what is the first split. 109 00:06:41,230 --> 00:06:45,190 And imagine that we say the first split is at value e1, so we say 110 00:06:45,190 --> 00:06:50,840 is the value x1 of a given, of a given data point, imagine the data point here. 111 00:06:50,840 --> 00:06:56,020 Is the x, the value x1 less or more than the value v1. 112 00:06:56,020 --> 00:06:58,060 Right? So I have v1. 113 00:06:58,060 --> 00:07:00,860 And now if the answer is yes, I go to the left and 114 00:07:00,860 --> 00:07:03,520 otherwise I go, I go to the right. 115 00:07:03,520 --> 00:07:06,610 And now I could now go and find the second split. 116 00:07:06,610 --> 00:07:09,780 So I will take the all, all the data that is, that is down here. 117 00:07:09,780 --> 00:07:12,590 This is everything that kind of goes to the left and 118 00:07:12,590 --> 00:07:17,160 I ask okay, how can I now split pluses and minuses in this case. 119 00:07:17,160 --> 00:07:20,470 And maybe I find then you, decide to draw a line here. 120 00:07:20,470 --> 00:07:25,410 So now I would have the value v2 and I can draw another decision out and ask, 121 00:07:25,410 --> 00:07:33,430 you know, is x2 less than v2 and then I say is, is, is it or is it not. 122 00:07:34,510 --> 00:07:37,090 If it is right then I notice I have all the pluses, so 123 00:07:37,090 --> 00:07:42,760 if the value is less than v2 then I here I say yes, let's predict plus. 124 00:07:42,760 --> 00:07:48,080 If the value, is, not less than v2, I still have this messy part. 125 00:07:48,080 --> 00:07:52,040 So, for example, I would want to maybe split again along this dimension and 126 00:07:52,040 --> 00:07:53,860 split along that dimension. 127 00:07:53,860 --> 00:07:58,180 And similarly, on the top I would want to split here, and this way build the, 128 00:07:58,180 --> 00:08:03,460 build it three throughout throughout again where I have the prediction. 129 00:08:03,460 --> 00:08:07,500 So this is kind of one idea how we can think about building a decision tree. 130 00:08:07,500 --> 00:08:11,370 What is now interesting here is that we have this complicated decision boundary, 131 00:08:11,370 --> 00:08:14,440 that splits pluses and minuses from each other. 132 00:08:14,440 --> 00:08:17,895 And we see that we kind of have this area where there are minuses, and 133 00:08:17,895 --> 00:08:22,760 then we have this other area here where there are pluses, and we 134 00:08:22,760 --> 00:08:26,400 see that we could never kind of separate these two pluses out with a single line, 135 00:08:26,400 --> 00:08:30,320 but we can use decision trees to learn this more complicated decision boundary.