Scientist Stories: Dmitry Kobak, Embeddings for Scientific Visualization

Welcome, data scientists! Today it's my great pleasure to be one of the hosts of the LS Live joint event with the Data Science Seminar, and now I will hand over to Oliver Stegele for the introduction. Good morning, everyone! Thank you so much for joining us. So I am— we have now really a fantastic event today where we have also our first external speaker for the LS Join Ellis Live Data Science Seminar. But before going there, I would just like to give you a very brief introduction to what Ellis Live is and why we have founded it and how that might also be something to watch out for in the future for your interests. So just one few words about Ellis. Ellis has been an initiative that has been funded by, founded by really active researchers in Europe who carry out data science research on all level. It's a network, a pan-European network that currently constructs and constitutes of the European Laboratory for Learning Intelligent Systems. And ELS has a number of initiatives, but the key idea is essentially to follow suit with international activities that have been now seen across the globe. AI is obviously pervasive nationally and internationally. There are activities across Europe, and one of these activities across Europe is really ELS. That wants to achieve awareness and also foster talent and excellence in Europe in AI research on all levels and in all application domains. So just, you know, some of the goals of LS. I want to be brief here and don't take up too much of the time of our speaker, but I think the key idea is really to create a community for bringing together AI expertise and excellence and have more of the events of this type. And keep us together and connected to foster impact in society. So there's two activities of ELLIS that I would like to mention. On one hand, there are ELLIS programs, which I will be brief about here, but there's also ELLIS Health, which has a strong Heidelberg component. You will hear more about this and might be very relevant. And, but you can also see from this list that really ELLIS is active across all areas of science and driving those. These, in addition to these programs that are sort of dispersed geographically and try to connect people across Europe. There's also LS Units. This is a sort of a map of the 30 units or so that are existing right now in Europe. And one of them is LS Heidelberg that is hosting today's event, co-hosting with the Data Science Seminar. And I just want to show you in 2 slides what is maybe different about LS Life Heidelberg and what we're trying to achieve and who constitutes LS Life and who we are. So, Alice Life Heidelberg is a joint venture between EMBL, DKFZ, and University of Heidelberg. And I think what's special about us is that we're really dedicated to solving and addressing challenges in the life sciences. That's all the way from basic biomedicine to healthcare by bringing together the expertise across these very closely connected centers. And what we hope to achieve is creating a bridge between biomedical data and AI research, and a bridge that hopefully can go from left to right and right to left that leverages the big datasets that are coming together, physiological response data types, big bioimaging data types, and also genome data that are now growing on scale where we can sequence people's genomes and other elements. And we would like to leverage those in the best possible way. And to facilitate these developments, we have established a unit. Here you can see the current set of PIs, and I'm together with Anna Kreschuk and Carsten Rother co-directing the unit. And it's a very vibrant community. We are also looking for new people to join us, so primarily also junior PIs are very welcome to add into this. So we're hoping this family will grow, and that's the nucleus And there will be also more events that are really open to all fellows from pre-docs to post-docs. So please join the events. And this is really one of the first events. And there will be many more to follow that hopefully will be of interest for you and will be stimulating to create new connections across institutions and across disciplines as well. Yeah, so this is just the last slide I have. I mentioned there's a strong research component to Connecting, also basically activities, foundational AI, where Heidelberg University People like Fred, who's hosting today's speaker, will have a very strong foundational interest and expertise. The link to oncology, which is primarily hosted at DKFZ, and then EMBL with a very broad and general mission to advance AI methodology across all areas of life sciences, and that we are trying to do. So thanks so much for listening to this very, very brief intro talk, and I will now hand over to Fred, who will introduce our speaker, who is actually our main guest. And apologies for taking away some of the time, but I thought it would be useful for you to know a bit what, what Alice Live is about. Thank you.

Thanks, Ollie, and thanks all for joining. We're very happy to have Dmitry Kovac with us today. Dmitry earned— well, he studied computer science and physics in Petersburg, earned his PhD in neuroscience from Imperial College, went on for postdoctoral work in Champagny, and is currently working in Freiburg. And well, the reason we were happy to invite Dimitri today is because he has been making great strides in our understanding of dimension reduction and visualization methods. And almost by definition with these methods, what works well and what doesn't, you know, beauty lies in the eye of the beholder. And the true data is 20,000-dimensional, and then you have this picture and that picture of the 20,000-dimensional data. And so it becomes really hard to argue which method is more faithful or which one is more true in a sense. And this is, with so many competing proposals out there, it's really important to try and develop a common theoretical framework and understanding what are their differences. And this is exactly where the work of Dimitri and his colleagues has been making great progress. And Sebastian, as always, corrects me when I'm making mistakes. Dimitri is in Tübingen, No longer in Freiburg, thanks to Bastian. All right, there is another reason to be interested in Dimitri's work. If ever you should decide to change your career path and go into the doctoring of election results and such, you should read Dimitri's paper and see how not to do it if you don't want to be caught out too easily. Really interesting work that Dimitri has been doing there. Maybe in a sideline, he will say a few words about that. Dimitri, we're happy to have you here today. Thanks for coming. Glad to listen to your talk now.

Thanks a lot, Fred. Thanks a lot for the great introduction. Let me share my screen and make it full screen. Now we can start. So you really took away part of the things that I wanted to say in the first slide. So that's great. I can just jump right in and say I'm going to talk about pictures like that most of the time in the talk. So that's a neighbor embedding. What you see here is 20 million points. I'm not going to tell you right now what the points are. I'll come to that later. If you're familiar with these things, you can try to guess what you're looking at, but it's hard. So that's 20 million objects depicted here, and I will argue that in many areas of science, it's actually useful to have visualizations like that, but it's hard to do them well. And that's what we're going to discuss today. So I will start with a gentle introduction into neighbor embeddings. I see a lot of people are listening here, so I'll try to explain what this is, why we're using it, where would one want to apply that, how that works. And then we'll talk about a couple of things. So one is optimization issues in t-SNE specifically, in one of the methods, what one should be aware when actually implementing this and doing the optimization. But then most of the talk So the main focus is going to be on that part, which is the trade-offs that one has when one changes some of the important parameters there. And we'll talk about two examples, primarily the trade-off between the coarse and fine cluster structure, and also another trade-off between more continuous and more discrete representations. So I will explain what I mean by that later on. And then along the way, and in the end, we're going to talk about the relationship between several existing algorithms and how they fall on this with respect to these traits on this spectrum. Okay, so let's start. So that's what Fred essentially said, the task of dimensionality reduction for data visualization. So I'm going to be talking about low-dimensional, like two-dimensional representation of the data, is to move from this high-dimensional dataset represented by a matrix here, or think about objects living in a high-dimensional space, maybe having tens of thousands of dimensions, and we want to have a two-dimensional representation of that, like I had in my first slide. So we want this in some sense to represent the data, but if you think about that, it's immediately clear that it's actually very hard to quantify what we want, what properties of the data we want to preserve when doing that. It's clearly not possible to preserve everything because we're losing information by reducing the dimensionality. So what is it that we want to preserve? If there are clusters in the data, we probably want to see clusters in 2D. If there is some continuous structure up there, we probably want to see a continuous structure here. In particularly complicated situations, you— it may not be— what, like if you're embedding the surface of the Earth, you have to make some compromises when you make a map. And now imagine that you're making a map of 10,000-dimensional space. So that's the, that's the challenge here. So I will just scroll through several slides that show examples of that. In several applications. And that's the fields that I know of at least that use this kind of low-dimensional visualizations a lot. So the example I know the best is single-cell transcriptomics, single-cell RNA sequencing. So here samples are cells and features are genes. And for each cell and gene, we get the measurement of how strongly this gene is working, is being expressed in that cell. Experimental methods allow to do this for, for example, in this case, half a million cells in the mouse nervous system. And then here you can see all different kinds of neural and non-neural cells arranged here. So this is a very vibrant field, and people love to use this kind of methods to actually take a look at the data. Another example: population genomics. So here samples are people, Features are single nucleotide polymorphisms, so actually positions in your DNA, and this is a large dataset from the UK. So each dot is a person. They are colored here by the ethnic background. WB is White British, for example, and this is maybe Indian descent and so on. And one can also see a lot of structure in the genetic structure of this population. Another different example is behavioral physiology. So here, samples are syllable renditions when a bird, a zebra finch I believe, is learning to sing a song. And the features are spectral groupings. So I'm not going to explain any of that in big detail, but again, you see hundreds of thousands of these samples and a lot of structure emerging when one does this representation. And here's a final example that I will give. That's Actually, non-biological example here. Samples are books and features are words. This is so-called bag-of-words representation of a book. So for each book and each word, the number in the data matrix tells how often this word occurs in this book. And there's 15 million books in this library, and this is a wonderful representation that shows how these books cluster by language. But then you zoom in inside the English and you see how they cluster by topics, and you can keep zooming in and you see more and more structure. Emerging. I'm sure there are many applications that I'm not aware of. To explain how these things really work, I will start with a very simple dataset though. I hope most of you are familiar with that. So it's an MNIST dataset, consists of handwritten images. So each sample is an image. I will treat pixels as features here. Okay, so I have some kind of features and 70,000 images. Okay, and now let's say we want to have a two-dimensional snapshot. So how would we do that? The classic method that probably first comes to mind, we can do principal component analysis. Again, I hope most people are familiar with it. We just project the data linearly on a subspace that has the most variation after projection, and here's how the first two principal components look like. So I color by the label, but the label information doesn't enter any of these visualizations in my talk all day. And we can see some structure. Ones are here and zeros are here, but overall it's not great because most labels, digits from most images from different labels, are mostly overlapping. Okay, so what else can we do? Here's another classical method developed 50 years ago called multidimensional scaling. So here we're trying to arrange the points in 2D to approximate high-dimensional pairwise distances. So we have High-dimensional distances D, we just find all of them in the dataset, and then we want to arrange the points such that the pairwise distance are just representing these Ds as close as possible in the least square error sense. It sounds very, very sensible thing to do, and if you throw MNIST in it, here's something like that comes out. And note that actually this is computationally very hard to optimize, and I'm just showing you a subset of 5,000, so a small subset of MNIST. And again, that's actually not better than PCA at all. So this is a bit disappointing. So why does it not work? And I think the reason why it doesn't work is actually very interesting. The reason MDS fails in some sense, like fails in a sense that this picture is disappointing, is that it actually is a bad idea to preserve high-dimensional distances. Because it's not possible to preserve them. You can see that as an example of recursive dimensionality, and I can explain that by just showing you the histogram of pairwise distances in the MNIST data before dimensionality reduction. Okay, and the— I mean, it looks reasonable, some kind of a bell-shaped curve, but note that all the distances are large. There are no small distances here. All the distances are around 2,000. The exact number doesn't matter. What matters is that they are all on this scale and there are no small distances. And now if you try to think how would you arrange the points in 2D so that there are no small distances, you see that it's impossible. And this, I believe, is the primary reason why, why this fails. So here's another example to illustrate that. Imagine that you just generate points from a standard Gaussian, meaning mean 0, unit standard deviation, in 2D. And I'm plotting the distribution of pairwise distances. Some distances are small close to 0, and some are larger. And now in 50 dimensions, or in 500 dimensions, and now imagine that your data is 500-dimensional and you're trying to match it with some arrangement of points in 2D, you just fail. It doesn't work. So the genius idea of the neighbor embedding, I think, is to say we just give up on that. We are not even going to try. Instead of preserving the distances, trying to go from green to blue here, we just try to preserve the neighbors. And the neighbors are the points that have very small pairwise distances, right? So we'll try to make it such that the neighbors end up neighbors. So this is the idea. So as far as I know, the really the first time this was suggested is a 2002 paper that suggested stochastic neighbor embedding idea. It wasn't really popular, was I think seen as very influential at the time. Then the follow-up work introduced t-SNE, a small modification that I will explain later on, and that became really, really popular, but actually also not right away. So these are citations from Google Scholar, and you see that actually people started using this a lot only in the recent years. And the reason— so this is not cumulative, this is number of citations per year— and the reason I think is exactly what I said before, that many different fields in biology and outside of biology started generating the data that's very amenable for this kind of visualizations. Okay, so even though this is a 20-year-old idea, that really gets momentum very recently. So now if I take the MNIST data and throw it into t-SNE, that's what comes out. And you see that it beautifully separates all labels, actually, in a completely unsupervised way. So that's great. Now I want to explain how it works. The— so I will introduce now the SNE and TSNE. The loss function of both of them— so the distinction actually doesn't matter for now— so the loss function of TSNE is the KLIP divergence between pairwise similarities. So we define something that I will call similarity or affinity, and that should be large when points are close together and small or even zero when they are far away. Okay, so we will have high-dimensional similarities measuring the properties of our actual data and low-dimensional similarities, and we want to move points around so that the low-dimensional similarities approximate the high-dimensional similarities. And the loss function is the KL divergence shown here. So P's are high-dimensional, Q's are low-dimensional here, and if you look at this loss function, you immediately see that you pay very high price for putting close neighbors close neighbors, remind to have high affinity, so p is large. And then you— if they are far away and your q is small, then this will be the high price here. If the, if the, the other way around, you also pay some price, but it's less. So if, if you have something that has— if you have a pair of points very far from each other, then the p is near zero, and there is this, this term almost doesn't contribute anything. You still pay the price. You will see a bit later why, and that's because the Qs are normalized to sum to 1, and this normalization actually is, um, and results in the price that you pay for putting neighbors that were far away close together. Okay, um, but I didn't tell you how to define P and Q, right? That, that's what I need to tell you now. So the P's, um,, and I see that I have a typo here. So these are high-dimensional affinities, so the affinities in the original data. The p's I will define as follows: I will just find all nearest neighbors. So for each point, I will find, for example, its 10 nearest neighbors, and then I will say the affinity to each of them is 1 and 0 everywhere else. And then I will symmetrize and normalize so that the entire thing sums to 1. So only nearest neighbors for very small number of k, like for example 10, get a non-zero affinity. And the low-dimensional— so apologies, this is just the other way around— the low-dimensional affinities, here I need something smooth so that I can differentiate things. But again, that's really the simplest thing possible. I take the distance, I put it through the kernel like a Gaussian kernel, and then I normalize to sum to 1. That's it. You can't really do it simpler. And the difference between SNE and t-SNE, really the only difference, is in the kernel. So the original SNE paper used the Gaussian kernel here, and the t-SNE used the Cauchy kernel that, as you can see here, decays slower. Okay, so some of you probably know t-SNE well, and they might wonder why I presented like that, because the actual— if you actually read the t-SNE paper, then it introduces this affinity somewhat different. It uses the adaptive Gaussian kernel. There's a perplexity parameter that regulates the kernel with and can be understood as the effective number of nearest neighbors and so on. So I argue, or I will actually just show you here, that this makes no difference. So here is the MNIST embedding defined with these Gaussian affinities with perplexity 30. So I don't even— I will not spend time to introduce exactly what it means. Important for me is that I take my definition of affinities that is really super simple. You just find nearest neighbors, you say these are— these, they have affinity 1, and then normalize, and this results in this picture. So these are not— these are not the same picture. If you look very closely, you will see some differences. It's really hard to see the difference. Okay, so, um, this I find more convenient for you to think about that. Um, okay, so that's it. I, I, I gave you the loss. I told you what the p and the q is. So we're done. We just need to know how to optimize that, and this is going to be important later on. So that's the— that's my most mathematical slide, but I need to explain these things. So the— this loss is optimized by gradient descent starting from some initial configuration points. So here is my KL divergence. P is a constant, so I can forget about log P. So I just have minus P log Q, and Q is W divided by Z. So I have these two terms here. Uh, this is normalization, right? The thing that comes out of the normalization and, and the other term that has p's inside. So the gradient descent of that works as a many-body simulation. I will have an animation on the next slide, so hopefully this will become clearer there. Every pair of neighbors, so points that have p non-zero, they attract each other. Just think about this physical force. While all points, all points, independent of what the p is, repulse each other. That's this term. Because you want— like, think about minimizing this loss. You want this to be small. Um, so, um, like this, for example, this term has to be small, so W has got to be small, so points have to be far away. And you don't even need to take the derivative to see that this is an attraction and this is repulsion. This wants to put the points far away, this wants to put the points close by because there's a minus sign. Okay, um, one can take the derivative and figure out the exact force that works on each point. And actually, it's pretty simple in this case, but even this is already enough to see what happens. So let me— ah, before I show this simulation, um, just one little word. I'm not going to hear about the actual implementations of that, and that's something I don't have time to talk a lot about today. If you want to embed 20 million points, you need to do this fast, and this is difficult because this is, for example, quadratic term.

Right?

It's for every, every point is repulsed from every other point. So you need some approximation here, and there are different ways. So if you heard about Barnes-Hart teaching, that's a way to approximate this to make it faster. Okay, and there are different ways to do it, and some are pretty fast. And here you can accelerate even finding the, the neighbors by using approximate k-nearest neighbor graph instead of exact. But this is a footnote. I imagine that this is all solved and you can just I mean, you can, you can iterate the gradient descent here. Okay, so now I'm doing the optimization of the TCNN on MNIST data. Here I start with a random configuration and I just let it run, um, and it ends up being pretty good but not great. So see what happens. So points of the same color are the same digit, right? They feel attraction, and you can just see how they like collect together in bigger and bigger blobs, but some don't. So blue point here, blue cluster here, and blue cluster on the right, they, they are stuck. So what you're seeing is a bad local minimum. They are stuck because they feel attraction, but they can't get through all these other points because they feel repulsion over them. And there's so many points that repulsion is too strong, right? And they can't penetrate. And it converges. If I let it run a bit longer, all movement will stop. It converges, but the minimum is— is, well, I argue that it's in this case for us it's bad locally. There's a trick of how you can do it better, and the trick, going back to the original Tisney paper, is, well, if it gets stuck because it can't penetrate, let's just increase the attractive forces. So we increase— as— so that's really optimization trick. For a while in the beginning, we increase the attractive forces you see all blue points can now actually combine together. And now we decrease them here and everything is expanding because now the repulsion becomes stronger again and you get the final embedding. So that's a better, uh, local minimum. Um, so a footnote here too, for this to work well, this initial stage where the attractive forces are increased, so that's called early saturation, this needs to be long enough, or the exaggeration needs to be strong enough, you know, for this to work out in this space. So actually, the heuristic here is that you need to choose the learning rate wisely, essentially big enough so that it works. If your learning rate is not big enough, in this time, all these clusters will not be able to come together. And only very recently, actually, it was understood that it needs to scale with the sample size. And modern implementations all implement this heuristic. So let me show what happens if you don't do that. So this is an example of t-SNE just taken directly from a paper in 2019 that has 2 million cells profiled from mouse embryo. And that's what they have in their Figure 1. And it's good, but could be better. And the only difference I'm doing here, or the only important difference, is that I'm now using high learning rate. And this learning rate that comes out since the sample size is so large, it's much— it's like several orders of magnitude higher than what they use because they just use some default parameters in some implementation available at a time. So now if you look carefully, look at the cluster 15 here. Part of it is here, part of it is here, part of that is here. So that's the same issue as we had with MNIST. And now I'm doing it with a high learning rate, and here's my cluster 15, right? So that's because the early exaggeration phase could work properly if my learning rate is scaled high enough. So this just shows that actually, well, as always in machine learning, so that is not really surprising, these optimization parameters can really matter also for this, for the neighbor embeddings. But I argue that in this case we have a good heuristic, so actually if your implementation just uses that then maybe you don't need to care about that anymore. That's good. Okay, so this does like half of the job, I think. But what another issue is, the issue of initialization. So we start with something, then we let it run. Usually, or traditionally, t-SNE uses random initialization, as I showed before in my animation with MNIST. Actually, I argue here it's not a great choice. Even without exaggeration, you will— you can have easily— can have situations where you— where t-SNE will converge to something that in some sense is suboptimal. It clearly breaks— not preserves some important features, global features of the original data. So this is a really simple toy example. The data are in 2D. That's the entire data. It's just a circle. It's just illustrative toy example. I do t-SNE with the proper parameters with random initialization, and I get a knot like that. It's actually a nice— I like this kind of picture. It's a nice knot, but I don't want to have this circle torn, right? So if I use a different initialization, for example PCA initialization, in this case, of course, PCA is just a circle itself, so well, I start with this and then it doesn't get torn. So that's good. That maybe seems a little bit— I have an animation also to show what happens. So here, random initialization, 6 different random initializations, all embedding a circle, and see what happens. A very interesting thing happens. I will come back to that later. During the early exaggeration phase, it's slowly unwrapping, very slowly, and doesn't unwrap fully. So we'll come back to that later, why it unwraps.. But once you turn it off, the early exaggeration, then the repulsion is stronger, right? You get these tears because this point and this point repulse each other, and then you get this final picture with this nice— so if you want to generate knots, you can do this, I think. But if you want to put embedding, you should not start with the random initialization but with something informative. And you can have different ways of arguing what is informative. But however you do it, you can take PCA, for example, and then in many, most cases, I would say it works better. And I didn't introduce UMAP yet, I'll come to it later. But the point here is that this is true for any neighboring embedding algorithm, I believe, at least for all that I've seen, because that's, that's an inherent thing here. The neighbors— you're taking care of preserving neighborhoods and you're not able to preserve the global features. So if you start with the informative initialization that does preserve global features like PCA, then you just end up with something that's more meaningful. Okay, I have, I think, one more real-world example and not a toy data like a circle. This is again a single-cell RNA-seq data. This is mouse cortex. Here I'm doing t-SNE with random initialization. I get all these different colors. These are different types of cells. In the mouse cortex clustered. And these are the colors from the original publication. But if I do principal component analysis, I get this. So I don't— and I can tell you what these three groups are. These are inhibitory neurons. These are excitatory neurons. And these are non-neurons. So just a quick glance at the PCA plot tells you there are three very different kinds of objects here. And that's true. That's biologically very meaningful. No way you can see it here. Moreover, some non-neurons are here on the top, some non-neurons are here at the bottom, interneurons are mixed together with excitatory neurons, and so on. So again, not great. If you do the PCA initialization trick, then of course these, for example, non-neural cells, they just start together in the lower left corner, so they will end up together in the lower left corner. All these islands that t-SNE finds. Okay, so again, you can measure it, you can measure, you can introduce some metrics to quantify this. I'm not doing this now, but it's clearly global structures preserved better here. Okay, so with this, I can come to these two, the main part of the talk, the two trade-offs. So let's start with a simple one, the low-dimensional similarity count. So I already mentioned that t-SNE was a later development on top of SNE. So what's actually the difference? And I already mentioned that the difference was the low-dimensional similarity kernel. SNE used Gaussian kernel, but because that's the simplest thing you can do, um, if you're a machine learner at least. And if you're— and the t-SNE said, well, let's do something that has wider tails, so we'll use the Cauchy kernel. Here's the formula. If alpha is 1, that's the Cauchy kernel. Um, and if— yeah, um, so that decays quadratically, uh, the tails when the distance increases. But in the— in a Gaussian, it decays exponentially, of course. So Cauchy has much fatter tails than Gaussian. So, and they argued that this addresses the crowding problem of SNE because, uh, maybe there are so many neighbors up there in the high-dimensional space So you want to have some slack in low-dimensional space and allow the points to move a bit further away in 2D so that the loss doesn't suffer so much. So we want this kernel to have wider tails to allow this further movement. That was the argument in the T-SNE paper. Actually, funny enough, I haven't— I have never seen an SNE of MNIST until we made it a couple of years ago. Because no, there was not even an efficient implementation where you could throw in this large dataset as MNIST and get the results for SN. So, but actually you can generalize that. So you can see this kernel as, as a kind of a t-distribution kernel. If alpha is 1, that's a Cauchy. If alpha goes to infinity, you get— it converges to Gaussian. And you can interpolate, but you can also choose alpha below 1. So this will be a kernel that's wider tailed than the t-distribution with 1 degree of freedom, which is the same as Cauchy. So okay, that, that's interesting. So if we go— note that this, as a neo-Feminist, it's actually not awful, right? It's reasonable. But okay, there's more overlap and, and less white space. So what happens if we decrease alpha lower? So I plug here alpha 0.5, and I get this. Actually, that was surprising the first time. I thought the digits will move further away, but instead they split into sub. So what you see here is some kind of substructure within a digit. And I argue that the substructure is meaningful. So for example, let's look at 4s here. They shatter in a bunch of islands. And if I look at these islands and just plot the average MNIST image, then in one of these islands, I get the 4 that's written like that. So that has a loop. And the 2s also, there's an island that has a loop here.. And in different islands, there is no loop. So actually, these are meaningful islands in some sense. And using heavier-tailed kernel brings out this finer cluster structure. At least that's our interpretation of that. And let me show how this works in two other datasets. So this is, in fact, one little part of this large library dataset that I briefly showed in the beginning. This is Russian language books. In the dataset, half a million of them. That's the standard TSNI. There's a very sharp divide at the point of Russian Revolution because the orthography changed. So all the words are now written differently as they were 100 years ago. It's over 100 by now. So before the revolution, that's why you see this sharp divide. But within, for example, if you look after the Soviet books, essentially, It's just one blob here. But using some labels that we have on the books, I can find the books on math. And they are all here. And the books on— the poetry books, they are all here, just searching for the authors, for example. And you see here that we get an island of poetry and an island of math with the heavier-tailed kernel. So these are meaningful islands. That's not just artifacts. It's not just noise what you see here. These are meaningful islands. And here, of course, all the poetry is also— it's close by. T-SNE does its job, but it's not separated from the rest. So there is this trade-off, I think, here between bringing out these maybe finer clusters versus showing them less separate from each other. So we can discuss maybe later in the end about what's a better visualization here. But the same happens across datasets. So if you take the single-cell dataset and decrease the alpha, then again it will shatter in more and more islands. And if you look at the islands, actually we can argue that these are meaningful splits, that something that splits here doesn't split arbitrarily, it splits in a way that represents the biology. Okay, and now the next part, or the biggest part— I'm not sure I have time to make it the largest— is this attraction-repulsion spectrum. The second spectrum. So that's a preprint from last year with the student, he was a master's student at the time, Nicholas. I mentioned early exaggeration before, and I mentioned that we just multiply the effective forces by a constant factor, but actually what happens if we don't switch it off? If we look at what embeddings we get with different exaggeration values. And you already could guess maybe from the animations that I showed before that when you look at what happens, for example, on MNIST before you switch it off, it actually looks like a nice embedding, right? So it makes sense, I think it makes sense to explore this entire spectrum. So I will denote exaggeration by rho. If rho equals 1, that's a standard t-SNE. And then I get the spectrum. Here on the right, I have stronger repulsion. Here on the left, I increase the attraction, so obviously I have stronger attraction. And here are different examples along this spectrum. And actually, there is a mathematical argument made a few years ago that— it's, it's not complicated, but I don't have time to explain it properly here— that if you increase, if you make attraction really, really strong, then what you're doing, you're approximating something called Laplacian eigenmaps of the affinity matrix. And this is, you take the affinity matrix, so this P matrix, the P-values, the affinities, and then normalize it in some way and take the eigenvector composition. And that's a method suggested 20 years ago, and you can use it, and it actually sometimes is useful. And here on AVENIST, this looks like that. And you see that, so it's clearly worse than t-SNE for our purposes of seeing the data. But you see that as the attraction increases, we kind of converge there, and that's because— so of course, as the attraction increases, you get smaller and smaller embeddings. So this is one technicality here, but I'm kind of zooming in, and when you zoom— after you zoomed in, that's how it looks, and that converges to the minimum because the leading eigenvectors of the Laplacian have the slowest shrinking speed. That's the, that's the technical reason here, but look up that paper if you're interested. Um, very interesting aspect of that, I think, is that there's a lot of information in the further eigenvectors of the Laplacian. So for example, look at these 3 colors here. That's 4, 9, and 7. You look at the first and the second, they overlap. You look at the 7th and the 9th eigenvector, and suddenly they are nicely separated. But you don't see this in the first 2. So you increase the repulsion now, like with t-SNE. And remember what I said before, the repulsion term is data agnostic. Just everything is repulsed from everything. The repulsion doesn't care about the data at all, just wants everything to be further away. And doing that brings out information from the higher Laplacian eigenvectors into the 2D representation. So I find this fascinating, actually, that it works like that. Okay, what is interesting though, so what's the intuition behind the spectrum? What properties? So here on the right, I kind of already said it, you see more of the local structure. But what do you see more when you go to the left of this spectrum? And the way we interpret that is that you see more and more continuous structures. So here's another different data set that's a brain organoid development single-cell RNA-seq data. As you go from blue to red, the organoid develops, and here you see very clear this progression, and here it's still visible, and here you don't see it, but you see all the different cell types. Okay, so I have to accelerate a little bit, so I will skip some of the examples and get to this part, which says that— well, so it's a different— so one observation is about the spectrum and how on the left you get continuous structures represented, and on the right you see more discrete structures represented. We have a lot of examples of that in our preprint. But it's different, it's a separate observation, is that several different neighboring embedding algorithms actually generate something that looks very, very super similar to the points on the spectrum. And that was surprising because if you know how the UMAP works, if you just read the UMAP paper, it sounds so different, so different from the TSD. The loss is different, the affinities are defined differently, everything is different. Different. And the same for force atlas. From the first glance, it doesn't look similar at all. But we look at dataset after dataset, and we see that UMAP looks like t-SNE with some exaggeration, and force atlas looks like t-SNE with larger exaggeration. And actually biologists love force atlas because you get embedding like that, and that so nicely corresponds to the biology of that, right? And here it doesn't. So, but you can also just increase the saturation in t-SNE and we'll get the same thing, roughly. Okay, so why does it work? So I will explain it for UMAP very briefly here. So the UMAP's loss function is a cross-entropy between non-normalized affinities. So remember, in t-SNE, the high-dimensional affinities are normalized to sum to 1, low-dimensional affinities normalized to sum to 1, and that's the normalization that takes care of the repulsion in t-SNE. That's the gradient of t-SNE here that I wrote in a way to bring out these non-normalized terms, and this is the normalization. Okay, if you do the exaggeration, this term appears here. Well, nothing else changes. In UMAP, there's the loss function is cross-entropy. You can rewrite it, um, I'm skipping that, and in the end you get something like that. So here the repulsion comes out from the cross-entropy, it doesn't come out from the normalization because there's no normalization. But if you look at it after you did this algebra, it looks very similar, looks super similar. So what— but this term is missing, the term with z is missing. And if you look at what the value of this term is for t-SNE, we just measured it on MNIST, and you see, well, for normal t-SNE, it's 10^-2. If you do some exaggeration, it may be 10^-4. So this is a really small number here, and this number is not present here. So how come. It makes the same result. So here I wrote that UMAP gives the result similar to t-SNE with this factor set to 1/10,000, but it doesn't have this factor. So why is that? And the answer to this is— well, our answer to that is that the reason is the optimization of UMAP. So UMAP's optimization uses negative— something called negative sampling. And what they mean by that is on each gradient descent step, they just sample a very, very small number of these— of the terms from the sum.. And this of course just decreases the influence of this sum, right? And if you look at what fraction they sample, then it's somewhat close to this number. So there you have it. It kind of effectively introduces this small number here. It effectively decreases the repulsion, but it doesn't come out from the loss. It doesn't come out from the math of UMAP as it is set up. It kind of accidental byproduct of how they do the optimization. So the reason UMAP works is not thanks to its loss function, but in some sense it's despite the loss function. And we have different experiments in the paper that show that, that provide direct evidence that this is the case. That maybe I have to skip in the interest of time. For different datasets, you get slightly different exaggeration values that provide the best match for UMAP, but there's always a very good match and the exaggeration is somewhere between 4 and 10. So I can't explain the number 4, and sometimes it's not 4 but 8 or 7. The argument here is that, well, there's somewhere on the spectrum of exaggerations, that's where the UMAP will be. And let's say, so the relationship, the exact relationship to force-sensitives 2, I think we understand a bit worse, but the match is actually as good. So there's some universality here, I think, beyond what we what we could mathematically understand in that paper that we just empirically show. Okay, do I have 2 minutes? And then I'm— okay, great. So, um, the— on the left here with strong attraction, you preserve these continuous structures, uh, like the organoid development type. What do you preserve on the right? More clear. Can you— are you actually losing something tangible when you go more to the left, because maybe you should always use false alphas or always use UMAP instead of t-SNE. So this is actually not in the preprint because we did it later, but I argue that yes, definitely you lose something, you lose a lot. You get— there's a metric that measures how many of the nearest neighbors in the high-dimensional space you have as the nearest neighbors in the lower-dimensional space. Let's call it nearest neighbor preservation. It's just, it's just a fraction, so it's from 0 to 1. It's a fraction of the 10 nearest neighbors that end up as 10 nearest neighbors in 2D. So for t-SNE on MNIST, it's something like 35%. That's not bad. You increase exaggeration, goes down a lot and very quickly. And for UMAP, it's also much lower, more like 10%. So actually, the neighbor structure is much more accurate here on the right than here. The problem is that with MNIST, you look at it and you think, well, okay, whatever, maybe I just don't care. Like this picture here looks as good as this, or maybe even better. In some sense, I think I like this picture more for MNIST because it shows, you know, more clearer the different digits. So who cares about this exact nearest neighbors? And I argue that we do care in some, at least in some situations. And I want to show, and I can finish with that, another example that's embedding, has to do with embedding document libraries. So A master student in the lab, Rita, she's doing now this work where she tries to embed all PubMed. So that— now I'm telling you what the image was that I started with. She downloaded all PubMed abstracts. There's 20 million of them that actually have abstracts in English. And then we use this bag of words representation where samples are these PubMed papers and the features are words and there's some normalization and preprocessing going on. But then eventually You just put it into the neighbor embedding algorithm, into t-SNE, and that's the embedding that we get. It's colored by topics. So we kind of infer topics here by where the paper was published. So if the journal where the paper was published has neuroscience in the title, then we color it in yellow. And I don't have time, but if you look very carefully, you'll see a lot of paramedical structure. Part of the neuroscience is together with psychology, and this is more cognitive neuroscience. Part of neuroscience is close to cell, and that's the cellular neuroscience. You can zoom in and look at the papers. And it makes sense. And probably the bigger half of this embedding is all medicine, so you get cancer and so on and so forth. We're really doing this now and still exploring this. You can color by year, publication year, and see structure there. Or look at it uncolored and you see all this, all this very, very fine structure that t-SNE brings out. Now, why do I say that this metric is important because what one can use it for is, let's say you take your paper, just any of your favorite papers, and you zoom in, you find this paper, and then you look at its neighbors. So you can explore the literature by doing that. But of course this only works if the neighbors, like the really neighbors that you get in 2D, they are meaningful. And what you find again here is before, if you increase exaggeration— so this is no exaggeration, this is consideration 2 and 4, then it just drops dramatically. And this does correspond— so I don't have time to show that, but it does correspond to the neighbors that you get into D being worse in a sense. You look at which neighbors they are, and they just don't make so much sense. Interestingly, we need to spend a lot of time optimizing this thing to get better values here. So here is our take-home message from this work in progress. T-SNE without exaggeration strongly outperforms t-SNE with any exaggeration, or UMAP, which we also tried, in terms of this local structure preservation. Meaning actually this making these things useless for this point of local exploration of the literature. But it may require a long time to converge. We're still working on how to do that because that's the first time I'm working with a dataset of this size. Single-cell biology doesn't have 20 million cells. Yet. Okay, let's keep that. And just the short summary is that I argued that optimization is important, initialization is important. In this sense, neighbor embedding are no different from any other machine learning algorithm that you apply gradient descent to. Two important parameters are the kernel shape, the degree of freedom, and this exaggeration, the attraction-repulsion and not, for example, the perplexity or the number of neighbors that usually people think of as an important parameter of t-SNE. And the reason I say that is if you have 20 million points, you can't increase this any way from 10, because even using a very small k takes a lot of time to converge. And the larger you— if you want to increase the perplexity, you will just never, never have the embedding. So this is effectively fixed to a very small number, but these two things you can change.. And there are trade-offs between— so saturation controls these trade-offs between global and the local continuous DC structure. Other algorithms— and I gave these two examples, but actually I have other examples— well, different neighbor embedding algorithms give something that's pretty close to what you get on the spectrum. So I think that's this universality of neighbor embeddings that we only partially understand so far. For UMAP, we do understand it well. Also, there's a follow-up work by Fred and Sebastian that looked into it for other algorithms, maybe not yet. And for UMAP it works thanks to negative sampling, which I think is ironic and very interesting because it's often— actually often in machine learning, deep learning for example, things work for other reasons than people originally thought they work. And this for me, this gives one of those examples, but in a way in a simpler situation than the deep learning. Okay, with this I thank all of you for listening, and these are the people who contributed to to some of the stuff that I was showing in the funding in the Behrens Lab where I am at.

Thank you. Wow, thanks for a great talk, Dimitri. You're a courageous man, not only in analyzing, you know, election results, but also in, in, um, going over a slide. Honestly, you know, wonderful science and great animations also, very happy with this.

Questions?

You can raise a hand or you can post your question in the chat. Philip Jormeister is the first one. For him as an end user, can you recommend any ready-to-use implementation of TISNE where you can adjust parameters such as kernel shape and attraction-repulsion?

Yes, that's an easy question. I recommend— I, I now always work with something called OpenT-SNE, and that's developed by Pavlin here, and some of these things were integrated there actually when we were working on that together. But open— so that's for Python, sorry, depends on where you're working.

If the question is about Python, then just use OpenT-SNE. Thank you. Nicholas Bäumer asks, is n over 12 generally applicable rule for choosing the TISNE learning rate?

Yes, so let me, let me go back there. Yes, the short answer is yes. The reason there's 12 is because there's 12 here. I think I didn't have time to explain this properly. So you use exaggeration 12, and that's just the value that the original paper suggested. I don't know why, it could be 10 or 20, this doesn't actually matter, just some number that is sufficiently large. And then you can show that the gradient descent may diverge if the product of the learning rate and that is larger than 1, or larger than n. That's— this paper shows that. So if you— that's basically the largest learning rate for exaggeration 12 that you can have so that it doesn't diverge. Okay, if you want to have— if you want to change 12 to something else, then you need to change that accordingly, otherwise it will blow up.

Thank you, and apologies, I went wrong in the order.

Leonardo asks, um, "Can something be concluded about the distance between clusters in the low-dimensional representation?" Yeah, so that's a more difficult question. And I guess, let me think of a good slide here. So to the first approximation, maybe no. Okay, you need to be really, really careful in— so for example, let's— here's an example. You do t-SNE, all the parameters are set appropriately apart from initialization, which in this case is bad. You get this embedding. I would argue that this yellow cell type— so if you know what the cell types are, it's pretty clear that the yellow cell type should be close to the orange cell type. The colors here are chosen smartly so that actually the distance in the color space is meaningful. So they should be here, but it's not. So if you look at the distance here, you would be misled about your interpretations. That's why there's— it's a common advice that you can read when you read about t-SNE is that don't interpret any large-scale features of the data. If you are very careful in how you're doing that, for example, initialization is chosen appropriately, and then you get something like that, then maybe you can interpret something. But, you know, rather err on the side of caution here. And I guess there can be datasets where initialization doesn't help. And in a way, what I think it's one of the open questions that we, for example, I'm also interested in working— we started to work on how to do this embedding such that the larger, like, the neighborhoods between larger groups of cells are also meaningfully preserved. But this doesn't do that, but importantly also UMAP doesn't do that, and no other algorithm that is based only on preserving k-nearest neighbor graph neighborhoods will do it for you. So some people argue that UMAP is better in that. It may be better on some specific datasets, but it's not—

you can't really rely on that. Also further up in the chat, Sebastian asked, looking at other dimension reduction methods that build on the KNN graph, such as isomap, local linear embedding, they do so much worse than the method you discussed today.

So what do UMAP, t-SNE, what do they do right which these other methods do wrong? Right, so I think, so my take on that is something that I tried to say here. So I wouldn't, so isomap for example, for example, is— I think, does— for me, it doesn't qualify as the nearest neighbor embedding. So you can have different sense in which things are based on the k-nearest neighbor graph. IsoMap constructs the nearest neighbors, but then it computes geodesic distances between all pairs of points, and then it uses multi-dimensional scaling to embed that. That's essentially the IsoMap. So by the time you are at the embedding stage, you have pairwise distances between all points, and some of them are large, and you try to preserve that.. So for me, ISO-MAP is not— like, neighbor embedding is a vague term, maybe, that it doesn't have a clear definition, but ISO-MAP doesn't qualify for me. So, and we see that, and of course it may preserve something that T-SNE doesn't preserve, but across what we see again and again is that really, if you want to have a good embedding— all good, what is good— but meaningful, interpretable embedding of these kind of datasets, then you need— that it needs to be a nearest neighbor embedding. And there are other examples than SNE, UMAP, and force-samples, but actually not a lot. So one example that— sorry, this will probably look weird on the video, but there's a very recent suggestion. Maybe some of you have seen this paper. And that's— so that would be another case of neighboring embeddings. It constructs k-nearest neighbor graph and chooses some attraction and repulsive forces and optimizes via negative sampling. I think it suffers from the same issues as UMAP, and you can also position some of these things on our spectrum and so on.

Very good, thank you. In hindsight, I think we should have invited our colleagues from the humanities who sometimes feel marginalized by, you know, biology with all their data and all their might and, you know, everything going high throughput. You've been telling us to them that, you know, it's them who have the lots of data. They would have been so happy to hear this. So we'll invite them next time. I would like to offer an exit point here for people who need to go and do other things. I think we can have at least a short after session for those those who didn't manage to ask their question right now. And well, those with really deep interest to continue the discussion will get in touch with Dimitri separately. Dimitri, that was a wonderful talk. Thank you so much. Thanks for coming. And yeah, looking forward to next talk in the data science seminar series. Yes, me too.

Thanks for inviting me. Bye-bye. Thank you.

Bye.