Text categorization using Naive Bayes: Why isn't this working?

Question

I'm trying to implement a system for text categorization using Naive Bayes as part of a school project. I have to hand code the algorithm and have been having some issues.

To make sure I understand exactly how Naive Bayes works, I decided to make a very simple example and manually perform Naive Bayes on it to make sure I get the right result.

So suppose there are two categories, DISASTER and POLITICS. There are only two training documents, one labelled DISASTER and one labelled POLITICS. (So the prior probabilities are both 0.5 and can be discarded in the calculations).

There is a single test document which we wish to classify as belonging to either DISASTER or POLITICS.

The documents are all very short, and consist of the following words: TRAINING (DISASTER): disaster disaster disaster disaster clown TRAINING (POLITICS): disaster clown politics politics politics... politics (40 consecutive occurrences of politics)

TEST document: map disaster politics politics politics

Intuition: Since the test document has so many occurrences of politics, I conjecture that it should be classified as POLITICS.

But if I use Naive Bayes', I get the following results (I used a simple smoothing technique, where I assumed that if a word was not seen before, I just gave it a count of 1 instead of 0):

P(test document|category = DISASTER) = (1/5)(4/5)(1/5)(1/5)(1/5) P(test document|category = POLITICS) = (1/42)(1/42)(40/42)(40/42)(40/42)

These calculations show that P(doc|DISASTER)>P(doc|POLITICS) and hence Naive Bayes would classify this test document as belonging to DISASTER, which makes no sense to me. Obviously I have made a mistake somewhere, or am not doing it correctly. What's the issue?

Answer 1

Because of the independence assumption of Naive Bayes as well as the particular nature of your training data set, any word that is not 'politics' heavily penalizes the probability of the document, given that it is about POLITICS. P(doc|POLITICS) is penalized to $1/42 \approx 2\%$ of its value for every additional word that isn't 'politics', while P(doc|DISASTER) is penalized to $1/5 \approx 20\%$ of its value.

So, ignoring the contribution of the feature words, looking at each 'non-feature word' of the corresponding class to get a feel of things, we'd need the following for classification as DISASTER:

$(1/5)^{n_{\text{non-disaster}}}(4/5)^{N-n_{\text{non-disaster}}}<(1/42)^{n_{\text{non-politics}}}(40/42)^{N-n_{\text{non-politics}}}$

The source of your problem is mainly the training corpus. There are too few non-feature words in them and so they gain exaggerated importance.

---

In general, going with your scheme, the classifier would pick:

$$c^\ast = \underset{\max c_i}{\arg\max} \left[ (n_{c_i,\text{train}}/N_{c_i,\text{train}})^{n_{c_i,\text{test}}} (1/N_{c_i,\text{train}})^{N_{\text{test}}-n_{c_i,\text{test}}} \right]$$

in order for your classifier to pick class $i$. Here,

$N_{c_i,\text{train}} \equiv$ total number of words in the training corpus for class $i$

$n_{c_i,\text{train}} \equiv$ total number of feature words in the training corpus for class $i$

$N_{c_i,\text{train}} - n_{c_i,\text{train}}\equiv$ total number of non-feature words in training corpus for class $i$

$n_{c_i,\text{test}} \equiv$ number of feature words of class $i$ in the test data

$N_\text{test} \equiv$ total number of words in the test data

Answer 2

I agree with Salmonstrikes - your data set is too small. However, you have smoothed the data incorrectly.

You have added 1 to the numerator but ignored adding anything to the denominator. You should add 1 to the denominator for each word which is present in the test set but not present in the training document.

Imagine the case where you have a training document of a new classification, let's call it SPORT with just a single word: Golf. Using your training set and your method of smoothing you would assign the probability for each word in the test set as 1/1 - clearly this is incorrect. In this case you should classify each word in the test set as 1/6. Why 1/6? Well, for each word in the test set which is not in the training document you increment the denominator by 1 - as the test set has 5 words (none of which are in the training document) we add 5 to the denominator, the denominator was 1 so it is now 6.

In your example given this would mean:

P(test document|category = DISASTER) = (1/7)(4/7)(1/7)(1/7)(1/7)

P(test document|category = POLITICS) = (1/43)(1/43)(40/43)(40/43)(40/43)

Using this method P(DISASTER|Test Set) = 0.35 and P(POLITICS|Test Set) = 0.65 which is more closely aligned to your intuition.