Dimensionality Reduction

Source: Concepts adapted from Ace the Data Science Interview — Chapter 7 (“Machine Learning”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course. Coding uses scikit-learn / NumPy on Piston.

Imagine a million rows and two million mostly-null features. Points sit far apart in a huge sparse space — “similarity” and neighborhoods stop meaning much. That is the curse of dimensionality. Collecting more data often is not feasible; hand-picking features among millions is painful. Dimensionality reduction compresses $X$ into fewer coordinates that still carry most of the signal — for modeling, summarization, and 2D/3D visualization.

This lesson covers the curse, PCA (principal components analysis), and a brief contrast with t-SNE. Linear-algebra warm-up lives in Math Behind ML.

Curse of dimensionality

In high-$p$ spaces with limited $n$:

• Distances concentrate — nearest and farthest neighbors look alike.
• Sparse coverage — most orthants / regions have no samples.
• Overfit risk rises for flexible models; noise features drown signal.

Remedies: more data (costly), feature selection / dropping collinear columns, or projection / embedding into $k \ll p$ dimensions.

Quiz

Curse of dimensionality

1 / 3

The curse of dimensionality (ML intuition) is mainly that…

Pick an answer to see if you are right.

Principal components analysis (PCA)

PCA builds a small set of principal components — orthogonal linear combinations of the original features that capture as much variance as possible, in order.

Find weight vector $w$ so $y = Xw$ (centered $X$) has maximal variance, with $\|w\|=1$. The next component maximizes variance subject to being uncorrelated / orthogonal to previous ones. In practice this is an eigendecomposition of $\mathrm{Cov}(X)$ (or SVD of the centered matrix):

• PC1 ↔ eigenvector for the largest eigenvalue $\lambda_1$
• PC2 ↔ next largest $\lambda_2$, and so on

Choose $k$ so the top components explain enough cumulative variance:

$$\frac{\lambda_1+\cdots+\lambda_k}{\lambda_1+\cdots+\lambda_p} \ge \text{threshold} \quad (k \ll p)$$

Assumptions / pitfalls (interview favorites):

• Linear combinations — nonlinear manifolds need other tools.
• Sensitive to scale — standardize features (different units otherwise dominate).
• Sensitive to outliers — they inflate variance directions.
• Components maximize variance, not “predict $y$” — supervised selection may still be needed.

t-SNE is a nonlinear, stochastic embedding used mainly for visualization, not a drop-in linear PCA substitute for pipelines.

Quiz

PCA

1 / 4

PCA’s first principal component is…

Pick an answer to see if you are right.

Compute

Compute: explained variance

1 / 5

Story problem — figure out which numbers are the formula inputs, then compute.

Eigenvalues λ=[5, 2, 1, 1]. What fraction of variance does PC1 explain (λ₁/Σλ)? Round to 2 decimals.

Enter a number (at most 2 decimal places).

Practice: PCA math & sklearn

Quick synthesis

Topic	Sound bite
Curse	High $p$, sparse data → distances / neighborhoods break
PCA	Orthogonal max-variance directions = top eigenvectors of Cov
Choose $k$	Cumulative explained variance threshold
Pitfalls	Scale, outliers, linearity assumption
t-SNE	Nonlinear viz embedding — not the same tool as PCA

Together with forests & boosting, you now have the Ace Ch.7 ensemble + compression toolkit. Next: Clustering — k-means, DBSCAN, GMM.