计算边缘化贝叶斯网络的步骤数
我正在尝试制定一种算法，该算法将找到最有效的排序来消除小型贝叶斯网络（由 DAG 表示）中的节点。所有节点都是布尔值，并且可以采用两种可能的状态，除了没有后继的节点（这些节点必须具有单个观察值；否则将它们边缘化与删除它们相同）。
我最初的计划是，我将递归地选择一个没有剩余前任的剩余变量，并且对于其每个可能的状态，通过图形传播该值。这将导致所有可能的拓扑排序。
给定拓扑排序，我想找到边缘化的成本。
例如，此图：
U --> V——> W--> X——>是——> Z
只有一种这样的排序（U、V、W、X、Y、Z）。
我们可以分解关节密度 g(U,V,W,X,Y,Z) = f1(U) f2(V,U) f3(W,V) f4(X,W) f5(Y,X) f6 (Z,Y)
因此该排序对应的边缘化将是
Σ(Σ(Σ(Σ(Σ(Σ(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)
对于此图，U --> V 可以通过 4 个步骤转化为 V 的符号函数（所有 U x 都是 V。鉴于此，V --> W 同样可以是变成一个符号函数需要 4 步，所以总共需要 18 步（4+4+4+4+2，因为 Z 只有一个状态）
。可以计算这个订单的总和吗？
非常感谢您的帮助！
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!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在给定的消除顺序下边缘化的步骤数在该顺序产生的最大团中大致呈指数关系（乘以节点数）；因此，最少的步数将是所有可能的排序产生的最大团大小的指数的最小值。这相当于图的树宽。
问题中路径图的树宽为 1。
http://www. cs.berkeley.edu/~jordan/papers/statsci.ps
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