PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiased estimation of log normalizing constants with applications to Bayesian cross-validation

Maxime Rischard, Pierre E. Jacob, Natesh Pillai

arXiv:1810.01382v1stat.COstat.ME

TL;DR

Intractable normalizing constants matter for model comparison, and computational difficulties also arise in Bayesian cross-validation. The paper combines unbiased MCMC estimators with path sampling to estimate log normalizing-constant ratios and uses log-scale unbiasedness for Bayesian cross-validation; path choice remains an important efficiency consideration.

  • Problem

    Normalizing constants can be intractable despite their use in model comparison, and computational difficulties also arise in Bayesian cross-validation.

    Source: §1 · p. 1, §2.2 · p. 3

  • Method

    The approach uses unbiased MCMC estimates of path-sampling integrands to estimate log normalizing-constant ratios.

    Source: §2.1 · p. 3, §2.4.1 · p. 5

  • Results

    The path-sampling estimator is unbiased for r01, and the Bayesian cross-validation procedure uses log-scale unbiasedness to produce an unbiased estimator.

    Source: §2.1 · p. 3, §2.2 · p. 4

  • Takeaways & Limitations

    Estimator efficiency depends on path design, and posterior approximations can be used when designing paths.

    Source: §4 · p. 16

    The estimators rely on both path sampling and unbiased MCMC estimators, and a poorly chosen path can give poor results.

    Source: §4 · p. 16

Abstract

from arXiv · show

Posterior distributions often feature intractable normalizing constants, called marginal likelihoods or evidence, that are useful for model comparison via Bayes factors. This has motivated a number of methods for estimating ratios of normalizing constants in statistics. In computational physics the logarithm of these ratios correspond to free energy differences. Combining unbiased Markov chain Monte Carlo estimators with path sampling, also called thermodynamic integration, we propose new unbiased estimators of the logarithm of ratios of normalizing constants. As a by-product, we propose unbiased estimators of the Bayesian cross-validation criterion. The proposed estimators are consistent, asymptotically Normal and can easily benefit from parallel processing devices. Various examples are considered for illustration.

1 Setting

Monte Carlo methods can approximate posterior expectations without the intractable normalizing constant, but the constant itself is useful for model comparison. This paper proposes unbiased estimation of log normalizing constants and extends that property to Bayesian cross-validation.

1 Setting

  • Posterior normalizing constants, also called marginal likelihoods or evidence, are useful for model comparison but are often intractable.MCMC can approximate posterior expectations without access to the normalizing constant.Source: §1 · p. 1
  • The proposed estimator combines unbiased MCMC with path sampling and has expectation exactly equal to log Z.The passage contrasts this with MCMC estimators that are only asymptotically unbiased and annealed importance or sequential Monte Carlo estimators that are unbiased for Z, not log Z.Source: §1 · p. 1
  • The log-scale unbiasedness also yields an estimator directly unbiased for Bayesian cross-validation objectives based on the logarithmic scoring rule.Averaging independent copies gives consistent estimators and asymptotically exact confidence intervals by the i.i.d. central limit theorem.Source: §1 · p. 2

2 Proposed estimators

The proposed estimators combine unbiased MCMC with path sampling to estimate log normalizing-constant ratios without bias, then use that property to estimate a Bayesian cross-validation criterion directly. The section also describes unbiased-MCMC implementation and tuning choices.

2.1 Unbiased path sampling

  • The path-sampling estimator combines unbiased estimates of the pathwise expectation with sampling over λ to estimate log(Z1/Z0) without bias.A discretized path with MCMC estimates instead yields consistency as the grid and iteration counts grow.Source: §2.1 · pp. 2–3

2.2 Unbiased Bayesian cross-validation

  • Sampling a training/validation split and estimating its negative log predictive density with the unbiased log-ratio estimator gives an estimator directly unbiased for CV.The logarithmic-scale unbiasedness is essential to this construction.Source: §2.2 · pp. 3–4

2.3 Reminders on unbiased MCMC

  • The implementation uses unbiased MCMC estimators based on coupled chains that meet, with a correction term making the estimator's expectation equal the target expectation.Other unbiased MCMC estimators could be substituted.Source: §2.3 · p. 4

2.4 Tuning choices

  • Path choice and tuning parameters for unbiased MCMC and the λ-distribution are the main operational choices for the proposed estimators.Paths may be generic, such as the geometric path, or chosen for algorithmic reasons.Source: §2.4 · p. 5

2.4.1 Tuning of unbiased MCMC

  • The expected cost of an unbiased MCMC estimate depends on its random meeting time; choosing k beyond likely meeting times and m as a multiple of k limits discarded iterations.Under further kernel conditions, variance can approach that of standard MCMC when k and m are sufficiently large.Source: §2.4.1 · p. 5

2.4.2 Tuning of the distribution q(dλ)

  • The λ sampling density is tuned to improve estimator efficiency, defined through the product of expected cost and variance.When cost is constant over λ, the proposed optimal density is proportional to the square root of the second moment of the unbiased pathwise estimator.Source: §2.4.2 · pp. 5–6

2.4.3 Proposed tuning procedure

  • The proposed tuning procedure estimates meeting-time behavior and second moments on a λ grid, then uses them to set tuning parameters and approximate q(λ) proportional to the square root of the second moment.The m parameters can be chosen to make expected cost approximately constant across λ.Source: §2.4.3 · p. 6

3 Numerical experiments

The numerical experiments cover toy examples and regression applications, with confidence intervals constructed from independent unbiased estimates and justified asymptotically under a finite-variance condition.

3 Numerical experiments

  • The experiments include toy examples and logistic regressions comparing path choices and unbiased MCMC estimators, including examples from Epifani et al. (2008) and Vehtari et al. (2017).Source: §3 · p. 7
  • Linear-regression experiments draw examples from Alqallaf and Gustafson (2001), Peruggia (1997), and Vehtari et al. (2017).Source: §3 · p. 7
  • For M independent unbiased estimators of µ, confidence intervals are asymptotically justified as M → ∞ by the central limit theorem for i.i.d. variables, provided estimator variance is finite.Under parallel-machine budget constraints, valid confidence intervals can be constructed following Glynn and Heidelberger (1991), with related remarks in Jacob et al. (2017).Source: §3 · p. 7

3.1 Toy examples of normalizing constant estimation

The normal example estimates a log normalizing-constant ratio of zero, while the double-well example estimates a ratio near −6.9 despite longer meeting times near the difficult endpoint.

3.1.1 Normal example

  • The normal example interpolates between N(0, 1) and N(4, 1), whose normalizing constants are equal, so r01 = 0.It uses a grid with L = 10 and coupled Metropolis–Hastings chains with normal random-walk proposals.Source: §3.1.1 · p. 7
  • The 95% confidence interval [−0.11, 0.12] contains the normal example’s known estimand r01 = 0 across 5,000 independent estimates.Figure 1 shows meeting-time distributions, estimates of m2(λ) used to define q(dλ), and estimators plotted against λ.Source: §3.1.1 · p. 8, Figure 1 · p. 8

3.1.2 Double-well example

  • Meeting times are much larger near λ = 1, where the Metropolis–Hastings chains struggle to explore both modes of the double-well potential.The experiment draws 1,000 meeting times at each of 11 grid values and sets k_l to twice their 99% quantiles.Source: §3.1.2 · p. 8
  • The 95% confidence interval [−7.55, −6.37] contains the double-well estimand r01 ≈−6.9 across 1,000 independent estimates.The right panel plots estimators against λ; the left shows meeting-time distributions and the middle estimates m2(λ).Source: §3.1.2 · p. 8, Figure 2 · p. 9

3.2 Logistic regression

The logistic-regression examples use Pólya-Gamma Gibbs sampling (PGG) for normalizing-constant estimation and compare path choices for leave-one-out cross-validation. Log-spaced tuning and a path from a Laplace approximation yield narrower reported intervals in their respective examples.

3.2.1 Normalizing constant estimation

  • The PGG sampler enables logistic-regression normalizing-constant estimation with little tuning because the sampler itself has no tuning parameters.The experiments tune a proposal distribution over λ using estimated second moments on a grid.Source: §3.2.1 · p. 10
  • Log-spaced λ values narrow the 95% interval for r01 from [63, 89] to [64.7, 74.7], reducing its width from 36 to 10.Large estimates near λ = 0 motivate the finer grid there.Source: §3.2.1 · pp. 10–11
  • A path from the Laplace approximation gives a 95% confidence interval of [70.24, 70.26] for log Z1 + n log 2, at lower computational cost than previous intervals.The authors note that path choice can strongly affect estimator efficiency.Source: §3.2.1 · p. 11

3.2.2 Cross-validation

  • For logistic-regression leave-one-out CV, the PGG and tempered random-walk MH approaches give 95% intervals of [−0.62, −0.56] and [−0.60, −0.56], respectively.The MH approach appears marginally more efficient, but comparing costs is difficult because iteration costs differ between PGG and MH.Source: §3.2.2 · pp. 12–13, Figure 4 · p. 12

3.2.3 Leukemia survival data

  • In the leukemia example, the leave-one-out CV interval is [−0.72, −0.66], while estimates vary substantially across splits, particularly for left-out observation 17.The authors note that tuning the proposal distribution or changing the path might reduce variance for particular splits.Source: §3.2.3 · p. 13, Figure 5 · p. 13

3.3 Linear regressions

The linear-regression examples apply unbiased MCMC estimators to cross-validation criteria, using either a prediction-error expectation or a log predictive score. The reported procedures produce estimates for the mammal-weight and stack-loss examples, with variability across held-out observations noted for stack loss.

3.3.1 Mammal weight data

  • For mammal-weight prediction error, 1,000 independent unbiased CV estimators give a 95% interval of [32.79, 33.03] and standard error 0.06, similar to Alqallaf and Gustafson (2001).The procedure randomly draws a data split and obtains an unbiased posterior estimator of the validation-set prediction-error expectation.Source: §3.3.1 · pp. 14–15
  • For mammal-weight log predictive score, the estimated CV criterion is 33.97 with standard error 0.1 from 1,000 independent estimators.The target criterion is −log p(YV | YT).Source: §3.3.1 · p. 15

3.3.2 Stack loss data

  • For stack-loss leave-one-out CV, 10,000 replicates give a 95% interval of [2.78, 2.82], with estimator variance varying across data splits.The figure plots the data and CV objective against the left-out observation.Source: §3.3.2 · p. 16, Figure 6 · p. 16

4 Discussion

The estimators depend on both path sampling and unbiased integral estimators, so poor path choices or MCMC mixing and coupling can undermine them. The approach also extends to other scoring rules, while comparisons with existing methods remain future work.

4 Discussion

  • Further work is needed to compare the estimators with sequential Monte Carlo, alternative normalizing-constant methods, and existing Bayesian cross-validation approaches.Source: §4 · p. 16
  • Poorly chosen paths, poor MCMC mixing, or ineffective coupling can cause the estimators to fail; path choice also produced orders-of-magnitude efficiency differences.Paths may benefit from posterior approximations such as Laplace approximations, and the distribution q(dλ) can be guided by preliminary runs.Source: §4 · p. 16
  • Because path sampling is a nested Monte Carlo problem with a linear inner-expectation term, unbiased estimates of that expectation yield unbiased estimates of the integrand.The discussion also notes that unbiased estimates extend to functions polynomial in the expectation, by multiplying independent estimates for powers.Source: §4 · pp. 16–17
  • The approach can be adapted to estimate Bayesian cross-validation objectives defined by other scoring rules, including the Hyvärinen score.Source: §4 · p. 17
Loading 1810.01382v1…