D-Separation

D-Separiertheit ist ein Begriff aus der Graphentheorie und beschreibt eine Eigenschaften 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 Separierung in ungerichteten Graphen.

Definition

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

• es gibt ein $v_i \in Z$, das durch eine eingehende sowie eine ausgehende Kante auf dem Pfad liegt oder
• es gibt ein $v_i \in Z$, das durch zwei ausgehende Kanten auf dem Pfad liegt oder
• es gibt ein $v_i \notin Z$, das durch zwei eingehende Kanten auf dem Pfad liegt und von dem kein Nachfolger in 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, Verma, Thomas and Pearl, Judea: Identifying independence in Bayesian Networks. In: Networks. 20, 1990, S. 507-534. Abgerufen am 6 October 2011.