Ordering Variables for Weighted Model Integration

Vincent Derkinderen, Evert Heylen, Pedro Zuidberg Dos Martires, Samuel Kolb, Luc Raedt
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:879-888, 2020.

Abstract

State-of-the-art probabilistic inference algorithms, such as variable elimination and search-based approaches, rely heavily on the order in which variables are marginalized. Finding the optimal ordering is an NP-complete problem. This computational hardness has led to heuristics to find adequate variable orderings. However, these heuristics have mostly been targeting discrete random variables. We show how variable ordering heuristics from the discrete domain can be ported to the discrete-continuous domain. We equip the state-of-the-art F-XSDD(BR) solver for discrete-continuous problems with such heuristics. Additionally, we propose a novel heuristic called bottom-up min-fill (BU-MiF), yielding a solver capable of determining good variable orderings without having to rely on the user to provide such an ordering. We empirically demonstrate its performance on a set of benchmark problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v124-derkinderen20a, title = {Ordering Variables for Weighted Model Integration}, author = {Derkinderen, Vincent and Heylen, Evert and Zuidberg Dos Martires, Pedro and Kolb, Samuel and de Raedt, Luc}, booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)}, pages = {879--888}, year = {2020}, editor = {Peters, Jonas and Sontag, David}, volume = {124}, series = {Proceedings of Machine Learning Research}, month = {03--06 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v124/derkinderen20a/derkinderen20a.pdf}, url = {https://proceedings.mlr.press/v124/derkinderen20a.html}, abstract = {State-of-the-art probabilistic inference algorithms, such as variable elimination and search-based approaches, rely heavily on the order in which variables are marginalized. Finding the optimal ordering is an NP-complete problem. This computational hardness has led to heuristics to find adequate variable orderings. However, these heuristics have mostly been targeting discrete random variables. We show how variable ordering heuristics from the discrete domain can be ported to the discrete-continuous domain. We equip the state-of-the-art F-XSDD(BR) solver for discrete-continuous problems with such heuristics. Additionally, we propose a novel heuristic called bottom-up min-fill (BU-MiF), yielding a solver capable of determining good variable orderings without having to rely on the user to provide such an ordering. We empirically demonstrate its performance on a set of benchmark problems.} }
Endnote
%0 Conference Paper %T Ordering Variables for Weighted Model Integration %A Vincent Derkinderen %A Evert Heylen %A Pedro Zuidberg Dos Martires %A Samuel Kolb %A Luc Raedt %B Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) %C Proceedings of Machine Learning Research %D 2020 %E Jonas Peters %E David Sontag %F pmlr-v124-derkinderen20a %I PMLR %P 879--888 %U https://proceedings.mlr.press/v124/derkinderen20a.html %V 124 %X State-of-the-art probabilistic inference algorithms, such as variable elimination and search-based approaches, rely heavily on the order in which variables are marginalized. Finding the optimal ordering is an NP-complete problem. This computational hardness has led to heuristics to find adequate variable orderings. However, these heuristics have mostly been targeting discrete random variables. We show how variable ordering heuristics from the discrete domain can be ported to the discrete-continuous domain. We equip the state-of-the-art F-XSDD(BR) solver for discrete-continuous problems with such heuristics. Additionally, we propose a novel heuristic called bottom-up min-fill (BU-MiF), yielding a solver capable of determining good variable orderings without having to rely on the user to provide such an ordering. We empirically demonstrate its performance on a set of benchmark problems.
APA
Derkinderen, V., Heylen, E., Zuidberg Dos Martires, P., Kolb, S. & Raedt, L.. (2020). Ordering Variables for Weighted Model Integration. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), in Proceedings of Machine Learning Research 124:879-888 Available from https://proceedings.mlr.press/v124/derkinderen20a.html.

Related Material