ConceptDBISAI-written · not yet proofread

Sparse Matrix

Also Sparse Matrices

A sparse matrix is a matrix with mostly zero entries, stored as the list of its non-zero entries as (value, row index, column index) triples instead of all m × n entries.

Know these firstVector Space Model

Typical case: a term-document matrix in the Vector Space Model, where $|V|$ is large but each document contains only a small fraction of the vocabulary, so storing all entries is infeasible.

Properties#

Space: $O(\text{nnz})$ for $\text{nnz}$ non-zero entries, instead of $O(m \cdot n)$ for the dense matrix.
Storage orders:
- row-major: sorted by row index first; the entries of one row are consecutive.
- column-major: sorted by column index first; the entries of one column are consecutive.

PyTorch: torch.sparse_coo_tensor(indices, values) builds a sparse matrix from a $2 \times \text{nnz}$ index tensor (rows, columns) and the values; “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, so $q^\top A$ works directly on the sparse $A$ .

Example#

ExampleLecture running example (4 terms × 6 documents)

Rows internet, web, surfing, beach; columns D1–D6 (DBIS_VL11 > Vector Space Model: documents as vectors). Row-major triples:

(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), (2, 2, 3), (1, 2, 4), (1, 2, 5)  ids of docs containing term 2
(1, 3, 3), (1, 3, 4), (1, 3, 5)                                ids of docs containing term 3

E.g. $(2, 2, 3)$ : “surfing” (row 2) has score 2 in D4 (column 3). 15 entries are stored instead of 24.

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)   # "web surfing"
scores = q @ A_sparse                                # [[2, 1, 2, 3, 1, 1]]

ExampleSmall example: 3 terms × 4 documents

Vocabulary $V = (\text{cat}, \text{dog}, \text{fish})$ :

A = \begin{pmatrix} 2 & 0 & 1 & 0 \\ 0 & 3 & 0 & 1 \\ 1 & 0 & 0 & 2 \end{pmatrix}

Non-zero entries as triples $(\text{value}, \text{row}, \text{col})$ in row-major order: $(2,0,0), (1,0,2), (3,1,1), (1,1,3), (1,2,0), (2,2,3)$ , i.e. 6 entries instead of 12.

Row-major reading (inverted index): cat → doc 0 (2), doc 2 (1); dog → doc 1 (3), doc 3 (1); fish → doc 0 (1), doc 3 (2). Column-major reading (document vectors): doc 0: cat 2, fish 1; doc 1: dog 3; doc 2: cat 1; doc 3: dog 1, fish 2.

import torch
rows   = [0, 0, 1, 1, 2, 2]
cols   = [0, 2, 1, 3, 0, 3]
values = [2, 1, 3, 1, 1, 2]
A = torch.sparse_coo_tensor(torch.tensor([rows, cols]),
                            torch.tensor(values, dtype=torch.float32), size=(3, 4))
q = torch.tensor([[1, 1, 0]], dtype=torch.float32)  # query "cat dog"
scores = q @ A                                      # [[2., 3., 1., 1.]]

Sources#

Slides 11, p. 14 (triples), Slides 11, p. 15 (row-/column-major, inverted index), Slides 11, p. 16 (PyTorch)
DBIS_VL11 > Sparse matrices, DBIS_VL11 > Sparse matrices in PyTorch

Connections

Mentioned in inline links4

LSI Ranking
$A_k$ is dense even if $A$ is sparse. §
Vector Space Model
Typos: “corresponse” → “corresponds”, “Effiecient” → “Efficient”, “Therefor” → “Therefore”, “sparce” → “sparse” (link sparse matrices), “matix” → “matrix”. §
VL11 – Vector Space Model, Word Embeddings
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 in… §
Sparse Matrices — store only non-zero (value, row, col) triples; row-major vs. column-major; torch.sparse_coo_tensor §
Word Embeddings and Language Models
Sparse Matrix — stores only the non-zero entries of $A$ ; row-major = inverted index §
$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… §

Search in these mentions →