Earlier quoted context omitted.
Well, the thing about noise, from a topological point of view, is that persistent homology simply cannot decide whether something is noise or not --- at least not right away. To be more precise: A lot of what PH does is actually some sort of multi-scale Betti number calculation. The Betti numbers count the number of k-dimensional "holes" in a data set. Their calculation is usually done by something that is called "si…
I am just starting to dig into PH for data analysis. I would be very interested in speaking with you more about the topic.
Big Data and the Topologist (2012)
11–20 of 22 posts
Re: Big Data and the Topologist (2012)
#12I tried analysing data using persistent homology. What is not obvious, although they do admit it in one line of every paper, is that is it susceptible to noise :( So it has to go in the bin even though I really want to know what my manifolds look like!
Just a few days ago the following paper was published on the ArXiv, it specifically tackles the problem of noise. I haven't had time to read it thoroughly, but it also contains a nice introduction to persistent homology for statisticians, who are usually not familiar with the concepts of algebraic topology. http://arxiv.org/pdf/1303.7117v1.pdf
Re: Big Data and the Topologist (2012)
#13Earlier quoted context omitted.
Well, the thing about noise, from a topological point of view, is that persistent homology simply cannot decide whether something is noise or not --- at least not right away. To be more precise: A lot of what PH does is actually some sort of multi-scale Betti number calculation. The Betti numbers count the number of k-dimensional "holes" in a data set. Their calculation is usually done by something that is called "si…
Well said points. I've been digging into writing some data viz tools that leverage ph recently, and everything you say is exactly true.
Re: Big Data and the Topologist (2012)
#14Earlier quoted context omitted.
Just a few days ago the following paper was published on the ArXiv, it specifically tackles the problem of noise. I haven't had time to read it thoroughly, but it also contains a nice introduction to persistent homology for statisticians, who are usually not familiar with the concepts of algebraic topology. http://arxiv.org/pdf/1303.7117v1.pdf
A note -- when linking to arXiv, please link to the abstract, not directly to the PDF.
Re: Big Data and the Topologist (2012)
#15I tried analysing data using persistent homology. What is not obvious, although they do admit it in one line of every paper, is that is it susceptible to noise :( So it has to go in the bin even though I really want to know what my manifolds look like!
Well, the thing about noise, from a topological point of view, is that persistent homology simply cannot decide whether something is noise or not --- at least not right away. To be more precise: A lot of what PH does is actually some sort of multi-scale Betti number calculation. The Betti numbers count the number of k-dimensional "holes" in a data set. Their calculation is usually done by something that is called "si…
Isn't that general, when one does not know anything of the data? You need assumptions (for example the simple one of linear separability) to detect noise, and even then, it is conditional in the sense that 'this is the smallest set of noisy items that makes the rest of the data satisfy the assumptions'
Re: Big Data and the Topologist (2012)
#16I tried analysing data using persistent homology. What is not obvious, although they do admit it in one line of every paper, is that is it susceptible to noise :( So it has to go in the bin even though I really want to know what my manifolds look like!
Persistent Homology was invented to deal with noise (even though nothing that deals with data is ever IMMUNE to noise). The basic idea is to pick out/discern the topological features (betti numbers) which persist over a range of one or more parameters. Let's take the simple case of single parameter persistence (call it epsilon). Say that we are given a set of N points equipped with a distance function (i.e. given any two points, we can compute a distance between them (http://en.wikipedia.org/wiki/Distance)). Now, construct a structure comprised of sets of varying lenghts (a set with a single point in it is called a vertex or a 0-simplex, a set with two points in it is called an edge or a 1-simplex, a set with three points in it is called a triangle or 2-simplex and so on.). Given a fixed epsilon, we will: 1. draw an edge (1-simplex) between all pairs of points which are within epsilon of each other. 2. draw a triangle (2-simplex) comprising of all triples of points which are within epsilon of each other (note that three points can have edges between all pairs without 'filling out' the triangle) 3. draw a tetrahedron (3-simplex) comprising of all sets of four points which are within epsilon of each other (remember the note from the previous point) 4. and so on..
Now given this set of simplices for a fixed epsilon, we can compute the number of holes of various dimensions, this gives us a fixed set of betti numbers.
Persistent Homology allows one to study the evolution of this complex as epsilon increases.
The trick about noise : if the features are 'short lived' (i.e. they existed for a short range of epsilon), they are likely noisy. The reason why persistent homology is great is because it identifies the topological features and produces a measure for how long they survive.
I made an example video showing persistence homology in action for a simple 3D dataset (sampled from a torus). Check it out here: https://www.youtube.com/watch?v=CKfUzmznd9g Notice that in this video there are three long lines in the left frame. The first corresponds to betti-0 (there is a single connected component). The second two correspond to betti-1 (there are two loops on a torus). The third corresponds to betti-2 (there is a singe empty space within the torus).
Re: Big Data and the Topologist (2012)
#17Earlier quoted context omitted.
Well said points. I've been digging into writing some data viz tools that leverage ph recently, and everything you say is exactly true.
Thank you. You got me interested...would you like to elucidate something about your work?
Re: Big Data and the Topologist (2012)
#18I tried analysing data using persistent homology. What is not obvious, although they do admit it in one line of every paper, is that is it susceptible to noise :( So it has to go in the bin even though I really want to know what my manifolds look like!
Disclaimer: I have written a few academic papers based on persistent homology and co-founded a company which uses it. Persistent Homology was invented to deal with noise (even though nothing that deals with data is ever IMMUNE to noise). The basic idea is to pick out/discern the topological features (betti numbers) which persist over a range of one or more parameters. Let's take the simple case of single parameter pe…
EDIT: I just realized that it was covered by the blog post. I am a complete moron. Sorry.
Re: Big Data and the Topologist (2012)
#19Earlier quoted context omitted.
Disclaimer: I have written a few academic papers based on persistent homology and co-founded a company which uses it. Persistent Homology was invented to deal with noise (even though nothing that deals with data is ever IMMUNE to noise). The basic idea is to pick out/discern the topological features (betti numbers) which persist over a range of one or more parameters. Let's take the simple case of single parameter pe…
I find that fascinating. Since you seem to know what you are talking about, can you name a good introductory book on the topic for someone who doesn't have an education in higher-level mathematics besides what's in a standard CS curriculum (I am a PhD student in machine learning/information retrieval)? EDIT: I just realized that it was covered by the blog post. I am a complete moron. Sorry.
http://www.amazon.com/Computing-Cambridge-Monographs-Computa...
Happy to help if you need it!
Re: Big Data and the Topologist (2012)
#20Earlier quoted context omitted.
Disclaimer: I have written a few academic papers based on persistent homology and co-founded a company which uses it. Persistent Homology was invented to deal with noise (even though nothing that deals with data is ever IMMUNE to noise). The basic idea is to pick out/discern the topological features (betti numbers) which persist over a range of one or more parameters. Let's take the simple case of single parameter pe…
I find that fascinating. Since you seem to know what you are talking about, can you name a good introductory book on the topic for someone who doesn't have an education in higher-level mathematics besides what's in a standard CS curriculum (I am a PhD student in machine learning/information retrieval)? EDIT: I just realized that it was covered by the blog post. I am a complete moron. Sorry.