Information Technology Reference
In-Depth Information
Die auf den Separatoren erklärten Nachrichten
M
B
C
(
s
BC
)
,dieinderobigenHerlei-
tung schon identifiziert wurden, können weiter vereinfacht werden, um schließlich
die Form aus Gleichung 25.2 zu erhalten:
x
BC
\
s
BC
D
C
BC
M
B
C
(
s
BC
)=
D
(
d
)
r
BC
=
b
B
(
b
)
D
adj
(
B
)\{
C
}
M
D
B
(
s
DB
)
\
s
BC
Weitere Propagationsverfahren
Wir wollen zum Abschluss des Kapitels zwei verwandte Evidenzpropagationsver-
fahren ansprechen. Informationen zu weiteren Verfahren finden sich u. a. in [Castillo
u. a. 1997, Borgelt u. a. 2009].
Das von uns beschriebene Verfahren [Jensen 1996, 2001, Jensen u. Nielsen 2007]
erlaubt es, beliebige gerichtete (jedoch azyklische) Graphenstrukturen als Ausgangs-
netz zu verwenden. Hat man es mit einfacheren Strukturen wie Bäumen zu tun, so
können auch weniger komplexe Algorithmen eingesetzt werden. Ein Vertreter hier-
für stellen Polybaum-Propagationsverfahren dar [Pearl 1988]. Da es sich bei Poly-
bäumen um einfach zusammenhängende Strukturen handelt (d. h. um einen Gra-
phen, der in zwei separate Teilgraphen zerfällt, sobald eine beliebige Kante entfernt
wird), ist der Propagationspfad schon ohne Transformation in eine Sekundärstruk-
tur eindeutig, weshalb der Algorithmus auf dem Originalgraphen arbeiten kann. Es
werden aufgrund der Kantenrichtungen zwei Nachrichtenarten unterschieden:
-
Nachrichten werden von Kind- zu Elternknoten gesendet, während
-Nachrichten
von den Eltern- zu den Kindknoten versandt werden. Selbstverständlich kann man
auch bei Polybäumen den Verbundbaum-Algorithmus verwenden, was dazu führt,
dass Knoten samt ihren Elternknoten zu einer Clique werden.
Eine weitere Technik, die nicht zwingend auf Graphenstrukturen basiert, ist die
sog. Bucket-Eliminierung [Dechter 1996, Zhang u. Poole 1996]. Hat man eine Fak-
torisierung einer Wahrscheinlichkeitsverteilung gegeben, lässt sich ein Attribut
eli-
minieren
,indemmandasProduktüberalledasAttributenthalteneFaktorensum-
miert. Durch sukzessive Summierung lässt sich damit ein Zielattribut isolieren. Die
Effizienz dieses Verfahrens ist stark von der Wahl der Summierungsreihenfolge ab.
Ein bedingter Unabhängigkeitsgraph kann hier mit Hilfe seiner Kanten die Summie-
rungsreihenfolge vorgeben.
