A Lattice Representation of Independence Relations

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

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

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.
Original languageEnglish
Title of host publicationProceedings of Machine Learning Research
Pages487-498
Volume72
Publication statusPublished - 2018
EventPGM 2018 Conference on Probabilistic Graphical Models - Prague
Duration: 11 Sept 201814 Sept 2018

Publication series

NameProceedings of Machine Learning Research
Volume72
ISSN (Electronic)1938-7228

Conference

ConferencePGM 2018 Conference on Probabilistic Graphical Models
CityPrague
Period11/09/1814/09/18

Keywords

  • Independence relations
  • Representation
  • Lattice-based partitioning
  • Combinatorial complexity
  • Efficiency of closure computation

Fingerprint

Dive into the research topics of 'A Lattice Representation of Independence Relations'. Together they form a unique fingerprint.

Cite this