Report

Tree Clustering for Constraint Networks By Rina Dechter & Judea Pearl Artificial Intelligence, Oct 1988 Chris Reeson Advanced Constraint Processing Fall 2009 1 Overview • Contributions of the Paper • Context of the Paper • Algorithms – Tree Clustering – Adaptive Consistency • Relative Merits • Conclusion • Related algorithms 2 Contributions of the Paper • Introduces Tree Clustering (T-C) for backtrackfree search • Introduces the Adaptive Consistency (A-C) algorithm • Compares the two algorithms 3 Context • Two ways to restrict CSPs to make finding the minimal CSP efficient – Topology of constraint graph – Types of constraints • T-C & A-C – Target the topology: tree – Are applicable to binary & non-binary CSPs • Two ways to transform a constraint graph into a tree – Remove redundant arcs in dual graphs (join tree) – Form larger clusters of c-variables (simulates a join tree) 4 Definitions • Hyper, dual, and primal graphs Hypergraph Dual graph Primal graph h5 8 1 h6 9 h8 2 h7 3 h2 13 h8 8 7 h3 h2 6 3 2 1 11 9 4 10 h4 13 5 h4 h7 h6 4 12 h1 h5 h3 10 11 8 5 12 8 7 6 • The discussion focuses on primal graphs for simplicity 5 From Join Graph to Join Tree • Join Graph – Start w/ the dual graph, remove redundant edges while maintaining the connectedness property – Connectedness property: For each two nodes sharing a variable, there is at least one path of labeled arcs containing the shared variable A ABC AEF C AE AC ACE E CDE CE • Join Tree – When the join graph is a tree, the dual CSP can be solved BT free w/ directional arc consistency – What if there isn’t a join tree? The idea for Tree Clustering ABC AEF AE AC ACE CE CDE Motivating Problem Constraint Graph C<A C A C≠D D A solution 1 4 2 3 3 4 A≠B D<A C<B B D<B F>B E>B F E G>F G>E G 5 Domains: {1, 2, 3, 4, 5} 7 Overview • Contributions of the Paper • Context of the Paper • Algorithms – Tree Clustering (T-C) – Adaptive Consistency (A-C) • Relative Merits • Conclusion • Related Algorithms 8 Tree Clustering (T-C): Idea • A CSP organized as a join tree can be solved efficiently • Tree Clustering Algorithm – Solves a CSP by breaking it into subproblems – Triangulates the primal graph – Solves subproblems & combines the solutions C A C A ABCD BD D B D BED B DE F E F DFE E EF G G EFG 9 Tree Clustering (T-C): Algorithm 1. Triangulate the primal graph 2. Identify all the maximal cliques in the primal chordal graph 3. Form a join tree 4. Solve the subproblems – Each cluster becomes single variable 5. Solve the tree problem – – Perform DAC from leaves to root Instantiate BT-free from root to leaves C A D B F E G 1 4 342, 351, 221, … 2 3 DFE 234, 415, 153, … 3 4 EFG 435, 123, 112, … ABCD 4312, 5312, 5432, … BD BED DE EF 5 10 Tree Clustering (T-C): Costs 1. Given a CSP and its primal graph generate a chordal primal graph: O(n2) 2. Identify all the maximal cliques in the primal chordal graph: O(|E’|) 3. Form the dual graph: O(n) 4. Solve the sub problems: O(kr) where k=domain size 5. Solve the tree problem: O(n ∙ t log t)… C A D B F E G 1 4 342, 351, 221, … 2 3 DFE 234, 415, 153, … 3 4 EFG 435, 123, 112, … ABCD 4312, 5312, 5432, … BD BED DE EF 5 11 Tree Clustering (T-C): Total Cost • Dominated by O(n ∙ t log t) – t is the largest number of solutions in a cluster, t ≤ kr – Time: O(n ∙ kr ∙ r log k) = O(nr ∙ kr ) – Space: O(n ∙ kr ) 12 Overview • Contributions of the Paper • Context of the Paper • Algorithms – Tree Clustering (T-C) – Adaptive Consistency (A-C) • Relative Merits • Conclusion • Related Algorithms 13 Adaptive Consistency (A-C) • An ordered constraint graph is backtrack-free if the level of directional strong consistency along this order is greater than the width of the ordered graph • Beware – Enforcing i-consistency for i > 2 often requires the addition of constraints which increase the width 14 Adaptive Consistency (A-C): Idea • Given an ordering d, – d-i-consistency is defined recursively – letting i change dynamically from node to node • (A-C later redefined as bucket elimination) 15 Adaptive Consistency: Algorithm A 1. 2. 3. 4. For i=n downto 1 do Steps 2-4 Compute PARENTS(Xi) Connect all PARENTS(Xi) Perform Consistency(Xi, PARENTS(Xi)) joining the constraints between Xi & its parents 5. Build a solution BT-free in the ordering (X1, …, Xn) C A D B F E C B D E F G G A C tighten A by 2 consist B ACB join CB join AC to tighten AC by 3c D BE join CB join AC to tighten ACB by 4c E tighten D by 2 consist F EF join DE to tighten DE by 3 consist G GF join GE to tighten EF by 3 consist 16 Adaptive Consistency: Cost • Time: O(n ∙ exp(W*(d) + 1)), see Dechter page 109 • Space: O(n ∙ kW*(d)) 17 Overview • Contributions of the Paper • Context of the Paper • Algorithms – Tree Clustering (T-C) – Adaptive Consistency (A-C) • Relative Merits • Conclusion • Related Algorithms 18 Relative Merits A • Arcs resulting from triangulation match arcs added by adaptive consistency, for the same ordering • Every cluster in T-C is represented in AC by a series of smaller constraints • Similar bounds – W*(d) + 1 = the size of the largest clique • A-C eliminates the redundancy of generated solutions • T-C enumerates all solutions that A-C represents via constraints. C A D B F E C B D E F G G A C A D B F E C B D E F G G 19 Conclusions • Tree clustering groups c-nodes into a tree capable of supporting query answering backtrack-free • Useful in systems that need to answer many questions about a dataset and where the environmental conditions undergo local changes • Recently, researchers have started looking at T-C for solving the CSP, see BTD by Jégou & Terrioux (and others in soft CSPs) 20 Note On Triangulation • Find the triangulated graph w/ smallest maximum clique: NP-hard • Heuristics – Operation: when eliminating a node, connect all its neighbors, to form a clique (fill edges) – H1: choose the node w/ smallest degree – H2: choose the node that, after elimination, yields the smallest number of fill edges – H3: Given any ordering (e.g., maximal cardinality ordering), moralize the graph • Elimination order is the reverse of instantiation order • Elimination order of a triangulated graph is called a perfect elimination scheme – In this ordering, every node is simplicial: forms a clique w/ its neighbors – If you follow elimination order, no fill edges need to be added Maximal Cardinality Ordering • An approximation of min. width ordering • Choose a node arbitrarily a simplicial node • Among the remaining nodes, choose the one that is connected to the maximum number of already chosen nodes, break ties arbitrarily • Repeat… • Reverse the final order Tsang 6.2.4 Dechter Fig 4.5 Two Additional Algorithms • Maximal Cliques of the triangulated graph • Join Tree of the triangulated graph