Probabilistic inference

Reasoning under Uncertainty

In this section, we'll study methods that can cope with uncertainty. The history of AI has seen various competing approaches to handling uncertain and imprecise information: fuzzy logic, non-monotonic logic, the theory of plausible reasoning et cetera. In most cases, probability theory has turned out to be the most principled and consistent paradigm for reasoning under uncertainty.

If you want an objective and diplomatic view on the matter, don't ask me. I'll just repeat a counter-argument made by a proponent of fuzzy logic when he tried to get around a rigorous formal proof showing that any method of inference where degrees of plausibility are represented as real numbers, other than probability theory, is inconsistent: the response of the fuzzy logic proponent was that since the proof is based on ordinary (two-valued) logic, it doesn't apply to fuzzy logic. Now that is a counter-argument that is hard to refute!

Probability Fundamentals

We are working to add material about the basic concepts of probability theory: probabilistic model, events, joint probability, conditional probability, etc.

Since this section is not finished yet, feel free to refresh these concepts from your favorite source. Two great examples are:

• Ian Goodfellow, Yoshua Bengio & Aaron Courville: Deep Learning (Section 3)
• Larry Wasserman: All of Statistics (Part I, Probability is great)

• Wikipedia: Bayes theorem (Section Drug testing)
• Youtube: Maths Doctor, A Level Statistics 1.5 Bayes' Theorem and medical testing
• Better Explained: Understanding Bayes Theorem with Ratios

Probabilistic Inference

Now that the probability basics are in place, we will see how they are used for inference in AI problems.

Bayes rule and probabilistic inference

Bayes rule has a central role in statistical inference and machine learning. The basis for this is that it can be applied in scenarios where one of the random variables in the model corresponds to an unknown "state" which we are interested to learn. If the model includes other variables that correspond to "observations" that can be made and that are dependent on the unknown state, we can use the Bayes rule as follows

The left side of the equation is called the posterior probability (probability after the observation). The first factor on the right is called the prior probability (probability prior to the observation), the middle factor is called the likelihood (how likely the observation is when the state is given), and the last term on the right has many names, of which the annoying denominator may be the most fitting. (Evidence and marginal likelihood are more common.)

     R = P(State=1 | obs) / P(State=2 | obs)

     P(State=1) P(obs | State=1) / P(obs)   P(State=1) P(obs | State=1)
R =  ------------------------------------ = ---------------------------
     P(State=2) P(obs | State=2) / P(obs)   P(State=2) P(obs | State=2)

  P(State=1 | obs) = R / (1+R)

Naive Bayes classification

One of the most useful applications of the Bayes rule is the so called naive Bayes classifier. It is a machine learning technique that can be used to classify objects such as text documents into two or more classes. The classifier is trained by analysing a set of training data, for which the correct classes are given.

The naive Bayes model is a probabilistic model that involves a class variable -- this corresponds to the state variable above -- and a number of feature variables. The assumption in the model is that the feature variables are conditionally independent given the class. (We will not discuss the exact meaning of conditional independence on this course. You can find more about it from the literature. For our purposes, it is enough to be able to exploit conditional independence in building the classifier.)

We will use a spam email filter as a running example for illustrating the idea of the naive Bayes classifier. Thus, the class variable indicates whether a message is spam (or "junk email") or whether it is a legitimate message (also called "ham"). The words in the message correspond to the feature variables, so that the number of feature variables in the model is determined by the length of the message.

The naive Bayes model can be represented as a Bayesian network, which encodes the conditional independence between the feature variables (in this case, the words of the email message) given the class variable as in the above diagram. We'll return to Bayesian networks in Week 3.

Estimating parameters

To define the naive Bayes model, we need to specify the distribution of each variable. For the class variable, this is the distribution of spam vs ham messages, which we can for simplicity assume to be 1:1, i.e., P(spam) = P(ham) = 0.5.

For the feature variables, we will define two distributions: one for the spam messages and another one for the ham messages. In each case, we will make the simplifying assumption that each of the words in the message is distributed according to the same distribution. And as we said above, we also assume that the words are independent of each other given the spam/ham class.

The word distributions for the two classes are best estimated from actual training data, i.e., a corpus of spam messages and a corpus of legitimate messages. The simplest way is to count how many times each word, aardvark, aardwolf, ..., Zyzzogeton, appears in the corpus and dividing the number by the total number of words in the corpus.

To illustrate the idea, let's assume that we have at our disposal both a spam corpus and a ham corpus. You can easily obtain one by saving a batch of your emails in two files.

Assume that we have calculated the number of occurrences of the following words in the two classes of messages:

        word    spam     ham
 ----------- ------- -------
 million         156      98
 dollars          29     119
 adclick          51       0
 conferences       0      12
 ----------- ------- -------
       total   95791  306438

We can now estimate that the probability that a word in a spam message is million, for example, is about 156/95791 ≈ 0.0016285. In other words, on the average, roughly every 614th word in a spam message is million. Likewise, we get the estimate 0.0003198 for the probability that a word in a ham message is million. Both of these probability estimates are small but more importantly, the former is higher than the latter. This turns out to be a sign that the word in question hints towards the message being spam -- which sounds logical. Words for which the ratio of the probabilities is the other way around, hint towards the message being ham.

Classifying new data

After the parameters of the model have been estimated, the classifier is ready for use! When we are given a new message, we will compute the posterior probability P(spam | message), where message is a place-holder for the words in the message, for example, P(spam | 'million', 'conferences') (which would be a really short message).

Let's compute the posterior probability

     P(spam | Word1 = 'million', Word2 = 'conferences')

which is abbreviated without a great risk of confusion -- but please note that unlike million and conferences, which are hyphenated ('like this') to indicate that they are words that occur in the message, the term spam indicates the class of the message, not the word "spam" -- as

     P(spam | 'million', 'conferences')

By Bayes rule, we have

                                      P(spam) P('million', 'conferences' | spam)
 P(spam | 'million', 'conferences') = ------------------------------------------
                                            P('million', 'conferences')

The numerator on the right side is the likelihood term and its meaning is the probability that the first two words are million and conferences given that the message is spam. The denominator on the right side -- it's the annoying one -- is the probability that the first two words are as stated when the spam/ham status of the message is not given.

Let's look at the likelihood term first. The conditional independence assumption, i.e., the naive Bayes assumption, implies that the likelihood can be "factorized" as follows

  P('million', 'conferences' | spam) = P('million' | spam) P('conferences' | spam)

This is very useful since these are the kind of probabilities we have estimated from the data. The same factorization rule can be applied no matter how many words there are in the message.

Next up is the annoying denominator. However, we'll use the hint above and avoid calculating the denominator (at least explicitly). To achieve this, we consider the ratio of posteriors:

 P(spam | 'million', 'conferences')   P(spam) P('million', 'conferences' | spam) / Z
 ---------------------------------- = ----------------------------------------------
  P(ham | 'million', 'conferences')    P(ham) P('million', 'conferences' | ham) / Z

where Z, defined as Z = P('million', 'conferences'), is the annoying denominator which cancels out just as promised in the hint.

The term P('million', 'conferences' | ham) is treated in the exact same manner as the term corresponding term for spam (see above), and the numbers required to calculate its value are available since we have estimated them from the training data.

The following exercises will demonstrate the use of the naive Bayes model.

Implementation details

The above exercise should make it relatively straightforward to see how the filter can be implemented by programming: the key insight is the routine nature of the word-by-word calculations.

A convenient way to group the computations is obtained by slight reshuffling of the terms. Consider still our example two-word message, and the following formula for the ratio of the posterior probabilities

     P(spam | 'million', 'conferences')
 R = ----------------------------------
      P(ham | 'million', 'conferences')

     P(spam) P('million' | spam) P('conferences' | spam)
   = ---------------------------------------------------
       P(ham) P('million' | ham) P('conferences' | ham)

Since the ratio of products is equal to the product of ratios -- i.e., for example, (ABC)/(DEF) = (A/D)(B/E)(C/F) -- we can group the above terms as

     P(spam)  P('million' | spam)  P('conferences' | spam)
 R = -------  -------------------  -----------------------
     P(ham)   P('million' | ham)   P('conferences' | ham)

More generally, the formula is

       P(spam)  N  P(word_i | spam)
   R = -------  Π  ----------------
       P(ham)  i=1 P(word_i | ham)

where N is the number of words in the message, and word_i is the i'th word in the message.

Intuitively, the above formula encodes the rule that any word whose probability is higher in spam messages than in ham messages will increase the ratio R, and vice versa. For example, in our two-word message, for i=1, we have word_i = 'million', and the ratio of the word probabilities is given by

    P(word_1 | spam)   P('million' | spam)   0.0016285
    ---------------- = ------------------- ≈ --------- ≈ 5.1
    P(word_1 | ham)    P('million' | ham)    0.0003198

Thus, each occurrence of the word 'million' in the message leads to roughly a five-fold increase in the posterior probability ratio.

Putting things together, here's a pseudocode sketch of the classification stage where we assume that the probability estimates have already been calculated from training data.

    spamicity(words, estimates):
1:     R = estimates.prior_spam / estimates.prior_ham
2:     for each w in words:
3:        R = R * estimates.spam_prob(w) / estimates.ham_prob(w)
4:     return R

Here estimates is an object that stores the estimated probabilities: estimates.prior_spam is the probability that a message is spam, P(spam), estimates.prior_ham the same for ham; estimates.spam_prob(w) is the probability P(Word = w | spam), and estimates.ham_prob(w) the same for ham.

                                       N
   logR = log(P(spam)) - log(P(ham)) + Σ [log(P(word_i | spam)) - log(P(word_i | ham))]
                                      i=1

python3 -m testrunner

Here is some additional material on naive Bayes spam filtering that you may like to take a look at:

• Dr Dobbs Journal: Naive Bayesian text classification
• M. Sahami, S. Dumais, D. Heckerman, E. Horvitz (1998). "A Bayesian approach to filtering junk e-mail". AAAI'98 Workshop on Learning for Text Categorization.