Retrieval answers a query that arrives once. Classification answers a question that is asked of every document: is this spam, is this about corporate earnings, how many stars does this review give? The categories are fixed in advance, and the system's job is to assign each new document to the right ones. The rules for doing so could be written by hand, and in some settings still are, but the approach that dominates is supervised learning. A person labels a set of example documents, and an algorithm learns from them a function that labels new documents automatically.
Classification belongs in a retrieval course for several reasons. It is retrieval's twin: a standing query that filters a stream of news is a binary classifier, and a ranking function is a classifier that has not yet chosen a threshold. It shares retrieval's representations. Documents are bags of terms built by the same text processing, weighted by the same statistics. And its first major method, Naive Bayes, rests on the same conditional independence assumption as the Binary Independence Model. The two are close relatives, one estimating the probability of relevance and the other the probability of a class.
This topic develops Naive Bayes in its two forms, shows how to choose which terms a classifier should use, defines how classifiers are evaluated, and compares Naive Bayes with classifiers built on the vector space model. The methods are tested on Reuters-21578, the collection the textbook uses. A final article examines my course project, which used Naive Bayes to predict the star ratings of Goodreads reviews.
Articles
The problem
- The text classification problem: standing queries, hand-written rules versus learning (with a three-word rule that beats Naive Bayes on one category), binary, multiclass, and multilabel tasks, and training and test data.
Naive Bayes
- Naive Bayes classification: Bayes' rule applied to documents, the multinomial model's generative story and estimates, add-one smoothing and how the smoothing constant changes decisions, computing in log space, Naive Bayes as a linear classifier, and the textbook's worked example carried through every step.
- The Bernoulli model and why Naive Bayes works: the second event model, why the two can disagree, how its weights are the Binary Independence Model's, and why a classifier built on a false assumption classifies well while its probabilities are badly calibrated.
Doing it well
- Feature selection: mutual information, the χ² statistic, and frequency, worked by hand on Reuters counts, with experiments showing why mutual information suits the multinomial model poorly.
- Evaluating classifiers: per-class precision and recall, micro- and macro-averaging computed on Reuters, the decision threshold and the precision-recall trade-off, confusion matrices, baselines, cross-validation, and why a classifier must be tested on documents it was not trained on.
- Vector space classification: Rocchio and k nearest neighbors, their decision regions in an interactive two-dimensional example, a comparison with Naive Bayes on Reuters, and linear classifiers and the bias-variance trade-off.
A project
- Predicting star ratings from review text: the Goodreads project, its results, and what I would change.
Related topics
- The Binary Independence Model shares Naive Bayes's independence assumption and its log odds form.
- Clustering groups documents without predefined categories or labeled examples.
- Retrieval evaluation defines the precision, recall, and F measures that classification evaluation builds on.
Course materials
The classifier I built with James R. Brown for our term project is in the Goodreads repository. The experiments on Reuters were written for this site.
References
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 13–14. Cambridge University Press.
- Sebastiani, F. (2002). Machine learning in automated text categorization. ACM Computing Surveys, 34(1), 1–47.