Converting between cosine similarity and concentration ratio

Posted on by John

I’ve written three posts on cosine similarity lately. The first looked at interpreting cosine similarity. The second looked at an approximation related to the first. The third looked at how ranking according to cosine similarity works better than cosine similarity itself.

Normalized word vectors are points on a high dimensional sphere, and geometry in high dimensions is counterintuitive. See the first post in this series for an explanation.

The set of points within a given angular distance of a point on a hypersphere is called a spherical cap. The ratio of the area of this spherical cap to that of the whole sphere is called cap fraction or concentration ratio. Concentration ratio explains why a modest cosine similarity value corresponds to a tiny portion of the area of the sphere and should be interpreted as a close match.

For this post, I wanted to share a plot of concentration ratio as a function of cosine similarity.

This shows that moderate values of cosine similarity correspond to infinitesimal concentration ratios. And yet, as the third post linked at the top showed, word vectors are very unevenly distributed, and even extremely small regions of the sphere can contain multiple word vectors.

I only included cosine similarity values up to 0.8 because the function plotted above takes a nosedive for larger values, even on a logarithmic scale.

Here’s the Python code to make the plot, using the function cap_fraction from here.

s = np.linspace(0, 0.8, 500)
plt.plot(s, cap_fraction(np.acos(s), 200))
plt.yscale("log")
plt.xlabel("cosine similarity")
plt.ylabel("concentration ratio")
plt.show()

Coffee + milk ≠ latte

Posted on by John

Yesterday I wrote about the canonical example of how vector embeddings of words add:

“king” − “man” + “woman” ≈ “queen”

This should be interpreted as saying that the word vector for king, minus the word vector for man, plus the word vector for woman, is in some sense close to the word vector for queen.

This post will look at another example. Is the expression

“coffee” + “milk” ≈ “latte”

true in some sense?

Notation

In this post I will use “foo” to mean the vector embedding of the word foo.

Coffee + milk

The cosine similarity between “coffee” + “milk” and “latte” is about 0.63. And for reasons given in the previous post, this is a large value of cosine similarity. But there are 11 words that are more similar to “milk” + “coffee” than “latte”. Here are the top 12 matches in order.

  1. coffee
  2. milk
  3. tea
  4. drink
  5. chocolate
  6. cream
  7. breakfast
  8. ice
  9. beer
  10. vanilla
  11. starbucks
  12. latte

There are two questions to resolve. First, why isn’t latte one of the closest words? Second, why is the cosine similarity large even though latte is not one of the best matches?

Concept arithmetic

When word vector arithmetic works, as in the king and queen example, the vectors combine concepts. If you replace the male gender component of king with a female component, you get a vector close to the vector for queen.

But when you add the vectors for milk and coffee, you’re not adding concepts, you’re adding ingredients.

The concepts of milk and coffee are similar in that they’re both common beverages, as are tea and even beer. A latte is a beverage, but it’s not as common as milk, coffee, tea, or beer.

Extremely uneven distribution

If you divide word vectors by their norm, you get a point on a high-dimensional sphere. In the case of the glove-twitter-200 vector embedding, you get a point on a sphere in 200 dimensions. As explained in the earlier post, a fairly large cosine similarity corresponds to a tiny portion of the sphere’s surface area.

In the example of “king” − “man” + “woman”, the vector “queen” is the closest match (except for “king” itself).

But there are a lot of words whose vectors are within a tiny region around “coffee” + “milk”. And by tiny, I mean a region that accounts for a proportion of the sphere on the order of 10−23.

The glove-twitter-200 vector list contains vectors for 1.2 million words. If these vectors were roughly evenly distributed on the sphere when normalized, you’d expect each patch representing 10−6 of the sphere to contain about a word or two. You wouldn’t expect a patch taking up 10−12 of the sphere to contain more than one word, and you certainly wouldn’t expect a patch taking up 10−23 of the sphere to contain 12 words.

Rank order

Rank order based on cosine similarity is more robust than cosine similarity itself. This is an example of a phenomenon that occurs regularly: a metric whose values are dubious might still rank things well. Naive Bayes is another example. It naively computes probabilities in a way that is blatantly wrong, and yet ranking things by these spurious probabilities works well in some cases.

The cosine similarity between “king” − “man” + “woman” and “queen” is roughly the same as the cosine similarity between “coffee” + “milk” and “latte.” But in the former example, rank order picks out queen as the best match; rank order works like you’d expect, because you’re working with attributes that can be decomposed.

Dog + infant = puppy?

I wouldn’t be surprised if the Anglo-Saxon word for puppy was something like dogchild. The language was full of colorful compound words, such as hronrad (“whale-road”) for the sea and nosethyrl (“nose-hole”) for nostril.

Here are the top ten matches for “dog” + “infant” along with their cosine similarities.

  1. dog, 0.819
  2. infant, 0.809
  3. toddler, 0.734
  4. dogs, 0.697
  5. puppy, 0.688
  6. cat, 0.682
  7. pet, 0.676
  8. child, 0.671
  9. newborn, 0.670
  10. baby, 0.650

This shows that “puppy” is close to “dog” + “infant”, both in terms of cosine similarity and rank order, though it’s not the closet.

This also shows that you have to take the addition of word vectors with a grain of salt. It’s no surprise that puppy was a good match, but it’s surprising that cat is nearly as good.

Fibonacci product

Posted on by John

The product of four consecutive Fibonacci numbers equals the product of two consecutive integers.

For example,

3 × 5 × 8 × 13 = 39 × 40.

I ran across this theorem in a note [1] that says “The product of any four consecutive Fibonacci numbers is twice a triangular number.” Since triangular numbers have the form n(n + 1)/2, twice a triangular number is the product of two consecutive integers.

The note also gives a way to find the numbers on the right hand side. We have

Fn Fn+1 Fn+2 Fn+3 = m(m + 1)

where m equals

Fn+1 Fn+2

if n is odd and

Fn Fn+3

if n is even.

In the example at the top, 3 is the 4th Fibonacci number, so n = 4. Since 4 is even, m is the product of the 4th and 7th Fibonacci numbers, i.e. m = 3 × 13 = 39.

More Fibonacci posts

[1] K. B. Subramaniam. On a link between Triangular and Fibonacci numbers. The Mathematical Gazette, Vol. 103, No. 558 (November 2019), p. 489.

Simple approximation for spherical cap area

Posted on by John

The previous post looked at how to interpret cosine similarity, or equivalently angles between word vectors. In a high-dimensional space, randomly chosen vectors are likely nearly perpendicular, and so relatively large angles, such as 50°, indicate very closely related words.

Another way to look at this, as explained in the previous post, is that in high dimensions, a spherical cap of angular radius θ represents a small portion of a sphere, even for moderately large θ.

The proportion of the area inside the spherical cap, given here, involves the “regularized incomplete beta function” and so it’s hard to have an intuition for the value.

For large dimension n, the approximation

n−1/2 sinn − 1(θ)

gives the proportion of the area inside the cap to within an order of magnitude. It’s easy to see that this function goes to zero quickly as n increases, provided |θ| < π/2.

If you have the cosine similarity c = cos θ rather than θ itself, the approximation becomes

n−1/2 (1 − c²)(n − 1)/2.

Python script

Let’s try it on the example from the previous post, in which n = 200 and θ = 49°.

import numpy as np
from scipy.special import betainc

# Fraction of S^{n-1} inside a spherical cap of angular radius theta
# theta is measured from the pole
# Assume 0 < theta < pi/2

def cap_fraction(theta, n):
    x = np.sin(theta) ** 2
    return 0.5 * betainc(0.5 * (n - 1), 0.5, x)

def cap_fraction_approx(theta, n):
    return n**(-0.5) * np.sin(theta)**(n-1)

theta = np.deg2rad(49)
print(cap_fraction(theta, 200)) 
print(cap_fraction_approx(theta, 200))

This prints 2.03e-26 and 3.37e-26. The order of magnitude is correct as advertised.

What counts as a large cosine similarity?

Posted on by John

Machine learning represents words as vectors and measures the similarity of words by the angles between the vectors.

For vectors x and y,

\mathbf{x} \cdot \mathbf{y} = ||\mathbf{x} || \,||\mathbf{y} || \, \cos(\theta)

where θ is the angle between the vectors, and so

\cos(\theta) = \frac{\mathbf{x} \cdot \mathbf{y}}{ ||\mathbf{x} || \,||\mathbf{y} || }

This is the cosine similarity between the words represented by x and y.

Small angles have large cosines, and so words with larger cosine similarities are closer together than words with smaller cosine similarities. The cosine similarity between a word and itself equals 1, and we’d expect unrelated words to have a cosine similarity near 0.

You can do a sort of arithmetic with vector embeddings of words. The canonical example is that

“king” − “man” + “woman” ≈ “queen”

Implicit in this equation is that we’re really adding vector representations of the words. Let a, b, c, and d be the vector embeddings of the words king, man, woman, and queen. What we’re really asserting is that

a − b + c ≈ d,

except that’s not true! Or at least it’s not true unless you view it in the right context.

The angle between a − b + c and d is about 49°, which corresponds to a cosine similarity of 0.656. Here I’m using the gensim glove-twitter-200 embedding that represents words as 200-dimensional vectors.

The way to interpret the equation above is not that a 49° degree angle is approximately 0, or that a similarity of 0.656 is approximately 1.

In high dimensions, such as 200-dimensional word embeddings, nearly all vectors are nearly perpendicular. I wrote a post about this here. So the angle between randomly selected words will usually be close to 90°, and so in that context an angle of 49° is relatively small. For example, the angle between the vector representations of king and fireplace is 89.25°.

If you divide word vectors by their norm, you can think of each vector as a point on a high-dimensional sphere, in our case a sphere in 200 dimensions. The proportion of vectors within 49° of a given point is surprisingly small in high dimensions.

Let’s say our point of interest is the north pole of an n-dimensional sphere. We’d like to calculate the proportion of the area of the sphere that is within an angle θ of the pole. I go through the calculations here. (Update: I give an approximation here that’s easier to work with than the exact formula.)

When n = 3, 17% of the area is with 49 degrees of the pole. But when n = 200, the proportion is on the order of 10−26, essentially zero.

The vector d above representing queen is within a relatively tiny region around the vector a − b + c.

In terms of cosine similarity, 0.656 is a large similarity. Words with a cosine similarity in this range are quite close, even though we wouldn’t normally think of 0.656 being close to 1. In this context, 0.656 is close to 1.

Related posts

Guessing the meaning of a number

Posted on by John

Suppose I give you an n-digit number and ask you what it represents. This seems impossible, and in theory it is impossible. But in practice it’s often possible.

Apps on a phone may automatically interpret a 10-digit number as a phone number or a 16-digit number as a package tracking number. And very often these interpretations are correct, given the kinds of things most people use their phones for.

It’s not surprising that a 10-digit number on a phone is a phone number. It’s more interesting that a 16-digit number is likely a tracking number. It could be other things, such as a credit card number. But people don’t usually write out credit card numbers in a text note; credit card numbers likely saved in some more opaque way.

I run into a variation of this problem routinely, trying to infer what a number represents inside medical notes.

A five-digit number could be a US postal code, or it could be a medical procedure code.

A six-digit number could be a date in MMDDYY format, or it could be a medical record number.

A ten-digit number could be a phone number, or it could be an NPI (National Provider Identifier) number.

It’s interesting that it’s possible make a good guess at what a number means inside unstructured text. Context has been lost, but not all context: you know you’re looking at medical notes. And that meager bit of context can be surprisingly useful.

Bayesian OCR

Posted on by John

The Greek letter β (beta) and the German letter ß (eszett) look similar, especially in some fonts.

Now suppose an OCR program sees some character that could be a beta or could be an eszett. It could calculate some kind of distance between between the pixel pattern of the character and the pixel patterns of beta and eszett. But that would be discarding context.

If you’re scanning a Greek document and run into a beta-like symbol, it’s very likely a beta. If you’re scanning a German document and run into a beta-like symbol, it could be a beta. For example, it could be a scientific paper that mentions beta particles or beta carotene. But most likely the symbol is an eszett.

The previous paragraph is saying you should compute the conditional probability of a set of pixels representing a character given the language of the document. You could be more sophisticated and look at the position of the symbol in a word as well. For example, if you see a symbol at the end of a Greek word that could either be ο (omicron) or σ (sigma), it’s likely an omicron because Greek has a different symbol ς for final sigma.

This post is a follow-on to my earlier post on the error rate in Google’s Ngram database. OCR errors are fairly common in that database, so why don’t they “just” fix the errors by using some sort of Bayesian method? OCR software probably does use some sort of Bayesian method, but it’s not that simple.

In that post I looked at the use of the word grok in English. The Ngram database shows the word being used before it was coined in 1961 due to OCR errors. Why didn’t Google compute the probability of a word being “grok” conditional on the publication date? That would be circular. We happen to know exactly when grok was coined, but in general we might try to determine when a word was coined by looking at a large set of scanned books, like the Ngram database!

Now we could compute the probable value of an ambiguously scanned word by conditioning on the language of the surrounding text. That would be a reasonable thing to do in general, but it could also lead to exactly the kind of errors we see in the Ngram data for grok.

Suppose you see an ambiguously scanned word in a book written in English. There is a higher prior probability that the word is an English word than a German word. Now suppose you see “gro?” where ? could be β, ß, or k. Without any context, perhaps the probability of the symbol being a k is small. But grok is an English word and groß is a German word which may lead you to conclude “?” is a k and the ambiguous word is grok.

Assigning higher prior probability to English words in English texts is the best thing to do on average, but in particular instances it will lead to errors. That’s life.

The Ngram database includes millions of scanned books. Google had to use OCR algorithms that work well on average. A linguist with a special interest in a particular word can be more careful and create a more sophisticated probability model (explicit or implicit) customized for their interests. Google did what they could operating at such a large scale.

Related posts

A 50-year-old computer-assisted proof

Posted on by John

The idea of using computers to assist with proofs is not new. The first major computer-assisted proof was published in 1976, the proof of the four color theorem by Kenneth Appel and Wolfgang Haken. The authors reduced the proof of the four color theorem to verifying calculations on 1,834 configurations, each checked by a computer program.

The proof was simplified over the years, and formalized in Coq in 2005. Everyone is satisfied that the theorem is true, but there has never been a satisfying proof, one that a human could read and say “I see now why any map can be colored using only four colors.” And there may never be one, but see this post for a contrary prediction.

The IBM mainframe that ran the calculations completing the proof of the four color theorem did not generate the proof. It simply executed the FORTRAN program that Haken and Appel (and Koch [1]) gave it.

I don’t see the recent proof of finite-time blowup for solutions to the Navier-Stokes equations as entirely different. Computers did higher-level tasks for the OpenAI team than the mainframe did for Haken and Appel, and these tasks were not as directly programmed as the tasks that were given to the mainframe, but still machines do what they are told to do.

Related posts

[1] John A. Koch was a programmer who worked on the four color proof with Haken and Appel. I don’t know how much credit he deserves, but I suspect it may be more than he was given.

AI is an intelligence multiplier

Posted on by John

A rising tide may lift all boats, but the AI tide lifts some boats much more than others.

By all accounts, the best programmers have had the biggest productivity boost from AI. And top tier mathematicians are using AI to settle long-standing mathematical conjectures. AI is a powerful tool, but tools don’t come to life and make things on their own.

I routinely have naive amateurs [1] send me proofs of open conjectures, and naturally more recent such proofs involve AI. I’ll get an email saying something like “I’ve solved the Collatz conjecture using ChatGPT, but I’m not a mathematician so I need some help verifying the proof.” And of course the supposed proof is rubbish.

The recent Navier-Stokes proof is impressive, but AI didn’t initiate the proof any more than LaTeX did. Nor did a child steer AI into proving the conjecture. Professional mathematicians were able to use AI to pursue their ideas at superhuman speed. But someone without an understanding of the Navier-Stokes problem, and familiarity with recent ideas for approaching the problem, could not have directed AI to produce a proof.

Computer scientists have been saying “garbage in, garbage out” from the beginning. A variation on this aphorism for the age of AI would be “mediocrity in, mediocrity out.”

***

[1] Amateurs can and do make contributions to mathematics. For example, in 2022 David Smith, a retired print technician, discovered a single shape that can be used to create an aperiodic tiling of the plane. By “naive amateurs” I mean people who literally do not know what they are talking about.

Posted in AI

The part of Navier-Stokes no one is talking about

Posted on by John

Yesterday OpenAI announced a proof that settled a long-standing question about the Navier-Stokes equations from fluid dynamics. The announcement has created a lot of buzz, as one would expect. But there’s an aspect of OpenAI’s work that I haven’t seen anyone talk about: they posted a Lean 4 formal proof at the same time as their conventional human-readable proof.

Quite a few other mathematical conjectures have been settled recently using AI, and these have also been accompanied with formal proofs, using Lean 4 in particular.

Until very recently, generating machine-verifiable formal proofs has been excruciatingly tedious. In 2005, Henk Barendregt and Freek Wiedijk wrote

To give an indication of how much work is needed for formalisation, we estimate that it takes approximately one work-week (five work-days of eight work-hours) to formalise one page from an undergraduate mathematics textbook.

That was the rule of thumb: forty hours per page. And this in the context of undergraduate textbooks. Research publications are much denser than textbooks. Furthermore, page 100 of a textbook probably depends mostly on material on pages 1 through 99. A sentence in a research article could cite anything that has been published before.

Say a research article takes 20 times more effort to formalize than page in an undergraduate textbook. Then formalizing the 166-page paper from OpenAI would take 132,800 person-hours. It took OpenAI 17 hours to verify their proof in Lean. I hesitate to use the word “revolutionary,” but lowering the cost of anything by four orders of magnitude is revolutionary.

I’ve used AI to generate formal proofs to check my work just for a little blog post. I wouldn’t dream of doing that if I had to pay someone a week’s salary to check my work.

Formal verification doesn’t just apply to mathematics. You could, for example, formally verify that a set of security policies are consistent and that, given certain assumptions, they accomplish their purpose. You could formally verify that a smart contract imposes a certain maximum liability. You could verify the correctness of mission-critical algorithms. These problems are easier than formalizing mathematics research, and it is easier to quantify the return on investment.

Related posts