Page 493 - Discrete Mathematics and Its Applications

472 7 / Discrete Probability

THEOREM 2 GENERALIZED BAYES’THEOREM Suppose that E is an event from a sample space
n
S and that F 1 ,F 2 ,...,F n are mutually exclusive events such that F i = S.Assume that
i=1
p(E) = 0 and p(F i ) = 0 for i = 1, 2,...,n. Then
p(E | F j )p(F j )
n
p(F j | E) = .
i=1 p(E | F i )p(F i )

We leave the proof of this generalized version of Bayes’ theorem as Exercise 17.

Bayesian Spam Filters

Most electronic mailboxes receive a flood of unwanted and unsolicited messages, known as
spam. Because spam threatens to overwhelm electronic mail systems, a tremendous amount of
work has been devoted to filtering it out. Some of the first tools developed for eliminating spam
were based on Bayes’ theorem, such as Bayesian spam filters.
A Bayesian spam filter uses information about previously seen e-mail messages to guess
whether an incoming e-mail message is spam. Bayesian spam filters look for occurrences of
particular words in messages. For a particular word w, the probability that w appears in a spam
e-mail message is estimated by determining the number of times w appears in a message from
a large set of messages known to be spam and the number of times it appears in a large set of
The use of the word spam
for unsolicited e-mail messages known not to be spam. When we examine e-mail messages to determine whether they
comes from a Monty might be spam, we look at words that might be indicators of spam, such as “offer,” “special,” or
Python comedy sketch “opportunity,” as well as words that might indicate that a message is not spam, such as “mom,”
about a cafe where the “lunch,” or “Jan” (where Jan is one of your friends). Unfortunately, spam filters sometimes fail
food product Spam comes to identify a spam message as spam; this is called a false negative. And they sometimes identify
with everything
regardless of whether a message that is not spam as spam; this is called a false positive. When testing for spam, it is
customers want it. important to minimize false positives, because filtering out wanted e-mail is much worse than
letting some spam through.

THOMAS BAYES (1702–1761) Thomas Bayes was the son a minister in a religious sect known as the
Nonconformists. This sect was considered heretical in eighteenth-century Great Britain. Because of the secrecy
of the Nonconformists, little is known of Thomas Bayes’ life. When Thomas was young, his family moved
to London. Thomas was likely educated privately; Nonconformist children generally did not attend school. In
1719 Bayes entered the University of Edinburgh, where he studied logic and theology. He was ordained as a
Nonconformist minister like his father and began his work as a minister assisting his father. In 1733 he became
minister of the Presbyterian Chapel in Tunbridge Wells, southeast of London, where he remained minister until
1752.
Bayes is best known for his essay on probability published in 1764, three years after his death. This essay
was sent to the Royal Society by a friend who found it in the papers left behind when Bayes died. In the
introduction to this essay, Bayes stated that his goal was to find a method that could measure the probability that an event happens,
assuming that we know nothing about it, but that, under the same circumstances, it has happened a certain proportion of times.
Bayes’ conclusions were accepted by the great French mathematician Laplace but were later challenged by Boole, who questioned
them in his book Laws of Thought. Since then Bayes’ techniques have been subject to controversy.
Bayes also wrote an article that was published posthumously: “An Introduction to the Doctrine of Fluxions, and a Defense
of the Mathematicians Against the Objections of the Author of The Analyst,” which supported the logical foundations of calculus.
Bayes was elected a Fellow of the Royal Society in 1742, with the support of important members of the Society, even though at that
time he had no published mathematical works. Bayes’ sole known publication during his lifetime was allegedly a mystical book
entitled Divine Benevolence, discussing the original causation and ultimate purpose of the universe.Although the book is commonly
attributed to Bayes, no author’s name appeared on the title page, and the entire work is thought to be of dubious provenance.
Evidence for Bayes’ mathematical talents comes from a notebook that was almost certainly written by Bayes, which contains much
mathematical work, including discussions of probability, trigonometry, geometry, solutions of equations, series, and differential
calculus. There are also sections on natural philosophy, in which Bayes looks at topics that include electricity, optics, and celestial
mechanics. Bayes is also the author of a mathematical publication on asymptotic series, which appeared after his death.