Classification: nearest neighbours and decision trees

About six weeks in, the course has covered unsupervised learning and, within supervised learning, regression: linear, kernel, ridge and LASSO (Parts 10 to 12). The next supervised problem is classification, which is far more widely applied.

Classification comes in two forms: binary, with two classes, and multi-class, with several. The course concentrates on binary classification. It is the most basic form, and once it is understood its ideas usually carry over to the multi-class problem with little change.

This is the regression setup (Part 10) with the labels restricted to two values. Which two numbers name the classes does not matter; some algorithms are neater with \(\{0, 1\}\), others with \(\{-1, +1\}\). In spam detection, for example, spam could be 1 and non-spam 0, or the other way round, or \(+1\) and \(-1\).

Regression measured the error of a function with the squared loss. For classification the intuitive error of a candidate \(h\) is the fraction of training points it gets wrong:

Each mistake costs 1 and each correct prediction costs 0, so the lecture names this the 0-1 loss. It suits classification better than the squared loss because all we care about is whether a prediction is right. The real goal is to be right on as many test points as possible; the training error is the proxy we can measure.

The overfitting argument from regression (Part 10) returns unchanged. If \(h\) may be any function, the training error can always be made 0, but such an \(h\) has probably fitted the noise as well. So the search is restricted to a smaller class of functions, and, as in regression, the first choice is the linear ones.

A linear classifier still combines the features linearly, as \(\mathbf{w}^\top\mathbf{x}\), and then thresholds the result at 0. The class of all of them is

In pictures, \(\mathbf{w}\) defines the hyperplane \(\mathbf{w}^\top\mathbf{x} = 0\) through the origin (a line in two dimensions). Points on the side \(\mathbf{w}\) points towards have \(\mathbf{w}^\top\mathbf{x} > 0\) and are predicted positive; points on the other side are predicted negative.

A point exactly on the hyperplane has \(\mathbf{w}^\top\mathbf{x} = 0\), a tie between the classes 8:41. The definition above sends it to the negative class. Calling it positive instead, or tossing a coin, would do just as well. With this class fixed, the learning problem becomes

For regression we took the gradient of the squared loss, set it to zero and solved (Part 10). That route does not work here. In general, finding the linear classifier with the smallest 0-1 loss on a given data set is NP-hard: no efficient algorithm for it is known. "In general" matters. For some data sets the problem is easy, and later lectures use such cases.

The difficulty comes from the loss. The squared loss changes smoothly as the prediction moves away from the real-valued label and can take any value from 0 to \(\infty\). Each term of the 0-1 loss takes only the values 0 and 1, so the total jumps between a few levels as \(\mathbf{w}\) changes. It is neither continuous nor differentiable, and minimizing it turns into a discrete search problem.

The 0-1 loss is what we want to minimize, and we cannot minimize it efficiently. Some other route is needed.

Part 18 comes back to the 0-1 loss and the surrogate losses that classification algorithms minimize in its place.

Regression allows any real-valued label, while classification restricts the labels to two values. So it looks as if regression already solves a broader problem, and we could simply reuse it.

1. Least squares as a classifier
2. Input \((\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\) with \(y_i \in \{-1, +1\}\).
3. Run plain (unregularized) linear regression to get \(\mathbf{w} \in \mathbb{R}^d\). Adding regularization (Part 12) would not change the argument much.
4. Threshold at \(\mathbf{w}^\top\mathbf{x} = 0\): use \(h_\mathbf{w}(\mathbf{x}) = \operatorname{sign}(\mathbf{w}^\top\mathbf{x})\) as the classifier.

This minimizes the squared loss, and that is where it goes wrong. The lecture's example has positive and negative points in two dimensions, and regression returns a \(\mathbf{w}\) whose line separates them well. Now add a bunch of positive points far away on the positive side. For classification they change nothing, because the old line still separates every point.

Regression, though, compares \(\mathbf{w}^\top\mathbf{x}\) with the label value itself. For the far points \(\mathbf{w}^\top\mathbf{x}\) is large, so \((\mathbf{w}^\top\mathbf{x} - 1)^2\) is large. To bring it down, least squares tilts \(\mathbf{w}\), and further points elsewhere tilt it again. The tilted line can misclassify points that were right before, even though a line with no mistakes exists.

So applying regression directly to classification and hoping for good test accuracy is not a good idea.

We seem to be stuck. The most natural loss for classification is NP-hard to minimize, and regression is the wrong tool. This is the main reason the course meets so many binary classification algorithms, while regression has one standard method, least squares. Each algorithm gets around the hardness in its own way, by making different assumptions.

The next lectures start with the simplest possible classification algorithms and then move to more principled ones. L41 ends with a question to think about before L42: forgetting everything above, given a training set and a new point, what is the simplest way to predict the new point's label?

If a new point were already in the training set, we would just return its label. Test points are almost never in the training set. The simplest alternative is to find the training point that looks most like the test point, the closest one, and copy its label.

1. Nearest neighbour
2. Given a test point \(\mathbf{x}_\text{test} \in \mathbb{R}^d\).
3. Find \(\mathbf{x}^*\), the point in the training set closest to \(\mathbf{x}_\text{test}\).
4. Predict \(\hat y_\text{test} = y^*\), the label of \(\mathbf{x}^*\).

What can go wrong? Data sets are always noisy, and we rarely know how one was put together. A point may have been labelled wrongly by a person, or sit where it should not: a \(+1\) point among \(-1\) points, or the reverse. If the nearest neighbour happens to be such an outlier, the algorithm cannot tell and copies the wrong label.

Nearest-neighbour prediction is affected by outliers.

The fix is to get more than one opinion: ask \(k\) neighbours and take the majority. The hope is that most of the \(k\) neighbours are not outliers. If most of them did carry the "odd" label, they would not really be outliers; they would be the local structure of the data.

1. k-NN (k-nearest neighbours)
2. Given \(\mathbf{x}_\text{test}\) and the number of neighbours \(k\).
3. Find the \(k\) training points closest to \(\mathbf{x}_\text{test}\): \(\mathbf{x}_1^*, \mathbf{x}_2^*, \dots, \mathbf{x}_k^*\). They depend on \(\mathbf{x}_\text{test}\).
4. Predict \(\hat y_\text{test} = \text{majority vote of } y_1^*, y_2^*, \dots, y_k^*\).

This is the first binary classification algorithm of the course, and a very simple one: look at your neighbours and follow the majority. Before trusting any algorithm we should ask what it assumes, what can go wrong, and whether it is practical to run. The rest of L42 asks these questions of k-NN.

The algorithm needs \(k\) as an input, and the data does not say what it should be. To see how \(k\) matters, look at the decision boundary: treat every point of the input space as a potential test point and ask which label the algorithm would predict there. The lecture recommends asking this of every algorithm in the course, since it shows where the algorithm says \(+1\) and where it says \(-1\).

k = 1: holes around outliers

In the lecture's two-dimensional picture the \(-1\) points sit in two outer groups with the \(+1\) points between them, plus one stray \(+1\) point among the \(-1\)s on one side and a stray \(-1\) among the \(+1\)s. With \(k = 1\), every location takes the label of its single closest training point. The outer regions come out \(-1\) and the middle \(+1\), except for a hole around each stray point: a \(+1\) island inside a \(-1\) region, and a \(-1\) island inside the \(+1\) region.

The real structure has three parts: \(-1\), then \(+1\), then \(-1\). Because of the outliers, \(k = 1\) cuts the space into more pieces than that. This is the outlier sensitivity from before, now visible as holes in the decision boundary.

Standard fact, not stated in the lecture: the 1-NN regions are unions of the Voronoi cells of the training points, the same cells that appear for K-means in Part 7.

k = n: one label everywhere

If \(k\) equals the number of training points, every training point votes on every test point. The vote is then the same everywhere: the majority label of the whole training set. In the lecture's picture there are more \(-1\) points (two groups) than \(+1\) points (one group), so all of \(\mathbb{R}^2\) is predicted \(-1\). This is clearly bad too.

Somewhere in between

Asking too few neighbours lets outliers through; asking too many drowns out the local structure. Some \(k^*\) in between ignores the outliers and recovers the three-part structure. Too small a \(k\) gives a boundary that is too rugged, with holes, and too large a \(k\) gives one that is too smooth. In general, the smaller the \(k\), the more complicated the decision boundary.

\(k\) is supplied to the algorithm, which then runs with it. That makes it a hyperparameter: something passed into the algorithm rather than learnt by it, exactly as in regression (cross-validation in Part 11, the regularization strength in Part 12).

The solution is to cross-validate for \(k\). Try several values of \(k\), measure the accuracy of each on held-out validation data, and keep the \(k\) with the best validation accuracy. The hope is that this \(k\) captures the structure in the data and not the outliers. The "Choose k by validation" button in the figure above does exactly this on its synthetic validation set.

With \(k\) settled, is k-NN the answer to binary classification? It has several issues.

Which distance?

Why should Euclidean distance decide who counts as a neighbour? Different features may need different notions of closeness: some measured one way, some with the L2 distance, and so on. The lecture sets this aside by supposing that a domain expert can design a distance that suits the data at hand.

Prediction is expensive

The more pressing problem shows up at prediction time. To predict for one \(\mathbf{x}_\text{test}\), the algorithm must find its \(k\) nearest training points. With a billion training points, that means computing a billion distances and sorting them, on the order of \(n \log n\) work. Hashing tricks or properties of the distance function can cut this down, but the cost still grows with the size of the data set, and the whole job is repeated for every new test point.

Prediction with k-NN is computationally expensive. This is its most visible problem.

Why is prediction so expensive? Because k-NN does not actually learn anything. Every prediction needs the entire data set; nothing useful is extracted from the data and kept. The extracted useful information is what we call a model, and k-NN has none. So the data can never be thrown away after "learning".

This is the fundamental issue, and it remains even with a well-chosen \(k\), a good distance function and plenty of computing power. The course opened with comprehension is compression (Part 2): you have learnt from data once its structure is captured in a succinct model and the data itself is no longer needed. k-NN extracts no compressed information at all.

Every algorithm from here on extracts a model from the data. Which model depends on what we assume about the data, and different assumptions lead to different algorithms.

The next algorithm is still simple and very popular, but it extracts a compact, interpretable model and does not need the data set at prediction time.

We want an algorithm that learns a model from the data, so that the data can be discarded and only the model used for test points. The decision tree is such an algorithm. It is simple and very popular, and several more complicated algorithms later in the course are built on it (Part 17).

The tree is a rooted binary tree in the computer-science sense. Each internal node holds a question with a yes/no answer and has two children, one per answer. Each leaf holds a decision, 1 or 0; for this algorithm the lecture writes 0 for the negative class. Leaves are also called prediction nodes.

Prediction is easy. Pass \(\mathbf{x}_\text{test}\) in at the root and answer the questions in turn: yes takes you to the left child, no to the right. The answers trace out a path, every path ends at a leaf, and the value in that leaf is \(\hat y_\text{test}\).

The model that k-NN lacked is the tree. Once it is built, it holds everything from the data set that prediction needs, so the data can be thrown away. Prediction is also fast: answer a few questions and read the leaf.

A question is a feature-value pair

Before building a tree we fix what kind of question it may ask. A question is a feature-value pair. With feature height and value 180 cm, the question is "is height \(\le\) 180 cm?". In general, for feature \(k\) and value \(\theta\), the question is \(f_k \le \theta\)?, and the tree is restricted to questions of this form.

The tree is built greedily 8:05: find the best question to ask first, then expand the tree below it. So we need a way to measure how good a question is. A useful way in is to ask what the best possible question would look like.

What a question does to the data

Put one question, say "height \(\le\) 130 cm?", to every point of the data set \(D\). Each point answers yes or no, so the question partitions \(D\) into two parts: the points that answered yes (perhaps points 1 and 10, and so on) and those that answered no (points 2 and 3, and so on).

\(f_k(\mathbf{x}_i)\) is the value of feature \(k\) for point \(i\).

The ideal question

The best possible question would let us predict from its answer alone. That happens when every point in \(D_\text{yes}\) has label \(+1\) and every point in \(D_\text{no}\) has label \(-1\), or the other way round. One question would then separate the classes in the training set, and we would hope it does the same for test points: ask it, and read off the label. Both parts would be pure, meaning all the labels on each side are the same.

In reality no single question may split the data into pure sets. So we need to measure how impure each side is, and for that we need a measure of impurity for a set of labels.

Take any set of labels \(y_1, \dots, y_k\), each 1 or 0. It could be any size; for instance, the \(k\) points that answered yes. Summarize it by \(p\), the fraction of 1s, a number between 0 and 1. A measure of impurity should behave as follows.

• Zero at the ends. At \(p = 1\) every label is 1, and at \(p = 0\) every label is 0. Both sets are clean, so the impurity is 0.
• Largest at \(p = \tfrac12\). With half the labels 1 and half 0 we are most uncertain about the label, so this is the worst case.
• Symmetric about \(\tfrac12\). A set with 25% ones and 75% zeros is as confusing as one with 75% ones and 25% zeros; neither label is special. So the impurity at \(\lambda\) must equal the impurity at \(1 - \lambda\).

Many functions have these properties. A popular choice is the entropy. The entropy of a set of labels is the entropy of its fraction of 1s, since that fraction is what decides how pure the set is.

Entropy has information-theoretic justifications, which the lecture skips. Its roots are in statistical physics and thermodynamics, which is where the name comes from, and Shannon borrowed it for information theory. For our purposes it is simply a function that measures impurity.

A question \(f_k \le \theta\) splits \(D\) into \(D_\text{yes}\) and \(D_\text{no}\), and each of the three sets has an entropy: \(\text{Entropy}(D)\), \(\text{Entropy}(D_\text{yes})\) and \(\text{Entropy}(D_\text{no})\). Here the entropy of a set means the entropy of the fraction of 1s among its labels. These three numbers say how impure the data was before the question and how impure each side is after it.

To score the question with one number, ask how much impurity it removes. Start from the impurity we had, \(\text{Entropy}(D)\), and subtract a combination of the impurities of the two sides, weighted by the fraction of points that went to each side.

Why weight by the number of points?

Entropy looks only at the fraction of 1s and ignores how many points there are. Suppose a question sends a set of points to \(D_\text{yes}\) and 80% of them are 1s. If \(D_\text{yes}\) holds 10,000 points (8,000 of them 1s), that should give us more confidence in the prediction after asking the question than if it holds 100 points (80 of them 1s). Yet both sides have the same entropy. Likewise, 9,900 ones out of 10,000 is exactly as impure by entropy as 99 out of 100, but the first question classifies far more points. Weighting by \(\gamma\) and \(1 - \gamma\) builds this in.

With base-2 logs, the 80% sets have entropy 0.722 and the 99% sets 0.081, whatever their size.

The perfect question

If a question makes both sides pure, both entropies are 0 and the gain is the whole of \(\text{Entropy}(D)\): all the impurity we started with is removed. The more the impurity drops, the more we learn about the label by asking, which is why the drop is called a gain in information.

A small example, computed for these notes: \(D\) has 8 points, 4 ones and 4 zeros, so \(\text{Entropy}(D) = 1\).

B is the perfect question. C makes one side pure, but that side holds a single point, so it earns less than A.

Information gain scores one feature-value pair. The features come with the data, but which values \(\theta\) should be tried? The natural choice is to discretize each feature over its [min, max] range in the data. If the heights in the data run from 100 to 200, cut that range into 10 partitions, which gives the questions height \(\le\) 100, height \(\le\) 110, height \(\le\) 120, …, height \(\le\) 200.

1. Decision tree (greedy, by information gain)
2. For each feature, discretize its [min, max] range in the current data set into a set of values \(\theta\). Every pair \(f_k \le \theta\) is a candidate question.
3. Pick the candidate with the largest information gain.
4. It splits the data into \(D_\text{yes}\) and \(D_\text{no}\). Each is a new data set: the points that answered yes, and the points that answered no.
5. Repeat the procedure on \(D_\text{yes}\) and on \(D_\text{no}\) separately. Say the best question on the yes side is \(f_l \le \theta_l\) and on the no side \(f_r \le \theta_r\); each splits its set again, and so on.
6. Stop growing a branch when one of the stopping rules in the next section applies, and make that node a leaf.

Some candidates can be dropped along the way. Suppose the root asks \(f_k \le \theta_k\). Every point in \(D_\text{yes}\) already satisfies \(f_k \le \theta_k\), so on that side a question \(f_k \le \theta\) with \(\theta\) larger than \(\theta_k\) gets "yes" from everyone and splits nothing. Such questions are useless there and can be left out. The best question is then found among the remaining ones.

The greedy procedure can keep building the tree as far as we let it. The lecture gives two points to keep in mind while growing it, and a remark on the impurity measure.

Stop when a node is pure enough

Complete purity is not required. If the fraction of 1s at a node is above 0.9, make the node a leaf with label 1; if it is below 0.1, make it a leaf with label 0. The thresholds are chosen heuristically.

Limit the depth

Even with a purity threshold, the tree may need many questions before a node becomes pure enough, and pushing for more and more purity tends to fit the noise. The depth of the tree is the number of questions asked before answering 1 or 0 for a test point, or equivalently the longest path from the root to a leaf. Treat it as a hyperparameter and do not grow the tree beyond it.

A branch that becomes pure enough before the depth limit stops there. A branch that does not is still cut off at the limit rather than allowed to grow forever. To choose the limit, cut the tree at different depths, measure the accuracy on a validation set, and keep the depth with the highest validation accuracy. In other words, cross-validate the depth.

Depth plays the role for a decision tree that \(k\) plays for k-NN: it controls how smooth the decision boundary is.

The lecture does not say which label a leaf gets when it is cut off by the depth limit. The usual choice is the majority label of the points that reach it.

Other impurity measures L44 · 7:14

Entropy is one popular measure of the goodness of a question. Another popular one is the Gini index. They come from different motivations, but for our purposes any reasonable function works if it is 0 at \(p = 0\) and \(p = 1\), peaks at \(p = \tfrac12\) and is symmetric about \(\tfrac12\).

The lecture does not write the Gini index down. Its standard two-class form is \(\text{Gini}(p) = 1 - p^2 - (1-p)^2 = 2p(1-p)\), which has all three properties.

What decision boundary comes out of a tree? The lecture's example has two features, \(f_1\) = height and \(f_2\) = weight, and a tree built from some data set:

• Root: \(f_1 \le 5\)? If no, predict 1.
• If yes, ask \(f_2 \le 7\)? If no, predict 0.
• If yes, ask \(f_1 \le 3\)? If yes, predict 1; if no, predict 0.

The first question cuts the plane at \(f_1 = 5\), and the whole region to the right is class 1 at once. To the left, the second question cuts at \(f_2 = 7\), and the part above is class 0. Below that, the third question asks about height again. A feature can repeat further down the tree, but only with a smaller value here: after \(f_1 \le 5\), asking \(f_1 \le 6\) would be pointless, while \(f_1 \le 3\) still splits.

Three of the four regions are pure. Region A still contains one class-0 point. A carefully cross-validated tree stops here and treats that point as an outlier. A tree that demands complete purity would not stop. It would keep asking questions about this region, cutting it into smaller pieces until the outlier sits in a box of its own labelled 0. That is overfitting.

Trees cut space into rectangles

Each question "feature \(\le\) value" divides a region in two with a line parallel to one of the axes. So a decision tree carves the space into rectangles. However intermingled the two classes are, rectangles small enough can enclose each point, and the number of points reaching a node shrinks with every question. In the worst case a leaf ends up with a single point, which is pure by default. So a tree grown long enough always makes every node completely pure, unless the same data point appears with both labels, which we assume does not happen.

Seeking purity is therefore a bad idea, because it fits the noise. A \(k\) that is too small made the k-NN boundary non-smooth; a tree grown too deep leaves small holes in the same way. Cross-validation catches this. In the lecture's illustration a validation point falls in the region around the outlier. The overgrown tree predicts it wrongly, while a smoother tree with a cross-validated depth predicts it correctly and is preferred. The hope is that the cross-validated depth captures the structure of the data much better.

The main reason is that trees are interpretable. Picture a doctor using a tree on a patient's vital parameters, such as blood pressure and temperature, to decide whether the patient has a particular disease. If the system says yes, the doctor has to act on it, and so wants to know why the system said so.

A tree gives that explanation directly. The patient was predicted to have the disease because the temperature was above some value, the blood pressure was below some value, and so on: the questions along the path to the leaf. The doctor can then bring in his or her own domain expertise to make further inferences.

This works only when the path is short. A list of 100 conditions explains nothing to anyone, so shorter trees are better for explaining. In most real-world data sets one hopefully does not need more than about 10 questions, which a person can still follow.

And unlike k-NN, a tree is a model derived from the data. Once it is built, the data points are no longer needed.

Binary classification now has two simple algorithms.

Both are reasonable, and the decision tree is a good algorithm because it gives a model. But neither makes any assumption about the data: give either one any data and it will try to produce a good answer. If we can make reasonable assumptions about the data, we can design algorithms better suited to them.

Making assumptions about data means understanding the structure in it and the noise in it, and reasoning about noise means reasoning about probabilities. Probability has not appeared at all in the classification algorithms so far. The next lectures model how the data itself is generated, in two different ways, and each way leads to a family of classification algorithms. Part 14 starts with generative and discriminative models.

Binary classification

Supervised learning with two classes, labelled \(\{0, 1\}\) or \(\{-1, +1\}\).

0-1 loss

The fraction of training points misclassified, \(\frac1n\sum_i \mathbf{1}(h(\mathbf{x}_i) \ne y_i)\). NP-hard to minimize over linear classifiers in general.

Linear classifier

\(h_\mathbf{w}(\mathbf{x}) = \operatorname{sign}(\mathbf{w}^\top\mathbf{x})\): predicts by the side of the hyperplane \(\mathbf{w}^\top\mathbf{x} = 0\) a point lies on.

Outlier

A point whose label disagrees with its surroundings, for example through a labelling error.

k-nearest neighbours (k-NN)

Predict the majority label of the \(k\) training points closest to the test point.

Decision boundary

The map of which label an algorithm predicts at every location of the input space, and where that label changes.

Hyperparameter

A setting passed into an algorithm rather than learnt, such as \(k\) or the tree depth; chosen by cross-validation.

Decision tree

A binary tree with a yes/no question at each internal node and a prediction at each leaf; the tree is the model.

Question

A feature-value pair, "\(f_k \le \theta\)?"; it splits a data set \(D\) into \(D_\text{yes}\) and \(D_\text{no}\).

Pure set

A set of points that all have the same label.

Entropy

Impurity of a set with fraction \(p\) of 1s: \(-[p\log p + (1-p)\log(1-p)]\). Zero for pure sets, largest at \(p = \tfrac12\).

Information gain

\(\text{Entropy}(D)\) minus the size-weighted entropies of \(D_\text{yes}\) and \(D_\text{no}\); the goodness of a question.

Depth

The longest root-to-leaf path in a tree: the most questions asked before a prediction.

Gini index

Another popular impurity measure; any function that is 0 at \(p = 0, 1\), peaks at \(\tfrac12\) and is symmetric will do.