Die Berechnung der Anzahl der Schritte ein Bayes-Netzwerk marginalisieren

Question

Ich versuche, einen Algorithmus zu machen, die die effizienteste Anordnung zur Beseitigung von Knoten in einem kleinen Bayes-Netzwerk finden (von einer DAG dargestellt). Alle Knoten sind boolean und zwei mögliche Zustände annehmen kann, mit Ausnahme von Knoten ohne Nachfolger (diese Knoten einen einzigen beobachteten Wert haben muss, andernfalls sie aus marginalisieren das gleiche ist, sie als zu entfernen)

.

Mein ursprünglicher Plan war, dass ich rekursiv eine verbleibende Variable wählen würde, die keine verbleibenden Vorgänger hat und für jeden seiner möglichen Zustände, propagieren den Wert durch den Graphen. Diese in allen möglichen topologischen Anordnungen führen würden.

eine topologische Ordnung Da wollte ich die Kosten der Marginalisierung finden.

Zum Beispiel dieses Diagramm:

U --> V --> W --> X --> Y --> Z

hat nur eine solche Anordnung (U, V, W, X, Y, Z).

Wir faktorisieren die gemeinsame Dichte g (U, V, W, X, Y, Z) = f1 (U) f2 (V, U) f3 (W, V) f4 (X, W) f5 (Y, X) f6 (Z, Y)

So ist die Marginalisierung dieser Bestellung entspricht, wird sein

S (S (S (S (S (S (G (W, X, Y, Z), Z), Y), X), W), V), U) =
S (S (S (S (S (S (f1 (U) f2 (V, U) f3 (W, V) f4 (X, W) f5 (Y, X) f6 (Z, Y), Z), Y), X), W), V), U) =
S (f1 (U)
S (f2 (V, U)
S (f3 (W, V)
S (f4 (X, W)
S (f5 (Y, X)
S (f6 (Z, Y), Z)
, Y)
, X)
, W)
, V)
, U)

Für dieses Diagramm U --> V in eine symbolische Funktion von V in 4 Stufen (alle U x gedreht werden alle V. Da, V --> W kann ebenfalls in eine symbolische Funktion in 4 Schritten gedreht werden. Also insgesamt, wird es 18 Schritte unternehmen, um (4 + 4 + 4 + 4 + 2, weil Z nur ein Zustand hat).

Hier ist meine Frage: Wie kann ich die schnellste Anzahl der Schritte bestimmen, dass diese Summe für diese Bestellung berechnet werden kann?

Vielen Dank für Ihre Hilfe!

Answer 1

Die Anzahl der Schritte zu marginalize mit einer bestimmten Eliminierungs Bestellung in der größten Clique durch diese Anordnung (mal die Anzahl der Knoten) erzeugte grob exponentiell sein; deshalb wird die geringste Anzahl von Schritten das Minimum der exponentiellen der größten von allen möglichen Anordnungen hergestellt Clique Größe. Dies entspricht dem Baumweite des Graphen.

Das Baumweite des Wegs Graphen in der Frage ist 1.

http://www.cs.berkeley.edu/~jordan/ Papiere / statsci.ps