Murder and NLP: The Taman Shud Case, Part 2

In my last post, I showed that the Tamam Shud Cipher (TSC) is almost certainly an initialism, a sequence of initials taken from English text. So what does it say, and why was it written?

It should be noted first that two hypotheses, not exclusive of one another, regarding the other facts of the case are:

H1) That Somerton Man was a Cold War spy who was operating for the Soviets or perhaps the Americans.

H2) That the nurse whose phone number was found in the book was a potential lover of the Somerton Man, and the Rubaiyat was given to him by her to share the romantic aspects of the poetry. She admitted having given another copy of the Rubaiyat to another man in 1945. That man and book both turned up during the investigation.

In that light, some possibilities for the source text behind the Tamam Shud Cipher:

P1) Passage(s) from existing literature.

P1a) Written out to help the writer memorize that literature.

P2) Something written by a person who once had the book.

P2a) A message sent by a Cold War spy.

P2b) A message written out for a friend or lover to read.

P2c) A rough draft for original poetry or prose using initials as shorthand.

P2d) Written out to help the writer memorize their own composition.

P3) Scratchwork for solving a puzzle.

We can investigate each of these possibilities, although definitive answers may prove elusive. I'll devote the rest of this post to beginning an examination of possibility (P1).

If the TSC can be found, in its entirety, in the initials of any previously-existing work of literature, then we can be sure we've found the answer. Why? The probability of two texts sharing the same initials is a function of their length, L, in words, and is approximately:

p_Match = 1 / 10^L

The number 10 occurs here because the probability of two randomly-chosen initials from English text being equal is about 1/10, not the 1/26 you would see if all letters occurred equally likely. The exact parameter may be experimentally derived and certainly isn't exactly 10.0, but it's so close that I use 10 to make the math easier to comprehend. The shortest line in the TSC has 9 letters and the longest has 13. Finding a random passge of 9 words to match the shortest line has a probability of about one in a billion, while a passage matching the longest line has a probability of about one in ten trillion. Meanwhile, the probability of an accidental match for the entire 44 TSC is a dicey 10^-44, which is essentially zero. If we find any existing text that matches the entire TSC, then it is definitely the text used to produce the TSC.

Note: This does not mean that if a person tries to write out their own original match for the TSC and succeeds that they have found the answer. In fact, it's not that hard to write text to match a given set of initials, which produces the illusion that someone can make quick and easy progress towards figuring it out. I will show in a later post how easy it is to concoct bogus matches after the fact.

Of course, finding matches for shorter substrings is easy, for sufficiently short length. Obviously, matches for substrings of length 1 and 2 are trivial to find, and by searching larger volumes of text, one finds matches of length 3, 4 and so on.

Work has been done in the past on trying to find exact matches for the TSC in a handful of major literary works, including the King James Bible. After an initial, failing search through digital copies of 40 books and 18 collections of poetry, I conducted a rather massive search which is as follows:

Project Gutenberg creates digital transcriptions of literary works. For my search of TSC matches, I downloaded by torrent the April 2010 collection of 29,500 books. Of these, 22,353 books are in text format. I preprocessed these to create an index of their initialisms, which amounts to 1.3 billion words of original text. I searched this for the longest matches that exist for TSC substrings, to arrive at these results:

R1) There is no exact match for the entire TSC, or any of its individual lines.

R2) The longest matches are of length 8, and there were twelve of these. It is apparent that these are entirely coincidental for the following reasons:

a) Many of them contradict one another, by matching the exact same subsequence of TSC.

b) They each begin in the middle of a sentence, and continue on into the middle of the next sentence.

c) We would expect, from the aforementioned formula, to find about ten matches of length L=8 and one match of length L=9 by sheer coincidence.

d) One of the matches is from 1963, many years after TSC was written down.

The matches were from nine works of literature, and one work each from science, economics, and reference. The matches are posted separately here.

In a nutshell, the Project Gutenberg corpus does not contain a match, and this should set the tone for any future searches. The works in this corpus are not only large in number but particularly central in literary importance. It is hard to characterize "literary importance" formally, but the reach of this corpus is impressive. When one thinks of authors predating 1950 who are likely to be taught in university literature courses, the number of works this corpus has is vast, although not comprehensive. For many famous works, it includes more than one edition. There are also translations of English works into other languages (although, recall, TSC is almost certainly an initialism of English text) and translations of literature in other languages into English.

Until a match is found, we can never prove that there is no match. Whatever corpus of n books we search, it's always possible that the exact match will be found in book n+1. It remains possible that TSC matches a book, poem, newspaper article, or other text not in this Gutenberg Corpus, but a lack of matches in 22 thousand books certainly suggests that searching any additional one – or one hundred – books chosen arbitrarily will yield a very low probability of finding a full, exact TSC match.

In an upcoming post, I'll discuss possibility (P2), and how to use a large corpus (now that we have one) as a resource for trying to decode the TSC. We can perhaps find information about the words or genre that are encoded within it. And that will also open up paths to searching for exact matches.

Murder and NLP: The Taman Shud Case, Gutenberg Matches

Appendix:

Longest matches of substrings of the Tamam Shud Cipher among the initials in a corpus of 22,353 Project Gutenberg books. These are all of length 8. There were many shorter matches and no longer matches.

Title, Author, Substring, Passage

"The Iceberg Express", David Magie Cory

cittmtsa: cake i think the mermaid took somewhat after

"On Laboratory Arts", Richard Threlfall

cittmtsa: care is taken to make the strokes as

"Showell's Dictionary of Birmingham", Thomas T. Harman and Walter Showell

cittmtsa: Church in this town, Mr. Thomas Smallwood, an

"Beatrix", Honore de Balzac

cittmtsa: contemplating in turn the marshes the sea and

"The Nail", Pedro de Alarçon

iaboaiaq: is a beautiful one, and I am quite

"The Evolution of Modern Capitalism", John Atkinson Hobos

ittmtsam: in the textile metal transport shipping and machine

"Northanger Abbey", Jane Austen

ittmtsam: it together that miss thorpe should accompany miss

"The Trouble with Telstar", John Berryman

ittmtsam: itching to take me to see a man

"Pensées", Blaise Pascal

mtsamstg: make them saint augustine montaigne s'bond the genealogy

"A Woman for Mayor", Helen M. Winslow

mtsamstg: motioned the stenographer and miss snow to go

"Ernest Maltravers", Edward Bulwer-Lytton

tpmliabo: that point my life is a bad one

"Carette of Sark", John Oxenham

ttmtsams: than twenty miles there soon after midnight steal

Murder and NLP: The Taman Shud Case, Part 1

Computational Linguistics Murder Mystery Theatre

Cracking the code found near the body of a dead man could help reveal the identity of his killer.

On December 1, 1948, the body of a dead man was found on Somerton Beach near Adelaide, South Australia. The identity of the man (henceforth, Somerton Man) was nowhere to be found among his belonging, and no one ever came forth to identify him. He seemed otherwise healthy, and the cause of death was possibly a deliberate poisoning. The identity of his killer, if there was one, has not been established. It is possible that he was a Soviet spy, and possible that he was killed for reasons pertaining to espionage, but that is speculative. The case remains one of the strangest unsolved crimes in Australia's history.

A slip of paper was found in the dead man's pocket, containing only the words "Tamam Shud." This was identified as the final line of Omar Khayyam's Rubaiyat, and a man came forward saying that he found a copy of the book in his car near the beach the same day the body was found. It turned out to be the same copy the slip of paper was torn from. Written in the book was the phone number of a nurse who lived nearby, and denied knowing the man, but various claims have been made that she did know him and was lying.

What does this strange murder story have to do with Natural Language Processing?! Also written in the book was a sequence of letters, in five lines. There is some ambiguity in the handwriting, but one reasonable reading of four of them is as follows:

WRGOABABD

WTBIMPANETP

MLIABOAIAQC

ITTMTSAMSTGAB

In addition, a line which begins like the third line above was written and crossed out between the first and second.

These letters are not in any obvious way comprehensible, and it has been supposed that the letters might represent a cipher that, if broken, would shed some light on the case. From here forward, I will call this the Tamam Shud Cipher, or TSC, although it is not clear that it is actually is a cipher, an intentionally coded message, in the literal sense of the term. The TSC has not been decoded in a highly convincing way in whole or in part.

Following many hypotheses regarding the nature of the cipher, previous work, including that of the students of Derek Abbott at the University of Adelaide, has suggested that the letters may be initials from an English text.

In previous work, the frequency of letters in the TSC was compared to letter frequencies in other collections of text. First, with samples of several languages, and next with the initial letters of words in those languages. The second is not the same as the first, because letters occur with different frequencies in different positions in words; for example, 'e' is the most common letter in English, but 's' and 't' begin more words than 'e'. Abbott’s students found that the TSC letter frequencies match those of English initials significantly better than those of English text overall, and also better than initials or text in any of several languages. I have performed similar tests using different source texts and reach the same conclusion.

This provides evidence that the TSC is, in fact, an initialism, a sequence of initials from some specific text – in this case, a short English text. However, this evidence falls short of proof. It shows that an English initialism is the best of the possibilities that were tested, and a quite a few were tested, but it leaves open that an untested possibility would fit the TSC letter frequency just as well or better. It also leaves unexamined the possibilty that the letters in TSC are initials taken from English text but are possibly in another sequence.

And so, more definitive evidence that TSC is an initialism from a specific English text is to examine short sequences of letters in TSC and measure how they rank compared to the sequences of initials from English text in general. Grammatical patterns in English make some sequences of initials more common than the same initials in another sequence, so by performing this study with the TSC and variations of TSC with its letters scrambled in random order, we should see how likely it is that TSC preserves the expected sequences.

We can use an arbitrarily large corpus of English to generate the initial-letter ngrams for English, but the TSC itself is short, and therefore it samples the space of ngrams very sparsely. This means that many kinds of statistical metrics will show a mismatch between TSC ngrams and corpus ngrams even if they are initialisms from the same language. For example, Pearson correlations of bigrams from a known, but short, English initialism and the corpus will come up negative due to the sparseness of the short string’s ngram matrix.

A useful metric that is more sensitive when the string we are testing against a corpus is short is to generate the ngrams within the string, and calculate the mean of how high those ngrams rank among the corpus ngrams. This, in effect, gives the string credit for containing common initial ngrams, but doesn’t punish it for lacking other initial ngrams because it is simply too short to “get around to” them.

I generated 1,000 random shuffles of the TSC, and for the TSC and each shuffle, I calculated the mean rank of the string’s initial ngrams in terms of those generated from a corpus of 5 million words of English literature, for n from 2 to 5. If the sequence of letters in the TSC are initials selected at random from English texts, or if they were generated by some other means altogether, then the mean ranks for the TSC should be about 50^th percentile in terms of the mean ngram ranks for the 1,000 random shuffles of TSC. If, however, the TSC was generated as an initialism from a specific English text, then its mean ngram ranks should be significantly higher than 50^th percentile. The results follow:

N         TSC Percentile

2          85.6

3          92.3

4          96.4

5          93.6

We see that the results are convincing, particular when n=4 (the matrices begin to become sparse for n=5, weakening the result). For many scientific purposes, 95^th percentile is offered as a standard of proof, and these results are fairly convincing that the TSC is an initialism, in correct order, of English text.

However, notes also that the TSC is written as a series of lines which may be linguistically unrelated to one another. If the four lines of TSC are lines of poetry, separate sentences, or in any way excerpts of a longer text, then the ngrams that are generated across the boundaries of lines potentially introduce noise. The idea that the lines are separate entities is further validated by the fact that the crossed-out line occurs in a different order than the similar line which is not crossed out.

So we can repeat the analysis, comparing TSC’s ngrams to those generated from random shuffles of TSC, but excluding the ngrams of TSC that start on one line and end on another. If TSC is not derived from sequences of English initials, we would, again, expect to see it rank about 50^th percentile in mean ngram rank among the random shuffles. What we see, instead, greatly strengthens the previous result.

N         TSC Percentile

2          96.9

3          99.2

4          99.2

5          99.2

It is exceedingly unlikely that any other method of generating lines of letters would show this regularity if these lines were not initialisms corresponding to one or more short English texts.

And so, this turns the focus deeper, given that the Tamam Shud cipher very likely is an initialism of some short English text(s), what does it say, and what does that say about the case? The story goes on in my next post.

APIs for Multilingual NLP

Coming soon, I will be able to announce the availability of APIs that provide text analytics in the world's major business languages.

A placeholder to that site is at gistology.com, showing with a map the scope of the countries whose languages will be covered. There'll be more to say about this soon.

Is Google Racist?

Like many service available online, Google's search bar offers completions that suggest the rest of a user's query before they have to type it all out. Potentially, you could enter a 25-letter query in just a few keystrokes, saving a little time – and who doesn't love saving time?

Sometimes, though, you see something like this:

In this case, I deliberately "baited" Google by starting out with a query that I knew would elicit a result like this, but it certainly took the bait. Maybe someone is wondering why black people are more likely than other races to have to sickle-cell anemia, but Google guesses instead that they have a racist question that want to research.

So Google was wrong, and fails to save the person a couple of seconds. But it does something more than that. It exposes the user to a couple of stereotypes that range from unflattering to extremely offensive. And by moderating the query a little, you can find a treasure trove of other stereotypes according to Google completions:

Californians are fake, stupid, and weird. Texans are stupid idiots. New Yorkers are rude and arrogant. (Actually, most groups of people are rude, if you go by the Google completions.) Americans are obese and ignorant. Chinese people are smart. Jews are rich. Asians are bad drivers. At least, this is what Google completions suggest, in response to a partially-typed query.

Why do these completions exist? Who is actually putting these stereotypes forth as true? You'd have to know Google's backend architecture in detail to answer that exactly, but some experimentation indicates the following:

1) People who type queries into Google. Common queries are more likely to appear as completions.

2) People who create web pages. Some completions are oddly-worded and unlikely to have originated as queries, but appear verbatim in various web pages.

3) People who see these queries and then select them. This is where the algorithm becomes insidious. The intention of a completion is to help someone save the effort of typing. But an interesting completion might sidetrack someone from their original purpose and click on it just to see what it's about. For example:

Benjamin Franklin had syphilis? Maybe some student had to write a term paper on the great thinker and now they've been given the lurid suggestion that the man had a sexually-contracted disease! If true, it's certainly not why Franklin became famous, but there it is as one (in fact, two) of the top four relevant facts about the man. Never mind his efforts in founding the United States, publishing newspapers, discovering the electrical nature of lightning and so on: He had V.D.! That's bad enough if it were true, but in fact, it appears not to be! If you follow the links these completions lead to, none of them have any evidence that Franklin had syphilis – just people asking if he did. But I'll admit, the completion made me want to click on it. And that's exactly the problem. I just "voted" for the Franklin - syphilis link, elevating it a little bit higher than the other possibilities. If syphilis had started off as the #4 completion, people like me vote it up to a higher position on the list, so more sensational queries tend to "win".

As a consultant for a news aggregator startup, I once had access to the data of which headlines people clicked on. An unmistakable trend was that headlines with exciting, sensational words in them were clicked on more often. This was true even if the word was simply being used as a metaphor ("Interest Rates Explode", "President Attacks His Critics").

It doesn't require that a lot of people believe that Franklin had syphilis or that any of those stereotypes are listed are true. It only requires that enough people type that query (or click on webpages that assert or even ask the question), it gets somewhere on the list of completions (maybe #10) and then other people see that completion, get intrigued, and vote it up. In fact, a lot of the people who vote up the racial stereotypes could even be people who are incredibly offended by them.

Benjamin Franklin is dead, but these sorts of completions exist for living celebrities, too. I did a search for 3 former NFL quarterbacks, and one of them had a completion for "gay". The man in question has denied being gay. How many people, every day, see this completion? Google is in effect spreading rumors about the man's personal life, just as they flash before our eyes a number of racial stereotypes.

So what is Google's role in this? Surely not that someone at Google decided that these racial stereotypes are useful suggestions. Google only built the system. The data voted for these completions to rank so high. If Google's algorithms work so well in general, then they can claim neutrality on these questions and say, Sorry, but these are the completions lots of people type and choose.

Except Google isn't neutral. Google does sanitize their completions in many cases.

If you type "scarlett johansson photos..." into Google's search bar, and then add any letter of the alphabet, it will show you completions. Any letter, that is, besides "n". "scarlett johansson photos n" produces no completions at all. Why? And so what? The reason why is that Google has specifically censored the completion that would allow the word "nude" to appear. I've had access to the logs of queries from search engines, and I guarantee you that the completions Google shows for "scarlett johansson photos" are not more common than "scarlett johansson nude" or "scarlett johansson photos nude". In fact, Google shows no completions for the word "nude" all by itself, even though it shows completions for "Mohorovičić discontinuity"... which one do you think people are searching for more?

So Google isn't completely neutral. They let the data vote for itself sometimes, even usually, but they censor some completions on, apparently, the suspicion that the results would be offensive or non-family-friendly.

Given that, there's not much excuse for letting these racial slurs show up. If it's offensive to suggest that an actress has taken her clothes off, it's certainly more offensive to allow the data to promote the racial stereotypes listed above. "It's just data" is a valid excuse for a person or company who uses big data as a tool. But once human hands go to work in the system, selecting what does and doesn't show up, those hands start to take some of the blame for the whole system. One imagines that these stereotypes have simply been below Google's radar, and that the "Don't Be Evil" company would want to censor those completions once they're aware of them.

Laughing Out Loud

This may make you laugh.

And laughs are something people like to share. When people communicate via social media, they type "laughs." In a sample of a million words of Twitter messages in ten different languages, I found that about 0.5% of all "words" are laughs – "haha", "LOL", or other ways of typing out a chuckle.

Do people everywhere laugh equally?

Not on your life.

In a study of ten Western languages (English, German, Dutch, Norwegian, Swedish, Danish, French, Spanish, Italian, and Portuguese), I found enormous differences in the frequency of Twitter-laughs.

The Germans laugh least, with Twitter laughs making up under 0.1% of all words.

Other languages of Northern Europe were somewhat more prone to laughs than German. In increasing order of laugh frequency, Norwegian, French, Swedish, English, and Danish all came in below 0.4%.

And then there are the happy Latins. Laughing just more than the Danes, Portuguese has 0.5% laughs, and that's nothing compared to the Italians who Twitter-laugh in 0.9% of words. But the runaway laugh champions are Spanish speakers who type Twitter laughs for 1.4% of words.

The North-South pattern is noteworthy, but is broken by the Dutch, who out-laugh their neighbors like they're misplaced Latins, finishing way up at 0.8%.

The Dutch withstanding, the North-South trend is sharp and undeniable, as this color-coded map makes clear.

What's even funnier, the languages where people laugh more often, they also type longer laughs.

While three "ha"s are the preferred laugh in Spanish and Italian, they are not afraid to laugh longer. The five-ha laugh ("jajajajaja") is more common in Spanish than the two-ha laugh is in German. This graph shows how laugh length occurs in the five most-spoken languages. While Spanish runs away with the championship here at every length, notice that English is actually the runner-up for the two-ha laugh ("haha") with Italian strongly preferring a three-ha approach ("ahahah").

When you take into account the length as well as frequency of laughs, Spanish Twitter has 24 times more laughing than German, as measured in character count. This is not a subtle difference!

So, why is all of this happening? It's clear that more Twitter laughs come from the warmer and sunnier countries.This is true not only in Europe but also in the Americas, where the most speakers of English, Spanish, and Portuguese live. Statistically speaking, the laugh statistic is highly correlated with the latitude of the corresponding European capital (farther south: r=0.66), how sunny that city is (more sun: r=0.74), and inversely with the suicide rate (r=-0.74; this is the same if you choose the U.S., Mexico, and Brazil instead of the U.K., Spain, and Portugal).

So is it as simple as this: Warm, sunny weather makes people laugh a lot and immune to depression?

That may be part of it. But another idea to consider is that in Germany and Scandinavia Twitter is used comparatively more often for business and relatively less often for chatting. When one subtracts the social chat, then naturally less laughter remains.

Overall, it's not clear how much Twitter reflects life as a whole. Until we plant microphones everywhere and monitor all human communication, studies like this will just be suggestive of larger truths. But insofar as it goes, this study of Twitter laughs serves to support a lot of existing cultural stereotypes.

Social Media: Linguistic Anarchy?

Your schoolteacher would be horrified. As technology opens up new channels for people to communicate via the written word, the use of language in those channels becomes increasingly ill-formed and deviant. Social critics may look at this as a relaxation in standards, a harbinger of the decay of reason and civilization.

However, it's really not that bad. People feel differently about standards in language, and one might observe that if language use did not vary over time, we would still be speaking Latin, Anglo-Saxon, Proto-Indo-European, or some more primeval language. Whether you identify more with prescriptive linguistics (the use of instruction to make students keep in line with existing standards) or descriptive linguistics (the laissez-faire study of language to understand it, without concern for changing how people use it), the truth is that people still adhere to standards, and in many ways, those standards aren't so different in the era of electronic media than they were in the long-lost era of pens and inkwells.

How does English, say, on Twitter, differ from English in the news? Certainly one sees slang, profanity, misspelling, and neologisms. But the single greatest set of differences come from the different kind of interaction. The news is meant to sound like the voice of God, detached, objective, hovering over the topic and the reader alike in the Third Person. In contrast, many interactions in social media are person-to-person, openly subjective, inherently spoken by the First Person to the Second Person... often on the topic of the First Person and/or the Second Person.

For ten major European languages, I have computed word frequencies for a corpus of news and of Twitter posts, and here I focus on the words which are the most prevalent on Twitter as compared to the news (frequency in Twitter minus frequency in the news). And for English, the word at the top of that list is nothing that would give schoolteachers and the clergy a stroke. It is "I." In fact, of the 39 words topping that list, only the acronym "LOL" and the abbreviation "u" are the stuff of which schoolteacher nightmares are made. The other 37 are almost exclusively words that are very common in The Queen's English and American Standard English, but happen to be more prevalent in first person narration than in the third person. They are common words that are natural descriptors of situated language, where the speaker's and listener's identity, time, place, attitude, and -- more generally -- their context, are part of the discussion.

And so, with an eye towards the top 25 words on the (Twitter-minus-news) frequency list, we see the following categories:

First-and-Second Person forms: I, am, me, my, we...

Deixis (words referring to the speaker's or listener's situation): today, just...

Simple, plainspoken vocabulary, words that are common in the news, but still more common for writers who are not consulting the thesaurus to make their language more flowery: not, was, do, had, did, have, got...

Far lower on the list come the shock words: "shit", "fuck", "alot", "alright", "ima", etc. And even the abbreviations are understandable, when writers are constrained to squeeze their idea into the 140 character limit, and deal with keypads that make extra effort a true burden. A drowning person is likely to yell for help in something other than complete sentences, and a person straining to fit an idea into Twitter's constraints has a legitimate motive for abbreviating more than they otherwise might. All told, we see that people have a strong tendency to hold to convention -- not the universal adherence to convention that William Safire would have liked, but it is still the most common case.

This is true in other languages as well, and to much the same degree. Here are, according to Twitter-minus-news frequency, the top 25 words for the five leading Western European languages. They reflect more or less the same tendencies.

English: I, 's, not, am, me, my, was, he, do, we, had, lol, news, did, u, have, new, today, just, think, haha, got, 'd, game, she.

French: je, j, c, pas, est, ai, tu, mais, moi, me, que, ça, a, t, mon, suis, on, ma, si, y, fait, il, te, quand, m.

German: ich, du, ja, d, nicht, aber, mir, mal, hab, was, jetzt, so, ist, noch, mich, da, dann, bin, es, schon, das, war, wenn, auch, dir.

Spanish: no, me, q, te, es, ya, si, yo, lo, jajaja, mi, tu, a, d, mas, pero, XD, jaja, jajajaja, eso, México, son, hay, solo, x.

Italian: non, mi, ho, io, ma, che, d, XD, è, ti, se, u, a, me, sono, lo, o, no, ci, l, ora, çç, sei, mia, poi.

Interestingly, the negative adverb in each language appears quite high. This seems to indicate that journalists exercise a discipline to express things in terms of positives while people generally use the negative a larger proportion of the time.

The big cross-language difference that is evident from the above is in the tendency for Twitter users to type out a "laugh", and this particularly stands out on the Spanish list. This merits a fun and funny, follow-up post on how much people type out laughs in different languages. The results will probably not surprise you.