An algorithm for reading dependencies from the minimal undirected independence map of a graphoid that satisfies weak transitivity

Jose M. Peña, Roland Nilsson, Johan Björkegren, Jesper Tegner

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

We present a sound and complete graphical criterion for reading dependencies from the minimal undirected independence map G of a graphoid M that satisfies weak transitivity. Here, complete means that it is able to read all the dependencies in M that can be derived by applying the graphoid properties and weak transitivity to the dependencies used in the construction of G and the independencies obtained from G by vertex separation. We argue that assuming weak transitivity is not too restrictive. As an intermediate step in the derivation of the graphical criterion, we prove that for any undirected graph G there exists a strictly positive discrete probability distribution with the prescribed sample spaces that is faithful to G. We also report an algorithm that implements the graphical criterion and whose running time is considered to be at most O(n2(e + n)) for n nodes and e edges. Finally, we illustrate how the graphical criterion can be used within bioinformaties to identify biologically meaningful gene dependencies.

Original languageEnglish (US)
Pages (from-to)1071-1094
Number of pages24
JournalJournal of Machine Learning Research
Volume10
StatePublished - Jan 1 2009

Keywords

  • Bioinformaties
  • Graphical models
  • Graphoids
  • Vertex separation
  • Weak transitivity

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'An algorithm for reading dependencies from the minimal undirected independence map of a graphoid that satisfies weak transitivity'. Together they form a unique fingerprint.

Cite this