Le calcul du nombre d'étapes de marginaliser un réseau bayésien

Question

Je suis en train de faire un algorithme qui trouvera le plus efficace pour éliminer les commandes noeuds dans un petit réseau bayésien (représenté par un DAG). Tous les noeuds sont booléennes et peut prendre deux états possibles, à l'exception des noeuds sans successeurs (ces nœuds doivent avoir une valeur observée seule, sinon les marginaliser en est le même que de les enlever)

.

Mon plan initial était que je choisirais récursive une variable restante qui n'a pas prédécesseurs restants et, pour chacun de ses états possibles, propager la valeur par le graphique. Cela aboutirait à tous les ordonnancements possibles topologiques.

Etant donné un ordre topologique, je voulais trouver le coût de marginalisant.

Par exemple, ce graphique:

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

a seulement une telle commande (U, V, W, X, Y, Z).

On peut factoriser la densité g d'articulation (U, V, W, X, Y, Z) = f1 (U) f2 (V, U) f3 (W, V) f4 (X, W) f5 (Y, X) f6 (Z, Y)

la marginalisation correspondant à cette commande sera

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

Pour ce graphique, U --> V peut être transformé en une fonction symbolique de V en 4 étapes (tous les U x all V. Etant donné que, V --> W peut également être transformé en une fonction symbolique en 4 étapes. Donc dans l'ensemble, il faudra 18 étapes (4 + 4 + 4 + 4 + 2 parce que Z n'a qu'un seul état).

Voici ma question: comment puis-je déterminer le plus rapide nombre d'étapes que cette somme peut être calculée pour cette commande?

Merci beaucoup pour votre aide!

Answer 1

Le nombre d'étapes de marginalisation avec une commande d'élimination donné sera à peu près exponentielle de la plus grande clique produite par cette commande (nombre de fois le nombre de noeuds); Par conséquent, le plus petit nombre d'étapes sera le minimum de l'exponentielle de la plus grande taille clique produite par tous les ordonnancements possibles. Cela équivaut à la largeur arborescente du graphe.

Le treewidth du graphe de chemin dans la question est 1.

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