Natural Language Processing

How programs analyze and generate text. The tasks, the processing pipeline and where the course wiki covers each step, bags of words and the synonym problem shown with three sentences, word vectors computed from co-occurrence counts in the million-word Brown corpus with their neighbors, their antonym problem and a failed analogy, word2vec, attention and the transformer, encoders such as BERT and decoders such as GPT, and the caveats that apply to every evaluation of a language system.

Consider three short film reviews:

  1. The film was wonderful.
  2. The film was terrible.
  3. A movie that is great.

Reviews 1 and 3 say nearly the same thing, and review 2 says the opposite. Count the words in each and compare the counts, the simplest way a program can represent text, and the result is reversed. Reviews 1 and 2 share three of their four words, and the cosine similarity of their word-count vectors is 0.75. Reviews 1 and 3 share no word at all, and their cosine is 0. A representation that cannot see that film and movie name the same thing, or that wonderful and terrible are opposites, misses most of what the sentences say.

Natural language processing (NLP) is the part of artificial intelligence concerned with programs that analyze, transform and generate human language. This article follows the main line of its development as a sequence of answers to the problem the three reviews pose: how to represent text so that a program can work with its meaning. It starts from the count-based representations that the course wiki develops for search, computes word vectors from a public corpus to show both what they capture and what they miss, and ends with the attention mechanism and the transformer, on which current language models are built. The library's Language Models from Scratch builds one of those models step by step, and the generative AI and prompt engineering articles take up how they generate text and how they are used.

Tasks and the pipeline

NLP covers a wide range of tasks. Classification assigns a label to a text: spam or not, the topic of a news story, the sentiment of a review. Information extraction pulls structured facts out of text, such as the names of people and organizations or the dates and amounts in a contract. Translation, summarization and simplification transform a text into another text. Question answering and dialogue respond to a request. Generation produces new text, from a short continuation to a long report.

Before 2018 or so, most systems for these tasks were built as a pipeline of separate steps, and the steps are still worth knowing, because they show what a program must do with raw text and because search engines and many classifiers still use them. The course wiki on information retrieval covers each in depth:

  • Tokenization splits a character sequence into units, usually words or pieces of words, with decisions to make about apostrophes, hyphens, numbers and languages written without spaces (Tokenization).
  • Normalization maps variant forms to one: case folding, removing accents, expanding abbreviations (Token Normalization).
  • Stop-word removal drops very common function words. It shrinks an index but has costs: with a typical English stop list the query to be or not to be disappears entirely, and web search engines largely stopped using stop lists (Stop Words). For sentiment, removing not reverses meaning.
  • Stemming and lemmatization reduce words to a common base. A stemmer such as Porter's strips suffixes by rule, so connected, connecting and connection all become connect; a lemmatizer uses a dictionary and the word's part of speech, so it can map better to good (Stemming and Lemmatization, The Porter Stemmer).
  • Representation turns the processed tokens into numbers a model can use, which is the subject of most of this article.

Modern language models fold most of these steps into the model. They tokenize text into subword pieces with a learned vocabulary, usually by byte-pair encoding, and leave case, morphology and function words for the network to handle; the library's BPE Tokenization for the Shakespeare GPT shows what that changes in practice.

Bags of words

The bag-of-words model represents a document by the words it contains and how often, ignoring their order. James, Witten, Hastie and Tibshirani (2021, §10.4) call it "the simplest and most common featurization". Each document becomes a vector with one entry per vocabulary word, almost all of them zero. Weighting the counts by how rare each word is across the collection gives TF-IDF, and measuring the angle between two such vectors gives cosine similarity, the score behind the vector space model of search. The same vectors feed classifiers such as naive Bayes, which the course wiki works for text classification, and models of themes such as topic models.

The representation is crude and surprisingly effective. It is fast, it needs no labeled data to build, and for deciding what a document is about the presence of a handful of words is usually enough. Its limits are the ones the three reviews expose. Order is lost, so dog bites man and man bites dog are the same bag. Different words are unrelated: in the vector for review 1, the film dimension has nothing to do with the movie dimension of review 3, so related documents that use different words look unrelated. Latent Semantic Indexing was an early answer to the second problem, finding a smaller set of dimensions in which words that occur in similar documents end up close together.

Word vectors from co-occurrence

The answer that took hold is to represent each word by the company it keeps. The distributional hypothesis, usually traced to Harris (1954) and Firth (1957) and cited here by attribution, holds that words occurring in similar contexts tend to have similar meanings. If Monday and Tuesday are both often preceded by on and next and followed by morning and night, a program can infer that they are similar without being told what either means.

The procedure can be carried out with nothing more than counting and linear algebra. The worked example below uses the Brown corpus, which its compilers titled a standard corpus of present-day edited American English: about a million words drawn from news, fiction, government documents and other genres (Francis and Kučera, 1964, revised 1979; used in the NLTK distribution). Its 500 files contain 1,161,192 tokens in 57,340 sentences; keeping lowercased words made only of letters leaves 981,716 words of 40,234 distinct types.

  1. Count. For the 10,000 most frequent words, count how often each pair occurs within two words of each other in the same sentence. This gives a $10{,}000 \times 10{,}000$ matrix $M$ with 969,270 nonzero cells.
  2. Reweight. Raw counts are dominated by frequent words: almost every word co-occurs with the. Pointwise mutual information compares how often word $w$ and context word $c$ co-occur with how often they would if they were independent, $$\text{PMI}(w, c) = \log_2 \frac{p(w, c)}{p(w)\, p(c)},$$ where $p(w, c)$ is the share of all co-occurrence counts in cell $(w, c)$ and $p(w)$, $p(c)$ are the shares of the row and column totals. Positive values mean the pair occurs together more often than chance. Setting negative values to zero gives positive PMI (PPMI).
  3. Compress. A truncated singular value decomposition, computed exactly, keeps the 100 strongest dimensions of the PPMI matrix, as in principal component analysis and LSI. Each word is now a dense vector of 100 numbers, normalized to length 1, called a word embedding.

Similar words should now have vectors that point in similar directions. The five nearest neighbors by cosine similarity, for a few words, are:

Word (count) Nearest neighbors (cosine)
monday (68) friday 0.84, tuesday 0.84, wednesday 0.83, sunday 0.82, night 0.80
walked (159) ran 0.82, climbed 0.81, rolled 0.78, moved 0.77, drove 0.77
red (197) white 0.75, crimson 0.69, yellow 0.69, black 0.69, sox 0.66
church (348) student 0.71, churches 0.68, presbyterian 0.67, catholic 0.66, baptist 0.66
boy (242) girl 0.75, woman 0.69, man 0.68, lady 0.65, fellow 0.64
money (265) extra 0.63, credit 0.62, capital 0.60, raising 0.60, fair 0.59

Nobody told the program that Monday is a day, that walked is a verb of motion in the past tense, or that crimson is a color. It found each from about a million words of text, along with the corpus's own habits: sox is near red because of a baseball team. Three limits are as instructive as the successes.

Similar is not synonymous. The cosine between wonderful and terrible is 0.51 and between good and bad 0.64, because opposites appear in the same contexts (the film was ___). Distributional similarity measures relatedness of use, and antonyms are closely related in use. A sentiment classifier built on such vectors must learn the difference from labeled data.

Rare words get poor vectors. Film occurs 96 times in the corpus and movie only 29, and their cosine is a modest 0.31; king (88 occurrences) has as its nearest neighbors the names Lewis and Morgan and the words finally and letter, which reflects how the word happens to be used in this corpus more than what it means.

Analogies need far more data. Mikolov, Chen, Corrado and Dean (2013, §1) cite the finding, from earlier work by Mikolov, Yih and Zweig (2013), that vector("King") − vector("Man") + vector("Woman") is closest to the vector of Queen. With the Brown vectors, the five words closest to that combination are shelley, lewis, katie, jane and marriage; queen ranks 95th. The regularity is a property of vectors trained on billions of words, not of the method alone.

word2vec

Mikolov et al. (2013) made word vectors cheap to train at that scale. Their two architectures replace counting and factorization with a shallow network trained on a prediction task: the continuous bag-of-words (CBOW) model predicts a word from its neighbors, and the skip-gram model predicts the neighbors from the word (§3). The trained weights of the network are the word vectors. They report learning high-quality vectors from a 1.6-billion-word dataset in less than a day, and they introduced a test of 8,869 semantic and 10,675 syntactic analogy questions on which skip-gram did particularly well on the semantic part (abstract, §4.1, §4.3). Later analysis showed that methods of this kind are closely related to factorizing a shifted PMI matrix like the one above, which is part of why the count-based example behaves like a small word2vec; that analysis is cited here by attribution (Levy and Goldberg, 2014). The library's essay note on distributed representations discusses how such vectors encode many features in a few dimensions.

Words in context: attention and the transformer

A word vector of the kind above is the same in every sentence, so bank has one vector whether it is a river bank or a savings bank. Representing a word in context requires a model that reads the sequence. Recurrent neural networks read one token at a time and carry a summary forward (James et al., 2021, §10.5). Vaswani et al. (2017, §1) describe their limitation: because each step depends on the previous one, their "inherently sequential nature precludes parallelization within training examples", which becomes a bottleneck for long sequences, and information from an early token must survive many steps to influence a late one.

Attention lets every position look at every other position directly. Vaswani et al. (2017, §3.2) describe an attention function as "mapping a query and a set of key-value pairs to an output", where the output is a weighted sum of the values and each weight comes from how well the query matches the corresponding key. In scaled dot-product attention, with the queries, keys and values for a whole sequence stacked as the rows of matrices $Q$, $K$ and $V$,

$$\text{Attention}(Q, K, V) = \operatorname{softmax}\!\left(\frac{Q K^{\mathsf{T}}}{\sqrt{d_k}}\right) V,$$

where $d_k$ is the length of the key vectors and the softmax is taken across each row. Each row of $QK^{\mathsf T}$ scores how relevant every position is to one position; the softmax turns the scores into weights that sum to one; and the output for that position is the weighted average of the value vectors. Because $Q$, $K$ and $V$ are computed from the token representations by learned matrices, the network learns what each position should look for and what it should offer. The library's Building Self-Attention Step by Step derives the formula from a running average of earlier characters and implements it in PyTorch; Assembling the Transformer Block adds several attention heads in parallel, feedforward layers, residual connections and layer normalization.

The transformer is built from such blocks, with information about each token's position added to its embedding, since attention by itself ignores order. Vaswani et al. (2017) introduced it for translation and reported 28.4 BLEU on the WMT 2014 English-to-German task, more than 2 points above the best previous results including ensembles, at a fraction of their training cost (abstract, §6.1). The design trades one cost for another: self-attention needs a number of operations per layer that grows with the square of the sequence length, against linear growth for a recurrent layer, but all positions can be computed at once (Table 1). For the sentence lengths of translation the trade favored attention.

Encoders and decoders

The original transformer has an encoder, which reads the source sentence with attention in both directions, and a decoder, which generates the translation one token at a time, each position attending only to earlier ones. Two families of models later kept one half each.

BERT (Devlin, Chang, Lee and Toutanova, 2019) keeps the encoder. It is pretrained on unlabeled text with a masked language model objective: 15% of the tokens in each sequence are selected at random, and the model is trained to predict the original tokens from the context on both sides (§3.1). A second pretraining task asks whether one sentence follows another. The pretrained model is then fine-tuned for a specific task with one added output layer (abstract). Their base model has 12 layers and 110 million parameters, the large one 24 layers and 340 million (§3). BERT-style models are suited to understanding tasks: classification, extraction and finding the passage that answers a question.

GPT models keep the decoder. Each position may attend only to earlier positions, and the model is trained to predict the next token, which is the self-supervised setup of the machine learning overview. Devlin et al. (2019, §3) note the contrast: the BERT transformer uses bidirectional self-attention, while the GPT transformer uses "constrained self-attention where every token can only attend to context to its left". Predicting the next token is exactly what generating text requires, and GPT-style models scaled to billions of parameters became the large language models behind current chat assistants. The generative AI article covers what happened as they grew, and the GPT walkthrough builds a small one; its bigram model is the simplest possible next-token predictor, and the final model has 10,788,929 parameters and produces Shakespeare-like text.

Evaluating language systems

Every evaluation of a language system rests on a test set and a measure, and both deserve suspicion.

The measure. Classification tasks can be scored with the measures of Binary Classification Metrics and the course wiki's Evaluating Classifiers. Generated text is harder. Translation is scored by BLEU, which counts overlapping word sequences with reference translations, and summarization by similar overlap measures; both reward matching a reference more than being correct or useful. Human judgments are better and costlier, and they disagree, as the course wiki's Relevance Judgments, Pooling, and Agreement shows for search.

The test set. Models trained on large crawls of the web may have seen the test set. Brown et al. (2020, §4) studied this "data contamination" for GPT-3, noting that it is "a growing problem when training high capacity models on datasets such as Common Crawl, which can potentially include content from test datasets simply because such content often exists on the web" (§1). A model can also score well by exploiting surface patterns: Geirhos et al. (2020, §1) cite a language model that "may appear to have learned to reason" but drops to chance performance when superficial correlations are removed from the dataset.

The prompt. For models used through prompts, the score depends on how the question is asked. Zhao, Wallace, Feng, Klein and Singh (2021, abstract) found that for GPT-3 "the choice of prompt format, training examples, and even the order of the training examples can cause accuracy to vary from near chance to near state-of-the-art". The prompt engineering article returns to this.

The uncertainty. A benchmark score is an estimate from a sample of questions, and two models' scores can differ by chance. The library's note on Adding Error Bars to Evals works through standard errors and paired comparisons for language model evaluations, and Challenges in evaluating AI systems describes the practical difficulties one developer met with six kinds of evaluation.

In Python

The bag-of-words comparison of the three reviews takes a few lines with scikit-learn:

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.metrics.pairwise import cosine_similarity

reviews = ["The film was wonderful.", "The film was terrible.", "A movie that is great."]
X = CountVectorizer().fit_transform(reviews)
print(cosine_similarity(X).round(2))

CountVectorizer lowercases the text and, by default, ignores one-letter tokens such as a, which does not change these three cosines: 0.75 between reviews 1 and 2, and 0 for both pairs with review 3. For the other steps of the pipeline, NLTK and spaCy provide tokenizers, stemmers, lemmatizers and part-of-speech taggers, and the Hugging Face transformers library loads pretrained transformer models such as BERT for classification, extraction and question answering. The word vectors and every number in the Brown corpus example are computed by tools/experiments/data-science/natural-language-processing.py in the site's repository.

References

  • Brown, T. B., Mann, B., Ryder, N., et al. (2020). Language models are few-shot learners. In Advances in Neural Information Processing Systems 33. arXiv:2005.14165. record · 4 pages
  • Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT 2019 (pp. 4171–4186). arXiv:1810.04805. record
  • Firth, J. R. (1957). A synopsis of linguistic theory, 1930–1955. In Studies in Linguistic Analysis (pp. 1–32). Blackwell. Cited by attribution; not read for this article. record
  • Francis, W. N., and Kučera, H. (1964; revised 1971 and 1979). Brown Corpus: A Standard Corpus of Present-Day Edited American English, for Use with Digital Computers. Department of Linguistics, Brown University. Used in the NLTK distribution (nltk_data, corpora/brown.zip), whose README gives the title and dates; the manual itself was not read. record
  • Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., and Wichmann, F. A. (2020). Shortcut learning in deep neural networks. Nature Machine Intelligence, 2, 665–673. arXiv:2004.07780. record · 2 pages
  • Harris, Z. S. (1954). Distributional structure. Word, 10(2–3), 146–162. Cited by attribution; not read for this article. record
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. §10.4 and §10.5. record · 30 pages
  • Levy, O., and Goldberg, Y. (2014). Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems 27. Cited by attribution; not read for this article. record
  • Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013). Efficient estimation of word representations in vector space. arXiv:1301.3781. record · 2 pages
  • Mikolov, T., Yih, W., and Zweig, G. (2013). Linguistic regularities in continuous space word representations. In Proceedings of NAACL-HLT 2013 (pp. 746–751). Cited as described by Mikolov, Chen, Corrado and Dean (2013); not read for this article. record
  • Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017). Attention is all you need. In Advances in Neural Information Processing Systems 30. arXiv:1706.03762. record · 7 pages
  • Zhao, Z., Wallace, E., Feng, S., Klein, D., and Singh, S. (2021). Calibrate before use: Improving few-shot performance of language models. In Proceedings of the 38th International Conference on Machine Learning, PMLR 139, 12697–12706. arXiv:2102.09690. record · 2 pages