Machine learning and natural language processing - The Computing Universe: A Journey through a Revolution - page 285

mathematician Gordon Welchman and engineer Harold Keen, Turing designed
a machine called the bombe , a high-speed electromechanical machine that
tested possible Enigma wheel arrangements ( Fig. 14.1 ), saving time by reduc-
ing the number of possible solutions. However, in the worst case it could still
take up to four days to try all the 336 possible wheel positions, and such a
delay meant that the information was of no use for rerouting ships away from
the U-boat packs. In an attempt to reduce the number of wheel positions that
needed to be searched, Turing and the team looked for what they called cribs ,
German words that they thought likely to occur in the unencrypted text. Many
of these came from German weather ships, which often repeated phrases like
“weather for the night” and “beacons lit as ordered.” In addition, because the
German operators spelled out numbers, the word ein (one) appeared in 90 per-
cent of Enigma messages. Armed with such cribs, Turing invented a manual sys-
tem that could reduce the number of wheel settings to be tested by the bombes
from 336 to as few as 18. He called his system Banburismus , after the nearby
town of Banbury where a printing shop produced the six-foot strips of card-
board needed to put his system into practice. To use the Banburismus system,
staff at Bletchley punched holes corresponding to each intercepted message
into a Banbury sheet. By putting one of the sheets on top of another, they could
see when letter holes coincided on both sheets. This enabled Turing's team to
guess a stretch of letters. They could update this guess as more data arrived,
using Bayesian inference, which uses a combination of new information and
prior beliefs to eliminate the least likely choices. To compare the probabilities
of his guesses, Turing introduced a unit of measurement he called a ban - short
for Banburismus. A tenth of a ban was called a deciban and, according to Jack
Good, Turing's colleague at Bletchley, “A deciban is about the smallest weight
of evidence perceptible to the intuition.” 4 By June 1941, the Bletchley Park team
could read messages to the German U-boats within an hour of their arrival.
After the war, the applications of Bayesian inference multiplied rapidly.
Jerome Cornfield, working at the U.S. National Institutes of Health (NIH),
introduced Bayesian methods into epidemiology, the branch of medicine that
studies the incidence and distribution of diseases. Using Bayes' Rule, Cornfield
combined research showing the probability that someone with lung cancer
was a cigarette smoker with NIH data to answer the opposite question, “What
is the probability that someone who smokes will develop lung cancer?” His
results showed that smokers are many times more likely to develop lung can-
cer than nonsmokers. At the RAND Corporation in Santa Monica, California,
Fred Iklé and Albert Madansky used a Bayesian approach to estimate the prob-
ability of an accident involving nuclear weapons. Because there had only been
“harmless” accidents with nuclear bombs, there was nothing that could be
said about this question from a frequentist viewpoint. Their report was com-
pleted in 1958 but remained classified for more than forty years. However, the
report persuaded General Curtis LeMay of the Strategic Air Command to issue
orders that two people should be required to arm a nuclear weapon and also
that combination locks should be installed on the warheads. A third applica-
tion area was in business, where executives routinely have to make critical
decisions with incomplete data and much uncertainty. At the Harvard Business
School, Robert Schlaifer and Howard Raiffa introduced Bayesian methods to

Fig. 14.1. A functioning replica of the
bombe code-breaking machine rebuilt at
Bletchley Park.