联合树j-tree算法过程简介11.pptVIP

如果贝叶斯网络底层的无向图中包含环，标准算法（如标量消元）是低效的。 如果我们把节点的高度互联的子集转变为“超级节点”，我们可以避开环的存在。 上述的最大势算法（mcs算法，Maximum Cardinality Search），实际上也是求是否存在完美消除序列的方法，存在完美消除序列即为弦图，反之不是， * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Step 6: Choose a Root Step 7: Populate Clique Nodes For each distribution (CPT) in the original Bayes Net, put this distribution into one of the clique nodes that contains all the variables referenced by the CPT. (At least one such node must exist because of the moralization step). For each clique node, take the product of the distributions (as in variable elimination). Better Triangulation Algorithm Specifically for Bayes Nets, Based on Variable Elimination Repeat until no nodes remain: If the graph has a simplicial node, eliminate it (consider it “processed” and remove it together with all its edges).去除单纯点 Otherwise, find the node whose elimination would give the smallest potential possible. Eliminate that node, and note the need for a “fill-in” edge between any two non-adjacent nodes in the resulting potential. Add the “fill-in” edges to the original graph. Find Cliques while Triangulating(or in triangulated graph) While executing the previous algorithm: for each simplicial node, record that node with all its neighbors as a possible clique. (Then remove that node and its edges as before.) After recording all possible cliques, throw out any one that is a subset of another. The remaining sets are the cliques in the triangulated graph. O(n3), guaranteed correct only if graph is triangulated. Choose Root, Assign CPTs Junction Tree Inference Algorithm Incorporate Evidence: For each evidence variable, go to one table that includes that variable. Set to 0 all entries in that table that disagree with the evidence. Upward Step: For each leaf in the junction tree, send a message to its parent. The message is the marginal of its table, ... J.T. Inference (Continued) (Upward Step continued)… summing out any va