6.034 Notes: Sections 10.2-10.3

6.034 Notes: Section 10.2 Slide 10.2.1 Now, let's go back to decision trees, and see if we can apply them to problems where the inputs are numeric. Slide 10.2.2 When we have features with numeric values, we have to expand our hypothesis space to include different tests on the leaves. We will allow tests on the leaves of a decision tree to be comparisons of the form xj > c, where c is a constant. Slide 10.2.3 This class of splits allows us to divide our feature-space into a set of exhaustive and mutually exclusive hyper-rectangles (that is, rectangles of potentially high dimension), with one rectangle for each leaf of the tree. So, each rectangle will have an output value (1 or 0) associated with it. The set of rectangles and their output values constitutes our hypothesis. Slide 10.2.4 So, in this example, at the top level, we split the space into two parts, according to whether feature 1 has a value greater than 2. If not, then the output is 1. Slide 10.2.5 If f1 is greater than 2, then we have another split, this time on whether f2 is greater than 4. If it is, the answer is 0, otherwise, it is 1. You can see the corresponding rectangles in the two-dimensional feature space. Slide 10.2.6 This class of hypotheses is fairly rich, but it can be hard to express some concepts. There are fancier versions of numeric decision trees that allow splits to be arbitrary hyperplanes (allowing us, for example, to make a split along a diagonal line in the 2D case), but we won't pursue them in this class. Slide 10.2.7 The only thing we really need to do differently in our algorithm is to consider splitting between each data point in each dimension. Slide 10.2.8 So, in our bankruptcy domain, we'd consider 9 different splits in the R dimension (in general, you'd expect to consider m - 1 splits, if you have m data points; but in our data set we have some examples with equal R values). Slide 10.2.9 And there are another 6 possible splits in the L dimension (because L is an integer, really, there are lots of duplicate L values). Slide 10.2.10 All together, this is a lot of possible splits! As before, when building a tree, we'll choose the split that minimizes the average entropy of the resulting child nodes. Slide 10.2.11 Let's see what actually happens with this algorithm in our bankruptcy domain. We consider all the possible splits in each dimension, and compute their average entropies. Slide 10.2.12 Splitting in the L dimension at 1.5 will do the best job of reducing entropy, so we pick that split. Slide 10.2.13 And we see that, conveniently, all the points with L not greater than 1.5 are of class 0, so we can make a leaf there. Slide 10.2.14 Now, we consider all the splits of the remaining part of the space. Note that we have to recalculate all the average entropies again, because the points that fall into the leaf node are taken out of consideration. Slide 10.2.15 Now the best split is at R > 0.9. And we see that all the points for which that's true are positive, so we can make another leaf. Slide 10.2.16 Again we consider all possible splits of the points that fall down the other branch of the tree. Slide 10.2.17 And we find that splitting on L > 5.0 gives us two homogenous leaves. Slide 10.2.18 So, we finish with this tree, which happens to have zero error on our data set. Of course, all of the issues that we talked about before with boolean attributes apply here: in general, you'll want to stop growing the tree (or post-prune it) in order to avoid overfitting. Slide 10.2.19 We ran this decision-tree algorithm on the heart-disease data set. This graph shows the crossvalidation accuracy of the hypotheses generated by the decision-tree algorithm as a function of the min-leaf-size parameter, which stops splitting when the number of examples in a leaf gets below the specified size. The best performance of this algorithm is about .77, which is slightly worse than the performance of nearest neighbor. Slide 10.2.20 But performance isn't everything. One of the nice things about the decision tree algorithm is that we can interpret the hypothesis we get out. Here is an example decision tree resulting from the learning algorithm. I'm not a doctor (and I don't even play one on TV), but the tree at least kind of makes sense. The toplevel split is on whether a certain kind of stress test, called "thal" comes out normal. Slide 10.2.21 If thal is not normal, then we look at the results of the "ca" test. This test has as results numbers 0 through 3, indicating how many blood vessels were shown to be blocked in a different test. We chose to code this feature with 4 binary attributes. Slide 10.2.22 So "ca = 0" is false if 1 or more blood vessels appeared to be blocked. If that's the case, we assert that the patient has heart disease. Slide 10.2.23 Now, if no blood vessels appeared to be blocked, we ask whether the patient is having exerciseinduced angina (chest pain) or not. If not, we say they don't have heart disease; if so, we say they do. Slide 10.2.24 Now, over on the other side of the tree, where the first test was normal, we also look at the results of the ca test. Slide 10.2.25 If it doesn't have value 0 (that is one or more vessels appear blocked), then we ask whether they have chest pain (presumably this is resting, not exercise-induced chest pain), and that determines the output. Slide 10.2.26 If no blood vessels appear to be blocked, we consider the person's age. If they're less than 57.5, then we declare them to be heart-disease free. Whew! Slide 10.2.27 If they're older than 57.5, then we examine some technical feature of the cardiogram, and let that determine the output. Hypotheses like this are very important in real domains. A hospital would be much more likely to base or change their policy for admitting emergency-room patients who seem to be having heart problems based on a hypothesis that they can see and interpret rather than based on the sort of numerical gobbledigook that comes out of nearest neighbor or naive Bayes. Slide 10.2.28 We also ran the decision-tree algorithm on the Auto MPG data. We got essentially the same performance as nearest neighbor, and a strong insensitivity to leaf size. Slide 10.2.29 Here's a sample resulting decision tree. It seems pretty reasonable. If the engine is big, then we're unlikely to have good gas mileage. Otherwise, if the weight is low, then we probably do have good gas mileage. For a low-displacement, heavy car, we consider the model-year. If it's newer than 1978.5 (this is an old data set!) then we predict it will have good gas mileage. And if it's older, then we make a final split based on whether or not it's really heavy. It's also possible to apply naive bayes to problems with numeric attributes, but it's hard to justify without recourse to probability, so we'll skip it. %To do: %- add a slide showing how one non­ isothetic split would do the job, %but it requires a lot of rectangles. 6.034 Notes: Section 10.3 Slide 10.3.1 So far, we've spent all of our time looking at classification problems, in which the y values are either 0 or 1. Now we'll briefly consider the case where the y's are numeric values. We'll see how to extend nearest neighbor and decision trees to solve regression problems. Slide 10.3.2 The simplest method for doing regression is based on nearest neighbor. As in nearest neighbor, you remember all your data. Slide 10.3.3 When you get a new query point x, you find the k nearest points. Slide 10.3.4 Then average their y values and return that as your answer. Of course, I'm showing this picture with a one-dimensional x, but the idea applies for higherdimensional x, with the caveat that as the dimensionality of x increases, the curse of dimensionality is likely to be upon us. Slide 10.3.5 When k = 1, this is like fitting a piecewise constant function to your data. It will track your data very closely, but, as in nearest neighbor, have high variance and be prone to overfitting. Slide 10.3.6 When k is larger, variations in the data will be smoothed out, but then there may be too much bias, making it hard to model the real variations in the function. Slide 10.3.7 One problem with plain local averaging, especially as k gets large, is that we are letting all k neighbors have equal influence on the predicting the output of the query point. In locally weighted averaging, we still average the y values of multiple neighbors, but we weight them according to how close they are to the target point. That way, we let nearby points have a larger influence than farther ones. Slide 10.3.8 The simplest way to describe locally weighted averaging involves finding all points that are within a distance lambda from the target point, rather than finding the k nearest points. We'll describe it this way, but it's not too hard to go back and reformulate it to depend on the k nearest. Slide 10.3.9 Rather than committing to the details of the weighting function right now, let's just assume that we have a "kernel" function K, which takes the query point and a training point, and returns a weight, which indicates how much influence the y value of the training point should have on the predicted y value of the query point. Then, to compute the predicted y value, we just add up all of the y values of the points used in the prediction, multiplied by their weights, and divide by the sum of the weights. Slide 10.3.10 Here is one popular kernel, which is called the Epanechnikov kernel (I like to say that word!). You don't have to care too much about it; but see that it gives high weight to points that are near the query point (5,5 in this graph) and decreasing weights out to distance lambda. There are lots of other kernels which have various plusses and minuses, but the differences are too subtle for us to bother with at the moment. Slide 10.3.11 As usual, we have the same issue with lambda here as we have had with epsilon, min-leaf-size, and k. If it's too small, we'll have high variance; if it's too big, we'll have high bias. We can use crossvalidation to choose. In general, it's better to convert the algorithm to use k instead of lambda (it just requires making the lambda parameter in the kernel be the distance to the farthest of the k nearest neighbors). This means that we're always averaging the same number of points; so in regions where we have a lot of data, we'll look more locally, but in regions where the training data is sparse, we'll cast a wider net. Slide 10.3.12 Now we'll take a quick look at regression trees, which are like decision trees, but which have numeric constants at the leaves rather than booleans. Slide 10.3.13 Here's an example regression tree. It has the same kinds of splits as a regular tree (in this case, with numeric features), but what's different are the labels of the leaves. Slide 10.3.14 Let's start by thinking about how to assign a value to a leaf, assuming that multiple training points are in the leaf and we have decided, for whatever reason, to stop spliting. In the boolean case, we used the majority output value as the value for the leaf. In the numeric case, we'll use the average output value. It makes sense, and besides there's a hairy statistical argument in favor of it, as well. Slide 10.3.15 So, if we're going to use the average value at a leaf as its output, we'd like to split up the data so that the leaf averages are not too far away from the actual items in the leaf. Slide 10.3.16 Lucky for us, the statistics folks have a good measure of how spread out a set of numbers is (and, therefore, how different the individuals are from the average); it's called the variance of a set. Slide 10.3.17 First we need to know the mean, which is traditionally called mu. It's just the average of the values. That is, the sum of the values divided by how many there are (which we call m, here). Slide 10.3.18 Then the variance is essentially the average of the squared distance between the individual values and the mean. If it's the average, then you might wonder why we're dividing by m-1 instead of m. I could tell you, but then I'd have to shoot you. Let's just say that dividing by m-1 makes it an unbiased estimator, which is a good thing. Slide 10.3.19 We're going to use the average variance of the children to evaluate the quality of splitting on a particular feature. Here we have a data set, for which I've just indicated the y values. It currently has a variance of 40.5. Slide 10.3.20 We're considering two splits. One gives us variances of 3.7 and 1.67; the other gives us variances of 48.7 and 40.67. Slide 10.3.21 Just as we did in the binary case, we can compute a weighted average variance, depending on the relative sizes of the two sides of the split. Slide 10.3.22 Doing so, we can see that the average variance of splitting on feature 3 is much lower than of splitting on f7, and so we'd choose to split on f3. Just looking at the data in the leaves, f3 seems to have done a much better job of dividing the values into similar groups. Slide 10.3.23 We can stop growing the tree based on criteria that are similar to those we used in the binary case. One reasonable criterion is to stop when the variance at a leaf is lower than some threshold. Slide 10.3.24 Or we can use our old min-leaf-size criterion. Slide 10.3.25 Once we do decide to stop, we assign each leaf the average of the values of the points in it.