02 Pre-processing - Chunk 07 (s.181-193)

Overview

This final chunk of the Pre-processing deck finishes the worked example of Concept - Latent Semantic Analysis (LSA) on a tiny 6-document x 5-term matrix (car, gas, oil, road, truck). It shows that the Concept - Singular Value Decomposition (SVD) $C=U\Sigma V^T$ gives a dense topic space for documents ($U\Sigma$), that each topic is a linear combination of words and that $V$ is the projection matrix that maps any new (sparse) document into that space (s.181-184). It then explains how to reduce dimensionality with Concept - Truncated SVD: keep only the largest singular values, zero out the rest, and use $U_d{\Sigma }_d$ and $V_d$ (s.185-189). With 2 dimensions, the similarity of doc 4 and doc 5 goes from about 0 (full space) to 0.75 (s.182, s.188). The chunk closes with why LSA is used (it handles Concept - Synonymy and Semantic Relatedness, Eckart-Young theorem), a 5-step implementation recipe, and a list of other document-representation approaches (NMF, LDA, RNN/CNN) (s.190-193).

Detailed notes

1. The doc-term example decomposed (s.181)

• Slide title: “Look at the doc-term example”. The document-term matrix $C$ (rows = documents 0-5, columns = terms car, gas, oil, road, truck) is shown as the product of three matrices:

Doc	car	gas	oil	road	truck
0	1	1	0	1	0
1	0	0	0	1	1
2	1	0	0	0	0
3	0	1	1	0	0
4	0	1	0	0	0
5	0	0	1	0	0

• $C=U\times \Sigma \times V^T$, where the three factors are labelled on the slide:
  • $U$ (6x5, columns topic1-topic5) = representation of documents (e.g. row 0 = -0.748623, 0.286454, -0.279712, -1.7e-17, 0.528459).
  • $\Sigma$ (5x5 diagonal) = importance of the semantic dimensions; diagonal values: topic1 2.162501, topic2 1.594382, topic3 1.27529, topic4 1.0, topic5 0.393915 (off-diagonal 0).
  • $V^T$ (rows topic1-topic5, columns car, gas, oil, road, truck) = representation of terms (e.g. topic1 = -0.440347, -0.703020, -0.262673, -0.475530, -0.129346).
• Takeaway: the sparse 0/1 matrix is re-expressed through 5 latent “topics”; singular values are sorted in decreasing importance.

2. New representation for documents (s.182)

• Multiply $U$ by $\Sigma$ -> final representation of documents $U\Sigma$ (s.182). Rows (6 docs x 5 topics), e.g. doc 0 = -1.618898, 0.456717, -0.356713, -1.7e-17, 0.208168; doc 4 = -0.703020, -0.350572, -0.154906, -5.773503e-01, -0.159788; doc 5 = -0.262673, -0.646747, 0.414592, 5.773503e-01, 0.086614.
• Doc 4 and doc 5 rows are boxed in orange.
• Message on slide: “Vectors for documents are dense in the new learned topic space. However, the similarity between doc4 and doc5 are still tiny.” A code cell cosine_similarity(dense_matrix[4].reshape(1,-1), dense_matrix[5].reshape(1,-1)) prints [[-6.10622664e-16]], i.e. cosine similarity $\approx 0$ (s.182).

Added context

Doc 4 contains only “gas” and doc 5 only “oil”, so they share no words; with all 5 dimensions kept, SVD is only a rotation/rescaling of the original space, so their cosine stays ~0. Only dimensionality reduction (s.188) can make them similar. The slide itself only says the similarity is “still tiny”.

3. Projection matrix $V$ and topics as word combinations (s.183)

• Slide shows $V^T$ (topics x terms) next to $V$ (terms x topics; rows car, gas, oil, road, truck; columns topic1-topic5).
• From $C=U\Sigma V^T$ it follows (multiply by $V$ on the right, $V^{T}V=I$): $C\cdot V=U\Sigma$. $V$ is the projection matrix (arrow on slide) that projects the document-term vectors into the topic space.
• Example topic: Topic 1 = -0.44 * car - 0.70 * gas - 0.26 * oil - 0.47 * road - 0.13 * truck.
• Statement: “Each topic is regarded as the linear combination of words.”

4. Folding in a new document (s.184)

• A new document is a sparse bag-of-words vector over the 5 terms: car 0, gas 0, oil 1, road 1, truck 1.
• Multiply by $V$ (5x5) -> dense vector: topic1 -0.867549, topic2 0.195819, topic3 1.369303, topic4 0.57735, topic5 -0.026225.
• Labels on slide: Sparse -> Dense.

5. How to reduce dimensionality (s.185-187)

• s.185 (section-style slide): “How to reduce dimensionality: Abandon unimportant topics.”
• s.186 “Reduce Dimensionality”:
  • Each singular value in $\Sigma$ tells how important its dimension is.
  • By setting less important dimensions to zero, we keep the important information, but get rid of the details.
  • The details may (a) be noise -> reduced LSI is a better representation because it is less noisy; (b) make things dissimilar that should be similar -> reduced LSI represents similarity better.
• s.187 Concept - Truncated SVD: “Zeroing out but these two largest singular values.” The diagonal $\Sigma$ with 2.162501, 1.594382, 1.27529, 1.0, 0.393915 is transformed (red arrow) to a matrix keeping only topic1 = 2.162501 and topic2 = 1.594382; all other entries 0.0.

6. Documents in 2 dimensions (s.188-189)

• s.188 “New Representation for Documents in 2 dimensions”: $U_d$ (columns topic3-5 crossed out in orange) $\times$ ${\Sigma }_d$ (topic3-5 rows/columns crossed out) = new document matrix with only topic1 and topic2 non-zero. “The new feature space is 2” (dimensions).
  • Reduced doc vectors: doc0 (-1.618898, 0.456717); doc1 (-0.604877, 0.842566); doc2 (-0.440347, 0.296174); doc3 (-0.965693, -0.997319); doc4 (-0.703020, -0.350572); doc5 (-0.262673, -0.646747); other columns -0.0/0.0.
  • “Now, we can compute the similarity for doc 4 and doc 5”: code comment # compute the new similarity -> [[0.75020516]].
• s.189 “For a new document”: the same new doc (0,0,1,1,1) is multiplied by $V_d=V[:,0:d]$ (first $d$ columns of $V$) -> topic1 -0.867549, topic2 0.195819 (row 0). Condition on slide: “Here, d is less than the original matrix rank.”

7. Why LSA works as text vectors (s.190-191)

• s.190: LSA tries to capture semantic information (documents that talk about the same topic): it does not require documents to use the same words; it projects documents in a reduced vector space. It tries to address the linguistic characteristics synonymy and semantic relatedness (Concept - Synonymy and Semantic Relatedness).
• s.191 “How LSA addresses synonymy and semantic relatedness”:
  • The dimensionality reduction forces us to ignore a lot of details.
  • We try to map different words (original space) to the same dimension in the reduced space.
  • The “cost” of mapping synonyms to the same dimensions is much less than the cost of collapsing unrelated words.
  • SVD selects the “least costly” mapping (Eckart-Young theorem).
  • The $V$ table (car, gas, oil, road, truck x topic1-5) is repeated at the bottom of the slide as reference.

8. Implementation recipe (s.192)

1. Given a corpus, get the document-term matrix $C$.
2. Compute SVD: $C=U\Sigma V^T$.
3. Original corpus represented in the reduced space (dim $d$): $U_d{\Sigma }_d$.
4. New documents are first transformed into the original vector space: $\mathbf{q}$ (their term vector).
5. Map them into the reduced space: $\mathbf{q}{V}_d$.

9. Other approaches for document representation (s.193)

• Other matrix decomposition methods: NMF (non-negative matrix factorization).
• Probabilistic model: topic model Latent Dirichlet Allocation (LDA).
• Deep-learning based models: RNN, CNN.
• (Slide only lists these names; no details given - see Concept - Other Document Representation Approaches.)

Figures & diagrams

• s.181 Factorization picture: sparse 6x5 doc-term table = $U$ (docs x topics) $\times$ $\Sigma$ (diagonal importances) $\times$ $V^T$ (topics x terms); labels in red: representation of documents / importance of the semantic dimensions / representation of terms.
• s.182 $U\times \Sigma$ = final doc representation (dense 6x5); doc4 and doc5 rows boxed orange; code output cosine $-6.1\times 10^{-16}$ (~0).
• s.183 Tables of $V^T$ and $V$ with equations $C=U\Sigma V^T\Rightarrow CV=U\Sigma$ and the Topic 1 linear combination.
• s.184 New doc vector (0,0,1,1,1) x $V$ = dense 5-d topic vector; Sparse -> Dense.
• s.185 Text-only slide (“Abandon unimportant topics”).
• s.187 $\Sigma$ before/after truncation (only 2.162501 and 1.594382 retained).
• s.188 Orange crosses over topic3-5 columns of $U$, rows/columns of $\Sigma$ and result; 2-d doc matrix; cosine(doc4, doc5) = 0.7502.
• s.189 New doc x $V$ with only the first $d$ columns -> 2-d vector (-0.8675, 0.1958).
• s.191 $V$ table (word-topic weights).
• s.192 Formulas for $C$, $U_d{\Sigma }_d$, $\mathbf{q}$, $\mathbf{q}{V}_d$.

flowchart LR
    C["C: doc-term matrix (sparse)"] --> SVD["SVD: C = U Σ V^T"]
    SVD --> TR["Truncate: keep d largest singular values"]
    TR --> UD["Docs: U_d Σ_d (dense, d-dim)"]
    TR --> VD["Projection: V_d = V[:, 0:d]"]
    Q["New doc q (sparse term vector)"] --> M["q V_d"]
    VD --> M
    M --> R["Dense d-dim vector -> cosine similarity"]

flowchart TD
    A["Full 5 topics: cos(doc4, doc5) ≈ 0 (s.182)"] -->|"abandon topics 3-5 (s.187-188)"| B["2 topics: cos(doc4, doc5) = 0.75 (s.188)"]
    B --> C["Details = noise / false dissimilarity removed (s.186)"]

Key terms

• Concept - Latent Semantic Analysis (LSA)
• Concept - Singular Value Decomposition (SVD)
• Concept - Truncated SVD
• Concept - Synonymy and Semantic Relatedness
• Concept - Other Document Representation Approaches
• Concept - Bag of Words (the sparse input vectors)

Formulas

• SVD: $C=U\Sigma V^T$ (s.183, s.192)
• Projection: $CV=U\Sigma$, $V$ = projection matrix (s.183)
• Topic as linear combination: ${\text{Topic}}_1=-0.44\cdot car-0.70\cdot gas-0.26\cdot oil-0.47\cdot road-0.13\cdot truck$ (s.183)
• Reduced docs: $U_d{\Sigma }_d$ (s.188, s.192); reduced projection $V_d=V[:,0:d]$ (s.189)
• New document: $\mathbf{q}{V}_d$ (s.192); condition $d<$ rank of original matrix (s.189)

Likely exam questions

1. What does each singular value in $\Sigma$ tell us? (s.186) How important its (semantic) dimension is.
2. Explain how dimensionality is reduced in LSA. (s.185-187) Compute SVD, keep the $d$ largest singular values, set the rest to zero (truncated SVD); docs become $U_d{\Sigma }_d$.
3. Why does reducing dimensions improve the representation? (s.186) Removed details may be noise, or may make similar things look dissimilar.
4. How do you map a new document into the LSA space? (s.184, s.189, s.192) Build its term vector $\mathbf{q}$, multiply by $V_d$: $\mathbf{q}{V}_d$.
5. What is the projection matrix and what does each topic represent? (s.183) $V$ (from $CV=U\Sigma$); each topic is a linear combination of words.
6. Why use LSA as text vectors? (s.190) Captures semantic information without requiring the same words; addresses synonymy and semantic relatedness.
7. How does LSA address synonymy and semantic relatedness? (s.191) Reduction maps different words to the same dimension; mapping synonyms is cheaper than collapsing unrelated words; SVD picks the least costly mapping (Eckart-Young).
8. Describe the implementation steps of LSA. (s.192) Doc-term matrix, SVD, $U_d{\Sigma }_d$ for the corpus, $\mathbf{q}$ for a new doc, $\mathbf{q}{V}_d$.
9. Why does the similarity of doc 4 and doc 5 change in the example? (s.182, s.188) Full space: cosine ~0; 2-d space: 0.75.
10. Name other document-representation approaches. (s.193) NMF; LDA topic model; RNN, CNN.

Common confusions

• Dense is not the same as similar: the full 5-topic dense vectors still give doc4/doc5 cosine ≈ 0; only the reduced space gives 0.75 (s.182 vs s.188).
• $V$ vs $V^T$: the slides show both; $V^T$ has topics as rows, $V$ (projection matrix) has terms as rows (s.183).
• $U\Sigma$ vs $U$: the final document representation is $U\Sigma$ (importance-scaled), not plain $U$ (s.182).
• $d$ must be smaller than the rank of the original matrix (s.189).
• New documents use $V_d$, not $U_d$: you do not recompute SVD (s.192).

Slide coverage

Slide	Content	Covered in
181	Doc-term example: $C=U\times \Sigma \times V^T$ with numeric tables	Detailed notes 1; Figures
182	$U\Sigma$ = new dense doc representation; cosine(doc4, doc5) ≈ 0	Detailed notes 2; Figures
183	Projection matrix $V$; topic = linear combination of words	Detailed notes 3; Formulas
184	New document: sparse -> dense via $V$	Detailed notes 4
185	How to reduce dimensionality: abandon unimportant topics	Detailed notes 5
186	Reduce dimensionality: singular values, noise, similarity	Detailed notes 5
187	Truncated SVD: keep two largest singular values	Detailed notes 5; Figures
188	Docs in 2 dimensions; cosine(doc4, doc5) = 0.75	Detailed notes 6; Figures
189	New document with $V_d=V[:,0:d]$; $d$ < rank	Detailed notes 6
190	Why use LSA as text vectors	Detailed notes 7
191	How LSA addresses synonymy / relatedness; Eckart-Young	Detailed notes 7
192	Implementation steps	Detailed notes 8; Formulas
193	Other approaches: NMF, LDA, RNN, CNN	Detailed notes 9

Previous: 02 Pre-processing - Chunk 06 (s.151-180) | Next: (none, last chunk of the deck) | Up: 02 Pre-processing - Index