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

Kalev Kask, Andrew Gelfand, Lars Otten, Rina Dechter

AAAI 2011 pp. 54-60

doi:10.1609/AAAI.V25I1.7828 /aaai/2011/kask2011aaai-pushing/

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.

PDF AAAI Semantic Scholar

Cite

Text

Kask et al. "Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7828

Markdown

[Kask et al. "Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/kask2011aaai-pushing/) doi:10.1609/AAAI.V25I1.7828

BibTeX

@inproceedings{kask2011aaai-pushing,
  title     = {{Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models}},
  author    = {Kask, Kalev and Gelfand, Andrew and Otten, Lars and Dechter, Rina},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {54-60},
  doi       = {10.1609/AAAI.V25I1.7828},
  url       = {https://mlanthology.org/aaai/2011/kask2011aaai-pushing/}
}