Nathaniel Bowditch

Posted on by John

A couple days ago a friend told me about the book Carry On, Mr. Bowditch, a fictional account of the life of Nathaniel Bowditch (1773–1838). I’ve been listening to the book on Audible, and apparently it’s only lightly fictionalized.

Bowditch was a self-educated mathematician and astronomer, best known for his book The American Practical Navigator, first published in 1801. The book has been continually revised over the last two centuries and is still in print, available for download from the National Geospatial-Intelligence Agency. The latest edition begins with a brief account of Bowditch’s life, confirming the essential details of the fictional biography.

Two things stand out about Bowditch: his attention to detail and his desire to make ideas accessible. He taught himself Latin in order to read Newton’s Principia and followed the text so closely that he found a number of errors.

Bowditch’s navigation book grew out of the numerous corrections he made to error he found in John Hamilton Moore’s The Practical Navigator, the leading navigation text of the time.

At the beginning of the 19th century it was theoretically possible to determine time, and hence longitude, from lunar observation. However, the method required ideal observation conditions and laborious calculation. Bowditch developed a way to make the necessary measurements under more general conditions, and simplified the necessary calculations. According to the biographical preface mentioned above,

Bowditch vowed while writing this edition [of his navigation text] to “put down in the book nothing I can’t teach the crew,” and it is said that every member of his crew including the cook could take a lunar observation and plot the ship’s position.

After completing The American Practical Navigator, Bowditch began an English translation of Pierre Laplace’s encyclopedic Mecanique Celeste, filling in details to make the work accessible to a wider audience. He was able to translate four out of the five volumes by the end of his life.

Related posts

Haversine law

Posted on by John

Suppose you want to solve a triangle. You know two sides and the angle between them. Then you can solve for the third side using the law of cosines.

Now suppose you want to solve a big triangle, a triangle on the surface of the earth so large that the curvature of the earth matters. You can still use the law of cosines, but you’ll need the spherical law of cosines:

cos(c) = cos(a) cos(b) + sin(a) sin(b) cos(C).

If you know the (angular) lengths of sides a and b, and (tangential) angle C between the two sides, you can solve for c by taking the inverse cosine of the right hand side above.

Now suppose you want to solve this big triangle because you’re a navigator on a ship a couple centuries ago, doing calculations by looking up trig functions and inverse trig functions in a table. You’re interested in triangles that are so big that you have to account for the fact that you’re living on a sphere. But at the same time, your triangles are still fairly small relative to the size of the globe.

The problem with the law of cosines

The numbers a and b will often be fairly small, and so their cosines will be near 1 and their sines are near zero. So the calculation

cos(a) cos(b) + sin(a) sin(b) cos(C)

will add a number near 1 and a number near zero. That’s a problem.

Say you’re working with five decimal place arithmetic. Then if the second term above is less than 10−5, its contribution to the sum gets completely lost in the addition to the first term. If the second term is larger than 10−5 but still small, its contribution to the sum will be partially lost.

Law of haversines

Enter the haversine, defined by

hav(θ) = (1 − cos(θ))/2.

The expression 1 − cos θ was called the versine, and so half of the versine is the haversine.

In terms of the haversine, the law of cosines above becomes the law of haversines:

hav(c) = hav(a − b) + sin(a) sin(b) hav(C).

Now suppose you have a table of haversines and inverse haversines. The law of haversines requires a little less work: you have one less table lookup, and you trade a product for a subtraction.

But the primary advantage is numerical accuracy: the terms on the right side have roughly the same size.

Tables

Note that we’re assuming the values in your table of haversines have been calculated correctly to the given precision. If you calculated your own values of haversines from the definition above, you’d lose precision in the subtraction 1 − cos θ, defeating the advantage of the law of haversines [1].

History

According to Wikipedia.

The first table of haversines in English was published by James Andrew in 1805, but Florian Cajori credits an earlier use by José de Mendoza y Ríos in 1801. The term haversine was coined in 1835 by James Inman.

Experiments

I ran some experiments that carried out arithmetic in float16 (11 bits of precision) to approximate what someone might have done by hand. When the difference between a and b was on the order of 1° or 0.1°, the law of cosine method often overflowed: the right-hand side evaluated to something larger than 1 even though theoretically it should be less than 1. The haversine method never overflowed.

The median error for the haversine method was a couple orders of magnitude less than that of the cosine method.

Related posts

[1] hav(θ) = (1 − cos(θ))/2 = sin²(θ/2). If you calculated hav θ by looking up sin(θ/2) and squaring it, you’d be doing extra work, but you wouldn’t have numerical problems.

Why fitting a logistic is nearly impossible from early data

Posted on by John

Nothing grows exponentially forever. What appears to be an exponential curve often turns out to be some sort of S curve, such as a logistic curve.logistic curve with extrapolations

Suppose you’re collecting data on the left side of the curve. If there’s even a small amount of error in your data, you won’t be able to predict the asymptotic value with any accuracy. But if you have data on both sides of the inflection point, you can make a good prediction of the limiting value.

I’ve written about this before, explaining that the problem is hard, but I didn’t say why it’s hard. Here I’d like to give an idea why it’s hard.

Suppose you want to fit a logistic equation

y(t) = \frac{L}{1 + \exp(-k(t - t_0))}

to three distinct values of t and the corresponding values of y. There is a unique solution, but in general you cannot find a solution in closed form. However, if the values of t are evenly spaced

y_2 - y_1 = y_1 - y_0 = h

there is a method [1] to solve for the parameters L, k, and t0. For this post we’re only interested in the limiting value L, and it can be found by

L = \frac{y_1^2(y_0 + y_2) - 2y_0 y_1 y_2}{y_1^2 - y_0 y_2}

independent of h.

To find out how small changes in the y‘s change the estimate of L, we take the partial derivatives of L with respect to the y‘s and find

\frac{\partial L}{\partial y_0} = \frac{\partial L}{\partial y_2} = \frac{y_1^2\, h^2}{\left(y_1^2 - y_0 y_2\right)^2}

and

\frac{\partial L}{\partial y_1} = \frac{-2\, y_0 y_2\, h^2}{\left(y_1^2 - y_0 y_2\right)^2}
All three derivatives have the same expression in the denominator: y1² − y0 y2.

If the function y(t) were an exponential, this expression would be exactly zero [2]. The function y(t) is not exactly exponential, but it is approximately exponential when the t‘s are in the left or right tail of the logistic curve. The further out in either tail the t‘s are, the closer the expression is to zero.

So when all the t‘s come from the same side of the inflection point, y(t) is nearly exponential the partial derivatives are huge and so the fitted value of L is extremely sensitive to changes in the y‘s.

As a concrete example, set L = k = 1 and t0 = 0. Evaluate y(t) at −2, −1.5, and −1. Then the values of y are

y0 = 0.11920292
y1 = 0.18242552
y2 = 0.26894142

If you forecast L using exactly these three values you’ll get L = 1.

But if you change y0 to 0.12374097, the forecasted value of L is infinite. Values of y0 in the interval [0.11920292, 0.12374097] predict values of K in [1, ∞].

[1] Raymond Pearl and Lowell J. Reed. On the Rate of Growth of the Population of the United States Since 1790 and its Mathematical Representation. Proceedings of the National Academy of Sciences of the United States of America, Vol. 6, No. 6 (Jun. 15, 1920), pp. 275-288

[2] exp(x + h)² = exp(x)² exp(h)² = exp(x) exp(x + 2h)

 

Empirical fractal

Posted on by John

There’s a common saying in discussion of fractals that the length of a coastline depends on how small a device you use to measure it. I thought this was a hypothetical, say as applied to the steps in the construction of the Koch snowflake. But the saying has its roots in actually surveying.

Lewis Fry Richardson (1881–1953) noticed that the length of the coast of Scotland depended on the size of segments used to measure it. More specifically, he found that the length followed a power law, i.e. that there’s a linear relation between the log of the coastline length and the log of the ruler length.

Here’s a reproduction of Richardson’s plot, taken from [1].

Mandelbrot built on Richardson’s observation and defined the idea of fractal dimension.

I was under the impression that fractals were invented as mathematical novelties that researchers later found applications for. But as is often the case, the applications came first. Or at least some applications came first.

Ideally there’s always a feedback cycle where applications lead to theory and theory leads to applications. As Donald Knuth put it, “The best theory is inspired by practice. The best practice is inspired by theory.”

Related posts

[1] Eoghan Bradley and Mark McCartney. Four hundred years of the fractal coastline of Scotland. The Mathematical Gazette, November 2019, Vol. 103, No. 558 (November 2019), pp. 518-521

Phone words

Posted on by John

I recently bought a copy of Los Alamos Rolodex, a book displaying business cards from Los Alamos Nation Labs from 1967 to 1978. You can find some examples of the cards here.

One of the cards in the book is for Eugene Frank, President of B & F Instruments. His card lists his phone number as

(215) MErcury 9-7100

At first glance I thought the “E” in “MErcury” had been accidentally capitalized. Then I realized the intention was that someone would dial ME (i.e. 63) and ingore “rcury”. So the phone number would be (215) 639-7100.

This card was from 1968, the height of the space race. Maybe the card was alluding to the Project Mercury or the planet Mercury, or both. [1]

The telephone keypad mapping (ITU E.161 standard) is a poor attempt at making phone numbers more memorable. For starters, there’s no way to encode 0 or 1 [2]. It’s unlikely a phone number will correspond to anything memorable unless you come up with the word first and then try to obtain the phone number, such as 800 FLOWERS.

Inserting extra letters, as Mr. Frank did, greatly increases the chances of encoding a phone number as a word. But then you need to denote which letters count and which ones are filler, so there’s not much advantage. Still, I wanted to play around with it for fun. I found 109 words [3] containing the letters from a telephone encoding of 4228646. (I’m using the file /usr/share/dict/words on my laptop as my list of words.)

Here are some of the more interesting hits.

  • semicatholicism
  • heartburning
  • gladiatorism
  • diabetogenic
  • galactogenetic
  • xanthocreatinine

There are over 30,000 words containing an encoding of the area code 832. One of these is traditional, and so I could write my phone number as

TraDitionAl semICAThOlIcisM.

Another choice for 832 is intercosmic, so

inTErCosmic GAlaCTOGeNetic

is another possibility.

Galactogentic can refer to the production of milk by the mammary glands or to the formation of galaxies (e.g. the Milky Way). Here intercosmic fits with the later sense.

I got greedy and tried to find a word containing the full phone number, 8324228646, but didn’t find anything.

Here’s my business card in the style of the Los Alamos Rolodex cards, created by Grok, using (832) GlAdiATOrIsM as the phone number.

Now suppose you remembered “gladiatorism” but not which letters were capitalized. Then you’d have to try up to 792, i.e. 12 choose 7, possible numbers, so this really isn’t a practical mnemonic. If you remembered “traditional semicatholicism” without capitalization it would be worse, with over a million possibilities (11 choose 3 times 15 choose 7). Some possibilities are counted twice, since different ways of selecting letters can lead to the same phone number, but still there are too many possibilities to try.

Related posts

[1] Thanks to Andrew for pointing out in his comment that it was common at one time to encode the first two numbers of the exchange (the second triplet of numbers in a phone number) as letters, and assign a word to those letters. Sometimes this was standardized, such as Pennsylvania 6 for 736, an example made famous by Glenn Miller. But from what I can tell, not all exchanges had standard names, and proposed standards weren’t always adopted in practice.

In the example above, I don’t know whether it was common to encode 639 as Mercury 9, or even ME 9, or whether Mr. Frank chose this. It was common chose some encoding for the first two numbers of the exchange, though that practice was going away by 1968. Perhaps Mr. Frank was an older man who retained a habit he acquired when it was more common. None of the other cards in the book spelled out the exchange.

Update: Thanks to Chuck for pointing out this list of recommended words for exchanges. Note that there are multiple suggestions for most exchanges, including six for 63X.

[2] Not only are there no letters for 0 and 1, the letters O and I represent digits. At one point in time the first digit of an exchange (the middle three digits) could not be a 0 or 1, but these digits could appear anywhere else.

[3] I initially found a list of 185 words, but some of these were duplicates: a word can represent a phone number in more than one way.

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 [1].

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.

[1] I poked around a little to get an idea just how unevenly words are distributed. The closest pair of words is jajaja and jajajaja with a cosine similarity of 0.993. The most isolated word, meaning the word whose nearest neighbor is furthest away, the the Thai word เคยไหม. It’s nearest neighbor is the Russian word боль with a cosine similarity of 0.283.

The glove-twitter-200 vectors were created from a corpus that is about half English and about other languages and strings of symbols that are not words in any language. Presumably เคยไหม would have a much closer neighbor in a corpus containing more Thai words.

I didn’t search the entire corpus, only the 50,000 most frequently occurring vectors, because a full search would require running an O(N²) search with N = 1,200,000.

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