lmcinnes / lmcinnes/pynndescent
TSSS missing a factor of 2
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 970
- Forks
- 107
- PR merge metrics
- No merged PRs in 30d
Description
This was reported to me at https://github.com/jlmelville/rnndescent/issues/8 but would also affect pynndescent, which is unsurprising as I directly converted the equation from here into C++.
Equation 7 of the TS-SS equation in the original paper ([PDF](https://www.researchgate.net/profile/Arash-Heidarian/publication/303513110_A_Hybrid_Geometric_Approach_for_Measuring_Similarity_Level_Among_Documents_and_Document_Clustering/links/5da389b592851c6b4bd33f63/A-Hybrid-Geometric-Approach-for-Measuring-Similarity-Level-Among-Documents-and-Document-Clustering.pdf)), written in terms of degrees, has a denominator of 720, which would convert to 4pi in radians (the pi would cancel). As can be seen at:
https://github.com/lmcinnes/pynndescent/blob/d99a821b0ed27cf97af16b688568be9838c1e397/pynndescent/distances.py#L518-L520
there's only a division of 2 that shows up in the calculation of the return value.
I would volunteer to write a PR and update any affected test, but I would like to to use that paper as a means of confirming my understanding of the equations, as there are some partial numerical results in it. Unfortunately, I quickly got fed up trying to back-convert the vectors in the figures to plausible 2D descriptors (e.g. how can A and B in figure 1a be vectors of length 6, with an angle of 30 degrees between them, but a Euclidean distance of 2). Obviously this doesn't affect the returned neighbors but it could have a (small) effect for anything that used the distances downstream, like UMAP.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with pynndescent/distances.py at lines 518-520 and compare the TSSS calculation with Equation 7 of the linked paper, including its degree-to-radian conversion. Confirm the factor against the paper's partial numerical results, then update the affected test and verify that the corrected distance remains consistent with expected neighbors.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- data, search
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100