Distance and Similarity

Suppose we have given every word in a collection of texts a handful of coordinates, so that each word is a point rather than a number in a list. On its own that is a table, and a table makes no claim about anything. It becomes a claim only at the moment we say that two words near each other in it are alike, because near is not a property of the table, it is a property of the table together with some rule for turning two rows into one verdict.

So the interesting object is not really the positions. It is the rule, and the positions are worth exactly what the rule can read out of them. Two people can hold the same table, ask the same question of it, and get different answers, and neither of them has made a mistake, because they picked up different rules.

Everything else on this page is an elaboration of that sentence, and two whole sections of this site rest on it, since every method that learns positions for words, and every network that learns them for pictures, is judged by whether nearness in what it produced turns out to mean something. Nothing below is a fact about language.

The worked numbers use words because a table of them is small enough to check by hand, and the same six rules are asked of a picture in exactly the same way.

The collection this page works on is twenty-four short documents, twelve about cooking and twelve about sailing, and between them they use twenty-three distinct words. Ten of those belong to the cooking documents, ten to the sailing ones, and three of them, and, the and we, turn up in both. It is a small collection on purpose, small enough that every answer on this page can be traced to particular words.

From that collection a table is fitted by looking at which words stood within two positions of which others, scoring each pairing by how much more often it happened than chance would explain, and squeezing the result down so that each word ends up with four numbers. How that is done is a whole page of its own further along, and none of what follows depends on it. The word this page stands at is sail, whose four numbers come out at 0.5369, 0.5223, 0.2690 and −0.2075.

There are two ways of putting a verdict about two positions into a number, and they point in opposite directions. A distance answers with something that grows as the two things get less alike, is zero when there is nothing between them, and has no upper limit at all, since two positions can always be moved further apart. A similarity answers with something that grows as they get more alike, and the useful ones are bounded, so that the largest value means as alike as this measure can express.

The boundedness is the difference that matters in practice rather than the direction. Two words that come back 0.0175 apart under a rule whose gap cannot exceed 2 are plainly near the top of what that rule can say, and the same pair is 0.3046 apart under the straight line, which means nothing at all until we know what the typical gap in this table is.

So a similarity can be read on its own and a distance can only be read against other distances from the same table, which is why reported figures in this area are usually similarities.

Given a similarity with a known ceiling we can always make a distance out of it by subtracting, and the two then order every pair identically, because subtracting from a constant reverses an order and reverses nothing else. That is worth saying plainly, since it means a page reporting an angle and a page reporting one minus that angle are reporting the same ranking, and any argument between them is about presentation.

gap  =  ceiling  −  similarity

What the conversion does not give us is a distance in the full sense. A distance in that sense makes a promise about three words at once, that going from one to another by way of a third never comes to less than going straight there, and this page calls it the detour promise. Reversing an order preserves which pair is nearer; it does not preserve the arithmetic relations between the numbers, so a rule that fails to keep the detour promise fails it just as badly once it has been subtracted from a ceiling, which is the failure Part 5 measures on this collection.

Before reading rules off a fitted table, where nobody can check the arithmetic, it is worth building the crudest possible table by hand. Take two words from the collection, oven and wind, and give every other word two numbers, which are how often it stood within two positions of each. That is an embedding, in the sense that matters here, because it gives each word a position worked out from how the word was used.

Three words are enough. Counted across the twenty-four documents, bake stood beside oven five times and beside wind never, stir stood beside oven twice and beside wind never, and sail stood beside wind five times and beside oven never. So the three positions are (5, 0), (2, 0) and (0, 5), and every number the next six steps quote can be got with a pencil.

…

Two of the three lie along one axis and the third lies along the other. Watch the top row of the table, since bake and stir are the pair the six rules will most obviously disagree about.

The most obvious rule takes the two positions coordinate by coordinate, works out how far apart the two numbers are in each, and adds those up. The second most obvious squares each gap before adding and takes a square root at the end, which is the straight-line distance we would measure with a ruler if the coordinates were drawn on paper. They differ in how much a single large disagreement is allowed to matter, since squaring turns a gap of four into sixteen where a gap of two becomes four.

summed gaps    =  |a₁ − b₁| + |a₂ − b₂| + …

straight line  =  √( (a₁ − b₁)² + (a₂ − b₂)² + … )

bake to sail    summed gaps    =  |5 − 0| + |0 − 5|  =  10
                straight line  =  √( 5² + 5² )  =  √50  ≈  7.0711

bake to stir    summed gaps    =  |5 − 2| + |0 − 0|  =  3
                straight line  =  √( 3² + 0² )  =  3

On the fitted table the two rules almost never part company. Asked for the nearest word to each of the twenty-three, they give the same answer twenty-three times out of twenty-three, which is the agreement square in step 16. That is not a general truth about the two rules, and it is a good reason not to spend effort choosing between them here.

Pushing the squaring further, to cubes and fourth powers and beyond, concentrates more and more of the answer on whichever single coordinate disagrees most, and in the limit the rule reads that coordinate and discards the rest. A pair of words is then as far apart as their worst disagreement and no further, whatever happens in the other coordinates.

worst coordinate  =  max over i of  |aᵢ − bᵢ|

The fourth rule reads only which way a position points from the origin and ignores how far along that direction it lies. Two words whose positions lie on one ray through the origin are identical to it however different their lengths, and two words at right angles are as unlike as non-negative counts can be. It is computed as the dot product of the two positions divided by both their lengths, which gives a similarity, and the matching gap is one minus that.

similarity  =  (a · b) / (‖a‖ ‖b‖)

gap         =  1  −  similarity

cosine similarity = (5 × 2 + 0 × 0) / (5 × 2) = 1
cosine distance = 1 − 1 = 0

Because the answer never leaves a fixed range this is one of the two bounded rules. On counts, which cannot go below zero, the gap runs from 0 to 1, and on a fitted table whose coordinates may be negative it runs from 0 to 2, with 2 reached only by a pair pointing exactly opposite ways.

The fifth rule does no arithmetic on the values at all. It looks at each coordinate, asks whether the two numbers are the same number, and reports the share of coordinates on which they are not. Nothing about the size of a disagreement reaches it, which is exactly right when the numbers are codes standing for categories and there is no sense in which one code is further from another.

coordinates that differ  =  (how many i have aᵢ ≠ bᵢ) / (how many i there are)

Asked of a fitted table it produces something worth looking at rather than something useful. Standing at sail it reports the nearest word as flour at 0.5, and every other word in the collection at exactly 1.0, so twenty-one of the twenty-two candidates are tied for last and the winner won by a coincidence. Across all two hundred and fifty-three pairs of words only six share even one coordinate exactly, and the best of those, at two coordinates in common, is flour with sail, a cooking word and a sailing word, which the collection has arranged as mirror images of each other.

The sixth rule divides each coordinate’s gap by the total size of the two numbers it sits between, then adds those fractions up. Every coordinate then contributes somewhere between nothing and one, whatever units it happens to be in, so no single coordinate can take over an answer merely by holding larger numbers. The price is that it is most sensitive near zero, since a move from one to two costs the same third as a move from a thousandth to two thousandths.

gaps against their size  =  sum over i of  |aᵢ − bᵢ| / (|aᵢ| + |bᵢ|)

bake to stir = |5 − 2| / (|5| + |2|) + 0 = 3/7 ≈ 0.4286
bake to sail = |5 − 0| / 5 + |0 − 5| / 5 = 1 + 1 = 2

A coordinate where both words hold zero would be zero divided by zero, and it is treated as contributing nothing on the grounds that the two words agree there and agreement should not be charged for. That is a convention rather than a derivation, and it is the first of several on this page.

Put together, the six answers for one pair of hand-counted words show how little they have in common. bake and stir are 3 apart under three of the rules, exactly 0 apart under the angle, half a table apart under the one that reads coordinates as labels, and 0.4286 apart under the last of them, and every one of those numbers is right about something.

Read the first column against the second. Under the angle, bake and stir are as close as two words can be and sail is as far as a pair of counts can get. Under the summed gaps the first pair is 3 apart and the second 10, so the ordering agrees while the scale does not, and under the coordinates that differ the first pair scores half only because they happen to share a zero. There is no arrangement of these numbers under which one rule is a rescaling of another.

Here is the experiment that separates the rules into two groups. Leave the collection alone but count one word’s company twice over, as though the same documents had been gathered twice for that word and once for everybody else. Its position moves straight out along the direction it already pointed, and nothing about which words it stood beside has changed.

…

Drag the slider and watch the angle column and the one beside it stay where they are while the other four climb. The positions are the hand-counted three, so every number in the table can still be checked.

summed gaps               |10 − 2| + |0 − 0|         =  8
straight line             √( 8² + 0² )               =  8
worst coordinate          max( 8, 0 )                =  8
gaps against their size   8 ∕ (10 + 2) + 0           ≈  0.6667
angle                     1 − (10 × 2) ∕ (10 × 2)    =  0
coordinates that differ   1 of 2                     =  0.5

If the length of a position carries how much of the word we saw, and its direction carries how the word was used, then a rule that ignores length is asking about usage and a rule that reads it is asking about usage and volume together. That is the standard argument for comparing word positions by angle, and on this collection it is worth checking rather than repeating, because the two fits disagree about it.

…

The same twenty-three words under two ways of fitting. Look at the leftmost dots, which are the three words used most, and notice that they sit at the bottom of one panel and the top of the other.

On the counting fit the relationship between how often a word was used and how long its position came out is −0.6284, which is strong and runs the wrong way for the standard argument. The three commonest words, and, the and we at eight uses each, have three of the shortest positions, at 0.3708, 0.3667 and 0.5770, where deck at five uses reaches 1.1628. On the fit that learns by predicting neighbours, on the identical documents, the same relationship is +0.7005.

The two signs are both explicable and that is the point. A method that scores a pairing by how much it beats chance gives a word occurring everywhere a low score against everything, since it beats chance nowhere, and a method that nudges a position once per occurrence moves a common word further from where it started.

So the length of a position records something about the fitting procedure at least as much as something about the word, and the standard argument for the angle is an argument about one family of methods rather than about word positions in general.

There is a tidy consequence of all this. If every position is first scaled to length one, so that only direction is left, then the straight-line gap between two of them is a fixed function of the angle between them, falling as the similarity rises. Ranking by one is therefore ranking by the other, and the question of which rule to use goes away.

for ‖a‖ = ‖b‖ = 1:    ‖a − b‖  =  √( 2 − 2 (a · b) )

Checked on the twenty-three words, the identity holds to 6.1 × 10⁻¹⁶, and the order the angle gives from sail is the same order the straight line gives, word for word down the whole vocabulary. Neither of those orders is the one the straight line gives on the table before scaling, which is what step 15 shows.

With the hand-counted table behind us we can put the question to the fitted one. Standing at sail, which word is nearest? The playground at the top of the page answers it six times over, and the six answers are not one answer.

Three rules say mast and two say rope, and the two candidates swap places rather than one of them being far down the other list. The cause is visible in the lengths, since rope at 1.0713 is a good deal longer than sail at 0.8225 while mast at 0.8281 is almost exactly as long, so the ruler is charging rope for a length difference the angle refuses to look at.

Standing at oven instead, five rules of six agree on eggs, and the disagreement vanishes. That is the ordinary case, and it is worth knowing that the rules mostly agree before spending any time on where they do not.

One word is an anecdote. Asking every rule for the nearest word to every one of the twenty-three, and counting how often two rules gave the same answer, turns the question into a measurement.

…

Each cell counts the words on which the row rule and the column rule name the same nearest neighbour, out of twenty-three. The diagonal is twenty-three by construction.

The summed gaps and the straight line agree on all twenty-three; the worst coordinate agrees with them on twenty-one; the gaps read against their size agree on nineteen; the angle agrees on fifteen; and the rule reading coordinates as labels agrees with the straight line on two and with the angle on none at all. Fourteen of the twenty-three words get the same answer from all five rules that read the coordinates as quantities, which is a majority and not a consensus.

Not all eight of the words where the angle and the straight line part company are the same kind of case, and the panel in step 16 lists them. Six are the length effect from step 15 working on genuinely close pairs, where sail and rope or flour and whisk are near each other by both rules and the two swap two candidates over. The other two are among the function words, where and, the and we are all short and all close to each other, so the ranking between them is decided by very little.

The rule reading coordinates as labels is a different matter and its disagreements are not disagreements at all. Its answer for sail is flour, a word from the other topic, and its answer for oven is anchor, also from the other topic, and both come from the collection having been built so that each cooking word has a sailing counterpart in the same position of the cycle. That symmetry puts a handful of coordinates at exactly equal values across the two topics, and a rule that reads only equality finds nothing else to go on.

Asking which word is nearest to sail means reading every other position in the collection, because none of these rules gives any way of ruling a word out without computing its answer. On the twenty-three-word table that is twenty-two comparisons of four numbers each, which is eighty-eight multiplications and then a sort. It is nothing, and it grows as the product of the vocabulary and the number of coordinates.

…

One question against vocabularies of rising size, timed once on whichever machine is serving this page, so the milliseconds depend on that machine while the multiplications do not.

A vocabulary of fifty thousand words at three hundred coordinates costs fifteen million multiplications for one question, and two hundred thousand words costs sixty million. That is a real amount of arithmetic to pay for one answer, and it is paid every time somebody asks, since nothing was precomputed at fitting time that a question can reuse.

What saves this in practice is that the arithmetic is a shape a machine is extremely good at. Squaring out the straight-line gap turns the expensive part into a single multiplication of two blocks of numbers, and comparing by angle after scaling every position to length one is the same multiplication with the lengths already divided out.

‖a − b‖²  =  ‖a‖²  −  2 (a · b)  +  ‖b‖²

The two squared-length terms are one pass over each side, and the middle term for every pair at once is one block multiplication, which is the operation numerical libraries have spent decades making fast. So the count of multiplications is unchanged and the time is not, and asking a hundred questions costs far less than a hundred times one question.

The identity in step 19 recovers a small number by subtracting large nearly equal ones, and that is the classic way to lose it. Word positions sit near the origin, so nothing goes wrong on the table as fitted. It goes wrong when the positions have been moved, which is not a strange thing to have happened, since adding a constant offset to every coordinate is something a preprocessing step can do without meaning anything by it.

…

The gap between sail and mast, which is 0.2750, measured three ways with the same amount added to every coordinate of both. Read the middle column downwards.

Moving both positions out by a hundred million leaves the true gap at 0.2750 and makes the shortcut answer 2.8284, which is ten times too large and so has stopped being a degraded reading of the right quantity. At a million out the shortcut is still giving 0.2742, wrong in the fourth digit, and a nearest-word list built from readings like that would reorder quietly and raise nothing.

The repair is to subtract a common point from both positions before applying the identity, which leaves every gap unchanged because shifting everything equally moves no pair relative to another, and makes the squared lengths numbers of the size of the spread rather than of the offset. The third column is that, and it agrees with the direct subtraction at every distance out. On two thousand four hundred ordinary pairs the two agree to within four parts in ten thousand million million of the answer.

a hundred million out    squared lengths  ≈ 4 × 10¹⁶     step between machine numbers  8
                         returned  8                     √8  ≈  2.8284

a million out            squared lengths  ≈ 4 × 10¹²     step between machine numbers  ≈ 0.0005
                         returned  0.0752                √0.0752  ≈  0.2742

Reading every position for every question looks like something that ought to be avoidable, and for some rules it is, because they promise that a detour is never shorter than the direct route. That promise is what lets a search discard a whole group of words at once, since if a group’s representative is far from the question then everything grouped with it is far too. The rule that compares by angle does not make the promise, and on this collection it breaks it often.

…

Every ordered triple of distinct words, checked under every rule. Only one rule has any red in it.

Of the ten thousand six hundred and twenty-six triples, fifteen hundred and forty have a shorter detour under the angle, and the worst of them is a long way from marginal. From harbour to crew reads 1.1066 directly, and going by way of mast costs 0.4469 and then 0.2313, which is 0.6782, a saving of 0.4284. The other five rules have not one violation between them.

direct              harbour → crew           1.1066
by way of mast      harbour → mast → crew    0.4469 + 0.2313  =  0.6782
saved by the detour                          1.1066 − 0.6782  =  0.4284

Everything so far has been a comparison between rules, and it is worth being clear that no amount of further data settles which one to take. A collection of documents fixes the positions, and having fixed them it has said everything it can say. Which of the six readings of those positions is the right one is a question about what we meant by alike, and the documents were never asked.

That is not a counsel of despair, because the choice can be argued from properties rather than guessed. If a word’s volume in the collection should not affect who its neighbours are, that argues for the angle and rules out four of the others, and step 12 makes the argument checkable. If some coordinate is a category code, that argues for the rule that reads equality and rules out the rest.

What cannot happen is for the choice to be made by fitting, since every one of the six will fit any table at all.

The origin is where the difference between the rules stops being a preference and becomes a question of whether there is an answer. A position at the origin has a perfectly ordinary straight-line gap to everything, equal to the other word’s own length, because a straight line needs no division and the origin is a point like any other. It has no angle to anything, because the cosine divides by both lengths and one of them is zero, so the quotient does not exist.

…

Seven inputs, what the mathematics leaves undefined about each and what came back. Two of the seven have no answer at all, and two more have an answer only because somebody chose one.

Where a quantity does not exist there are three things an implementation can do, and each costs something. It can refuse, which is honest and forces a caller to decide; it can return a convention, which keeps a calculation running and puts a number that was never measured into a list that will be sorted; or it can return something not a number, which propagates and makes every later comparison false.

The middle one is the usual choice for a zero position under the angle, where the convention is that it sits at a right angle to everything, and it is defensible, though the number it puts into a list that will be sorted was never measured from anything.

Distance discriminates less as coordinates are added, and this is a property of distance rather than of any table. With more coordinates each pair of positions accumulates more small differences, those differences average out, and the nearest and the farthest positions to a given point draw together until the word we call nearest is barely nearer than the rest.

…

How much further the farthest word is than the nearest, at four widths, for the fitted table and for a table of the same shape whose numbers were drawn independently.

On the fitted table the figure falls from 39.42 at two coordinates to 7.02 at four, 3.51 at eight and 0.63 at sixteen, so at the widest the farthest word is only about six tenths further off than the nearest one. The usual demonstration of this uses positions drawn independently, and the grey bars are that, and up to eight coordinates the fitted table holds up substantially better, at 3.51 against 1.04.

At sixteen the advantage reverses and the fitted table reads 0.63 against 0.70, which is a real crossing rather than noise in one seed and is reported here because the tidier claim would have been that structure always helps.

The last limit is the one the rest of this topic inherits and cannot fix. Every rule on this page answers with one number, and one number cannot carry a respect. Two words come back alike, and nothing in the answer says whether they are alike in subject, in grammatical role, in register, in how often they were used, or in having been mangled by the same quirk of the collection.

A consequence shows up in the answers themselves. The measure is symmetric to the last bit, so reading a pair one way round and the other gives figures 0.0 apart, and yet the relation built out of it is not. Five of the twenty-three words have a nearest word that does not name them back, and mast is the clearest of them, since its nearest is sail while sail’s nearest is rope.

…

The words whose nearest neighbour has a different nearest neighbour of its own. The measure reads the same in both directions, and yet which word comes first does not.

This is the shape of the objection raised against similarity-as-distance long before any of these tables existed, that people judge a small thing to be like a large one more readily than the reverse, and that the judgement can break the detour rule as well. What the arithmetic here shows is a mild version of the same thing arising from a perfectly symmetric measure, purely because being the nearest is a comparison against a field of candidates and the field changes with the word.