Probabilistic Reasoning and Sampling Methods in Artificial Intelligence

Artificial Intelligence: Representation and Problem Solving Probabilistic Reasoning (3): Sampling Methods 15-381 / 681 Instructors: Fei Fang (This Lecture) and Dave Touretzky feifang@cmu.edu Wean Hall 4126 1 6/23/2025

Recap Probability Models and Probabilistic Inference Basics of Bayes Net Independence Exact Inference Real problems: very large network, hard to compute conditional probabilities exactly (computationally expensive) Today: Sampling methods for approximate inference 2 Fei Fang 6/23/2025

Recap Law of large numbers (LLN): the average of the results obtained from a large number of trials should be close to the expected value, and will tend to become closer as more trials are performed ?1,?2, ,?? are i.i.d. Lebesgue integrable random variables with expected value ? ?? = ?, ?. Then the sample average ??= 1 ??1+ + ?? converges to the expected value, i.e., ?? ? for ? Weak law: lim ? Pr ?? ? > ? = 0, ? > 0 Strong law: Pr lim ? ??= ? = 1 Express the quantity we want to know as the expected value of a random variable ?, i.e., ? = ?(?). Generate sample values ?1, ,?? (which are i.i.d random variables) and the sample average should converge to ? 3 Fei Fang 6/23/2025

Recap Bag 1: two gold coins. Bag 2: two pennies. Bag 3: one of each. Defines the probability model Bag is chosen at random, and one coin from it is selected at random; the coin is gold This is the evidence What is the probability that the other coin is gold given the observation? Try 3000 times. P(other coin is gold | first coin is gold) #(first coin is gold and other coin is gold) #(first coin is gold) 4 Fei Fang 6/23/2025

Outline Approximate Inference Direct Sampling Markov Chain simulation 5 Fei Fang 6/23/2025

Approximate Inference in BN For inference in BN, often interested in: Posterior probability of taking on any value given some evidence: ?(?|?) Most likely explanation given some evidence: argmax ? ?(? = ?|?) Exact inference is intractable in large networks Enumeration Variable Elimination Approximate inference in BN through sampling If we can get samples of ? from the posterior distribution ?(?|?), we can use these samples to approximate posterior distribution and/or most likely explanation (based on LLN) 6 Fei Fang 6/23/2025

Approximate Inference in BN Approximate inference in BN through sampling Assume we have some method for generating samples given a known probability distribution (e.g., uniform in [0,1]) A sample is an assignment of values to each variable in the network Generally only interested in query variables after finish sampling Use samples to approximately compute posterior probabilities Queries can be issued after finish sampling 7 Fei Fang 6/23/2025

Example: Wet Grass Variables: ??????(?), ?????????(?), ????(?), ??? ?????(?) +c -c 0.5 0.5 Domain of each variable: ???? (+) or ????? ( ) Cloudy What is the probability distribution of ?????? if you know the sprinkler has been turned on and it rained, i.e., ?(?| + s,+r)? +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r Rain Sprinkler .9 .2 .5 .8 Wet Grass Samples of ?????? given +? & +?: +, , +, +, , +, +, +, +, +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 ? +c +s,+r 0.7 ? c +s,+r 0.3 8 Fei Fang 6/23/2025

Sampling for a Single Variable Want to sample values of a random variable ? whose domain is {????,?????}, with probability distribution 0.5,0.5 ?(?) +c -c 0.5 0.5 Simple approach ? = rand([0,1]) If (? < 0.5) Sample= +c (? = ????) Else Sample = c (? = ?????) 9 Fei Fang 6/23/2025

Sampling with Condition Want to sample values of a random variable ? when c (? = ?????) ?(?|?) Find the corresponding rows in the conditional probability table (CPT): ? ? c = 0.5,0.5 +c +s 0.90 +c -s 0.10 Simple approach ? = rand([0,1]) If (? < 0.5) Sample= +s (? = ????) Else Sample = s (? = ?????) -c +s 0.5 -c -s 0.5 10 Fei Fang 6/23/2025

Direct Sampling (Forward Sampling) Directly generate samples from prior distribution and conditional distribution specified by Bayes Net (i.e., without considering any evidence) Create a topological ordering based on the DAG of Bayes Net A node can only appear after all of its ancestors in the graph Sample each variable in turn, conditioned on the values of its parents 11 Fei Fang 6/23/2025

Example: Wet Grass Valid topological ordering: +c -c 0.5 0.5 ?,?,?,? ?,?,?,? Use the ordering ?,?,?,?, sample variables in turn Cloudy +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 12 Fei Fang 6/23/2025

Estimate Probability We can use the samples to estimate probability of an event ?1= ?1, ,??= ?? ? ?1= ?1, ,??= ?? ???(?1, ,??) When #?????? , the approximation becomes exact (called consistent) ? 14 Fei Fang 6/23/2025

Example: Wet Grass What is ? +c, s,+r,+w ? +c -c 0.5 0.5 Cloudy Sample 10000 times according to this sampling procedure, if you get (+c, s,+r,+w)? times, then +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 ? ? +c, s,+r,+w 10000 15 Fei Fang 6/23/2025

Reject Sampling If the query is conditional (posterior) probability ? ? ? , then need to reject the direct samples that do not match the evidence ? ? ? ????,? ???? Inefficient 16 Fei Fang 6/23/2025

Quiz 1 You get 100 direct samples 73 have s, of which 12 have + r 27 have +s, of which 8 have +r What is a reasonable estimate of ? +s +r ? A: 20 100 B: 12 73 C: 8 27 D: None of the above +c -c 0.5 0.5 Cloudy +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 18 Fei Fang 6/23/2025

Likelihood Weighting Likelihood Weighting Generate only samples that agree with evidence and weight them according to likelihood of evidence More efficient than reject sampling A particular instance of the general statistical technique of importance sampling Likelihood Weighting 1. Initialize counter N for query variables ? to be ? 2. Run ? iterations. In each iteration, get a sample ? = (?,?, ) of all variables that is consistent with evidence ?, together with a weight ?. Set N ? N ? + ?. 3. Normalize counter N to get estimation ?(?|?) 20 Fei Fang 6/23/2025

Likelihood Weighting Get a sample together with a weight in likelihood weighting Select a topological ordering of variables ?1, ,?? Set ? = 1 For ? = 1..? If ?? is an evidence variable with value ?? ? ? ? ??= ?????????(??) Else ?? ?????? ???? ? ?????????(??) 21 Fei Fang 6/23/2025

Example: Wet Grass Use the ordering ?,?,?,? Evidence: +c,+w Get a sample: +c -c 0.5 0.5 Cloudy +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 22 Fei Fang 6/23/2025

Consistency of Likelihood Weighting Likelihood Weighting is consistent: As ? , estimation converges to ?(?|?) (see detailed proof in textbook) A simple case: there is only one query variable ?. Let ? be set of all random variables. Let ? = ?\? be the set of non-evidence variables. Let ? = |?| and ? = |?|. Let ? = ?\{? ?}. 24 Fei Fang 6/23/2025

Quiz 2 Using likelihood weighting, if we get 100 samples with +r and total weight 1, and 400 samples with r and total weight 2, what is an estimate of ?(? = +?| + w)? A: 1 9 B: 1 3 C: 1 5 D: 1 6 +c -c 0.5 0.5 Cloudy +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 26 Fei Fang 6/23/2025

Markov Chain Simulation Recap: Direct sampling methods (including rejection sampling and likelihood weighting) generate each new sample from scratch Markov chain Monte Carlo (MCMC): Generate a new sample by making a random change to the preceding sample Recall: simulated annealing (also can be seen as a member of MCMC family) 28 Fei Fang 6/23/2025

Gibbs Sampling A particular form of MCMC suited for Bayes Net Given a sample ? (consistent with evidence ?), simulate a new sample ? by randomly sampling a value for one of the nonevidence variable ?? Sampling for ?? is conditioned on the current values of the variables in the Markov blanket of ?? Markov blanket=parents + children + children s parents Start from an initial sample, iteratively generating new samples. After generating enough samples, answer the query How to choose the nonevidence variable? Option 1: Go through all the nonevidence variable in turn based on an arbitrary order (not necessarily a topological order) Option 2: Randomly choose a non-evidence variable uniformly randomly 29 Fei Fang 6/23/2025

Example: Wet Grass Evidence: +s,+w. Order of non-evidence variables: ?,?. Initial sample (+c,+s, r,+w) Sample ? Get c. Get new sample ( c,+s, r,+w) Cloudy Sample ? Get +r. Get new sample ( c,+s,+r,+w) Rain Sprinkler Sample ? Get c and sample c,+s,+r,+w Wet Grass Sample ? Get r and sample c,+s, r,+w How to compute ?(?| + s, r) and ?(?| c,+w,+s)? Exact inference! . 30 Fei Fang 6/23/2025

Example: Wet Grass Compute ?(?| + s, r) through exact inference +c -c 0.5 0.5 Cloudy +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 32 Fei Fang 6/23/2025

Quiz 3 Evidence: +s,+w. Initial sample (+c,+s, r,+w). Current sample ( c,+s,+r,+w) What is NOT a possible next sample when using Gibbs sampling? A: ( c,+s,+r,+w) B: (+c,+s,+r,+w) C:( c,+s, r,+w) D:( c, s,+r,+w) +c -c 0.5 0.5 Cloudy +c +s .1 +c -s -c +s .5 -c -s +c +r .8 +c -r -c +r .2 -c -r .9 .2 Rain Sprinkler .5 .8 Wet Grass +s +r +w .99 +s +r -w .01 +s -r +w .90 +s -r -w .10 -s +r +w .90 -s +r -w .10 -s -r +w 0 -s -r -w 1.0 34 Fei Fang 6/23/2025

Example: Wet Grass Following this process and get 100 samples Assume you get 31 samples with +r, 69 with r What is ?(?| + s,+w)? 36 Fei Fang 6/23/2025

Gibbs Sampling How many samples are generated in total? 38 Fei Fang 6/23/2025

Gibbs Sampling Why Gibbs Sampling works? The sampling process can be seen as a Markov Chain State ?: An assignment to all variables, must be consistent with evidence ? Transition probability ?(? |?): decided by the ordering of choosing nonevidence variable, and the conditional probability defined by the Bayes Net. Can only transit to neighboring states, i.e., states with at most one variable being different 40 Fei Fang 6/23/2025

Example: Wet Grass From G. Mori 41 Fei Fang 6/23/2025

Gibbs Sampling Why Gibbs Sampling works? The sampling process can be seen as a Markov Chain The sampling process settles into a dynamic equilibrium and long-run fraction of time spent in each state is exactly proportional to its posterior probability (See detailed proof in textbook) Gibbs sampling is consistent: Converges to true posterior distribution when #sampled 42 Fei Fang 6/23/2025

Summary Approximate Inference in Bayes Net Direct (Forward) Sampling Reject Sampling Likelihood Weighting Markov chain simulation Gibbs Sampling 43 Fei Fang 6/23/2025

Acknowledgment Some slides are borrowed from previous slides made by Tai Sing Lee 44 Fei Fang 6/23/2025