The Text Classification Problem

An analyst wants to follow news about multicore computer chips. Running the same search every morning is tedious, so the search is saved and run automatically on each day's new articles. Matching documents are delivered, and the rest are discarded. That saved search is a standing query, and it divides each day's news into two classes: relevant to multicore chips, and not (Manning, Raghavan, and Schütze, 2008, ch. 13). A standing query written as keywords, such as multicore AND (chip OR processor), will miss articles that say multi-core or dual-core CPU. It can be refined by hand, but each refinement adds rules that someone must maintain. The alternative is to show the system examples of articles that do and do not belong, and let it learn the distinction.

That is text classification: assigning documents to categories fixed in advance. This article defines the problem and its variants, compares the ways of solving it, and surveys where it is used.

The problem

Manning, Raghavan, and Schütze (2008, §13.1) define the problem formally. Given:

• a document space $\mathbb{X}$, the set of all possible documents, each represented in some way, for instance as a bag of terms;
• a fixed set of classes $\mathbb{C} = \{c_1, \dots, c_J\}$, also called categories or labels;
• a training set $\mathbb{D}$ of labeled documents $\langle d, c \rangle$, each document paired with its correct class,

a learning method produces a classifier $\gamma: \mathbb{X} \to \mathbb{C}$ that maps documents to classes. The aim is not to label the training documents correctly, which is trivial, but to label new documents correctly. A classifier that memorizes its training set and fails on new documents is said to overfit. Whether it generalizes is measured on a test set of labeled documents kept apart from training, as described in evaluating classifiers.

The experiments in this topic fill in each symbol concretely. The documents are Reuters-21578 news stories, each represented as the bag of its stemmed terms after stop words are removed; a median training story has 58 tokens and 38 distinct terms. The classes are the collection's topic categories, such as earn, grain, and ship. The training set is the 7,769 stories of the standard training split, and the test set the 3,019 stories of the test split. The learning method is Naive Bayes or one of the vector space classifiers, and the classifier it produces for grain is a function that reads a story and answers yes or no.

Variants

The task comes in several shapes:

• Binary classification assigns each document to one of two classes: spam or not, relevant to the standing query or not.
• Multiclass (one-of) classification assigns each document to exactly one of several classes, such as the language of a document, or the star rating of a review.
• Multilabel (any-of) classification assigns each document to any number of classes, including none. A news story about a wheat export deal can be about grain, wheat, and trade at once. Multilabel problems are usually decomposed into one binary classifier per class, each deciding independently whether its class applies.
• Hierarchical classification assigns documents to classes arranged in a taxonomy, such as the subject headings of a library or a product catalog, where the structure can be used to share evidence between related classes.

The classes in the standard ModApte split of the Reuters-21578 collection, used for the experiments in this topic, are multilabel. A story can belong to several of 90 topic categories, so classifiers for it are built one class at a time. Of the 10,788 stories in the split, 9,160 carry exactly one category, 1,173 carry two, and the rest between three and fifteen. The experiments use the ten largest categories, whose sizes differ by a factor of sixteen:

The labels overlap in ways that make some categories hard to separate. Of the 283 stories labeled wheat, 280 are also labeled grain, and of the 237 labeled corn, 235 are. Of the 582 grain stories, 146 are about neither wheat nor corn. A classifier for wheat must therefore learn not "is this about grain?", which nearly every positive and many negative examples share, but the narrower "is this about wheat in particular?". The per-category results in Naive Bayes classification show the consequence: wheat and corn are among the hardest categories.

Three ways to classify

Manual classification. People read documents and assign classes. Editors classified documents this way in library catalogs, in the Yahoo! web directory, and in the legal and medical indexes described in search in professional domains. Manual classification is accurate when done by experts, but it is slow and expensive, and it cannot keep up with large or fast-moving collections.

Hand-written rules. An expert writes rules, often Boolean expressions over terms, that assign classes. Well-crafted rules can be very accurate, and for narrow, stable categories they remain in use. But they are expensive to write and maintain. Each rule needs someone who understands both the domain and the rule language, and rules must be revised as vocabulary changes.

Supervised learning. People label a training set, which requires domain knowledge but no technical skill, and an algorithm learns the classifier. The effort shifts from writing rules to labeling examples, which is cheaper and can be repeated whenever the categories or vocabulary change. Learned classifiers are now the standard approach. Sebastiani (2002) described how they became dominant in research from the early 1990s, reaching effectiveness comparable to that of human experts with far less expert labor.

A rule against a learner

Hand-written rules should not be underestimated. For the Reuters category grain, consider the rule "assign grain if the story contains grain, wheat, or corn", applied to stemmed terms. Chosen without looking at the test stories, it scores as follows (computed by tools/experiments/reuters/reuters_more.py):

Three words beat a classifier trained on the whole vocabulary. The rule is precise because these words rarely occur outside grain stories, and most of the 30 test stories it misses name a particular grain instead, such as rice (14 of them), maize (9), or barley (5). The learned classifier finds almost every grain story but also assigns many others, a bias in where its decision threshold sits; evaluating classifiers shows that moving the threshold, chosen on held-out training data, raises its F1 to 0.807. The comparison is fair to the rule only for a category that a few words define. Writing equally good rules for acq (acquisitions) or money-fx, which no short list of words defines, is likely to be much harder, and doing so for all 90 categories, and maintaining the rules as the news changes, is the cost that learning avoids.

In practice the approaches are often combined. Rules handle cases that must never be wrong, learned classifiers handle the rest, and people review uncertain cases, whose labels then become new training data.

The bag-of-words representation

Most text classifiers in this course represent a document the way the vector space model does: as a bag of terms, possibly weighted. Every distinct term becomes a feature. A collection may have tens of thousands of features, most absent from any given document. That high dimensionality has two consequences. Classifiers must handle features that occur rarely in training, which is the role of smoothing in Naive Bayes. And it is often useful to reduce the number of features, the subject of feature selection.

Where classification is used

Classification is among the most widely deployed applications of retrieval methods:

• Spam filtering, the most familiar binary classifier, which began moving to statistical methods in the late 1990s (see search applications);
• Routing and topic categorization of news, support tickets, and documents into the queues or folders where they belong;
• Sentiment analysis, deciding whether a review or post is positive or negative, or how many stars it gives, as in my Goodreads project;
• Language identification, an early step of text processing;
• Vertical selection in web search, deciding whether a query should trigger news, image, or shopping results (see how a web search engine answers a query);
• Content moderation and safety, flagging documents that violate policies;
• Technology-assisted review in legal discovery, classifying documents as responsive or not.

Each of these replaces a judgment that would otherwise require a person to read every document. That is the economic reason classification is so widely used, and the reason its errors, the topic of evaluating classifiers, matter.

References

• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 13 introduction and section 13.1. Cambridge University Press.
• Sebastiani, F. (2002). Machine learning in automated text categorization. ACM Computing Surveys, 34(1), 1–47.