On Combining Graph-based Variance Reduction schemes

Vibhav Gogate, Rina DechterAISTATS 2010

Abstract

Estimating values in graphical models, such as calculating the probability of evidence, is a fundamental task in AI often addressed via Importance Sampling. However, high variance remains a significant challenge. This paper presents a novel hybrid framework that combines Rao-Blackwellised $w$-cutset sampling with AND/OR sampling. By performing exact inference on sub-structures while simultaneously exploiting problem decomposition through AND/OR search spaces, the proposed estimators significantly reduce variance. Experimental results on grid networks, genetic linkage models, and combinatorial problems demonstrate that these graph-based schemes can improve accuracy by an order of magnitude over traditional methods.

Introduction

Weighted counting over graphical models, such as Bayesian or Markov networks, is a cornerstone of many AI tasks, including medical diagnosis and constraint satisfaction. Because exact calculation is often NP-hard, researchers frequently turn to Importance Sampling. However, Importance Sampling is notorious for high variance; if samples fail to capture high-probability regions, estimates become wildly inaccurate.

To mitigate this, structural exploitation is common. Two primary techniques have emerged: Rao-Blackwellisation ($w$-cutset sampling), which reduces the sampling space by solving a subset of variables exactly, and AND/OR Sampling, which uses problem decomposition to reuse samples across independent branches. This paper introduces a unified framework that combines these two approaches, creating a new family of estimators that significantly outperform previous methods.

The Hybrid Framework: AND/OR $w$-cutset Sampling

The authors propose a unified framework that performs AND/OR sampling specifically over the $w$-cutset variables. This hybrid approach leverages the strengths of both exact inference and decomposition.

AND/OR $w$-cutset Tree and Graph Sampling

In AND/OR $w$-cutset Tree Sampling, samples are arranged in an AND/OR tree rather than a linear path. This allows the algorithm to exploit conditional independencies. For every leaf in this cutset tree, exact inference (using techniques like bucket elimination) is performed on the remaining variables.

The more advanced AND/OR $w$-cutset Graph Sampling recognizes identical sub-problems (contexts) reached via different paths. By merging these nodes, the tree becomes a graph. This process extracts "virtual samples" from the raw data, effectively increasing the sample size without additional draws from the proposal distribution.

Evolution of search structures: (a) Constraint graph, (b) Pseudo-tree, (c) AND/OR tree, (d) OR tree, and (e) AND/OR graph.

The core innovation is the Variance Hierarchy. The authors mathematically establish that these hybrid schemes are guaranteed to have lower or equal variance compared to the individual schemes they are built from.

Key Insights

The success of this approach stems from the orthogonality of the combined techniques. Rao-Blackwellisation reduces the "dimensionality" of the sampling space, while AND/OR decomposition increases the "effective sample size" through the virtual sample multiplier. By using the AND/OR graph structure, a small number of actual samples can represent an exponentially larger number of virtual assignments.

However, there is a trade-off between time, space, and variance. While graph-based schemes offer the lowest variance, they require more memory and computational overhead to manage complex data structures. The more "graph-based" the scheme, the higher the memory (space) required to store and manage the contexts.

Experimental Evaluation

The authors evaluated their algorithms on three distinct types of benchmarks:

  • Grid Networks: Partially deterministic $s \times s$ grids, standard for testing probabilistic inference.
  • Linkage Networks: Real-world genetic linkage instances converted into Bayesian networks.
  • 4-Coloring Problems: Hard combinatorial instances generated using flat graph coloring generators.

In almost all tests, the AND/OR $w$-cutset graph sampling scheme provided the most accurate estimates. On difficult Linkage and Grid benchmarks, the new schemes achieved errors significantly lower than standard importance sampling—often improving accuracy by a factor of 10 or more within a one-hour time limit. Furthermore, the hybrid schemes maintained a lead even as time progressed, showing that the overhead of building AND/OR structures pays off quickly as problem difficulty increases.

Conclusion

This work demonstrates that combining Rao-Blackwellisation with AND/OR decomposition provides a powerful tool for variance reduction in graphical models. While memory constraints remain a consideration for extremely large models, the order-of-magnitude gains in accuracy make these hybrid schemes a significant advancement. Future directions include exploring better ways to automatically select the $w$-cutset and developing adaptive proposal distributions that evolve as more data is collected.

Summary updated

BibTeX
@article{gogate2010combining,
  author = {Vibhav Gogate and Rina Dechter},
  title = {{On Combining Graph-based Variance Reduction schemes}},
  journal = {AISTATS},
  year = {2010},
}
Figure