Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models

Authors

  • Kalev Kask University of California, Irvine
  • Andrew Gelfand University of California, Irvine
  • Lars Otten University of California, Irvine
  • Rina Dechter University of California, Irvine

Abstract

We study iterative randomized greedy algorithms for generating (elimination) orderings with small induced width and state space size — two parameters known to bound the complexity of inference in graphical models. We propose and implement the Iterative Greedy Variable Ordering (IGVO) algorithm, a new variant within this algorithm class. An empirical evaluation using different ranking functions and conditions of randomness, demonstrates that IGVO finds significantly better orderings than standard greedy ordering implementations when evaluated within an anytime framework. Additional order of magnitude improvements are demonstrated on a multi-core system, thus further expanding the set of solvable graphical models. The experiments also confirm the superiority of the MinFill heuristic within the iterative scheme.

Downloads

Published

2011-08-04

How to Cite

Kask, K., Gelfand, A., Otten, L., & Dechter, R. (2011). Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 54-60. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7828

Issue

Section

Constraints, Satisfiability, and Search