t-SNE for visualization

The Core Idea

Goal: Map high-dimensional points $\mathbf{x}_1, \ldots, \mathbf{x}_n \in \mathbb{R}^d$ to low-dimensional points $\mathbf{y}_1, \ldots, \mathbf{y}_n \in \mathbb{R}^2$ (or 3D) such that similar points stay similar.

How?

1. In high-D space, define a probability $p_{ij}$ that point $i$ picks $j$ as its neighbor (based on Gaussian similarity).
2. In low-D space, define a probability $q_{ij}$ thati$picks$j$ (using a t-distribution with1 degree of freedom, heavier tails).
3. Make $q_{ij}$ match $p_{ij}$ by minimizing the KL-divergence: $\text{KL}(P \| Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$.

Why t-distribution in low-D? The crowding problem: in100D, you can fit many points equidistant from a center. In 2D, they'd overlap. The t-distribution's heavy tails let moderately-distant points spread out more, reducing overlap.

Step-by-Step Derivation

Step 1: High-Dimensional Similarities $p_{ij}$

For each point $i$, we compute conditional probability that $i$ picks $j$ as neighbor:

Why Gaussian? We model similarity as a Gaussian centered at $\mathbf{x}_i$. The $\sigma_i$ (called perplexity in practice) controls neighborhood size.

Symmetrize to get joint probability:

Why symmetrize? So $p_{ij} = p_{ji}$ (no direction bias), and $\sum_{ij} p_{ij} = 1$ (valid probability distribution).

Step 2: Low-Dimensional Similarities $q_{ij}$

In 2D, use Student's t-distribution (1 degree of freedom):

Why t-distribution? Compare to Gaussian in low-D:

• Gaussian: $e^{-\|\mathbf{y}_i - \mathbf{y}_j\|^2}$ → decays fast, far points vanish.
• t-distribution: $(1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2)^{-1}$ → decays slower (heavy tail), far points still contribute, giving them room to spread.

Step 3: Minimize KL Divergence

The cost function is:

Why this direction (not $\text{KL}(Q \| P)$)? $\text{KL}(P \| Q)$ heavily penalizes $q_{ij} \ll p_{ij}$ (nearby points pushed apart) but lightly penalizes $q_{ij} \gg p_{ij}$ (far points too close). We care more about preserving local structure (nearby points), so this asymetry is correct.

Gradient:

Why this gradient?

• $(p_{ij} - q_{ij})$: If $p_{ij} > q_{ij}$, points $i,j$ are too far in2D → pull together. If $p_{ij} < q_{ij}$, they're too close → push apart.
• $(\mathbf{y}_i - \mathbf{y}_j)$: direction of force.
• $(1 + \|\cdots\|^2)^{-1}$: the t-distribution weight, ensures smooth gradients.

We optimize via gradient descent (often with momentum + early exaggeration trick).

Hyperparameters

Other key parameters:

• Learning rate (typically 100–1000): too low = slow convergence, too high = instability.
• Number of iterations (1000–5000): t-SNE optimizes via gradient descent, needs many steps.
• Early exaggeration (first ~250 iterations): multiply $p_{ij}$ by 4 to create tight, well-separated clusters, then reduce to 1 for fine-tuning.

Worked Example1: 3D Gaussian Blobs to 2D

Data: 3 clusters in 3D, each cluster is a Gaussian blob with 100 points.

Cluster A: centered at (0,0,0), σ=0.5
Cluster B: centered at (5,0,0), σ=0.5
Cluster C: centered at (2.5, 4, 0), σ=0.5

Step 1: Compute $p_{ij}$ for all pairs (300 × 299 / 2 = 44,850 pairs).

• For two points in cluster A, $\|\mathbf{x}_i - \mathbf{x}_j\|^2 \approx 0.5$, so $p_{ij}$ is large.
• For a point in A and a point in B, $\|\mathbf{x}_i - \mathbf{x}_j\|^2 \approx 25$, so $p_{ij} \approx 0$.

Step 2: Initialize $\mathbf{y}_i$ randomly in2D (say, uniform in $[-0.001, 0.0001]$).

Step 3: Compute $q_{ij}$ (initially all similar, ~1/44850).

Step 4: Compute gradient. Example: if point $i$ in cluster A is far from its true neighbor $j$ in2D, $p_{ij} - q_{ij} > 0$, gradient pulls them together.

Why this step? The gradient descent iteratively adjusts $\mathbf{y}_i$ to make the2D distribution $Q$ match the high-D distribution $P$.

Iterations: After 1000 steps, clusters A, B, C form3 distinct blobs in 2D. Global distances (A-to-B vs A-to-C) may be distorted, but within-cluster and between-cluster separation is preserved.

Worked Example 2: MNIST Digits

Data: 60,000 images 784 pixels each (28×28 flattened).

Perplexity = 30: Each digit considers ~30 neighbors.

Process:

1. Compute $p_{ij}$ for60k points (sparse: only store top neighbors per point, ~1.8 billion pairs total → use approximate methods like Barnes-Hut to speed up).
2. Run gradient descent for 5000 iterations.
3. Result: 10 distinct clusters (one per digit 0-9) in 2D. Some overlap (e.g., 4 and 9 are visually similar).

Why is this useful? A human can now visually inspect the learned representation: Are there outliers? Do digits form coherent clusters? Is there a smooth transition (manifold) between similar digits?

Common Mistakes

Comparison: PCA vs t-SNE

| Aspect | PCA | t-SNE | |--------|----| | Preserves | Global variance (linear) | Local neighborhoods (non-linear) | | Deterministic? | Yes | No (random init) | | Speed | Fast ($O(nd^2)$) | Slow ($O(n^2)$, ~$O(n \log n)$ with Barnes-Hut) | | Interpretable axes? | Yes (principal components) | No (arbitrary coordinates) | | Use case | Quick EDA, preprocessing | Final visualization for publication/EDA |

Algorithm Pseudocode

1. Compute pairwise squared distances in high-D: D[i,j] = ||x_i - x_j||²
2. For each point i:
     Binary search σ_i to achieve desired perplexity
     Compute p_j|i = exp(-D[i,j] / 2σ_i²) / Σ_k exp(-D[i,k] / 2σ_i²)
3. Symmetrize: p_ij = (p_j|i + p_i|j) / 2n
4. Initialize y_i ~ N(0,10⁻⁴ I) randomly in 2D
5. For t = 1 to max_iter:
     Compute q_ij = (1 + ||y_i - y_j||²)⁻¹ / Z
     Compute gradient: ∂C/∂y_i = 4 Σ_j (p_ij - q_ij)(y_i - y_j)(1 + ||y_i - y_j||²)⁻¹
     Update y_i via gradient descent with momentum
     (Optional: early exaggeration in first 250 iters)
6. Return y_1, .., y_n (2D coordinates)

Why t-SNE Works: The Math Intuition

Crowding problem: In 100D, a sphere of radius $r$ has volume $\propto r^{100}$. In 2D, volume $\propto r^2$. So 100D neighbors can't all fit equidistant in 2D → they'd crowd/overlap.

Solution: The t-distribution $(1 + d^2)^{-1}$ decays like $d^{-2}$ for large $d$, much slower than Gaussian's $e^{-d^2}$. This gives heavy tails: moderately-far points in 2D can still have non-negligible $q_{ij}$, so they repel less and spread out naturally.

Force analogy: Each pair $(i,j)$ exerts a force:

• Attractive if $p_{ij} > q_{ij}$ (they should be closer).
• Repulsive if $p_{ij} < q_{ij}$ (they should be farther).
• The equilibrium $p_{ij} = q_{ij}$ is a local minimum of KL.

Connections

• 2.5.1 PCA: Linear dimensionality reduction, preserves global variance. t-SNE is non-linear, preserves local structure.
• 2.5.10 UMAP: Similar goal (local structure preservation), but faster and deterministic with hyperparameters. Often compared to t-SNE.
• 2.4.3 K-Means Clustering: After t-SNE visualization, you might use k-means on the original high-D data to formally cluster.
• 3.2.1 Autoencoders: Non-linear dimensionality reduction via neural networks. Can be used for visualization + downstream tasks (unlike t-SNE).
• 1.3.5 KL Divergence: The core loss function in t-SNE. Understanding KL(P||Q) asymetry is crucial.
• 2.5.9 Manifold Learning: t-SNE assumes data lies on a low-D manifold in high-D space.

When to Use t-SNE

✅ Use when:

• You have high-dimensional data (50+ features) and want to visualize clusters for human interpretation.
• You need to explore data before modeling (EDA).
• You're presenting results in a paper/report and want a compelling2D scatter plot.

❌ Don't use when:

• You need reproducible, deterministic embedings (use PCA or UMAP).
• You need to embed new test data (t-SNE has no inverse mapping; use parametric t-SNE or autoencoders).
• Data is already low-D (3–5 features): just use scatter plots or PCA.
• You need embedings for downstream ML tasks (classification, regression): use PCA, LDA, or autoencoders.

Practical Tips

1. Perplexity: Start with 30. Increase for large datasets (1M points → perplexity 50–100), decrease for tiny datasets (100 points → perplexity 5–15).
2. Multiple runs: t-SNE is stochastic. Run 3–5 times with different seeds and check consistency. If results vary wildly, your data may not have clear structure.
3. Preprocessing: Standardize features (mean=0, std=1) before t-SNE. High-variance features dominate distances.
4. Coloring: Color points by known labels (if available) to validate cluster separation.
5. Barnes-Hut approximation: For $n > 5000$, use Barnes-Hut t-SNE (available in scikit-learn) to reduce complexity from $O(n^2)$ to $O(n \log n)$.

#flashcards/ai-ml

What does t-SNE stand for? :: t-Distributed Stochastic Neighbor Embedding

Low-D similarity formula in t-SNE? :: $q_{ij} = \frac{\left(1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2\right)^{-1}}{\sum_{k \neq l} \left(1 + \|\mathbf{y}_k - \mathbf{y}_l\|^2\right)^{-1}}$

Concept Map

Hinglish (regional understanding)