PaperlayerView exact revision on arXiv

Source-linked AI summary

On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods

Anne-Marie Lyne, Mark Girolami, Yves Atchadé, Heiko Strathmann, Daniel Simpson

arXiv:1306.4032v4stat.MEstat.COstat.ML

TL;DR

Doubly-intractable posteriors make standard MCMC difficult because the likelihood’s parameter-dependent normalising term cannot be computed. The paper studies pseudo-marginal inference using unbiased likelihood estimates formed by stochastic truncation of a series. It describes sign correction for potentially negative estimates to preserve posterior expectations.

  • Problem

    Doubly-intractable models have an intractable likelihood normalising term, limiting standard MCMC inference, and no general method is available for all such posteriors.

    Source: §1 · p. 2

  • Method

    The paper estimates the intractable likelihood through an infinite series whose terms are estimated unbiasedly and Russian Roulette sampling finitely truncates the series within pseudo-marginal MCMC.

    Source: §1 · p. 2, §3 · p. 6, §5.2 · p. 11

  • Results

    Sign correction allows pseudo-marginal MCMC to use potentially negative unbiased estimates while preserving expectations with respect to the posterior.

    Source: §8 · p. 21

  • Takeaways & Limitations

    The reviewed and developed pseudo-marginal approach does not require exact simulation from the underlying model, but does require unbiased estimates of the inverse normalising term.

    Source: §8 · p. 20

    For unbounded likelihood functions, unbiased estimates are not guaranteed to be positive, preventing their direct use in the pseudo-marginal framework.

    Source: §3.2 · p. 7

Abstract

from arXiv · show

A large number of statistical models are "doubly-intractable": the likelihood normalising term, which is a function of the model parameters, is intractable, as well as the marginal likelihood (model evidence). This means that standard inference techniques to sample from the posterior, such as Markov chain Monte Carlo (MCMC), cannot be used. Examples include, but are not confined to, massive Gaussian Markov random fields, autologistic models and Exponential random graph models. A number of approximate schemes based on MCMC techniques, Approximate Bayesian computation (ABC) or analytic approximations to the posterior have been suggested, and these are reviewed here. Exact MCMC schemes, which can be applied to a subset of doubly-intractable distributions, have also been developed and are described in this paper. As yet, no general method exists which can be applied to all classes of models with doubly-intractable posteriors. In addition, taking inspiration from the Physics literature, we study an alternative method based on representing the intractable likelihood as an infinite series. Unbiased estimates of the likelihood can then be obtained by finite time stochastic truncation of the series via Russian Roulette sampling, although the estimates are not necessarily positive. Results from the Quantum Chromodynamics literature are exploited to allow the use of possibly negative estimates in a pseudo-marginal MCMC scheme such that expectations with respect to the posterior distribution are preserved. The methodology is reviewed on well-known examples such as the parameters in Ising models, the posterior for Fisher-Bingham distributions on the $d$-Sphere and a large-scale Gaussian Markov Random Field model describing the Ozone Column data. This leads to a critical assessment of the strengths and weaknesses of the methodology with pointers to ongoing research.

1. INTRODUCTION

Doubly-intractable posteriors pose a challenge for MCMC because the data density’s parameter-dependent normalising term cannot be computed. The paper reviews existing approaches and studies pseudo-marginal inference using unbiased estimates of the intractable likelihood.

1. INTRODUCTION

  • The likelihood normalising term Z(θ) can be unavailable because it is nonanalytic or cannot be computed with finite resources, obstructing posterior inference by MCMC.The paper focuses on doubly-intractable distributions, where this parameter-dependent term is also intractable.Source: §1 · p. 2
  • The paper represents the intractable likelihood as an infinite series and uses Russian Roulette truncation to obtain unbiased estimates with finitely many terms.The resulting estimates are used in a pseudo-marginal MCMC scheme.Source: §1 · p. 2
  • The paper reviews approximate and exact inference methods, then studies an alternative pseudo-marginal approach and evaluates it on Ising, Fisher–Bingham, and large-scale Gaussian Markov random field models.The experiments include the Ozone Column data set.Source: §1 · p. 2

2. INFERENCE METHODS FOR DOUBLY-INTRACTABLE DISTRIBUTIONS

The section surveys approximate and exact approaches to doubly-intractable posteriors, outlining their mechanisms and the conditions that limit their use.

2.1 Approximate Bayesian Inference

  • Approximate Bayesian inference includes pseudo-likelihood, ABC, shadow priors, Monte Carlo approximations, and deterministic approximations such as INLA, each with method-specific trade-offs.Pseudo-likelihood can scale well but may yield biased inference; ABC does not sample from the exact posterior, while INLA relies on applicable assumptions and standard software.Source: §2.1 · pp. 3–4
  • Shadow priors remove constrained-data dependence from the conditional posterior, but δ updates remain and the method is useful only when their computational burden is lower.Updating δ is reduced to d one-dimensional problems; an approximate version can ignore the normalising constant, sometimes with little impact on inference.Source: §2.1 · p. 4
  • Consistent Monte Carlo approximations avoid sampling from the model likelihood, but their grid requirements grow exponentially with dimension and require substantial tuning.Their approximation quality depends on the number and location of grid points.Source: §2.1 · p. 4

2.2.1 Introducing auxiliary variables

  • Walker’s auxiliary-variable RJMCMC scheme can handle bounded unnormalised densities, but requires suitable bounds and data on a bounded interval.Finding tight bounds is difficult and their choice affects sampling efficiency; unbounded data support prevents the construction’s geometric series from converging.Source: §2.2.1 · p. 5
  • The auxiliary-variable construction introduces ν, k, and s^(k), then samples their joint density to recover the data distribution while avoiding the intractable normalising term.Integrating out ν and s^(k) and summing over k returns the data distribution.Source: §2.2.1 · p. 5

2.3 Valid Metropolis–Hastings-Type Transition Kernels

  • Møller et al.’s method and the Exchange algorithm cancel intractable normalising terms in the acceptance ratio, but require exact likelihood sampling, which can be prohibitively slow or impossible.The Exchange algorithm targets the exact posterior; perfect sampling is cited as one way to sample from the likelihood.Source: §2.3 · pp. 5–6

3. AN ALTERNATIVE APPROACH USING PSEUDO-MARGINAL MCMC

The section develops pseudo-marginal MCMC using unbiased likelihood estimates, first for exact posterior sampling and then for likelihoods represented by infinite series. Russian Roulette truncation preserves unbiasedness, while possibly negative estimates require a signed-estimate treatment.

3. AN ALTERNATIVE APPROACH USING PSEUDO-MARGINAL MCMC

  • An unbiased, positive target-density estimate in pseudo-marginal MCMC yields a chain whose parameter marginal is the exact posterior.The likelihood estimator is propagated forward between proposals.Source: §3 · p. 6

3.1 Proposed Methodology

  • Russian Roulette truncates an infinite likelihood series in finite time while retaining an unbiased estimate; the prior is assumed tractable.The proposed series is finite almost surely and has finite expectation.Source: §3.1 · p. 7

3.2 The Sign Problem

  • For unbounded functions, unbiased estimates are not guaranteed to be positive, preventing their direct use in the pseudo-marginal framework.For bounded functions, the procedure can proceed if the bound supports efficient sampling.Source: §3.2 · p. 7
  • Weighting expectations by the estimate's sign allows MCMC to compute posterior integrals from estimates that may be negative.The sign and absolute value of the estimate are used in this construction.Source: §3.2 · p. 7
  • The resulting Monte Carlo estimate of a posterior expectation is consistent but biased, and the procedure saves the sign of accepted estimates.The method permits unbiased likelihood estimators that occasionally return negative values.Source: §3.2 · p. 8

4. PSEUDO-MARGINAL MCMC FOR DOUBLY-INTRACTABLE DISTRIBUTIONS

The method represents the intractable likelihood through a series whose terms can be estimated unbiasedly, then truncates it stochastically. This yields an unbiased estimate that may be negative, which the proposed MCMC scheme accommodates while preserving posterior expectations.

4. PSEUDO-MARGINAL MCMC FOR DOUBLY-INTRACTABLE DISTRIBUTIONS

  • Directly estimating the reciprocal normalising constant with an instrumental density requires sampling from the likelihood, and the estimator’s variance depends strongly on that density.If likelihood sampling is available, the Exchange algorithm can be implemented instead.Source: §4 · p. 8
  • Unbiased estimates of the normalising constant feed a series representation and unbiased stochastic truncation, producing an estimate that may be negative but supports posterior-preserving MCMC.The chain targets a distribution proportional to the estimate’s absolute value, then computes Monte Carlo estimates for the desired posterior.Source: §4 · pp. 8–9

4.1 Geometric Series Estimator

  • The geometric-series estimator requires a convergence condition that is difficult to guarantee without knowing the normalising constant; loose upper bounds can make convergence slow.A pilot run can guide a conservative choice, but poorly characterised estimates may still introduce approximation into the chain.Source: §4.1 · p. 10

4.2 Unbiased Estimators Using an Exponential Auxilliary Variable

  • An exponential auxiliary variable creates a joint distribution whose marginal over the auxiliary variable is the posterior, while an approximation to the normalising constant can improve series convergence.When the approximation is an upper bound, it also prevents alternating signs in the Taylor-series terms and reduces the impact of negative estimates.Source: §4.2 · p. 10

5. UNBIASED TRUNCATION OF INFINITE SUMS: RUSSIAN ROULETTE

The section describes unbiased ways to truncate an infinite series, especially Russian Roulette stopping-time truncation. In the MCMC scheme, an estimator-based correction preserves the desired posterior marginal, while truncation probabilities trade computation time against variance.

5.1 Single Term Weighted Truncation

  • Single-term weighted truncation draws an index k with probability q_k and returns φ_k(θ)/q_k, an unbiased estimate of the infinite sum.For a geometric series, a Poisson choice can yield infinite variance, whereas a geometric importance distribution has finite variance under conditions on its parameter.Source: §5.1 · p. 11

5.2 Russian Roulette

  • Russian Roulette truncates a series at a random stopping time and weights its partial sums to produce an unbiased estimate used in the MCMC scheme.A multiplicative correction to the Hastings ratio accounts for using an approximate rather than actual normalising term; the estimator’s unbiasedness gives the required marginal posterior.Source: §5.2 · pp. 11–12
  • For geometric-series Russian Roulette, variance is finite when q > φ(θ)^2; choosing probabilities near one lowers variance but increases computation time.Probabilities near zero reduce computation time but can produce very high, possibly infinite, variance.Source: §5.2 · pp. 11–12
  • Russian Roulette can debias a consistent estimator, but this alternative requires only consistency and offers no obvious way to reduce the chance of a negative estimate in pseudo-marginal MCMC.The construction writes the target as an infinite series of differences between successive approximations before truncation.Source: §5.2 · p. 12

6. EXPERIMENTAL EVALUATION

In the Ising and Fisher–Bingham examples, debiasing-series methods are compared with Exchange-based approaches. The reported estimates agree well, while Russian Roulette and Poisson truncation show favorable mixing or autocorrelation and effective sample size results in the reported comparisons.

6.1 Ising Lattice Spin Models

  • The 10 × 10 Ising comparison used debiased likelihood estimates with Russian Roulette or Poisson truncation alongside Exchange variants and a matrix-transfer MCMC chain.The analysis fixed α = 0, used a uniform prior on β ∈ [0,1], and compared five methods over 20,000 iterations.Source: §6.1 · p. 13
  • In this example, Russian Roulette and Poisson truncation outperform approximate and exact Exchange on autocorrelation functions (Figure 4) and effective sample size (Table 1), while remaining comparable to the exact implementation.Source: §6.1 · p. 13
  • On a 40 × 40 grid, estimates from Exchange and the proposed methodology agreed to the third or fourth decimal place; perfect sampling was no longer possible on a 60 × 60 grid, particularly near the critical value.Sequential Monte Carlo estimated Z_i(θ) at each iteration in the 40 × 40 Roulette implementation.Source: §6.1 · p. 14

6.2 The Fisher–Bingham Distribution on a Sphere

  • Importance sampling can provide unbiased normalising-constant estimates for applying the Exact-Approximate methodology to Fisher–Bingham posterior inference.The distribution’s normalising constant Z(λ) is intractable; Walker’s auxiliary-variable method was used as a comparison.Source: §6.2 · p. 15
  • The Fisher–Bingham experiment simulated 20 points at λ = [0,0,−2] and inferred λ3 while fixing λ1 = λ2 = 0.The method used uniform-sphere importance samples and a uniform prior on λ3 ∈ [−5,0].Source: §6.2 · p. 16
  • For Fisher–Bingham inference, posterior means and standard deviations agreed well, while Russian Roulette had superior effective sample size and autocorrelation; six of 10,000 estimates were negative.The comparison used Russian Roulette with geometric construction and Walker’s auxiliary-variable technique.Source: §6.2 · p. 16

7. THE LIMITS OF EXACT APPROXIMATE METHODS: THE OZONE DATA SET

The ozone example exposes practical limits of exact-approximate inference: estimating its likelihood entails difficult sparse linear solves and log-determinants, and the Russian Roulette chain failed to converge. Approximation and solver issues prevent exact targeting, while alternatives remain constrained.

7.1 The Model

  • For the 173,405 satellite ozone measurements, the analysis uses a stationary model with a Matérn SPDE precision matrix on a 196,002-vertex global triangulation.The sparse precision matrix supports low-memory storage and fast matrix-vector products; inference targets κ and τ after marginalising the latent field.Source: §7.1 · pp. 17–18

7.2 Likelihood Estimation and Russian Roulette

  • Russian Roulette truncation of a Maclaurin expansion estimates the likelihood from log-likelihood estimates, but lacking a lower bound for the log-likelihood compromises unbiasedness.The approach splits the exponential into factors near one, whose series converge rapidly; log-determinant estimation uses Monte Carlo estimates and numerical linear algebra.Source: §7.2 · pp. 18–19
  • Near-zero smallest eigenvalues of Q(κ) make sparse linear systems converge catastrophically slowly, so regularisation, preconditioning, and large solver iteration limits only partially address the problem.Full floating-point precision is unattainable for these solves, preventing the resulting chain from exactly targeting π(κ,τ|y).Source: §7.2 · p. 19
  • High log-determinant estimator variance slows exponential-series convergence and is amplified by Russian Roulette, motivating scaling-and-squaring.The series may require many terms to keep the overall estimate variance low.Source: §7.2 · p. 19

7.3 Results and Remarks on Approximate Schemes

  • The exact marginal posterior was relatively simple, but the Russian Roulette random-walk chain still failed; Figure 7 displays the exact marginals for log2(τ) and log2(κ).The authors considered an appropriately scaled random-walk Metropolis algorithm sufficient for exploring the exact density.Source: §7.3 · p. 19, Figure 7 · p. 20
  • The Russian Roulette chain failed to converge, showing catastrophic sticking and extremely high autocorrelation for the ozone posterior.The authors attribute this likely to log-likelihood approximation, slow log-determinant solver convergence, and bias from scaling.Source: §7.3 · pp. 19–20
  • Avoiding Russian Roulette or using an approximate transition kernel did not resolve catastrophic sticking, and sampling from the likelihood for the Exchange algorithm is infeasible.The authors suggest that further approximation, such as a composite-likelihood quasi-posterior, may be needed; subsampling methods are unavailable for this single-observation inference problem.Source: §7.3 · p. 20

8. DISCUSSION AND CONCLUSION

The paper presents pseudo-marginal MCMC with Russian Roulette estimates as applicable to a broad class of doubly-intractable distributions, subject to conditions on unbiased estimation and estimator signs. Its ozone example marks a boundary: a fully unbiased log-determinant estimate is currently unavailable there.

8. DISCUSSION AND CONCLUSION

  • The method does not require exact simulation from the underlying model, relying instead on unbiased estimates of the inverse normalising term.Its parallelism may support larger models, though the paper notes a limit to scalability and points to approximate methods for very large-scale models.Source: §8 · pp. 20–21
  • The method uses stochastic truncation of a series to produce an unbiased estimate of the target distribution.For bounded likelihood functions with nonanalytic normalisers, the paper says the methodology can proceed to full MCMC without further restriction.Source: §8 · p. 21
  • When the likelihood function is unbounded, unbiased estimates are not guaranteed to be positive, so an absolute-measure MCMC scheme with sign correction preserves posterior expectations.Monte Carlo error inflation depends on sign-problem severity; in the examples considered, it was not a practical issue when normaliser-estimate variance was well controlled.Source: §8 · p. 21
  • For the total column ozone data set, a completely unbiased estimate of log(det(Q)) required by the method is currently not attainable.The paper identifies efficient unbiased or consistent normaliser estimators as an area for future work.Source: §8 · p. 21
  • Strictly positive estimates from the series expansions require normaliser estimates in a bounded interval, while the general sign problem is NP-hard.The authors identify the absolute-measure approach as one way to address the sign problem.Source: §8 · p. 21

APPENDIX A: RUSSIAN ROULETTE

Russian Roulette estimates an infinite series by stopping at a finite random time and weighting the retained partial sum. The estimator is unbiased under the stated conditions, but truncation speed trades off against variance.

APPENDIX A: RUSSIAN ROULETTE

  • The Russian Roulette truncation uses a finite random stopping time and weights the retained partial sum by the probabilities of reaching each term.The stopping probabilities are positive, with p0 = 1; the random time can be viewed as the algorithm’s running time.Source: Appendix A · pp. 21–22
  • The truncated series estimator has finite expectation and is unbiased for the original series under the stated conditions.The appendix also establishes the necessary integrability condition for finite expectation.Source: Appendix A · pp. 21–22
  • Choosing a stopping rule for quick termination can produce high or even infinite variance.The appendix states that if the sum of n α_n S_(n−1) diverges, the estimator’s variance is infinite.Source: Appendix A · p. 22
  • For geometric series terms, the choice of truncation probability controls both variance and average computing time.The appendix gives E(τ̂) = 1/(1−q), says variance is infinite if q > α^2, and reports q = α as a simulation rule of thumb.Source: Appendix A · pp. 22–23

APPENDIX B: COMPUTING ABSOLUTE MEASURE EXPECTATIONS

The appendix estimates expectations under a possibly signed target by running a Markov chain on its absolute measure and correcting with the sign. Under stated chain conditions, the estimator converges almost surely, while its accuracy depends on sign and autocorrelation behavior.

APPENDIX B: COMPUTING ABSOLUTE MEASURE EXPECTATIONS

  • For a possibly signed target π, the method samples from the probability density proportional to |π| and weights estimates by sign(π).The appendix assumes the relevant absolute integrals are finite and constructs an ergodic Markov chain with the absolute-measure density as its invariant distribution.Source: Appendix B · p. 23
  • With a φ-irreducible, aperiodic chain, the signed expectation estimator converges almost surely to the target integral.The appendix derives this from the Markov-chain law of large numbers.Source: Appendix B · p. 23
  • The sign problem’s severity is reflected by r: smaller r makes accurate estimation harder.The appendix gives a rough Monte Carlo variance approximation using an estimate of the common autocorrelation sum.Source: Appendix B · p. 24
Loading 1306.4032v4…