AND/OR Importance Sampling

Vibhav Gogate, Rina DechterUAI 2008

TL;DR

This paper introduces AND/OR Importance Sampling, a novel technique that leverages the structure of probabilistic graphical models to significantly reduce variance in probability estimation compared to traditional importance sampling. By caching and reusing computations within an AND/OR search space, it achieves more accurate estimates with the same computational resources.

What Problem Does This Paper Address?

Many real-world problems, such as calculating the probability of evidence in Bayesian networks or counting solutions in constraint satisfaction problems, are computationally intractable (NP-hard). These problems often boil down to summing a function over a vast number of possibilities. Importance sampling is a popular technique to approximate these sums by drawing samples from a related distribution and computing a weighted average. However, traditional importance sampling can suffer from high variance, meaning the estimates can fluctuate wildly and be unreliable, especially when the proposal distribution is a poor approximation of the true distribution. This paper aims to improve the accuracy and reliability of importance sampling for these complex graphical models.

Methods

The core innovation is AND/OR Importance Sampling. Instead of treating the entire problem as a monolithic sum, this method breaks it down by exploiting the inherent structure of the graphical model, represented by an AND/OR search tree or graph.

Here's how it works:

  • AND/OR Search Space: The paper first defines an AND/OR search space, which is a structured representation of the problem that mirrors the graphical model's dependencies. OR nodes represent alternative choices or assignments, while AND nodes represent subproblems that must all be solved.
  • Caching and Reusing Computations: The key idea is to cache intermediate results (samples and their associated weights) within this AND/OR structure. When a subproblem is encountered multiple times, the cached results are reused. This is analogous to memoization in dynamic programming.
  • "Expectation by Parts": The method estimates expectations by breaking them down into conditional expectations, which are then approximated. This "expectation by parts" approach, when combined with caching, leads to a more efficient use of samples.
  • AND/OR Sample Tree/Graph: The generated samples are organized into an AND/OR sample tree or graph. The values of nodes in this structure are computed recursively, leveraging the cached information. The value of the root node then serves as the AND/OR importance sampling estimate.
  • Variance Reduction: The paper theoretically proves that this AND/OR approach can achieve lower variance than standard importance sampling. This is because the effective sample size is increased by reusing cached computations, leading to more stable estimates.

Datasets

The paper evaluates its method on three sets of benchmark Bayesian networks:

  • Random Networks: These are general networks used to test the core algorithm.
  • Linkage Networks: These are generated from pedigree structures and often have complex dependencies.
  • Grid Networks: These networks have a structured grid-like topology.

The authors note that for instances with zero probabilities or determinism, they use a modified approach called SampleSearch, which was introduced in prior work.

Key Insights and Ideas

  • Structure is Key: The paper powerfully demonstrates that exploiting the inherent structure of graphical models (via AND/OR trees/graphs) is crucial for improving sampling-based inference.
  • "Expectation by Parts" for Efficiency: Breaking down complex expectations into smaller, conditional ones and approximating them individually is more efficient than approximating the entire expectation at once.
  • Memoization for Variance Reduction: Caching and reusing computations within the AND/OR structure effectively increases the "effective sample size," leading to more stable and accurate estimates. This is the core mechanism for variance reduction.
  • AND/OR Graphs Offer Further Improvement: Moving from AND/OR trees to AND/OR graphs (by merging identical subtrees) can lead to even greater variance reduction, as it further consolidates computations.

Key Results

The experimental evaluation shows that AND/OR Importance Sampling (both tree and graph versions) consistently outperforms traditional importance sampling.

  • Random Networks: AND/OR-graph sampling was better than AND/OR-tree, which was better than pure IJGP-sampling. The difference in error was not dramatic because the proposal distribution was already a good approximation.
  • Grid Networks: AND/OR-graph SampleSearch and AND/OR-tree SampleSearch were substantially better than pure SampleSearch.
  • Linkage Networks: This is where the benefits were most pronounced. AND/OR-graph SampleSearch was substantially more accurate than AND/OR-tree SampleSearch, which was in turn substantially more accurate than pure SampleSearch. The log-scale plots in Figure 6 highlight an order-of-magnitude difference in errors, indicating that AND/OR methods are significantly better when the proposal distribution is a poor approximation of the posterior.

Limitations and Future Work

  • Complexity of AND/OR Graphs: While AND/OR graphs offer better variance reduction, their construction and traversal can be more complex, with time complexity dependent on the treewidth of the pseudo-tree.
  • Focus on Probability of Evidence: The current work focuses on estimating the probability of evidence. The authors suggest that their approach could be extended to other inference tasks like belief updating.
  • Combining Techniques: The paper mentions that variance reduction from Rao-Blackwellisation is orthogonal to AND/OR estimation, suggesting future work could combine these techniques for even greater gains.
  • Preliminary Evaluation: The authors describe their experimental evaluation as "preliminary but quite promising," indicating that further extensive testing on a wider range of problems would be beneficial.

Summary updated

BibTeX
@inproceedings{gogate2008or,
  author = {Vibhav Gogate and Rina Dechter},
  title = {{AND/OR Importance Sampling}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure