We’re all aware of what ‘distance’ means in real-life scenarios, and how our notion

of what ‘distance’ means can change with context. If we’re talking about the distance

from the ODG office to one of our favorite lunch spots, we probably mean the distance

we walk when traversing Chicago’s grid of city blocks from the office to the restaurant,

not the ‘direct line’ distance on the Earth’s surface. Similarly, if we’re talking

about the distance from Chicago to St. Louis, the distance we’re talking about probably

depends on whether we’re driving (taking the shortest path via available roads) or flying

(which is usually much closer to the ‘straight line’ path on the Earth’s surface

than driving is). In this post, we explore a more rigorous construction of distance

and its applications to data science.

## What is a metric?

Most people have also encountered distances in their math classes – things like

computing the distance between two points in the Cartesian plane with the familiar

formula $$sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$$.

As mathematicians love to do, we can attempt to broadly generalize what we mean

by ‘distance’ while still retaining the key properties that make such a measurement

useful. Really, what ‘distances’ are doing in most scenarios is giving some

quantitative indication of how ‘close’ two things are, where what we mean by

‘close’ depends on the situation. For a slightly less obvious example of distances,

we can talk about distances between people in a social network. We can define a

distance as follows: everyone I have personally met has distance 1 from me,

everyone that one of my acquaintances has met that I haven’t has distance 2 from

me, and so on. Then the ‘distance’ between two people in this scenario – the

shortest path of acquaintances connecting them – can be thought of as a measurement

of how similar their social networks are. This is a special case of something

called a ‘graph distance’, and people study distances like this on sites like

Facebook all the time.

As mentioned above, mathematicians have singled out a few properties that give a

useful and meaningful notion of distance. Given a function $$d(x,y)$$, what

properties would we like it to satisfy in order to be called a distance?

First, we want the distance from something to itself to be $$0$$, and the distance

from something to a different something to be strictly larger than $$0$$. Said

differently, we want our distance function to be able to detect equality:

$$d(x,y)=0$$ should imply that $$x=y$$.

Secondly, we want the distance between $$x$$ and $$y$$ to not depend on the order:

$$d(x,y)$$ should equal $$d(y,x)$$. Note that this can actually fail in some real

life examples (for instance, one way streets might mean this is false for the

driving distance between two places), but it is desirable for theoretical

applications.

Finally, we don’t want there to be ‘shortcuts’: the distance from $$x$$ to $$y$$

should truly be the shortest distance from $x$ to $$y$$ – I can’t get a shorter

distance by first going to some intermediate $$z$$. Mathematically, we can write

this as $$d(x,y) leq d(x,z)+d(z,y)$$ for all $$z$$. This is known as the triangle

inequality.

Any function satisfying these 3 properties is called a *metric* and can be used

as a meaningful notion of distance.

### Metrics and Data Science

This is all well and good, but why should a data scientist care about metrics?

The answer is that distance computations are at the heart of a number of common

important algorithms from machine learning, and understanding what’s going on

behind the scenes can lead to better insights and increased accuracy.

Broadly speaking, when we’re attacking (for instance) a classification problem,

the heart of what we’re actually trying to do is to find a way to compare a new,

unclassified data point to previously seen data points. We then use that

additional information to try and classify our new point in a way that attempts

to be as consistent as possible with the known data. In order to do this, we

need some sort of additional numerical information about comparisons between

data points. Metrics are exactly the tool that allow us to translate notions of

‘similarity’ into a useable mathematical form.

Let’s quickly run through some specific examples.

- K-Nearest Neighbors: This is probably the simplest and most well-known of all metric-based ML algorithms. The idea is clear – given a new data point, we want to classify it based on the closest nearby known data points. What we mean by ‘closest’ obviously depends on the choice of a metric. There is a lot of work that has been done on choosing the best metric for a given problem – more on that later.
- Support Vector Machines – This algorithm attempts to find a maximally separating hyperplane between classes. Again, ‘maximally separating’ here depends on the choice of a metric. With techniques like kernelization, you are implicitly working with the points in some higher dimensional space (along with its Euclidean metric!).
- Clustering – Many clustering objective functions come from trying to minimize the sum of distances between cluster centers and points in the cluster in various metrics. The clusters you get will depend on the choice of metric. Common choices are the standard Euclidean distance and the ‘taxicab’ or $$ell_1$$ distance – named because it works like distances in a city with a grid layout like Chicago (it’s also commonly called the Manhattan distance for the same reason).

### Choosing the Right Metric for the Job

So now we’ve established that metrics appear quite often and that the choice of

metric can affect the efficacy of a model. The obvious question is then: how do

I choose the right metric for the job?

One potential direction this question might lead is dimensionality reduction. If

my data lies in some very high dimensional space, doing computations like finding

the nearest neighbor to a given data point can be quite computationally expensive.

The idea of dimensionality reduction is to (hopefully!) drastically lower the

number of necessary dimensions in order to speed this process up. But this is

useless unless there’s some guarantee that pairwise distances don’t become too

distorted – otherwise I’m no longer able to compute the correct nearest neighbor.

The Johnson-Lindenstrauss lemma is an example of the kind of theorem that one

might hope to prove in the direction of showing that such a process is possible.

At a high level, it says that if I take random projections of my data to roughly

(log of the number of data points) dimensions, distances are preserved (modulo

some factors) with high probability. So most of the time, just taking random

projections allows me to severely reduce the dimensionality of my data without

losing too much information about the pairwise distances!

But perhaps I want to leave my data unchanged and just change the metric on the

ambient space to better serve my classification task. This is broadly the subject

of a field called ‘metric learning’. The general goal is often to learn a special

kind of metric called a Mahalanobis distance – one of the form

$$d(x,y) = sqrt{(x-y)^top M (x-y)}$$ where $$M$$ is a positive semidefinite matrix –

that improves the classification results of algorithms like K-Nearest Neighbors.

The idea is often to translate the condition ‘points of the same class are close,

whereas points of different classes are far apart’ into an optimization problem,

and then optimize!

This is just scratching the surface of the ways metrics are studied and applied

to machine learning and data science problems. I learned a lot about

Johnson-Lindenstrauss and high dimensional geometry in data science from Blum,

Hopcroft and Kannan’s book Foundations of Data Science

(which is free online!). For metric learning, Kulis’ Metric Learning: A Survey is a nice introduction.