Umap: Combining multiple distances

[Vslira]

spoiler alert: this is a theory question, so not directly related to the library. Sorry if it's the wrong place to ask, feel free to close/delete then

@lmcinnes I just watched your PyData Ann Arbor presentation and got curious about your point on combining distances. You say something to the tune of "as long as you define a distance for a datatype (column), you can use that to embed the object".

How does that work, exactly? Let's say that I have a reading with 3 dimensions and another two dimension specifying, say, hour and day of the week. Do I need to provide the distance between objects in this 5-dimensional type or can I just define a distance using the first 3 dimensions and a second one using the last 2? I Got the impression that it's the second case (thus the supervised embedding capabilities of UMAP), but then you're implicitly saying that you can combine multiple distances with varying underlying distributions. Is that the case? And if so, can you give any pointers regarding how that works or how/under what assumptions it makes sense?

Because that's the general case of combining multiple distances/scores without explicit weighting which is a very broad (and hard) problem that can have lots of applications by itself.

Thanks in advance and congratulations for the great research and library (and HDBSCAN, too!)

[lmcinnes]

So, first of all, this approach doesn't solve all the problems, particularly relative weighting between metrics, but it gives some useful steps in that direction.

As to your question, the goal would be to do the second case -- have a distance for 3 dimensional space, and a different distance for 2 dimensional space, and then combine them. The theory mechanics of it are that we generate fuzzy simplicial sets for each metric independently (and there is an automatic isomorphism between the zero simplices, or points, because we are implicitly working on the same underlying data). In fuzzy simplicial set land there is a natural way of combing them -- take the intersection of the two. Now you have a combined fuzzy simplicial set and you can embed as normal.

How to interpret this? If we want to keep things simple we can only consider the 1-skeleton of the fuzzy simplicial set (which we will do for computational reasons anyway). We can simply view that as a weighted graph with the weights notionally being the probability that the edge exists. Each metric will give a different weighted graph on the same vertices -- these are different view of the data. The combined graph will simply be the graph over the same vertices where the probability of an edge existing is the probability of the edge existing in both graphs.

Does that make sense? I can explain further, but perhaps this is enough to get the relevant ideas communicated.

[Vslira]

That makes perfect sense, actually! The "relative weights" problem is then taken care of by combining the probabilities (as an AND) on all graphs. Pretty elegant, even if it doesn't solve the problem in general.

Thanks!

[atarashansky]

If I had fuzzy simplicial sets for two different metrics and I wanted to combine them, should I take their union or intersection? I guess another way of asking this question is: Intuitively, how does the choice of the set_op_mix_ratio parameter affect the resulting projection?

[lmcinnes]

I believe for most cases you are interested in the intersection -- essentially you want two points to be considered close if they are close in both senses of distance. It could be possible that you are interested in a more forgiving approach, where you can consider points close if they are close in either metric, but this will definitely tend to glue things together a lot more and potentially create a big ball. It does definitely depend on your use case and what exactly you think makes the most sense for that situation.