Perplexity as an Effective Neighborhood Size

Perplexity Measures the Spread of a Cell’s Conditional Neighbors

In t-SNE, each cell \(i\) is associated with a conditional probability distribution over the other cells. The distribution gives higher probability to cells that are closer to \(i\) in the original space. Perplexity summarizes how spread out that distribution is: it is the effective number of neighbors receiving probability mass, not a literal count of neighbors selected by a cutoff.

The bandwidth is adjusted separately for each cell so that these conditional distributions have a specified perplexity. This matters when cells occupy regions with different distance scales. A single bandwidth could make neighborhoods too concentrated in one region and too diffuse in another.

If the probability is uniform over exactly \(k\) cells and zero elsewhere, then \(H_i=\log_2 k\), so \(\operatorname{Perp}_i=k\). For a nonuniform distribution, perplexity is the number of equally likely neighbors that would give the same entropy. It is generally not an integer.

Bandwidth Controls Entropy

Let \(d_{ij}^2\) denote the squared distance between cells \(i\) and \(j\) in the representation used to construct t-SNE’s input similarities. Excluding the self-comparison \(j=i\), the conditional probabilities have the Gaussian-weight form

Here \(\sigma_i>0\) is the bandwidth for cell \(i\), and \(\beta_i\) is its inverse-variance parameter. Increasing \(\beta_i\) (equivalently, decreasing \(\sigma_i\)) makes differences in distance matter more, concentrating probability on the nearest cells. Decreasing \(\beta_i\) spreads probability more evenly. The target perplexity \(P^*\) is set by the analyst; the algorithm seeks a bandwidth for each cell whose conditional distribution has perplexity near \(P^*\).

The limits describe the attainable range. With distinct nearest distances, perplexity approaches 1 at the concentrated end, but does not equal 1 for a finite bandwidth when there are other cells at finite distances. Tied nearest cells can make the smallest attainable perplexity greater than 1.

Why Binary Search Works

The monotonicity of entropy provides the basis for binary search. To see it, write \(q_j=d_{ij}^2\), \(Z(\beta)=\sum_{j\ne i}\exp(-\beta q_j)\), and use natural-log entropy temporarily. The resulting entropy in bits is the natural-log entropy divided by \(\ln 2\).

Differentiating \(\ln Z\) gives \(-\mathbb{E}_{p_\beta}[q]\), while differentiating the probability-weighted mean distance gives \(-\operatorname{Var}_{p_\beta}(q)\). Therefore,

For \(\beta>0\), the derivative is strictly negative whenever the squared distances are not all equal. Thus a trial value of \(\beta\) gives an entropy that can be compared with the target \(\log_2 P^*\). If the trial entropy is too high, increase \(\beta\); if it is too low, decrease \(\beta\). Repeatedly halving a bracket around the target is a straightforward binary search.

Implementations often search in \(\beta_i\) or in \(\log \beta_i\), and use numerical tolerances rather than requiring exact equality. The search is performed for each cell because each cell has its own set of distances.

How Bandwidths Adapt to Local Distance Scales

A fixed target perplexity does not imply a fixed bandwidth. A cell in a dense region may have small distances to its neighbors, while a cell in a sparse region may have much larger distances. To obtain similarly concentrated probability distributions, the dense-region cell will generally need a smaller \(\sigma_i\), and the sparse-region cell a larger \(\sigma_i\). This is adaptation to local distance scale, not a direct estimate of cell density.

The target perplexity is a tuning choice, not a guarantee of a particular biological neighborhood. Conditional probabilities depend on the supplied representation, distance metric, and cell set. Even when two cells have the same perplexity, their probability mass can be distributed over different cells and with different shapes.

Feasibility, Diagnostics, and Alternatives

Before trusting a binary search, check whether the target is attainable for each cell. If there are \(n\) cells, each conditional distribution has \(n-1\) candidate neighbors, so its perplexity cannot exceed \(n-1\). At the concentrated end, ties among nearest cells can impose a lower limit above 1. For example, if two cells are tied at the minimum distance, their limiting probabilities are \(1/2\) each and the limiting perplexity is 2.

Other useful diagnostics include checking that probabilities sum to 1, that the reported perplexity is close to the target, and that the fitted bandwidths are finite and positive. A very large or very small bandwidth can reflect unusual distances, duplicates, a target near a limit, or preprocessing problems. Underflow in \(\exp(-\beta_i d_{ij}^2)\) can also make some weights numerically zero; stable implementations rescale exponents or use log-probability calculations.

A fixed Gaussian bandwidth is a simple alternative, but it does not adapt to different local distance scales. A fixed-\(k\) nearest-neighbor rule instead selects a number of neighbors, whereas perplexity controls entropy: with nonuniform probabilities, its effective number can differ from the number of neighbors with appreciable weight. Neither choice removes the need to inspect distances and assess whether the resulting neighborhoods are appropriate. Perplexity is not a cluster count, a hard radius, or proof that cells form discrete populations.