We can use the Law of Total probability with Bayes rule (see slide) to work out the posterior probabilities of a set of hypotheses $H_1, \dots, H_n$, where these hypotheses are disjoint (cannot co-occur) and are collectively exhaustive.

For more details, see the lecture notes.

Let the prior probabilities of our two hypotheses be $P(H_1) = 0.5$, $P(H_2) = 0.5$. Further, let

1. Find \( P(H_1 \mid E) \) and $P(H_2 \mid E)$

   Show Answer

   \[ P(E \mid H_1) \times P(H_1) = 0.8 \times 0.5 = 0.4 \]

   \[ P(E \mid H_2) \times P(H_2) = 0.2 \times 0.5 = 0.1 \]

   \[ P(H_1 \mid E) = \frac{0.4}{0.4 + 0.1} = 0.8 \]

   \[ P(H_2 \mid E) = \frac{0.1}{0.4 + 0.1} = 0.2 \]

Our goal here is to create a (very) simple machine learning algorithm for identifying strings matching a given statistical pattern. This is a kind of classification task. We want to classify whether a string that we have never seen before is similar to our training set. This could be used for spam detection (do the messages match the patterns of spam messages). Here we are going to try detecting whether a string is likely to be an English word.

To simplify matters for now, we will work only with messages made of the letters A, B, C, and D. We will assume that every message is four letters long. This keeps the process tractable to work out by hand. However, the interactive demos allow you to have a longer alphabet, and to use large training sets. Use these demos to see how the same approach scales to a real-world use case.

We have a collection of strings that we want to learn from. These might represent spam messages, or English words, or whatever it is we are modelling. This is the training data that we want to use to parametrise or models.

CABA CBCB CACB CBCC

We have no training data for non-target strings (e.g. non-spam messages). For simplicity, we will assume that we have no knowledge about these strings, and thus that, as far as we know, they are generated completely at random. We could easily extend the approach here to incorporate more sophisticated models of non-target strings if we wanted to.

The basic idea is that we will devise a model that describes a mechanism for how strings are generated. This model will depend on several probabilities. We can work out these probabilities from frequencies in our training dataset.

We are trying to classify strings as either English or not English. We will describe two models, $M_1$, a model that generates 'English' (in inverted commas), and $R_1$, a model that generates random messages. On the assumption that only these two models could have been used, we will then work out the probability that a given message was generated by $M_1$ and not $R_1$.

Let us say that strings are generated by a weighted random choice for each successive letter. In other words, for each character in the string, a random letter is picked. Each letter has a probability of being selected that is independent of where that letter occurs, or of any other character.

If we know nothing about the distribution of letters, we start with the assumption that any letter is as likely as any other. This will be our modelling assumption for when words are not 'English', giving us the model $R_1$.

By looking at our training data, we can pick probabilities based on the frequencies with which letters appear.

We have now parametrised our model $M_1$ with probabilities based on our training data. We can now use $M_1$ to generate a random 'English' word. Remember, our model says that each letter is chosen independently based on the probability of selecting each letter. Note that how realistic this generated word is (how much it looks to us like 'English') will be limited by the simplistic modelling assumptions we have made.

We can also use our parametrised model $M_1$ to determine the probability that a given word is 'English'. The basic idea is to see how likely model $M_1$ is to generate a given word and compare that to the probability of getting that word using model $R_1$.

For example, if we have a four letter word CBCB, we can work out the probability of generating this word based on model $M_1$ as

Now we have $P(CBCB \mid M)$, which tells us how likely it is that M generates CBCB. However, what we want is $P(M \mid CBCB)$. In other words, how likely is it that the model used was M if the string observed was CBCB? We can use Bayes rule to find this.

$P(M_1)$ is the prior probability that model M was used. In other words, it's our initial expectation of the likelihood that the message is 'English'. We might know or guess that 50% of messages are 'English'. In this example, our prior probability would be set to $P(M_1) = 0.5$.

To use Bayes' rule, we need to work out $P(CBCB)$, the probability of generating CBCB. We know the probability for generating this given model $M_1$. We need to consider the possibility that the message is not 'English'.

One of our modelling assumptions is that strings are either generated by R_1 (they are random), or they are generated by $M_1$ (they are 'English').

We can work out the probability of generating this word if letters were random (model $R_1$) as

As $R_1$ and $M_1$ are the only possibilities (given on our modelling assumptions), they form a partition. Thus we can use the Law of Total Probability:

This gives us everything we need to calculate $P(M \mid CBCB)$.

To improve on this, we might recognise that different letters are more or less likely to appear in different positions.

Let $P(A_n)$ be the probability of letter $A$ appearing at position $n$. Initially, we might assume that the likelihood of any given letter in a given position is equally likely. If we have four letters, these would each be $0.25$.

Now, as above, we can use our new model, $M_2$, to generate 'English' words.

As above, we can work out the probability that the string CBCB is generated based on the assumption that model $M_2$ is used

We can also work out the probability that the string CBCB is generated based on the assumption that messages are generated at random. Let us call this model $R_2$.

In our second attempt, we are assuming that the messages we are classifying were either generated by $M_2$ or by $R_2$. As above we can use the Law of Total Probability and Bayes rule to work out $P(M_2 \mid CBCB)$.

Now we might consider that different letters are more or less likely depending on the letter that appear in front of them.

We need to find the probabilities of the letters appearing in the first position: \( P(A_1), P(B_1), \dots \). And we need to find a conditional probabilities of each letter occurring in position $n$ for every letter that could have occurred in position $n-1$. This can be represented in a probability tree. As each letter depends only on the previous letter, a better representation is as a Markov Chain.

Using this diagram, we can generate a random 'English' word by randomly walking down the probability tree or Markov chain according to the transition probabilities.

Now we can also calculate the probability of generating the string CBCB assuming model $M_3$ is used: $P(CBCB \mid M_3)$. We can also calculate the probability assuming strings are randomly generated: $P(CBCB \mid R_3)$. From here we can calculate $P(M_3 \mid CBCB)$

Next, we might reason that it doesn't matter where a pair of letters appears. We might want to learn a model $M_4$ defined by the probabilities of transitioning between each pair of letters.

We construct a Markov Model with a node for each letter and a edge between each pair of letters. The probabilities labeling these edges can be found from frequencies with with certain pairs of letters appear in the dataset.

From here, the same process can be followed as with the previous modelling attempts to work out $P(CBCB \mid M_4)$.