General-Purpose MCMC Inference over Relational Structures

Brian Milch, Stuart RussellUAI 2006 · OpenReview

TL;DR

This paper introduces a general-purpose Markov Chain Monte Carlo (MCMC) inference engine built on the BLOG probabilistic modeling language. It tackles the challenge of applying MCMC to relational structures by allowing "partial world" MCMC states and providing efficient methods for computing acceptance probabilities, significantly reducing the need for application-specific code.

What Problem Does This Paper Address?

Many real-world problems involve inferring underlying objects and their relationships from observed data, such as identifying publications from citations or tracking objects from sensor readings. These "relational inference" tasks are notoriously difficult for standard probabilistic algorithms due to the vast number of possible object configurations. While Markov Chain Monte Carlo (MCMC) methods, particularly Metropolis-Hastings (M-H), have shown promise, existing implementations require extensive custom coding for each new problem. This includes defining MCMC state representations and calculating acceptance probabilities, making it cumbersome to adapt MCMC to new relational domains. The paper aims to bridge this gap by creating a flexible, general-purpose MCMC system that leverages a probabilistic modeling language (BLOG) and supports user-defined proposal distributions without requiring deep, application-specific implementation details.

Methods

The core of the paper's contribution lies in its novel approach to MCMC states and acceptance probability computation.

  • Partial World MCMC States: Instead of requiring MCMC states to represent complete possible worlds, the system uses "partial instantiations." These are incomplete descriptions of worlds that focus only on relevant variables (evidence and query variables) and abstract away interchangeable objects. This is crucial because full world representations can be infinitely large or computationally intractable. The paper provides theoretical conditions (Theorem 1) under which MCMC over these partial states yields correct posterior probabilities.
  • Abstract Partial Instantiations: To handle interchangeable objects (like multiple publications that are indistinguishable without specific attributes), the system uses "abstract partial instantiations." These employ object identifiers (e.g., Pub@A3F) that can be mapped to concrete objects later. This simplifies the proposal distribution design by avoiding the need to explicitly manage object identities and their probabilities.
  • Efficient Acceptance Probability Computation: The paper introduces a method to efficiently compute the probability ratio $p(s')/p(s_n)$ required for the M-H acceptance probability. This is achieved by:
  • Difference Data Structures: MCMC states are represented using "patches" that store only the changes from the previous state, making state updates and copying more efficient.
  • Context-Specific Bayes Net: A graph representing the active dependencies in the current MCMC state is maintained. This allows the system to quickly identify which factors in the probability ratio need to be recomputed, avoiding unnecessary calculations. Proposition 5 is key here, stating that if a variable and its active parents are unchanged, its probability factor remains the same.

Datasets

The paper evaluates its system on a citation matching task. The datasets used are described as "four sets of about 300-500 unparsed citations that were collected by [Lawrence et al., 1999]." These datasets are annotated with true citation clusters, serving as ground truth for evaluating accuracy.

Key Insights and Ideas

  • The Power of Partiality: The most significant insight is that MCMC doesn't need to explore full possible worlds to be effective. By focusing on partial descriptions and providing theoretical guarantees, the system dramatically reduces computational burden and complexity.
  • Abstraction for Interchangeability: Using abstract object identifiers is a clever way to handle the common problem of indistinguishable objects in relational models. It decouples the proposal design from the complexities of object enumeration and assignment.
  • Leveraging Structure for Efficiency: The use of a context-specific Bayes net to track active dependencies is a powerful optimization. It highlights how understanding the structure of the probabilistic model and the current state can lead to significant speedups in inference.
  • Generalization is Achievable: The paper demonstrates that a general-purpose MCMC engine can be built that performs comparably to application-specific systems, paving the way for broader adoption of MCMC in complex relational domains.

Key Results

The paper's experimental results on the citation matching task show:

  • Comparable Accuracy: The general-purpose BLOG MCMC engine achieved accuracy comparable to a hand-coded Java implementation of a similar M-H approach. For instance, the "accuracy (final)" for the BLOG engine on the "Face" dataset was 96.3% (±0.8%), very close to the hand-coded Java's 96.0% (±0.9%).
  • Efficiency Trade-offs: While the general-purpose engine is more flexible, it is slower than the hand-coded system. The BLOG engine consistently took about 5 times longer than the hand-coded Java implementation for the same number of samples. This is attributed to the overhead of using general data structures (hash tables) and interpreting BLOG model logic compared to optimized, application-specific code. However, the authors note that their current computing infrastructure has improved enough that the general system runs faster than a hand-coded system did three years prior.

Limitations and Future Work

  • Proposal Distribution Still Requires Effort: While the engine is general, users still need to implement the proposal distribution, which can be a significant undertaking. The paper suggests that a declarative language for specifying proposals would be ideal but is a future research direction.
  • Speed vs. Generality: The current general-purpose implementation is slower than highly optimized, application-specific code due to the overhead of general data structures and interpretation. Future work could focus on optimizing these general components or developing techniques to detect and exploit more domain-specific structure automatically.
  • Limited Automatic Cancellation Detection: The system doesn't automatically detect cancellations in probability factors, a feature present in Gibbs sampling.
  • Future Work: The authors plan to extend their BLOG model and proposal distribution to simultaneously reconstruct publications, researchers, and venues in citation matching. They also aim to develop models and proposals for other tasks like coreference resolution in text and to understand common principles for effective proposal distributions to build a library of reusable modules.

Summary updated

Abstract

Tasks such as record linkage and multi-target tracking, which involve reconstructing the set of objects that underlie some observed data, are particularly challenging for probabilistic inference. Recent work has achieved efficient and accurate inference on such problems using Markov chain Monte Carlo (MCMC) techniques with customized proposal distributions. Currently, implementing such a system requires coding MCMC state representations and acceptance probability calculations that are specific to a particular application. An alternative approach, which we pursue in this paper, is to use a general-purpose probabilistic modeling language (such as BLOG) and a generic Metropolis-Hastings MCMC algorithm that supports user-supplied proposal distributions. Our algorithm gains flexibility by using MCMC states that are only partial descriptions of possible worlds; we provide conditions under which MCMC over partial worlds yields correct answers to queries. We also show how to use a context-specific Bayes net to identify the factors in the acceptance probability that need to be computed for a given proposed move. Experimental results on a citation matching task show that our general-purpose MCMC engine compares favorably with an application-specific system.
BibTeX
@inproceedings{milch2006general,
  author = {Brian Milch and Stuart Russell},
  title = {{General-Purpose MCMC Inference over Relational Structures}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=NHYgDTk82JC},
}
Figure