Dimensionality Reduction

Dimensionality Reduction: Trade-offs and Techniques

In this blog, we discuss some trade-offs involved when choosing a Dimensionality Reduction (DR) technique. Dimensionality reduction aims to represent high-dimensional data in a lower-dimensional space while preserving as much meaningful structure as possible.

$$ f : \mathbb{R}^n \to \mathbb{R}^k, \quad k < n $$

The goal is to find a mapping \( f \) that captures the essential relationships among the data points in \( \mathbb{R}^n \) within a lower-dimensional space \( \mathbb{R}^k \). However, depending on the technique used, distortions such as artificial clusters or misplaced neighbors may appear. We will focus on three widely used methods: t-SNE, UMAP, and TriMap.

1. t-SNE (t-distributed Stochastic Neighbor Embedding)

t-SNE models the pairwise similarities between points in both the high-dimensional and low-dimensional spaces using probability distributions.

In the high-dimensional space, the conditional probability of point \( x_j \) being a neighbor of \( x_i \) is defined as:

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

Here, \( \sigma_i \) controls the local neighborhood size around point \( x_i \) and is chosen such that the perplexity of the distribution equals a user-defined value:

$$ \text{Perplexity}(P_i) = 2^{-\sum_j p_{j|i} \log_2 p_{j|i}} $$

To make the similarity symmetric, we define:

$$ p_{ij} = \frac{p_{i|j} + p_{j|i}}{2n} $$

In the low-dimensional space, a Student-t distribution with one degree of freedom (equivalent to a Cauchy distribution) is used to measure similarity:

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

The cost function minimizes the Kullback–Leibler (KL) divergence between the high- and low-dimensional distributions:

$$ \mathcal{L}_{\text{t-SNE}} = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}} $$

The embedding \( y_i \) is initialized from a small Gaussian distribution:

$$ y_i \sim \mathcal{N}(0, 10^{-4} I) $$

Notation:
\( x_i, x_j \in \mathbb{R}^n \): high-dimensional data points
\( y_i, y_j \in \mathbb{R}^k \): corresponding low-dimensional embeddings
\( \sigma_i \): local variance parameter (determined by perplexity)
\( p_{ij}, q_{ij} \): pairwise similarity probabilities in high and low dimensions
\( n \): number of data points

2. UMAP (Uniform Manifold Approximation and Projection)

UMAP constructs a weighted graph from high-dimensional data that approximates the local manifold structure, then optimizes a corresponding low-dimensional layout that preserves these relationships.

The algorithm proceeds in two stages:

1. Graph Construction: A fuzzy topological representation is built by connecting each point to its nearest neighbors with membership strength based on distance and local connectivity.
2. Graph Optimization: The low-dimensional embedding is found by minimizing a cross-entropy loss between high- and low-dimensional graphs.

$$ \mathcal{L}_{\text{UMAP}} = \sum_{(i,j)} \Big[ w_{ij} \log \frac{w_{ij}}{w'_{ij}} + (1 - w_{ij}) \log \frac{1 - w_{ij}}{1 - w'_{ij}} \Big] $$

Notation:
\( w_{ij} \): edge weight (similarity) in high-dimensional graph
\( w'_{ij} \): corresponding edge weight in low-dimensional graph
\( (i,j) \): pair of neighboring points

3. TriMap

TriMap takes a different approach by considering triplets of points rather than pairs. It seeks an embedding that preserves the relative ordering of distances among triplets.

Given a triplet \((i, j, k)\), the objective is to ensure that if \(x_i\) is closer to \(x_j\) than to \(x_k\) in high-dimensional space, the same holds true for their low-dimensional representations:

$$ \|x_i - x_j\| < \|x_i - x_k\| \quad \Longrightarrow \quad \|y_i - y_j\| < \|y_i - y_k\| $$

TriMap minimizes a weighted sum of triplet-based loss terms using a smooth logistic function:

$$ \mathcal{L}_{\text{TriMap}} = \sum_{(i,j,k)} w_{ijk} \, \log\!\left(1 + \exp\!\big(\|y_i - y_j\|^2 - \|y_i - y_k\|^2\big)\right) $$

Notation:
\( (i,j,k) \): triplet of indices
\( w_{ijk} \): weight indicating the importance of triplet \((i,j,k)\)
\( y_i, y_j, y_k \in \mathbb{R}^k \): low-dimensional representations

4. Parametric vs. Non-Parametric Mapping

Dimensionality reduction methods can be categorized as:

• Parametric: Learn a mapping function \( f_\theta \) so that new points can be directly embedded using the same parameters \( \theta \). Example: Parametric t-SNE, Autoencoders.
• Non-Parametric: The embedding is learned only for the training data. New points require recomputation of the entire mapping. Example: standard t-SNE, UMAP, TriMap.

References

1. TriMap: Large-scale Dimensionality Reduction Using Triplets
2. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
3. Parametric t-SNE