Sparse representations for text categorization

Tara N. Sainath, Sameer R. Maskey, Dimitri Kanevsky, Bhuvana Ramabhadran, David Nahamoo, Julia HirschbergInterspeech 2010

TL;DR

This paper introduces Sparse Representations (SRs) as a novel approach for text categorization, demonstrating promising results that slightly outperform the standard Naive Bayes classifier. By leveraging the idea of representing text documents as sparse linear combinations of training examples, the authors show SRs can adaptively select relevant training data, offering a new avenue for text classification research.

What Problem Does This Paper Address?

Text categorization, the task of assigning documents to predefined categories, is a fundamental problem in Natural Language Processing with applications ranging from spam filtering to topic modeling. While many sophisticated classification methods exist (e.g., SVMs, decision trees, neural networks), the authors explore a less-trodden path by adapting Sparse Representations (SRs), a technique successful in image and phonetic classification, to the domain of text. The core challenge is to find effective ways to represent text data and build classifiers that are both accurate and efficient, especially when dealing with large vocabularies and potentially noisy data.

Methods

The paper proposes using Sparse Representations (SRs) for text classification. The core idea is to represent a test document vector y as a linear combination of training document vectors, forming a dictionary H. This dictionary H is constructed from all training documents, making it an over-complete dictionary (more training examples than feature dimensions). The key is to find a sparse coefficient vector β such that y ≈ Hβ. This sparsity is enforced to select only a few relevant training examples that best represent the test document.

The authors explore three different classification rules based on the resulting sparse coefficient vector β:

  1. Maximum Support: Assigns the class with the largest individual β coefficient.
  2. Maximum L2 Support: Assigns the class with the largest L2 norm of β coefficients belonging to that class.
  3. Minimum Residual Error: Assigns the class that minimizes the difference between the test document y and its reconstruction using the corresponding training examples from H.

For solving the sparse representation problem (y = Hβ), they use the Approximate Bayesian Compressive Sensing (ABCS) method, which combines L1 and L2 norms on β.

As a baseline, they also implement and evaluate the standard Naive Bayes (NB) classifier, a probabilistic method that assumes conditional independence between words given a class.

Datasets

The experiments are conducted on the 20 Newsgroup Corpus. This corpus contains approximately 18,000 newsgroup documents divided into 20 different classes. For their experiments, 60% of the documents (around 11,314) were used for training, and the remaining 40% (around 7,532) were used as the held-out test set.

Key Insights and Ideas

  • SRs for Text: A Promising New Frontier: The paper successfully adapts SRs, a technique proven in other domains, to text classification, opening up a new research direction.
  • Adaptive Feature Selection: SRs inherently select a small subset of relevant training examples to represent a test document. This adaptive nature is a key advantage, potentially leading to more robust and interpretable models compared to methods that use all training data or fixed feature sets.
  • Sparsity Matters: Enforcing sparsity on the coefficient vector β provides a small but statistically significant improvement in classification accuracy over a non-sparse solution. This suggests that focusing on a few "good" training examples is beneficial.
  • Classification Rule Sensitivity: The choice of classification rule significantly impacts SR performance. The "Maximum L2 Support" rule emerged as the most effective among the tested SR-specific rules, offering better accuracy than "Maximum Support" and "Minimum Residual Error."
  • Vocabulary Size Trade-off: Like many text classification methods, SR performance improves with larger vocabulary sizes up to a point. However, beyond a certain threshold (where vocabulary size approaches the number of training documents), SR accuracy begins to degrade because the over-complete dictionary assumption is violated, limiting the degrees of freedom for finding sparse solutions.

Key Results

  • SRs Outperform Naive Bayes (Slightly): Across various vocabulary sizes, the proposed SR method achieved slightly higher accuracy than the Naive Bayes classifier. For instance, with a vocabulary size of 6,215, SR achieved 78.8% accuracy compared to NB's 77.9%.
  • Sparsity Improves Accuracy: Enforcing sparsity on β yielded a small accuracy improvement (78.8% vs. 78.6%) compared to a non-sparse solution for a vocabulary size of 6,215.
  • L2 Support is Best SR Metric: The "Maximum L2 Support" rule achieved the highest accuracy (78.8%) among the SR classification rules tested, outperforming "Maximum Support" (77.2%) and "Minimum Residual Error" (55.5%) for a vocabulary size of 6,215.
  • Accuracy Increases with Vocabulary Size (Initially): Both NB and SR accuracies generally increased as vocabulary size grew from 1,000 to 8,000. SR showed a 0.3-0.8% absolute improvement over NB in this range.
  • Degradation at High Vocabulary Sizes: Beyond a vocabulary size of 8,000, SR accuracy started to drop, approaching NB's performance, due to the violation of the m << N assumption.

Limitations and Future Work

  • Slight Improvement Over NB: While promising, the SR method's improvement over Naive Bayes is modest. The authors acknowledge that their current SR method may not yet outperform state-of-the-art text classification techniques.
  • Feature Selection: The current SR approach uses raw term frequencies as features and does not incorporate advanced feature selection techniques. The authors suggest that future work could explore using SRs with better feature selection methods.
  • Comparison to SVMs: The paper plans to compare SR results to SVMs in future work, similar to their previous research in phonetic classification.
  • Vocabulary Size Limit: The SR method's effectiveness is limited when the vocabulary size (m) approaches or exceeds the number of training documents (N). Future research could investigate ways to mitigate this limitation.

Summary updated

BibTeX
@inproceedings{sainath2010sparse,
  author = {Tara N. Sainath and Sameer R. Maskey and Dimitri Kanevsky and Bhuvana Ramabhadran and David Nahamoo and Julia Hirschberg},
  title = {{Sparse representations for text categorization}},
  booktitle = {Interspeech},
  year = {2010},
}
Figure