Machine Learning - Lecture 4: The Naive Bayes Classifier

Machine Learning - Lecture 4: The Naive Bayes Classifier
Let's say we have some data that lists symptoms and ailments for everybody in a certain group.

  SYMPTOM       AILMENT

  sneezing      flu
  sneezing      hayfever
  headache      concussion
  sneezing      flu
  coughing      flu
  backache      none
  vomiting      concussion
  crying        hayfever
  temperature   flu
  drowsiness    concussion

Prediction

There are 10 cases in all so we can work out the probability of seeing a particular ailment or symptom just by counting and dividing by 10.

  P(hayfever) = 2/10 = 0.2

  P(vomiting) = 1/10 = 0.1

As a simple, statistical model of the data, these (so-called prior) probabilities can be used for prediction.

Let's say we're undecided whether someone has flu or hayfever.

We can use the fact that P(flu) > P(hayfever) to predict it's more likely to be flu.

Conditional probabilities

This sort of modeling becomes more useful when conditional probabilities are used.

These are values we work out by looking at the probability of seeing one value given we see another, e.g., the probability of vomiting given concussion.

Conditional probabilites are notated using the bar `|' to separate the conditioned from the conditioning value.

The probability of vomiting given concussion is written

  P(vomiting|concussion)

We can work this value out by seeing what proportion of the cases involving concussion also show vomiting.

  P(vomiting|concussion) = 1/3 = 0.3333

Prediction from conditional probabilities

Conditional probabilities enable conditional predictions.

For example, we could tell someone who's known to have concussion that there's a 1/3 chance of them vomiting.

This can also be a way of generating diagnoses.

If someone reports they've been sneezing a lot, we can say there's a 2/3 chance of them having flu, since

  P(flu|sneezing) = 2/3

The problem of multiple attributes

What happens if the data include more than one symptom?

We might have something like this.


  SYMPTOM       OCCUPATION    AILMENT

  sneezing      nurse         flu
  sneezing      farmer        hayfever
  headache      builder       concussion

We'd like to be able to work out probabilities conditional on multiple symptoms, e.g.,


  P(flu|sneezing,builder)

But if a combination doesn't appear in the data, how do we calculate its conditional probability?




Using inversion

There's no way to sample a probability conditional on a combination that doesn't appear.

But we can work it out by looking at probabilities that do appear.

Observable probabilities that contribute to


  P(flu|sneezing,builder)

are


  P(flu)
  P(sneezing|flu)
  P(builder|flu)

All we need is some way of putting these together.




The naive assumption

Probability theory says that if several factors don't depend on each other in any way, the probability of seeing them together is just the product of their probabilities.

So assuming that sneezing has no impact on whether you're a builder, we can say that


  P(sneezing,builder|flu) = P(sneezing|flu)P(builder|flu)

The probability of a sneezing builder having flu must depend on the chances of this combination of attributes indicating flu. So


  P(flu|sneezing,builder)

must be proportional to


  P(flu)P(sneezing,builder|flu)



Normalization needed

Unfortunately, this value is purely based on cases of flu. It doesn't take into account how common this ailment is.

We need to factor in the probability of this combination of attributes associating with flu in particular, rather than some other ailment.

We do this by expressing the value in proportion to the probability of seeing the combination of attributes.




This gives us the value we want.


Naive Bayes Classifier
A Naive Bayes Classifier is a program which predicts a class value given a set of set of attributes.

For each known class value,



Calculate probabilities for each attribute, conditional on the class value.
Use the product rule to obtain a joint conditional probability for the attributes.
Use Bayes rule to derive conditional probabilities for the class variable.

Once this has been done for all class values, output the class with the highest probability.

The problem of missing combinations
A niggling problem with the NBC is where the dataset doesn't provide one or more of the probabilities we need.

We then get a probability of zero factored into the mix.

This may cause us to divide by zero, or simply make the final value itself zero.

The easiest solution is to ignore zero-valued probabilities altogether if we can.

Summary

Clustering and nearest-neighbour methods ideally suited to numeric data.
Probablistic modeling may be more effective with categorical (symbolic) data.
Probabilities easily derived from datasets.
But for classification, we normally need to invert the conditional probabilities we can sample.
The Naive Bayes Classifier uses Bayes Rule to identify the class with the highest probability.
On average, the NBC seems to be perform better than expected.


Please read full article from Machine Learning - Lecture 4: The Naive Bayes Classifier

Read full article from Machine Learning - Lecture 4: The Naive Bayes Classifier