Baysian Spam Detector

Spam detection with Bayesian Networks

These are my notes for the Bayesian Networks section of the udacity course on artifical intelligence.

In [22]:
# python standard library
from fractions import Fraction
import sys
In [23]:
# it turns out 'reduce' is no longer a built-in function in python 3
if sys.version_info.major >= 3:
    from functools import reduce
In [24]:
spam = 'offer is secret, click secret link, secret sports link'.split(',')
In [25]:
ham = 'play sports today, went play sports, secret sports event, sports is today, sports costs money'.split(',')

The terms have to be changed to be either all plural or all singular. In this case I changed 'sport' to 'sports' where needed.

The SpamDetector classes

I originally implemented everything as functions, but decided it was too scattered and created these after the fact, which is why there's all the duplication below. I left the old code to validate these classes.

The MailBag

This class holds either spam or ham. It actually holds both but the idea is one of them is the real type of interest.

In [26]:
class MailBag(object):
    A place to put spam or ham
    def __init__(self, mail, other_mail, k=0):
         - `mail`: list of example mail
         - `other_mail`: mail not in this class (e.g. spam if this is ham)
         - `k`: Laplace smoothing constant
        self.mail = mail
        self.other_mail = other_mail
        self.k = k
        self._bag = None
        self._probability = None
        self._vocabulary_size = None
        self._sample_size = None

    def vocabulary_size(self):
        :return: count of unique words in all examples
        if self._vocabulary_size is None:
            self._vocabulary_size = len(set(self.bag) | set(self.bag_boy(self.other_mail)))
        return self._vocabulary_size

    def bag(self):
        :return: list of words in `mail`
        if self._bag is None:
            self._bag = self.bag_boy(self.mail)
        return self._bag

    def sample_size(self):
        :return: count of mail in both spam and not spam
        if self._sample_size is None:
            self._sample_size = len(self.mail + self.other_mail)
        return self._sample_size
    def probability(self):
        :return: count of this mail/total sample size
        if self._probability is None:
            SPAM_AND_HAM = 2
            self._probability = self.l_probability(len(self.mail),
                                                   len(self.mail) + len(self.other_mail),
        return self._probability

    def bag_boy(self, lines):
         - `lines`: list of lines

        :return: list of words taken from the lines
        tokenized = (line.split() for line in lines)
        bag = []
        for tokens in tokenized:
            for token in tokens:
        return bag

    def l_probability(self, event_size, sample_size, classes):
         - `event_size`: count of events of interest
         - `sample_size`: count of all events
         - `classes`: count of all classes of events

        :return: probability with Laplace Smoothing
        return Fraction(event_size + self.k,
                        sample_size + classes * self.k)

    def p_message(self, message):
         - `message`: line of mail

        :return: p(message|this class)
        probabilities = (self.p_word(word) for word in message.split())
        return reduce(lambda x, y: x * y, probabilities) * self.probability
    def p_word(self, word):
         - `word`: string to check for
        :return: fraction of word occurence in bag
        return self.l_probability(self.word_count(word), len(self.bag), self.vocabulary_size)
    def word_count(self, word):
         - `word`: string to check for
        :return: number of times word appears in bag
        return sum((1 for token in self.bag if token == word))


In [27]:
class SpamDetector(object):
    A bayesian network spam detector
    def __init__(self, spam, ham, k=0):
         - `spam`: list of example spam lines
         - `ham`: list of example ham_lines
         - `k`: laplace smoothing constant
        self.spam = MailBag(mail=spam, k=k, other_mail=ham)
        self.ham = MailBag(mail=ham, k=k, other_mail=spam)

    def p_spam_given_message(self, message):
         - `message`: line to check if it's spam
        :return: probability that it's spam
        p_message_given_spam = self.spam.p_message(message) 
        return p_message_given_spam/ (p_message_given_spam +

# leave this in the same cell so updating the class updates the instance
detector = SpamDetector(spam=spam, ham=ham)
l_detector = SpamDetector(spam=spam, ham=ham, k=1)

What is the size of the vocabulary?

In [28]:
def bagger(mail):
    converts list of lines into list of tokens
     - `mail`: list of space-separated lines
    :return: list of words in `mail`
    mail_tokenized = (line.split() for line in mail)
    mail_bag = []
    for tokens in mail_tokenized:
        for token in tokens:
    return mail_bag

spam_bag = bagger(spam)
ham_bag = bagger(ham)
In [29]:
def assert_equal(expected, actual, description):
    assert expected == actual, \
        "'{2}'\nExpected: {0}, Actual: {1}".format(expected, actual,
In [30]:
vocabulary_list = set(spam_bag) | set(ham_bag)
vocabulary = len(set(spam_bag) | set(ham_bag))
assert_equal(spam_bag, detector.spam.bag, 'check spam bags')
assert_equal(ham_bag, detector.ham.bag, 'ham bags')
assert_equal(vocabulary, detector.spam.vocabulary_size, 'vocabulary size')

what is the probability that a piece of mail is spam?

In [31]:
mail_count = len(ham) + len(spam)
assert_equal(mail_count, detector.spam.sample_size, 'mail count')
p_spam = Fraction(len(spam), mail_count)
assert_equal(p_spam, Fraction(3, 8), 'p-spam known')
assert_equal(p_spam, detector.spam.probability, 'p-spam detector')

what is p('secret'| spam)?

In [32]:
def word_count(bag, word):
    count the number of times a word is in the bag

     - `bag`: collection of words
     - `word`: word to count
    :return: number of times word appears in bag
    return sum((1 for token in bag if token == word))
In [33]:
def p_word(bag, word, k=0, sample_space=12):
    fraction of times word appears in the bag

     - `bag`: collection of words
     - `word`: word to count in bag
     - `k`: laplace smoothing constant
     - `sample_space`: total number of words in vocabulary
    :return: Fraction of total bag that is word
    return Fraction(word_count(bag, word) + k, len(bag) + k * sample_space)
In [34]:
p_secret_given_spam = p_word(spam_bag, 'secret')
assert p_secret_given_spam == Fraction(3, 9)
assert_equal(p_secret_given_spam, detector.spam.p_word('secret'),
             'secret given spam')

what is p('secret'| ham)?

In [35]:
p_secret_given_ham = p_word(ham_bag, 'secret')
assert p_secret_given_ham == Fraction(1, 15)
assert_equal(p_secret_given_ham, detector.ham.p_word('secret'), 'p(secret|ham)')

You get a message with one word - 'sports', what is p(spam|'sports')?

In [36]:
$p(spam|`sports') = \frac{p(`sports' | spam)p(spam)}{p(`sports')}$
$p(spam|`sports') = \frac{p(`sports' | spam)p(spam)}{p(`sports')}$
In [37]:
p_sports_given_spam = p_word(spam_bag, 'sports')
assert p_sports_given_spam == Fraction(1, 9)
assert_equal(p_sports_given_spam, detector.spam.p_word('sports'),
In [38]:
p_sports_given_ham = p_word(ham_bag, 'sports')
expected = Fraction(1, 3)
assert p_sports_given_ham == expected
assert_equal(p_sports_given_ham, detector.ham.p_word('sports'),
In [39]:
p_ham = Fraction(len(ham), mail_count)
assert_equal(p_ham, detector.ham.probability, 'p(ham)')
In [40]:
p_sports = Fraction(word_count(spam_bag, 'sports') + word_count(ham_bag, 'sports'), vocabulary)
In [41]:
p_spam_given_sports = (p_sports_given_spam * p_spam)/(p_sports_given_spam * p_spam + p_sports_given_ham * p_ham)
assert p_spam_given_sports == Fraction(3, 18)
assert_equal(p_spam_given_sports, detector.p_spam_given_message('sports'),

Given the message 'secret is secret', what is the probability that it is spam?

In [42]:
$p(spam|message) = \frac{p(message|spam)p(spam}{p(message|spam)p(spam) + p(message|ham)p(ham)}$
$p(spam|message) = \frac{p(message|spam)p(spam}{p(message|spam)p(spam) + p(message|ham)p(ham)}$

So, the question here is, how do you calculate the probabilities for the entire message instead of for a single word? The answer turns out to be to multiply the probability for each of the words together - so p('secret is secret'| spam) is the product p('secret'|spam) x p('is'|spam) x p('secret'|spam)

In [43]:
$p(spam|sis) = \frac{p(s|spam)p(i|spam)p(s|spam)p(spam)}{p(s|spam)p(i|spam)p(s|spam)p(spam) + p(s|ham)p(i|ham)p(s|ham)p(ham)}$
$p(spam|sis) = \frac{p(s|spam)p(i|spam)p(s|spam)p(spam)}{p(s|spam)p(i|spam)p(s|spam)p(spam) + p(s|ham)p(i|ham)p(s|ham)p(ham)}$

Where s = 'secret', i = 'is' and sis='secret is secret'.

In [44]:
p_is_given_spam = p_word(spam_bag, 'is')
assert_equal(p_is_given_spam, detector.spam.p_word('is'), 'p(is|spam)')
p_is_given_ham = p_word(ham_bag, 'is')
assert_equal(p_is_given_ham, detector.ham.p_word('is'), 'p(is|ham)')
In [45]:
def p_message_given_class(message, bag, class_probability, k=0, sample_space=12):
     - `message`: string of words
     - `bag`: bag of words
     - `class_probability`: probability for this class (e.g. p(spam))
     - `k`: Laplace smoothing constant
     - `sample_space`: Size of the vocabulary
    :return: p(message|classification) * p(classification)
    probabilities = (p_word(bag, word, k=k, sample_space=sample_space) for word in message.split())
    probability = class_probability
    for p in probabilities:
        probability *= p
    return probability
In [46]:
def p_spam_given_message(message, k=0, sample_space=12):
     - `message`: string of words
     - `k`: Laplace Smoothing constant
     - `sample_space`: total count of words in spam/ham bags
    :return: probability message is spam
    spam_probability = p_spam if k == 0 else lp_spam
    ham_probability = p_ham if k == 0 else lp_ham
    p_m_given_spam = p_message_given_class(message, spam_bag, spam_probability, k=k, sample_space=sample_space)
    p_m_given_ham = p_message_given_class(message, ham_bag, ham_probability, k=k, sample_space=sample_space)
    return p_m_given_spam/(p_m_given_spam + p_m_given_ham)
In [47]:
message = 'secret is secret'
expected = Fraction(25, 26)
p_sis_given_spam = (p_secret_given_spam * p_is_given_spam * p_secret_given_spam
                    * p_spam)
assert p_message_given_class(message, spam_bag, p_spam) == p_sis_given_spam
assert_equal(p_sis_given_spam, detector.spam.p_message(message), 'p(sis|spam)')

p_sis_given_ham = p_secret_given_ham * p_is_given_ham * p_secret_given_ham * p_ham
assert p_message_given_class(message, ham_bag, p_ham) == p_sis_given_ham
assert_equal(p_sis_given_ham, detector.ham.p_message(message), 'p(sis|ham)')

p_spam_given_sis = p_sis_given_spam / (p_sis_given_spam + p_sis_given_ham)
assert_equal(p_spam_given_sis, detector.p_spam_given_message(message), 'p(spam|sis)')
assert p_spam_given_message(message) == p_spam_given_sis
assert p_spam_given_sis == expected

What is the probability that "today is secret" is spam?

In [48]:
$p(spam|tis) = \frac{p(t|spam)p(i|spam)p(s|spam)p(spam)}{p(t|spam)p(i|spam)p(s|spam)p(spam) + p(t|ham)p(i|ham)p(s|ham)p(ham)}$
$p(spam|tis) = \frac{p(t|spam)p(i|spam)p(s|spam)p(spam)}{p(t|spam)p(i|spam)p(s|spam)p(spam) + p(t|ham)p(i|ham)p(s|ham)p(ham)}$
In [49]:
tis = 'today is secret'
p_spam_given_tis = p_spam_given_message(tis)
assert p_spam_given_tis == 0
assert_equal(p_spam_given_tis, detector.p_spam_given_message(tis),
In [50]:
'today' in spam_bag

Since one of the words isn't in the spam bag of words, the numerator is going to be 0 (p('today'|spam) = 0) so the probability overall is 0.

Laplace Smoothing

When a single missing word drops the probability to 0, this means your model is overfitting the data. To get around this Laplace Smoothing is used.

In [51]:
$p(s) = \frac{s_{count} + k}{total_{count} + k * |classes|}$
$p(s) = \frac{s_{count} + k}{total_{count} + k * |classes|}$

let k = 1.

What is the probability that a message is spam if you have 1 example message and it's spam?

In [52]:
def l_probability(class_count, total_count, k=1, classes=2):
     - `class_count`: size of event space
     - `total_count`: size of sample space
     - `k`: constant to prevent 0 probability
     - `classes`: total number of events
    :return: probability of class_count with Laplace Smoothing
    return Fraction(class_count + k, total_count + classes * k)
In [53]:
k = 1
# classes = spam, ham
number_of_classes = 2
In [54]:
messages = 1
spam_messages = 1
actual = Fraction(spam_messages + k, messages + number_of_classes * k)
assert actual == Fraction(2, 3)

What if you have 10 messages and 6 are spam?

In [55]:
messages, spam_messages = 10, 6
actual = l_probability(spam_messages, messages, k, number_of_classes)
expected = Fraction(spam_messages + k, messages + number_of_classes * k)
assert actual == expected

What if you have 100 messages and 60 are spam?

In [56]:
messages, spam_messages = 100, 60
print(l_probability(spam_messages, messages, k, number_of_classes))

spam/ham with Laplace Smoothing

What are the probabilities that a message is spam or ham with k=1?

In [57]:
lp_spam = l_probability(total_count=mail_count, class_count=len(spam))
assert_equal(lp_spam, l_detector.spam.probability, 'p(spam)')
lp_ham = l_probability(total_count=mail_count, class_count=len(ham))
assert_equal(lp_ham, l_detector.ham.probability, 'p(ham)')

What are p('today'|spam) and p('today'|ham)?

In this case the class-count isn't 2 (for spam or ham) but 12, for the total number of words in the vocabulary.

In [58]:
print(p_word(spam_bag, 'today', k=1, sample_space=vocabulary))
In [59]:
lp_today_given_spam = l_probability(total_count=len(spam_bag),
                                    class_count=word_count(spam_bag, 'today'),
assert_equal(lp_today_given_spam, l_detector.spam.p_word('today'), 'p(today|spam)')
lp_today_given_ham = l_probability(total_count=len(ham_bag),
                                   class_count=word_count(ham_bag, 'today'),
assert_equal(lp_today_given_ham, l_detector.ham.p_word('today'),
assert lp_today_given_spam == Fraction(1, 21)
assert lp_today_given_ham == Fraction(1, 9)
print('p(today|spam) = {0}'.format(lp_today_given_spam))
print('p(today|ham) = {0}'.format(lp_today_given_ham))
p(today|spam) = 1/21
p(today|ham) = 1/9

What is p(spam|m) if m = 'today is secret' and k=1?

In [60]:
tis = 'today is secret'
lp_is_given_spam = p_word(spam_bag, 'is', k=1, sample_space=vocabulary)
assert_equal(lp_is_given_spam, l_detector.spam.p_word('is'), 'p(is|spam)')

lp_is_given_ham = p_word(ham_bag, 'is', k=1, sample_space=vocabulary)
assert_equal(lp_is_given_ham, l_detector.ham.p_word('is'), 'p(is|ham)')

lp_secret_given_spam = p_word(spam_bag, 'secret', k=1, sample_space=vocabulary)
assert_equal(lp_secret_given_spam, l_detector.spam.p_word('secret'), 'p(secret|spam)')

lp_secret_given_ham = p_word(ham_bag, 'secret', k=1, sample_space=vocabulary)
assert_equal(lp_secret_given_ham, l_detector.ham.p_word('secret'), 'p(secret|ham)')

lp_tis_given_spam = lp_today_given_spam * lp_is_given_spam * lp_secret_given_spam * lp_spam
lp_tis_given_ham =  lp_today_given_ham * lp_is_given_ham * lp_secret_given_ham * lp_ham
lp_spam_given_tis = Fraction(lp_tis_given_spam, lp_tis_given_spam + lp_tis_given_ham)

assert_equal(lp_tis_given_spam, l_detector.spam.p_message(tis), 'p(tis|spam)')
assert_equal(lp_tis_given_ham, l_detector.ham.p_message(tis), 'p(tis|ham)')
assert_equal(lp_spam_given_tis, l_detector.p_spam_given_message(tis), 'p(spam|tis)')

This is just more double-checking to make sure that the functions I originally wrote match the hand-calculated answers.

In [61]:
actual = p_message_given_class(tis, ham_bag, lp_ham, k=1, sample_space=vocabulary)
assert lp_tis_given_ham == actual, "Expected: {0} Actual: {1}".format(lp_tis_given_ham, actual)
In [62]:
actual = p_spam_given_message(message=tis, k=1, sample_space=vocabulary)
assert lp_spam_given_tis == actual , "Expected: {0} Actual: {1}".format(lp_spam_given_tis, actual)


Since the code ended up being so messy I'm going to re-do the last example using the class-based version only.

In [64]:
spam_detector = SpamDetector(spam=spam, ham=ham, k=1)
message = 'today is secret'
answer = spam_detector.p_spam_given_message(message)
print("p(spam|'today is secret') = {0}".format(answer))
p(spam|'today is secret') = 324/667
In [65]:
assert_equal(lp_spam_given_tis, answer, "p(spam|'today is secret')")