OverviewOverviewBayesian Networks: Representation (Pearl, 1988)Mixed Networks: Mixing Belief and ConstraintsMixed networks: Distribution and QueriesApplicationsSlide 8Approximate InferenceOverviewImportance Sampling: OverviewGenerating i.i.d. samples from QRejection ProblemRejection ProblemRejection ProblemRejection ProblemRejection ProblemRevising Q to backtrack-free distribution:Generating samples from QFGenerating samples from QFApproximations of QFAlgorithm SampleSearchAlgorithm SampleSearchAlgorithm SampleSearchAlgorithm SampleSearchGenerate more SamplesGenerate more SamplesTraces of SampleSearchSampleSearch: Sampling DistributionThe Sampling distribution QF of SampleSearchAsymptotic approximations of QFApproximations: Convergence in the limitApproximations: Convergence in the limitImproving Naive SampleSeach: The IJGP-wc-SS algorithmExperimentsSlide 39Slide 40Slide 41Results: Solution Counts Latin Square instances (size 8 to 16)Results: Solution Counts Langford instancesSlide 44Results on MarginalsSlide 46Slide 47Summary: SampleSearchOverviewMotivationOR Search TreeAND/OR Search TreeAND/OR TreeComplexity of AND/OR Tree SearchBackground: AND/OR search spaceExample Bayesian networkRecap: Conventional Importance SamplingAND/OR Importance Sampling (General Idea)AND/OR Importance Sampling (General Idea)Slide 62Slide 64Algorithm AND/OR Importance SamplingProperties of AND/OR Importance SamplingAND/OR w-cutset (Rao-Blackwellised) samplingAND/OR w-cutset samplingFrom Search Trees to Search GraphsFrom Search Trees to Search GraphsMerging Based on ContextAND/OR GraphsAND/OR graph samplingVariance Hierarchy and ComplexityExperimentsSlide 80Slide 81Summary: AND/OR Importance samplingOverview•Introduction: Mixed graphical models•SampleSearch: Sampling with Searching•Exploiting structure in samplinig: AND/OR Importance samplingOverview•Introduction: Mixed graphical models•SampleSearch: Sampling with Searching•Exploiting structure in samplinig: AND/OR Importance samplingBayesian Networks: Representation(Pearl, 1988)))(|()())(|(1iniiiiXpaXPXPXpaXP :CPTslung CancerSmokingX-rayBronchitisDyspnoeaP(D|C,B)P(B|S)P(S)P(X|C,S)P(C|S)P(S, C, B, X, D) = P(S) P(C|S) P(B|S) P(X|C,S) P(D|C,B)Belief Updating:P (lung cancer=yes | smoking=no, dyspnoea=yes ) = ?Mixed Networks: Mixing Belief and ConstraintsBelief or Bayesian NetworksADB CEFADB CEF)|(),,|( ),|(),|(),|(),( :CPTS}1,0{:Domains,,,,, :VariablesAFPBAEPCBDPACPABPAPDDDDDDFEDCBAFEDCBAConstraint Networks)( :solutions ofset theExpresses),(),(),(),( :sConstraint}1,0{:Domains,,,,, :Variables4321RsolEARBCDRACFRABCRDDDDDDFEDCBAFEDCBAB C D=0D=10 0 0 10 1 .1 .91 0 .3 .71 1 1 0),|( CBDP allowednot is 1D1,C1,B allowednot is 0,0,0)(3 DCBBCDRB=R=Constraints could be specified externally or may occur as zeros in the Belief networkMixed networks:Distribution and Queries•The distribution represented by a mixed network T=(B,R):•Queries:–Weighted Counting (Equivalent to P(e), partition function, solution counting)–Marginal distribution: )()(RsolxBxPMotherwise ,0)( if ),(1)(RsolxxPMxPBT)(iTXPApplications•Determinism: More Ubiquitous than you may think! •Transportation Planning (Liao et al. 2004, Gogate et al. 2005)–Predicting and Inferring Car Travel Activity of individuals•Genetic Linkage Analysis (Fischelson and Geiger, 2002)–associate functionality of genes to their location on chromosomes.•Functional/Software Verification (Bergeron, 2000)–Generating random test programs to check validity of hardware•First Order Probabilistic models (Domingos et al. 2006, Milch et al. 2005)–Citation matching8S13mL11fL11mL13mX11S13fL12fL12mL13fX12X13Model for locus 1S23mL21fL21mL23mX21S23fL22fL22mL23fX22X23Model for locus 2Functions on Orange nodes are deterministicApproximate Inference •Approximations are hard with determinism•Randomized Polynomial ε-approximation possible when no zeros are present (Karp 1993, Cheng 2001)•ε-approximation NP-hard in the presence of zeros•Gibbs sampling is problematic when MCMC is not ergodic.•Current remedies–Replace zeros with very small values (Laplace correction: Naive Bayes, NLP)–bad performance when zeros or determinism is real!Overview•Introduction: Mixed graphical models•SampleSearch: Sampling with Searching–Rejection problem –Recovery, and analysis–Empirical evaluation•Exploiting structure in samplinig: AND/OR Importance samplingImportance Sampling: Overview•Given a proposal or importance distribution Q(z) such that f(z)>0 implies Q(z)>0, rewriteEXZwherezfMeEXPePZzEXB\ P(e) )(),()(\  )()()()()()(zQzfEzQzQzfzfMQZz ZzGiven i.i.d. samples z1,..,zN from Q(z),P(e)M]Mˆ[E )(1 )()(1ˆQ11NjNjjjjzwNzQzfNMGenerating i.i.d. samples from QA=0B=0 B=1 B=0 B=1A=1C=1C=1C=1 C=0 C=0 C=0 C=1Root0.8 0.20.4 0.60.20.80.2 0.8 0.2 0.8 0.20.80.20.8C=0)8.0.2.0()(),|(),8.0,2.0,6.0,4.0()|(),2.0,8.0()(),|()|()(),,(),...,|(.....)|()(11121CQBACQABQAQBACQABQAQCBAQXXXQXXQXQ Q(X)nnRejection Problemsolution. anot is xi if :sampling Importance0)()()(1~1xifxiQxifNMNiA=0B=0C=0B=1 B=0 B=1A=1C=1C=1C=1 C=0 C=0 C=0 C=1Root0.8 0.20.4 0.60.20.80.2 0.8 0.2 0.8 0.20.80.20.8Toss a biased coinP(H)=0.8, P(T)=0.2Say we get HRejection Problemsolution. anot is xi if :sampling Importance0)()()(1~1xifxiQxifNMNiA=0B=0C=0B=1C=1C=1 C=0Root0.80.4 0.60.20.80.2 0.8Toss a biased coinP(H)=0.4, P(T)=0.6Say, We get a HeadRejection Problemsolution. anot is xi if :sampling Importance0)()()(1~1xifxiQxifNMNiA=0B=0C=0B=1C=1C=1 C=0Root0.80.4 0.60.20.80.2 0.8Toss a biased coinP(H)=0.4, P(T)=0.6Say, We get a HeadRejection Problem•A large number of assignments generated will be rejected, thrown awaysolution. anot is xi if :sampling Importance0)()()(1~1xifxiQxifNMNiA=0B=0C=0 C=1Root0.80.40.20.8Toss a biased coinP(H)=0.4, P(T)=0.6Say, We get a HeadRejection ProblemAll Blue leaves correspond to solutions i.e. f(x) >0All Red leaves correspond to non-solutions i.e. f(x)=0solution. anot is xif 0)()()(1ˆ :sampling Importancei1iNiiixfxQxfNMA=0B=0C=0B=1 B=0 B=1A=1C=1C=1C=1 C=0 C=0 C=0 C=1Root0.8 0.20.4 0.60.20.80.2 0.8 0.2 0.8 0.20.80.20.8Constraints: A≠B A≠CRevising Q to backtrack-free distribution: All Blue leaves correspond to solutions i.e. f(x)