Dimensionality Reduction and Visualization

Definition Dimensionality reduction replaces each feature vector $\mathbf{x} \in \mathbb{R}^p$ by a vector $\mathbf{z} \in \mathbb{R}^d$ with $d < p$. A linear method such as PCA fits a map, $\mathbf{z} = V_d^{\top}(\mathbf{x} - \bar{\mathbf{x}})$ with training mean $\bar{\mathbf{x}}$ and loadings $V_d$, that applies to any new observation. A nonlinear embedding such as t-SNE computes coordinates for the observations it is fitted on, and a method may or may not provide a map for new ones. Keeping a subset of the original features is the special case called feature selection. When the reduced coordinates feed a model that will be evaluated, the reduction is fitted on training data only. What counts as success depends on the purpose. Compression is judged by reconstruction error at a given storage cost, prediction by the held-out performance of the model that uses the coordinates, and visualization by how faithfully the plot shows the relationships it is meant to show, usually local neighborhoods.

Definition A PCA pipeline is an ordered sequence of fitted steps, for example imputation of missing values, scaling, PCA with $k$ components and a predictor. Fitting the pipeline on training rows estimates every step there, the imputation values, the means and standard deviations, the PCA mean and loadings, and then the predictor’s parameters from the training scores. Predicting for a new row applies the same fitted steps in the same order, without refitting any of them. In cross-validation the whole pipeline is refitted on the training part of each fold. The number of components $k$ is a hyperparameter chosen by the downstream validation score, inside an inner loop when the same data also estimate performance. Fitting the scaler or the PCA on all rows, held-out rows included, lets the held-out features shape the coordinate system, so the evaluation no longer describes a pipeline applied to new data and can be biased, even though PCA never sees the labels.

Definition A reduction $\mathbf{z} = f(\mathbf{x})$ loses information about a quantity when that quantity cannot be recovered from $\mathbf{z}$. For PCA with $k$ components, the discarded part of a centered observation $\mathbf{x}_c$ is $\mathbf{x}_c - V_k V_k^{\top}\mathbf{x}_c$, whose squared length is its reconstruction error. For a target, the loss appears as collisions. If $f(\mathbf{x}) = f(\mathbf{x}')$, every predictor that sees only $\mathbf{z}$ gives the two observations the same prediction, so when their targets differ at least one of them is predicted wrongly. PCA ranks directions by variance and never uses the target, so a direction with little variance that determines the target can be discarded while the explained variance ratio stays close to $1$.

Definition Fix a representation of $n$ observations, a distance and an integer $k$ with $1 \le k \le n - 1$. The $k$-neighborhood $N_k(i)$ of observation $i$ is the set of the $k$ other observations closest to it, with ties broken by a fixed rule. The local neighborhood structure of the data is the collection of these sets, or equivalently the $k$-nearest-neighbor graph that joins each observation to its neighbors. A low-dimensional map preserves it to the degree that the neighborhoods $N_k'(i)$ computed in the map agree with those of the original representation, which can be measured by the average overlap

a number between $0$ and $1$. The structure depends on the features, their scaling, the distance and $k$.

Definition The t-distributed stochastic neighbor embedding, or t-SNE, places observations $\mathbf{x}_1, \dots, \mathbf{x}_n$ as points $\mathbf{y}_1, \dots, \mathbf{y}_n$ in a low-dimensional space, usually the plane. For each $i$ and each $j \ne i$ it sets

a conditional distribution over the other observations with its own bandwidth $\sigma_i > 0$. The perplexity of that distribution is

and each $\sigma_i$ is found by a numerical search so that this perplexity equals one value set by the user, also called the perplexity. A uniform distribution over $m$ observations has perplexity $m$, so perplexity is an effective number of neighbors. It always lies between $1$ and $n - 1$, and it is $n - 1$ for every bandwidth when all other observations are equally far from $\mathbf{x}_i$, so the setting has to be smaller than $n - 1$. Typical values are between 5 and 50. The input affinities are symmetrized, and the map affinities use a Student t kernel with one degree of freedom,

The points $\mathbf{y}_i$ minimize the Kullback-Leibler divergence

by gradient descent from a random or PCA-based start. The objective is not convex, so different starts and settings can end in different layouts. Standard t-SNE produces coordinates only for the observations it was fitted on.

Definition Uniform manifold approximation and projection, or UMAP, as defined in its original paper, first finds the $k$ nearest neighbors $N_k(i)$ of each observation, where $k$ is the neighbor count set by the user. Let $d_{ij}$ be the distance between observations $i$ and $j$, and let $\rho_i$ be the distance from observation $i$ to its nearest neighbor at positive distance. The directed weights are

for $j \in N_k(i)$, with $w_{i \to j} = 0$ for every other $j$. The local scale $\sigma_i > 0$ is found by a numerical search so that the $k$ weights of observation $i$ add to $\log_2 k$, or come as close to it as the distances allow. The directed weights are combined by

a number between $0$ and $1$ for each pair. In the map, similarity is $v_{ij} = (1 + a \lVert \mathbf{y}_i - \mathbf{y}_j \rVert_2^{2b})^{-1}$, with constants $a, b > 0$ fitted to the minimum distance setting, which controls how tightly points can pack. The points minimize $\sum_{i < j} c(w_{ij}, v_{ij})$, where

with $0 \ln 0$ read as $0$, by stochastic gradient descent with sampled non-neighbor pairs, usually starting from a spectral layout of the graph. Some implementations can place new observations into a fitted map, which does not remove concerns about distribution shift or information loss.