02 Pre-processing - Chunk 06 (s.151-180)

Overview

This chunk finishes a worked example of Concept - Cosine Similarity on bag-of-words vectors (s.151-169; the slides carry a “StatQuest”-style logo and cartoon style) and then returns to the lecture’s own thread: the Concept - Document-Term Matrix built from a toy six-document corpus (s.170-171). It shows why a pure counting representation has no semantics (s.172) and why it is high-dimensional and sparse (s.171). Two remedies are contrasted: Concept - Feature Selection (keep a subset of columns; s.173) and Concept - Dimensionality Reduction (learn new features by combining old ones, ${\mathbb{R}}^M\to {\mathbb{R}}^d$, $d<m$; s.174-176). Linear (PCA) vs non-linear (manifold learning) methods are pictured (s.175). The chunk ends with the linear projection of the matrix to a document-”topic” matrix (s.176), how to find the projection by matrix decomposition (Concept - Latent Semantic Analysis (LSA) via Concept - Singular Value Decomposition (SVD), and Concept - Non-negative Matrix Factorization (NMF); s.177) and the SVD definition, properties, a users-to-movies example and the reduced SVD (s.178-180).

Detailed notes

1. Cosine similarity worked example (s.151-169)

Setup A: two words (s.151-158). Phrases A = “Hello, World!” and B = “Hello!”. Count table (columns Hello, World): A = (1, 1), B = (1, 0) (s.151).

• Formula (s.151): $\text{Cosine Similarity}=\frac{{\sum }_{i=1}^n{A}_i{B}_i}{\sqrt{{\sum }_{i=1}^n{A}_i^2}\sqrt{{\sum }_{i=1}^n{B}_i^2}}$
• Plugging in (s.151, “when i = 2 we plug in the word counts for the second word, World”): $\frac{(1\times 1)+(1\times 0)}{\sqrt{1^2+1^2}\sqrt{1^2+0^2}}$.
• “When we do the math, we get 0.71” (s.152).
• Geometric meaning (s.153): plotting the points on a graph with Hello on the x-axis and World on the y-axis, A is the point (1,1) and B is (1,0); the angle between the two vectors from the origin is 45°, and $\cos (45^{\circ })=0.71$ = the cosine similarity — “the same value we got when we took the cos(45°)”.
• Why a 2-D plot was possible (s.154-157): when the table only has 2 different words, the points can easily be plotted on a 2-dimensional graph (s.155); one word (Hello) is the x-axis, the first dimension (s.156), the other (World) is the y-axis, the second dimension (s.157). With more than 2 different words you need more than 2 dimensions to plot the points (s.158).

Setup B: five words (s.159-169).

• Phrases (s.159-161): A = “I love Troll 2!”, B = “I love Gymkata!”.
• Count table, 5 different words (s.162):

	I	Love	Troll	2	Gymkata
A = I love Troll 2!	1	1	1	1	0
B = I love Gymkata!	1	1	0	0	1

• That means a 5-dimensional graph would be needed (s.163); “I have no idea how to draw a 5-Dimensional graph” (s.164).
• The good news (s.165-166): you do not need to draw it; having the equation lets you “just plug the numbers into the equation”: $\frac{(1\times 1)+(1\times 1)+(1\times 0)+(1\times 0)+(0\times 1)}{\sqrt{1^2+1^2+1^2+1^2+0^2}\sqrt{1^2+1^2+0^2+0^2+1^2}}$.
• Result: 0.58 (s.167-168), i.e. the cosine similarity between the two phrases is 0.58. (Check: numerator 2, denominator $\sqrt{4}\cdot \sqrt{3}=3.46$, giving 0.577.)
• Summary (s.169): cosine similarity is “a relatively easy to calculate metric that can tell us how similar or different things are”.

2. The document-term matrix (s.170-171)

• Bag-of-Words (TF-IDF): Document-Term Matrix (s.170). Toy corpus of six documents (documents 0-5): “car road gas”, “truck road”, “car”, “gas oil”, “gas”, “oil”.
• Resulting binary count matrix (columns car, gas, oil, road, truck) (s.170):

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

• Shape (s.171): the matrix $C$ is $n$ by $m$; $m$ = vocabulary size, $n$ = number of documents. It is high-dimensional (red) and sparse (orange).

3. Problem: just counting, no semantics (s.172)

• Same matrix with rows 4 (“gas”) and 5 (“oil”) boxed in orange and an arrow to “Cosine similarity is zero” (formula $\cos \theta =\frac{\mathbf{A}\cdot \mathbf{B}}{\Vert \mathbf{A}\Vert \Vert \mathbf{B}\Vert }=\frac{\sum A_i{B}_i}{\sqrt{\sum A_i^2}\sqrt{\sum B_i^2}}$).
• Takeaway: “gas” and “oil” are related words, but because they occupy different columns their vectors are orthogonal; counting representations capture no semantic relation between terms. (Interpretation of the slide’s title and boxed rows; the slide states only “Just Counting No Semantic” and “Cosine Similarity is zero”.)

4. Remedy 1: Feature Selection (s.173)

• Based on measures such as mutual information, keep the top-ranked K features: “choose a subset of the features” (s.173).
• Example figure: the 5-column matrix is reduced to two columns, car and gas (rows 0-5: (1,1), (0,0), (1,0), (0,1), (0,1), (0,0)).
• Drawback (red text): “Still sparse and discard lots of information”.

5. Remedy 2: Dimensionality Reduction (s.174-175)

• New features are learned by combining old features (s.174).
• Formally a map ${\mathbb{R}}^M\to {\mathbb{R}}^d$ with $d<m$.
• Algorithms listed: PCA, NMF, Auto-encoder, t-SNE, Kernel PCA, Manifold learning, … (s.174).
• Figure (s.174, from geeksforgeeks): 3-D axes (x, y, z) with two green cylinders reduced either to an x-y plane (two circles) or an x-z… view with two vertical bars; i.e. projecting 3-D data onto a lower-dimensional plane.
• Linear vs Nonlinear (s.175): left, PCA: a 2-D point cloud (axes f1, f2) with two new orthogonal axes e1 (long direction of the cloud) and e2; right, Manifold Learning (from Quora): a rolled-up (Swiss-roll-like) coloured sheet being pulled flat by two cartoon figures, i.e. “unrolling” a curved manifold into a flat strip. Takeaway: PCA is linear; manifold learning handles non-linear structure.

6. Linear projection of the term-document matrix (s.176-177)

• Figure (s.176): a big blue matrix (Doc. rows by Term columns, n by m) $\times$ an orange Projection Matrix (m by d) = a tall thin blue matrix, the Document-”Topic” Matrix (Doc. rows, Topic columns). The slide asks “what is the shape?” — answer from the product of shapes: n by d.
• How to find the projection matrix (s.177): it is also called matrix decomposition in linear algebra. Methods: Latent Semantic Analysis: SVD (bold), Non-negative Matrix Factorization, …

7. SVD (s.178-180)

Definition and properties (s.178) (slide borrowed from a Stanford/Mining-of-Massive-Datasets style lecture; note it uses $m$ documents by $n$ terms, the opposite of s.171/180):

• $A_{[m\times n]}=U_{[m\times r]}{\Sigma }_{[r\times r]}(V_{[n\times r]}{)}^T$ and $A\approx U\Sigma V^T={\sum }_i{\sigma }_i{\mathbf{u}}_i\circ {\mathbf{v}}_i^T$ (sum of rank-1 terms; ${\sigma }_i$ scalar, ${\mathbf{u}}_i,{\mathbf{v}}_i$ vectors).
• $A$: input data matrix, $m\times n$ (e.g. $m$ documents, $n$ terms).
• $U$: left singular vectors, $m\times r$ ($m$ documents, $r$ concepts).
• $\Sigma$: singular values, $r\times r$ diagonal matrix (strength of each “concept”); $r$ = rank of $A$.
• $V$: right singular vectors, $n\times r$ ($n$ terms, $r$ concepts).
• Properties: it is always possible to decompose a real matrix $A$ into $U\Sigma V^T$; $U,\Sigma ,V$ are unique; $U,V$ are column-orthonormal: $U^{T}U=I$, $V^{T}V=I$ (columns are orthogonal unit vectors); $\Sigma$ is diagonal with positive singular values sorted in decreasing order ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$.
• Figure: block diagrams of $A\approx U\Sigma V^T$ and of $A$ as the sum of two rank-1 outer products (dark red and green bars with ${\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1$ and ${\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2$).

Example: Users-to-Movies (s.179). $A=U\Sigma V^T$ with users as rows and movies as columns (Matrix, Alien, Serenity, Casablanca, Amelie). The 7x5 rating matrix (rows): (1,1,1,0,0), (3,3,3,0,0), (4,4,4,0,0), (5,5,5,0,0), (0,2,0,4,4), (0,0,0,5,5), (0,1,0,2,2).

• $U$ (7x3) first column: 0.13, 0.41, 0.55, 0.68, 0.15, 0.07, 0.07 (labelled the SciFi-concept); second column 0.02, 0.07, 0.09, 0.11, -0.59, -0.73, -0.29 (the Romance-concept); third column -0.01, -0.03, -0.04, -0.05, 0.65, -0.67, 0.32.
• $\Sigma$ = diag(12.4, 9.5, 1.3); 12.4 is circled as the “strength” of the SciFi-concept.
• $V^T$ (3x5) rows: (0.56, 0.59, 0.56, 0.09, 0.09), (0.12, -0.02, 0.12, -0.69, -0.69), (0.40, -0.80, 0.40, 0.09, 0.09). The first row’s entries for Matrix/Alien/Serenity (0.56…) are circled/linked to the SciFi-concept.
• Interpretation (centre text): “‘movies’, ‘users’ and ‘concepts’”: U = user-to-concept similarity matrix; V = movie-to-concept similarity matrix (“V is ‘movie-to-concept’ similarity matrix”); $\Sigma$ diagonal elements = “strength” of each concept.

Reduced SVD (s.180) (source: csiu.github.io blog). In the lecture’s notation the $n\times m$ matrix $C$ (n documents by m terms) decomposes into 3 parts $C=U\ast \Sigma \ast V^T$:

• $U$ is $n$ by $r$ (doc. side)
• $\Sigma$ is a diagonal matrix whose diagonal entries are the singular values, size $r$ by $r$
• $V^T$ is $r$ by $m$ (term side)
• $r$ is the rank of the matrix, usually the min of $m$ and $n$.
• Orthonormality: $U^{T}U=V^{T}V=I^{r\times r}$.
• Figure: blue C (doc rows, term columns) = blue U (tall) $\times$ diagonal band $\Sigma$ $\times$ blue wide $V^T$.

Added context

Cosine similarity ranges from 0 (orthogonal, no shared terms) to 1 (same direction) for non-negative count vectors. Truncating $\Sigma$ to the top $d$ singular values gives the rank-$d$ “topic” space of s.176; the slides state only the full/reduced decomposition, so this truncation step is background knowledge (it is how LSA is normally used).

Figures & diagrams

• s.151-153 Count table + cosine formula for “Hello, World!” vs “Hello!”; s.153 adds a 2-D plot (x=Hello, y=World), pink point (1,1), green point (1,0), 45° angle, $\cos (45^{\circ })=0.71$. Takeaway: cosine similarity = cosine of the angle between count vectors.
• s.154-158 Same table faded formula; narration about plotting in 2-D and needing more dimensions for more words.
• s.159-164 “I love Troll 2!” vs “I love Gymkata!”; 5-column count table; 5-D plot impossible to draw.
• s.165-169 Formula plugged in with five terms, result 0.58, summary speech bubble.
• s.170 Toy corpus (green box, six one-to-three word documents) $\to$ document-term matrix (red arrow).
• s.171 Text-only: matrix shape facts.
• s.172 Matrix with rows 4 and 5 boxed, “Cosine similarity is zero” + formula.
• s.173 Full matrix $\to$ reduced two-column matrix (car, gas) by feature selection.
• s.174 Geeksforgeeks illustration of 3-D to 2-D reduction.
• s.175 PCA axes e1/e2 on a point cloud vs Swiss-roll manifold unrolled.
• s.176 Block-matrix diagram: (n by m) x (m by d) = document-topic matrix.
• s.178 SVD block diagrams, definition and property boxes.
• s.179 Users-to-movies numeric SVD with SciFi / Romance concepts annotated.
• s.180 Reduced SVD block diagram (C = U Σ V^T) and $U^{T}U=V^{T}V=I$.

flowchart TD
    DTM["Document-term matrix C (n docs x m terms)<br/>high-dimensional, sparse, no semantics"] --> FS["Feature selection<br/>keep top-K columns (e.g. mutual information)<br/>still sparse, loses information"]
    DTM --> DR["Dimensionality reduction<br/>R^M -> R^d, d < m<br/>new features = combos of old"]
    DR --> LIN["Linear: PCA, LSA (SVD), NMF"]
    DR --> NL["Non-linear: Kernel PCA, t-SNE, manifold learning, auto-encoder"]
    LIN --> PROJ["Projection matrix P (m x d)<br/>C x P = doc-topic matrix (n x d)"]
    PROJ --> DEC["Found by matrix decomposition: SVD C = U Sigma V^T"]

flowchart LR
    C["C (n x m)"] --- eq["="] --- U["U (n x r)"] --- S["Sigma (r x r) diagonal"] --- VT["V^T (r x m)"]

Key terms

• Concept - Cosine Similarity
• Concept - Document-Term Matrix
• Concept - Bag of Words
• Concept - TF-IDF
• Concept - Feature Selection
• Concept - Dimensionality Reduction
• Concept - Latent Semantic Analysis (LSA)
• Concept - Singular Value Decomposition (SVD)
• Concept - Non-negative Matrix Factorization (NMF)

Formulas

• Cosine similarity (s.151): $\cos \theta =\frac{{\sum }_i{A}_i{B}_i}{\sqrt{{\sum }_i{A}_i^2}\sqrt{{\sum }_i{B}_i^2}}=\frac{\mathbf{A}\cdot \mathbf{B}}{\Vert \mathbf{A}\Vert \Vert \mathbf{B}\Vert }$ (s.172)
• Worked values: Hello/World: $\frac{1}{\sqrt{2}\cdot 1}=0.71=\cos 45^{\circ }$ (s.152-153); Troll 2/Gymkata: $\frac{2}{2\cdot \sqrt{3}}=0.58$ (s.167)
• Dimensionality reduction: ${\mathbb{R}}^M\to {\mathbb{R}}^d$, $d<m$ (s.174)
• Projection: $(n\times m)\cdot (m\times d)=(n\times d)$ (s.176)
• SVD (s.178): $A_{[m\times n]}=U_{[m\times r]}{\Sigma }_{[r\times r]}{V}_{[r\times n]}^T$, $A\approx {\sum }_i{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$
• Reduced SVD (s.180): $C=U\Sigma V^T$, $U$: $n\times r$, $\Sigma$: $r\times r$, $V^T$: $r\times m$, $r=\mathrm{rank}\le \min (m,n)$; $U^{T}U=V^{T}V=I^{r\times r}$

Likely exam questions

1. Compute the cosine similarity of “I love Troll 2!” and “I love Gymkata!”. (s.162-168) Vectors (1,1,1,1,0) and (1,1,0,0,1): dot product 2, norms 2 and $\sqrt{3}$, result 0.58.
2. Explain cosine similarity and its geometric meaning. (s.151-153) Cosine of the angle between the two count vectors; for (1,1) vs (1,0) the angle is 45° so similarity 0.71. The formula works in any number of dimensions, so no need to plot.
3. What is the shape of the document-term matrix and what are its problems? (s.171) $n\times m$ (documents by vocabulary); high-dimensional and sparse.
4. Why is bag-of-words “just counting, no semantic”? (s.172) Related terms (gas, oil) sit in different columns so their cosine similarity is zero.
5. Discuss feature selection and its drawback. (s.173) Keep top-K features ranked by e.g. mutual information; the result is still sparse and discards a lot of information.
6. Describe dimensionality reduction and name algorithms. (s.174) Learn new features by combining old ones, ${\mathbb{R}}^M\to {\mathbb{R}}^d$, $d<m$; PCA, NMF, auto-encoder, t-SNE, kernel PCA, manifold learning.
7. Compare linear and non-linear dimensionality reduction. (s.175) PCA projects onto linear axes (e1, e2); manifold learning unrolls a curved structure (Swiss roll) into a flat low-dimensional one.
8. What is the shape of the document-topic matrix? (s.176) $(n\times m)\times (m\times d)=n\times d$.
9. How can the projection matrix be found? (s.177) By matrix decomposition: LSA via SVD, NMF, etc.
10. State the SVD and its properties. (s.178, s.180) $C=U\Sigma V^T$; $U$, $V$ column-orthonormal ($U^{T}U=V^{T}V=I$); $\Sigma$ diagonal with non-negative singular values in decreasing order; $r$ = rank.
11. Interpret U, Σ and V in the users-to-movies example. (s.179) U: user-to-concept; V: movie-to-concept; Σ: strength of each concept (12.4 for SciFi).

Compare and contrast:

	Feature selection (s.173)	Dimensionality reduction (s.174)
What changes	Keeps a subset of the original columns	Builds new features as combinations of old ones
Result	Still sparse, discards information	Dense low-dimensional representation, $d<m$
Examples	Top-K by mutual information	PCA, SVD/LSA, NMF, t-SNE, auto-encoder

Common confusions

• Matrix orientation: s.171/176/180 use $n$ = documents, $m$ = terms ($C$ is $n\times m$); the borrowed SVD slide s.178 uses $m$ documents, $n$ terms. Same maths, swapped letters.
• Feature selection vs dimensionality reduction: selection keeps original features; reduction creates new ones (s.173-174).
• Zero cosine similarity does not mean unrelated meaning: it only means no shared terms; gas/oil are related semantically but get 0 (s.172).
• Cosine vs distance: cosine similarity is large when the angle is small; 0.71 at 45°, 1 at 0° (s.153).
• “Topic” in the projection: the d columns are latent concepts/topics, not original words (s.176, s.179).

Slide coverage

Slide	Content	Covered in
151	Cosine similarity, Hello/World table, plugging in i=2	Detailed notes 1; Formulas
152	Result 0.71	Detailed notes 1
153	2-D plot, 45°, cos(45°)=0.71	Detailed notes 1; Figures
154	Note: only 2 different words in table	Detailed notes 1
155	Can plot on 2-D graph	Detailed notes 1
156	Hello on x-axis	Detailed notes 1
157	World on y-axis	Detailed notes 1
158	More than 2 words needs more dimensions	Detailed notes 1
159	Example phrases Troll 2 / Gymkata	Detailed notes 1
160	Phrase A = I love Troll 2!	Detailed notes 1
161	Phrase B = I love Gymkata!	Detailed notes 1
162	5-word count table	Detailed notes 1
163	Needs 5-D graph	Detailed notes 1
164	Cannot draw 5-D graph	Detailed notes 1
165	Equation comes in handy	Detailed notes 1
166	Plug numbers into equation	Detailed notes 1; Formulas
167	Result 0.58	Detailed notes 1
168	Cosine similarity between phrases is 0.58	Detailed notes 1
169	Summary of cosine similarity	Detailed notes 1
170	Document-term matrix of toy corpus	Detailed notes 2
171	Shape n by m; high-dimensional, sparse	Detailed notes 2
172	Just counting no semantic; cosine zero	Detailed notes 3
173	Feature selection	Detailed notes 4
174	Dimensionality reduction, algorithms	Detailed notes 5
175	Linear (PCA) vs nonlinear (manifold)	Detailed notes 5; Figures
176	Linear projection to document-topic matrix	Detailed notes 6
177	How to find projection matrix (LSA/SVD, NMF)	Detailed notes 6
178	SVD definition and properties	Detailed notes 7
179	SVD users-to-movies example	Detailed notes 7
180	Reduced SVD	Detailed notes 7

Previous: 02 Pre-processing - Chunk 05 (s.121-150) | Next: 02 Pre-processing - Chunk 07 (s.181-193) | Up: 02 Pre-processing - Index