Mid-Semester Exam Revision: NLP Foundations

This revision covers the complete pre-mid-semester syllabus for Natural Language Processing: the introductory module, vector semantics and TF-IDF, word embeddings with skip-gram negative sampling, statistical n-gram language modeling, and neural language models with an introduction to large language models. Along the way it collects every piece of exam guidance, worked computation, and clarification that came up during the session.

8.1 Introduction to NLP: Applications, Ambiguities, and Levels of Understanding

The first module is the introduction to NLP, and it is the easiest place to gain marks because the questions here are application-oriented rather than computational. The recap of this module covers what NLP is, where it is relevant, why it is worth studying, the interesting applications, the different roles NLP engineers can play, and a quick history of the field. For this module the reference book is the James Allen book, which is available online. Master the vocabulary and the example types in this module, and the conceptual marks follow cheaply.

8.1.1 What the Module Covers

The module sets out the core question: what is Natural Language Processing? NLP (the area of AI concerned with making machines understand and generate human language) is not one single technique but a whole stack of techniques, and the module first maps the territory. It covers where NLP is relevant, why we study it, and what the interesting applications are. It also maps the different roles an NLP engineer can play in industry, and surveys real-world applications that make the area useful. A quick history of the field rounds out the introduction. The reason this module exists is to give a clear picture of what the course content covers and why each later topic matters, so the rest of the syllabus does not look like a pile of unrelated algorithms.

A case study kind of example was used to understand the complexity of human language. This is the module's central message: natural language is hard, and that difficulty is what makes NLP interesting. The module walks through the different interesting applications, and the challenges that make natural language such a difficult problem, including the ambiguities that exist in language, with examples of each type.

The different roles an NLP engineer can play in industry all sit on this foundation: engineers who build and train models, engineers who ship and serve them, data scientists who turn language data into features, and specialists who design the human-facing applications. For the exam, what matters is being able to say, for a given problem, whether it is an NLP application and how you would implement it at a basic level — the applications themselves, not their internal machinery.

8.1.2 Why Natural Language Is Hard

Human language is genuinely hard for machines. The module opens with a small case study to show the complexity of human language, so that the difficulty of NLP is felt rather than asserted. Think about a simple booking dialogue: a customer says "I want to book a table for two tonight", and the system must decide what "tonight" means (which day, which time zone), what "two" attaches to (people, not tables), and whether "book" is a verb or a noun in this sentence. Each of those decisions is automatic for a human and opaque for a machine.

The challenges of NLP are the reason the field exists: language is ambiguous (one string of words, several meanings), context-dependent (the same word means different things in different surroundings), and full of exceptions (every rule of grammar has counterexamples, from irregular plurals to idioms). A machine must handle all of these to be useful. The difficulty is not a bug in the field; it is the field's defining problem, and every later topic in the syllabus — vector semantics, language models, neural networks — is a different weapon aimed at it.

8.1.3 Ambiguities in Natural Language

Ambiguity is the property of language where one piece of text can carry several meanings. The module distinguishes the different types of ambiguities and expects students to understand each type in depth, with examples. The differences between the different ambiguities matter: a word can be ambiguous on its own (lexical ambiguity), and a sentence can be ambiguous in structure or in what it refers to. Knowing which type of ambiguity an example shows, and why, is exactly the kind of conceptual question this module produces.

The main types to recognize:

• Lexical ambiguity — a single word carries several meanings. "Bank" is a financial institution or a riverbank; "can" is a container, a modal verb, or the verb "to put in a can". The classic classroom sentence "I can can the can" uses all three roles of can in one sentence, and a machine must use context to sort them out.
• Structural (syntactic) ambiguity — a sentence has more than one possible grammatical structure. In "The man saw the boy with the telescope", the telescope can belong to the man (he looked through it) or to the boy (the boy was holding it). Same seven words, two different arrangements of who owns what.
• Referential (anaphoric) ambiguity — a pronoun or phrase has more than one possible antecedent. In "Ravi told Kiran that he had passed", he could refer to either person until the wider context pins it down.
• Pragmatic ambiguity — the same sentence carries different intended meanings in different situations. "Can you pass the salt?" is a question about ability in form, but a request for action in practice. The intent, not the literal words, decides the meaning.

For the exam, be ready to name the type of ambiguity in a given example and justify the choice by pointing at exactly which part of the sentence carries the multiple readings.

8.1.4 Levels of Language Understanding

Language understanding happens at several levels, and the module asks students to explain each level and how the levels differentiate, with examples. The standard stack of levels runs from the sounds of language up to meaning in context:

• Phonetics — the physical sounds of language and how they are produced and perceived.
• Phonology — how sounds combine and pattern in a particular language.
• Morphology — word structure: how roots, prefixes, and suffixes build words (un-break-able).
• Syntax — sentence structure: how words combine into grammatical sentences ("the cat sat" is well-formed; "cat the sat" is not).
• Semantics — meaning: what words and sentences denote, independent of who says them.
• Discourse — multi-sentence structure: how sentences link together, including coreference, where later mentions refer back to earlier ones ("Ravi bought a phone. He charged it overnight" — he and it point backward).
• Pragmatics — meaning in context and intent: what a speaker means by an utterance in a situation, beyond the literal words.

Some texts merge phonetics and phonology into one "sounds" level or add a separate lexical level for word knowledge, which is why you may see the stack counted as six levels in one book and seven in another; the James Allen diagram used in the module names the full set above, and any enumeration that names these seven layers is the complete answer. The exam asks for the levels, an example of each, and how the levels differ — the differences matter more than the count.

The same stack shows up inside every NLP application in the same shape: there is an understanding part, and then a generation part. A conversational AI system has to understand what the user's intent is and what the entities are, and then has to generate the response. That is exactly an encoder-decoder pattern: understand first, then generate. When you describe any NLP system at a basic level, this two-phase pattern is the skeleton to draw.

8.1.5 Classical, Modern, and Hybrid NLP Systems

The module contrasts the architecture of a classical NLP system with modern NLP systems, and introduces hybrid systems. A classical NLP system runs explicit pipelines: tokenization, parsing, feature engineering, and rules. Every stage is hand-designed: split the text into tokens, parse the grammar, engineer the features, apply the rules. A modern NLP system leans on learned representations and large language models: instead of hand-designed rules, the model learns patterns from data. A hybrid NLP system combines the two: for lighter processing it is a good idea to use classical NLP pipelines; for advanced reasoning kind of tasks, use LLMs; and for post-processing, use guardrails and rules, which are again the classical aspect.

This hybrid pattern is the recommended way to build NLP applications, and it is the same idea for every concept studied in the course: light work goes to the cheap classical pipeline, hard reasoning goes to the large model, and safety checks wrap around the outside. In an exam answer about how you would implement an NLP application, sketching this split — pipeline for the simple parts, LLM for the reasoning parts, guardrails around the edges — is the pattern the course teaches.

8.1.6 Evaluating NLP Systems

Another important part of the module is evaluating NLP systems: what are the different metrics used for NLP? It is not just accuracy. There are task-specific measures such as accuracy and the ROUGE score, F1 score, and considerations of data and generalization. Simple problems on F1 score, accuracy, precision, and recall are possible, because precision and recall have been practiced time and again across courses.

The distinction to internalize: accuracy is the share of all predictions that are right; precision is the share of positive predictions that are right; recall is the share of actual positives that were found; and the F1 score combines precision and recall. With $TP$ true positives (correct positive calls), $FP$ false positives (negative cases called positive), $FN$ false negatives (positive cases missed), and $TN$ true negatives:

$$\text{accuracy}=\frac{TP+TN}{TP+FP+FN+TN},\text{precision}=\frac{TP}{TP+FP},\text{recall}=\frac{TP}{TP+FN}$$

$$\text{F1}=\frac{2\times \text{precision}\times \text{recall}}{\text{precision}+\text{recall}}$$

8.1.7 Student Questions and Answers

8.1.8 Exam Notes

Recap and bridge. This module gives the vocabulary for everything that follows: language is ambiguous at several levels, systems are understood in an encoder-decoder shape, and evaluation means more than accuracy. The next module starts the first big tool for taming that ambiguity — representing words as vectors, so that meaning becomes geometry a machine can compute with.

8.2 Vector Semantics: Frequency-Based Embeddings and TF-IDF

The core idea of this module: semantics can be better represented for understanding if words are represented as vectors. If you want to find the semantic relations among words, vectors represent them better. Lexical semantics — how words relate — covers relations like synonymy, similarity, and antonymy, and these are quite intuitive, not something to memorize. The marks here come from the math: a small numerical problem on cosine similarity or TF-IDF is the expected shape.

8.2.1 Why Vectors Represent Words

The intuition behind vector semantics: because of context words and because of vector representation, any word can be represented in a multi-dimensional vector space, and relations among words can then be captured mathematically. This makes similarity easy for machines. Word embedding means converting the textual word representation into a vector representation; they are called embeddings because the words are embedded in the vector space. If words are embedded in a vector space and plotted, words similar to each other will be embedded closer to each other in the vector space.

There are mainly two families of word embeddings. The frequency-based approach counts occurrences in the corpus, computing term frequency and IDF vectors, and can also build co-occurrence vectors from words lying close to each other in the training corpus. The prediction-based approach learns embeddings by training a model to predict, and it is covered in detail through skip-gram negative sampling, with CBOW and GloVe as relatives.

The basic idea of representing words as vectors comes from a simple representation: a set of documents and a set of words, with numbers indicating how many times each word appears in each document. These numbers are the term frequencies. This matrix can represent a vector for a document or a vector for a word, and both representations are possible. Document vectors help understand which documents are similar to each other, which is useful in many applications including web search. Reading the same matrix row-wise gives each word in the training corpus a vector made of its term frequencies across documents, which helps understand which words are similar to each other or lie in the same semantic space.

A related representation is the co-occurrence matrix: take the matrix of all words and compute the frequency of words occurring close to each other within a plus and minus context window. This gives a vector representation of every word with respect to the other words in the training corpus. This is the same concept later used in skip-gram negative sampling.

8.2.2 Cosine Similarity

To compute the mathematical similarity among vectors, you cannot just subtract vectors and find a distance. The vector similarity measure is the dot product. But the dot product is not normalized by the size of the vectors, so the measure used is cosine similarity, where the dot product is divided by the size of the vectors. For two vectors $v$ and $w$:

$$\cos (v,w)=\frac{v\cdot w}{\Vert v\Vert \Vert w\Vert }$$

where $v\cdot w={\sum }_i{v}_i{w}_i$ is the dot product (multiply matching entries and add) and $\Vert v\Vert =\sqrt{{\sum }_i{v}_i^2}$ is the size (magnitude) of the vector. The verbal description from the recap: "you cannot just subtract it and find the distance, you need a vector similarity measure that is the dot product; dot product is not normalized by the size, and that is why we go for cosine similarity, where we divide by the size of the vector." Dividing by the size makes the score normalized, independent of the length of the document.

The dot product alone is a poor similarity measure because it rewards long vectors: a word like "the" occurs often, so its vector has big entries and a big magnitude, and its dot products are inflated by pure frequency, not by meaning. Dividing by both magnitudes removes that inflation and leaves the angle between the vectors — the direction of agreement — as the score. For non-negative count vectors the cosine ranges from 0 (perpendicular, no shared context) to 1 (same direction, same context); opposite directions give $-1$.

A lesser cosine similarity value indicates that the two words are not similar to each other. If the value is close to one, the words are similar to each other and lie in the same semantic space. Students should be able to explain whatever output values they get — the exam asks for the calculation and the interpretation of the result, not just the number.

8.2.3 Term Frequency and Inverse Document Frequency

Term frequency is the occurrence of each term in each document, meaning the count of how many times a term occurs in a document. Two refinements are applied. First, since the raw counts can be very large, a logarithm squashes the values. Second, one is added to avoid zeros, so that a term occurring in a document does not get a zero TF value. Following the Jurafsky and Martin convention:

$$w_{t,d}=1+{\log }_{10}(t{f}_{t,d})\text{for }t{f}_{t,d}>0$$

where $t{f}_{t,d}$ is the raw count of term $t$ in document $d$ and $w_{t,d}$ is the log-squashed term frequency weight. The plus-one applies only when the term occurs: for a term that does not appear in the document, $w_{t,d}=0$. Some texts write the squash as ${\log }_{10}(t{f}_{t,d}+1)$, which is the same idea in slightly different form — it also keeps every occurring term above zero and compresses large counts. On the exam, use the form the question specifies; the standard form in the lecture is $1+{\log }_{10}(t{f}_{t,d})$.

The log matters because raw counts are skewed: a word with 1000 occurrences and a word with 10 occurrences differ by a factor of 100 in raw count but only by a factor of about 3 after the log squash. That stops a very frequent word from dominating the vector by sheer count.

A normalized variant also exists: the raw count divided by the total number of words in the document. This is the normalization used when computing cosine similarity. Advanced normalized versions like BM25 exist but are not part of this curriculum.

Document frequency $d{f}_t$ is how many documents contain the term. This differs from collection frequency, which counts every occurrence of the word across every document. Document frequency only checks whether the term appears in a document at all: out of 100 documents, one of them may have the term Romeo, and out of 100 documents, 31 of them may have the term action — those are document frequency counts, presence only, not multiplicity.

Inverse document frequency captures the rarity of the term. Term frequency alone cannot capture rarity: frequent terms like "the" get more weight in a document, which is not useful. If a document is about Sachin Tendulkar, the word Sachin Tendulkar may not occur frequently, and words like good, player, and cricket may appear more often — but the document should give more weight to Sachin Tendulkar. That is what inverse document frequency captures. The formula:

$$id{f}_t={\log }_{10}\left(\frac{N}{d{f}_t}\right)$$

where $N$ is the total number of documents and $d{f}_t$ is the document frequency of term $t$. If a term occurs in fewer documents, the term is more important, so the inverse is taken. The inverse is taken with respect to the total number of documents. The log base 10 is for squashing the values.

The full TF-IDF weight combines both:

$$w_{t,d}=(1+{\log }_{10}t{f}_{t,d})\cdot {\log }_{10}\left(\frac{N}{d{f}_t}\right)$$

The combination rewards words that are frequent locally (high TF) but rare globally (high IDF) — exactly the words that define what a document is about. A worked example computed TF-IDF values from the raw values, producing decimal values; the resulting vector for the word battle was shown alongside vectors for other words. The log also helps squash the values to decimal magnitudes.

8.2.4 Sparse Versus Dense Representations

The advantage of the frequency-based approach is that it is easy, it does not take much computation, and it is faster to compute. The disadvantages are the many zeros and the long vector length for each word.

The alternative is a dense vector representation with short vector length for each word. Dense models are parameterized by their embedding dimension: GPT-4 has token embeddings of 1024 dimensions, while GPT-3 and earlier models had 768 dimensions. Some small language models have 300 dimensions, and Andrew Ng recommends 300 as a practical dimension. Depending on the model size, the dimensions of the vectors vary for each of the input words, also called tokens. (One slide in the recap attributes 1024 dimensions to GPT-4, and a later remark extends that to newer models; the numbers stand as stated — the takeaway is the ladder: about 300 for small models, 768 for the GPT-3 era, 1024 for the newer generation.)

Dense vectors were built to fix exactly the two complaints above: no more zeros to store, and short enough vectors that similarity is cheap to compute.

8.2.5 Student Questions and Answers

8.2.6 Exam Notes

Recap and bridge. Sparse vectors turn words into positions in a huge, mostly-empty space, and TF-IDF weights make the positions meaningful by rewarding rare, distinctive words; cosine similarity then measures the angle between any two positions. The catch is scale — 100,000 dimensions per word. The next module throws out the zeros and learns short, dense vectors instead, and the algorithm it uses is skip-gram negative sampling.

8.3 Word2Vec and Skip-Gram with Negative Sampling

Word embedding is the slightly complex topic of the pre-mid-semester syllabus. The sparse vectors have the challenges above, so the course moves to denser vector representations, and the detailed mathematical problem solved in class is skip-gram negative sampling (SGNS). A similar approach is used for CBOW, and GloVe was discussed briefly. Contextual word embeddings involve mathematical problems too, but those belong to the post-mid-semester part.

8.3.1 Self-Supervision and One-Hot Encoding

Word2Vec algorithms are self-supervised: training data is needed, but no human labels are needed for that training data. The SGNS algorithm uses the data itself to automatically create positive and negative samples through self-supervision. The labels the model trains against come from the corpus structure, not from a human annotator: if two words appear next to each other in real text, that appearance is itself the label.

Before the embeddings come the one-hot encoding of words. A one-hot vector is equal to the size of the vocabulary: every word in the one-hot representation is a vector the size of the unique vocabulary, with a 1 at the position where that word occurs in the unique vocabulary and 0 everywhere else. One-hot encoding is not suitable for finding semantic similarity, but it serves as a base: multiply it with the feature-dimension matrix to get the vector representation for each word in the dimensions of the features. The names of the features are immaterial — they are learned by the deep learning algorithms. What matters is the number of features: Andrew Ng recommends 300 dimensions, GPT-2 and GPT-3 have 768, and newer models have 1024 dimensions for each of these token IDs.

Multiplying the one-hot vector by the weight matrix automatically reduces the dimension of the word embedding. In the in-class example the one-hot had dimension 1 by 4 (4 columns), the weight matrix was 4 by 5, and the resulting vector was 1 by 5:

$$h=x\cdot W,x\in \{0,1{\}}^{1\times 4},W\in {\mathbb{R}}^{4\times 5},h\in {\mathbb{R}}^{1\times 5}$$

More generally, if the unique vocabulary size is 50,000, the sparse vector is $1\times 50,000$, and a weight matrix of $50,000\times 5$ reduces this $1\times 50,000$ vector to $1\times 5$. That is the advantage: the sparse vectors are reduced into the denser vector representation.

8.3.2 How SGNS Builds Its Training Data

The first step of SGNS is to create the self-supervised data. Pick a target word, pick the context window of plus minus 5 words, and try to predict whether each word is a context word for the given target or an out-of-context word. This algorithm comes from a very innovative and important research paper by Google. The in-class example took apricot as the target with a plus minus 2 word context window: the words inside that window are positive context words, and all words lying outside the context window are considered negative context words. This is how positive examples and corresponding negative examples are generated.

Once the examples exist, the problem is posed as a classification problem. The final output classification — whether a word is context or not — is not the interest. The interest is in learning the weights of the in-between features, the weight matrix. The classification task is scaffolding: it forces the weights to absorb the useful statistics of co-occurrence, and when training is done, the weights are the embeddings.

8.3.3 Probabilities, Loss, and Gradient Updates

The classifier is simple logistic regression treated as binary classification: context words are positive, out-of-context words are negative. For similarity, a sigmoid function is needed: similarity alone is not enough, so the sigmoid turns the dot product into probability values. Giving a probability of being a context word makes this a probabilistic model, which is more useful in real-world applications than a deterministic model. The standard sigmoid from logistic regression:

$$\sigma (z)=\frac{1}{1+e^{-z}},z=c\cdot t$$

where $c$ is the context word embedding and $t$ is the target word embedding; $c\cdot t$ is their dot product, a scalar. So the probability that $c$ is a positive context word of target $t$ is:

$$P(+)=\sigma (c_{pos}\cdot t)=\frac{1}{1+e^{-(c_{pos}\cdot t)}}$$

The probability for a negative context word is one minus the positive probability:

$$P(-)=1-\sigma (c_{neg}\cdot t)=\sigma (-c_{neg}\cdot t)=\frac{1}{1+e^{+c_{neg}\cdot t}}$$

The middle step uses the sigmoid symmetry $1-\sigma (x)=\sigma (-x)$, which is the single most important identity for this topic: the negative case runs the same dot product through the sigmoid with a plus sign inside. The dot product is the same; the sign is only added inside the sigmoid.

Standard gradient descent learns the word embeddings: each word in the corpus gets both a target word embedding and a context word embedding, because a word can be a target in one pair and a context for other words. The final word embedding for a word is a combination of its target word embedding and its context word embedding.

The training objective is to maximize the similarity (probability) between target and positive context, and minimize the similarity between the word and negative context words. The loss function takes a log of the probabilities, because the log converts a product into a sum, which is easier to calculate; and because it is a loss to minimize, there is a negative sign. This is cross entropy, with $K$ negative examples:

$$L=-\left[\log \sigma (c_{pos}\cdot t)+\sum _{k=1}^K\log \sigma (-c_{ne{g}_k}\cdot t)\right]$$

Substituting the sigmoid probabilities mechanically gives the expanded form:

$$L=-\left[\log \frac{1}{1+e^{-(c_{pos}\cdot t)}}+\sum _{k=1}^K\log \frac{1}{1+e^{+c_{ne{g}_k}\cdot t}}\right]$$

To update the embeddings, take the partial derivatives of this loss with respect to the three variables — the positive context embedding, the negative context embeddings, and the target embedding. These are like the three weights in the gradient descent algorithm. The derivation itself does not need to be memorized; only the final formulas matter. For those who want to see where they come from, the two building blocks are $\frac{d}{dz}\log \sigma (z)=1-\sigma (z)$ and $\frac{d}{dz}\log \sigma (-z)=-\sigma (z)$ (the second follows from the symmetry identity), with $\frac{d}{dz}\sigma (z)=\sigma (z)(1-\sigma (z))$ behind both. For the positive context, the derivative is the predicted minus the actual, where the actual for positive is one, which is why the formula has the minus one:

$$\frac{\partial L}{\partial c_{pos}}=\left[\sigma (c_{pos}\cdot t)-1\right]t$$

For each negative context word, the actual is zero:

$$\frac{\partial L}{\partial c_{ne{g}_k}}=\sigma (c_{ne{g}_k}\cdot t)t$$

For the target vector, both positive and negative contributions appear, since the target appears in both parts of the loss:

$$\frac{\partial L}{\partial t}=\left[\sigma (c_{pos}\cdot t)-1\right]c_{pos}+\sum _{k=1}^K\sigma (c_{ne{g}_k}\cdot t)c_{ne{g}_k}$$

Note the sign convention: in the negative terms the sigmoid is computed with the positive sign inside, $\sigma (c_{ne{g}_k}\cdot t)=1/(1+e^{+c_{ne{g}_k}\cdot t})$, because the probability of a negative sample is one minus the positive probability. The dot product itself is the same; the sign is only added inside the sigmoid. The derivative forms above match the standard treatment in Jurafsky and Martin, chapter 6.

For the positive term, read the factor $\sigma (c_{pos}\cdot t)-1$ as predicted minus actual: the actual target for a positive pair is 1, so the factor is $\hat{P}-1$, which is why the formula carries the minus one. For a negative pair the actual target is 0, and the factor is simply $\sigma (c_{neg}\cdot t)=\hat{P}-0$.

The weight update uses gradient descent with learning rate $\eta$:

$$t_{new}=t_{old}-\eta \frac{\partial L}{\partial t}$$

In practice the algorithm loops over many iterations and many positive examples; the in-class demonstration ran only one iteration, and the exam likewise asks for a single iteration.

8.3.4 Worked Example: Learning the Embedding for "net"

8.3.5 CBOW and GloVe at a Glance

CBOW uses a similar self-supervised approach to SGNS, and there will be no mathematical problems on CBOW — it is conceptual only. CBOW runs the skip-gram idea in the opposite direction: instead of predicting the context words from the target, it averages (or sums) the context word vectors and predicts the target word. GloVe was discussed briefly: it is conceptual, and at most a very minor problem could appear. Where SGNS learns from local context windows, GloVe learns from the global co-occurrence statistics of the whole corpus, fitting vectors so that ratios of co-occurrence probabilities are captured.

Reviewing the CBOW and GloVe walkthroughs is enough for the exam; the marks and the math sit with SGNS.

8.3.6 Student Questions and Answers

8.3.7 Exam Notes

Recap and bridge. SGNS turns co-occurrence into a binary classification game: pull the target toward its real context words and push it away from sampled negatives, one gradient-descent step at a time. The table procedure above is the whole algorithm in miniature. The next module switches from learning word meaning to scoring whole word sequences — statistical language modeling with n-grams, smoothing, and perplexity.

8.4 Statistical Language Modeling: N-Grams, Smoothing, and Perplexity

Language modeling is a broad topic with many real-world applications, and it is not that difficult a concept. The exam problem on this module is not necessarily a complete four-mark problem everywhere; it is also possible to get a combination of a mathematical problem and an application-oriented question. The core skill to practice is counting from a corpus and substituting values into the formulas.

8.4.1 The Language Modeling Problem

Language modeling is predicting the next set of words given a set of words. To model any language means to model how sentences are generated; communication is generating a well-formed sentence, and language modeling does that for you. It does so using statistical techniques like the probabilistic n-gram, or using neural language modeling with transformers and LLMs.

To predict a sequence of words, the standard Bayes rule computes the joint probability of the sequence. Because a sequence of words follows one after another, the joint probability of all the words is what is wanted. The chain rule of probability expands it:

$$P(w_1,w_2,\dots ,w_n)=P(w_1)\cdot P(w_2\mid w_1)\cdot P(w_3\mid w_1,w_2)\cdots P(w_n\mid w_1,\dots ,w_{n-1})$$

Each factor is one word's probability given all the words before it: the chance of the first word, times the chance of the second given the first, and so on. This is exact probability — no approximation yet.

The challenge: to compute these probabilities in the training data, that much data is needed. Longer context sentences do not repeat, so at most bigram or trigram values exist in a corpus; 5-gram or 6-gram values will not be available. A four-word history like "its water is so" is already rare enough that its counts are unreliable or zero, and the chain rule demands exactly those rare counts. The solution is the Markov assumption: the current word only depends on the previous one word or the previous two words. Depending on the previous one word gives the bigram probability; depending on the previous two words gives the trigram probability:

$$P(w_n\mid w_1,\dots ,w_{n-1})\approx P(w_n\mid w_{n-1})\text{(bigram)}$$

$$P(w_n\mid w_1,\dots ,w_{n-1})\approx P(w_n\mid w_{n-2},w_{n-1})\text{(trigram)}$$

The approximation trades a little accuracy for counts we can actually measure: the bigram only needs the pair $(w_{n-1},w_n)$ to have appeared, which common pairs do.

The unigram is also a possibility but it captures no context at all, so unigram is not preferred unless no bigram or trigram values are available — only then does one fall back to unigram probability. A unigram model treats a sentence like a bag of words: $P(\text{I want to eat healthy food})\approx P(\text{I})P(\text{want})P(\text{to})P(\text{eat})P(\text{healthy})P(\text{food})$.

For computing sequence probabilities, log values are generally used instead of probabilities, for faster computation. When computing the probability of a complete sequence, the log values are multiplied into a sum. This matters in practice because the raw product of many small probabilities underflows to zero on a computer: $\log (p_1{p}_2{p}_3)=\log p_1+\log p_2+\log p_3$ replaces a shrinking product with a stable sum of negative numbers. The Google Ngram corpus makes such counts readily available.

8.4.2 Counting Bigrams and Trigrams

Given a corpus, the bigram and trigram probabilities are computed from a count table. The table has the corpus frequencies — the unigram counts, how many times each word occurs in the corpus — alongside the bigram counts, how many times two words occur together, the second word coming after the first. For example, the count for want coming after want is 0. Each bigram probability is the count of the pair divided by the unigram count of the first word:

$$P(w_n\mid w_{n-1})=\frac{C(w_{n-1},w_n)}{C(w_{n-1})}$$

where $C(w_{n-1},w_n)$ is the bigram count and $C(w_{n-1})$ is the unigram count of the previous word. This is the maximum likelihood estimate: "count the pair, count the first word, divide".

Zero probability is a problem, and to avoid zero probabilities Laplace smoothing is applied. A single zero in the product makes the whole sentence probability zero: $P(\text{sentence})=(\dots )\times 0\times (\dots )=0$. The zero is not "very unlikely", it is "cannot happen", which is almost never true for a sensible phrase — and it also makes perplexity infinite, so evaluation breaks too.

Sentence probability: once the individual bigram probabilities exist, the probability of any sentence is computed by multiplying all of these probabilities together, giving the overall probability for that particular sentence. Start and end tags: if the question includes the start and end of the sentence, include them in the counts; if the question does not mention them, make an assumption and write it out. Read the question properly before answering, and write any assumption explicitly — otherwise an ambiguous answer cannot earn marks. For example, a bigram model scores "I want english food" as $P(\text{I}\mid ⟨s⟩)\times P(\text{want}\mid \text{I})\times P(\text{english}\mid \text{want})\times P(\text{food}\mid \text{english})\times P(⟨/s⟩\mid \text{food})$, where $⟨s⟩$ and $⟨/s⟩$ mark the start and end of the sentence.

8.4.3 Laplace Smoothing, Interpolation, and Backoff

Laplace smoothing (add-one smoothing) adds one in the numerator and the vocabulary size in the denominator:

$$P_{Laplace}(w_n\mid w_{n-1})=\frac{C(w_{n-1},w_n)+1}{C(w_{n-1})+V}$$

where $V$ is the vocabulary size. If three sentences are given, the unique vocabulary across those sentences gives $V$ — just count the unique words. If the question asks to perform Laplace smoothing, or if there is a zero anywhere, add the one in the numerator and the vocabulary size in the denominator to compute the probabilities.

Why add $V$ below? Because we added 1 to each of the $V$ possible next words, the denominator must grow by $V\times 1=V$ so that every row still sums to 1. It gives every unseen pair a small head start of one imaginary sighting: nothing keeps a zero probability, common pairs lose a little mass, and rare pairs gain a little.

Laplace smoothing has a drawback: it manipulates the counts. When the joint counts are substituted into the formula, the counts get changed because of the added one and the vocabulary size, and the counts change substantially, which is not desirable in some applications. With a vocabulary of tens of thousands of words, the $+V$ swamps the real counts.

The workarounds that avoid manipulating the counts are interpolation and backoff. In interpolation, lambda values weight the three levels, giving more priority to the trigram, less to the bigram, and less to the unigram:

$$\hat{P}(w_n\mid w_{n-2},w_{n-1})={\lambda }_{1}P(w_n\mid w_{n-2},w_{n-1})+{\lambda }_{2}P(w_n\mid w_{n-1})+{\lambda }_{3}P(w_n)$$

where ${\lambda }_1,{\lambda }_2,{\lambda }_3$ are the interpolation weights. If the exam gives the lambda values, substitute them to calculate the probability; otherwise make an assumption. The lambda values can also be learned using validation data. By the standard convention the weights sum to one, ${\lambda }_1+{\lambda }_2+{\lambda }_3=1$, which keeps the blended estimate a proper probability; if the lecture materials ever present weights that do not sum to one, that is a simplified example, and the sum-to-one form is the one used in practice.

Backoff is a similar concept to interpolation but without the combination: use the trigram if it is available; if the trigram is not available, go for the bigram; if the bigram is not available, go for the unigram. Interpolation always takes a combination of trigram, bigram, and unigram; backoff falls down the hierarchy only when a level is missing. Think of asking a local for a restaurant on your exact street: if they know one, great (trigram); if not, they suggest the neighborhood (bigram); if even that is blank, they name a city-wide favorite (unigram).

In practice, most real-world language modeling problems use interpolation, not Laplace smoothing. Laplace smoothing is used for certain applications like classification; otherwise, today's systems use interpolation or transformers.

8.4.4 Perplexity

Perplexity is an evaluation measure for language models, used not only for n-gram language modeling but also for neural language modeling, and even for ChatGPT and the LLM transformers, where research papers report it. It is an intrinsic evaluation measure because it measures the algorithm level; extrinsic evaluation is black-box, testing the whole system's performance using accuracy, precision, recall, and so on. The extrinsic test is the honest gold standard — put the model in the real task and measure task accuracy — but it is slow; perplexity is the fast stand-in that scores the model directly on test text.

The intuition behind perplexity: raw probability values may not indicate how good the system is, but a single number is easy to compare. Lower perplexity is better; the model should aim for lower perplexity. The formula takes the sequence probability computed from the language model and raises it to the inverse of the sequence length, the Nth root of the inverse of the probabilities:

$$PP(w_1,\dots ,w_N)=P(w_1,\dots ,w_N{)}^{-1/N}$$

where $P(w_1,\dots ,w_N)$ is the sequence probability computed from the language model, and $N$ is the number of words in the sequence. The minus sign in the exponent turns "high probability" into "low perplexity", and the $1/N$ averages over the length so long and short test sets are comparable.

The cleanest reading of the number: perplexity is the effective number of equally likely choices the model is torn between at each step — the branching factor. A model that gives every digit 0–9 probability $1/10$ has perplexity exactly 10; a sharp model that is usually sure has perplexity near 2.

Real numbers confirm the story: on the Wall Street Journal test set, a unigram model scores perplexity 962, a bigram 170, and a trigram 109 — each extra word of context removes most of the uncertainty, and the drop from 962 to 109 is the value of context written as one number.

8.4.5 Student Questions and Answers

8.4.6 Exam Notes

Recap and bridge. An n-gram model scores a sentence as a product of short-horizon next-word probabilities; smoothing and interpolation rescue the zeros; perplexity turns the model's uncertainty into one comparable number. The next module swaps the count table for a neural network — and softmax takes over from the raw counts at the output side.

8.5 Neural Language Models and Introduction to LLMs

Neural language modeling is applying neural network algorithms to the language modeling problem. Most of the textbook content on this module covers the neural networks part first, because the neural networks must be known before they can be applied to language modeling. The deep neural networks course already covers backpropagation, so this exam will not have a direct backpropagation-through-time calculation. The examinable shape of this module is architectural: how the network is built, what activation ends the output layer, and why the neural model beats the n-gram model on unseen words.

8.5.1 From Perceptrons to Multi-Layer Networks

A neural network is built from perceptrons. A perceptron is the simplest unit: it adds up weighted inputs plus a bias, fires 1 if the sum is above zero, and 0 otherwise. A single neuron cannot solve certain nonlinear functions like XOR, which is why a network with multiple perceptrons is needed — the XOR problem needs 2 perceptrons, and that is why multi-layer perceptron networks exist.

The XOR problem is worth understanding because it explains why depth exists: XOR should fire when two inputs differ, so the yes-cases (0,1) and (1,0) sit on opposite corners of the input square, and the no-cases on the other two corners. No single straight line can separate them, so one perceptron — one straight cut — always fails. Two perceptrons arranged in a hidden layer can do it: one hidden unit learns "at least one input is on", the other learns "both inputs are on", and the output combines them into "at least one on, but not both".

A network has an input layer, a hidden layer, and an output layer. If the output is logistic binary classification, the output side uses a sigmoid. Forward propagation is the simple chain of sum of products and activation function: multiply the weights, then apply the sigmoid or any activation function, get the output; again sum of products, apply the activation, and so on. The bias is replaced with $x_0=1$ to make the equations simpler: a fake input fixed at 1 with its own weight plays the exact role of the bias, so $w\cdot x+b$ becomes one clean dot product.

For the language modeling problem, the network takes word embeddings as inputs — the token IDs are converted into word embeddings and given as input, because for any NLP application the input is always word embeddings, never raw tokens. Raw token IDs are just indices with no meaning attached; the embedding vector carries the meaning, and the network can generalize between similar words.

8.5.2 Softmax for Multi-Class Next-Word Prediction

Language modeling is a multi-class problem: the idea is to predict the next word from multiple given words, so the prediction is from multiple words, not just two. So the output side always uses softmax for language modeling. For sentiment analysis, which is usually a binary class problem, the sigmoid at the output side is used. The rule of thumb: two classes — sigmoid; many classes — softmax.

The softmax normalizes the output scores into a probability distribution over the vocabulary:

$$\text{softmax}(z_i)=\frac{e^{z_i}}{{\sum }_j{e}^{z_j}}$$

where $z_i$ is the output score for word $i$, and the sum runs over all words in the vocabulary. It works in two moves: raise $e$ to each score, which makes every score positive and rewards large scores; then divide by the total, so the pieces add to 1. A big score gets a big share of the probability.

A possible exam question: for building the language model that predicts the next word, explain how the neural network would be built given, say, four hidden nodes. That is a network-definition question, not a backpropagation computation.

8.5.3 Sentence Embeddings and the Advantages of Neural Models

Beyond word embeddings, the module covers sentence embeddings: combine the word vectors using the maximum of elements or the mean of elements to get a single vector for the sentence. Texts vary in length, but a feedforward network wants a fixed-size input, and pooling collapses any number of word vectors into one fixed-size vector.

The loss function was also covered, but there will be no problems on backpropagation through time, which is not a focus of this course — the focus is how the feed-forward network is applied for neural language modeling.

The pros and cons of neural language models are simple to understand. The major advantage is the word embeddings: for unseen words, the neural model can still predict, mainly because of the word embeddings, whereas the n-gram language models work with the actual words and cannot predict unseen words. An n-gram model treats "dog" and "cat" as unrelated symbols; if training text only has "the cat gets fed", a bigram model cannot predict anything after "the dog gets". The neural model sees that dog sits near cat in embedding space and reuses the cat pattern to predict "fed". That sharing is the key exam point.

When neural language models are mentioned, it means large language models or small language models: LLMs use the same concept as neural language models, though they use the transformer architecture instead of the simple feed-forward network — and the transformer is ultimately neural networks only.

8.5.4 Large Language Models, Fine-Tuning, and Prompt Engineering

Large language models are language models with a large number of parameters, trained on a large set of training data. They could be pre-trained models, and then fine-tuned for specific applications: if a model is wanted for a specific task or specific domain, it is retrained on that particular data set. Many models are openly available on Hugging Face. LLMs are used everywhere today.

Prompt engineering was introduced with zero-shot, where the model is given no training examples, and few-shot, where the model is given a few examples. In zero-shot you describe the task and rely on what the model already learned; in few-shot you place a few worked examples inside the prompt and the model copies the pattern. Both adapt the model with no weight changes — the adjustment lives entirely in the prompt. Generative AI means generating new content: given a certain text as the input prompt, the model generates text. Generative AI is not just for textual content — it can generate image content and video content given text, and today coding agents generate whole chunks of code.

8.5.5 Student Questions and Answers

8.5.6 Exam Notes

Recap and bridge. The neural language model replaces the n-gram count table with embeddings, a hidden layer, and a softmax over the vocabulary; its defining advantage is generalizing to unseen words through embeddings. That same architecture, scaled into transformers, is what LLMs run on today. The revision now closes with a collected summary of the exam guidance and the industry applications behind every module.

Exam Guidance Summary

• The exam is 30 marks, closed book, with 30% weightage. There are around 6 to 7 questions. Each question may have sub-parts, and the paper combines numerical problems, scenario-based case studies, and conceptual questions, assessing problem solving ability as well as understanding.
• The mark distribution has plus or minus one mark variation; some questions carry four or five marks. Depending on the length or complexity of the problem, POS tagging, vector semantics, or language modeling could carry a little more weight.
• Write the justification of answers wherever required. Give the specific formulas used. If a formula is specified in the question, use that respective formula.
• Topic-wise expectations: an application-oriented case study question on the introduction module; a four-mark mathematical problem on statistical (n-gram) language modeling; an application-oriented question, possibly with a small evaluation problem, on neural language models and introduction to LLMs; a mathematical problem on vector semantics (sparse vectors, TF, IDF, cosine similarity); a mathematical problem on word embeddings (skip-gram negative sampling); a problem on POS tagging based on HMM and the Viterbi algorithm; and a small problem on MEMM or ML-based approaches, mostly an application-oriented question on neural language modeling. Nothing will be asked outside the curriculum.
• For stop words: use the list given in the exam; if no list is given, write all assumptions, stating which words were treated as stop words.
• Regular and makeup exams are kept at similar difficulty — roughly eighty to ninety percent similar, not a replica.
• For TF-IDF, use log base ten, or whatever base the question specifies. State the formula used.
• For the SGNS problem, only a single iteration is asked, with simple values and fewer negatives. Derivation is not required. Show the computation in a table step by step. One or two decimal places are fine.
• For n-gram problems, count the vocabulary $V$ from the given sentences for Laplace smoothing. Include start and end tags when the question mentions them; otherwise state the assumption. The bigram table convention: rows hold the first word, columns hold the next word; the same convention applies to POS tagging emission and transition matrices.
• No backpropagation-through-time problems. No mathematical problems on LLM and prompt engineering. No mathematical problems on CBOW; CBOW and GloVe are conceptual only.
• Read every question properly before answering, write answers neatly, and write assumptions out so that the evaluation is unambiguous.
• For clarity on the SGNS formulas, refer to chapter 6 of Jurafsky and Martin.

Key Industry Applications

• Web search uses document vector representations to find similar documents.
• ChatGPT and today's LLM transformers use perplexity as an intrinsic evaluation measure, reported in research papers.
• Token embedding dimensions in production models: GPT-3 era models use 768 dimensions, GPT-4 uses 1024, and small language models use around 300 dimensions, the size Andrew Ng recommends.
• The Word2Vec skip-gram negative sampling algorithm comes from a research paper by Google.
• The Google Ngram corpus provides ready-made n-gram counts.
• Hugging Face hosts many openly available pre-trained language models that can be fine-tuned for specific tasks and domains.
• Generative AI goes beyond text: given a text prompt, models generate images, videos, and code; coding agents generate whole chunks of code.
• Conversational AI systems follow an encoder-decoder pattern: understand the user's intent and entities, then generate the response.
• Hybrid NLP systems are the recommended production pattern: classical pipelines for lighter processing, LLMs for advanced reasoning, and guardrails and rules for post-processing.
• Hybrid search combines sparse representations (TF-IDF) with dense representations (contextual embeddings or SGNS), a topic of a later course.
• Sentiment analysis is a binary classification problem, so the network output uses a sigmoid.
• In production language modeling, interpolation is preferred over Laplace smoothing; Laplace smoothing finds use in applications like classification.
• BM25 is an advanced normalized ranking formula used in information retrieval; it is mentioned as beyond this curriculum.