PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian structure learning using dynamic programming and MCMC

Daniel Eaton, Kevin Murphy

arXiv:1206.5247v1cs.LGstat.ML

TL;DR

When many DAG structures remain plausible, common MCMC proposals can mix poorly, while dynamic programming is limited in the priors and features it handles. The paper uses DP as an informative proposal for MCMC in DAG space, reporting faster convergence and more accurate estimates at comparable compute time.

  • Problem

    Local MCMC proposals can mix poorly, while DP is restricted to modular priors and features and has costly predictive-density computation.

    Source: §1 · p. 1

  • Method

    The method uses dynamic programming as a data-driven proposal for Metropolis–Hastings sampling in DAG space.

    Source: §1 · p. 2

  • Results

    The hybrid method produces more accurate estimates than other approaches given comparable compute time.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The method improves MCMC convergence speed and can also be viewed as overcoming some limitations of Koivisto and Sood's DP algorithm [KS04, Koi06].

    Source: §6 · p. 8

    Scaling is currently limited to 22 nodes by the exponential time and space complexity of the underlying DP algorithm.

    Source: §6 · p. 8

Abstract

from arXiv · show

MCMC methods for sampling from the space of DAGs can mix poorly due to the local nature of the proposals that are commonly used. It has been shown that sampling from the space of node orders yields better results [FK03, EW06]. Recently, Koivisto and Sood showed how one can analytically marginalize over orders using dynamic programming (DP) [KS04, Koi06]. Their method computes the exact marginal posterior edge probabilities, thus avoiding the need for MCMC. Unfortunately, there are four drawbacks to the DP technique: it can only use modular priors, it can only compute posteriors over modular features, it is difficult to compute a predictive density, and it takes exponential time and space. We show how to overcome the first three of these problems by using the DP algorithm as a proposal distribution for MCMC in DAG space. We show that this hybrid technique converges to the posterior faster than other methods, resulting in more accurate structure learning and higher predictive likelihoods on test data.

1 Introduction

Bayesian averaging over graph structures is preferable when many DAGs remain plausible, but exact dynamic programming (DP) has important scope and predictive-density limitations. The paper combines DP with Metropolis–Hastings (MH) sampling in DAG space and reports more accurate estimates than other approaches at comparable compute time.

1 Introduction

  • Bayesian model averaging is preferred when many graph structures remain plausible, because a MAP estimate can yield unwarranted structural conclusions and poor predictions.This is especially relevant when sample size is small relative to the hypothesis space.Source: §1 · p. 1
  • DP analytically marginalizes over node orders and computes exact marginal posterior edge probabilities in O(d2d) time.The method is practical for d ≤20 and faster than comparable MCMC algorithms on similarly sized problems.Source: §1 · p. 1
  • DP is restricted to modular priors and modular features, limiting long-distance feature queries and potentially biasing structural conclusions.Its predictive-density computation requires rerunning DP for each test case, and incomplete observations may require exponentially many runs.Source: §1 · pp. 1–2
  • The hybrid method produces more accurate estimates than other approaches given comparable compute time.It combines DP with MH sampling in DAG space.Source: §1 · p. 2
  • Using a deterministic algorithm as an MCMC proposal had prior precedent, but the authors apply an exact algorithm to graphical-model structure learning.Source: §1 · p. 2

2 Previous work

Earlier approaches sample DAGs, node orderings, or average over graphs with dynamic programming, each with different computational or modeling constraints. The paper situates its approach against these alternatives and methods for predictive-density estimation.

2 Previous work

  • Local add, delete, or reverse proposals mix poorly beyond about 10 dimensions, while adjacency-matrix Gibbs sampling can get stuck even more easily.Multiple restarts can ameliorate the latter problem somewhat.Source: §2 · p. 2
  • Node-order sampling can mix more easily than local DAG proposals, but requires a modular prior, and approximate importance correction yields inferior results to this method.Computing the exact correction is #P-hard.Source: §2 · p. 2
  • Dynamic programming reuses likelihood terms across orderings to compute marginal likelihoods and posterior features exactly.For example, parent order does not affect a node's conditional likelihood.Source: §2 · p. 2
  • Predictive-density alternatives include plug-in graph estimates and exact DP, but exact DP is expensive because it recomputes local marginal likelihoods for every test case.The proposed method averages over sampled graphs for comparable predictive performance at lower cost.Source: §2 · p. 2

3 Modular priors

Order-based methods induce graph priors by summing over orderings, and modular priors can favor graphs with more consistent orders. The section explains the resulting prior artifacts and the difficulty of correcting them exactly.

3 Modular priors

  • A modular prior factors into local ordering and parent-set terms, with each node's parent set constrained to its predecessors in the ordering.The parent-set factor does not depend on the relative order of parents.Source: §3 · p. 3
  • Summing a modular joint prior over orderings favors DAGs consistent with more orders, potentially preserving prior-driven edge predictions even with large samples.Graphs in the same Markov equivalence class have the same likelihood, so prior effects are not washed out.Source: §3 · p. 3
  • A uniform ordering prior combined with equal parent-set weights, called modular flat, does not produce a uniform DAG prior after summing over orders.The figure reports that modular flat is closest to uniform in KL distance but still introduces artifacts.Source: §3 · p. 3, Figure 1 · p. 3
  • Correcting the order-induced graph prior by dividing by each graph's number of consistent orders yields a uniform prior, but computing that count is #P-complete.The figure notes that this correction still leaves the Ellis prior distinct from the uniform distribution.Source: §3 · p. 3, Figure 1 · p. 3
  • The proposed method can cheaply generate samples from an arbitrary prior, unlike order-based methods that define their joint prior over graphs and orders.Source: §3 · pp. 2–3

4 Our method

The method uses Metropolis–Hastings with a mixture of local edge edits and global proposals informed by DP edge marginals. Its proposal balance is controlled by β, and the approach uses multinomial CPDs with conjugate Dirichlet priors.

4 Our method

  • The Metropolis–Hastings proposal mixes uniformly chosen legal single-edge additions, deletions, or reversals with global proposals based on the DP algorithm.The proposed move is accepted with a probability determined by the Metropolis–Hastings step.Source: §4 · pp. 3–4
  • The global proposal samples each edge pair using exact DP marginal posteriors, orients included edges according to their relative marginals, and rejects cyclic graphs.For edge i–j, inclusion probability is p_ij + p_ji, and the orientation probability for i→j is p_ij/(p_ij + p_ji).Source: §4 · p. 4
  • β = 1 gives the standard local proposal, β = 0 gives an independence sampler, and intermediate settings perform between the purely local and global proposals.The global proposal is independent of the current graph; the paper also tried β schedules.Source: §4 · p. 4
  • For β > 0 the chain is aperiodic and irreducible, while β = 0 may lack these properties unless edge marginals near 0 or 1 are truncated.The experiments used C = 1e−4 for truncation.Source: §4 · p. 4
  • The method assumes multinomial CPDs, parameter independence and modularity, and uniform conjugate Dirichlet priors; it uses the BDeu score and AD trees for efficient computation.The technique can extend to other CPDs when their conditional likelihood can be computed or approximated, for example using BIC.Source: §4 · p. 4

5 Experimental results

Across the experiments, DP+MCMC methods converge quickly, recover structural features well, and provide competitive predictive likelihoods. Predictive performance varies by dataset, and exact DP can be costly to run.

5.2 Structural discovery

  • For edge detection on the 20-node child network, DP+MCMC reaches AUC 1.0, matching exact DP and significantly outperforming DAG and order samplers.The edge-detection comparison averages 10 MCMC runs over 200 seconds of compute time.Source: Figure 4 · p. 5, §5.2 · pp. 5–6
  • For path detection on the same network, DP+MCMC with β = 0 or β = 0.1 significantly improves AUC over the other MCMC methods.Path presence is a harder target than edge presence.Source: Figure 5 · p. 5, §5.2 · p. 6

5.1 Speed of convergence to the exact posterior marginals

  • On the six-node CHD dataset, DP+MCMC is reported to converge fastest and most accurately among the compared methods.Figure 3 shows the convergence comparison on CHD data.Source: §5.1 · p. 5, Figure 3 · p. 5

5.3 Accuracy of predictive density

  • On synthetic data, hybrid and global MCMC outperform order sampling in predictive likelihood, and all BMA methods except Gibbs beat the plug-in estimators.The comparison uses a 15-node network; the authors suggest exact DP may be hurt by its modular prior.Source: Figure 6 · p. 6, §5.3 · p. 7
  • On the Adult dataset, exact DP is most accurate but takes over 350 hours; hybrid MCMC with β = 0.1 approximates it at a fraction of the cost.The test set log-likelihood is plotted against training time.Source: Figure 7 · p. 6, §5.3 · p. 7
  • On T-cell data, DP gives the best result but takes 90 hours; global, hybrid, and order samplers perform almost as well at a fraction of the cost.All BMA methods outperform the optimal plug-in estimator.Source: Figure 8 · p. 6, §5.3 · p. 7

5.4 Convergence diagonstics

  • Adult traceplots show Gibbs chains are sticky and local proposals explore poor configurations, while global and order samplers perform well; the global sampler has lower variance and higher quality than the order sampler.The figure's lower-right panel zooms in on the first 25 seconds.Source: §5.4 · pp. 7–8, Figure 9 · p. 7

6 Summary and future work

The paper presents DP-guided MCMC as a way to improve convergence speed in DAG-space sampling and overcome some limitations of dynamic programming. Scaling beyond 22 nodes remains future work because the underlying DP algorithm has exponential time and space complexity.

6 Summary and future work

  • The proposed method improves the convergence speed of MCMC samplers in DAG space and can overcome some limitations of the DP algorithm.Source: §6 · p. 8
  • The method is currently limited to 22 nodes by the underlying DP algorithm’s exponential time and space complexity.Source: §6 · p. 8
  • The authors identify sampling variable partitions and graphs given those partitions as a direction for scaling the method.They note that DP can exploit layering efficiently when the largest layer is small.Source: §6 · p. 8
Loading 1206.5247v1…