A Lattice Representation of Independence Relations

Linda C. van der Gaag, Marco Baioletti, Janneke H. Bolt
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:487-498, 2018.

Abstract

Independence relations in general include exponentially many statements of independence, that is, exponential in terms of the number of variables involved. These relations are typically fully characterised however, by a small set of such statements and an associated set of derivation rules. While various computational problems on independence relations can be solved by manipulating these smaller sets without the need to explicitly generate the full relation, existing algorithms are still associated with often prohibitively high running times. In this paper, we introduce a lattice representation for sets of independence statements, which provides further insights in the structural properties of independence and thereby renders the algorithms for some well-known problems on independence relations less demanding. By means of experimental results, in fact, we demonstrate a substantial gain in efficiency of closure computation of semi-graphoid independence relations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-van-der-gaag18a, title = {A Lattice Representation of Independence Relations}, author = {{van der Gaag}, Linda C. and Baioletti, Marco and Bolt, Janneke H.}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {487--498}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/van-der-gaag18a/van-der-gaag18a.pdf}, url = {https://proceedings.mlr.press/v72/van-der-gaag18a.html}, abstract = {Independence relations in general include exponentially many statements of independence, that is, exponential in terms of the number of variables involved. These relations are typically fully characterised however, by a small set of such statements and an associated set of derivation rules. While various computational problems on independence relations can be solved by manipulating these smaller sets without the need to explicitly generate the full relation, existing algorithms are still associated with often prohibitively high running times. In this paper, we introduce a lattice representation for sets of independence statements, which provides further insights in the structural properties of independence and thereby renders the algorithms for some well-known problems on independence relations less demanding. By means of experimental results, in fact, we demonstrate a substantial gain in efficiency of closure computation of semi-graphoid independence relations.} }
Endnote
%0 Conference Paper %T A Lattice Representation of Independence Relations %A Linda C. van der Gaag %A Marco Baioletti %A Janneke H. Bolt %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-van-der-gaag18a %I PMLR %P 487--498 %U https://proceedings.mlr.press/v72/van-der-gaag18a.html %V 72 %X Independence relations in general include exponentially many statements of independence, that is, exponential in terms of the number of variables involved. These relations are typically fully characterised however, by a small set of such statements and an associated set of derivation rules. While various computational problems on independence relations can be solved by manipulating these smaller sets without the need to explicitly generate the full relation, existing algorithms are still associated with often prohibitively high running times. In this paper, we introduce a lattice representation for sets of independence statements, which provides further insights in the structural properties of independence and thereby renders the algorithms for some well-known problems on independence relations less demanding. By means of experimental results, in fact, we demonstrate a substantial gain in efficiency of closure computation of semi-graphoid independence relations.
APA
van der Gaag, L.C., Baioletti, M. & Bolt, J.H.. (2018). A Lattice Representation of Independence Relations. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:487-498 Available from https://proceedings.mlr.press/v72/van-der-gaag18a.html.

Related Material