Information Technology Reference
In-Depth Information
Abbildung 25.1: Der graue Knoten separiert
die Knoten in den vier Teilbäumen voneinan-
der. Wir werden diese Idee aufgreifen und da-
mit die Evidenzpropagation vereinfachen.
Knotens in mehrere isolierte Teilbäume, d. h., ein instanziiertes Attribut A (in einem
ungerichteten Baum) macht die Attribute der entstehenden Teilbäume unabhängig,
wie in Abbildung 25.1 illustriert ist. Eine ähnliche Separierung findet auch in gerich-
teten Bäumen statt: Hier werden bei Instanziierung eines Attributes A die Knoten
der Kindbäume (also der Teilbäume, die einen Kindknoten von A als Wurzel haben)
bedingt unabhängig voneinander. Allerdings muss bei Polybäumen der Möglichkeit
mehrerer Elternknoten von A Rechnung getragen werden. Denn diese haben mit A
ja eine konvergierende Verbindung, die sich durch Instanziieren von A öffnet. Weiter
verkompliziert wird der Sachverhalt beim Betrachten allgemeiner Graphen, also be-
liebiger ungerichteter Graphen oder beliebiger gerichteter, azyklischer Graphen: Da
es hier zwischen zwei Knoten mehr als einen Pfad geben kann, ist ein eindeutiger
Evidenzfluss nicht mehr automatisch gewährleistet. Zur Lösung all der angespro-
chenen Probleme sind jeweilige Algorithmen entwickelt worden. Wir wenden uns
einer Lösung zu, die mit allen o. g. Graphenstrukturen umgehen kann.
Die Evidenzpropagation selbst wird auf einem Verbundbaum durchgeführt. Die
Baumstruktur garantiert die Eindeutigkeit des Evidenzflusses, während die Wahl
eines Verbundgraphen dadurch begründet ist, dass jeder allgemeine Graph (gerich-
tet oder ungerichtet) in einen semantisch äquivalenten Verbundbaum transformiert
werden kann. Semantisch äquivalent bedeutet hier, dass der resultierende Verbund-
baumweiterhin eine bedingte Unabhängigkeitskarte der zugrunde liegenden Vertei-
lung sein muss.
Wie ein beliebiger ungerichteter Graph in einen Verbundbaum transformiert
werden kann, haben wir in Abschnitt 23.2.2 gesehen. Konzentrieren wir uns da-
her auf die Transformation eines beliebigen gerichteten, azyklischen Graphen in
einen Verbundbaum. Die Idee, einfach die Kantenrichtungen zu ignorieren und so-
mit einen äquivalenten ungerichteten Graphen zu erhalten, scheitert leider, wie man
sich leicht überzeugt. Betrachten wir den gerichteten, azyklischen Graphen G 1 in
Abbildung 25.2. Dieser kodiert ausschließlich 3 die folgenden bedingten Unabhän-
gigkeiten:
I G 1 = {
A G 1 D | C ,
B G 1 D | C , A G 1 B |
}
3 Die symmetrischen Pendants der Unabhängigkeiten gelten selbstverständlich, werden jedoch aus
Gründen der Übersichtlichkeit nicht mit aufgeführt.
Search WWH ::




Custom Search