Dynamic Cutset Networks

Chiradeep Roy, Tahrima Rahman, Hailiang Dong, Nicholas Ruozzi, Vibhav Gogate
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:3106-3114, 2021.

Abstract

Tractable probabilistic models (TPMs) are appealing because they admit polynomial-time inference for a wide variety of queries. In this work, we extend the cutset network (CN) framework, a powerful sub-class of TPMs that often outperforms probabilistic graphical models in terms of prediction accuracy, to the temporal domain. This extension, dubbed dynamic cutset networks (DCNs), uses a CN to model the prior distribution and a conditional CN to model the transition distribution. We show that although exact inference is intractable when arbitrary conditional CNs are used, particle filtering is efficient. To ensure tractability of exact inference, we introduce a novel constrained conditional model called AND/OR conditional cutset networks and show that under certain conditions exact inference is linear in the size of the corresponding constrained DCN. Experiments on several sequential datasets demonstrate the efficacy of our framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-roy21a, title = { Dynamic Cutset Networks }, author = {Roy, Chiradeep and Rahman, Tahrima and Dong, Hailiang and Ruozzi, Nicholas and Gogate, Vibhav}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {3106--3114}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/roy21a/roy21a.pdf}, url = {https://proceedings.mlr.press/v130/roy21a.html}, abstract = { Tractable probabilistic models (TPMs) are appealing because they admit polynomial-time inference for a wide variety of queries. In this work, we extend the cutset network (CN) framework, a powerful sub-class of TPMs that often outperforms probabilistic graphical models in terms of prediction accuracy, to the temporal domain. This extension, dubbed dynamic cutset networks (DCNs), uses a CN to model the prior distribution and a conditional CN to model the transition distribution. We show that although exact inference is intractable when arbitrary conditional CNs are used, particle filtering is efficient. To ensure tractability of exact inference, we introduce a novel constrained conditional model called AND/OR conditional cutset networks and show that under certain conditions exact inference is linear in the size of the corresponding constrained DCN. Experiments on several sequential datasets demonstrate the efficacy of our framework. } }
Endnote
%0 Conference Paper %T Dynamic Cutset Networks %A Chiradeep Roy %A Tahrima Rahman %A Hailiang Dong %A Nicholas Ruozzi %A Vibhav Gogate %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-roy21a %I PMLR %P 3106--3114 %U https://proceedings.mlr.press/v130/roy21a.html %V 130 %X Tractable probabilistic models (TPMs) are appealing because they admit polynomial-time inference for a wide variety of queries. In this work, we extend the cutset network (CN) framework, a powerful sub-class of TPMs that often outperforms probabilistic graphical models in terms of prediction accuracy, to the temporal domain. This extension, dubbed dynamic cutset networks (DCNs), uses a CN to model the prior distribution and a conditional CN to model the transition distribution. We show that although exact inference is intractable when arbitrary conditional CNs are used, particle filtering is efficient. To ensure tractability of exact inference, we introduce a novel constrained conditional model called AND/OR conditional cutset networks and show that under certain conditions exact inference is linear in the size of the corresponding constrained DCN. Experiments on several sequential datasets demonstrate the efficacy of our framework.
APA
Roy, C., Rahman, T., Dong, H., Ruozzi, N. & Gogate, V.. (2021). Dynamic Cutset Networks . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:3106-3114 Available from https://proceedings.mlr.press/v130/roy21a.html.

Related Material