5
$\begingroup$

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?


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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .