Poset Representations for Sets of Elementary Triplets

L. C. van der Gaag, J. H. Bolt
Proceedings of the 10th International Conference on Probabilistic Graphical Models, PMLR 138:521-532, 2020.

Abstract

Semi-graphoid independence relations, composed of independence triplets, are typically exponentially large in the number of variables involved. For compact representation of such a relation, just a subset of its triplets, called a basis, are listed explicitly, while its other triplets remain implicit through a set of derivation rules. Two types of basis were defined for this purpose, which are the dominant-triplet basis and the elementary-triplet basis, of which the latter is commonly assumed to be significantly larger in size in general. In this paper we introduce the elementary po-triplet as a compact representation of multiple elementary triplets, by using separating posets. By exploiting this new representation, the size of an elementary-triplet basis can be reduced considerably. For computing the elementary closure of a starting set of po-triplets, we present an elegant algorithm that operates on the least and largest elements of the separating posets involved.

Cite this Paper

BibTeX
@InProceedings{pmlr-v138-van-der-gaag20b, title = {Poset Representations for Sets of Elementary Triplets}, author = {{van der Gaag}, L. C. and Bolt, J. H.}, booktitle = {Proceedings of the 10th International Conference on Probabilistic Graphical Models}, pages = {521--532}, year = {2020}, editor = {Jaeger, Manfred and Nielsen, Thomas Dyhre}, volume = {138}, series = {Proceedings of Machine Learning Research}, month = {23--25 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v138/van-der-gaag20b/van-der-gaag20b.pdf}, url = {https://proceedings.mlr.press/v138/van-der-gaag20b.html}, abstract = {Semi-graphoid independence relations, composed of independence triplets, are typically exponentially large in the number of variables involved. For compact representation of such a relation, just a subset of its triplets, called a basis, are listed explicitly, while its other triplets remain implicit through a set of derivation rules. Two types of basis were defined for this purpose, which are the dominant-triplet basis and the elementary-triplet basis, of which the latter is commonly assumed to be significantly larger in size in general. In this paper we introduce the elementary po-triplet as a compact representation of multiple elementary triplets, by using separating posets. By exploiting this new representation, the size of an elementary-triplet basis can be reduced considerably. For computing the elementary closure of a starting set of po-triplets, we present an elegant algorithm that operates on the least and largest elements of the separating posets involved.} }
Endnote
%0 Conference Paper %T Poset Representations for Sets of Elementary Triplets %A L. C. van der Gaag %A J. H. Bolt %B Proceedings of the 10th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2020 %E Manfred Jaeger %E Thomas Dyhre Nielsen %F pmlr-v138-van-der-gaag20b %I PMLR %P 521--532 %U https://proceedings.mlr.press/v138/van-der-gaag20b.html %V 138 %X Semi-graphoid independence relations, composed of independence triplets, are typically exponentially large in the number of variables involved. For compact representation of such a relation, just a subset of its triplets, called a basis, are listed explicitly, while its other triplets remain implicit through a set of derivation rules. Two types of basis were defined for this purpose, which are the dominant-triplet basis and the elementary-triplet basis, of which the latter is commonly assumed to be significantly larger in size in general. In this paper we introduce the elementary po-triplet as a compact representation of multiple elementary triplets, by using separating posets. By exploiting this new representation, the size of an elementary-triplet basis can be reduced considerably. For computing the elementary closure of a starting set of po-triplets, we present an elegant algorithm that operates on the least and largest elements of the separating posets involved.
APA
van der Gaag, L.C. & Bolt, J.H.. (2020). Poset Representations for Sets of Elementary Triplets. Proceedings of the 10th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 138:521-532 Available from https://proceedings.mlr.press/v138/van-der-gaag20b.html.

Related Material