1 00:00:00,750 --> 00:00:06,410 So welcome to today's lecture in the Big Data Analytics summer school at Caltech. 2 00:00:06,410 --> 00:00:07,910 My name is Thomas Fuchs. 3 00:00:07,910 --> 00:00:13,040 I'm a research technologist at JPL and a visiting scientist at Caltech. 4 00:00:13,040 --> 00:00:16,740 And I will speak about decision trees and random forests today. 5 00:00:19,590 --> 00:00:22,660 So we will start by introducing Decision Trees. 6 00:00:22,660 --> 00:00:23,950 How they work? 7 00:00:23,950 --> 00:00:27,100 How they are inferred and how they are tested? 8 00:00:27,100 --> 00:00:32,740 Decision Trees are then used in one of the next modules as base classifier for 9 00:00:32,740 --> 00:00:33,740 random forests. 10 00:00:35,490 --> 00:00:42,080 Decision trees are widely used in science and in practice due to their simplicity, 11 00:00:42,080 --> 00:00:49,920 their speed and their applicability to a lot of different problems. 12 00:00:49,920 --> 00:00:53,520 So in general a decision tree is a set of nodes. 13 00:00:53,520 --> 00:00:57,740 On the left side we see general tree structure. 14 00:00:57,740 --> 00:01:03,660 The tree starts at a root node that's zero in that case then we have intermediate 15 00:01:03,660 --> 00:01:10,930 split nodes where decisions are made and then the trees splits up in sub 16 00:01:10,930 --> 00:01:15,560 partitions and then at the end we have terminal nodes or leaf nodes. 17 00:01:17,480 --> 00:01:21,070 So, in practice you can imagine a very simple example, 18 00:01:21,070 --> 00:01:23,060 as you can see on the right. 19 00:01:23,060 --> 00:01:29,200 In this scenario we want to classify images, to belong to one of two classes. 20 00:01:29,200 --> 00:01:32,490 One is outdoor images, the other one is indoor images. 21 00:01:32,490 --> 00:01:36,140 So, you can think of asking a set of questions. 22 00:01:36,140 --> 00:01:40,410 So the first question could be, is the top part of the image blue? 23 00:01:41,550 --> 00:01:44,160 If yes, you could go to the right and 24 00:01:44,160 --> 00:01:48,660 then ask the next question, is the bottom part of the image blue? 25 00:01:48,660 --> 00:01:52,210 If yes, you would go right, if no you would go left. 26 00:01:52,210 --> 00:01:56,940 And so on until you reach one of these leaf nodes and the leaf node then 27 00:01:56,940 --> 00:02:01,050 indicates if the image is actually an indoor image or an outdoor image. 28 00:02:03,150 --> 00:02:07,660 So this is naturally a very simple example it will fail most of the time but 29 00:02:07,660 --> 00:02:11,620 it should give you an intuition how these procedures work. 30 00:02:11,620 --> 00:02:17,180 In medicine you would for example ask questions about gene expression or 31 00:02:17,180 --> 00:02:23,790 protein concentration, or any other value you can measure and which is interesting, 32 00:02:23,790 --> 00:02:27,790 and the leaf nodes for example would indicate if a patient has cancer or not. 33 00:02:29,160 --> 00:02:33,253 In space exploration, we would be interested, for example, in surface 34 00:02:33,253 --> 00:02:37,752 features and asteroids, and we will talk about that in one of the later modules. 35 00:02:41,217 --> 00:02:48,070 So, in practice we represent samples in our data set with a feature vector. 36 00:02:48,070 --> 00:02:52,340 So, features or attributes describe objects. 37 00:02:52,340 --> 00:02:56,550 So, in this case we have a two dimensional Feature Space, and 38 00:02:56,550 --> 00:02:57,930 we have two kinds of objects. 39 00:02:57,930 --> 00:03:03,480 A positive class with red pluses and a negative class with the green minuses. 40 00:03:04,990 --> 00:03:08,790 And they are described by two features, x1 and x2. 41 00:03:08,790 --> 00:03:13,250 So these could be for example, weight and height of persons. 42 00:03:13,250 --> 00:03:18,220 These could be two genes, these could be two visual features. 43 00:03:18,220 --> 00:03:24,870 This could be two astronomical features describing stars, for example. 44 00:03:24,870 --> 00:03:30,840 And what you can see is that the feature space is in the feature space, 45 00:03:30,840 --> 00:03:33,260 the two classes are very mixed. 46 00:03:33,260 --> 00:03:38,000 And if you want to now train a classifier, to differentiate these two classes, 47 00:03:38,000 --> 00:03:39,610 it's not entirely trivial. 48 00:03:41,190 --> 00:03:44,980 So in practice, one could think of a linear classifiers or 49 00:03:44,980 --> 00:03:49,650 combinations of these features and try to split the data set 50 00:03:49,650 --> 00:03:55,100 based on some linear combination of x1 and x2 which in this case 51 00:03:55,100 --> 00:03:59,960 clearly would not work regardless where we try to make this decision boundary. 52 00:04:01,630 --> 00:04:05,920 So in practice, what we want to do is we want to use a method which can 53 00:04:05,920 --> 00:04:11,210 flexibly partition the feature space into sub-partitions where 54 00:04:11,210 --> 00:04:13,140 each partition at the end will presents a leaf node. 55 00:04:15,080 --> 00:04:17,460 So when we learn a decision tree and 56 00:04:17,460 --> 00:04:24,270 I will explain decision tree learning based on what we do for random forests. 57 00:04:24,270 --> 00:04:27,950 There are lot of different techniques how that could be done, but 58 00:04:27,950 --> 00:04:30,030 I will talk about the most commonly used one. 59 00:04:31,820 --> 00:04:37,450 So in decision tree learning, you would start by looking at all the different 60 00:04:37,450 --> 00:04:41,990 axis, the different kinds of feature and try all possible split nodes and 61 00:04:41,990 --> 00:04:46,990 then choose one of them satisfying some kind of criterium. 62 00:04:46,990 --> 00:04:50,750 In this case it could be the misclassification rate. 63 00:04:50,750 --> 00:04:56,640 So you want to find the vertical split number one, which past separates 64 00:04:56,640 --> 00:05:02,089 into two sets of samples into both positive or negative ones. 65 00:05:04,040 --> 00:05:08,280 Then in the next step you would go recursively down the tree and 66 00:05:08,280 --> 00:05:13,930 then look only on the left part so and, after you split with 67 00:05:13,930 --> 00:05:18,500 a feature one and then you would decide what kind of feature this could be 68 00:05:18,500 --> 00:05:22,740 again in our scenario feature one or two would separate this classes best. 69 00:05:23,930 --> 00:05:25,580 So, in the case on the left, 70 00:05:25,580 --> 00:05:30,460 there is a quite nice operation, which optimizes the misclassification rate. 71 00:05:32,610 --> 00:05:36,350 On the right side, again, you try to separate the space and 72 00:05:36,350 --> 00:05:38,490 come up with a feature. 73 00:05:38,490 --> 00:05:42,940 Then, this is continued until one of these classes is pure. 74 00:05:44,040 --> 00:05:48,910 So in decision tree learning for random forest, we would stop learning if you 75 00:05:48,910 --> 00:05:53,987 only have one sample within one of the sub-classes or 76 00:05:53,987 --> 00:05:59,340 sub-leaves or if the partition or samples in this partition would be from one class, 77 00:05:59,340 --> 00:06:00,380 we'll be able to have a pure leaf. 78 00:06:01,440 --> 00:06:04,980 In this case it's partition A, 79 00:06:04,980 --> 00:06:08,390 and everything inside would be the negative class. 80 00:06:10,400 --> 00:06:16,210 We then can continue that in all sub parts until we end up with a completely grown 81 00:06:16,210 --> 00:06:22,839 tree which completely separates the features space in only pure classes. 82 00:06:23,880 --> 00:06:26,710 So you can see at the leaf nodes on the right, 83 00:06:26,710 --> 00:06:32,620 some leafs represent the positive class, some represent the negative class. 84 00:06:34,520 --> 00:06:38,440 In practice, what you see here is over fitting example. 85 00:06:38,440 --> 00:06:44,510 So we completely over-fitted the feature space to nicely separate the classes. 86 00:06:44,510 --> 00:06:48,270 In practice this will lead to excellent training error, but 87 00:06:48,270 --> 00:06:50,210 to very poor generalization. 88 00:06:51,480 --> 00:06:56,200 And in practice, to overcome that, if one only trains one tree, 89 00:06:56,200 --> 00:07:01,541 one would use pruning strategies where you actually limit the depth 90 00:07:01,541 --> 00:07:07,200 of this trees to generalize better or you could use something 91 00:07:07,200 --> 00:07:11,440 like random forests where all these tress are learned from different kinds of data. 92 00:07:13,950 --> 00:07:18,060 So now during testing we could just go down this tree. 93 00:07:18,060 --> 00:07:20,340 Let's see we now have a model. 94 00:07:20,340 --> 00:07:26,630 We get a new sample and that's a new person with height and weight or 95 00:07:26,630 --> 00:07:31,490 a new biologic example with expression of two genes that's the yellow 96 00:07:31,490 --> 00:07:36,380 star on the left and if you want to classify it for being either red or green. 97 00:07:37,610 --> 00:07:40,800 So we would start at the top of this tree and 98 00:07:40,800 --> 00:07:43,880 then successively ask all these question. 99 00:07:43,880 --> 00:07:47,860 So the first question would be, is feature one, 100 00:07:47,860 --> 00:07:53,630 which is our x axis, larger than the threshold at one, then we go to the right, 101 00:07:53,630 --> 00:07:59,360 then we check the threshold on feature b for, split node three. 102 00:07:59,360 --> 00:08:04,650 And we also go to the right, and we come to, number six which, again, 103 00:08:04,650 --> 00:08:09,450 checks the feature, does, split on feature two and so 104 00:08:09,450 --> 00:08:12,180 on, until we end up at a leaf node. 105 00:08:13,620 --> 00:08:18,740 And this leaf node, in this case the partition F, is completely green, so 106 00:08:18,740 --> 00:08:20,260 that's a negative class. 107 00:08:20,260 --> 00:08:25,450 So we would classify the new sample as green, in this case. 108 00:08:28,820 --> 00:08:35,220 So, what you can see here are different properties of a random forest already. 109 00:08:35,220 --> 00:08:39,730 So, first of all, in practice, you would not only two features as in this case but 110 00:08:39,730 --> 00:08:42,460 you would, would have a whole set of features. 111 00:08:42,460 --> 00:08:46,390 So, for vision examples, the number of features quite often go into 112 00:08:46,390 --> 00:08:51,959 the millions for DNA micro-arrays, you would have hundreds of thousands. 113 00:08:53,430 --> 00:08:55,340 For some astronomic scenarios, 114 00:08:55,340 --> 00:09:00,190 you would have very sophisticated features which go into the hundreds. 115 00:09:00,190 --> 00:09:01,910 But the tree would, first of all, 116 00:09:01,910 --> 00:09:05,450 operate in a much more high dimensional case as in this simple example. 117 00:09:07,170 --> 00:09:11,260 But regardless how big the space is, during test time, when we 118 00:09:11,260 --> 00:09:16,600 actually go down this tree, we would only check this, in this case, four conditions. 119 00:09:17,740 --> 00:09:20,000 So it's very fast. 120 00:09:20,000 --> 00:09:26,313 It can be implemented enormously fast and that gives you a huge benefit for real 121 00:09:26,313 --> 00:09:33,367 time applications like autonomous driving for robots or decision making in medicine. 122 00:09:37,716 --> 00:09:41,657 So in the example before, we used split nodes or 123 00:09:41,657 --> 00:09:47,940 also they are also cal, called weak learners, which were decision stops. 124 00:09:47,940 --> 00:09:53,800 So these are axis parallel splits, at each split node. 125 00:09:53,800 --> 00:09:57,940 But theoretically, we could use any kind of function at these nodes. 126 00:09:57,940 --> 00:10:02,000 So, we could, for example, use linear combinations of features as seen in 127 00:10:02,000 --> 00:10:07,890 in the center plot or as seen on the right plot, we could use for example, conic cuts 128 00:10:07,890 --> 00:10:14,480 to get a more localized estimation of these features. 129 00:10:14,480 --> 00:10:18,920 Theoretically, one could actually use trees, neural network or 130 00:10:18,920 --> 00:10:21,370 support vector machines that these splits but 131 00:10:21,370 --> 00:10:25,710 that would actually defy the reason to use these trees and 132 00:10:25,710 --> 00:10:32,065 that's this enormous simplicity and transparence of the final model. 133 00:10:32,065 --> 00:10:36,709 [SOUND] So, another difference which is important for 134 00:10:36,709 --> 00:10:41,351 our applications is that, what I showed you before, 135 00:10:41,351 --> 00:10:46,737 was a tree which was learned until you only have poor classes. 136 00:10:46,737 --> 00:10:50,160 So, every leaf node represents only one class. 137 00:10:50,160 --> 00:10:55,000 But nowadays, in most examples we would not do that especially if 138 00:10:55,000 --> 00:10:59,830 you have millions of samples like in the image specification tasks. 139 00:10:59,830 --> 00:11:03,774 You would not want to trend trees which, which are thousands of level deep or 140 00:11:03,774 --> 00:11:05,042 hundreds of levels deep. 141 00:11:05,042 --> 00:11:09,600 But you would like to stop earlier and then you would have a mixture 142 00:11:09,600 --> 00:11:14,400 of samples at each leaf node, and that gives rise to a posterior estimate. 143 00:11:15,580 --> 00:11:22,550 So, the histograms at every leaf are a proxy for a posterior for a random forest. 144 00:11:22,550 --> 00:11:28,580 So, if you have, for example, in this case, we have four different classes blue, 145 00:11:28,580 --> 00:11:32,650 yellow, red and green, evenly balanced on the right. 146 00:11:32,650 --> 00:11:34,040 And, then if you go down the tree, and 147 00:11:34,040 --> 00:11:40,080 the, the leaf nodes are not pure, but you would have a dominant class. 148 00:11:40,080 --> 00:11:44,750 For example, at the bottom right you would have red which is dominating, but 149 00:11:44,750 --> 00:11:46,580 you would also have the other classes. 150 00:11:47,710 --> 00:11:52,830 That then can be used to actually quantify the uncertainty of the tree. 151 00:11:52,830 --> 00:11:57,700 So, if all the classes have nearly equal weight, that would indicate that, 152 00:11:57,700 --> 00:12:02,480 that classifier is quite unsure of what's a prominent class but if you would have, 153 00:12:02,480 --> 00:12:05,570 as in this case, dominating class, 154 00:12:05,570 --> 00:12:09,410 you would, with high confidence, classify and use sample as red. 155 00:12:12,360 --> 00:12:12,860 Thank you.