Are there any versions of t-SNE for streaming data?

Question

My understanding of t-SNE and the Barnes-Hut approximation is that all data points are required so that all force interactions can be calculated at the same time and each point can be adjusted in the 2d (or lower dimensional) map.

Are there any versions of t-sne that can efficiently deal with streaming data? So if my observations are arriving one at a time, it will find the best location on the 2d map to place the new observation, or continuously update all points on the 2d map to account for ht new observation.

Would this even make sense or does it go against the setup of t-sne.

Answer 1

I had exactly the same question and posted it on a YouTube video of a CS231n lecture given by Andrej Karpathy a few weeks ago. Here is the question I posted followed by Andrej' response:

https://www.youtube.com/watch?v=ta5fdaqDT3M&lc=z12ji3arguzwgxdm422gxnf54xaluzhcx

Q:

Does t-SNE need an entire batch of images (or more generally, data) to create the low-dimensional feature space? With PCA you can create a low-dimensional feature space on a batch of data and then project new data points onto that same space without having to "retrain". Is that true for t-SNE?

I ask because I noticed that scikit-learn has t-SNE as part of its manifold class, but that module does not have a transform() method as PCA does. So, at least, in sklearn, it would seem this is not possible.

My question boils down to this. How would you apply t-SNE in a streaming or online situation where you want to continually update the visualization with new images? Presumably, one would not want to apply the algorithm on the entire batch for each new image.

A:

+Evan Zamir yes this is possible with t-SNE, but maybe not supported out of the box with regular t-SNE implementations. Normally each point's location is a parameter in the optimization, but you can just as well create a mapping from high-D -> low-D (e.g. neural net) and backprop through the locations. Then you end up with the embedding function and can project new points. So nothing preventing this in principle, but some implementations might not support it as it's a less frequent use case.

Answer 2

When dealing with streaming data, you might not want/need to embed all the points in history in a single t-SNE map. As an alternative, you can perform an online embedding by following these simple steps:

1. choose a time-window of duration T, long enough so that each pattern of interest appears at least a couple of times in the window duration.

2. scroll the window as the data streams in, with a time-step dt much smaller than T. For each position of the window, compute a t-SNE embedding of the data points in the time window.

3. seed each embedding with the outcome of the previous one. In t-SNE, one needs to choose the initial coordinates of the data points in the low-dimensional space. In our case, because we choose dt much smaller than T, two successive embeddings share most of their data points. For all the shared data points, match their initial coordinates in the present embedding to their final coordinates in the previous embedding. This step will ensure that similar patterns have a consistent representation across successive embeddings. (in the sklearn implementation in python, the seed parameter is "init". By default, the sklearn implementation sets the initial position of the points randomly)

Note 1: It is important that the patterns of interest appear at least once in any given time window, so that the memory of the representation does not get lost as the window slides through the dataset. Indeed, t-SNE typically does not converge to a unique solution but only to a local minimum, so if the memory is lost, a similar pattern might be represented in very different ways in two instanciations of an embedding.

Note 2: This method is particularly relevant when dealing with non-stationary time series, where one wishes to track patterns that evolve slowly through time. Indeed, each embedding is here taylored specifically to the small time window on which it is computed, ensuring that it captures temporally local structure in the best way (contrarily to a full embedding of the whole non-stationary dataset).

Note 3: In this method the successive embeddings cannot be parallelized, because one needs the outcome of the previous embedding in order to seed the next one. However, because the seed (i.e. initial coordinates of the points) is well chosen for most points (all shared points between succesive embeddings), an embedding typically converges very fast, in a few iterations only.

For an example of application of this method to non-stationary time series, see this article (ICLR 2016, Learning stable representations in a changing world with on-line t-SNE: proof of concept in the songbird), where it was successfully applied to track the emergence of syllables across development in the songbird.

Answer 3

There is a recently published variant, called A-tSNE, which supports dynamically adding new data and refining clusters either based on interest areas or by user input. The paper linked below has some pretty nice examples of this:

Citation: arXiv:1512.01655

Approximated and User Steerable tSNE for Progressive Visual Analytics Nicola Pezzotti, Boudewijn P.F. Lelieveldt, Laurens van der Maaten, Thomas Höllt, Elmar Eisemann, Anna Vilanova

Summary:

Progressive Visual Analytics aims at improving the interactivity in existing analytics techniques by means of visualization as well as interaction with intermediate results. One key method for data analysis is dimensionality reduction, for example, to produce 2D embeddings that can be visualized and analyzed efficiently. t-Distributed Stochastic Neighbor Embedding (tSNE) is a well-suited technique for the visualization of several high-dimensional data. tSNE can create meaningful intermediate results but suffers from a slow initialization that constrains its application in Progressive Visual Analytics. We introduce a controllable tSNE approximation (A-tSNE), which trades off speed and accuracy, to enable interactive data exploration. We offer real-time visualization techniques, including a density-based solution and a Magic Lens to inspect the degree of approximation. With this feedback, the user can decide on local refinements and steer the approximation level during the analysis. We demonstrate our technique with several datasets, in a real-world research scenario and for the real-time analysis of high-dimensional streams to illustrate its effectiveness for interactive data analysis.

Answer 4

The Barnes-Hut approximation makes t-SNE highly scalable (at least, you can use it with 100 000 lines, I tried it). You can call it from R : Rtsne

The complexity of the implemented algorithm is $O(n\log(n))$ whereas the naive implementation had a complexity of $O(n^2)$. The details of the underlying approximation can be found here Accelerating t-SNE using Tree-Based Algorithms.

Answer 5

Barnes-Hut approximation is now the default method in scikit-learn as of version 0.17.0:

By default the gradient calculation algorithm uses Barnes-Hut approximation running in O(NlogN) time. method=’exact’ will run on the slower, but exact, algorithm in O(N^2) time. The exact algorithm should be used when nearest-neighbor errors need to be better than 3%. However, the exact method cannot scale to millions of examples. New in version 0.17: Approximate optimization method via the Barnes-Hut.