Natural Language Processing — cheatsheet, everything on one card.

A dense revision card for Natural Language Processing fundamentals: what NLP systems do, how meaning becomes vectors, how TF-IDF and PPMI weight evidence, how Word2Vec and GloVe learn embeddings, how n-gram language models assign probabilities, how smoothing rescues unseen text, how neural networks and neural language models work, and how sequence labelling moves from HMM and Viterbi to Bi-LSTM-CRF, BERT-style transformers and LLM-agent tagging. Keep the formulas visible, but learn the story behind each formula: NLP is mostly the art of turning messy language into useful probability, geometry and structure.

NLP map: language as signal, structure and meaning

overview

• Natural Language Processing is the computational treatment of human language. It sits between linguistics, algorithms, statistics and machine learning. A useful NLP system must handle spelling variation, morphology, syntax, semantics, discourse, ambiguity and context.
• Why it is hard: language is discrete on the surface but continuous in meaning. The same word can mean different things in different contexts, different words can mean almost the same thing, and sentences can be grammatical while still requiring world knowledge. “Bank,” “crane,” “light,” “book” and “charge” are classic ambiguity examples.
• Core pipeline: collect text → normalize/tokenize → represent units → learn patterns → predict labels, probabilities, rankings or generated text → evaluate against a task. Older pipelines used explicit modules; modern systems often learn representations end-to-end, but the old concepts still explain what the model is doing.
• Applications: search, spelling correction, machine translation, sentiment analysis, document classification, question answering, summarization, chatbots, named-entity recognition, information extraction, speech interfaces, grammar checking, text generation, code assistants and decision-support agents.
• Levels of analysis: characters handle spelling and subwords; words carry lexical meaning; phrases and syntax describe structure; semantics captures meaning; pragmatics and discourse connect language to speaker intent, context and previous text.

Lexical semantics and the distributional hypothesis

meaning

• Lexical semantics studies word meaning: synonymy, antonymy, hypernymy, hyponymy, meronymy, polysemy, homonymy and word sense. “Vehicle” is a hypernym of “car”; “wheel” is a meronym of “car”; “hot” and “cold” are antonyms.
• Distributional hypothesis: words that occur in similar contexts tend to have similar meanings. Instead of hand-writing every semantic relation, count where words appear and compare their context profiles. “Tea” and “coffee” are close because they share neighbors such as drink, cup, hot, milk, sugar and morning.
• Vector semantics: represent each word or document as a vector of numbers. Each dimension records evidence: a document count, a context count, a weighted association or a learned hidden feature. Semantic similarity becomes geometric similarity.
• Important distinction: sparse count vectors are interpretable but large. Dense embeddings are compact and powerful but less directly interpretable. Both use the same intuition: context is evidence for meaning.

Term-document and word-context matrices

counts

• Term-document matrix: rows are terms and columns are documents. Cell \(X_{t,d}\) stores how much term \(t\) appears in document \(d\). Each document column can be treated as a bag-of-words vector for retrieval or classification.
• Word-context matrix: rows are target words and columns are context words or context features. Cell \(X_{w,c}\) counts how often context \(c\) occurs near target \(w\), often within a fixed window such as two words left and two words right.
• Bag-of-words assumption: ignore word order and keep counts. This loses syntax, negation scope and phrase meaning, but it is robust, simple and surprisingly strong for topic and retrieval tasks.
• Sparsity: most words do not appear in most documents or contexts. Sparse matrices are memory-efficient when stored as triples, but direct similarity can be noisy unless weighting reduces the effect of common words.

Matrix	Rows	Columns	Best use
term-document	terms	documents	search, document similarity, classification features
word-context	target words	neighbor words/features	lexical semantics, similarity, embedding pretraining intuition
co-occurrence	words	words	association, analogy-like semantic neighborhoods

TF-IDF, PPMI and cosine similarity

weighting

• Cosine similarity compares direction rather than length: \(\cos\theta=\frac{a\cdot b}{\|a\|\|b\|}\). Two documents can be similar even if one is longer, because cosine normalizes by vector magnitude. The score is high when the same dimensions are strong in both vectors.
• Term frequency: raw count \(c(t,d)\) says how often term \(t\) appears in document \(d\). Log-scaled TF, \(\mathrm{tf}(t,d)=1+\log c(t,d)\), prevents repeated words from dominating linearly.
• Inverse document frequency: \(\mathrm{idf}(t)=\log\frac{N}{\mathrm{df}(t)}\), where \(N\) is number of documents and \(\mathrm{df}(t)\) is number of documents containing \(t\). Rare but informative words get higher weight; common words get lower weight.
• TF-IDF: \(\mathrm{tfidf}(t,d)=\mathrm{tf}(t,d)\times\mathrm{idf}(t)\). It rewards terms that are frequent in one document but not everywhere. This is the classic retrieval weighting idea.
• PMI: \(\mathrm{PMI}(w,c)=\log_2\frac{P(w,c)}{P(w)P(c)}\). It asks whether a word and context co-occur more than chance. Positive PMI means association; negative PMI means they co-occur less than expected.
• PPMI: \(\mathrm{PPMI}(w,c)=\max(\mathrm{PMI}(w,c),0)\). Negative values are clipped to zero because sparse negative evidence is often unreliable.

Word embeddings: Word2Vec, skip-gram, CBOW and negative sampling

embeddings

• Embedding idea: learn a dense vector for each word so words useful in similar prediction contexts have nearby vectors. The dimensions are not manually named; they emerge because the model must predict neighboring words or a target word from neighbors.
• Skip-gram: given a center word, predict surrounding context words. The softmax probability is \(P(w_o\mid w_i)=\frac{\exp(v'_{w_o}\cdot v_{w_i})}{\sum_{w=1}^{|V|}\exp(v'_w\cdot v_{w_i})}\). It is conceptually clean but expensive because the denominator sums over the whole vocabulary.
• CBOW: continuous bag-of-words predicts the center word from the average or sum of surrounding context vectors. CBOW is often faster and smoother for frequent words; skip-gram often works better for rare words because each center-context pair becomes a direct training signal.
• Negative sampling: replace huge softmax with a binary task: make real word-context pairs score high and random noise pairs score low. Objective: \(\log\sigma(v'_o\cdot v_i)+\sum_{k=1}^{K}\mathbb{E}_{w_k\sim P_n}\log\sigma(-v'_{w_k}\cdot v_i)\). It is the practical trick that made Word2Vec fast.
• What the vectors learn: syntactic and semantic regularities. Nearby words share topics or functions; vector offsets can encode relationships such as gender, tense, country-capital or comparative degree, though analogy behavior is not a guarantee of human-like understanding.

GloVe and visualizing embeddings with t-SNE

global + visual

• GloVe stands for Global Vectors. Instead of predicting local context windows one by one, it factorizes global co-occurrence statistics. The model tries to make vector dot products approximate log co-occurrence counts: \(J=\sum_{i,j}f(X_{ij})(w_i^T\tilde{w}_j+b_i+\tilde{b}_j-\log X_{ij})^2\).
• Why log counts: raw co-occurrence counts are extremely skewed. Log compression makes big counts manageable while preserving the fact that frequent co-occurrences carry signal.
• Weighting function: very rare co-occurrences can be noisy and very frequent ones can dominate. GloVe uses \(f(X_{ij})\) to balance those extremes.
• t-SNE visualization: t-distributed stochastic neighbor embedding maps high-dimensional vectors to two dimensions for inspection. It preserves local neighborhoods better than global distances, so clusters can be meaningful but exact spacing and axis directions should not be over-interpreted.
• Embedding caveats: embeddings inherit corpus bias, confuse senses when a word has multiple meanings, and may place antonyms near each other because antonyms often occur in similar contexts. Contextual models such as BERT reduce this by computing different vectors for the same word in different sentences.

N-gram language models: chain rule, MLE and Markov assumption

probability

• Language model: assigns a probability to a sequence of words. It can rank which sentence is more likely, predict the next word, support spelling correction, speech recognition, machine translation and text generation.
• Chain rule: any sentence probability can be decomposed exactly: \(P(w_1^n)=\prod_{i=1}^{n}P(w_i\mid w_1^{i-1})\). The problem is that long histories are too sparse to estimate directly.
• N-gram assumption: approximate the next word using only the previous \(n-1\) words. Bigram: \(P(w_i\mid w_1^{i-1})\approx P(w_i\mid w_{i-1})\). Trigram: condition on two previous words.
• MLE: estimate probability from counts: \(P_{\mathrm{MLE}}(w_i\mid w_{i-n+1}^{i-1})=\frac{C(w_{i-n+1}^{i})}{C(w_{i-n+1}^{i-1})}\). Count the full n-gram and divide by the count of its context.
• Sentence boundaries: add start and end tokens such as \(<s>\) and \(</s>\). They let the model learn how sentences begin and when to stop.

Smoothing, backoff and interpolation

unseen text

• Zero problem: MLE assigns zero probability to unseen n-grams. One zero makes the whole sentence probability zero, even if the sentence is perfectly reasonable. Smoothing redistributes probability mass from seen events to unseen events.
• Laplace/add-one: \(P_{\mathrm{add1}}(w\mid h)=\frac{C(h,w)+1}{C(h)+|V|}\). Add one to every possible continuation and add vocabulary size to the denominator. It is simple but often over-smooths.
• Add-k: \(P_{\mathrm{add}k}(w\mid h)=\frac{C(h,w)+k}{C(h)+k|V|}\), where \(0<k<1\) is common. Smaller \(k\) is less aggressive than add-one.
• Backoff: use the highest-order model when evidence exists; otherwise fall back to a lower-order model, usually with a discount so total probability remains valid.
• Interpolation: always mix multiple orders: \(P(w_i\mid h)=\lambda_3P(w_i\mid w_{i-2},w_{i-1})+\lambda_2P(w_i\mid w_{i-1})+\lambda_1P(w_i)\), with \(\sum_j\lambda_j=1\). This is smoother because every order contributes.
• Kneser-Ney intuition: a word is likely after a new context if it appears in many different contexts, not merely because it is frequent. “Francisco” is frequent in “San Francisco” but not a generally likely continuation; continuation counts fix that.

Evaluation: log probability, cross-entropy and perplexity

evaluation

• Use log probabilities: multiplying many small probabilities underflows, so language models usually sum logs: \(\log P(w_1^n)=\sum_{i=1}^{n}\log P(w_i\mid h_i)\).
• Perplexity: \(\mathrm{PP}(W)=P(w_1^N)^{-1/N}=\sqrt[N]{\frac{1}{P(w_1^N)}}\). Lower is better. Intuitively it is the average branching factor: how many choices the model feels it has at each word.
• Cross-entropy link: if \(H(W)=-\frac{1}{N}\sum_i\log_2P(w_i\mid h_i)\), then \(\mathrm{PP}=2^{H(W)}\). A lower cross-entropy means a lower perplexity.
• Evaluation caveat: perplexity compares models on the same tokenization and test data. It does not always predict downstream task quality or human usefulness, especially for dialogue and instruction-following systems.

Neural networks: units, activations, XOR and feedforward computation

neural basics

• Neuron: compute a weighted sum and pass it through a non-linear activation: \(z=w\cdot x+b,\ a=f(z)\). Without non-linearity, stacked layers collapse to one linear transformation.
• Activations: sigmoid \(\sigma(z)=\frac{1}{1+e^{-z}}\) maps to \((0,1)\); tanh maps to \((-1,1)\); ReLU \(\max(0,z)\) is simple, sparse and helps deep networks train. Sigmoid is interpretable as a probability for binary output, but it can saturate.
• XOR problem: a single linear separator cannot solve XOR because positive examples occupy opposite corners. A hidden layer creates intermediate features that make the final separation possible. This is the standard motivation for multilayer networks.
• Feedforward network: information flows input → hidden layers → output. Each layer computes \(h^{(l)}=f(W^{(l)}h^{(l-1)}+b^{(l)})\). Training adjusts weights to reduce loss by gradient descent and backpropagation.
• Softmax classifier: \(P(y=k\mid x)=\frac{e^{s_k}}{\sum_j e^{s_j}}\). It converts class scores into a probability distribution over labels.

Neural language models, LLM/SLM and prompt engineering

modern language models

• Neural LM shift: replace sparse n-gram tables with embeddings and neural networks. Similar contexts share parameters, so the model generalizes beyond exact observed n-grams. A neural LM still estimates \(P(w_i\mid \text{context})\), but context is encoded as vectors.
• Small language models and large language models: the difference is mainly scale, data, architecture capacity and deployment target. SLMs are cheaper and easier to run locally; LLMs tend to handle broader tasks and longer instructions but require more compute and careful safety controls.
• Prompt engineering: specify task, context, constraints, examples and output format. Good prompts reduce ambiguity. For classification, include labels and criteria. For extraction, define schema. For reasoning, ask for intermediate checks but verify final answers separately.
• Failure modes: hallucination, prompt sensitivity, hidden bias, brittle formatting, stale knowledge and overconfident answers. Use retrieval, constrained decoding, evaluation sets, human review and clear refusal boundaries where errors matter.

POS tagging with HMMs: transition, emission and decoding

sequence labels

• Part-of-speech tagging assigns a grammatical tag to each token: noun, verb, adjective, adverb, determiner, pronoun, preposition and so on. Tagging is useful because downstream systems need syntactic hints before deeper parsing or extraction.
• Ambiguity: many words have multiple tags. “Book” can be noun or verb; “flies” can be noun or verb. Context resolves the ambiguity.
• HMM ingredients: transition probability \(P(t_i\mid t_{i-1})\) says which tags follow which tags. Emission probability \(P(w_i\mid t_i)\) says which words are likely under a tag.
• Local tag choice: \(\hat{t}=\arg\max_t P(w\mid t)P(t)\) combines how likely the word is for a tag with how likely the tag is overall. Full tagging uses sequence context, not just this local decision.
• HMM joint probability: \(P(w_1^n,t_1^n)=\prod_{i=1}^{n}P(w_i\mid t_i)P(t_i\mid t_{i-1})\), usually with a start tag. The best tag sequence maximizes this product.

Viterbi, MEMM and bidirectionality

decoding

• Viterbi: dynamic programming for the single best hidden tag path. Recurrence: \(v_t(j)=\max_i v_{t-1}(i)a_{ij}b_j(o_t)\). Store backpointers so the best final path can be reconstructed.
• Why dynamic programming: enumerating every tag sequence is exponential in sentence length. Viterbi reuses partial best paths and runs in roughly \(O(nT^2)\), where \(n\) is tokens and \(T\) is number of tags.
• MEMM: maximum entropy Markov models use discriminative classifiers for transitions, so they can use rich features such as suffixes, capitalization, previous word and surrounding tokens. They model \(P(t_i\mid t_{i-1},x)\), but can suffer from label bias because each state normalizes locally.
• Bidirectionality: a tag may depend on both left and right context. In “to book flights,” the following word helps make “book” a verb. Bidirectional models read the sequence forward and backward before predicting tags.

Bi-LSTM-CRF, transformers, BERT/RoBERTa and LLM-agent tagging

modern tagging

• Bi-LSTM-CRF idea: a bidirectional LSTM creates contextual token representations; a CRF layer chooses the globally best tag sequence using learned transition scores. The LSTM understands token context, while the CRF enforces sequence-level consistency such as not placing an inside-entity tag after an impossible previous tag.
• CRF score: a path receives emission scores from token features plus transition scores between labels. Decoding again uses Viterbi-style dynamic programming, but scores come from a neural network rather than count tables.
• Transformer: self-attention lets every token directly attend to other tokens. This solves the long-distance bottleneck of strict recurrence and enables large pre-trained models.
• BERT: bidirectional encoder representations from transformers. It is pre-trained with masked language modelling and then fine-tuned for tagging by adding a classifier over token representations. RoBERTa improves training choices, data and masking strategy while keeping the encoder idea.
• LLM-agent tagging: an LLM can tag text through prompting, tool use, retrieval, schema validation and self-checking. This is flexible for low-data settings, but production tagging still needs deterministic schemas, test sets, confidence checks and fallback handling.