5
$\begingroup$

The shortest form of this question is:

How much TDA can be done with tSNE?

Specifically, I'm referring to the application of TDA to clustering data, so, think along the lines of Ayasdi's implementation:

enter image description here

My understanding is that TDA constructs simplical complexes on a continuum of scales, to then find persistent components. This is an oversimplification because there is also work done by the Mapper algorithm to recognize persistent homologies.

Whereas, tSNE is a 2-D stochastic embedding, which assumes two separate distributions: a gaussian distribution that generates neighbors in high dimensions, and a Cauchy distribution in 2 dimensions, and then constructs an embedding that preserves distances as best as possible between the original space and the embedded space. The analogy to persistent components can be made in our choice of the tSNE perplexity parameter, which specifies the width of each Gaussian distribution, and can therefore give us a simplical complex where edges connect pairs of points that generate each other with some minimal probability.

I would think then that tSNE is equivalent to TDA if we also compute persistent homologies?

Improve this question
$\endgroup$
2
  • $\begingroup$ A different nonlinear dimensionality reduction called tree preserving embedding (dx.doi.org/10.1073/pnas.1018393108) is essentially (i.e., up to practical details) functorial in the sense of Carlsson and Memoli. I have slides detailing this; email me if you want them. $\endgroup$
    – Steve Huntsman
    Commented Apr 6, 2017 at 12:08
  • $\begingroup$ @SteveHuntsman: Thanks! TPE looks interesting in how it better preserves density than tSNE. However, it looks like TPE is O(n^3) whereas the Barnes Hut implementation of tSNE is O(n*log(n)) making it much more attractive. I forget the complexity of TDA but if I recall correctly it's at least n^2. So one of the ulterior motives behind my question is to understand how much is lost in terms of topological structure, because it's way faster to run tSNE. $\endgroup$
    – Alex R.
    Commented Apr 7, 2017 at 1:00

1 Answer 1

Reset to default
10
$\begingroup$

I am a co-founder of Ayasdi and contributed to the the original research at Stanford.

The screen shot that you pasted is the output of the Mapper algorithm. A couple of notes of clarification:

  1. Mapper produces a graph as an output, where nodes are groups of data points and edges between them signify non-empty intersection i.e. some points can be in more than one node and whenever that happens, Mapper connects all such nodes.

  2. The output of t-SNE (and other dimensionality reduction methods such as PCA, MDS etc..) is a lower dimensional representation.

  3. Mapper uses as its input results of dimensionality reduction (e.g. Mapper is happy to consume the results of T-SNE as an input).

The above is to say that comparing the results of mapper and dimensionality reduction methods does not make sense - they produce different objects.

Why would you want to use Mapper when you have awesome dimensionality reduction?

  1. Dimensionality reduction methods suffer from projection loss - points well separated in high dimensional space, might appear to be in the same neighborhood in the lower dimensional projection. Mapper protects against this by clustering points in high dimensional space after determining a grouping from the lower dimensional projection.

  2. The output of mapper is very convenient - it is easy to work with graphs and build ML pipelines on top of them.

Some other notes/pointers:

  1. LargeVis - since you are interested in efficient dimensionality reduction.
  2. Your idea on constructing simplicial complexes - there are many ways of constructing complexes (e.g. vietoris-rips), and yours is interesting as well, but if you want a complex, simpler methods are generally better.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .