Abstract
Density-based distances (DBDs) offer an elegant solution to the problem of metric learning. By defining a Riemannian metric which increases with decreasing probability density, shortest paths naturally follow the data manifold and points are clustered according to the modes of the data. We show that existing methods to estimate Fermat distances, a particular choice of DBD, suffer from poor convergence in both low and high dimensions due to i) inaccurate density estimates and ii) reliance on graph-based paths which are increasingly rough in high dimensions. To address these issues, we propose learning the densities using a normalizing flow, a generative model with tractable density estimation, and employing a smooth relaxation method using a score model initialized from a graph-based proposal. Additionally, we introduce a dimension-adapted Fermat distance that exhibits more intuitive behavior when scaled to high dimensions and offers better numerical properties. Our work paves the way for practical use of density-based distances, especially in high-dimensional spaces.
Introduction
In many machine learning tasks, determining the distance between data points is a fundamental requirement. While Euclidean distance is the standard default, it often fails when data resides on a curved manifold. For instance, consider two points on opposite sides of a spiral: a straight-line Euclidean path cuts through regions where no data exists, failing to capture the intrinsic structure of the dataset.
Fermat distances, a class of density-based distances, address this by making the "cost" of travel inversely proportional to the data density. In this framework, paths are incentivized to stay within high-density regions, effectively following the "shape" of the data, much like light follows the path of least time through a lens.
Limitations of Traditional Estimators
Historically, Fermat distances have relied on $k$-nearest neighbor ($k$-NN) graphs to estimate paths. However, these estimators face significant hurdles:
- Poor Convergence: They require an impractical amount of data to produce accurate distance estimates.
- The Curse of Dimensionality: As dimensionality increases, data becomes sparse. Graph-based paths become jagged, inaccurate, and numerically unstable, often clipping through low-density regions.
Methodology: Modernizing Fermat Distances
This research proposes a three-pronged approach to make density-based metrics practical for modern high-dimensional machine learning.
1. Normalizing Flows for Density Estimation
Instead of relying on local neighbor counts, the authors utilize Normalizing Flows (NFs). NFs learn a smooth, continuous probability distribution $p(x)$ of the data. This provides far more accurate density estimates for initial pathfinding than traditional $k$-NN methods, which the authors identified as the primary bottleneck in previous implementations.
2. Score-Based Path Relaxation
To eliminate the "jaggedness" inherent in graph-based paths, the authors introduce a relaxation method. By reparameterizing the geodesic equation to maintain constant Euclidean speed, they achieve numerical stability. They employ Score Matching to learn the gradient of the log-density ($s(x) = \nabla \log p(x)$), which serves as a guide to pull the path toward high-density regions during optimization. Interestingly, the authors found that training a dedicated score model provides the necessary smoothness that differentiating an NF often lacks.
3. Dimension-Adapted Scaling
A critical contribution is the introduction of a scaling parameter $\beta = 1/D$, where $D$ is the dimension. The authors demonstrate that without this scaling, geodesics in high dimensions behave counter-intuitively, taking extreme detours that degrade the metric's utility.
Key Results
The proposed method was evaluated on synthetic 2D datasets (Spirals, GMMs) and the latent space of an MNIST autoencoder.
- Faster Convergence: On 2D data, the NF-based approach reached accuracy levels with 1,000 samples that traditional power-weighted graph methods couldn't reach even with 100,000 samples.
- Robustness to Dimension: While graph-based error explodes as dimensions increase toward 25, the score-based relaxation method remains robust, effectively "beating" the curse of dimensionality.
- Qualitative Superiority: Visualizations confirm that the learned paths are smooth and semantically meaningful, capturing transitions between data modes (e.g., morphing a '3' into an '8' in latent space) more naturally than previous techniques.
Conclusion
By replacing traditional graph-based estimators with deep generative models and score matching, this work transforms Fermat distances from a theoretical curiosity into a practical tool for manifold learning. The combination of Normalizing Flows for density and Score Matching for path refinement provides a stable, scalable framework for learning distances that truly respect the underlying structure of data.
Summary updated