Word Embeddings and Language Models

Concepts#

1. 1 Vector Space Modeldocuments as term-score vectors in a term-document matrix $A$; retrieval as $q^\top A$ start here
2. 2 Cosine Similaritylength-normalized dot product; ranks documents, words and chunks by direction
3. 3 Sparse Matrixstores only the non-zero entries of $A$; row-major = inverted index
4. 4 One-Hot Encodingwords as orthogonal unit vectors; a VSM column is their sum
5. 5 Embeddingdense low-dimensional word/text vectors whose cos-sim reflects meaning
6. 6 Language Modeldistribution over the next token given the previous tokens
7. 7 N-Gram Modelcount-based language model (unigram, bigram, trigram), sampling via cumulative counts
8. 8 Large Language Modelvery large neural language model; base vs. instruct, system prompt, API
9. 9 Retrieval-Augmented Generationchunk, embed, retrieve top-$k$ by cos-sim, prompt the LLM
10. 10 Softmaxturns a score vector into a probability distribution (exam: relation to sigmoid)
11. 11 Sigmoidtwo-class special case of softmax (WS 23/24 Task 5.3)

How it fits together#

From text to vectors#

Every representation in this topic is a vector over a vocabulary $V$, and a document vector is a sum of word vectors:

Queries are encoded exactly like documents, so query and documents live in the same space.

Comparing vectors: three ways to score documents#

With $A \in \mathbb{R}^{|V| \times n}$ (rows = terms, columns = documents) and query $q \in \{0,1\}^{|V|}$, all $n$ scores come from one product $q^\top A \in \mathbb{R}^{1 \times n}$:

The DBIS use of the normalization trick: computing $n + 1$ norms per query is costly, so normalize all document vectors once in advance; afterwards cos-sim with every document is again a single product $q'^\top A'$. The same holds for embeddings: ranking words by cos-sim to emb["internet"] (ES11) and ranking chunks by cos-sim to the query embedding (RAG) are the same operation.

Storing the matrix#

$A$ is mostly zeros, so it is kept as a sparse matrix of (value, row, column) triples. Row-major order groups the entries per term, which is literally an Inverted Index with scores; column-major order groups them per document. So “VSM with a sparse matrix” and “inverted index with BM25” are the same retrieval, written as linear algebra vs. as list processing. PyTorch: torch.sparse_coo_tensor, and q @ A_sparse computes all scores.

From counts to LLMs#

All language models here compute $\Pr(\text{next token} \mid \text{previous tokens})$; they differ in how. Tokens can be words, subwords (modern LLMs) or characters (lecture n-gram code).

1. Unigram → bigram → trigram: condition on $0$, $1$, $2$ previous tokens; learn by counting and normalizing; generate by sampling via cumulative counts.
2. Why counting stops working: $|V|^n$ possible n-grams ($100^3 = 10^6$ trigrams for $|V| = 100$), and most long contexts never occur (smoothing = random next token).
3. Neural language model: same distribution, computed by a network forward pass; allows context sizes up to $10^6$ tokens.
4. LLM: a very large neural LM. A base model only continues text; an instruct model is trained to converse and is steered by a system prompt. Services return $k$ tokens per request (max_completion_tokens, temperature).

RAG: where the two halves meet#

When the text exceeds even an LLM’s context size (ES12: all lecture transcripts), RAG uses the first half of the topic to choose the input for the second: split the text into sentence-complete chunks, embed them, embed the query with the same model, take the $k$ chunks with the highest cos-sim (linear scan in ES12), and give their text plus a system prompt to the LLM. Knobs: chunk size, overlap, embedding model, $k$, system prompt.

Softmax and sigmoid#

Not lectured in WS 25/26, but asked in WS 23/24 Task 5.3 under this topic: softmax maps a score vector $z \in \mathbb{R}^k$ to a distribution, $\text{softmax}(z)_i = e^{z_i} / \sum_j e^{z_j}$, and the sigmoid $\sigma(z) = 1 / (1 + e^{-z})$ is its two-class case: $\text{softmax}([x, 0]) = (\sigma(x), \sigma(-x))$. Sigmoid is the output of logistic regression (Linear Classifiers and Logistic Regression).

Key Formulas#

• Scores of all documents: $q^\top A \in \mathbb{R}^{1 \times n}$ (Vector Space Model)
• $\text{cos-sim}(x, y) = \dfrac{x \bullet y}{|x| \cdot |y|} = x' \bullet y'$ with $x' = x / |x|$ (Cosine Similarity)
• Document vector $= \sum_{w \in \text{doc}} e_w$ (one-hot, One-Hot Encoding) or $\sum_{w \in \text{doc}} \text{emb}(w)$ (Embedding)
• $\Pr(v \mid v_1 \dots v_{n-1}) = \#v_1 \dots v_{n-1} v \,/\, \sum_{u \in V} \#v_1 \dots v_{n-1} u$ (N-Gram Model)
• $\text{softmax}([x, 0]) = (\sigma(x), \sigma(-x))$ (Softmax, Sigmoid)

Exercises & Exam Questions#

import math

def cos_sim(emb1: list[float], emb2: list[float]) -> float:
    dot = sum(a * b for a, b in zip(emb1, emb2))
    norm1 = math.sqrt(sum(a * a for a in emb1))
    norm2 = math.sqrt(sum(b * b for b in emb2))
    return dot / (norm1 * norm2)

class SimplisticLanguageModel(torch.nn.Module):
    def __init__(self, n: int, d: int):
        super().__init__()
        self.linear = torch.nn.Linear(n * d, d)

    def forward(self, X: torch.Tensor):
        # X has shape (batch_size, n * d)
        return self.linear(X)

def sample(tokens: list[str], probs: list[float], k: int) -> str:
    top_k_indices = argsort(probs)[len(probs) - k:]
    top_k_probs = [probs[i] for i in top_k_indices]
    top_k_tokens = [tokens[i] for i in top_k_indices]
    top_k_probs_normalized = [p / sum(top_k_probs) for p in top_k_probs]
    return top_k_tokens[sample_from_dist(top_k_probs_normalized)]

Lectures#

• DBIS_VL11 — vector space model, retrieval as $q^\top A$, dot product vs. BM25 vs. cosine similarity, sparse matrices in PyTorch, one-hot encodings, word embeddings
• DBIS_VL12 — tokens, unigram/bigram/trigram models and sampling, neural language models and LLMs (base vs. instruct, API), retrieval-augmented generation

Related Topics#

• Inverted Index and Ranking — tf and BM25 scores; the sparse row-major term-document matrix is an inverted index
• Latent Semantic Indexing — works on the same term-document matrix, factorized by SVD
• Linear Classifiers and Logistic Regression — sigmoid, softmax and logistic regression (the other parts of the exam tasks above)
• Inner Products and Norms — foundation: dot product, norms, angles behind cosine similarity