D-Separation

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

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

• es gibt ein ${\displaystyle z\in Z}$, das durch eine eingehende sowie eine ausgehende Kante auf dem Pfad liegt oder
• es gibt ein ${\displaystyle z\in Z}$, das durch zwei ausgehende Kanten auf dem Pfad liegt oder
• es gibt ein ${\displaystyle z\notin Z}$, das durch zwei eingehende Kanten auf dem Pfad liegt und von dem kein Nachfolger in ${\displaystyle Z}$ enthalten ist.

Algorithmus

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

Anwendungen

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

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]).