Computing the number of steps to marginalize a Bayesian network

Question

I'm trying to make an algorithm that will find the most efficient ordering for eliminating nodes in a small Bayesian network (represented by a DAG). All of the nodes are boolean and can take two possible states, with the exception of nodes with no successors (these nodes must have a single observed value; otherwise marginalizing them out is the same as removing them).

My original plan was that I would recursively choose a remaining variable that has no remaining predecessors and, for each of its possible states, propagate the value through the graph. This would result in all possible topological orderings.

Given a topological ordering, I wanted to find the cost of marginalizing.

For instance, this graph:

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

has only one such ordering (U,V,W,X,Y,Z).

We can factorize the joint density 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 the marginalization corresponding to this ordering will be

∑(∑(∑(∑(∑(∑(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)

For this graph, U --> V can be turned into a symbolic function of V in 4 steps (all U x all V. Given that, V --> W can likewise be turned into a symbolic function in 4 steps. So overall, it will take 18 steps (4+4+4+4+2 because Z has only one state).

Here is my question: how can I determine the fastest number of steps that this sum can be computed for this ordering?

Thanks a lot for your help!

Answer 1

The number of steps to marginalize with a given elimination ordering will be roughly exponential in the largest clique produced by that ordering (times the number of nodes); therefore, the fewest number of steps will be the minimum of the exponential of the largest clique size produced by all possible orderings. This is equivalent to the treewidth of the graph.

The treewidth of the path graph in the question is 1.

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