Skip to main content
Journal cover image

Pushing the power of stochastic greedy ordering schemes for inference in graphical models

Publication ,  Conference
Kask, K; Gelfand, A; Otten, L; Dechter, R
Published in: Proceedings of the National Conference on Artificial Intelligence
November 2, 2011

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 multicore system, thus further expanding the set of solvable graphical models. The experiments also confirm the superiority of the MinFill heuristic within the iterative scheme. Copyright © 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.

Duke Scholars

Published In

Proceedings of the National Conference on Artificial Intelligence

ISBN

9781577355083

Publication Date

November 2, 2011

Volume

1

Start / End Page

54 / 60
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kask, K., Gelfand, A., Otten, L., & Dechter, R. (2011). Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In Proceedings of the National Conference on Artificial Intelligence (Vol. 1, pp. 54–60).
Kask, K., A. Gelfand, L. Otten, and R. Dechter. “Pushing the power of stochastic greedy ordering schemes for inference in graphical models.” In Proceedings of the National Conference on Artificial Intelligence, 1:54–60, 2011.
Kask K, Gelfand A, Otten L, Dechter R. Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In: Proceedings of the National Conference on Artificial Intelligence. 2011. p. 54–60.
Kask, K., et al. “Pushing the power of stochastic greedy ordering schemes for inference in graphical models.” Proceedings of the National Conference on Artificial Intelligence, vol. 1, 2011, pp. 54–60.
Kask K, Gelfand A, Otten L, Dechter R. Pushing the power of stochastic greedy ordering schemes for inference in graphical models. Proceedings of the National Conference on Artificial Intelligence. 2011. p. 54–60.
Journal cover image

Published In

Proceedings of the National Conference on Artificial Intelligence

ISBN

9781577355083

Publication Date

November 2, 2011

Volume

1

Start / End Page

54 / 60