Machine Learning 1. Lecture 4. Metric Methods of Classification and Regression

What this lecture is about

Today, metric methods of supervised learning. They are probably the simplest methods in machine learning: what could be simpler than the nearest neighbour method? On the other hand, year after year I kept adding things to this lecture — it seemed very simple to me, so I added one interesting thing, then another — and as a result today's material is dense. Hold on, but you will learn a lot of interesting things.

The continuity and compactness hypotheses

Let us start with a very simple paradigm. In regression, when we recover one numerical quantity as a function of other numerical quantities, it seems that in nature we most often meet continuous functions. So the assumption that the dependence being recovered is continuous is, if not the most frequent, then the most obvious of everything that can occur.

There are samples where $y$ clearly depends continuously on $x$, and there are samples that are who knows what, some chaos, and it is not obvious whether there is any functional dependence at all. For classification problems the notion changes slightly, and since the sixties, including in the Russian literature, the term compactness hypothesis has been established. Compactness here is understood in the everyday sense, not at all in the sense of the definitions from courses in mathematical and functional analysis: what is meant is that classes are compact clumps of points. If the classes are mixed with each other chaotically, then it is probably some wrong problem: either the metric was introduced wrongly, or there are many errors in the data — in short, something is wrong with it.

The classic example is Fisher's irises: three classes of 50 specimens each, four features plotted against each other pairwise. One sees very well what we mean when we say that classes are compact clumps of points: here is one clump, here are two others, a little less separated from each other. If the clumps are well separated from each other, the problem is easy, and it probably does not even matter much which models we use to separate the classes — everything will work out well.

How to measure distances between objects

Let us get used to the terms. Of a distance function between two objects, as a rule, only non-negativity is required. A metric is a little more: it has an important property, the triangle inequality. When we say «metric methods of classification and regression», we mean that a distance function has been introduced, which is as a rule a metric. None of the methods explicitly requires the triangle inequality, and we will not talk about it further. But if it does not hold, it is intuitively clear that the distance function is somehow not quite right and may behave wrongly. So we mostly use metrics.

The first thing that comes to mind is the Euclidean metric in ${\mathbb{R}}^n$: squared differences, a square root; we have all long been used to it. In the generalized metric, parameters are introduced. The feature weights $w_j$ play two roles. The first is normalization, bringing features to a common scale: if one feature is measured in fractions of a unit and another in billions, then when they are added directly the second will simply drown out the first, and the first will not be visible against it. The second is setting the degree of importance, the informativeness, of the features. Another generalization is the exponent $p$: it need not be two. The geometry of the metric space depends on $p$ — what the level lines look like, the sets of points equidistant from a given one.

This is not the only way to introduce distances; we will not deal with such things further in the course, but so that you know what exists in the world. There are lots of problems on symbol strings, in particular many problems of bioinformatics, where there is a natural definition of the distance between strings. The simplest is the edit distance (the Levenshtein distance): how many insertions, substitutions and deletions have to be made to turn one string into another.

Something similar is done with signals. For example, in recognizing signatures or handwriting written with an electronic pen, the object is described by several curves: the coordinates of the pen, the direction of its motion, the azimuth; one could also introduce speed, tilt angle, pressure. How do we compare two handwritten letters? Take their signals and imagine that little springs are stretched between nearby points of the signals. To bring one signal to the other, some springs have to be compressed and some stretched; the energy of compression and stretching is the distance between the signals. Such methods are called alignment: one can align symbol sequences, and one can align signals. Images are compared in the same way, faces for example: we stretch a mesh over a face, each edge of which is a little spring, and compute the energy of compression and stretching needed to make one face from another. For similar faces this energy is small.

A signal or a symbol sequence can be of arbitrary length, and generating from it a vector of a fixed number of features (feature generation) is rather difficult. But measuring the distance between such objects directly may be much simpler. So metric methods can in general be feature-free: we can compute distances between objects but do not know any features.

The generalized metric classifier

Let us start with classification methods under the condition that we can measure the distance from any object to any object of the training sample $x_1,\dots ,x_{\ell }$. Let us agree on notation.

I begin straight away with the generalization; the other methods will be special cases. This is a heuristic, and it somewhat diverges from what I have been instilling in you since the first lecture: that we always write out an optimization criterion and find the model parameters by optimizing it. Not so here. This is the rarest case in machine learning where we build an algorithm without an optimization problem, which is why I say that metric algorithms are the simplest: no explicit optimization even takes place here. One could, of course, pose the inverse problem: construct the optimization functional that we implicitly optimize by writing out such an algorithm. That is not homework, but whoever is interested — try it as an exercise.

What does the algorithm consist of? We assign the object $x$ to the class whose objects are closest. We rank all the objects relative to $x$ by increasing distance and see which class has more objects among its neighbours. The degrees of closeness of the neighbours are summed separately for each class — the square bracket says we sum only over the objects of class $y$ — and we get ${\Gamma }_y(x)$. Everything depends on how the function $w$ is defined, and it can be defined in different ways; substituting different definitions into this formula, we will get different heuristic metric classification methods.

The $k$ nearest neighbours method

The simplest special case is the nearest neighbour method: the weight is one only for the first neighbour and zero for the others. What is bad about the first nearest neighbour? That it may by chance be in the wrong class. We should look at a neighbourhood of nearest neighbours and vote on which class has more. That is the $k$ nearest neighbours method ($k$ nearest neighbours, $k$NN) — voting over the $k$ nearest neighbours:

The method is very easy to implement. There is even a name for it — lazy learning: training comes down to memorizing the sample. In essence the method has one parameter, $k$, and it can be optimized. For this there is the criterion we talked about in the first lecture — leave-one-out:

We take as training objects the whole sample except one object $x_i$, exclude it from all neighbourhoods and see whether it was classified correctly. By the minimum number of errors we determine the optimal $k$. A small $k$ is bad because noisy data affects the result; a large $k$ is bad because we look at too large a neighbourhood and oversmooth. Somewhere in the middle an optimal $k$ can always be found.

The red curve also shows that the optimum is fairly wide: the data is noisy, but it does not matter how precisely the optimum is determined. Choosing parameters by leave-one-out occurs fairly often in machine learning, which is why I am talking about this plot for so long: remember that for many parameters LOO gives a characteristic optimum. It is good when it is wide.

Drawbacks of the $k$ nearest neighbours method:

• ambiguous classification when ${\Gamma }_y(x)={\Gamma }_s(x)$, $y\ne s$ — if among the nearest neighbours there are equal numbers of objects of different classes;
• the values of the distances are not taken into account. Suppose we take five nearest neighbours, four of them really are the nearest, and the fifth is somewhere out on its own and not a neighbour at all. We ranked the objects by distance, but the distances themselves are not taken into account, and that is probably wrong: the function $w$ should depend on them directly.

Weighted neighbours and the Parzen window method

Let us gradually deal with these drawbacks. To prevent ties among the estimates ${\Gamma }_y$, one can introduce weights that decrease with the neighbour's number: the farther the neighbour, the smaller its weight.

A linear dependence should not be used. Suppose, for example, there are two classes and four nearest neighbours: the first and fourth in one class, the second and third in the other. The estimates of the classes will be equal. A nonlinear decreasing function is needed, a geometric progression for example, and for two classes the problem is solved. But if there are three classes, ambiguity can still arise. For two classes there is also a simple solution — take an odd number of neighbours — but for three classes it may no longer work.

The next problem: how should the distances to the neighbours be taken into account? It is probably more correct for the weight to depend not on the neighbour's number but explicitly on the distance to it. Let us introduce a decreasing function $K$ of the distance $\rho$ — we will call it the kernel — and one more parameter $h$, the bandwidth.

The function $K$ can even be defined so that it is positive on the interval $[0,1]$ and zero outside it. Then all the neighbours at distances less than $h$ get nonzero weights, and the rest are not taken into account at all. Substituting such a function into the general metric classifier, we see another useful thing: we can get rid of the numbering of objects by neighbourhood altogether. The distances are taken into account explicitly, and the metric algorithm is written as a sum over all the objects of class $y$, where $K(\rho /h)$ is simply a closeness function.

One unpleasant point. In the $k$ nearest neighbours method we guarantee that there will be $k$ votes. But a window of width $h$ may contain no objects at all. Moreover, at one point of the space the neighbourhood of radius $h$ may contain a thousand objects, and at another none. These two ideas can be combined — closeness with a kernel and $k$ nearest neighbours — so that a given number of neighbours is guaranteed to fall into any neighbourhood. For this a variable window width is introduced: as $h$ we take the distance to the $(k+1)$th neighbour. Then the $(k+1)$th neighbour will most likely have zero weight, and the first $k$ are guaranteed nonzero weights. «Most likely» — assuming that all the distances are different.

By LOO one can optimize the window width $h$, if it is fixed, and the number of neighbours $k$, and also choose the kernel $K$. The plots have a characteristic minimum both in $h$ and in $k$.

The method of potential functions

Let us look at the Parzen window method and realise the following. We stood at the point $x$, the object to be classified, looked at its neighbourhood — $k$ nearest neighbours or of radius $h$ — and saw objects of which classes fall into it. One can look at the problem dually: stand at each object of the training sample and say that it spreads the potential of its class around itself over a neighbourhood of some radius. With each point of the training sample we associate two parameters: the radius of the potential $h_i$ and its amplitude ${\gamma }_i$. The method now has $2\ell$ parameters.

The analogy with electrostatics is very vivid: ${\gamma }_i$ is the size of the «charge» at the point $x_i$, $h_i$ the «range» of the potential centred at $x_i$, and $y_i$ the sign of the charge. In physics there are only two classes, charges $+1$ or $-1$, and from physics one can even take a formula for the kernel, $K(r)=\frac{1}{r}$ or $\frac{1}{r+a}$. But this is of course pure heuristics: in our case the kernel is an arbitrary decreasing function, and there is no reason to take it from electrostatics in particular. In classification problems there are no restrictions either on $K$ or on the number of classes. And if there are many classes, the analogy is more with a smell: each point spreads the smell of its class, and we stand at the point $x$, sniff and try to understand which class we are closer to.

Potential functions as a linear classifier

Another important insight: the method of potential functions can be written as a linear classifier. It would seem that the two methods were proposed from completely different heuristic principles. A linear classifier is a separating hyperplane; potential functions are the compactness hypothesis, a metric, converting distance into closeness. Yet the result turns out very similar. In the case of two classes, $Y=\{-1,+1\}$:

Here ${\Gamma }_{+1}(x)$ is an estimate of how close the objects of class $+1$ are to $x$, minus the same estimate for class $-1$. We took account of the minus in front of the sum over the objects of class $-1$ by multiplying by $y_i$. Compare with the linear classification model:

• $f_j(x)=y_{j}K(\frac{1}{h_j}\rho (x,x_j))$ are new features of the object $x$, the closeness (similarity) of the object $x$ and the training object $x_j$;
• ${\gamma }_j$ are the weights of the linear classifier;
• $n=\ell$: the number of features equals the number of training objects.

An interesting and unexpected turn. We always talked about the «objects–features» matrix, $\ell$ objects and $n$ features, while in metric methods there were initially no features, only distances between objects. It turns out that the distance from the object $x$ being classified to a training object, as a function of $x$, can be treated as a feature, and if we make closeness out of distance with a kernel — also a feature. The features are moreover parametrized: the radius $h_j$ sits in them, which would have to be determined somehow. But if we have estimated or roughly determined it somehow — for example, as the distance to the tenth neighbour, or such that the neighbourhood contains mainly objects of one class — and fixed it, then the method of potential functions becomes a linear classifier: the features are the closenesses to the objects of the training sample, the weights are the amplitudes of the potentials ${\gamma }_j$. Now it is clear how to train such a method: as a linear classifier over these features, having formed the «objects–features» matrix explicitly.

An idea arises at once: perhaps there is no need to compute closenesses to all the objects of the training sample, and it is enough to take a subset of prototypes and compute distances only to them? The sample may contain a million objects, and we will take, say, a hundred typical representatives in each class and cut the volume of stored data by a factor of 10,000. Why store all the objects if one can keep only those sufficient for reliable classification? We will now work this idea out and along the way get acquainted with an interesting theory.

Complete cross-validation and the compactness profile

This is an element of the combinatorial theory of generalization ability, which makes it possible to obtain criteria of the leave-one-out type, and even complete cross-validation, by an elegant, efficiently computable formula. There will even be one proved theorem here. For my course this is a little unusual; further on I will not refer much to generalization theory. But this insertion is in place here: it gives a logical transition to prototype selection methods — how to select from the training sample a small number of objects sufficient to classify all the others. For this we will need efficient formulas for computing cross-validation.

We take the original sample $X^L$ and split it in all possible ways into a training part $X^{\ell }$ and a control part $X^k$. Note: $k$ here is new notation, the length of the control sample, not the number of nearest neighbours. $C_L^{\ell }$ is the number of all ways of making such a split. On each split we compute the share of the objects of the control sample on which the algorithm trained on the training sample errs, and we average these error shares. Cross-validation in general is splitting the sample into train and test; when the splits are all possible ones, it is complete cross-validation. Computationally the thing is very inefficient, especially for large $k$: there may be astronomically many splits, and we will not compute this sum explicitly. For $k=1$ we get our old acquaintance: $\mathrm{CCV}(X^L)=\mathrm{LOO}(X^L)$, there are only $C_L^{L-1}=L$ splits, and the computation can be done directly.

The problem: obtain an efficiently computable formula for the complete cross-validation of the one nearest neighbour method and answer the question of whether the 1NN method can be improved by minimizing CCV. You will say: what can be changed in the one nearest neighbour method? To run ahead: the set of prototypes. One can throw out of the training sample the objects not needed for classification and keep the part that optimizes generalization ability in the sense of complete cross-validation. This is no longer quite lazy learning: training will consist in selecting the most important objects. But first we need a formula for CCV computed more efficiently than by full summation over partitions. Can we get away from summing over partitions? We can, and first we need a definition that formalizes that very compactness hypothesis.

In meaning, this is exactly the formalization of the compactness hypothesis: if the classes are compact clumps of points, then for each object most of its nearest neighbours lie in the same class, and $\Pi (m)$ is close to zero for small $m$.

I managed to obtain this result when I was working on generalization theory for my doctoral dissertation. It is interesting not only because it formalizes the notion of compactness explicitly, as the compactness profile of the sample, but also because it gives a method of prototype selection.

The proof

The proof is not difficult, rather beautiful, and shows how theorems about generalization ability — about how a method trained on some data will work on new data — can be proved by combinatorial methods at all. Under a finite sample such a prediction can be made.

The reasoning is fairly simple, but it relies essentially on this being the method of one, the first, nearest neighbour. A similar theorem can be proved for $k$ nearest neighbours: technically a little more complicated, but in essence the same combinatorics. However, combinatorial bounds on generalization ability can be obtained for few machine learning methods: it is rather the exception.

Properties of the compactness profile and the CCV estimate

Let us denote the combinatorial factor

• $R(m)\to 0$ faster than a geometric progression:
  $$\frac{R(m+1)}{R(m)}=1-\frac{\ell -1}{L-1-m}<\frac{k}{L-1}.$$
  So in the compactness profile only $\Pi (m)$ at small $m$ matter for the estimate.
• A formalization of the compactness hypothesis: the more often close objects lie in the same class, the smaller CCV.
• For small $k$:
  $$\begin{array}{rl}k=1& :\mathrm{CCV}=\Pi (1)=\mathrm{LOO};\\ k=2& :\mathrm{CCV}=\Pi (1)\frac{\ell }{\ell +1}+\Pi (2)\frac{1}{\ell +1};\\ k=3& :\mathrm{CCV}=\Pi (1)\frac{\ell }{\ell +2}+\Pi (2)\frac{2\ell }{(\ell +1)(\ell +2)}+\Pi (3)\frac{2}{(\ell +1)(\ell +2)}.\end{array}$$
  At $k=2$, $k=3$, $\Pi (2)$, $\Pi (3)$ begin to be counted, but with very small weights, and the main contribution comes from $\Pi (1)$, that is, LOO.
• CCV depends weakly on the control length $k$.

Along the way we have justified — true, only for metric nearest neighbour methods — that leave-one-out can be used: this estimate is unbiased and depends little on the control length, which is also good news.

Prototype selection

What did we obtain all this for? To learn, in the nearest neighbour method, to get rid of the training sample: to throw out most of its objects so that what remains are prototypes, representatives of their classes, by which all the other objects can be classified successfully. In English this is prototype learning, and there are hundreds of prototype selection methods: simple and complex, heuristic, optimization-based and many others. One of them is based on bounds through the compactness profile. The definition will have to be modified by introducing a dependence of the profile on the set of prototypes $\Omega$; this is no more complicated than what we have already done.

It is proved in the same way, only the terms are grouped a little differently in the proof: the contribution of each object to CCV is singled out, if only the subset $\Omega$ is used as prototypes — the objects we allow to be nearest neighbours. Two fairly obvious greedy strategies arise.

In the first strategy we look at which object's removal from the set of prototypes changes complete cross-validation least, and successively throw out the most useless objects. In the second we go from the other end: take as a seed, for example, one random object of each class and ask which object it is most profitable to add so that CCV becomes minimal afterwards.

The topic of prototype selection arose somewhere in the sixties and was quite popular until the nineties; hundreds of methods have been invented, mostly heuristic. Why so? Prototype selection is a search for an optimal subset in a finite set of points, and that is an NP-hard problem: in general it requires going through an exponential number of subsets. All known algorithms revolve one way or another around how to cut the search time and find a more or less good set of prototypes. And our method, though it rests on a bound on generalization ability — an efficiently computable formula for complete cross-validation — at the moment of optimization solves an NP-hard problem by a heuristic algorithm, successive greedy removal or addition.

So today we generalized the nearest neighbour method and made it nontrivial in two directions. First: we began increasing the number of neighbours, voting, weighting the neighbours, and reached the method of potential functions, which turned out to be a kind of linear classifier with closenesses as features. Here the method remains lazy learning; training comes down to storing the sample. Second: we kept the one nearest neighbour method but threw the bulk of the unneeded objects out of the training sample and kept only the prototypes sufficient for good classification — we posed the optimization problem of keeping the minimum number of prototypes.

Nonparametric regression: kernel smoothing

Metric regression methods are also called nonparametric — such a random play on words. The simplest of them is kernel smoothing.

What is bad about this approach? That someone clever has to come and say what the model $f$ is up to its parameters. We do not know the parameter $\theta$ and train it, but $f$ itself — a linear dependence, a neural network, or God knows what else — has to be given by someone. And if there are no considerations about this function? The idea arises to do without it — hence the name «nonparametric methods».

Note a technical point: I inserted the weights $w_i$ of the objects of the training sample. In ordinary least squares they are absent, or rather they are ones. Now we will play on this: we will generalize least squares so as to build the dependence not on the whole sample but only on part of it. Let us move all the complexity of the problem from the choice of the family $f$ into the weights. As the model we take simply a constant, $f(x,\theta )=\theta$, a scalar parameter that we will find very quickly by least squares. And we make the weights depend on the very point $x$ at which we want to compute the recovered dependence.

Look what I did. The model does not depend on $x$ — a constant, a trivial solution. But we build this trivial solution in the neighbourhood of every point of the space, and that is the trick. The dependence on $x$ is put not into the model but into the weights of the objects of the training sample in the least squares criterion. We have turned the problem statement inside out: we simplified the form of the dependence to the limit and concentrated all the complexity in the choice of weights — as closeness functions, decreasing kernel functions of the distance. Here the window width $h$ also arises: we still have to learn to determine the radius of the neighbourhood of the point $x$ — where and how many objects lie on which we solve the least squares problem.

The least squares problem for a constant is solved analytically, in one's head: differentiate with respect to $\theta$, set the derivative to zero, and ${\sum }_i{w}_i(x)2(\theta -y_i)=0$ remains; move the sums over, take $\theta$ out of the sum — done. If there are no weights, the least squares solution for the constant model is the mean value of $y_i$ over the sample, and if there are, the weighted mean.

What we have obtained is called the kernel smoothing formula, or the Nadaraya–Watson formula. The weights depend on the metric, so this is a metric method of recovering a dependence. How to derive the formula is very simple. But why it will work, why it will be a good approximation, is no longer simple. Such theorems are proved in deep courses of mathematical statistics, and I will show one without proof, just so you understand what mathematics exists here.

Without a probabilistic assumption about how the sample was generated, we could prove nothing at all. The joint density of the x's and y's is a cloud of points: y depends on x somehow, with some noise. The mean $y$ at a given point $x$ is the expectation $\mathsf{E}(y\mid x)$, and we are not going to recover dependences that grow too fast, with vertical asymptotes — condition 3 formalizes this. The kernel decreases neither too fast nor too slowly. The window width should be neither too large nor too small: as the amount of training data grows, the window can be narrowed, but not too fast, otherwise no point will fall into the window. There are many requirements, but they are quite reasonable and interpreted more or less obviously. Then the Nadaraya–Watson formula converges pointwise to the conditional expectation of $y$ at the given point $x$.

Choosing the kernel and the window width

Now relatively simple questions: how to choose the kernel $K$ and the window width $h$.

The recommendations are these. One can take the Gaussian kernel: its branches go off to plus and minus infinity, and every point of the training sample is guaranteed to make some nonzero contribution — all the terms in both the numerator and the denominator will be nonzero. Or, even better, the quartic kernel, a piece of a fourth-degree polynomial: it is smooth. The approximating function inherits the smoothness of the kernel: if the kernel is smooth, the function obtained by the Nadaraya–Watson formula will be smooth too, and we like smooth functions. The rectangular kernel is not very good: the function comes out piecewise constant, with jumps, and in many problems that is inconvenient.

So:

• the kernel $K(r)$ strongly affects the smoothness of the function $a_h(x)$ and weakly affects the quality of the approximation;
• the window width $h$ strongly affects the quality of the approximation;
• a variable window width by the $k$ nearest neighbours:
  $$w_i(x)=K\left(\frac{\rho (x,x_i)}{h(x)}\right),h(x)=\rho (x,x^{(k+1)}),$$
  where $x^{(k)}$ is the $k$th neighbour of the object $x$;
• optimizing the window width — by cross-validation, exactly as for classification; one gets a plot with a characteristic minimum:
  $$\mathrm{LOO}(h,X^{\ell })=\sum _{i=1}^{\ell }(a_h(x_i;X^{\ell }\setminus \{x_i\})-y_i{)}^2\to \underset{h}{\min }.$$

The problem of outliers

One more point is how to work with large outliers; I will talk about this in detail in another lecture. If two points with values $+40$ and $-40$ are added to a sample of a hundred points — note the scale: that is somewhere a floor above and a floor below — the approximation jerks towards these outliers. This can be used to identify outliers and effectively remove them from the sample. There is an algorithm that literally in one or two iterations finds such points and throws them out, and the approximation at the places of the outliers returns to where it ought to be.

Summary

Metric methods are, one could say, the simplest thing in machine learning, but even in them there is something to train: the number of nearest neighbours, the window width, the weights of the objects; objects can be thrown out, keeping prototypes. What I did not talk about and will not talk about is distance learning: how to introduce parameters into the metric itself and optimize them. Such problems are, on the whole, easily solved by the stochastic gradient method. An important insight we will return to in the next lectures: metric methods of the potential function type are a variety of linear classifier, where the amplitudes of the potentials serve as the parameters. And an interesting point is how to reduce a problem without features to a problem with features: measure the distances to prototypes. All the objects of the training sample can be taken as prototypes, reference objects, but that is inefficient; a selection can be made.

Seminar