d-Separation

Eigenschaft von Knotenmengen in gerichteten Graphen

d-Separation ist ein Begriff aus der Graphentheorie und beschreibt eine Eigenschaft von Knotenmengen in gerichteten Graphen. Das d ist die Abkürzung für das englische directed, was gerichtet bedeutet.[1] Analog kann man auch die u-Separation definieren, also die Separation in ungerichteten Graphen.

Definition

Bearbeiten

Seien   und   zwei nichtleere disjunkte Knotenmengen eines Graphen und   eine beliebige Knotenmenge. Dann heißt   d-separiert von   gegeben  , wenn für jeden ungerichteten Pfad von   nach   gilt, dass er durch   blockiert ist. Ein Pfad heißt blockiert durch   falls:

  • es gibt ein  , das durch eine eingehende sowie eine ausgehende Kante auf dem Pfad liegt oder
  • es gibt ein  , das durch zwei ausgehende Kanten auf dem Pfad liegt oder
  • es gibt ein  , das durch zwei eingehende Kanten auf dem Pfad liegt und von dem kein Nachfolger in   enthalten ist.

Algorithmus

Bearbeiten

Ein effizientes Verfahren, um alle d-separierten Knoten zu finden, ist der Bayes-Ball-Algorithmus.

Anwendungen

Bearbeiten

Bayessche Netze sind Modelle für die gemeinsame Verteilung einer Menge von Zufallsvariablen. Sie stellen Abhängigkeiten durch gerichtete Kanten in einem Graphen dar, wobei die Knoten den Zufallsvariablen entsprechen. Man kann zeigen, dass in Bayesschen Netzen die Unabhängigkeit von Zufallsvariablen mit der d-Separiertheit der Knoten zusammenhängt.

Quellenangaben

Bearbeiten
  1. Dan Geiger, Thomas Verma, Judea Pearl: Identifying independence in Bayesian Networks. In: Networks. 20. Jahrgang, 1990, S. 507–534 (ucla.edu [PDF; abgerufen am 6. Oktober 2011]).