Unsupervised Learning — Dimensionality Reduction

Principal Component Analysis (PCA) and t-Distributed Stochastic Neighbor Embedding (t-SNE): two ways to compress high-dimensional data into fewer dimensions, built from scratch in NumPy.

---

Learning Objectives

---

Task-by-Task Reference

Each task entry captures only what is new relative to all previous tasks.

---

Task 0 — PCA with variance preservation (0-pca.py)

Challenge: Find the weights matrix W whose columns pick the directions of maximal variance, keeping only enough components to retain var (default 0.95) of the total variance.

Approach: Decompose X with np.linalg.svd(X, full_matrices=False). The squared singular values are proportional to the covariance eigenvalues, so their cumulative sum over the total gives the variance fraction each prefix of components keeps. np.argmax(frac >= var) + 2 gives the component count — one extra past the crossing, as the reference does — and W = Vt[:nd].T extracts the dominant right singular vectors.

New techniques introduced:

Key takeaway: PCA is an eigendecomposition of the covariance in disguise — SVD gives the same directions without ever building the covariance matrix, and the singular values tell you how much variance each component carries.

---

Task 1 — PCA with fixed dimensions (1-pca.py)

Challenge: Instead of a variance target, project onto a fixed number of components ndim, and make the function validate its own input.

Approach: ndim must be a positive int (else ValueError). Center X (X - np.mean(X, axis=0)) because this time the data is not pre-centered, SVD again for the directions, clamp ndim to the components actually available with min(ndim, Vt.shape[0]), then project: T = X_c @ Vt[:ndim].T.

New techniques introduced:

Key takeaway: Projection is one matmul — the work is picking the right directions; the rest is guarding the input.

---

Task 2 — Initialize P affinities (2-P_init.py)

Challenge: Prepare every variable t-SNE needs for its high-dimensional similarities — distances, the empty affinity matrix, per-point Gaussian precisions, and the entropy target — with no loops.

Approach: Compute pairwise squared distances with the identity ‖x_i−x_j‖² = ‖x_i‖² + ‖x_j‖² − 2·x_i·x_j, using X @ X.T for all dot products and the row-norms sum_X. Zero the diagonal, then hand back an (n,n) zeros matrix for P, (n,1) ones for betas, and the target entropy H = log2(perplexity) (perplexity is defined as 2^H).

New techniques introduced:

Key takeaway: The whole pairwise distance matrix is three array expressions — no nested loops over pairs.

---

Task 3 — Shannon entropy and P affinities (3-entropy.py)

Challenge: For one point, turn its distances into probabilities and measure how "spread out" they are — the quantity the perplexity controls.

Approach: Apply the Gaussian kernel num = exp(-Di * beta), normalize to probabilities Pi = num / num.sum(), then compute the Shannon entropy Hi = -Σ Pi·log2(Pi).

New techniques introduced:

Key takeaway: A bigger beta tightens the Gaussian, concentrates the probabilities, and lowers the entropy — that inverse relationship is what the next task exploits.

---

Task 4 — P affinities (4-P_affinities.py)

Challenge: Give every point its own Gaussian so that all entropies equal the target H — a root-finding problem solved per point, then fuse the one-directional similarities into a symmetric affinity matrix.

Approach: For each point, drop its self-distance (np.delete(D[i], i)), compute the entropy, and run a binary search on beta until |Hdiff| <= tol (capped at 50 tries): entropy too high → double beta, too low → halve it, otherwise bisect between the recorded bounds. Store the row of Pi, then average the matrix with its transpose and divide by 2n: P = (P + P.T) / (2 * n).

New techniques introduced:

Key takeaway: Perplexity is a constraint, not a parameter — each point's Gaussian is solved for, one binary search at a time.

---

Task 5 — Q affinities (5-Q_affinities.py)

Challenge: Measure the same similarities in the low-dimensional space, using a distribution with heavier tails than the Gaussian.

Approach: Same distance trick on Y, then the Student-t kernel num = 1 / (1 + D) — the heavy tails leave more room between clusters in the embedding. Zero the diagonal and normalize: Q = num / num.sum().

New techniques introduced:

Key takeaway: Q has the same pipeline as P — kernel, zero diagonal, normalize — only the kernel changes.

---

Task 6 — Gradient descent (6-grads.py)

Challenge: Decide how each embedded point should move so Q comes closer to P.

Approach: PQ = P - Q marks where the distributions disagree, and the kernel weights num from Q_affinities scale each pair. For each point i, dY[i] = Σ_j PQ(j,i)·num(j,i)·(Y[i] − Y[j]): attracted to neighbors P values higher, repelled where Q dominates.

New techniques introduced:

Key takeaway: The gradient is a sum of pairwise forces — each pair either pulls or pushes, scaled by how much the two distributions differ.

---

Task 7 — Cost (7-cost.py)

Challenge: Score how well the embedding matches the original data, so the training loop has a number to report.

Approach: Floor both matrices with np.maximum(P, 1e-12) (and Q) to keep logs finite, then sum the KL divergence C = Σ P·log(P/Q).

New techniques introduced:

Key takeaway: Cost is 0 when P equals Q and grows as they drift apart — it is the "distance" between the two distributions.

---

Task 8 — t-SNE (8-tsne.py)

Challenge: Chain everything into one transform: PCA preprocessing, affinity building, and a momentum-driven optimization loop with early exaggeration and periodic cost reports.

Approach: PCA to idims, then P × 4 so clusters separate hard in the first 100 iterations (early exaggeration). Initialize Y randomly, keep the previous step for momentum (0.5 for the first 20 iterations, 0.8 after), and update Y = Y − lr·dY + momentum·(Y − Y_prev), re-centering Y each step. Stop exaggerating at iteration 100 and print the cost every 100 iterations.

New techniques introduced:

Key takeaway: The algorithm is a short loop — gradients, momentum, center, report — and every piece was already built in tasks 0–7.

---

Technique Inventory

---

Resources

• t-SNE paper — van der Maaten & Hinton
• PCA — scikit-learn
• t-SNE — scikit-learn
• np.linalg.svd — NumPy
• Shannon entropy — Wikipedia
• Kullback-Leibler divergence — Wikipedia
• Principal component analysis — Wikipedia
• Student's t-distribution — Wikipedia