Source-linked AI summary
Weighing and Integrating Evidence for Stochastic Simulation in Bayesian Networks
Robert Fung, Kuo-Chu Chang
TL;DR
Logic sampling handles evidence poorly because trials whose sampled evidence disagrees with observations are discarded. The paper introduces evidence weighting and combines it with evidential integration; the reported example shows at least about 100-times-faster convergence after partial integration, while broader convergence analysis remains preliminary.
Problem
Logic sampling performs poorly with evidence because trials that do not match observed evidence are discarded, limiting stochastic inference when evidence is present.
Method
The paper augments logic sampling by sampling state nodes and weighting each trial by the likelihood of the evidence, optionally integrating evidence through arc reversal.
Results
In the example network, partial evidential integration made the evidence-weighted convergence rate at least about 100 times faster than without that integration.
Takeaways & Limitations
Evidence weighting offers a relatively low-cost stochastic simulation mechanism that can handle deterministic variables, while evidential integration can address its extremal-likelihood convergence drawback.
Takeaways & Limitations
The results are preliminary, and further research is needed on convergence analysis; evidence weighting can also reduce to logic sampling for extremal likelihoods.
Abstract
from arXiv · showhide
Stochastic simulation approaches perform probabilistic inference in Bayesian networks by estimating the probability of an event based on the frequency that the event occurs in a set of simulation trials. This paper describes the evidence weighting mechanism, for augmenting the logic sampling stochastic simulation algorithm [Henrion, 1986]. Evidence weighting modifies the logic sampling algorithm by weighting each simulation trial by the likelihood of a network's evidence given the sampled state node values for that trial. We also describe an enhancement to the basic algorithm which uses the evidential integration technique [Chin and Cooper, 1987]. A comparison of the basic evidence weighting mechanism with the Markov blanket algorithm [Pearl, 1987], the logic sampling algorithm, and the evidence integration algorithm is presented. The comparison is aided by analyzing the performance of the algorithms in a simple example network.
2 The Evidence Weighting Techniue
Evidence weighting modifies logic sampling by sampling state nodes and weighting each trial by the evidence likelihood, so all trials can contribute to posterior estimates. Its benefits diminish for extremal evidence likelihoods, and selective evidence weighting remains an unevaluated trade-off.
- Core mechanism: Evidence weighting samples only state nodes and uses the product of evidence likelihoods to increment event counts before normalization.This replaces the constant increment used in logic sampling with a likelihood-based trial weight.
- Core mechanism: Sampling from P(X) and weighting by P(E|X) estimates the posterior probability of an event given the evidence.For each trial, U(z_i) indicates whether the sampled realization belongs to the event of interest.
- Advantages and limits: All trials are valid and contribute to reducing error, unlike logic sampling trials rejected when sampled evidence does not match observations.The advantage depends on evidence likelihoods that are not uniformly extremal.
- Advantages and limits: Selecting only evidence pieces that bear on each event may reduce noise, but the trade-off between extra computation and convergence improvement was not studied.The paper identifies this as a possible sufficient-information optimization rather than an established improvement.
3 Evidence Weighting With Evidential Integration
Evidential integration is combined with evidence weighting to address slow convergence caused by extremal evidence likelihoods. In the example, partial integration made convergence at least about 100 times faster, while integration costs create a computation trade-off.
- Integration mechanism: Evidential integration reverses arcs to integrate evidence into the network before applying evidence weighting.The goal is to transform the network so stochastic samples are generated more efficiently.
- Integration mechanism: Partial integration makes evidence likelihoods more comparable, improving the efficiency of evidence-weighted sampling in the example network.Only the arc between the evidence and one predecessor was reversed in the described example.
- Example result: The second network’s convergence rate was at least about 100 times faster than the first network’s under the same evidence-weighting technique.The reported comparison used partial evidence integration.
- Computational trade-off: The amount of evidence integration should balance fixed arc-reversal costs against dynamic simulation costs under different convergence rates.Avoiding an expensive arc reversal can be part of this trade-off.
- Evaluation setup: The paper evaluates evidence weighting, Markov blanket, logic sampling, and evidential integration on a simple example network using repeated simulation runs.The experiments used 100, 200, 500, 1000, and 2000 trials per run, with 100 runs for each setting and algorithm.
1 N E·n•Of' = N L L: L I p:(z;)- p(zJ) I (4) i=l • j
The paper evaluates evidence weighting and evidential integration as enhancements to stochastic simulation, comparing their accuracy, convergence, and computational costs with alternative algorithms. In the example network, evidence weighting and evidential integration achieve greater accuracy for a given computation time, while evidence weighting retains advantages for deterministic functions and low per-trial cost.
- Evaluation: The evaluation compares four simulation algorithms using posterior-estimation error, standard deviation, and runtime in an example Bayesian network.The measures are reported across Figures 4 through 8.
- Accuracy and convergence: Errors decrease approximately in inverse proportion to the square root of the number of simulation trials, while estimate deviations also decrease as trials increase.The inverse-square-root relationship is attributed to the Central Limit Theorem.
- Computational cost: The Markov blanket algorithm has by far the highest cost per trial, whereas evidence weighting, evidential integration, and logic sampling have similar per-trial costs.The cost disparity is expected to grow with network size.
- Overall comparison: For the example network, evidence weighting and evidential integration are significantly more accurate for a given amount of computation time.This comparison combines estimation error with runtime.
- Evidence weighting: Evidence weighting handles deterministic functions, samples only in a causal direction, and uses all trials to calculate posteriors.The paper presents these properties as advantages of the mechanism.
- Limitations and extensions: Evidence weighting can converge slowly when evidence likelihoods are extremal, and combining it with evidential integration is proposed to avoid this drawback.The paper characterizes the reported results as preliminary and calls for further convergence analysis.