Big Data and the Topologist (2012) | Hacker News Reader

Big Data and the Topologist (2012)

ldtopology.wordpress.com

42 pointskdavis21 comments

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 "simplicial homology" in algebraic topology. Topologists like simplicial homology because it "only" requires that your input data is given in the form of a simplicial complex. A simplicial complex is a sort of generalized graph. Think of your input data is being described by vertices, edges, triangles, tetrahedra, and their higher-dimensional counterparts. Got it? Good.

Now, the problem about real-world data is that it does not come in the form of a simplicial complex. So, this sort of structure needs to be approximated somehow. And it is precisely through this approximation that the noise begins to creep in. PH tries to deal with the noise by assigning a weight to each feature it detects, sort of like a "scale" on which the feature "lives" (note that I am talking about a feature in the sense of a "hole" here). Features that live "long" are considered important. Features that don't live long, are not considered important.

So, coming finally back to your comment: You, as a user of PH, have to (sort of) decide what to consider as noise and what not. If you take a look at the seminal applications in PH, you will find that the extraction of features works quite well, although some sort of preprocessing might be required.

Anyway, if you are interested about using PH to analyse some data, I would be happy to discuss some stuff with you :)

Disclaimer: I am working with PH from the point of visualization. I try to make the topological structure of a data set visible.

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.

"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'

Yeah I understand all that. I sent you an email.

"Now, the problem about real-world data is that it does not come in the form of a simplicial complex." Not really true. real world data comes from a low dimensional manifold complex + noise.

I thought PH would extract the manifold but I could not get a tractable solution.

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.

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

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!

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.

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

Been working through the exposition in that paper the past few days, very very accessible writing. Very concrete intelligible examples. You can even ignore the few pieces or category theory and still take away a lot of understanding

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

Yeah that looks like a step in the right direction, but the use of purely synthetic examples leaves me a little sceptical it will work in practice. I don't have time to try every papers algorithms out. If they don;t put in real examples I think perhaps they tried it on real data but it still did not work. Persistent Homology is in its infancy, its developed by pure mathematicians who are a bit innocent to the horrors of real data (or willfully ignore pragmatic trivialities in preference to interesting theoretical results).

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

Out of curiosity what criteria did you use to indicate a homology element was persistent?

KXEN does some interesting things with assuming that what the data approximates is (I think) the solution set to a quadratic equation, rather than a linear one.

Reply on news.ycombinator.com