# Divergence between Probability Distributions from Samples via the Chamfer Distance

Suppose I have two probability distributions $$P$$ and $$Q$$. I want to compute a divergence/distance between them. I do not have access to their densities, but I can draw samples $$x\in D \subset \mathbb{R}^m$$ from them. Let $$X = \{x_i\mid x_i\sim P\}_{i=1}^n$$ and $$Y = \{y_j\mid y_j\sim Q\}_{j=1}^n$$. Ideally, I'd like to be able to compute this fairly quickly as well.

There are a few simple candidates: the Earth Mover's (Wasserstein) distance (EMD) is good, but this one is a bit costly. I can use kernel density estimation, and then estimate the KL divergence with a Monte Carlo estimator (e.g., here or here), or fit a probability distribution to $$X$$ and $$Y$$ (e.g. Gaussian or GMM), and then come up with a distance (e.g. based on parameters or analytic KL divergences say), but simple distributions don't fit well, this has too many parameters I need to tweak, and it seems unnecessarily complex. (The Monte Carlo KL estimates didn't perform well either; I'd like to avoid density estimation). There's also the Hausdorff distance which has some probabilistic connections but depends wildly on $$n$$. I haven't yet explored kernelized maximum mean discrepancy much, which seems promising though.

However, I have seen quite a few papers lately use the Chamfer Distance (it is not a metric, but it is some form of divergence nonetheless) as an efficient (yet still quite effective in practice) substitute for the EMD. (e.g. see [1], [2]). It is written $$\mathcal{D}_C[X,Y] = \frac{1}{|X|} \sum_{x\in X} \min_{y\in Y} d(x,y) + \frac{1}{|Y|} \sum_{y\in Y} \min_{x\in X} d(x,y)$$ where $$d:D\times D\rightarrow\mathbb{R}^+$$ is some distance metric, e.g. $$d(x,y)=||x-y||_2^2$$. Basically, for each point in one set, we get the closest point in the other set, and compute the distance between them - summing the result over the set, and then doing the same for the other set. Sometimes the normalizing fractions are left out.

My questions:

1. Is there a probabilistic connection to using this on samples? E.g., for a particular $$d$$, is there a well-known continuous divergence that this approximates/bounds?

2. Can $$\mathcal{D}_C$$ be used as a reasonable (pseudo)-distance between $$P$$ and $$Q$$? For example, can we guarantee that, as $$n\rightarrow\infty$$, if $$D_C[X,Y]\rightarrow 0$$, then, say, the KL or JS-divergence must also shrink to zero or be bounded by it? What sort of assumptions would be needed for this?

• Have you found any answer? Jun 26, 2020 at 20:14
• Note that d(x,y)=||x-y||^2 is not a distance metric. Usually one requires that the triangle inequality be satisfied for that. Sep 27, 2021 at 22:09

## Question 1: Continuous probabilistic Extension

Here's a possible continuous extension of $$\mathcal D_C$$ stated in terms of probability theory

$$\mathfrak{D}_C[P,Q]=\mathbb{E}_{x\sim P}\left[ \inf_{y\in\operatorname{supp} Q} d(x,y)\right] + \mathbb{E}_{x\sim Q}\left[ \inf_{y\in\operatorname{supp} P} d(x,y)\right]$$

where $$\mathbb E_{x\sim P}$$ is expectation with $$P$$-distributed $$x$$ and $$\operatorname{supp} P$$ is the support of the probability measure $$P$$.

It is unclear to me how easily one can estimate this via sampling, but focusing on the first term we can get some intuition. Let $$\{x_1,\ldots,x_n\}$$ and $$\{y_1,\ldots,y_m\}$$ be i.i.d. samples of $$P$$ and $$Q$$ (resp.) and note that since $$d(x,y)\geq 0$$ we have

$$\mathbb{E}_{x\sim P}\left[ \inf_{y\in\operatorname{supp} Q} d(x,y)\right] \leq \mathbb{E}_{x\sim P}\left[ \min_j d(x,y_j)\right] \approx \frac{1}{n}\sum_{i=1}^n \min_j d(x_i,y_j).$$

## Question 2a: Is $$\mathcal D_C[X,Y]$$ a (psuedo)-metric?

No. The Chamfer distance you wrote with $$d(x,y)=\|x-y\|^2$$ is neither a metric or pseudo-metric because it does not satisfy the triangle inequality. This is mentioned in your second reference (page 4 where Chamfer distance is introduced) but for a concrete counter-example consider $$A=\{0\}$$, $$B=\{1,2\}$$, and $$C=\{3\}$$. Then $$\mathcal D_C[A,C]=3^2+3^2=18$$ but $$\mathcal D_C[A,B]=\mathcal D_C[B,C]=1^2+\tfrac{1}{2}(1^2+2^2)=3.5$$. This counter-example also works if you use $$d(x,y)=\|x-y\|$$.

## Question 2b: $$\mathcal D_C[X,Y] \to 0$$ implies KL or JS divergence $$\to 0$$?

No. Let $$\Omega\subseteq\mathbb{R}^m$$ be the unit ball and consider any two probability distributions $$P\neq Q$$ with support $$\Omega$$. Let $$X_n=\{x_1,\ldots,x_n\}$$ and $$Y_n=\{y_1,\ldots,y_n\}$$ be i.i.d. samples from $$P$$ and $$Q$$ respectively. Let $$H$$ denote the Hausdorff distance and note that since $$X_n\subseteq \Omega$$ we have

$$H(\Omega,X_n) = \sup_{p\in \Omega} \min_{x\in X_n} \|p-x\|.$$

Note that as $$n\to\infty$$ we have $$H(\Omega,X_n)\to 0$$ almost surely (if not, then there would be some disk $$D\subseteq \Omega$$ which didn't receive any samples, but that would happen with probability $$(1-P(D))^n$$ which vanishes as $$n\to\infty$$ since $$P(D)>0$$). Applying the same argument to $$Y_n$$ we have that (almost surely) for any $$0<\delta<\tfrac{1}{2}$$ we can choose an $$N$$ so that $$H(\Omega,X_N),H(\Omega,Y_N)<\delta$$. By triangle inequality we have

$$H(X_N,Y_N)\leq H(X_N,\Omega) + H(\Omega, Y_N) < 2\delta$$

which implies that

$$\forall x\in X_N\quad \min_{y\in Y_N} \|x-y\|<2\delta$$ $$\forall y\in Y_N\quad \min_{x\in X_N} \|x-y\|<2\delta$$

Since $$d(x,y)=\|x-y\|^2$$ in the OP and $$2\delta<1$$ we have,

$$\forall x\in X_N\quad \min_{y\in Y_N} d(x,y)<2\delta$$ $$\forall y\in Y_N\quad \min_{x\in X_N} d(x,y)<2\delta$$

Thus,

$$\mathcal D_C[X_N,Y_N] < \frac{1}{N}\sum_{x\in X_N} 2\delta + \frac{1}{N}\sum_{y\in Y_N} 2\delta = 4\delta$$

Since $$0<\delta<\tfrac{1}{2}$$ was arbitrary, we can conclude that $$\lim_{n\to\infty} \mathcal D_C[X_n,Y_n]=0$$ (almost surely). However, since $$P\neq Q$$ were general measures with support $$\Omega$$, they in general have nonzero KL or JS divergence.