Probabilistic Inference: Exact and Sampling Methods

From model to query

Inference is the step that turns a probability model into a decision-relevant answer.

A typical query asks for the posterior distribution of a variable given evidence: the probability of a machine fault given sensor readings, demand level given early orders, or supplier delay given current logistics signals. Define the query variable, evidence and model before choosing the computational method. A fast algorithm answering the wrong query creates false efficiency.

Distinguish prediction from diagnosis. Prediction propagates beliefs forward from causes or current state to future outcomes. Diagnosis uses evidence to update beliefs about hidden causes. In a Bayesian network, both are applications of conditioning.

Direct enumeration and its limitation

The most conceptually direct method sums the joint probability over all unobserved variables.

Enumeration is useful for understanding the mathematics and for very small models, but the number of combinations grows rapidly. Structured inference methods exploit factorisation so that repeated computation can be avoided. This is a core theme of the source: representation and computational complexity are connected.

The proportionality reminds us that the result must be normalised so probabilities sum to one. In continuous models, integrals replace sums.

Variable elimination

Variable elimination rearranges multiplication and summation so intermediate factors are reused rather than repeatedly expanding the whole joint distribution.

The analyst chooses an elimination order for hidden variables. At each step, factors containing the variable are multiplied and the variable is summed out, producing a new factor. The final factors are combined and normalised. The answer is exact, but the size of intermediate factors can become large.

Elimination order matters. Removing a highly connected variable early can create a large intermediate factor. Graph structure therefore determines computational difficulty. Practical systems use graph heuristics to find reasonable orders rather than searching every possible ordering.

Belief propagation and message passing

When the graph has tree-like structure, local messages can efficiently compute marginals.

Message passing summarises the effect of one part of the graph on another. In a tree, messages flow between connected variables or factors until each required belief combines local evidence and incoming information. The result can be exact. In graphs with loops, related iterative methods may be used as approximations, but convergence and accuracy are not automatically guaranteed.

The managerial insight is broader than the algorithm: structure enables local computation. A modular risk model can be easier to update than one monolithic table because evidence from one subsystem can be summarised before being passed onward.

Sampling from probabilistic models

Sampling approximates expectations or posterior probabilities by drawing representative states.

Direct ancestral sampling draws variables in network order from their conditional distributions. It is simple when there is no evidence or when evidence is easy to incorporate. Rejection sampling discards samples inconsistent with evidence, which becomes inefficient when evidence is rare. Likelihood weighting keeps samples but weights them according to the evidence likelihood.

Gibbs sampling is a Markov chain method that repeatedly resamples each non-evidence variable conditioned on the others. After an initial period, samples can approximate the posterior under suitable conditions. Correlated variables can make mixing slow; diagnostics and multiple chains may be needed in serious applications.

Gaussian and continuous inference

Some structured models use Gaussian assumptions because linear-Gaussian relationships permit efficient analytical inference.

Means and covariance matrices represent beliefs, and conditioning produces updated Gaussian distributions. This is the foundation of common state-estimation methods. The advantage is computational efficiency; the risk is assuming a shape that cannot represent multimodal, bounded or strongly skewed uncertainty.

When a continuous problem is not well represented by Gaussian assumptions, sampling or other approximations may be more appropriate. Choose a representation that preserves the features of uncertainty that matter to the decision.

Worked example: diagnosing a delayed delivery

Suppose a generic delivery can be late because of production, supplier or transport conditions, and several status signals are observed.

An exact model could use variable elimination to compute the probability of each cause given the signals. If the network is small and sparse, this can be fast and reproducible. If the model expands to hundreds of dependent variables with continuous timing, exact factors may become impractical.

A sampling approach can generate plausible hidden scenarios consistent with the evidence, estimate the probability of each cause and quantify the distribution of final delivery time. The business decision might then be whether to expedite, notify the customer or wait for more information. Inference is valuable because it turns fragmented signals into a coherent posterior belief rather than a collection of disconnected alarms.

Validation and computational discipline

Approximate inference needs error awareness, and exact inference needs complexity awareness.

For sampling, monitor convergence, effective sample size, weight degeneracy and stability across repeated runs. For exact methods, monitor factor size and numerical stability. Compare methods on smaller cases where exact answers are available. The objective is enough accuracy to support the decision, not computational elegance for its own sake.

Application checklist

• State the query, evidence and required accuracy before selecting an algorithm.
• Use exact inference when model structure keeps computation manageable.
• Choose variable-elimination order with graph structure in mind.
• Use message passing where factorisation supports local computation.
• Select a sampling method suited to the evidence and model.
• Check convergence and effective sample information for Monte Carlo methods.
• Test approximate algorithms on cases with known or exact answers.
• Report inference error when it can affect the decision.