On Minimum Elementary-Triplet Bases for Independence Relations

Janneke Bolt, Linda C. van der Gaag
Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, PMLR 103:32-37, 2019.

Abstract

A semi-graphoid independence relation is a set of independence statements, called triplets, and is typically exponentially large in the number of variables involved. For concise representation of such a relation, a subset of its triplets is listed in a so-called basis; its other triplets are defined implicitly through a set of axioms. An elementary-triplet basis for this purpose consists of all elementary triplets of a relation. Such a basis however, may include redundant information. In this paper we provide two lower bounds on the size of an elementary-triplet basis in general and an upper bound on the size of a minimum elementary-triplet basis. We further specify the construction of an elementary-triplet basis of minimum size for restricted relations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v103-bolt19a, title = {On Minimum Elementary-Triplet Bases for Independence Relations}, author = {Bolt, Janneke and {van der Gaag}, Linda C.}, booktitle = {Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications}, pages = {32--37}, year = {2019}, editor = {De Bock, Jasper and de Campos, Cassio P. and de Cooman, Gert and Quaeghebeur, Erik and Wheeler, Gregory}, volume = {103}, series = {Proceedings of Machine Learning Research}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v103/bolt19a/bolt19a.pdf}, url = {https://proceedings.mlr.press/v103/bolt19a.html}, abstract = {A semi-graphoid independence relation is a set of independence statements, called triplets, and is typically exponentially large in the number of variables involved. For concise representation of such a relation, a subset of its triplets is listed in a so-called basis; its other triplets are defined implicitly through a set of axioms. An elementary-triplet basis for this purpose consists of all elementary triplets of a relation. Such a basis however, may include redundant information. In this paper we provide two lower bounds on the size of an elementary-triplet basis in general and an upper bound on the size of a minimum elementary-triplet basis. We further specify the construction of an elementary-triplet basis of minimum size for restricted relations.} }
Endnote
%0 Conference Paper %T On Minimum Elementary-Triplet Bases for Independence Relations %A Janneke Bolt %A Linda C. van der Gaag %B Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications %C Proceedings of Machine Learning Research %D 2019 %E Jasper De Bock %E Cassio P. de Campos %E Gert de Cooman %E Erik Quaeghebeur %E Gregory Wheeler %F pmlr-v103-bolt19a %I PMLR %P 32--37 %U https://proceedings.mlr.press/v103/bolt19a.html %V 103 %X A semi-graphoid independence relation is a set of independence statements, called triplets, and is typically exponentially large in the number of variables involved. For concise representation of such a relation, a subset of its triplets is listed in a so-called basis; its other triplets are defined implicitly through a set of axioms. An elementary-triplet basis for this purpose consists of all elementary triplets of a relation. Such a basis however, may include redundant information. In this paper we provide two lower bounds on the size of an elementary-triplet basis in general and an upper bound on the size of a minimum elementary-triplet basis. We further specify the construction of an elementary-triplet basis of minimum size for restricted relations.
APA
Bolt, J. & van der Gaag, L.C.. (2019). On Minimum Elementary-Triplet Bases for Independence Relations. Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, in Proceedings of Machine Learning Research 103:32-37 Available from https://proceedings.mlr.press/v103/bolt19a.html.

Related Material