I am considering a number of experiments using Approximate Bayesian Computation. In most of the literature I see reference to a metric function to calculate distance between observed and simulated summary statistics.

My intuition would tell me that there is no reason that this distance function need be a true metric, i.e satisfying the four properties usually associated with a metric, in particular symmetry and the triangle inequality.

Is there any argument or proof either way on this matter?


Short answer

Not all the axioms of a metric are needed (see below). However I can't think of any published examples using a distance which isn't closely based on a metric.

Metrics recap

The axioms of a metric are:

  1. $d(y,y') \geq 0$ (non-negativity)
  2. $d(y,y') = 0$ iff $y=y'$ (identifiability)
  3. $d(y,y') = d(y',y)$ (symmetry)
  4. $d(y,y') \leq d(y,z) + d(z,y')$ (triangle inequality)

ABC recap

ABC bases acceptance of simulated (parameter, data) pairs $(\theta, y)$ on the distance $d(y,y_0)$ where $y_0$ is the observed data. Small distance values are more likely to be accepted. This answer concentrates on the simple scheme which accepts if $d$ is below a threshold $\epsilon$.

Necessity of the axioms in ABC

  • Non-negativity. This axiom is assumed in all implementations of ABC I've seen.
  • Identifiability. ABC produces $\theta$ samples from the exact posterior if acceptance only occurs for $y=y_0$. If there are multiple solutions to $d(y,y_0)=0$ this acceptance rule cannot be attained, which seems like a major deficiency. In particular a limit of increasingly stringent acceptance rules would not produce sampling targets converging on the true posterior. So identifiability seems essential.
  • Symmetry. This clearly isn't essential as ABC only uses $d(y,y_0)$. We could quite easily take $d(y_0,y) \neq d(y,y_0)$ without affecting the algorithm.
  • Triangle inequality. This is also not needed. For example suppose $y \in \mathbb{R}$ and $d_1(y,y')=|y-y'|$ (a metric). Then $d_2(y,y')=(y-y')^2$ breaks the triangle inequality (e.g. consider $y=0, z=1, y'=2$) but produces the same ABC acceptance regions as $d_1$ for appropriately chosen acceptance thresholds.

Some sufficient conditions for ABC distances

In the appendix of a preprint I make a case for some conditions on ABC distance functions which are sufficient for the ABC target distribution to converge to the posterior. Other conditions could probably be reached by different arguments though! (My argument is a by-product of some theory I needed for ABC-SMC algorithms.)

The argument is based on the acceptance regions $A_t=\{ y | d(y,y_0) \leq \epsilon_t \}$ for any sequence $\epsilon_1 > \epsilon_2 > \ldots$ converging on zero. The conditions are (omitting some technicalities):

  1. The Lebesgue measure $|A_t|$ converges to 0 as $t \to \infty$.
  2. The sets $A_t$ have bounded eccentricity. Essentially under projection to any lower dimensional space, the Lebesgue measure of $A_t$ still converges to zero.

Condition 1 ensures that the acceptance region shrinks to a vanishingly small region around the observations. Condition 2 avoids a limiting acceptance region in which some but not all components of $y$ match those of $y_0$.

  • $\begingroup$ Thanks Dennis for your very thorough answer. I will have a read of the paper shortly. It was the final 2 axioms that I felt intuitively need not be satisfied in the context of ABC and you backing that up for me is great. $\endgroup$ – jamieRowen May 10 '16 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.