Heavy-Tailed Kernels Reveal a Finer Cluster Structure in t-SNE Visualisations

T-distributed stochastic neighbour embedding (t-SNE) [12] and related methods [13, 15] are used for data visualisation in many scientific fields dealing with thousands or even millions of high-dimensional samples. They range from single-cell cytometry [1] and transcriptomics [16, 19], where samples are cells and features are proteins or genes, to population genetics [4], where samples are people and features are single-nucleotide polymorphisms, to humanities [14], where samples are books and features are words.

T-SNE was developed from an earlier method called SNE [5]. The central idea of SNE was to describe pairwise relationships between high-dimensional points in terms of normalised affinities: close neighbours have high affinity whereas distant samples have near-zero affinity. SNE then positions the points in two dimensions such that the Kullback-Leibler divergence between the high- and low-dimensional affinities is minimised. This worked to some degree but suffered from what was later called the ‘crowding problem’: distinct high-dimensional clusters tended to overlap in the embedding. The idea of t-SNE was to adjust the kernel transforming pairwise low-dimensional distances into affinities: the Gaussian kernel was replaced by the heavy-tailed Cauchy kernel (t-distribution with one degree of freedom \(\nu \)), ameliorating the crowding problem.

The choice of the specific heavy-tailed kernel was mostly motivated by mathematical and computational simplicity: a t-distribution with \(\nu =1\) has a density proportional to \(1/(1+x^2)\) which is mathematically compact and fast to compute. However, a t-distribution with any finite \(\nu \) has heavier tails than the Gaussian distribution (which corresponds to \(\nu \rightarrow \infty \)). It is therefore reasonable to explore the whole spectrum of the values of \(\nu \) from \(\infty \) to 0. Given that t-SNE (\(\nu =1\)) outperforms SNE (\(\nu =\infty \)), it might be that for some data sets \(\nu <1\) would offer additional insights into the structure of the data.

While this seems like a straightforward extension and has already been discussed in the literature [10, 18], no efficient implementation of this idea has been available until now. T-SNE is usually optimised via adaptive gradient descent. While it is easy to write down the gradient for an arbitrary value of \(\nu \), the exact t-SNE from the original paper requires \(\mathcal O(n^2)\) time and memory, and cannot be run for sample sizes much larger than \(n\approx 10\,000\). Efficient approximations have been developed allowing to run approximate t-SNE for much larger sample sizes [9, 11], but until now have only been implemented for \(\nu =1\). As a result, the effect of \(\nu \ne 1\) on large real-life datasets has remained unknown.

Here we show that the recent FIt-SNE approximation [9] can be modified to use an arbitrary value of \(\nu \) and demonstrate that \(\nu <1\) can reveal ‘hidden’ structure, invisible with standard t-SNE.

Yang et al. [18] introduced symmetric SNE with the kernel family calling it ‘heavy-tailed symmetric SNE’ (HSSNE). This is exactly the same kernel family as (\(\star \star \)), but with \(\alpha \) replaced by \(1/\alpha \). However, Yang et al. did not show any examples of heavier-tailed kernels revealing additional structure compared to \(\alpha =1\) and did not provide an implementation suitable for large sample sizes (i.e. it is not possible to use their implementation for \(n\gtrsim 10\,000\)). Interestingly, Yang et al. argued that gradient descent is not suitable for HSSNE and suggested an alternative optimisation algorithm; here we demonstrated that the standard t-SNE optimisation works reasonably well in a wide range of \(\alpha \) values (but see Discussion).

Van der Maaten [10] discussed the choice of the degree of freedom in the t-distribution kernel in the context of parametric t-SNE. He argued that \(\nu >1\) might be warranted when embedding the data in more than two dimensions. He also implemented a version of parametric t-SNE that optimises over \(\nu \). However, similar to [10, 18] did not contain any examples of \(\nu <1\) being actually useful in practice.

UMAP [13] is a promising recent algorithm closely related to an earlier largeVis [15]; both are similar to t-SNE but modify the repulsive forces to make them amenable for a sampling-based stochastic optimisation. UMAP uses the following family of similarity kernels: which reduces to Cauchy when \(a=b=1\) and is more heavy-tailed when \(0<b<1\). UMAP default is \(a\approx 1.6\) and \(b\approx 0.9\) with both parameters adjusted via the min_dist input parameter (default value 0.1). Decreasing min_dist all the way to zero corresponds to decreasing b to 0.79. In our experiments, we observed that modifying min_dist (or b directly) led to an effect qualitatively similar to modifying \(\alpha \) in t-SNE. For some data sets this required manually decreasing b below 0.79. In case of MNIST, \(b=0.3\), but not \(b=0.79\), revealed sub-digit structure (Figure S1)—an effect that has not been described before (cf. [13] where McInnes et al. state that min_dist is “an essentially aesthetic parameter”). In other words, the same conclusion seems to apply to UMAP: heavy-tailed kernels reveal a finer cluster structure. A more in-depth study of the relationships between the two algorithms is beyond the scope of this paper.

We showed that using \(\alpha <1\) in t-SNE can yield insightful visualisations that are qualitatively different compared to the standard choice of \(\alpha =1\). Crucially, the choice of \(\alpha =1\) was made in [12] for the reasons of mathematical convenience, and we are not aware of any a priori argument in favour of \(\alpha =1\). As \(\alpha \ne 1\) still yields a t-distribution kernel (scaled t-distribution to be precise), we prefer not to use a separate acronym (HSSNE [18]). If needed, one can refer to t-SNE with \(\alpha <1\) as ‘heavy-tailed’ t-SNE.

We found that lowering \(\alpha \) below 1 makes progressively finer structure apparent in the visualisation and brings out smaller clusters, which—at least in the data sets studied here—are often meaningful. In a way, \(\alpha <1\) can be thought of as a ‘magnifying glass’ for the standard t-SNE representation. We do not think that there is one ideal value of \(\alpha \) suitable for all data sets and all situations; instead we consider it a useful adjustable parameter of t-SNE, complementary to the perplexity. We observed a non-trivial interaction between \(\alpha \) and perplexity: Small vs. large perplexity makes the affinity matrix \(p_{ij}\) represent the local vs. global structure of the data [7]. Small vs. large \(\alpha \) makes the embedding represent the finer vs. coarser structure of the affinity matrix. In practice, it can make sense to treat it as a two-dimensional parameter space to explore. However, for large data sets (\(n\gtrsim 10^6\)), it is computationally unfeasible to substantially increase the perplexity from its standard range of 30–100 (as it would prohibitively increase the runtime), and so \(\alpha \) becomes the only available parameter to adjust.

One important caveat is to be kept in mind. It is well-known that t-SNE, especially with low perplexity, can find ‘clusters’ in pure noise, picking up random fluctuations in the density [17]. This can happen with \(\alpha =1\) but gets exacerbated with lower values of \(\alpha \). A related point concerns clustered real-life data where separate clusters (local density peaks) can sometimes be connected by an area of lower but non-zero density: for example, [16] argued that many pairs of their 133 clusters have intermediate cells. Our experiments demonstrate that lowering \(\alpha \) can make such clusters more and more isolated in the embedding, creating a potentially misleading appearance of perfect separation (see e.g. Figure 1). In other words, there is a trade-off between bringing out finer cluster structure and preserving continuities between clusters.

Choosing a value of \(\alpha \) that yields the most faithful representation of a given data set is challenging because it is difficult to quantify ‘faithfulness’ of any given embedding [8]. For example, for MNIST, KL divergence is minimised at \(\alpha \approx 1.5\) (Fig. 7), but it may not be the ideal metric to quantify the embedding quality [6]. Indeed, we found that k-nearest neighbour (KNN) preservation [8] peaked elsewhere: the peak for \(k=10\) was at \(\alpha \approx 1.0\), for \(k=50\) at \(\alpha \approx 0.9\), and for \(k=100\) at \(\alpha \approx 0.8\) (Fig. 7). We stress that we do not think that KNN preservation is the most appropriate metric here; our point is that different metrics can easily disagree with each other. In general, there may not be a single ‘best’ embedding of high-dimensional data in a two-dimensional space. Rather, by varying \(\alpha \), one can obtain different complementary ‘views’ of the data.

Very low values of \(\alpha \) correspond to kernels with very wide and very flat tails, leading to vanishing gradients and difficult convergence. We found that \(\alpha =0.5\) was about the smallest value that could be safely used (Figure S2). In fact, it may take more iterations to reach convergence for \(0.5<\alpha <1\) compared to \(\alpha =1\). As an example, running t-SNE on MNIST with \(\alpha =0.5\) for ten times longer than we did for Fig. 4C, led to the embedding expanding much further (which leads to a slow-down of FIt-SNE interpolation) and, as a result, resolving additional sub-clusters (Figure S3). On a related note, when using only one single MNIST digit as an input for t-SNE with \(\alpha =0.5\), the embedding also fragments into many more clusters (Figure S4), which we hypothesise is due to the points rapidly expanding to occupy a much larger area compared to what happens in the full MNIST embedding (Figure S4). This can be counterbalanced by increasing the strength of the attractive forces (Figure S4). Overall, the effect of the embedding scale on the cluster resolution remains an open research question.

In conclusion, we have shown that adjusting the heaviness of the kernel tails in t-SNE can be a valuable tool for data exploration and visualisation. As a practical recommendation, we suggest to embed any given data set using various values of \(\alpha \), each inducing a different level of clustering, and hence providing insight that cannot be obtained from the standard \(\alpha =1\) choice alone.⁸

The loss function, up to a constant term \(\sum p_{ij}\log p_{ij}\), can be rewritten as follows: where we took into account that \(\sum p_{ij}=1\). The first term in Eq. (1) contributes attractive forces to the gradient while the second term yields repulsive forces. The gradient is The first expression is more convenient for numeric optimisation while the second one can be more convenient for mathematical analysis.

For the kernel the gradient of \(w_{ij} = k(\Vert \mathbf{y}_i - \mathbf{y}_j\Vert )\) is Plugging Eq. 4 into Eq. 3, we obtain the expression for the gradient [18]⁹ For numeric optimisation it is convenient to split this expression into the attractive and the repulsive terms. Plugging Eq. 4 into Eq. 2, we obtain where It is noteworthy that the expression for \(\mathbf{F}_\mathrm {attr}\) has \(w_{ij}\) raised to the \(1/\alpha \) power, which cancels out the fractional power in k(d). This makes the runtime of \(\mathbf{F}_\mathrm {attr}\) computation unaffected by the value of \(\alpha \). In FIt-SNE, the sum over j in \(\mathbf{F}_\mathrm {attr}\) is approximated by the sum over \(3\Pi \) approximate nearest neighbours of point i obtained using Annoy [3], where \(\Pi \) is the provided perplexity value. The \(3\Pi \) heuristic comes from [11]. The remaining \(p_{ij}\) values are set to zero.

The \(\mathbf{F}_\mathrm {rep}\) can be approximated using the interpolation scheme from [9]. It allows fast approximate computation of the sums of the form and where \(K(\cdot )\) is any smooth kernel, by using polynomial interpolation of K on a fine grid.¹⁰ All kernels appearing in \(\mathbf{F}_\mathrm {rep}\) are smooth.