Sparse Text Representations: Counts, N-Grams, and TF–IDF

A complaint router may separate billing from technical issues using words, short phrases, punctuation, and character fragments. These features ignore much of grammar. Yet they can be accurate, fast, and easy to debug.

Their strength is also their limit: they rely on lexical overlap and observed combinations. A careful baseline reveals how much complexity the problem actually requires. The published record shows how demanding that baseline can be, on benchmarks whose numbers are still on the page.

Most entries are zero because each document uses only a small part of the vocabulary. The field's standard text-categorization benchmark says how small. Reuters RCV1-v2, assembled by Lewis and colleagues and published in 2004, is 804,414 documents over a stemmed vocabulary of 47,236 terms. Its weighting is steps 3 to 5 below and nothing more: Cornell ltc, that is (1+log_e n(t,d)) x log_e(|D|/n(t)), followed by cosine normalization.

The paper records the shape of a single row: “Average document length for RCV1-v2 documents with our text representation is 123.9 terms, and average number of unique terms in a document is 75.7.” Roughly 75.7 filled cells in a row 47,236 columns wide.

scikit-learn distributes the same matrix, and reports the whole object the same way: “The feature matrix is a scipy CSR sparse matrix, with 804414 samples and 47236 features”, and “The array has 0.16% of non zero values”. The non-zero values are cosine-normalized log TF-IDF vectors. That is what sparse means as a measurement rather than as an adjective. It is also why the storage question in step 2 is not a detail.

Different units capture different kinds of regularity and failure. For two of these families the trade-off has been counted rather than asserted.

Word unigrams give one inspectable column per observed token. Lexicon and metadata features inject domain knowledge, at the price of maintenance and proxy risk. Word n-grams capture phrases and negation, and the cost of that is the column space. Google put a number on it in 2006. One body of web text yields 13,588,391 distinct unigrams, after words seen fewer than 200 times are discarded, and 1,176,470,663 distinct five-grams, after sequences seen fewer than 40 times are discarded. That is roughly 87 times as many columns for five-word units as for single words, and it is what remains after both thresholds have thrown material away. Alex Franz and Thorsten Brants announced the release on Google's research blog: “We processed 1,024,908,267,229 words of running text and are publishing the counts for all 1,176,470,663 five-word sequences that appear at least 40 times.” The catalog record for the corpus lists the levels in between — 314,843,401 bigrams, 977,069,902 trigrams, 1,313,818,354 fourgrams — so the growth can be watched happening.

Character n-grams are robust to spelling variation, handle morphology and identifiers, can match irrelevant fragments, and are the standard multilingual baseline. The headline number for that last claim belongs to the language set, not to the feature family. Cavnar and Trenkle's character n-gram classifier ran in 1994 on a test set that “consisted of 3478 usable articles”, and they report that “the system misclassified only 7 articles out of 3478, yielding an overall classification rate of 99.8%”. Two decades later a survey of language identification in the Journal of Artificial Intelligence Research set that figure beside re-evaluations of the same method: “The original paper reports an accuracy of 99.8% over eight European languages (>300 bytes test size). Lui and Baldwin (2011) report an accuracy of 68.6% for the method over a dataset of 67 languages (500 byte test size), and Jauhiainen et al. (2017b) report an accuracy of over 90% for 285 languages (25 character test size).” Same features, same method. 99.8 and 68.6 are facts about how many languages you asked it to separate.

Term frequency reflects how strongly a feature appears in one document, while inverse document frequency reduces the weight of terms appearing across many documents. Implementations differ in smoothing, sublinear scaling, and normalization. RCV1-v2's log TF, idf and cosine normalization above is one specific choice among several in common use.

TF–IDF does not discover truth or semantic importance. A rare footer, identifier, or annotation artifact can receive high weight, so somebody still has to inspect the features.

Their advantages are especially strong when labels are limited and vocabulary carries the task.

The baseline is fast enough to make the comparison uncomfortable. Joulin and colleagues reported in 2017 that “our fast text classifier fastText is often on par with deep learning classifiers in terms of accuracy, and many orders of magnitude faster for training and evaluation”. They “can train fastText on more than one billion words in less than ten minutes using a standard multicore CPU”, and can “classify half a million sentences among 312K classes in less than a minute”.

Accuracy, too, and on a benchmark anyone can rerun. On the 50,000-review IMDB set, Wang and Manning's NBSVM with bigrams reached 91.22% in 2012. It is a linear classifier over sparse bag-of-n-gram counts, reweighted by Naive Bayes log-count ratios. The neural results on the same split were 89.23% for WRRBM+BoW(bnc) and 87.42% for WRRBM. The same table gives 89.45 on RT-2k and 93.18 on Subj. Two years later Mesnil and colleagues re-ran the comparison on the same protocol, and found the sparse model the strongest single component of their own system: “The most competitive method is the method based on reweighed bag-of-words (Wang & Manning, 2012).” Their full ensemble, three combined models, reports that “we achieve a new state-of-the-art performance of 92.57%, to be compared to 91.22% reported by (Wang & Manning, 2012)”.

In retrieval the pattern held across eighteen datasets at once. BEIR, published in 2021, evaluated 10 retrieval systems zero-shot on 18 datasets by nDCG@10. Measured against BM25, a purely lexical sparse weighting, the late-interaction model ColBERT “is still able to outperform BM25 on 9/18 datasets”. Of docT5query the paper says “It outperforms BM25 on 11/18 datasets”. Only the cross-attention re-ranker BM25+CE beat it on almost all, 16 of 18. The abstract states the finding without hedging: “Our results show BM25 is a robust baseline and re-ranking and late-interaction based models on average achieve the best zero-shot performances, however, at high computational costs.” A heavier model does not have to win by much to be worth it. It does have to win.

A weak baseline teaches little. A disciplined one can challenge much larger models, as the IMDB and BEIR results above were disciplined enough to do.

Train a linear model on a small routing dataset. For ten correct and ten incorrect predictions, list the highest contributing features and identify whether they reflect intent, domain, source, or leakage. Then create counterfactual edits that remove headers, change names, or paraphrase key phrases, and test whether the decision follows the intended evidence.

The exercise has a published worked answer, on a corpus that has been in teaching use for decades. The 20 Newsgroups collection — 18,846 posts across 20 topics — is where this failure was documented twice, by two unrelated groups. scikit-learn's own documentation states it flatly: “It is easy for a classifier to overfit on particular things that appear in the 20 Newsgroups data, such as newsgroup headers.” It names the mechanism too: “Almost every group is distinguished by whether headers such as `NNTP-Posting-Host:` and `Distribution:` appear more or less often.” Its worked example is a multinomial Naive Bayes with alpha=0.01 over TF-IDF unigrams, run not on all 20 groups but on the four-group subset alt.atheism, talk.religion.misc, comp.graphics and sci.space, with 2,034 training documents and 34,118 features. Macro F1 falls from 0.88213 to 0.76995 once headers, footers and quotes are stripped from training and test alike, and the top features turn out to be header artefacts. The instruction that follows is blunt: “you should strip newsgroup-related metadata”.

The same shortcut was measured a second time, with different instruments. Ribeiro and colleagues trained an RBF-kernel SVM over unigrams on the atheism-versus-christianity subset, and what explained its predictions was header debris: Posting, Host and Re:. “Although this classifier achieves 94% held-out accuracy ... predictions are made for quite arbitrary reasons”. The token Posting appears in 22% of the training examples, 99% of them in the class Atheism. On an out-of-domain religion dataset the original classifier scored 57.3%, against 69.0% for a manually cleaned version. Both measurements agree on the uncomfortable half. Removing the shortcut lowered the number on the in-domain page and raised the one that mattered. That gap, not the coefficient list itself, is what inspection is for.