Topological data analysis: How to quantify "holes" in your data and why?

Speaker 1 [00:07]

Thank you for the introduction, and thank you everyone for coming. It's amazing, this room, it looks full. I'm André, I just finished my PhD at the Institute of Science and Technology in Austria, and now moved to INRIA in France. So I will talk about a tool that's called topological data analysis, and I'm telling this from the point of view of, I am researching in this area and think it's a cool tool to use on data. So, I will use examples that are kind of more synthetic and silly. I will not have a concrete use case. I will leave that, hopefully, up to you to see whether this can be useful for you. The goals of this talk are threefold. I want to tell you what is TDA, so topological data analysis. What is it about? Why is it a useful tool to know about? And then, because we are at PyCon, how to use it with Python. So the first example I will go through is a pipeline to classify point sets. Let's imagine that we have some data like this, where each bracket here is one data point for us. So one data point is several points in a plane. And we would like to split them like this, because here each row has some different parameters with which I created random point clouds with some specific random point cloud process. And now we would like some pipeline to classify them like this. So here are some specific things about how we want to classify. We want to care about spatial relations between the points, but we don't really want to care about the absolute position. Examples of this, the easiest are coming from really positional data. So you can imagine you have positions of cells in a tissue from a body, then you don't really care where exactly a cell is, but you do care very much about their spatial interaction. Even more detailed, you can have positions of proteins in molecules within a cell, and that's actually some example that I saw a talk about where people really care, okay, if the spatial distribution is different, then the protein is different. want to automatically classify. Another example would be positions of atoms in three-dimensional structure in a material of, let's say, some amorphous glass, and then you care about some properties with respect to the spatial distribution. But the examples can be also more abstract. You can imagine that you have some time series or, you know, some anomaly detection. You can have abstract data. You don't really care where exactly each point is, because maybe the situations are very different, but you care that one point set is very different from the others because that's some anomaly, maybe there is some fraud going on or something like this. But for the sake of examples, I will stay with more concrete things. So here we just have points in a plane. So one thing that many of you might think of given this kind of problem is, okay, let's let's use what we know, let's just rasterize the points and classify it with some classical image recognition. And, you know, this is a viable solution for sure, but there are definitely some disadvantages. You need training, you need a lot of data to do the training right, arguably the problem is not really a visual problem, and you need to somehow deal with the things that you don't care about, right? if you rotate things or translate, you still want to consider it the same. So let's not do this, and let's instead see how we can use topological data analysis to deal with this problem. So what topological data analysis does is it creates some fingerprint for each point cloud that summarizes the spatial distribution, and that's the main part. We will use a particle tool from TDA called persistent homology, and then once you have this fingerprint, you can vectorize it, and then you can use whatever classifier that you like. So how does this summary work? We start with a set of points, and we want to say something about kind of the shape of how the points are distributed in a plane. And we want to create a fingerprint that we can then use in further analysis. The main idea is that we can grow disks around those points and study the evolving shape. And the particular thing we look at is of two types in this case. The first is components of connectivity. So here I have green edges. Each green edge is drawn as two disks merge two components together. So in particular, in the middle picture, you see that here the disks are connected, but there is no edge. And the reason is because these components were already connected, so this was not a new connection. So the green edges are just new connections. And then I just take all these edges, and I remember their lengths. Okay? It sounds silly, but it really tells you something about the connectivity of the points, the distances that they have with respect to each other. And now I do something similar but with holes. So right, this was components of connectivity, and now we look at holes or loops in this. We do the same thing. We grow the disks, and whenever we have a loop in our data or, you know, some area in the plane around which we have the disks but is empty inside, we recognize this as a loop. And then again, we get the radii where something like this gets created, like the second picture here, and a radius where it dies, like the last picture there, and we pair these events together and draw it as a bar. So here you can see something that we call a barcode. The Y axis is irrelevant here. It's just about the X axis and the starts and ends of those bars. You see that there are two big ones and a lot of tiny ones. The big ones are really what matters. So this one really correlates to this hole that you see at the picture. And again, the second and the last is the birth and the death radius for this feature. So the birth radius is here, the death radius is there. If we grow a bit bigger, then we see where the second feature, the second big feature that we care about comes from. It's from this other loop. And again, where the arrow comes from, that's the birth radius, and the last picture is the death radius. So now we have these bars for components of connectivity and for loops. This is nice to understand, but a little bit difficult to work with and visualize when you have more of them. So here I will, oh, okay, I also wanted to show you that there are also some tiny ones that are a bit irrelevant, but might also be relevant when you have a lot of them and you want to maybe summarize something about those as well. But instead of the bars, we often look at the scatter plot. So this is Persistence Diagram. It's exactly the same information, but instead of drawing the bar, I use both x- and y-axis, and the x-axis is the birth time, and the y-axis is the death time or radius. So hopefully with this, it's clear what it means. You see that the top bar is shown as one dot that's far away from the diagonal because the difference between the birth and the death is large, and the other one is there at the top. And all the tiny ones are very close to the diagonal because they are very short. So the diagonal means the birth and death is the same. So if the difference between birth and death is small, the points are at the diagonal. So hopefully this object is somewhat clear. What we really care about are the things that are far away from the diagonal. The green parts at the persistent diagrams are the components of connectivity. They are all at this vertical line because they all started at zero. At zero, we already had all the points, and then we just merged them. So it's only the death times that go up. So what can we do with this? Let's come back to our problem. We have point clouds. What do we do? We compute this persistence diagram for each of them, and then we have a bunch of persistence diagrams. Now, this can seem silly. I went from point clouds to point clouds, right? So how did I help myself? The important thing is that the point clouds that we have now are of a different sort. Here the absolute position of each point really matters, right? If I transfer some point around, then suddenly the bar says very different thing. The radius when it got created and died would be different. So here we can compare them much more directly than before, and that's the important thing. It's still a bit tricky. How do you compare them? There are many different possibilities. One nice option is to vectorize them, and one particular vectorization I will show you here is quite intuitive. You can just kind of blur the points and have a raster image where, instead of a point, you put some caution over it to blur it over the pixels, and you see that visually the things on the right side are kind of capturing the things on the left side. Now that we have vectors, we can do whatever, right? You can put some simple machine learning. Here I just do a very simple dimensionality reduction, so here I do principal component analysis just to show you that the vectors are indeed different for the different rows. It looks like this. Maybe you wouldn't really trust me that it looks so different when there is so few of them. When I put 100 points in each category, then it's quite convincing. We can also do something else. Here I do UMAP. That's also a dimensionality reduction method. You also see that it clusters kind of nicely. Not all the points are separated all that well, but this is just a silly example. If you would want to look how some of them look like, then I show a bit here, but I will not really comment much further there. So what did we learn here? We learned that we can take this problem of the classification, and without any sort of training, we already get some pretty nice separation. And of course, if you wanted to work further with this, there is many parameters to tweak and many other things to do, but it's a nice, you know, nice start. Okay. How do we do this in Python? I will show you how to get from the point cloud to the vector. Now, part of why I wanted to give the talk here is because there is many TDA packages, because the field is still very academic, and many people implement their algorithms. But then there is lots of overlaps of what packages do what. And it's a bit difficult to orient yourself in. This will not be any summary of all the packages and what they do. I will more show you some that can do the job so that you could start analyzing your own data. There is a nice web page called Catalyst where you can search for software and packages that do the things that you would like to do. It looks like this. You can enter some text at the top, like Python or, you know, point clouds, and it will show you which packages you can use. I will show some particular analysis in Goody. That's one that's pretty popular. I have a good experience with this, that it's written in C++ with binds to Python, but it actually installs, so that's always nice. All right, so how to go from point clouds to a persistent diagram. We start with points, they're just lists of some tuples, we import Goody, and now the first thing we ask Goody is to create something called alpha complex, so we have Goody.alpha complex inside the points in, and then we do this create simplex tree. Don't really think much about what this means, what's important is that what happens now is we build some discrete structure over the points that's then used for the further computations. This alpha complex is a buzzword you might see a lot if you Google about the political data analysis. There are many different options of what kind of complex you use. So the particular discretization of your situation can change things at the end. And so here I just wanted to tell you about some other names. So alpha complex and Delaunay complex is what we work with here. Here, check complex is something similar, it's used more in theory than in practice. Very popular thing is Viatoris-Ribbs complex, and why I tell you about this here is because if you have data that are of higher dimensions, say more than seven, then you should really use that. Okay, so we have our complex, now we tell this object to compute the persistence. And now that it's computed, we can get the barcodes. So we want to get the components of connectivity and the loops, so we call persistence intervals in dimension 0 and 1. So dimension 0 is components of connectivity, dimension 1 is loops. One thing that Goody in particular does is that it uses squared Euclidean distance rather than Euclidean distance. So here it's a bit technical, I just square-rooted so that the diagram I get in the end is more intuitive with how I read it. And then we can plot the person's diagram. You see that this library allows you to just plot it. The form in which it wants to eat the bars is like this. You put a list, and the first is the dimension zero, the second is the dimension one. You see that there is one blue dot that's very high. Blue is the dimension one, so loops, and it corresponds to this hole in the middle. Okay, some alternative way how to plot it. So as I said, many libraries do the same thing in a bit different way. I'm showing this package in particular because that's my package, and what it does is a bit beyond what I will talk about, but, you know, I wanted to have it somewhere in the talk, so you can at least plot the diagram with my package if you would like. I like it visually better. All right. So now we have persistent diagram. We want to vectorize it. You could do the vectorization with Goody also, but because I want to show you more libraries, I imported one called persim. That's for persistent image, and that's the one that I showed before where we kind of rasterize the diagram, blur the points, and get a vector. It might look a bit scary at first that there is a lot of parameters, and indeed you should take some care to set the parameters well. So what's there is the birth range, so that's the radii at which you will rasterize, right? Then the persistence range, so that's kind of the death radius. The pixel size, so the pixel in the grid, how big it should be. And then there are some more. The weight, as such, you should just leave this. That means that if the point is further away from the diagonal, that's what we call persistence, the difference between birth and death, then the Gaussian will be bigger. And that's because we care about those points more, so we want them to be weighted more. And then you have weight parameters as to how much bigger this Gaussian will be. Once we set up these transformers, then we can apply them. So for the dimension zero, I use the personal image transformer zero. I say transform, load it, put it onto the bars. There's one detail. You see that I'm not using the last bar. That's because, as you see at the person's diagram, at the very, very top, there is this green component on the red line that's an infinite living component. So one component is still left at the end of the procedure of growing the disks, right? And it's something that's always there and not really relevant for us, so we just throw it away and we don't care about this. And then I just take this and put it in a single vector, so I flatten those images, I put them one behind the other, and then I can work with this. So that's how you could do this analysis that I showed at the start. Just to mention some other options for vectorization, so that's more to have the buzzwords if you then look at the slides. What we use now is persistent image, but we can have also persistent landscape or silhouette. You can just do some simple statistics of the bars. So we just take the bars and say, okay, I take the number of them, I take the averages, I take the minimums, the maximums, the midpoints. It works surprisingly well, so that's a fun alternative. Pairslay is kind of a fun thing that you might care about because that's a specific layer for a neural network that aims to learn the right kind of vectorization. So that's a fun option. Other alternatives is to compare them directly. Bottleneck distance or Wasserstein distances are distances of the diagrams themselves that are not necessarily so good for applications because you cannot do averaging and stuff like that, but there's many kernel methods. So what the kernel method means is it's some function to which you put two diagrams. It tells you some distance, but it has nice properties, say, for machine learning and so on because you can also do averaging and similar things. And the last option is to just look at the Persistence Diagram, and that is often quite powerful because it detects something that you might want to see in your data. So here I will show you several things at once. One is another library. This one is called Teaspoon. It's mainly for signal processing, but one nice thing it has is this Make Data module That is useful when you want to just play around and, you know, create some data and try out the methods. So I create a sphere with 500 points. Here you can see that it's a sphere. But let's say that I don't know whether I have a sphere or not, and I want to check somehow algorithmically, so I will use topological data analysis for this. I do the same pipeline as before. I use the Goody, I compute persistence, I compute the persistence diagram. Here I use a bit different method to get the bars, I just say dot persistence, and you see that the form in which it's written is like this. It's tuples of a number and a tuple. The first thing tells me the degree, the second tells me the bar. And you see the important thing here is the first thing is degree two, and the difference is somewhat large. So before I talked about components of connectivity and loops, now that we move to dimension three, we have a third type of a feature, and that's a sphere that's empty inside. So three-dimensional space around which we have our growing balls. So here it is as a persistence diagram, and here is the feature that I just pointed out. It's a degree two or dimension two feature that's very prominent, and it shows the sphere. Instead of sphere, I can take, say, a torus. And again, you see very prominent two-dimensional feature. What is a torus? That's an inside of, say, a car wheel, right? It's something, a tube that goes around and connects itself, and it's hollow inside. And the hollow inside is what we detect with the pair-resistance diagram here. Another thing that you see here, very prominent, are two loops. And these two loops are one loop that goes around the whole tire and one that goes around the tube. Now, this might be a bit confusing at this point with what I told you so far. So what is a loop again, I hear you ask. So let's go again through this. Before I told you it's just a hole, right? But suddenly when we are in third dimension and you imagine that you have just a loop like this in 3D, then it's not really a hole, right? It doesn't enclose any space. So how do we actually define a loop? This is what I showed you before, and this is where the topology in topological data analysis comes into play. In topology, we can morph things and consider them still the same. So this loop can be morphed like this or like that, and still the same loop for me, as long as it stays within the disks and as long as I don't do any cutting or gluing. So it's really a rubber band, right, that I can move around. So if I have this blue loop and this green loop, those are different because there's no way how I can move this blue rubber band to the green one because there is the hole in the middle that doesn't allow me to pull it through. This red one, it looks like a big loop, but I can contract it into a point, so it's really a dead loop for me. So hopefully now it makes sense when we talked about the features that it gets bored when you can draw a rubber band that goes all around, and it cannot be contracted, so it's some non-trivial loop. But once we grow the disk space so that the hole is covered, then the loop can be contracted, and then it's a dead loop for us. And so this is in what sense this torus had two big loops. Again, when you imagine that you have the tire, one goes around the tube, it just cannot be contracted. One goes another way around, it cannot be contracted, and you cannot change one into the other. That's a bit more difficult to imagine, but trust me. Okay, so this is what DDA does. Now we have point clouds. How about images? Often we have raster images, we can do something similar. Still starting with the growing disks, we can change our perspective. So you can imagine that you have a plane, and you have a function on this plane, which are cones going upwards from the points. And now imagine you are raising water from the bottom going up, and you always look at everything that's underwater. That's the space that you have as the growing disks, right? If everything that's underwater you kind of project down. It's the same thing, right? Why am I telling you different point of view on the same thing? That's because now that we have an image, we can do this kind of filtration of an image. So here I imported sklearn and loaded digits. These are 8x8 raster pictures, black and white, or not black and white, grayscale, and each pixel has some value. I will flip the values because I want the things that we painted to appear first, right? So we have it like this. And now we can slowly rise the level of water and show only those pixels that have that value or lower right so here you see the filtration at the at the first picture we have zeros we don't see anything at the second we have ones so we see these three ones that you see at the picture and then we go two three four and so on until at the very end everything is covered and now we can play the same game so these dots are some components of connectivity that appear and they get merged that will be the zero dimensional features and we have also some loops appearing, and that's dimension one feature that appears and then later disappears. I will show you again a different library just so that you see more. This one is called Dionysus, and it has a nice easy way how to apply it to the images. You could just install it, but as I was telling you before, sometimes there are problems, So when I tried, I just got, you know, failed to build a wheel. You need to deal with this somehow. I used chit-gpt. It helped me in the end in installs, so, you know, there are ways. So what can we do? We first build this filtration object. It has this scary name, phil freudenthal, and we feed it the image, where the image now is just an 8x8 NumPy array. And what it does inside is build some triangulation of the image and then puts weights on the triangles and the edges and the nodes so that it corresponds to this intuition that I described before with the water going from the bottom up. Okay, so then we ask Dionysus to compute the homology, and then we get the diagrams. I change the diagrams to something I can more easily work with. So here I just do a dictionary where D is the degree of the features, and for each I I take each bar in diagrams D and go bar birth, bar death, just have a tuple with the birth and the death. So this is what I get. This is how the persistent diagrams looks. What's important here, the blue loop, that's the dimension one feature, and that's what corresponds to the zero being zero, being a loop. Let's look more carefully, and let's start with what the degree zero features are. At two, we have some feature appearing, and that's why we have a birth event. In the diagram, you see it like this. When we grow, it grows like this. These things are considered connected. On the right side, in the green, we see a different feature that got born at four. We grow further. At this point, we merge those two. So at the radius 6, the red component and the green get merged. That's why in radius 6, we have depth of this feature that got born at 4. If we go further, then we get to radius 7. In particular, I highlight two components that get merged at the next step, at 8. So at 8, we have this. You see that two events happened. First is that components got merged, so you have depth of this green feature, degree zero feature. And the second thing that happened is that a loop got created. And that's why you have birth at 8 of this dimension 1 of a loop. And then when you grow further, at the end, at 16, it dies, because that's when it gets filled. So, you know, what can we do with this? We see, oh, okay, if there is a hole, right, in the digit, then I can detect it. So how about I look at all digits that have a loop of size at least 8? And by size, I now mean the difference between birth and death. So, how can we do this? Well, we import the digits. Then for each, we flip it so that it's the intuition that we have that first the things that we draw appear. We do the same pipeline as I just showed to compute the diagrams. Again, I put them to this dictionary form that I can work with easily. And now I count those that have the large loop, right? So I create an empty hits list. I go through the purchase diagrams and the targets. So the just the target is what says what the image actually should be, right? These are the labels of the images. And I check the maximum length of a loop. So you see that I look at person's diagram in degree one, I take the difference between death and birth, and I look at maximum of these. And if this is larger or equal to eight, I append the target to my hits. And I want to count how many zeros did I hit, how many ones did I hit, and so on. And so, you know, it's not as good as I actually hoped for when I was putting the example together. But again, it's just silly examples that I'm showing so that you get intuition about what the analysis is about. So it's not great, but it's also not too bad, right? You see that the ones that we would expect, 0s, 6s, 8s, and 9s, we actually got some, and we got many more of those than the other ones that don't have loops. And again, right, I'm not saying that you should use this analysis to classify digits, right? That's silly. What I'm saying is that this is something where I didn't do any sort of training. I just summarized this spatial distribution of the images, and I got some information from it. Right? And I think that that's fun and can be relevant in various settings. We can look, and that's, you know, one advantage. If it doesn't go right, and here we saw, oh, we got some twos, how come? The analysis is intuitive enough that you can understand what goes wrong. It's not a black box, right? If you compare it to some machine learning, especially some more advanced techniques, it can often be very difficult to kind of debug it, right, and understand why does it go wrong in my data. With this, it's quite clear, and I can look back at the images and say, oh, okay, it's because let's look at the first image here. You see the loop. There is a loop that's created at radius six, and then it dies at 15, right? So that's length nine, and that's why it appears as a hit. And that's also the choice of the filtration that I did, where the size of the loop as in really how big is it in the picture, that doesn't play a role here now, right? What plays a role is the pixel intensity at which it gets closed and the pixel intensity in which it disappears again. But you could also do a different filtration, and that's where the pipeline is very versatile. You could just do some, let's say you only choose some of the pixels of certain height, And then you grow from there, and then that would correlate more with the intuition of growing disks. And maybe you would capture the actual size of the loop and get more 0s and fewer 2s. OK. We have five minutes left. So there are some technical details I wanted to go through, but let's skip this. And the last thing that's very fun, because this is an actual application that someone told me about that I thought was very, very neat, how to find a second highest peak in a signal. So this example and the figures I'm showing are due to Stefan Huber. This is his website. I recommend this is a good source if you want to look into these things because he works in industry now and tries to apply the TDA methods to various things like optimizing the machines in a factory, you know, taking all the data from the sensors and doing something with that. But this example is very simple. You have some signal, there's some machine that measures some frequencies, and you see that there's a high peak, and then there's also a high peak at the very start, which is at zero. And they had this issue that, oh, we want to detect the second highest peak because the first one is something trivial that, you know, is there as an artifact. And then you could say, okay, let's take, like, the second maximum, but that can be tricky because if you go down from the top peak, there could be just a little bump that would be the second maximum, and then it wouldn't be really the thing that you care about. And so what we can do here is we can filter, and now we will filter from top to the bottom, but otherwise very similar as what we did with the images. You filter and you look what's above. You have components of connectivity appearing at the local maxima and then joining together at the local minima. And then we can get the person's diagram like this. Now it's kind of flipped because we went from the top, so the birth times are bigger than the death times. But if we draw it back into the picture, you see that the longest bar is the thing we don't care about, but the second longest bar is exactly this bump that we care about. So this is a very simple but actually useful case for topological data analysis. That's basically what I wanted to tell you. Let me finish with some resources that might be useful if you want to get into this. There's this Donut database. That's a database of research papers that apply TDA methods to any real-world problems. They have a lot of text, so if you care about some particular field, you can just search for that. Then there's the CAT list that I showed you before, a list of software that can be used. There is a fun online community of researchers that try to do also some videos as tutorials. So if you go to this YouTube channel and search for a playlist called Tutorialathon, it's like a marathon of tutorials, then you can find a lot of videos that can be very useful if you want to get into this. You can contact me. I'm always happy to talk. It's my LinkedIn GitHub and good old e-mail. And I thank you for your attention. I thank you, too. It's a difficult session when energy goes down on the third day of the event, and it's just before lunch. We are hungry. I'm hungry. And it was too advanced for me to follow everything, but it's existential. I like every time you were saying birth and death, I was like, oh, yes, it's very philosophical. Yeah. And it might be that I'm not going to even understand if there is a typo in the question or what. I'm just going to read what they asked. What different methods did you try before arriving to the increasing radius solution? What other ideas were you considering? Oh, before what? Before arriving to the increasing radius solution. Right, so I did not start with the problem and wanted to solve this. I jumped into this field as an established method. So I couldn't really tell you the whole history of how people came to this. I know that one use case that really made this popular was when you have proteins and you have positions of molecules in 3D. sometimes a protein is the structure so that there is a tunnel and that's important for killing a cell so there was an antibacterial kind of a protein because this tube makes ions go through and people are asking okay can we automatically detect a tube in a structure of a protein when I have positions of the atoms right and people often draw the balls around atoms to kind of, you know, simulate the radii where atoms are bound. But then it's tricky to get the right radius and so exactly this kind of growing spheres and noticing when a loop appears and when it disappears, when you do this in 3D, you can very easily identify tubes. So this was one use case where it really became popular and, you know, since then we are trying to use it on many different things talking about popular one popular question how useful it is with sparse and noisy data right uh that's always difficult right like how stable it is uh there are stability results so if you perturb your points then the results will stay similar so that's very powerful that's good if you have outliers that can be tricky to work with so you can very easily imagine you see the loop there, if I just put one point in the middle, and that can be just a mistake, it kills the loop very quickly, right? So that changes the result a lot. And people do different things. You can filter your data with respect to density, so you try to get rid of the outliers. There is something called multi-persistence where you have kind of two axes of the filtration. One is this density parameter, the other is the radius, but then it gets much more difficult with the fingerprints that you can get from there. Someone asks how we can apply topology data analysis to time series. So one application is that you just kind of plot the time series as points in your phase space. So you forget about the time, right? You just take the vectors, the measurables, and that can be some high-dimensional Euclidean space. And then you compute the persistence just for degree one, so that's the loops. And if you have a loop, this can detect periodic events, right? Because if you imagine, for example, you have a pendulum and you have the angle and the speed, classical example in physics, in the plane this would draw a circle because it goes back and forth. And so, you know, circles kind of show that there might be a periodic event. So that's one use case. And people try to use this, for example, for transcription in biology. So that's looking at which genes are being used in a cell, and these are like tens of thousands length vectors, and they try to see a loop and then see which genes are actually active in this loop, and then think about, oh, what is this biologically? I just envy your excitement. I'm just nodding, but I don't understand much. It's a fun field. I really envy. I wish I could understand. The last question. How well does TPA work for outlier detection? Right. So I commented on this a bit, that the outliers can be difficult to work with. For detection as such, I'm not sure. I don't have a good answer for this. I think that there are some ways, but I'm not that familiar with any particular methods to detect outliers. There are still several questions coming up. I suggest you to find Andre during lunch and bother him because he will be happy to answer your questions, I'm sure. Otherwise, enjoy your lunch. Thanks again for your very insightful advanced level talk. Thank you, everyone, for coming.