Poset Representations for Sets of Elementary Triplets

L.C. van der Gaag, J.H. Bolt

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the 10th International Conference on Probabilistic Graphical Models
Number of pages12
Publication statusPublished - 2020

Keywords

  • Independence relations
  • Efficiency of representation
  • Elementary closure computation

Fingerprint

Dive into the research topics of 'Poset Representations for Sets of Elementary Triplets'. Together they form a unique fingerprint.

Cite this