Fermat Distance: learning with manifolds and probability densities

When we are working with high dimensional data, typically we have to deal with the problem of defining a distance between points that can take into account its underlying structure. For example, many tasks in machine learning require a notion of distance or similarity between points, such as clustering, classification, dimensionality reduction, and deep learning. This distance has to capture as much relevant information as possible in order to give better results.

For this scenario, a good hypothesis is that the dataset is constituted by a set of samples with unknown density distribution which is supported on a lower dimensional manifold. In some cases, this can be corroborated and there are a few degrees of freedom that parametrize the points in the dataset. Even more, there are theoretical results that show that independently of the dimension of the space, points are near to some lower dimensional structure.

Tipically, real data is modeled as a collection of points living in a manifold with a intrinsic dimension lower than the ambient space.

Naturally, The number of points needed to fill a $D$ dimensional set scales exponentially in the dimension $D$ of the space, making impossible for a finite set of points to do that task. More technically, the Johnson-Linderstraus Lemma claims that given a dataset of $n$ points, there always exists a projection of the points in $\mathbb{R}^d$ with $d = \mathcal O (\log (n / \varepsilon^2))$ that preserves the Euclidean distance between all pairs of points with an error smaller than $\varepsilon$ , independently of the dimension of the dataset.

The Fermat distance

For the sake of the explanation, let consider first that we know the density $f : \mathcal{M} \mapsto \mathbb{R}_{\geq 0}$ , where $\mathcal{M}$ is a $d$ -dimensional manifold embedded in $\mathbb{R}^D$ . As previously mentioned, typically we have $d \ll D$ but this is not a restricted condition. On $\mathbb{R}^D$ we have defined some distance, for example, the Euclidean distance $\ell(x, y) = \| x-y \|_2$ . Given two points $p, q \in \mathcal{M}$ and a parameter $\beta \geq 1$ we define the Fermat distance between $p$ and $q$ as

$\begin{equation*} \mathcal D_\beta (x, y) = \inf_{\gamma \subset \mathcal M} \int_\gamma \frac{1}{f^\beta} d\ell \label{eq:fermat_macro} \end{equation*}$

where the minimization carried over all rectifiable curves $\gamma$ that start at $p$ and end at $q$ .

Given the input distance $\ell (\cdot, \cdot)$ , $\mathcal D_\beta (\cdot, \cdot)$ defines a (new) distance that takes into consideration both manifold and density.
For $\beta = 1$ , the Fermat distance is identical to the length of the geodesic on $\mathcal M$ , recovering the Isomap distance.
For higher values of $\beta$ , paths that cross for regions with low density are disfavorable.

Let’s considerer the example of a bimodal distribution supported on the lower dimensional manifold $\mathcal{M}$ , with modes in points $x_1$ and $x_2$ and with different dispersions (see image below). If we consider the point $\tilde x$ on the manifold, both Euclidean and geodesic distance will make $\tilde x$ nearer to $x_1$ than to $x_2$ . On the contrary, since the density $f$ takes lower values in every path $\gamma$ that conects $x_1$ with $\tilde x$ , the Fermat distance $\mathcal D (x_1, \tilde x)$ will be higher than $\mathcal D_\beta (x_1, \tilde x)$ for a choice of $\beta$ large enough.

On the other hand, for $\beta > 1$ the optimal path $\gamma^*$ that realizes the Fermat distance is most likely to cross regions with high density. In that way, we can think $\gamma^*$ as the most likely continuous transformation of $p$ to $q$ .

The Fermat distance is defined as an optimization problem which selects a path minimizing some functional. As its name suggests, the definition of the Fermat distance resembles the optical principle in optics.

In optics, the path follows by light in a media is a minimizer of the optical path lenght, which is the path integral of the refractive index of the media. This least action formulation of the geometric optic is known as Fermat’s Principle.

The refractive index is related to the speed of light in the media. More specific, if $c$ is the speed of light in vacuum and $v$ is the speed of light in the media, the refractive index is defined as $n = c/v$ . Then, the path integral

$\int_\gamma n(x) d\ell$

represents the time that requires to a ray of light to go through the path given by $\gamma$ . Regions with lower refractive index represent regions where light can move faster. In that way, the role of the refractive index in the definition of the Fermat distance is played by the inverse power of the density $1/f^\beta$ : the light moves faster in regions with high density.

How to estimate the Fermat distance?

Assuming that we have knowledge of the density $f$ and its support $\mathcal{M}$ , finding the optimal path $\gamma$ that minimizes the Fermat distance could be computationally expensive. However, in a real case scenario we have the information of $f$ via some finite set of samples $\mathbb X_n = \{ x_1, x_2, \ldots, x_n \}$ with common density $f$ . One approach could be to first estimate the density to estimate in a second step the Fermat distance.

However, let see how it is possible to estimate the Fermat distance directly using mathematical results in percolation theory. Given two points $p$ and $q$ and a sequence $(y_1, \ldots, y_k)$ of points such that $y_i \in \mathbb X_n$ for all $i = 1, 2, \ldots, k$ , with $k > 1$ , we say that $(y_1 , \ldots, y_k)$ is a path from $p$ to $q$ if $y_1$ and $y_k$ are the nearest points in $\mathbb X_n$ to $x$ and $y$ , respectelly. Given a parameter $\alpha \geq 1$ , the Fermat distance estimator is defined as

$\begin{align*} D_{\mathbb X_n, \alpha}(p, q)=\min \bigg \{ & \sum_{i=1}^{k-1} \| y_{i+1}-y_i \|^\alpha: (y_1, \dots, y_k) \text{ is a} \\ &\text{path from $p$ to $q$} \bigg \} . \end{align*}$

Starting in $p$ , this represents the minimum cost of going to $q$ when the local cost from moving from one point $x$ to another $y$ is $\| x - y \|^\alpha$ .

At a first glance, the relationship between the Fermat distance and its estimator is not immediate. However, it can be proved that if we rescale adequately $D_{\mathbb X_n, \alpha}(p, q)$ and take the limit as the number of samples $n$ goes to infinity then

$\begin{equation*} \lim_{n \to \infty} \, n^{\beta} \, D_{\mathbb X_n, \alpha} (p, q) = \mu \, \mathcal D_\beta (p, q), \end{equation*}$

where the parameter $\alpha$ and $\beta$ satisfies the relation $\beta = (\alpha -1 )/d$ , with $d$ the intrinsic dimension of the manifold and $\mu$ some constant that depends on $\alpha$ and $d$ .

To better understand this result, let’s consider the simple case where $\alpha=2$ and the contribution of each $\| y_{i+1}-y_i \|^\alpha$ is proportional to the area of a circle with center $y_i$ and radious $\| y_{i+1}-y_i \|$ . Then, the Fermat distance estimator is proportional to the total area of the shaded region in the figure above. Consequently, a path that goes for regions with high density will have lower cost, as the Fermat distance does.

Algorithmic Implementation

The minimization between all possible paths that connect two given points can be treated as a shortest path problem in the graph with nodes in the points $\mathbb X_n$ and where the weight of the edge between two points $x$ and $y$ is $\| x -y \|^\alpha$ . The faster method to compute $D_{\mathbb X_n, \alpha}$ is the Floyd-Warshall algorithm, which requires $\mathcal O (n^3)$ operations (a lot!). However, we can perform the two following relaxation of the problem

Since the power $\alpha$ discourages large distances between consecutive points of the optimal path, we can restrict the search of paths $(q_1, \ldots, q_k)$ where each $q_i$ is $k$ -nearest neighbour of $q_{i+1}$ . Even more, if we choose $k = \mathcal O (\log (n / \varepsilon))$ then with probability at least $1-\varepsilon$ the estimator of the Fermat distance doesn’t change. In such case, Dijkstra algorithm requires $\mathcal (k n^2 \log n)$ operations.

Furthermore, we can consider a subset of points $z_1, z_2, \ldots, z_m \in \mathbb X_n,$ which we are going to call the landmarks, selected with some rule, for example, a random sample of size $m$ from $\mathbb X_n$ . Then, we compute the shortest path from each of the $z_i$ to the rest of the $n$ points in $\mathcal O (k m n \log n)$ operations using Dijsktra algortihm. Finally, it is possible to bound the Fermat distance $D_{\mathbb X_n, \alpha}(p, q)$ between all $p$ and $q$ as

$\begin{align*} D_{\mathbb X_n , \alpha}(p,q) \, &\geq \, \max_{i} \bigg | D_{\mathbb X_n , \alpha}(p,z_i) - D_{\mathbb X_n , \alpha}(z_i,q) \bigg | \\ D_{\mathbb X_n , \alpha}(p,q) \,&\leq\, \min_{i} \bigg \{ D_{\mathbb X_n , \alpha}(p,z_i) + D_{\mathbb X_n , \alpha}(z_i,q) \bigg \}. \end{align*}$

If both lower and upper bound are the same, we have the exact value of $D_{\mathbb X_n, \alpha}(p,q)$ , but if not we have some inteval where the real value lies.

An implementation in Python of all these variants can be found in www.aristas.com.ar/fermat

References

Weighted Geodesic Distance Following Fermat’s Principle
F. Sapienza, P. Groisman, M. Jonckheere
6th International Conference on Learning Representations (ICLR), 2018.

Nonhomogeneous Euclidean first-passage percolation and distance learning
P. Groisman, M. Jonckheere, F. Sapienza

Fermat Distance: learning with manifolds and probability densities

The Fermat distance

How to estimate the Fermat distance?

Algorithmic Implementation

References

Read Next

Catamarca, the Most Beautiful

Hi

Recent Posts

Catamarca, the Most Beautiful

Fermat Distance: learning with manifolds and probability densities

Write Me

Fermat Distance: learning with manifolds and probability densities

The Fermat distance

How to estimate the Fermat distance?

Algorithmic Implementation

References

Read Next

Catamarca, the Most Beautiful

Sliding Sidebar

Hi

Follow me

Recent Posts

Catamarca, the Most Beautiful

Fermat Distance: learning with manifolds and probability densities

Write Me