t-SNE Algorithm

t-distributed Stochastic Neighbor Embedding

Probabilistic Foundation

Master conditional probabilities and neighbor distributions

Algorithm Mechanics

Understand symmetric SNE and t-distribution innovation

Parameter Tuning

Learn perplexity selection and optimization strategies

Practical Applications

Apply t-SNE effectively while avoiding common pitfalls

Why t-SNE? The Crowding Problem

The Challenge: High-dimensional neighborhoods cannot fit in low-dimensional space. Points that are far apart in high dimensions become artificially close in 2D/3D embeddings.

Traditional Methods' Failures

  • PCA: Linear assumptions miss manifold structure
  • MDS: Preserves all distances, loses local detail
  • Isomap: Geodesic distances, but still global focus
  • LLE: Local preservation, but unstable

The Crowding Problem

  • High-D: many points at similar distances
  • Low-D: limited space for all those points
  • Result: distant points crush together
  • Local neighborhoods get destroyed

t-SNE's Solution: Focus on preserving local neighborhoods only. Use probability distributions to handle uncertainty in neighbor relationships.

From SNE to t-SNE

Original SNE

Asymmetric probabilities

Difficult optimization

→

Symmetric SNE

Simplified gradients

Better convergence

→

t-SNE

Heavy-tailed distribution

Solves crowding problem

Key Innovations

  • Probabilistic approach: Neighbor relationships as probabilities
  • Perplexity: Effective neighborhood size parameter
  • Symmetric formulation: Simpler optimization landscape
  • Student-t distribution: Heavy tails prevent crowding

The t-SNE Insight

Use different probability distributions in high and low dimensions to solve the crowding problem while preserving local structure.

Mathematical Foundation

High Dimensions

Gaussian Distribution

$$p_{j|i} = \frac{\exp(-||x_i - x_j||^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-||x_i - x_k||^2 / 2\sigma_i^2)}$$

Conditional probabilities

vs

Low Dimensions

Student-t Distribution

$$q_{ij} = \frac{(1 + ||y_i - y_j||^2)^{-1}}{\sum_{k \neq l} (1 + ||y_k - y_l||^2)^{-1}}$$

Heavy-tailed distribution

Perplexity and Bandwidth

$$\text{Perp}(P_i) = 2^{H(P_i)}$$

$$H(P_i) = -\sum_j p_{j|i} \log_2 p_{j|i}$$

Effective number of neighbors

Objective Function

  • Minimize KL divergence between P and Q
  • $$C = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}}$$
  • Symmetric probabilities: $p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}$

The t-SNE Algorithm

Algorithm Steps

1. Compute High-D Probabilities

  • Calculate pairwise distances
  • Binary search for optimal σᵢ values
  • Ensure target perplexity
  • Symmetrize: $p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}$

2. Initialize Low-D Embedding

  • Random Gaussian initialization
  • Small variance (σ = 10⁻⁴)
  • Center around origin

3. Optimize Embedding

  • Compute low-D probabilities qᵢⱼ
  • Calculate gradient of KL divergence
  • Update positions with momentum
  • Repeat until convergence

Gradient Computation

$$\frac{\delta C}{\delta y_i} = 4 \sum_j (p_{ij} - q_{ij})(y_i - y_j)(1 + ||y_i - y_j||^2)^{-1}$$

Key Implementation Details

  • Early exaggeration: Multiply P by 4 for first 50 iterations
  • Momentum: Accelerates convergence, prevents oscillation
  • Learning rate: Typically 100-1000
  • Iterations: Usually 1000+ for convergence

Critical Parameters

Perplexity (5-50)

  • Low values (5-15): Local structure, tight clusters
  • High values (30-50): More global awareness
  • Rule of thumb: 5-50, often 30 works well
  • Dataset dependent: Larger datasets can use higher values

Learning Rate (10-1000)

  • Too low: Slow convergence, local minima
  • Too high: Unstable optimization, poor quality
  • Typical range: 100-1000
  • Adaptive: Some implementations adjust automatically

Number of Iterations (1000+)

  • Early phase: Rough positioning (250 iterations)
  • Fine-tuning: Detailed structure (750+ iterations)
  • Convergence: Monitor KL divergence decrease
  • Quality vs time: More iterations = better results

Early Exaggeration (4-12)

  • Purpose: Encourage separation of clusters
  • Duration: First 50-250 iterations
  • Effect: Clusters move apart, create space
  • Value: Usually 4, sometimes up to 12

t-SNE Strengths and Applications

✓ Strengths

  • Exceptional local structure: Preserves neighborhoods beautifully
  • Cluster revelation: Makes hidden clusters visible
  • Non-linear manifolds: Handles complex curved structures
  • Flexible distances: Works with various similarity metrics
  • Intuitive results: Often matches human expectations

✗ Limitations

  • No global structure: Cluster distances meaningless
  • Computational cost: O(n²) complexity
  • Parameter sensitivity: Results vary with settings
  • No deterministic results: Random initialization effects
  • No new point projection: Must recompute for new data

Success Stories

  • Single-cell genomics
  • Image dataset exploration
  • Word embedding visualization
  • Document clustering
  • Biological data analysis

When t-SNE Excels

  • Exploratory data analysis
  • Cluster discovery
  • Pattern visualization
  • Quality assessment
  • Presentation purposes

When to Avoid

  • Need global distance preservation
  • Very large datasets (>10k points)
  • Streaming/online scenarios
  • Quantitative analysis
  • Production ML pipelines

Implementation Challenges

Computational Reality: Standard t-SNE has O(n²) complexity in both time and memory, making it impractical for large datasets without approximations.

Computational Bottlenecks

  • Distance computation: O(n²) pairwise distances
  • Probability calculation: Expensive normalization
  • Gradient computation: All-pairs interactions
  • Memory requirements: Store n×n probability matrices

Barnes-Hut Approximation

  • Idea: Approximate distant point interactions
  • Tree structure: Hierarchical space partitioning
  • Complexity: O(n log n) instead of O(n²)
  • Trade-off: Speed vs accuracy

Practical Guidelines

  • Dataset size: Standard t-SNE up to ~10k points
  • Barnes-Hut: Up to ~100k points
  • Preprocessing: PCA to 50 dimensions first
  • Sampling: Use subset for exploration

Modern Alternatives

  • UMAP: Faster, preserves more global structure
  • FIt-SNE: Faster t-SNE implementation
  • Multicore-TSNE: Parallel processing
  • openTSNE: Modern, optimized implementation

Avoiding Common Pitfalls

Interpretation Mistakes

  • Distance fallacy: Cluster distances are meaningless
  • Size interpretation: Cluster sizes don't reflect data density
  • Isolated points: May be artifacts, not real outliers
  • Multiple runs: Different results don't mean errors

Parameter Pitfalls

  • Wrong perplexity: Too low = fragmented clusters
  • Insufficient iterations: Premature stopping
  • Poor learning rate: Unstable or slow optimization
  • No preprocessing: Scaling issues with raw data

Best Practices

Data Preparation

  • Standardize features (zero mean, unit variance)
  • Remove or handle missing values
  • Consider PCA preprocessing for very high dimensions
  • Remove duplicates and near-duplicates

Parameter Selection

  • Try multiple perplexity values (10, 30, 50)
  • Run multiple times with different seeds
  • Monitor convergence (KL divergence)
  • Use early exaggeration appropriately

Validation

  • Compare with known structure
  • Test with different parameters
  • Validate clusters with domain knowledge
  • Use quantitative metrics when possible

Key Takeaways

t-SNE's Legacy: Revolutionized data visualization by solving the crowding problem through probabilistic neighborhood preservation and heavy-tailed distributions.

Core Insights

  • Local focus: Prioritize neighborhood preservation over global distances
  • Probabilistic approach: Handle uncertainty in neighbor relationships
  • Heavy-tailed solution: Student-t distribution prevents crowding
  • Parameter sensitivity: Perplexity critically affects results

When to Use t-SNE

  • Exploratory data analysis and visualization
  • Cluster discovery in high-dimensional data
  • Pattern recognition and anomaly detection
  • Quality assessment of embeddings
  • Presentation and communication purposes

Limitations to Remember

  • Global structure loss: Cluster distances meaningless
  • Computational complexity: Doesn't scale to very large data
  • Stochastic results: Different runs give different outputs
  • No out-of-sample: Can't project new points easily

Modern Context

  • Still excellent for small-medium datasets
  • UMAP often preferred for larger datasets
  • Remains gold standard for local structure
  • Essential tool in data scientist toolkit
  • Continues to inspire new methods
1 / 10