Live data from Hacker News

Big Data and the Topologist (2012)

ldtopology.wordpress.com

11–20 of 22 posts

Re: Big Data and the Topologist (2012)

#11

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.

Certainly, I would be glad to discuss things as well. You can reach me as topolomancer (at) annwfn (dot) net.

Re: Big Data and the Topologist (2012)

#12
post #7

I 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

Very good find, thanks for that. I recall that Peter Bubenik is working on a similar approach. His recent paper about "Persistence landscape" is also quite accessible, in my opinion: http://arxiv.org/abs/1207.6437

Re: Big Data and the Topologist (2012)

#13

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…

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)

#14
post #8
post #7

Earlier 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.

A good idea. This helps so that when the paper is updated one finds the most current version.

http://arxiv.org/abs/1303.7117

Re: Big Data and the Topologist (2012)

#15

I 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…

"persistent homology simply cannot decide whether something is noise or not"

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)

#16

I 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 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)

#17

Earlier 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?

Oh, well thats part of a general subproject of "what are good low dimensional computational geometry algorithms/problems/techniques that can help do basic data vis well?!". I'm spending a wee bit of time right now evaluating what are suite of primitives / algorithms/ data structures I want to have for designing a EDSL for declarative data vis / plotting.

Re: Big Data and the Topologist (2012)

#18

I 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…

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.

Re: Big Data and the Topologist (2012)

#19
post #18

Earlier 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.

I recommend Afra's book:

http://www.amazon.com/Computing-Cambridge-Monographs-Computa...

Happy to help if you need it!

Re: Big Data and the Topologist (2012)

#20
post #18

Earlier 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.

I like "Computational topology" by Edelsbrunner and Harer. They start with some basic graph theory and build on that to give a solid overview of algebraic topology, persistent homology, and even some Morse theory.
Post reply on HN