Visualizing Data using t-SNE (t-SNE)

Implements t-Distributed Stochastic Neighbor Embedding (t-SNE), a nonlinear dimensionality reduction algorithm that converts high-dimensional data (e.g., 784-dimensional image vectors) into 2D or 3D visualizations by modeling pairwise similarities as Student-t distributions in low-dimensional space. Uses gradient descent optimization with symmetric KL-divergence minimization to preserve local neighborhood structure while revealing global clustering patterns. The algorithm employs Barnes-Hut approximation for O(N log N) computational efficiency on large datasets, avoiding O(N²) pairwise distance computation.

Automatically calibrates the perplexity parameter (effective neighborhood size) based on dataset characteristics to balance local vs. global structure preservation. Uses binary search to find the bandwidth σᵢ for each point such that the Shannon entropy of the conditional probability distribution matches the target perplexity, ensuring consistent neighborhood density across heterogeneous data distributions. This adaptive approach prevents over-smoothing in sparse regions and over-clustering in dense regions.

Implements a two-phase stochastic gradient descent optimization strategy: early exaggeration phase (iterations 1-100) amplifies attractive forces between neighbors by scaling P matrix by 4x, accelerating convergence and escaping poor local minima; followed by standard optimization phase with momentum-based updates. Uses adaptive learning rate scheduling and momentum accumulation (typical momentum = 0.5 → 0.8) to balance exploration and convergence speed. Gradient computation leverages efficient pairwise distance calculations and Student-t kernel evaluations.

Approximates O(N²) pairwise distance computations using a space-partitioning tree (quad-tree in 2D, oct-tree in 3D) that groups distant points and computes their aggregate contribution via multipole expansion. For each point, traverses the tree and decides whether to compute exact distances (for nearby nodes) or use aggregated far-field approximation (for distant clusters), reducing complexity to O(N log N). Threshold parameter θ controls accuracy-speed tradeoff: θ = 0 (exact), θ > 0.5 (aggressive approximation).

Minimizes symmetric Kullback-Leibler divergence between high-dimensional (P) and low-dimensional (Q) probability distributions: KL(P||Q) + KL(Q||P). Constructs P matrix from high-dimensional pairwise distances using Gaussian kernels with adaptive bandwidth; constructs Q matrix from low-dimensional embedding using Student-t kernels (heavier tails than Gaussian). The symmetric formulation ensures both attractive forces (matching neighbors) and repulsive forces (pushing non-neighbors apart) are balanced, preventing mode collapse and crowding artifacts. Gradient computation yields closed-form expressions for efficient backpropagation.

Provides tools for practitioners to explore the effect of hyperparameters (perplexity, learning rate, early exaggeration) on embedding quality through interactive visualization and quantitative metrics. Supports side-by-side comparison of embeddings with different parameters, convergence curve plotting, and quality metrics (trustworthiness, continuity, local structure preservation). Enables iterative refinement of parameters based on visual inspection and metric feedback without requiring full retraining from scratch.