Why t-SNE Minimizes a KL Divergence

Why Compare Pairwise Probabilities?

t-SNE does not try to reconstruct every original distance in the embedding. Instead, it represents relationships between cells as probability distributions over pairs, then chooses low-dimensional coordinates whose pairwise probabilities resemble those computed from the high-dimensional data. Its objective is the Kullback–Leibler (KL) divergence from the high-dimensional distribution to the embedding distribution.

The direction of this comparison matters. The objective gives substantial cost to a pair that is assigned high probability in the input space but very low probability in the embedding. That asymmetry is central to t-SNE’s emphasis on preserving nearby cells. It does not mean that every aspect of the original geometry is preserved equally well.

Definition: For two probability distributions $P=(p_a)$ and $Q=(q_a)$ on the same finite set, with $q_a>0$ wherever $p_a>0$, their Kullback–Leibler divergence is $$ KL(P\|Q)=\sum_{a:p_a>0}p_a\log\left(\frac{p_a}{q_a}\right). $$ The logarithm here is natural, so the divergence is measured in nats. A term with $p_a=0$ is defined to contribute zero.

The Distributions in the t-SNE Objective

Suppose there are $n$ cells. The high-dimensional distribution $P$ describes pairwise similarities derived from the cell data and the chosen neighborhood scale. The earlier material on the t-SNE pairwise similarity model defines how those similarities are formed; here, the important point is that the resulting joint probabilities are fixed while the embedding is optimized.

The probabilities are indexed by ordered cell pairs. For distinct cells $i$ and $j$, $p_{ij}$ is the high-dimensional joint probability assigned to that pair. Usually the joint distribution is symmetrized, so $p_{ij}=p_{ji}$, and it is normalized so that $\sum_{i\ne j}p_{ij}=1$. Self-pairs have probability zero. The perplexity choice affects $P$, but the KL objective compares whatever $P$ has been constructed with the embedding distribution.

For low-dimensional coordinates $y_1,\ldots,y_n$, standard t-SNE defines the embedding probability using a Student t kernel with one degree of freedom:

q_{ij} = \frac{(1+\|y_i-y_j\|^2)^{-1}} {\sum_{k\ne l}(1+\|y_k-y_l\|^2)^{-1}}, \qquad i\ne j, \qquad q_{ii}=0.

The denominator sums over all ordered pairs of distinct cells, so $\sum_{i\ne j}q_{ij}=1$. At any finite set of coordinates, every $q_{ij}$ for $i\ne j$ is positive. This makes the KL objective well-defined when the corresponding $p_{ij}$ is positive.

Definition: The t-SNE objective for embedding coordinates $Y=(y_1,\ldots,y_n)$ is $$ C(Y)=KL(P\|Q) =\sum_{i\ne j:p_{ij}>0}p_{ij}\log\left(\frac{p_{ij}}{q_{ij}}\right). $$ Here $P$ is fixed by the high-dimensional data and modeling choices, while $Q$ changes as the coordinates change.

Why the Direction of KL Matters

For a particular pair, the contribution is $p_{ij}\log(p_{ij}/q_{ij})$. If $p_{ij}$ is appreciable and $q_{ij}$ is made very small, that contribution grows without bound as $q_{ij}$ approaches zero. By contrast, when $p_{ij}$ is tiny, a mismatch on that pair is weighted by a tiny $p_{ij}$. Individual contributions can be negative, but the sum over all pairs is nonnegative.

The comparison is asymmetric: in general, $KL(P\|Q)\ne KL(Q\|P)$. In t-SNE the high-dimensional distribution is first in the divergence. Thus, a high-probability pair in $P$ needs a reasonably high probability in $Q$ to avoid a large cost. This makes it costly to separate cells that are close under the high-dimensional similarity model. It does not impose an equally strong cost for every low-$P$ pair that happens to receive a high $q_{ij}$; such a mismatch affects the total through normalization and the other terms, but is weighted differently.

A useful algebraic view separates the terms that depend on the embedding:

C(Y) = \underbrace{\sum_{i\ne j}p_{ij}\log p_{ij}}_{\text{constant in }Y} - \sum_{i\ne j}p_{ij}\log q_{ij}.

The first sum is constant because $P$ is fixed. Therefore, minimizing KL is equivalent to minimizing the cross-entropy $-\sum p_{ij}\log q_{ij}$. Each high-probability pair receives a large weight in this criterion. A low $q_{ij}$ for such a pair incurs a large penalty because $-\log q_{ij}$ is large.

Worked Example: A Close-Pair Probability Is Lost

Consider a hypothetical probability-table illustration with three pair categories. Their high-dimensional probabilities are $P=(0.80,0.15,0.05)$, while the embedding assigns $Q=(0.20,0.40,0.40)$. Both distributions sum to 1. The first category represents a pair type that is strongly favored in the input-space similarities.

Calculate the divergence. Using the KL formula,

\begin{aligned} KL(P\|Q) &=0.80\log(0.80/0.20) +0.15\log(0.15/0.40) +0.05\log(0.05/0.40)\\ &=0.80\log(4)+0.15\log(0.375)+0.05\log(0.125)\\ &\approx 1.1090-0.1471-0.1040\\ &\approx 0.8579\text{ nats}. \end{aligned}

The first term alone is about $1.109$ nats: the embedding gave only $0.20$ probability to a category assigned $0.80$ in $P$. The other terms are negative, which is permitted for individual terms; their inclusion does not contradict the nonnegativity of the total divergence. This probability table illustrates the weighting and asymmetry of the objective, rather than specifying coordinates for a particular cell dataset.

Why the Total Divergence Cannot Be Negative

The nonnegativity of KL explains why the objective is a discrepancy measure even though some terms can be negative. For every index with $p_a>0$, apply $-\log x\ge 1-x$ with $x=q_a/p_a$. If $P$ and $Q$ are normalized and $Q$ is positive on the support of $P$, then

\begin{aligned} KL(P\|Q) &=\sum_{a:p_a>0}p_a\left[-\log(q_a/p_a)\right]\\ &\ge \sum_{a:p_a>0}p_a(1-q_a/p_a)\\ &=\sum_{a:p_a>0}p_a-\sum_{a:p_a>0}q_a\\ &=1-\sum_{a:p_a>0}q_a \ge 0. \end{aligned}

The last inequality holds because the $q_a$ values on the support of $P$ sum to at most 1. Equality requires $P=Q$; with positive probabilities throughout the same pair set, this means every corresponding probability is equal. Thus the minimum possible objective is zero, attained when the two pair distributions match. In practice, t-SNE’s coordinate constraints and nonconvex optimization mean the achieved value need not be zero.

Worked Example: A Small Divergence When the Distributions Are Similar

Suppose two hypothetical pair categories have $P=(0.50,0.30,0.20)$ and $Q=(0.40,0.40,0.20)$. These are valid distributions because each sums to 1.

Substitute into the definition.

\begin{aligned} KL(P\|Q) &=0.50\log(0.50/0.40) +0.30\log(0.30/0.40) +0.20\log(0.20/0.20)\\ &=0.50\log(1.25)+0.30\log(0.75)+0.20\log(1)\\ &\approx 0.11157-0.08630+0\\ &\approx 0.02527\text{ nats}. \end{aligned}

The distributions differ, so the divergence is positive, but the mismatch is modest compared with the preceding example. The third category contributes zero because its probabilities agree. The negative contribution from the second category offsets part of the positive contribution from the first; only the full sum is the divergence.

How the Objective Moves Coordinates

The gradient makes the attraction of high-$P$ pairs explicit. Let $w_{ij}=(1+\|y_i-y_j\|^2)^{-1}$, so $q_{ij}=w_{ij}/Z$, where $Z=\sum_{k\ne l}w_{kl}$. Since $\sum p_{ij}=1$, the objective can be written as a constant minus $\sum p_{ij}\log w_{ij}$, plus $\log Z$. Differentiating these terms with respect to $y_i$, using the symmetry of $p_{ij}$ and $q_{ij}$, gives

\nabla_{y_i}C = 4\sum_{j\ne i} (p_{ij}-q_{ij}) \frac{y_i-y_j}{1+\|y_i-y_j\|^2}.

The factor of 4 reflects the use of symmetric probabilities indexed over ordered pairs. When $p_{ij}>q_{ij}$, the pair’s contribution to the gradient points along $y_i-y_j$; gradient descent moves $y_i$ in the opposite direction, toward $y_j$. When $p_{ij}<q_{ij}$, the pair contributes a repulsive component. These are pairwise components of the gradient: the net movement of a cell depends on all its pairs, not just one.

Worked Example: The Direction of One Pair’s Gradient

Consider a hypothetical one-dimensional embedding pair with $y_i-y_j=2$, $p_{ij}=0.30$, and $q_{ij}=0.05$. The contribution of this pair to the gradient for $y_i$, using the displayed formula, is

4(0.30-0.05)\frac{2}{1+2^2} = 4(0.25)\frac{2}{5} = 0.400.

This positive gradient component points in the direction of increasing $y_i-y_j$. A gradient-descent update subtracts a positive multiple of the gradient, so this pair’s component moves $y_i$ toward $y_j$, reducing their separation. The calculation isolates one pair’s contribution; other cells also contribute to the full gradient.

Assumptions, Diagnostics, and Alternatives

The interpretation above depends on the distributions being constructed and normalized as stated. $P$ must represent the high-dimensional pair similarities chosen for the analysis, and $Q$ must use the same pair indexing and total probability mass. The coordinates must be finite for the standard t kernel to give positive $q_{ij}$. If probabilities are accidentally normalized over unordered pairs in one distribution and ordered pairs in the other, the quantities are not comparable and the calculated objective is not the stated t-SNE KL divergence.

Several checks help identify problems in reasoning or implementation:

Check normalization. Confirm that the off-diagonal entries of both $P$ and $Q$ sum to 1. A wrong denominator changes every probability and hence the objective.
Check the direction. The standard objective is $KL(P\|Q)$, not $KL(Q\|P)$. Reversing the arguments changes which discrepancies are weighted strongly.
Check the support. If $p_{ij}>0$ but an implementation sets $q_{ij}=0$, the corresponding KL contribution is infinite. With the standard t kernel and finite coordinates, $q_{ij}>0$.
Do not interpret a low objective as proof of global geometric fidelity. The objective concerns pair probabilities, not exact preservation of all original distances.

Other criteria answer different questions. A squared-error objective on pairwise distances penalizes numerical distance differences directly; it does not use the KL probability weighting that emphasizes high-$P$ pairs. Reversing the KL arguments changes the weighting and the consequences of assigning probability to pairs that were unlikely under $P$. Neither alternative is simply a notational variation of the t-SNE criterion.

The KL objective also has limits. A good match to local pair probabilities does not guarantee that distances between separated embedding groups faithfully represent high-dimensional distances. The normalization couples all pairs, and the coordinate objective is nonconvex, so different initializations can lead to different local solutions. A plotted separation should therefore be interpreted as a feature of this probability-matching embedding, not as a direct estimate of global cell-to-cell distance.

Common pitfall: “A negative term in the KL sum means the objective is invalid.” This is incorrect because individual terms $p_{ij}\log(p_{ij}/q_{ij})$ can be negative. The normalized sum is nonnegative. A second common error is to say that t-SNE penalizes every mismatch equally. It does not: the $P$-weighted objective especially penalizes assigning very small embedding probability to pairs that have high probability in the input-space distribution.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

If $p_{ij}=0.25$ and $q_{ij}=0.025$, what is that pair’s KL contribution? What does its sign and size indicate?
Why can one term in a KL sum be negative even though the total divergence is nonnegative?
What direction does the pairwise gradient contribution encourage when $p_{ij}>q_{ij}$?
Why does reversing the arguments to form $KL(Q\|P)$ change the t-SNE objective’s interpretation?

Solutions. (1) The contribution is $0.25\log(0.25/0.025)=0.25\log(10)\approx 0.5756$ nats, a positive and substantial cost for assigning much less embedding probability than input probability. (2) A term is negative when $q_{ij}>p_{ij}$, but other terms offset it; nonnegativity applies to the normalized sum, not each summand. (3) Since the gradient component points along $y_i-y_j$, gradient descent moves against it, drawing the pair closer together. (4) Reversing the arguments changes the probability weights: the standard direction weights each log discrepancy by $p_{ij}$, whereas the reversed direction weights it by $q_{ij}$, so the two objectives penalize mismatches differently.