Tree Decomposition methodsChapter 9ICS-275Spring 2010Radcliffe2Tree-solvingBelief updating (sum-prod)MPE (max-prod)CSP – consistency (projection-join)#CSP (sum-prod)P(X)P(Y|X) P(Z|X)P(T|Y) P(R|Y) P(L|Z) P(M|Z))(XmZX)(XmXZ)(ZmZM)(ZmZL)(ZmMZ)(ZmLZ)(XmYX)(XmXY)(YmTY)(YmYT)(YmRY)(YmYRTrees are processed in linear time and memoryRadcliffe3Inference and TreewidthEKFLHCBAMGJDABCBDEFDGFEFHFHKHJ KLMtreewidth = 4 - 1 = 3treewidth = (maximum cluster size) - 1The dual graph of a constraint problem associates a node with each constraint scope and an arc for each two nodes sharing variables. This transforms anon-binary constraint problem into a binary one, called the dual problem:Variables: constraints,Domains: legal tuples of the relationBinary constraints between any two dual variables that share original variables, enforcing equality on the values assigned to the shared variables. Therefore, if a problem's dual graph happens to be a tree, it can be solved by the tree-solving algorithm.It turns out, however, that sometimes, even when the dual graph does not look like aThe Dual problem/The acyclic problemICS 275, Fall 2010Dual Constraint Problems Constraints can be: C= AVE F=AVE and so on…ICS 275, Fall 2010Dual Constraint Problems Constraints can be: C= AVE F=AVE and so on…ICS 275, Fall 2010Graph concepts reviews:Hyper graphs and dual graphs A hypergraph is H = (V,S) , V= {v_1,..,v_n} and a set of subsets Hyperegdes: S={S_1, ..., S_l }. Dual graphs of a hypergaph: The nodes are the hyperedges and a pair of nodes is connected if they share vertices in V. The arc is labeled by the shared vertices.  A primal graph of a hypergraph H = (V,S) has V as its nodes, and any two nodes are connected by an arc if they appear in the same hyperedge. if all the constraints of a network R are binary, then its hypergraph is identical to its primal graph.ICS 275, Fall 2010Acyclic Networks The running intersection property (connectedness): An arc can be removed from the dual graph if the variables labeling the arcs are shared along an alternative path between the two endpoints.  Join graph: An arc subgraph of the dual graph that satisfies the connectedness property.  Join-tree: a join-graph with no cycles Hypertree: A hypergraph whose dual graph has a join-tree. Acyclic network: is one whose hypergraph is a hypertree.ICS 275, Fall 2010Example Constraints are:  R_{ABC} = R_{AEF} = R_{CDE} = {(0,0,1) (0,1,0)(1,0,0)} R_{ACE} = { (1,1,0) (0,1,1) (1,0,1) }. d= (R_{ACE},R_{CDE},R_{AEF},R_{ABC}). • When processing R_{ABC}, its parent relation is R_{ACE}; • processing R_{AEF} we generate relation • processing R_{CDE} we generate: • R_{ACE} = \pi_{ACE} ( R_{ACE} x R_{CDE} ) = {(0,1,1)}.  A solution is generated by picking the only allowed tuple for R_{ACE}, A=0,C=1,E=1, extending it with a value for D that satisfies R_{CDE}, which is only D=0, and then similarly extending the assignment to F=0 and B=0, to satisfy R_{AEF} and R_{ABC}.)}1,0,1)(1,1,0{()( ABCACEACEACERRR)}1,1,0{()( AEFACEACEACERRRICS 275, Fall 2010Solving acyclic networks Algorithm acyclic-solving applies a tree algorithm to the join-tree. It applies (a little more than) directional relational arc-consistency from leaves to root. Complexity: acyclic-solving is O(r l log l) steps, where r is the number of constraints and l bounds the number of tuples in each constraint relation (It assumes that join of two relations when one’s scope is a subset of the other can be done in linear time)ICS 275, Fall 2010Recognizing acyclic networks Dual-based recognition: • perform maximal spanning tree over the dual graph and check connectedness of the resulting tree.• Dual-acyclicity complexity is O(e^3) Primal-based recognition: • Theorem (Maier 83): A hypergraph has a join-tree iff its primal graph is chordal and conformal.• A chordal primal graph is conformal relative to a constraint hypergraph iff there is a one-to-one mapping between maximal cliques and scopes of constraints.ICS 275, Fall 2010Primal-based recognition Check cordality using max-cardinality ordering. Test conformality Create a join-tree: connect every clique to an earlier clique sharing maximal number of variablesICS 275, Fall 2010Tree-based clustering Convert a constraint problem to an acyclic-one: group subset of constraints to clusters until we get an acyclic problem. Tree-decomposition: Hypertree embedding of a hypergraph H= (X,H) is a hypertree S = (X, S) s.t., for every h in H there is h_1 in S s.t. h is included in h_1. This yield algorithm join-tree clustering and tree-decomposition in general Hypertree decomposition: Hypertree partitioning of a hypergraph H = (X,H) is a hypertree S = (X, S) s.t., for every h in H there is h_1 in S s.t. h is included in h_1 and X is the union of scopes in h_1.ICS 275, Fall 2010Join-tree clustering Input: A constraint problem R =(X,D,C) and its primal graph G = (X,E). Output: An equivalent acyclic constraint problem and its join-tree: T= (X,D, {C ‘}) 1. Select an d = (x_1,...,x_n) 2. Triangulation(create the induced graph along $d$ and call it G^*: ) for j=n to 1 by -1 do  E  E U {(i,k)| (i,j) in E,(k,j) in E } 3. Create a join-tree of the induced graph G^*: a. Identify all maximal cliques (each variable and its parents is a clique). Let C_1,...,C_t be all such cliques,  b. Create a tree-structure T over the cliques: Connect each C_{i} to a C_{j} (j < I) with whom it shares largest subset of variables.  4. Place each input constraint in one clique containing its scope, and let P_i be the constraint subproblem associated with C_i. 5. Solve P_i and let {R'}_i $ be its set of solutions. 6. Return C' = {R'}_1,..., {R'}_t the new set of constraints and their join-tree, T. Theorem: join-tree clustering transforms a constraint network into an acyclic networkICS 275, Fall 2010Example of tree-clusteringICS 275, Fall 2010Complexity of JTC complexity of JTC: join-tree clustering is O(r k^ (w*(d)+1)) time and O(nk^(w*(d)+1)) space, where k is the maximum domain size and w*(d) is the induced width of the ordered graph. The complexity of acyclic-solving is O(n w*(d) (log k) k^(w*(d)+1))ICS 275, Fall 2010Let R=<X,D,C> be a CSP problem. A tree decomposition for R is <T,,>, such thatT=(V,E) is a tree associates a set of variables (v)X with each