Overfitting Naive Bayes

Question

My question is what are potential reasons for Naive Bayes to perform well on a train set but poorly on a test set?

I am working with a variation of the 20news dataset. The dataset has documents, which are represented as "bag of words" with no metadata. My goal is to classify each document into 1 of 20 labels. My error rate on training data is 20%, but my error rate on test data is 90% (for comparison, guessing yields 95% error rate). For some reason, my classifier is predicting class 16 for almost all documents in test set. In train set this problem does not occur. Furthermore, this issue persists with different train/test splits. I'm trying to figure out what I'm doing wrong.

Here are some things I've considered:

• Is Naive Bayes overfitting to the training set? If Naive Bayes is implemented correctly, I don't think it should be overfitting like this on a task that it's considered appropriate for (text classification).
• Is my train/test split bad? I've tried splitting the data in different ways, but it does not seem to make a difference. Right now I'm splitting the data by placing a random 90% sample of documents into the train set and the rest into the test set - separately for each label.
• Problems with numerical accuracy? I've implemented the calculations in log probabilities, but in any case, I would expect that problem to manifest in train set as well.
• Problems with unseen words? The fraction of unseen words relative to a particular newsgroup is the same, 20%, for both train and test sets.
• Problems with Laplace smoothing? I wasn't sure what was the appropriate way to implement Laplace smoothing for this task, so I tried a variety of ways. To my surprise they all yielded very similar results.
• Imbalanced dataset? Doesn't look like it. There are approximately as many unique words inside documents of label 16 as there are in other classes. Also the number of documents per each label is roughly even.

Edit: Turns out I had an implementation bug. I won't detail it here as it will be unlikely to help anyone with similar issues.

Answer 1

Let me try to answer your questions point by point. Perhaps you already solved your problem, but your questions are interesting and so perhaps other people can benefit from this discussion.

• Is Naive Bayes overfitting to the training set? If Naive Bayes is implemented correctly, I don't think it should be overfitting like this on a task that it's considered appropriate for (text classification).

Naive Bayes has shown to perform well on document classification, but that doesn't mean that it cannot overfit data. There is a difference between the task, document classification, and the data. Overfitting can happen even if Naive Bayes is implemented properly.

• Is my train/test split bad? I've tried splitting the data in different ways, but it does not seem to make a difference. Right now I'm splitting the data by placing a random 90% sample of documents into the train set and the rest into the test set - separately for each label.

It's good that you're keeping the class distribution the same in your training and test set. Are you using cross-validation? Perhaps try it because, even though it's rare, it might happen that you just get unlucky with your splitting due to some seed.

• Problems with numerical accuracy? I've implemented the calculations in log probabilities, but in any case, I would expect that problem to manifest in train set as well.

You're correct, if it was an issue, it would show in the training set as well.

• Problems with unseen words? The fraction of unseen words relative to a particular newsgroup is the same, 20%, for both train and test sets.

This doesn't seem to be the issue then. You could perhaps reduce that percentage by using stemming or lemmatization.

• Problems with Laplace smoothing? I wasn't sure what was the appropriate way to implement Laplace smoothing for this task, so I tried a variety of ways. To my surprise they all yielded very similar results.

Laplace smoothing is useful especially when you do not have a lot of data and you need to account for some uncertainty. For this dataset, this doesn't seem to be an issue, as shown by the similar results you've experienced.

• Imbalanced dataset? Doesn't look like it. There are approximately as many unique words inside documents of label 16 as there are in other classes. Also the number of documents per each label is roughly even.

Are the documents of the same lengths? Because perhaps label 16 simply contains documents that are larger and therefore have bigger word frequencies. They might also contain very common words. It would be interesting to look at a histogram of the words in each class. This could be very informative in understanding whether label 16 is very different from the others.

Answer 2

Text mining is rather a tricky field of machine learning application, since all you've got is "unstructured and semi structured data" and the preprocessing and feature extraction step matters a lot. The text mining handbook is a priceless reference in this area of research. but to be specific about your case, I can suggest two answers:

• as noted, preprocessing step plays a very important role here. in text mining it is likely to get trapped inside the curse of dimensionality, since you probably have say around 1000 documents but more than 15000 unique words in a dataset. techniques such as stemming and lemmatizing, static and dynamic stopword and punctuation erasing all aim solving this issue. So preprocessing and feature extraction is not an option. it is a MUST

• Naive Bayes model is a linear classifier. Even though it is a very popular algorithm in text classification, there are still risks of rising such problems as yours. the main reason could be that your word-space matrix is highly sparse. you must have paid attention to the fact that in calculating the posterior probability of belonging to a class, Naive Bayes, naively multiplies all single probabilities of P(y|x_i). and if there is at least one zero probability, your final answer would be zero, no matter what other inverse observation probabilities are. If you have implemented the algorithm yourself, try already-constructed tools in MATLAB, Python sci-kit learn library, or data mining softwares like KNIME and RapidMiner. they have delicately handled such practical issues in implementing Naive Bayes algorithm.

Answer 3

Unless you're doing it on some other related file, you're not removing stopwords. If label 16 makes a great use of such, that's a plausible explanation for such result.

On the other hand (unless again, you're doing it on some other file) you're not reducing words to their morphemes. Not doing so might cause these kind of anomalies. Check the Nltk documentation to learn how to do such thing.