Approximate Inference in Bayes Nets: Random vs. Rejection Sampling
Approximate inference methods in Bayes nets, such as random and rejection sampling, utilize Monte Carlo algorithms for stochastic sampling to estimate complex probabilities. Random sampling involves sampling in topological order, while rejection sampling generates samples from hard-to-sample distributions based on easy-to-sample ones. The sprinkler network example illustrates how these methods work, estimating probabilities of specific events and partially specified events. By generating random events and counting outcomes, these methods provide approximate solutions that converge to the true distribution with increasing sample size.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Approximate Inference in Bayes Nets Outline I. Random sampling II. Rejection sampling * Figures are either from the textbook site.
Approximate Inference Methods These methods, also called Monte Carlo algorithms, are based on the principle of stochastic sampling. Generate random events based on the probabilities in the Bayes net. Count up different answers found in these events. Monte Carlo algorithms are used to estimate quantities that are difficult to calculate exactly. Accuracy depends on the size of the sample set. Can get arbitrarily close to the true probability distribution as the size increases. Two families of algorithms: direct sampling and Markov chain sampling.
I. Random Sampling Sample variables in topological order. The value of a node is conditioned on those already assigned to its parents (the assignments are guaranteed by the topological order). from the domain of ??, e.g., true or false
The Sprinkler Network Every morning Mary checks the weather. If it s cloudy, she usually does not turn on the sprinkler. The grass will be wet if the sprinkler is on, or if it rains during the day. Order: Cloudy, Sprinkler, Rain, WetGrass 1. Value true sampled from ? Cloudy = 0.5,0.5 . How? Generate a pseudo-random number ? in the range [0, 1]. Return true if ? < 0.5 and false otherwise. 2. Value false sampled from ? Sprinkler | Cloudy = true = 0.1,0.9 . 3. Value true sampled from ? Rain | Cloudy = true = 0.8,0.2 . PRIOR-SAMPLE() returns the event [true, false, true, true]. 4. Value true sampled from ? WetGrass | Sprinkler = false,Rain = true = 0.9,0.1 .
Sampling Process ????1, ,??: probability of a specific event generated by PRIOR-SAMPLE. ? ? ??parents(??)) ????1, ,?? = ?=1 (probability of joint distribution) = ?(?1, ,??) ? total samples produced by PRIOR-SAMPLE. ???(?1, ,??) times that the specific event ?1= ?1 ??= ?? occurs. ???(?1, ,??) ? lim ? = ????1, ,?? =?(?1, ,??) ???true,false,true,true = 0.5 0.9 0.8 0.9 = 0.324 Cloudy, Sprinkler, Rain, WetGrass
Partially Specified Event Estimate the probability of the partial event ??1= ??1 ???= ???, 1 ?1< < ?? ?: ?(??1, ,???) ???(??1, ,??? ) ?(??1, ,???) ? the fraction of all sampled complete events that match the partially specified event ExampleRain = true holds for 511 of 1,000 samples generated from the sprinkler network. ? Rain = true = 0.511
II. Rejection Sampling (RS) Generate samples from a hard-to-sample distribution given an easy-to-sample distribution. Estimate ? ? ?) as follows: Generate samples from the prior distribution specified by the BN. ? ? Rejects all those that do not match the evidence ?. ???? : the number of samples that are not rejected. Rejects ? = ? Count how often ? = ? occurs in the remaining ???? samples for every value ? of ?. ? = ? ? = ? ? = ? ? = ? ????,? : the vector of counts, one for each value ? of ?, of samples that contain ? = ? and also agree with the evidence ?. 2,1,2 ? ? ? ? ? ?) = ?????,? =????,? ???? ? ? ?) = 0.4,0.2,0.4
Estimation of True Probability by RS ????,? ???? ? ? ?) = =????,? /? ???? /? Standard deviation 1/ ? of error in each probability ?(?,?) ?(?) ???(?1, ,??) ? since ?(?1, ,??) ? ? ?) ? ? ?) Example Estimate ? RainSprinkler = true) using 100 samples. 73 samples have Sprinkler = false and are rejected. Of the 27 samples with Sprinkler = true, only 8 have Rain = true. ? RainSprinkler = true) ? 8,19 = (0.296,0.704)
How Fast Does RS Converge? How many samples are needed before the resulting estimates are close to the correct answers with high probability? The complexity of rejection sampling depends primarily on the fraction of samples that are accepted. =prior probability of the evidence ?(?) ?(?) is vanishingly small for complex networks with many evidence variables. The fraction of samples consistent with ? drops exponentially as the number of evidence variables grows. Rejection sampling is unusable for complex problems.
