UCI ICS 161 - Approximate Solution Sampling on AND/OR search space

Unformatted text preview:

Approximate Solution Sampling ( and Counting) onAND/OR search spaceVibhav Gogate and Rina DechterDonald Bren School of Information and Computer SciencesUniversity of California, Irvine, CA 92697, USA{vgogate,dechter}@ics.uci.eduAbstract. In this paper, we describe a new algorithm that approximately solves theproblem of sampling solutions from a uniform distribution over the solutions of aconstraint network. Our new algorithm improves upon the Sampling/ImportanceResampling (SIR) component of our previous scheme of SampleSearch-SIR bytaking advantage of the decomposition implied by the network’s AND/OR searchspace. We describe how our new scheme can be modified to approximately countand lower bound the number of solutions of a constraint network. We demonstrateboth theoretically and empirically that on networks which have a favorable de-composition, our new algorithm yields far better performance than competing ap-proaches.1 IntroductionThe paper introduces a new method for approximately solving the §csp problem whichis the problem of generating solutions from a uniform distribution over the solutionsof a constraint network. As pointed out in earlier work [17, 3, 4], the §csp problem hastremendous applications in fields such as verification and probabilistic reasoning. Ourmain contribution is in improving the Sampling/Importance Resampling component ofour previous scheme of SampleSearch-SIR [7] by exploiting problem decomposition viaAND/OR search spaces for graphical models [2].SampleSearch-SIR [7] approximately solves the §csp problem as follows. First, Sam-pleSearch [4] is used to generate an initial set A of samples from the backtrack-freedistribution QF. Second, each sample is weighed by the reciprocal of the probability ofit being generated from QF. Third, a distribution M is formed over the initial set A bynormalizing the weights and finally a smaller set of samples B is drawn from M . Thefinal step is often called as the resampling step. It was shown by [12] that as the size ofthe initial set A increases the distribution over the samples generated in the resamplingstep (i.e. B) will converge to the uniform distribution over the solutions.In our new scheme, called AO-SIR, the first step of generating the initial set of sam-ples from QF(using SampleSearch) remains the same. What changes is that the initialset A of samples is stored on an AND/OR structure. The AND/OR representation definesa new distribution over the initial set of samples, from which samples are drawn in theresampling step. We argue and show that the AND/OR structure imposed on the sampleswill lead to a more accurate sampling scheme than the earlier one we proposed in [7]. In-tuitively, SampleSearch-SIR is a method for learning a multi-variate distribution over theconstraint network (or any graphical model) from an initial set A of weighted samples.SampleSearch-SIR assumes no independencies among the variables in the constraint net-work. The AND/OR representation of the samples on the other hand captures some of theinherent conditional independencies, yielding a more compact sample representation thatcaptures a larger set of virtual samples. Therefore, AO-SIR is likely to be more accurateand have better convergence properties.Subsequently, we derive a new unbiased estimator using the samples stored on theAND/OR structure and show how it can be combined with SampleSearch to approxi-mately count and lower bound the number of solutions of a constraint network, improv-ing over our previous solution counter [5].To evaluate whether exploiting decomposition via the AND/OR s tructure yields im-proved performance in practice, we performed an empirical evaluation on a wide range ofsatisfiability benchmarks . We found that on most problems our new schemes that operatein the AND/OR space are more accurate than SampleSearch-SIR for solution samplingwhile in the case of solution counting, we were able to improve upon the lower boundsreported in [5, 8] in most cases.The rest of the paper is organized as follows. In section 2, we present preliminariesand previous work. In section 3, we present the AO-SIR algorithm and describe its prop-erties. In section 4, we define a new unbiased estimator in AND/OR space. Empiricalresults are presented in section 5 and we end with a brief summary in section 6.2 PreliminariesDefinition 1 (constraint network, counting and sampling). A constraint network (CN)is defined by a 3-tuple, R = hX, D,Ci, where X = {X1,. ..,Xn} is a set of variables asso-ciated with a set of discrete-valued domains, D = {D1,. .., Dn}, and C = {C1,. ..,Cr} isa set of constraints. Each constraint Ciis a relation RSidefined on a subset of variablesSi⊆ X. The relation denotes all compatible tuples of the cartesian product of the domainsof Si. A solution is an assignment of values to all variables x = (X1= x1,. ..,Xn= xn),xi∈ Di, such that x belongs to the natural join of all constraints i.e. x ∈ RS1⊲⊳ . .. ⊲⊳ RSr.The constraint satisfaction problem (CSP) is to determine if a constraint network has asolution, and if so, to find one. The primal graph (also called the constraint graph) of aconstraint network is an undirected graph that has variables as its vertices and an edgeconnects any two variables involved in a constraint.The solution counting problem #csp is the problem of counting the number of solutionsof a constraint network. The solution sampling problem §csp is the problem of samplingsolutions from a uniform distribution over the solutions of a constraint network.2.1 AND/OR search spaces for general inferenceThe AND/OR search space [2] is a generic inference scheme that can be used to exactlysolve various combinatorial problems in graphical models. We can solve most combina-torial problems by search, by systematically enumerating all the possible combinations.In the simplest case, t his process defines an OR search tree, whose nodes represent partialvariable assignments. This search space does not capture the st ructure of the underlyingCBDA≠≠≠{1,2,3}{1,2,3}{1,2,3}{1,2,3}(a)CB DA(b)2B0 12 1 2 0D0 1D0 12A02A0101A12A01A12A12A02A02C0B1D1A02D2A11B0D0A2102D2A202010112011212020201210(c)2B D0 101C0 1B D B D1 2 1 202 0 22 0 1 1A1 2A0 2A0A1A2A0(d)2B D0 101C0 1D D1 2 0 21 220B1A02A1B0A2(e)Fig.1. (a) A 3-coloring problem, (b) Pseudo-tree (c) AND/OR tree whose pseudo-tree is a chain(d) AND/OR tree (e) AND/OR search graphgraphical model. To remedy this problem, [2] introduced the notion of AND/OR


View Full Document

UCI ICS 161 - Approximate Solution Sampling on AND/OR search space

Download Approximate Solution Sampling on AND/OR search space
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Approximate Solution Sampling on AND/OR search space and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Approximate Solution Sampling on AND/OR search space 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?