Chapter 1: Introduction to NLP

The first NLP systems encoded language knowledge by hand. The 1954 Georgetown-IBM demonstration translated more than 60 Russian sentences into English using a 250-word vocabulary and just six grammar rules, and it fueled predictions that translation would be solved within years. Chomsky's Syntactic Structures (1957) gave syntax a formal footing. ELIZA (1966) imitated a therapist with keyword patterns, and SHRDLU (around 1970) obeyed commands in a toy world of blocks. The 1966 ALPAC report concluded that machine translation had not delivered and US funding was cut sharply. The lesson was that rules work in narrow domains but cannot keep up with open-ended language.

By the late 1980s, large machine-readable corpora and cheaper computing made it possible to learn language patterns by counting. IBM's translation models learned word alignments from Canadian parliamentary proceedings in English and French, the Penn Treebank (1993) supplied millions of words annotated with tags and parse trees, and hidden Markov models became standard for tagging and speech. The formula above picks the label $\hat{y}$ that maximizes $P(x \mid y) P(y)$: a likelihood estimated from counts times a prior. The weakness was sparsity, since most word combinations never appear in any training corpus, so models needed smoothing and hand-designed features to generalize.

Neural methods replaced sparse counts with dense learned vectors. Word2Vec (2013) trained embeddings by predicting nearby words, so words used in similar contexts ended up close together. Recurrent networks, especially LSTMs, read a sentence one token at a time, updating a hidden state $h_t$ from the current input $x_t$ and the previous state $h_{t-1}$, as the formula shows. Encoder-decoder models (2014) translated by compressing a source sentence into vectors and decoding a target, and Bahdanau attention let the decoder look back at every source word instead of a single summary vector. The remaining weaknesses were sequential computation, which was slow to train, and difficulty remembering information across long distances.

The Transformer (2017) removed recurrence entirely. In the formula, every token forms a query $Q$ that is compared with the keys $K$ of all tokens, the scores are divided by $\sqrt{d_k}$ to keep them in a stable range, and the softmax weights mix the values $V$. Every position therefore connects directly to every other in one layer, and all positions are computed in parallel. Pretraining then exploited this at scale: BERT (2018) learned bidirectional representations by predicting masked words, and GPT models learned to predict the next token. One pretrained model fine-tuned for many tasks replaced separate pipelines. The main cost is attention's quadratic growth with sequence length.

Tokenization splits raw text into tokens, the units a model counts or embeds. Word tokenizers split on spaces and punctuation, which is simple but leaves rare words and new names out of a fixed vocabulary. Subword tokenizers such as BPE learn a vocabulary of frequent pieces: the formula says BPE repeatedly merges the adjacent pair $(a, b)$ with the highest frequency into a new symbol $ab$. Rare words then decompose into known pieces instead of an unknown token. Real tokenizers rarely split along morphemes: GPT-2 splits 'unhappiness' into un, h, appiness. The choice trades vocabulary size against sequence length, and every later task inherits its mistakes.

POS tagging assigns each word a grammatical category such as noun, verb, adjective, or determiner. The formula asks for the tag sequence $\hat{t}_1, \ldots, \hat{t}_n$ that is most probable given the words $w_1, \ldots, w_n$, so tags are chosen jointly, not one word at a time. Context matters because many words are ambiguous: 'book' is a noun in 'a book' and a verb in 'book a flight'. Hidden Markov models combined word-given-tag and tag-transition probabilities, and the Viterbi algorithm found the best sequence; modern taggers use bidirectional neural encoders and exceed 97 percent accuracy on news text. The Penn Treebank defines 36 word-level tags.

NER finds spans of text that name specific things and assigns each a type, such as PERSON, ORGANIZATION, LOCATION, or DATE. Because entities can span several tokens, NER is usually cast as sequence labeling with BIO tags: B-TYPE marks the first token of an entity, I-TYPE marks a continuation, and O marks tokens outside any entity. With $k$ entity types there are $2k + 1$ labels. A valid sequence never starts an entity with I-, which is why taggers often add a CRF layer that scores label transitions. NER feeds search, question answering, and knowledge graphs, and it fails on unseen names, on nested entities, and when moved to a new domain.

Text classification assigns one or more labels to a whole document; sentiment analysis, spam filtering, topic tagging, and intent detection are all instances. In the formula, $\phi(x)$ is a feature vector for the text, such as word counts or a neural embedding, $\mathbf{w}$ is a learned weight per feature, $b$ is a bias, and the predicted class $\hat{y}$ is the one with the highest score. A linear model over word counts is a strong baseline that is fast and interpretable. Its weakness is that it ignores word order and composition, so negation ('not good') and contrast ('good but') confuse it, and fine-tuned Transformers handle these far better.

Bag-of-words fixes a vocabulary of $V$ words and represents a document $d$ by the vector in the formula: entry $i$ is the number of times word $w_i$ occurs in $d$. Every document, short or long, becomes a point in the same $V$-dimensional space, so any standard classifier can use it. The vectors are extremely sparse, because a document uses a tiny fraction of the vocabulary. The cost of the simplicity is that order is discarded: 'dog bites man' and 'man bites dog' get identical vectors. Adding bigrams as extra features recovers some local order at the price of a much larger vocabulary, and words outside the vocabulary are dropped.

Raw counts let frequent words like 'the' dominate a document vector. TF-IDF fixes this by multiplying two factors. The term frequency $\text{tf}(t, d)$ counts how often term $t$ appears in document $d$. The inverse document frequency $\log(N / \text{df}(t))$ uses the corpus size $N$ and the number of documents $\text{df}(t)$ that contain $t$: a term found in every document gets $\log 1 = 0$, while a rare term gets a large weight. The result rewards words that are frequent in one document but rare overall. TF-IDF remains a strong baseline for search and classification, but it still ignores word order and treats synonyms as unrelated.

Word embeddings represent each word $w$ by a dense vector $\mathbf{v}_w$ in $\mathbb{R}^d$, usually with $d$ between 100 and 300, learned so that words used in similar contexts get similar vectors. Similarity is measured with the cosine in the formula, which ignores vector length and compares direction only. Unlike one-hot or bag-of-words vectors, where every pair of different words is equally unrelated, embeddings let knowledge transfer: a classifier that learns 'car' also learns something about 'automobile'. Word2Vec predicts neighboring words, GloVe factorizes co-occurrence counts, and FastText adds character n-grams for rare words. All of them give one vector per word, which mixes the senses of words like 'bank'.

Static embeddings give a word one vector everywhere, so 'bank' in 'river bank' and in 'bank account' share a point that blends both senses. Contextual representations compute a vector for each occurrence from the whole sentence. ELMo (2018) did this with bidirectional LSTMs; BERT and GPT do it with Transformer layers, where each token's vector is updated by attending to its neighbors. The same word then gets different vectors in different contexts, which handles polysemy and lets one pretrained encoder serve many tasks. The costs are that every occurrence needs a forward pass through a large network, and the vectors depend on the model's layers and training data.

Lexical ambiguity arises when one word form has several meanings: WordNet lists 18 senses for 'bank' across its noun and verb uses. Structural ambiguity arises when one word sequence has several valid parse trees: in 'I saw the man with the telescope', the phrase 'with the telescope' can attach to 'saw' (the instrument) or to 'the man' (what he carries). Only about one in five WordNet lemmas is polysemous, but those include the most frequent words. People resolve ambiguity with context and world knowledge so quickly that they rarely notice it, while a model has to infer the right reading from data.

Coreference resolution decides which earlier mention a pronoun or noun phrase refers to. The formula scores each candidate referent for compatibility with the pronoun and its context, then normalizes the scores over all candidates to get a probability. Grammar alone often cannot decide: in 'The trophy doesn't fit in the suitcase because it is too big', both nouns agree with 'it', and only knowing how containers work picks the trophy. Winograd schemas pair sentences that differ in one word, flipping the referent. WinoGrande scales this to about 44,000 problems built to defeat word-association shortcuts; at publication the best model scored 79.1 percent against 94 percent for humans.

In figurative language the intended meaning differs from the literal words. Sarcasm says the opposite of what is meant ('Oh great, another meeting'), hyperbole exaggerates, metaphors map one domain onto another, and idioms such as 'kick the bucket' have meanings unrelated to their parts. A sentiment model that sums word polarities reads 'great' as positive and misses the complaint. The usual cue to sarcasm is incongruity, positive wording about a negative situation, which needs knowledge of what situations are normally pleasant. Tone of voice and facial expression are lost in text, and even human annotators disagree on sarcasm, which makes labeled data noisy and evaluation unreliable.

Most NLP research and data cover a handful of the world's 7,000 or so languages. Joshi et al. (2020) found that most languages have almost no labeled data, so methods that need millions of annotated examples do not transfer. Languages also differ structurally. Agglutinative languages such as Turkish and Finnish stack suffixes, so a single root yields thousands of word forms and word-level vocabularies explode. Chinese, Japanese, and Thai do not mark word boundaries with spaces, so segmentation becomes a task in itself. Multilingual models such as mBERT and XLM-R share one subword vocabulary across about 100 languages and transfer some skill from high-resource to low-resource languages.

Search ranks documents by relevance to a query. The formula scores a document $d$ for a query $q$ by summing, over each query term $t$, the term's TF-IDF weight in the document times its IDF, so rare query words that appear often in the document count most. BM25 refines this by saturating term frequency and normalizing for document length. Lexical matching fails on synonyms: a query for 'car' misses a page that only says 'automobile'. Dense retrieval embeds queries and documents as vectors and compares them, and DPR beat a BM25 baseline by 9 to 19 points in top-20 passage accuracy. Production systems combine both, then rerank the top results.

Machine translation maps a source sentence $x$ to a target sentence $y$. The formula factors the probability autoregressively: each target token $y_t$ is predicted from the source and the tokens $y_{<t}$ already produced, and decoding searches for a high-probability $\hat{y}$, usually with beam search. The field moved from word-for-word rules to statistical phrase tables and then to neural encoder-decoders; Google's 2016 neural system cut translation errors by an average of 60 percent compared with its phrase-based system. Today's Transformer models learn from hundreds of millions of sentence pairs. They still struggle with idioms, rare terminology, low-resource languages, and preserving tone.

Conversational systems carry on multi-turn dialogue. Task-oriented assistants help a user complete a goal, such as booking a flight or getting a refund, and are traditionally built as a pipeline: intent classification finds what the user wants, slot filling extracts the needed parameters, dialogue state tracking remembers what has been said, a policy decides the next action, and generation phrases the reply. Open-domain chatbots handle free conversation. Large language models fine-tuned with human feedback now perform most of these steps in one model, but production systems still extract structured intents and slots so they can call backend APIs reliably and check their actions.

Clinical notes, research papers, and patient records hold information that structured databases miss. Biomedical NLP extracts it: clinical NER finds diseases, drugs, doses, and symptoms; medical coding maps diagnoses to ICD codes for billing and statistics; relation extraction finds drug interactions in the literature; and trial matching links patients to eligibility criteria. General models struggle because clinical text is telegraphic and full of abbreviations, and because negation matters ('no fever' is not a fever). Models pretrained on biomedical text, such as BioBERT, which continued BERT's training on PubMed, outperform general models on these tasks. Privacy rules and the cost of errors make deployment harder than in most domains.