A new method of parameter estimation for multinomial naive bayes text classifiers

Sang-Bum Kim, Hae-Chang Rim, Heui-Seok LimSIGIR 2002 · DOI

Sure, here's a blog-style summary of the paper "A New Method of Parameter Estimation for Multinomial Naive Bayes Text Classifiers":

TL;DR

This paper introduces a "topic document model" to improve parameter estimation in Naive Bayes text classifiers. By considering document boundaries, their method better estimates term probabilities, leading to significant performance gains, especially for rare categories and with limited training data.

What Problem Does This Paper Address?

Naive Bayes classifiers are popular for text classification due to their simplicity. However, a common approach, the "topic unigram language model," can lead to inaccurate probability estimates. This happens because it treats all training documents equally, averaging term occurrences without accounting for document length or structure. This can be problematic, especially when short documents, which might contain more "essential" terms, are diluted by longer documents with more noise. The paper aims to address this by proposing a method that gives more weight to terms in shorter documents, reflecting their potential importance in representing a topic.

Methods

The core contribution is the "topic document model" approach. Unlike the traditional "topic unigram language model" which estimates $P(w_k|C_j)$ (the probability of term $w_k$ given class $C_j$) by averaging over all tokens in documents of class $C_j$, the new model estimates this probability by averaging over the documents themselves. Specifically, it calculates the expectation of term occurrences within documents belonging to a class.

The formula for the new model is:

$P(w_k \in d_i | Topic(d_i) = c_j) = \sum_{x=1}^{N_{c_j}} P(w_k \in d_x) P(d_x | c_j)$

where $P(d_x | c_j)$ is the prior probability of document $d_x$ belonging to class $c_j$. The paper assumes this prior is uniform for simplicity, effectively averaging the term probabilities across documents.

To estimate $P(w_k \in d_x)$, they use a smoothed term frequency:

$P(w_k \in d_x) = \frac{\theta + TF_{kx}}{\theta |V| + length(d_x)}$

where $TF_{kx}$ is the term frequency of $w_k$ in document $d_x$, $|V|$ is the vocabulary size, and $length(d_x)$ is the number of tokens in $d_x$. Additive smoothing with $\theta = 0.0001$ is used to avoid zero probabilities.

Datasets

The authors evaluated their approach on two standard benchmark collections:

  • Reuters 21578: Used for evaluating performance on 10 major categories and all 90 categories.
  • 20 Newsgroup collection: Used for evaluating accuracy.

For the 20 Newsgroup collection, 2/3 of the data was used for training and 1/3 for testing. The "ModApte" split was used for Reuters 21578.

Key Insights and Ideas

  • Document boundaries matter: The traditional approach of averaging over all tokens can obscure the importance of terms in shorter documents.
  • Short documents can be more informative: The intuition is that shorter documents often contain more "essential" terms for representing a topic, while longer documents might have more noise.
  • Improved performance on rare categories: The new model shows significant gains for categories with fewer training documents, a known weakness of traditional Naive Bayes.
  • Faster convergence: The topic document model achieves competitive performance with fewer training documents compared to the traditional approach.

Key Results

  • Reuters 21578: A 7.9% performance improvement was observed for the 90 categories when using the topic document model (TDM) compared to the topic unigram language model (TLM). For the 10 major categories, the improvement was less significant.
  • 20 Newsgroup collection: TDM achieved a 6.94% improvement in accuracy over TLM.
  • Training data efficiency: TDM achieved top performance with approximately 3,000 training documents on the 20 Newsgroup collection, whereas the traditional approach required more.

Limitations and Future Work

  • Limitations: The paper assumes a uniform prior probability for documents belonging to a class ($P(d_x|c_j)$). This simplification might not hold in all scenarios. The paper also mentions substituting average document length for missing terms for efficiency, which could introduce approximation errors.
  • Future Work: The authors plan to further formalize their framework and extend the model to probabilistic Information Retrieval (IR) models.

Summary updated

BibTeX
@inproceedings{kim2002new,
  author = {Sang-Bum Kim and Hae-Chang Rim and Heui-Seok Lim},
  title = {{A new method of parameter estimation for multinomial naive bayes text classifiers}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2002},
  doi = {10.1145/564376.564459},
}
Figure