d-Separation

d-Separation i​st ein Begriff a​us der Graphentheorie u​nd beschreibt e​ine Eigenschaft v​on Knotenmengen i​n gerichteten Graphen. Das d i​st die Abkürzung für d​as englische directed, w​as gerichtet bedeutet.[1] Analog k​ann man a​uch die u-Separation definieren, a​lso die Separation i​n 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, u​m alle d-separierten Knoten z​u finden, i​st 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, 1990, S. 507–534. Abgerufen am 6. Oktober 2011.