Uncategorized

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

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

Ngram error rate

Posted on by John

The Online Etymological Dictionary gives the following etymology for grok:

grok (v.)

“understand empathically,” 1961, an arbitrary formation by U.S. science fiction writer Robert A. Heinlein (1907-1988) in his book “Stranger in a Strange Land.” In the book it is a transliteration of a Martian word and is said to mean etymologically “to drink.” It attained popular use in 1960s-70s counterculture but is perhaps obsolete now except in internet technology circles.

I don’t believe anything in the statement above is disputed. And yet Google’s Ngram Viewer tells a very different story.

The plot implies that use of the word grok had been increasing before Heinlein’s book came out and is now much more common than it was in the 1970s. Note that the plot ends before the Grok AI came out in late 2023.

Apparently the Ngram data is unreliable, mainly for two reasons: OCR errors and inaccurate date attribution. Presumably the blip around 1900 was due to the former, OCR causing words like crok or grog to be cataloged as grok. And presumably the rise in usage before 1961 was due to the latter, misattributing the date of sources published after 1961.

The supposed rise in usage before 1961 is interesting. You’d expect some lag between the time a word circulates in conversation and when it appears in books, but apparently this lag can be smaller than the effect of date misattribution.

Etymonline speculates that grok is “perhaps obsolete now except in internet technology circles.” That matches my experience. Even in technological circles, the word was uncommon before Grok was released. Maybe it was more common in print than in conversation.

Related posts

Previous posts with Ngram stats. The effects are so large that they’re probably directionally correct after adjusting for a substantial error rate.

Hugging Face Easter Egg

Posted on by John

NVIDIA has offered to buy Hugging Face for $12,930,300,000.

129303 is the Unicode code point for the Hugging Face emoj (U+1F917), which you can verify with the following Python code.

>>> import unicodedata
>>> 129303 == 0x1F917
True
>>> unicodedata.name(chr(0x1F917))
'HUGGING FACE'

Hugging Face emoji

Related posts

Three-term recurrences

Posted on by John

There many examples of families of functions where each function can be computed as a linear combination of the two previous terms

f_{n+1}(x) = a(x) f_n(x) + b(x) f_{n-1}(x)

where a and b are functions of x and possibly n. This is called a three-term recurrence formula.

It’s amazing how often you can run into three-term recurrence formulas. There are theorems that give conditions for such recurrences to hold, but I haven’t reached the bottom of that rabbit hole [1].

For this post I just want to give examples.

NB: before using any of the recurrences below, see the next post for a numerical pitfall to avoid.

Bessel functions of the first and second kind:

\begin{align*} J_{\nu+1}(x) &= \frac{2\nu}{x}\,J_\nu(x) - J_{\nu-1}(x) \\ Y_{\nu+1}(x) &= \frac{2\nu}{x}\,Y_\nu(x) - Y_{\nu-1}(x) \end{align*}

Modified Bessel functions of the first and second kind:

\begin{align*} I_{\nu+1}(x) &= I_{\nu-1}(x) - \frac{2\nu}{x}\,I_\nu(x) \\ K_{\nu+1}(x) &= K_{\nu-1}(x) + \frac{2\nu}{x}\,K_\nu(x) \end{align*}

Chebyshev polynomials of the first and second kind:

\begin{align*} T_{n+1}(x) &= 2x\,T_n(x) - T_{n-1}(x) \\ U_{n+1}(x) &= 2x\,U_n(x) - U_{n-1}(x) \end{align*}

Hermite polynomials (physicists’ convention):

H_{n+1}(x) = 2x\,H_n(x) - 2n\,H_{n-1}(x)

Legendre polynomials:

P_{n+1}(x) = \frac{2n+1}{n+1}\,x\,P_n(x) - \frac{n}{n+1}\,P_{n-1}(x)

[1] See Bochner’s theorem for orthogonal polynomials, the Nikiforov–Uvarov method, and Infeld-Hull factorization.

How NASA’s Mariner 9 probe encoded images

Posted on by John

NASA set Mariner 9 to photograph Mars in 1971. The images had to be encoded for transmission using an error-correcting code, otherwise they would be significantly corrupted when they were received on Earth.

The images were encoded for transmission using a code based on Hadamard matrices, specifically a (32, 6, 16) Hadamard code. This means that each 6-bit pixel value was encoded as a 32-bit code word, with all code words differing in at least 16 positions.

The previous post explained a way to construct Hadamard matrices of order 2n. Use this process to create a 32 × 32 Hadamard matrix H and create a 64 × 32 matrix M by stacking H on top of −H. Then form a matrix M′ by changing all the −1 entries to 0. The rows of M′ are the code words.

For a 6-bit photo pixel value, one of the bits determines whether to read a code word from the top half or bottom half of M′. The other five bits determine which row to choose.

So a pixel is transmitted as a 32-bit codeword c, one of the 64 rows of M′. Ideally c would be received, but possibly some corrupted versions c′ is received with some of bits flipped.

Replace all the 0’s in c′ with −1 to create c″. Now multiply M by c″, thinking of the latter as a column vector. This yields a column vector of length 64. The largest component of this vector corresponds to the row of M′ that was most likely sent.

To see this, suppose there was no corruption: c was transmitted and c was received. Then the product Mc″ has a 32 in the entry corresponding to c and zeros everywhere else. If no more than 7 bits in c were corrupted, the row with the largest entry corresponds to the row that was transmitted.

In practice the product Mc″ can be computed using an algorithm analogous to the FFT using fewer operations than it would take to multiply a general 64 × 32 matrix by a 32 × 1 matrix.

Cryptic but consistent

Posted on by John

Suppose you’ve never worked at the command line and you’re reading a book about the bash shell. You read that !$ is a shortcut to refer to the last word of the previous command. That little fact will almost certainly not stick in your head for a couple reasons. First, you probably see no need for such a shortcut. Second, the syntax seems completely arbitrary.

But then after you use the command line a while, you might begin to notice a pattern. You often have to run a pair of commands with the same last argument, such as when you make a directory then navigate into it.

mkdir /some/long/path/name
cd /some/long/path/name

Maybe someone sees you typing this and offers a helpful suggestion: you can type !$ to repeat the last part of the previous command.

mkdir /some/long/path/name
cd !$

Once you learn this, you’ll see uses for it regularly. Sorta like when you buy a green Toyota Corolla and suddenly become aware how many green Toyota Corollas there are out there.

So then you start to use !$, but you have some doubts: is the syntax !$ or $!? As long as it’s just two cryptic symbols, you may have a hard time remembering.

Although the command line is cryptic, it is also consistent. On the command line, and in Unix [1] culture more generally, ! refers to a command. For example, you can run a command from inside the Vim text editor with the :! command. And $ often refers to the end of something, such as the end of a string in a regex. So you type !, telling the shell that you’re about to refer to part of a string, then type $ to specify that last part.

The characters !$ are an example of an event designator, a sort of mini language for referring to parts of commands. The syntax may seem mysterious, but every bit of it is analogous to syntax elsewhere in Unix culture. For example, 

!:s/foo/bar/

replaces the first instance of foo with bar, and 

!:gs/foo/bar/

will replace all instances. This is very similar to commands in sed and in vi For more on event designators, see this recent article by Filip Roséen.

There’s a saying that when the student is ready, the teacher will appear [2]. A less woo-woo version of this saying would be that until the student is ready, it doesn’t matter whether a teacher is there. Once you’ve used the command line to see a need for various shortcuts, there’s a much better chance they’ll stick.

Related posts

[1] Linux has so thoroughly eclipsed Unix that many people say “Linux” when they’re referring to things inherited from Unix that are now part of Linux and other operating systems, as well as various software packages and programming languages.

Here’s a plot of references to Unix versus Linux over time, via Google’s ngram viewer.

[2] When I first heard this, someone told me it was an Asian proverb. It sure sounds like one. But apparently it comes from a 19th century pastiche of eastern and western ideas.

Dogs and fat tails

Posted on by John

I was reading a blog post on boat names because it was on Hacker News this morning. The post contained a link to a data set on dog names in NYC and I poked around the data a little. The top names were not at all what I expected, but then again this is limited to NYC; it’s not a sample across the US. These were the top 10 names:

  1. Bella
  2. Luna
  3. Max
  4. Charlie
  5. Coco
  6. Lola
  7. Rocky
  8. Milo
  9. Teddy
  10. Lucy

I wondered if the name frequencies might fit a power-law distribution. They do not, but they follow a log-normal distribution remarkably well.

Related posts

Manually unbreakable cryptography

Posted on by John

Suppose you were able to go back in time, to an era before computers, and give someone contemporary cryptography. Encryption methods that are essentially unbreakable now would certainly be unbreakable then. But there’s a catch: not only do attackers not have computers, neither do users.

Manual cryptography

If you told someone about RSA encryption, for example, you’d lose them right after you said “First you find a couple 1000-digit primes.” But there’s no need for using 1000-digit primes if no attacker has a computer. You could use 100 digit primes. Could you use 10 digit primes? If you chose primes just big enough to make the method unbreakable by hand, could someone implement it by hand?

Kirchhoff’s principle says the strength of an encryption method should depend only on keeping the key secret, not the method. If you could keep the method secret, RSA would be unbreakable because nobody thought of anything like it before computers. But to make our thought experiment more interesting, let’s suppose that an enemy has also traveled back in time. If you tell your side about RSA, he can tell his side about it as well. So we’re back to Kirchhoff’s principle.

An encryption method combining substitution and permutation would have been practical to carry our manually. The ADFGVX cipher from 1918 was a start in this direction. That idea could been extended further, with a larger substitution set and longer permutations, and with more than one round of substitution and permutation, approaching what would be come the approach used in modern symmetric encryption. Such a method might have been manually implementable without being manually breakable.

Mechanized cryptography

World War II was a time of transition from manual cryptography to computerized cryptography. Encryption machines were attacked by cryptanalysis machines, though these machines were general-purpose computers. If you could implement a symmetric encryption method like AES in a mechanical device, no mechanical device could break it.

You could use something like DES, simpler than AES but still unbreakable at the time. DES is considered broken because now you could throw enough compute power at it to break it by brute force, but that would not be possible with only mechanical devices.

My hunch is that the best approach would be stream ciphers. Maybe it would be practical to implement one of these by hand or with the aid of simple calculating machines. Something like PCG, which is not cryptographically secure today [1], would have been then, though I don’t know how practical it would have been to carry out PCG, say, in the 1940s.

More pre-computer cryptography

[1] In 2020, Charles Bouillaguet, Florette Martinez, and Julia Sauvage were able to break PCG using 20,000 CPU-hours. See their paper Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology. ISSN 2519-173X, Vol. 2020, No. 3, pp. 175–196.