Overfitting Naive Bayes
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.