On Relaxing Determinism in Arithmetic Circuits

Arthur Choi, Adnan Darwiche
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:825-833, 2017.

Abstract

The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-choi17a, title = {On Relaxing Determinism in Arithmetic Circuits}, author = {Arthur Choi and Adnan Darwiche}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {825--833}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/choi17a/choi17a.pdf}, url = {https://proceedings.mlr.press/v70/choi17a.html}, abstract = {The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).} }
Endnote
%0 Conference Paper %T On Relaxing Determinism in Arithmetic Circuits %A Arthur Choi %A Adnan Darwiche %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-choi17a %I PMLR %P 825--833 %U https://proceedings.mlr.press/v70/choi17a.html %V 70 %X The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).
APA
Choi, A. & Darwiche, A.. (2017). On Relaxing Determinism in Arithmetic Circuits. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:825-833 Available from https://proceedings.mlr.press/v70/choi17a.html.

Related Material