Using multi-step proposal distribution for improved MCMC convergence in Bayesian network structure learning

Antti Larjo, Harri LähdesmäkiEURASIP J. Bioinform. Syst. Biol 2015 · OpenReview

TL;DR

This paper tackles the challenge of slow convergence in Bayesian network (BN) structure learning using Markov Chain Monte Carlo (MCMC). They introduce a novel "multi-step" proposal distribution that allows MCMC chains to take larger "jumps" in the complex space of possible network structures, significantly improving convergence speed and the ability to escape local optima. This approach is demonstrated to be more effective than traditional single-step methods, especially on real-world biological data.

What Problem Does This Paper Address?

Learning the structure of Bayesian networks (BNs) is crucial for understanding complex probabilistic relationships, particularly in fields like systems biology where BNs can model gene regulatory or protein signaling pathways. However, the sheer number of possible network structures grows exponentially with the number of variables, making exhaustive search impossible. Markov Chain Monte Carlo (MCMC) methods are commonly used to sample from the posterior distribution of possible network structures. The main hurdle with MCMC is its slow convergence, often getting stuck in "local maxima" – suboptimal network structures – which hinders accurate inference. This paper addresses this by proposing a more efficient way for MCMC to explore the vast space of BN structures.

Methods

The core contribution is the development of a "multi-step proposal distribution" for MCMC in BN structure learning. Traditionally, MCMC explores the structure space by making small, single-edge modifications (adding, deleting, or reversing an edge) to the current network. This is referred to as a "single-step" proposal. The authors extend this by allowing the MCMC chain to propose transitions that involve a sequence of t single-edge modifications, effectively taking a larger "jump" in the structure space.

The multi-step proposal is constructed as a mixture of transitions of different lengths. The probability of proposing a transition of length t is tunable. The authors derive the acceptance probability for these multi-step moves, showing that the Hastings ratio can be computed efficiently without needing to evaluate the size of the entire neighborhood, which is a significant computational bottleneck for larger steps. They also provide a proof of ergodicity for the Markov chain constructed with this multi-step proposal, ensuring it converges to the correct stationary distribution.

Datasets

The primary dataset used for evaluation is from a study by Sachs et al. [5], which contains flow cytometry measurements of 11 proteins in a human primary T cell signaling network. This dataset includes both unstimulated and perturbed conditions. The authors also use simulated datasets from the well-known Alarm network [30] to systematically test the performance of their method across varying dataset sizes and with different proposal distribution configurations.

Key Insights and Ideas

  • Jumping Out of Local Optima: The most significant insight is that larger steps (multi-step proposals) are crucial for escaping local maxima in the complex, multimodal posterior landscape of BN structures. Single-step proposals are too "local" in their exploration.
  • Tunable Exploration: The multi-step proposal is highly flexible. By adjusting the lengths of the steps and their probabilities, one can tailor the exploration strategy to the specific dataset and problem. This adaptability is a key advantage.
  • Computational Efficiency: Despite proposing larger jumps, the method is designed to be computationally efficient. The authors show that the acceptance probability calculation doesn't require enumerating all possible intermediate structures, mitigating the computational cost associated with larger steps.
  • Real-World Applicability: The method demonstrates improved convergence on a real biological signaling network, where single-step MCMC struggled to find consistent results across different chains.

Key Results

  • Improved Convergence: Figures 1 and 6 show that using a proposal with a mixture of one and two steps ([p₁=0.5, p₂=0.5]) leads to much better agreement between independent MCMC chains compared to the standard one-step proposal. This indicates that the chains are converging to the same posterior distribution.
  • Finding Higher Scoring DAGs: Figure 7 and Table 1 demonstrate that multi-step proposals (especially those with a mix of step lengths) are significantly better at finding higher-scoring DAGs and exploring a larger portion of the DAG space compared to one-step proposals. For instance, the probability of reaching the highest scoring DAGs was substantially higher with multi-step proposals.
  • Dataset Size Matters: Figure 9 shows that for smaller datasets, single-step proposals are adequate. However, as dataset size increases, the posterior becomes "peakier," and multi-step proposals become essential to avoid getting stuck.
  • Performance on Simulated Data: Using the Alarm network, the authors show that multi-step proposals ([p₁=0.8, p₂=0.2]) yield significantly lower sums of squared differences in edge posterior probabilities between chains compared to single-step proposals, indicating better convergence.

Limitations and Future Work

  • Tuning Complexity: While flexible, finding the optimal mix of step lengths for the proposal distribution might require some tuning, potentially through an adaptive phase during the burn-in period.
  • Not a Universal Solution: The authors acknowledge that their proposal is not guaranteed to outperform all existing methods in every scenario but emphasizes its generality and ease of implementation.
  • Future Work: The paper suggests that this multi-step proposal framework can be easily adapted for full adaptive MCMC samplers. It also highlights the potential for using informative priors, which is particularly relevant in biological applications. The authors also note that while their method improves convergence, further research might be needed to fully capture complex causal relationships, especially in systems with loops or hidden variables.

Summary updated

Abstract

Bayesian networks have become popular for modeling probabilistic relationships between entities. As their structure can also be given a causal interpretation about the studied system, they can be used to learn, for example, regulatory relationships of genes or proteins in biological networks and pathways. Inference of the Bayesian network structure is complicated by the size of the model structure space, necessitating the use of optimization methods or sampling techniques, such Markov Chain Monte Carlo (MCMC) methods. However, convergence of MCMC chains is in many cases slow and can become even a harder issue as the dataset size grows. We show here how to improve convergence in the Bayesian network structure space by using an adjustable proposal distribution with the possibility to propose a wide range of steps in the structure space, and demonstrate improved network structure inference by analyzing phosphoprotein data from the human primary T cell signaling network.
BibTeX
@article{larjo2015using,
  author = {Antti Larjo and Harri Lähdesmäki},
  title = {{Using multi-step proposal distribution for improved MCMC convergence in Bayesian network structure learning}},
  journal = {EURASIP J. Bioinform. Syst. Biol.},
  year = {2015},
  url = {https://openreview.net/forum?id=1CtaFIcwA8},
}
Figure