On the continuum limit of t-SNE for data visualization
Authors: Jeff Calder, Zhonggan Huang, Ryan Murray, Adam Pickarski
Organizations: School of Mathematics, University of Minnesota · Department of Mathematics, University of Utah · Department of Mathematics, North Carolina State University
This work is concerned with the continuum limit of a graph-based data visualization technique called the t-Distributed Stochastic Neighbor Embedding (t-SNE), which is widely used for visualizing data in a variety of applications, but is still poorly understood from a theoretical standpoint. The t-SNE algorithm produces visualizations by minimizing the Kullback-Leibler divergence between similarity matrices representing the high dimensional data and its low dimensional representation. We prove that as the number of data points n→∞, after a natural rescaling and in applicable parameter regimes, the Kullback-Leibler divergence is consistent as the number of data points n→∞ and the similarity graph remains sparse with a continuum variational problem that involves a non-convex gradient regularization term and a penalty on the magnitude of the probability density function in the visualization space. These two terms represent the continuum limits of the attraction and repulsion forces in the t-SNE algorithm. Due to the lack of convexity in the continuum variational problem, the question of well-posedeness is only partially resolved. We show that when both dimensions are 1, the problem admits a unique smooth minimizer, along with an infinite number of discontinuous minimizers (interpreted in a relaxed sense). This aligns well with the empirically observed ability of t-SNE to separate data in seemingly arbitrary ways in the visualization. The energy is also very closely related to the famously ill-posed Perona-Malik equation, which is used for denoising and simplifying images. We present numerical results validating the continuum limit, provide some preliminary results about the delicate nature of the limiting energetic problem in higher dimensions, and highlight several problems for future work.
Figures & tables
Figure 2.1: Evolution of the t-SNE embedding over the iterations of gradient descent, taken from [ 12 ] . The result after k=250 iterations in (d) is the end of the early exaggeration phase. Results do not change significantly after 500 iterations of gradient descent.
Figure 2.2: Embeddings obtained by using tSNE on points distributed on a sphere, taken from [ 39 ] , for different choices of n . The scaling of the embedding plots grows in n . The way in which the sphere is cut up to create microstructure is partially explained later in our paper, in Corollary 4.2 .
Figure 3.1: The function Θ(v) for η(z)=43(1−z2)+ .
Figure 3.2: Random Initialization. Top row compares Tn and T while the bottom row compares Tn′ and T′ . We increase the separation between the Gaussian clusters from left to right.
Figure 3.3: Identity Initialization. Top row compares Tn and T while the bottom row compares Tn′ and T′ . We increase the separation between the Gaussian clusters from left to right.
Figure 3.4: Continuum Limit Initialization. Top row compares Tn and T while the bottom row compares Tn′ and T′ . We increase the separation between the Gaussian clusters from left to right.
Figure 3.5: Comparison of t-SNE loss during optimization for random initialization, identity initialization, and initializing with the continuum limit.
This paper considers the energy landscape of the t-SNE algorithm. While this algorithm has enjoyed broad adoption, the non-convexity of the associated energy has made it difficult to rigorously understand what the algorithm captures in many settings. In particular, a number of well-known numerical examples, several of which are reproduced in this article, suggest a complicated energy landscape with many local minimizers that do not respect the topology or clustering structure of the underlying data. This work seeks to provide first steps towards a rigorous explanation of these phenomena. Specifically, for a general family of energies, which include both the original t-SNE algorithm and recently identified large data limits, and for densities in feature space which obey a continuous symmetry, we construct infinite families of distinct critical points. These critical points are based upon identifying pairs of discrete symmetries, one in the original feature space and the other in the target embedding space, which are preserved under gradient dynamics. These critical configurations exhibit many characteristics, such as topology breaking and spurious clustering, which are often observed empirically. Finally, numerical and analytical examples are given throughout as a means of illustrating the approach.
Nakul Haridas, Ryan Murray
Department of Mathematics North Carolina State University Raleigh, North Carolina, USA
t-SNE has gained popularity as a dimension reduction technique, especially for visualizing data. It is well-known that all dimension reduction techniques may lose important features of the data. We provide a mathematical framework for understanding this loss for t-SNE by establishing a number of results in different scenarios showing how important features of data are lost by using t-SNE.
We extend the results by Auffinger and Fletcher in 2023 on the large-sample limit of t-SNE to a broader class of input and output kernels. We prove that under natural assumptions on the input distribution and the decay of the output kernel, if perplexity scales linearly with data size, the empirical measures and values of minimizers converge to an equilibrium distribution. We conclude with numerical examples comparing different kernels.
Yi Gu, Antonio Auffinger
Department of Mathematics, Northwestern University