Stop Words

With a typical English stop list, the query to be or not to be disappears entirely. Every word in it is a function word, and every one is on the list. The band The Who becomes the single word who, which is also usually a stop word. Flights to London and flights from London become the same query, and vitamin A loses its letter. These are the standard examples of what stop-word removal costs (Manning, Raghavan, and Schütze, 2008, §2.2.2). The question is whether the savings justify such failures.

Stop words are the very frequent words of a language, such as articles, prepositions, conjunctions, pronouns, and auxiliary verbs, that carry little information about what a document is about. Removing them at indexing time was standard practice for decades. This article explains how stop lists are built, what removal gains and loses, and why practice has shifted from removing stop words to keeping them and reducing their influence in other ways.

Why common words carry little information

A term helps retrieval when its presence distinguishes documents that are about something from documents that are not. The appears in nearly every English document of any length, so knowing that a document contains the says almost nothing about it. Luhn (1958) made this argument when he proposed that the most frequent words in a text lie outside the band of words that indicate its content. As described in term statistics, the most frequent terms of a collection also occur in nearly every document, so they have the longest postings lists. Under an idealized Zipf distribution over 400,000 terms, the 25 most frequent terms account for about 28 percent of all tokens. A short list of words therefore accounts for a large share of the work an index does.

A real collection behaves much the same. In Reuters-21578, the 10,788 newswire stories used for the term statistics article, tokenized the same way (lowercased runs of letters), the 25 most frequent of 29,187 terms make up 32.3 percent of the 1,330,267 tokens. The 30 most frequent are shown below, marked by whether two widely used stop lists contain them: the 33-word English list of the Lucene search library (which this site's own search also uses) and the 198-word English list distributed with NLTK.

Three kinds of term crowd the top of the list. The first are function words, which every general stop list contains. The second are the house vocabulary of a financial newswire: said, mln (million), vs (versus, in tables of results), dlrs (dollars), pct (percent), cts (cents), shr (share), and net. Said occurs in 63 percent of the stories, nearly as many as the (64 percent). These are stop words for this collection and for no general list. The third are fragments created by earlier stages: s from possessives and from U.S., u from U.S., and lt from an undecoded markup entity, described in the delineation article. A ranked frequency list is therefore a diagnostic of the whole pipeline as well as the raw material for a stop list.

Building a stop list

The usual procedure is simple (Manning, Raghavan, and Schütze, 2008, §2.2.2):

1. Count the collection frequency of every term in a representative collection.
2. Sort the terms by frequency and take the most frequent ones as candidates.
3. Review the candidates by hand, removing any that carry meaning in the collection's domain.

Several published lists were built this way and became standards. C. J. van Rijsbergen's textbook (1979) included a list of about 250 English words, the SMART system used one of 571, and Fox (1989) derived a list of 421 words from the frequencies of the Brown corpus. Lists for other languages are built the same way, and they must be: a stop list is specific to a language, and applying an English list to French or German text leaves most of their function words in place.

Frequency alone is a crude criterion. A list can also be derived from document frequency, by choosing the terms with the lowest inverse document frequency, or from how evenly a term is spread across documents. Lo, He, and Ounis (2005) proposed a method that samples terms and scores how informative each is by Kullback–Leibler divergence, compared it with frequency-based lists on four TREC collections, and found the best results by merging an automatically derived list with a classical one.

Domain-specific stop words

General lists are wrong in specialized collections, in both directions. In a collection of clinical notes, patient appears in nearly every document and discriminates almost nothing, while in general text it is informative. In a collection of computer science abstracts, computer, system, and algorithm behave like stop words. Conversely, general lists contain words that matter in some domains. Legal text distinguishes may from shall, as described in search in professional domains, and in a collection about information technology, IT is not the pronoun it. Stop lists for specialized collections should be derived from that collection's own statistics and reviewed by someone who knows the domain.

What removal gains

Removing stop words at indexing time has three benefits:

• A smaller index. The postings lists of the most frequent terms are the longest, so dropping a few dozen terms removes a disproportionate share of the postings. The saving is largest in a positional index, which stores every occurrence of every term, so its size is proportional to collection frequency. It is smaller in an index that stores one posting per document, whose size is proportional to document frequency.
• Faster queries. A query containing the would otherwise have to read and merge one of the longest lists in the index.
• Less noise in ranking. Without weighting, matches on function words would contribute as much to a document's score as matches on content words.

The difference between the two kinds of index can be measured. In a positional index every token is a posting, so a stop list saves the share of tokens it covers. In an index with one posting per document, it saves the share of document postings, the sum of the listed terms' document frequencies. On Reuters:

The positional saving is about twice the document-level saving for short lists, because the most frequent words occur many times in each document that contains them: the averages ten occurrences per story that contains it. The published lists save less than the frequency-derived lists of the same length, because they are not tuned to this collection. Only 146 of NLTK's 198 entries ever appear as tokens (some, such as wasn't, contain an apostrophe that this tokenizer splits on, and others, such as yourselves, are rare in news), while the newswire's own frequent terms, such as said and mln, are on neither list. (Computed by tools/experiments/textproc/stopwords.py.)

What removal costs

The costs are the queries in the opening paragraph. Removal fails whenever function words carry the meaning:

• Phrases and names: The Who, Let It Be, President of the United States, To be or not to be.
• Relations: flights to London versus flights from London, with and without in a product search.
• Words that are stop words in one sense and content words in another: can (a container), will (a legal document), US (the country), IT (the field), vitamin A.

What survives depends on the list. Applied to the opening queries, the two lists used above leave:

The short list happens to keep who and from, so with it The Who survives as one word and the two flight queries stay distinct. The longer list loses both. Neither list can save to be or not to be.

These losses are permanent for that index. A word removed at indexing time cannot be recovered at query time, because the index no longer records where it occurred. No later improvement in query processing or ranking can restore the phrase to be or not to be to an index that discarded every word in it. The only remedy is to rebuild the index from the original text, if it was kept.

Why practice changed

Manning, Raghavan, and Schütze (2008, §2.2.2) describe the trend in information retrieval systems as moving from large stop lists of 200 to 300 terms, to very small lists of 7 to 12 terms, to no stop list at all. They note that web search engines generally do not use stop lists. The reasons are developments covered later in the course, which reduce what removal gains while its costs stay the same:

• Compression. The postings lists of frequent terms consist of very small gaps between document numbers, which compression stores in very few bits. The long lists of common words therefore cost much less space than their length suggests.
• Term weighting. Weighting schemes such as TF-IDF and BM25 give terms that occur in most documents very low weights. The exact treatment differs between IDF formulas; some BM25 variants would make such weights negative unless they are floored or shifted. In the standard TF-IDF form $\log(N/\mathit{df})$, a term occurring in every document has an inverse document frequency of exactly zero. Weighting removes the noise in ranking without discarding the words.
• Efficient query processing. Techniques that process postings in order of their contribution to the score, and stop early when remaining contributions cannot change the top results, can often avoid reading most of a common term's long list (see search at scale).

The weighting argument is easy to check with numbers. With base-10 logarithms and the $N = 10{,}788$ Reuters stories:

A match on cocoa is worth about eleven times a match on the. In this collection the does not reach zero weight, because 3,837 stories, about a third, never use it: most of them are short tables of company results (median length 29 words) such as Shr 14 cts vs nine cts, but weighting has already done most of what removal would. Said is weighted like a stop word without being on any list. Not, on both lists, carries more than three times the weight of the, and removing it would discard a word whose presence can reverse the meaning of a query.

Open-source search libraries reflect this shift. Lucene's English analyzer applies a list of only 33 words, and Elasticsearch's standard analyzer applies no stop list by default.

Alternatives to removal

Several techniques keep stop words available for the queries that need them while limiting their cost:

• Remove stop words at query time, not at indexing time. The index keeps every word. Ordinary queries ignore stop words, while phrase queries and queries consisting mostly of stop words use them. The decision can then be made per query, and changed later without rebuilding the index.
• Index common-word pairs. A word pair that contains a stop word, such as the who or to be, can be indexed as a single term in addition to its parts. The pairs add terms and postings to the index, but they are much rarer than the stop words alone, so phrase queries containing them are answered from short lists. Lucene's common-grams filter implements this approach.
• Rely on weighting. Keep stop words in both the index and the query and let low weights make them nearly irrelevant to ranking, except when they distinguish one phrase from another.

For a small system, such as a course project indexing a few thousand documents, removing a short stop list remains a reasonable simplification, as long as it is applied identically to documents and queries and its effect on phrase queries is understood. For anything larger or longer-lived, the more flexible choice is to keep the words and decide how to treat them at query time.

Stop words and neural rankers

Neural ranking models give a further reason to keep function words. A model such as BERT reads the query and document as sentences, and words like to, from, not, and without are part of what the sentence means. Dai and Callan (2019) found that a BERT-based ranker performed better on longer, natural-language versions of queries than on short keyword versions, the reverse of the usual pattern for classical models, and that removing stop words from the queries hurt the neural ranker. The words a bag-of-words model treats as noise carry structure that a model of language can use. In systems that retrieve candidates with a classical model and re-rank them with a neural one, the second stage must therefore see the original text with its stop words, taken from a document store if necessary, even if the first-stage index drops them or gives them little weight.

Where stop-word removal fits in the pipeline

Stop-word removal takes the tokens produced by tokenization. Its position relative to the other steps matters. Checking tokens against the list after case folding lets The and the match the same list entry. Checking it before stemming avoids comparing the list against stems, which may not resemble the words on it. If stemming runs first, the stop list must be stemmed too. Whichever order is chosen, it must be the same for documents and queries.

References

• Dai, Z., and Callan, J. (2019). Deeper text understanding for IR with contextual neural language modeling. In Proceedings of SIGIR 2019, 985–988.
• Fox, C. (1989). A stop list for general text. SIGIR Forum, 24(1–2), 19–21.
• Lo, R. T.-W., He, B., and Ounis, I. (2005). Automatically building a stopword list for an information retrieval system. Journal on Digital Information Management, 3(1), 3–8.
• Luhn, H. P. (1958). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159–165.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 2.2.2. Cambridge University Press.
• van Rijsbergen, C. J. (1979). Information Retrieval, 2nd edition, chapter 2. Butterworths.