D-Separation

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.

Inhaltsverzeichnis

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.

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • séparation — [ separasjɔ̃ ] n. f. • 1314; lat. separatio 1 ♦ Action de séparer, de se séparer, fait d être séparé. ⇒ désagrégation, disjonction, dislocation, dispersion; dis . La séparation des éléments d un mélange. Séparation des isotopes (à partir d un… …   Encyclopédie Universelle

  • Separation des pouvoirs — Séparation des pouvoirs La séparation des pouvoirs est un principe de répartition des différentes fonctions de l État, qui sont confiées à différentes composantes de ce dernier. On retient le plus souvent la classification de Montesquieu, appelée …   Wikipédia en Français

  • Separation de l'Eglise et de l'Etat — Séparation de l Église et de l État Demande de traduction Separation of church and state → …   Wikipédia en Français

  • Séparation de l'église et de l'état — Demande de traduction Separation of church and state → …   Wikipédia en Français

  • Séparation de l’Église et de l’État — Séparation de l Église et de l État Demande de traduction Separation of church and state → …   Wikipédia en Français

  • separation — sep·a·ra·tion /ˌse pə rā shən/ n 1: cessation of cohabitation between a married couple by mutual agreement with intent that it be permanent; also: legal separation compare divorce ◇ In some cases in which the estrangement is extreme, a separation …   Law dictionary

  • Separation des convexes — Séparation des convexes Un exemple de séparation stricte Étant donnés deux convexes d un même plan ne se rencontrant pas, il est toujours possible de subdiviser le plan en deux demi plans de sorte que chacun contienne entièrement l un des… …   Wikipédia en Français

  • SÉPARATION DE CORPS — En droit civil français, la séparation de corps est un simple relâchement du lien conjugal. À la différence du divorce, elle existait dans le droit français ancien qui l’a reprise du droit canonique. Aussi la séparation de corps est elle parfois… …   Encyclopédie Universelle

  • Separation anxiety disorder — Separation anxiety is a psychological condition in which an individual has excessive anxiety regarding separation from home or from people to whom the individual has a strong emotional attachment (like a father and mother). Background Present in… …   Wikipedia

  • Separation of duties — (SoD) is the concept of having more than one person required to complete a task. It is alternatively called segregation of duties or, in the political realm, separation of powers.General descriptionSeparation of duties is one of the key concepts… …   Wikipedia

  • Separation — Séparation Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”