ConceptDBISAI-written · not yet proofread

LSI Ranking

Also LSI · Latent Semantic Indexing Method · Document Expansion · Low-Rank Approximation of the Term-Document Matrix

Latent semantic indexing ranks documents with a rank-k approximation of the term-document matrix from its SVD, so that a query also matches documents that share no term with it but belong to the same latent concepts.

Know these firstSingular Value Decomposition Vector Space Model

Definition

Let $A \in \mathbb{R}^{m \times n}$ be the term-document matrix of the Vector Space Model ( $m$ terms, $n$ documents, e.g. tf.idf entries) and $A = U S V$ its reduced SVD with $U \in \mathbb{R}^{m \times r}$ , $S \in \mathbb{R}^{r \times r}$ , $V \in \mathbb{R}^{r \times n}$ (IR-exam notation, $V$ row-orthonormal). For $k \le r$ let $U_k, S_k, V_k$ keep the $k$ largest singular values (first $k$ columns of $U$ , top-left $k \times k$ block of $S$ , first $k$ rows of $V$ ). Latent semantic indexing (LSI) ranks the documents for a query vector $q \in \mathbb{R}^m$ by the scores

\text{scores}(q) = q^\top A_k, \qquad A_k = U_k S_k V_k,

the dot product of $q$ with the best rank- $k$ approximation $A_k$ of $A$ . The $k$ dimensions are the latent concepts: $U_k$ maps terms to concepts, $V_k$ documents to concepts.

Formula#

The exams discuss three equivalent-looking ways to score (WS 21/22, WS 22/23):

Variant	Scores ( $1 \times n$ )	Idea
Approximated matrix	$q^\top U_k S_k V_k$	rank- $k$ matrix $A_k$ replaces $A$
Query in concept space	$(U_k^\top q)^\top$ vs. documents $S_k V_k$	compare in the $k$ -dim. concept space
Document expansion	$q^\top T_k A$ , with $T_k = U_k U_k^\top$	keep $A$ , but expand the query by related terms

Document expansion uses the $m \times m$ term-to-term matrix $T_k = U_k U_k^\top$ (projection onto the $k$ concept directions): $q^\top T_k$ gives weight to terms that co-occur with the query terms. Since $A_k = U_k U_k^\top A$ (because $V = S^{-1} U^\top A$ ), $q^\top T_k A = q^\top A_k$ when $k = r$ is cut consistently, so the variants agree.

Properties#

Cost: computing $U, S, V$ is done once offline. A query then needs $q^\top U_k$ ( $k$ numbers), then multiplication with $S_k V_k$ .
$\operatorname{rank}(A_k) = k$ and $A_k$ is the best rank- $k$ approximation (Eckart–Young).
$A_k$ is dense even if $A$ is sparse.

Example#

ExampleScoring with $k = 1$ (WS 21/22 style code)

def top(q, U, S, V, k):
    Uk = U[:, 0:k]        # m x k
    Sk = S[0:k, 0:k]      # k x k
    Vk = V[0:k, :]        # k x n
    scores = q.transpose().dot(Uk).dot(Sk).dot(Vk)   # 1 x n
    return numpy.argmax(scores)

Dimension check: $(1 \times m)(m \times k)(k \times k)(k \times n) = 1 \times n$ , one score per document.

Sources#

Not covered in WS 25/26 (DBIS_VL13 > Work at the Chair: LSI is taught in the advanced course in WS 26/27). Source is the past exams.
WS 21/22 Task 5.1 (not published) (top(q, U, S, V, k)), WS 22/23 Task 5.1 (not published) (top(q, A, U, k), document expansion)

Connections

Mentioned in inline links2

Latent Semantic Indexing
LSI Ranking — scores documents with the rank- $k$ approximation $A_k = U_k S_k V_k$ instead of $A$ §
Ranking. LSI Ranking replaces $A$ by $A_k$ . The three ways of computing the scores (approximated matrix $q^\top A_k$ , query in concept space, document expansion $q^\top U_k U_k^\top A$ ) give the same scores, because $A_k = U_k U_k^\top A$ .… §
Singular Value DecompositionLA
Use in DBIS: Latent Semantic Indexing (rank- $k$ approximation of the term-document matrix, LSI Ranking); exams WS 16/17 Task 5, WS 17/18 Task 5, WS 19/20 Task 5.1, WS 22/23 Task 5.2 §

Search in these mentions →