LectureDBISAI-written · not yet proofread

VL11 Vector Space Model, Word Embeddings

Documents as vectors in a term-document matrix, retrieval as a matrix-vector product, cosine similarity, sparse matrices in PyTorch, and words as vectors via one-hot encodings and word embeddings.

Held Tue 20 Jan 2026 Source lecture-11

Organisation#

Vector Space Model: documents as vectors#

Running example for the whole lecture: four words, six documents (Slide 6).

	D1	D2	D3	D4	D5	D6
internet	1	1	0	1	0	0
web	1	0	1	1	0	0
surfing	1	1	1	2	1	1
beach	0	0	0	1	1	1

Each row corresponds to a word, each column to a document. A non-zero entry is the score of that word in that document; the lecture uses tf scores, ES11 uses BM25 scores.

Retrieval as a matrix-vector product#

A query is also a vector: 1 for every term that occurs in the query, 0 for all other terms. The relevance of a document to the query is the dot product of the two vectors. With tf entries this is exactly the tf score sum from Lecture 2 (Lecture 2, Slide 10) (Slide 8).

Let $A \in \mathbb{R}^{|V| \times n}$ be the term-document matrix ( $|V|$ = number of terms, $n$ = number of documents) and $q \in \{0,1\}^{|V|}$ the query vector. Then

q^T \cdot A \in \mathbb{R}^{1 \times n}

contains the relevance scores of all documents at once (Slide 9).

Linear algebra in PyTorch#

The course uses PyTorch for this and the next lecture (earlier years: numpy/scipy). In PyTorch, vectors and matrices are both tensors: a vector is a 1D tensor, a matrix a 2D tensor (Slide 10).

import torch
A = torch.tensor([[1, 1, 0, 1, 0, 0],
                  [1, 0, 1, 1, 0, 0],
                  [1, 1, 1, 2, 1, 1],
                  [0, 0, 0, 1, 1, 1]])
q = torch.tensor([[0, 1, 1, 0]])
scores = q @ A   # tensor([[2, 1, 2, 3, 1, 1]])

Document similarity#

Variant 1: dot product with BM25 scores#

Problem with the plain dot product: documents with more and/or higher entries (longer documents, more repetitions) get larger scores. One remedy is to use BM25 scores as matrix entries: BM25 was designed to account for document length and term frequency so that scores reflect relevance. With BM25 entries, the dot product gives exactly the same ranking as the inverted-index ranking of Lecture 2. ES11, Exercise 1 uses this variant (Slide 11).

Variant 2: cosine similarity#

It is called cosine similarity because it equals $\cos \alpha$ , where $\alpha = \sphericalangle(x, y)$ is the angle between the two vectors. This follows from the law of cosines: for a triangle with sides $a, b, c$ ,

c^2 = a^2 + b^2 - 2ab \cos \sphericalangle(a, b).

For $\sphericalangle(a, b) = 90°$ the cosine is $0$ and the law reduces to Pythagoras’ theorem.

Proof

x \bullet y / (|x| \cdot |y|) = \cos \sphericalangle(x, y)

(left as an exercise in the lecture)

Take the triangle spanned by $x$ and $y$ ; its third side is $x - y$ . The law of cosines gives

|x - y|^2 = |x|^2 + |y|^2 - 2 |x| |y| \cos \sphericalangle(x, y).

Expanding the left side with the dot product: $|x - y|^2 = (x - y) \bullet (x - y) = |x|^2 - 2\, x \bullet y + |y|^2$ . Comparing both sides yields $x \bullet y = |x| |y| \cos \sphericalangle(x, y)$ , i.e. $\text{cos-sim}(x, y) = \cos \sphericalangle(x, y)$ .

Efficient computation#

For ES11 the cos-sim between the query and each of the $n$ documents is needed repeatedly. The $n$ dot products are one matrix-vector product (as above), but computing the $L_2$ -norm $n + 1$ times is costly. Instead, normalize all vectors once in advance (Slide 13):

x' = \frac{x}{|x|}, \quad y' = \frac{y}{|y|} \quad\Rightarrow\quad |x'| = |y'| = 1, \qquad \text{cos-sim}(x, y) = \text{cos-sim}(x', y') = x' \bullet y'.

So after normalizing the columns of $A$ (and $q$ ), $q'^T A'$ gives all cosine similarities.

Sparse matrices#

Storing all entries of a large term-document matrix is infeasible, but most entries are zero. A sparse-matrix representation stores only the non-zero entries together with their row and column index, as triples (value, row index, column index), with 0-based indices (Slide 14):

(1, 0, 0),\ (1, 0, 1),\ (1, 0, 3),\ \dots,\ (2, 2, 3),\ \dots

E.g. $(2, 2, 3)$ : “surfing” (row 2) has score 2 in D4 (column 3).

Two principal storage orders (Slide 15):

row-major: store row by row (sort by row index first),
column-major: store column by column (sort by column index first).

TheoremSparse row-major term-document matrix = inverted index

In row-major order, the entries of row $i$ (term $i$ ) are consecutive, and their column indices are the ids of the documents containing term $i$ , with the score as payload:

(1, 0, 0), (1, 0, 1), (1, 0, 3)          ids of docs containing term 0
(1, 1, 0), (1, 1, 2), (1, 1, 3)          ids of docs containing term 1
(1, 2, 0), (1, 2, 1), (1, 2, 2) ...      ids of docs containing term 2
(1, 3, 3), (1, 3, 4), (1, 3, 5)          ids of docs containing term 3

This is exactly an Inverted Index with scores. Column-major order gives, per document, its term vector.

Sparse matrices in PyTorch#

To initialize a sparse matrix efficiently, specify the non-zero values and their row and column indices. “coo” stands for “coordinates”; internally, the non-zero values are always stored in row-major order. A sparse tensor can be multiplied with a dense tensor (Slide 16):

values = [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
rows   = [0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
cols   = [0, 1, 3, 0, 2, 3, 0, 1, 2, 3, 4, 5, 3, 4, 5]
A_sparse = torch.sparse_coo_tensor(
    torch.tensor([rows, cols]), values, dtype=torch.int)

q = torch.tensor([[0, 1, 1, 0]], dtype=torch.int)
scores = q @ A_sparse

Word embeddings: words as vectors#

Vocabulary#

One-hot encoding#

Relation to the VSM. In a term-document matrix, each document column is simply the sum of the one-hot encodings of the words it contains, with multiplicity (Slide 19):

The same holds for the query vector; since a query typically contains few keywords, each at most once, it has a few 1s and 0s otherwise.

Properties. The one-hot encodings of any two distinct elements are orthogonal: their dot product, and hence their cos-sim, is $0$ . So “internet” and “web” are exactly as (dis)similar as “internet” and “beach”. Desirable instead: semantically similar words have a higher cos-sim than semantically dissimilar ones (Slide 20).

Word embeddings#

How such vectors are computed is not covered in this course (see IR WS 22/23, Lecture 9); for ES11 they are provided.

Using the embeddings for ES11#

The provided embeddings are a dictionary from word to embedding tensor (Slide 22):

embs = torch.load("embeddings.pt")
emb_internet = embs["internet"]
emb_web = embs["web"]
sim = torch.cosine_similarity(emb_internet, emb_web, dim=0)

Document embedding. The embedding of a document is the sum of the embeddings of its words, in analogy to the one-hot sum on Slide 19:

doc_emb = embs["internet"] + embs["web"] + embs["surfing"]

References#

Textbook (Manning, Raghavan, Schütze, Introduction to Information Retrieval), Section 6.3: The vector space model for scoring. PyTorch tensor basics, the chair’s PyTorch cheat sheet, and “PyTorch for numpy users” (Slide 23).

Open Questions#

cos-sim measures the alignment of vectors. What does that mean for embeddings? In good embeddings, semantic relatedness is encoded in the direction of the vectors: related words point in similar directions (cos-sim close to $1$ ), unrelated words do not (Slide 21). Because cos-sim ignores length, a document embedding (a sum of word embeddings, whose length grows with the number of words) is compared by what it is about, not by how long it is (Slide 13, Slide 22).
What about word order, “cute cats eating” vs. “eating cute cats”? With the lecture’s document embedding (sum of word embeddings) and with VSM vectors, both phrases get identical vectors, since addition is commutative; order is lost (Slide 22). See the bag-of-words warning above.

Concepts#

Vector Space Model (VSM) — documents as columns of a term-document matrix, retrieval as $q^T A$
term frequencies — tf entries of the running example; the dot product reproduces the tf score sum of Lecture 2
BM25 — matrix entries for which the dot product gives the Lecture 2 ranking (ES11, Exercise 1)
cos-similarity — length-normalized similarity, equal to the cosine of the angle; precompute normalized vectors
Sparse Matrices — store only non-zero (value, row, col) triples; row-major vs. column-major; torch.sparse_coo_tensor
Inverted Index — equivalent to the sparse row-major term-document matrix
One-Hot Encoding — words as orthogonal unit vectors; documents are sums of one-hot encodings
Embeddings — dense, low-dimensional word vectors with semantic cos-sim; document embedding as sum
Term-Document Matrix — matrix $A$ of term scores per document
Vocabulary — (ordered) set of distinct words, words ↔ indices
Law of Cosines — justifies that cos-sim equals the cosine of the angle
Document Embedding — sum of the word embeddings of a document (bag of words)