What is the importance of the log2(k) for calculating sigma?

[CRISTIANJULIOCESAR]

To find the sigma using log2(k), in this video (1:11:00), it is mentioned that log2(k) has beneficial properties but i didn't find that information in the original article. This is the video: https://www.youtube.com/watch?v=G9s3cE8TNZo&t=4514s&ab_channel=MachineLearningDojowithTimScarfe

I fully understand that a binary search is used to satisfy an equation to find sigma, but I do not understand the reason for log2(k), was it empirical as she say in the video due to experiments carried out by the original authors??

Thank you in advance :)

[jlmelville]

I am sure I also asked @lmcinnes this several years ago, but I searched my emails and can't find an answer. However, my recollection was that the answer was that it is empirical (although bear in mind I might simply have imagined this).

There is a connection the entropic affinity calculation in t-SNE, where the Shannon entropy of the input probabilities is calibrated to reproduce the log of the input perplexity. I suspect it is in analogy to that procedure. The important thing is to do some kind of normalization step to get the different density around each item in the dataset on a similar scale.

[CRISTIANJULIOCESAR]

I agree, the UMAP approach uses a modified way of finding sigma like the perplexity of tSNE.

I tried myself to change the log n to see how afectes to the 2D embedding, it seams log3,4,5 scales the value sigma gets to a smaller values (disconnecting "real" dense of points) and log2(K) work just fine for the embedding. Higher n's values of the logn it reach faster (less iteration) the low cross entropy values but with a shattered clusters.

I used this code for the implementation of UMAP from scratch: https://morioh.com/p/884822e1fbd6 to see that.

and yes, normalization is important to take into account dense regions for computing smoothed distances (a different approach of a an adaptive kernel such as PHATE). But it seems that log2 works just fine. At least now have some idea of how to explain the reason of this log2.

Thank you @jlmelville