PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploiting Contextual Independence In Probabilistic Inference

D. Poole, N. L. Zhang

arXiv:1106.4864v1cs.AI

TL;DR

Probabilistic inference needs compact representations for conditional probabilities beyond ordinary belief-network structure. The paper represents contextual independence with confactors and extends variable elimination so context determines which tables are multiplied. The resulting method can be much more efficient than VE when contextual structure exists, although efficiency depends on the problem and elimination ordering.

  • Problem

    Belief networks compactly represent independence, but inference remains difficult and conditional probabilities need more compact representations that exploit contextual independence.

  • Method

    The paper represents conditional probabilities with confactors and extends variable elimination so tables multiplied during elimination may depend on context.

  • Results

    CVE can be much more efficient than VE when contextual structure exists, while some instances incur overhead without savings.

  • Takeaways & Limitations

    Contextual variable elimination extends standard variable elimination and can exploit structure that ordinary table-based inference does not.

  • Takeaways & Limitations

    CVE may be uncompetitive when confactor tables are no smaller than VE tables, and good elimination-ordering heuristics remain an open problem.

Abstract

from arXiv · show

Bayesian belief networks have grown to prominence because they provide compact representations for many problems for which probabilistic inference is appropriate, and there are algorithms to exploit this compactness. The next step is to allow compact representations of the conditional probabilities of a variable given its parents. In this paper we present such a representation that exploits contextual independence in terms of parent contexts; which variables act as parents may depend on the value of other variables. The internal representation is in terms of contextual factors (confactors) that is simply a pair of a context and a table. The algorithm, contextual variable elimination, is based on the standard variable elimination algorithm that eliminates the non-query variables in turn, but when eliminating a variable, the tables that need to be multiplied can depend on the context. This algorithm reduces to standard variable elimination when there is no contextual independence structure to exploit. We show how this can be much more efficient than variable elimination when there is structure to exploit. We explain why this new method can exploit more structure than previous methods for structured belief network inference and an analogous algorithm that uses trees.

1. Introduction

Probabilistic inference is broadly useful but computationally difficult, motivating compact belief-network representations and algorithms that exploit both network and contextual independence.

  • Probabilistic inference supports diagnosis, perception, and user modelling but is difficult computationally and requires many probability specifications.
  • Belief networks compactly represent independence among random variables and provide algorithms that exploit this structure.
  • Structured conditional-probability representations have been developed using causal independence, parametric forms, rules, and trees.
  • The paper extends efficient belief-network inference to exploit contextual independence, following earlier rule-based and mathematical treatments.
  • The paper introduces confactors, extends variable elimination to use them, and develops efficiency improvements for contextual inference.

2. Background

Belief-network inference computes posterior probabilities by representing conditional dependencies as factors and eliminating non-query variables through products, summation, and normalization.

  • Belief networks are acyclic directed graphs whose nodes are random variables and whose arcs connect each variable to its parents.
  • Variable elimination computes posterior probabilities by summing out non-query, non-observed variables from products of conditional-probability factors.
  • VE exploits distributivity by moving factors that do not contain the eliminated variable outside the sum.
  • The VE procedure selects a non-query variable, eliminates it from the relevant factors, and returns a normalized result.
  • Factor products combine functions over the union of their variables, while summation removes the eliminated variable from the resulting function.
  • The three primitive table operations are setting variables, forming products, and summing out variables.

3. Contextual Independence

Contextual independence makes a variable independent of selected predecessors only under particular contexts, allowing conditional probabilities to use parent contexts rather than all predecessor assignments. The paper represents these contexts with trees and confactors, reducing parameters while preserving inference structure.

  • Definition: Contextual independence holds when variables are independent given an assignment to a context, subject to positive-probability conditions.The definition permits conditioning on additional variables and specializes to ordinary contextual independence when that set is empty.
  • Applications and scope: Contextual independence arises in settings including medical diagnosis, engineered insulation, adaptive questionnaires, and learned decision trees.The paper presents these as examples rather than claiming that contextual independence is always present or exploitable.
  • Parent contexts: A parent context for X_i is an assignment to predecessors that makes X_i independent of all earlier variables.Parent contexts determine which variables act as parents for a variable in each context.
  • Compact representation: A contextual representation can require fewer probabilities than a traditional table, because relevant parents may change with observed values.For E with four parents, the tabular form requires 16 numbers, whereas the cited parent contexts require 6.
  • Tree representations: Tree paths encode parent contexts, with each leaf storing a conditional probability that is independent of untested predecessors.For example, a leaf can specify P(e|a ∧b) without depending on C or D.
  • Confactors: The paper represents structured conditional probabilities using confactors, which combine context conditions with tables.Confactors cover tables and rules as special cases and support the later contextual variable elimination algorithm.

4. Contextual Variable Elimination

Contextual variable elimination applies variable elimination to confactors rather than ordinary tables, processing only context-compatible contributions. It can sum variables separately across contexts and reduces to standard variable elimination when contextual independence is absent.

  • Core algorithm: CVE represents conditional probabilities as confactors and performs variable elimination using confactor multisets instead of tables.Its finer-grained units allow the factors multiplied during elimination to depend on the current context.
  • Context-sensitive elimination: For an elimination variable, CVE can ignore confactors whose contexts are incompatible with the current context.This context-sensitive selection is the source of savings when contextual independence goes beyond ordinary conditional independence.
  • Result: When there is no contextual independence, all confactors have empty contexts and CVE reduces to standard variable elimination.When contextual independence is present, the paper states that the savings can be substantial.
  • Context-sensitive elimination: CVE may sum out a variable in some contexts while retaining it in others, rather than eliminating it globally in one step.Remaining variables are interpreted relative to the contexts in which the variable has or has not been eliminated.
  • Primitive operations: The algorithm uses multiplication, summing out, and confactor splitting, with splitting enabling the other operations when their prerequisites are not met.Splitting preserves the program invariant by replacing a confactor with context-specific confactors having the same contribution.
  • Primitive operations: Confactors with the same context can be multiplied, while compatible confactors containing an elimination variable can be combined through context-specific summation.The additive operation extends tables over the union of variables before adding values pointwise.

4.5 Examples of Eliminating Variables

Contextual elimination manipulates confactors by splitting compatible contexts so that multiplication or summation can proceed locally. The examples show that splitting order affects efficiency, while residual confactors preserve correctness and can avoid the large factors produced by standard VE.

  • Efficiency: Eliminating B with contextual factors avoids the size-32 factor that standard VE produces over A, C, D, E, Y, and Z.The examples illustrate the computational benefit of retaining context-specific structure during elimination.
  • Splitting confactors: Confactors are split only when needed to create identical or complementary contexts for multiplication or summation.Splitting increases representation complexity, so it should be applied judiciously.
  • Splitting heuristics: The choice of splitting order does not affect correctness but can change the total number of later splits.A useful heuristic is to split first on variables appearing in the table, or on variables required by the most combinations.
  • Multiplication: Compatible confactors can be split on each other’s contexts, producing matching contexts that can then be multiplied.Residual confactors represent the incompatible cases created by the split.
  • Summation: Complementary context values permit summing out a variable when no other compatible confactor contains that variable.For multivalued variables, multiple splits may be required across value pairs.

4.7 Evidence

Evidence is incorporated by pruning incompatible confactors, removing observed assignments from contexts, and restricting tables. After absorption, inference proceeds with a simplified confactor base and posterior contributions are combined and normalized.

  • Absorbing evidence: Evidence absorption removes confactors incompatible with observations and removes observed variable assignments from remaining contexts.These operations retain only contexts consistent with the evidence.
  • Absorbing evidence: Each table is restricted to the observed values using the same selection operation as tabular VE.This directly reduces the table arguments affected by the evidence.
  • Inference after absorption: Incorporating evidence only simplifies the confactor base, and confactors involving only observed variables can be removed before normalization.The invariant changes from equality to proportionality when such constant contributions are discarded.
  • Posterior computation: For a single query variable, the probability of each query value with the evidence is proportional to the product of applicable confactor contributions.Constants associated with the evidence cancel during normalization.
  • Posterior computation: With multiple query variables, the remaining confactors are multiplied and the result is renormalized.

4.9 The Abstract Contextual Variable Elimination Algorithm

The abstract contextual variable elimination algorithm repeatedly selects a non-query variable and eliminates it from applicable confactors through context-sensitive multiplication, splitting, and summation. Its correctness follows from preserved invariants and termination, while contextual structure can avoid large intermediate factors.

  • Algorithm: The algorithm incorporates evidence, eliminates each non-query variable in a chosen ordering, and then computes the query posterior.The elimination procedure is called once for every non-query, non-observed variable.
  • Algorithm: During elimination, compatible confactors are split and multiplied, while confactors with complementary values of the eliminated variable are summed out.The procedure repeats these operations until the variable is removed from all applicable contexts.
  • Correctness: The procedure is correct because its local operations preserve the program invariants, and it halts because the relevant confactor sets are bounded.When it halts, the eliminated variable has been removed in every context.
  • Context-specific simplification: Contextual elimination can remove trivial one-valued confactors when a variable has no children in a particular context.This generalizes the usual case where a non-observed, non-query node has no children globally.
  • Efficiency example: After eliminating OT, the contextual confactors require a combined FH–MH representation only in contexts where OT is relevant to both houses; their total table size is 24.For other contexts, CVE treats FH and MH separately, avoiding unnecessary combination.

4.13 CVE Compared To VE

CVE and TVE use confactors to exploit contextual structure, but they differ in when compatible confactors are multiplied. In the counterexample, delaying multiplication makes CVE more expensive than both TVE and VE, while preemptive multiplication can improve VE.

  • Tree-based variable elimination: TVE combines VE’s derivation tree with CVE’s confactors, multiplying compatible confactors whenever VE multiplies two factors.The associated confactors maintain mutually exclusive, covering contexts, and their total table size is no greater than the corresponding VE factor size.
  • Contextual variable elimination: CVE delays some multiplications performed by VE, hoping that separate confactors can be simplified before they must be combined.This postponement can save work when eliminating variables simplifies the separate factors before their eventual multiplication.
  • Counterexample: The counterexample uses binary variables except W, whose domain size is 1000, so multiplications involving W dominate the arithmetic.The analysis excludes other multiplications because they total less than one hundred.
  • Counterexample: CVE performs about 20000 multiplications, compared with about 16000 for both TVE and VE in the counterexample.When eliminating C, CVE performs an additional 4000 multiplications, whereas TVE performs none; both methods produce identical resulting confactors.
  • Comparison with VE: VE can also benefit from preemptive multiplication: in Example 23, multiplying P(C) by P(S|BC) before eliminating B is more efficient than delaying it.The example uses the same domain sizes as the counterexample and compares elimination of B followed by C.
  • Limitations: The choice of when to multiply remains a difficult secondary optimization problem, so neither CVE’s delayed strategy nor TVE’s preemptive strategy is generally established as optimal.The paper presents the multiplication strategy as a computationally difficult optimization issue.

5. Avoiding Splitting

Absorption avoids some confactor splitting by combining a complete set of mutually exclusive, covering confactors with another confactor. The method preserves correctness, but its ordering heuristic may not minimize computation.

  • Absorption: A complete multiset of confactors has mutually exclusive and covering contexts.This completeness property lets every relevant context match exactly one confactor in the set.
  • Absorption: Absorption replaces a complete set R and another confactor with products formed against the applicable members of R, avoiding some splitting of the other confactor.Elements of R may still need to be split during multiplication.
  • Correctness: The absorption replacement preserves the program invariant because the resulting confactors remain complete and preserve the represented probability in every complete context.Compatible contexts use the appropriate product, while incompatible contexts remain unchanged.
  • Example: Using the confactors for P(B|Y,Z) as a complete set avoids splitting other confactors on Y when eliminating B.This is illustrated as an application of absorption to the confactors in Figure 4.
  • Correctness: The confactors for any variable remain complete throughout contextual variable elimination.The paper establishes this proposition by showing that splitting, multiplication, and addition preserve completeness.
  • Limitations: Absorption is a heuristic because its imposed multiplication ordering can be less efficient than another associative ordering.The paper notes that determining a better multiplication order may require computationally difficult meta-level analysis.

6. Empirical Results

The empirical results examine whether contextual independence can offset the overhead of maintaining confactors. On the water network and randomized networks, CVE is often or significantly faster than VE, but performance depends on the contexts and elimination ordering.

  • Motivation: Synthetic networks can make VE exponentially worse than CVE, while networks without contextual independence reduce CVE to VE with little overhead.The experiments therefore test when contextual-independence savings outweigh the cost of reasoning about context variables.
  • Pseudo-natural example: The constructed contextual water network used 41 confactors with total table size 5834, compared with tabular representation size 11018.The network had 32 variables, and probabilities within 0.05 were collapsed to create confactors.
  • Pseudo-natural example: The water-network experiment used 60 random queries with 0, 5, and 10 observed variables to compare CVE and VE runtimes.Figure 10 presents the runtimes as a scatterplot, with 20 runs for each observation count.
  • Pseudo-natural example: CVE was often significantly faster than VE on the water network, although some cases were much worse because contextual independence saved no work while context maintenance remained overhead.Inference also became faster as the number of observations increased.
  • Statistical analysis: The water-network runtime comparisons were statistically significant, with the least significant result at the 0.2 level for 10 observations and the others below 0.001.The reported tests used matched-sample t-tests on logarithms of runtimes, whose differences correspond to multiplicative speedups.
  • Randomized networks: In the randomized examples, the number of splits was strongly correlated with the number of distinct variables in splits, limiting how independently those factors could be assessed.The paper conjectures that fewer variables appearing in contexts may improve efficiency because variables appearing only in tables remain in tables.
  • Randomized networks: The randomized-network experiment found CVE significantly faster than VE for the class generated by prioritizing splits on variables appearing in different contexts.The comparison used scatterplots of runtimes for CVE and VE across the generated examples.

7. Comparison With Other Proposals

CVE exploits contextual structure that standard VE and clique-tree methods ignore, but its context-manipulation overhead can erase the advantage when contextual structure is weak.

  • Comparison with other proposals: CVE is compared with earlier rule-based, tree-based, clique-tree, and similarity-network approaches for exploiting context-specific information.The paper positions CVE as a specific algorithm for combining confactors and tables, with broader analysis and empirical evaluation than earlier proposals.
  • Example comparison: CVE creates a maximum confactor table size of 16 in the example where VE creates a factor of size 64 after eliminating B.The same example yields clique sizes of 64 and 32, and those methods do not use the conditional-probability structure.
  • Trade-offs: VE and clique-tree propagation manipulate tables faster than confactors, so CVE is not always competitive despite smaller structural representations.The paper reports cases where confactor and table sizes are equal or where context-manipulation overhead dominates.

8. Conclusion

The paper presents contextual variable elimination for posterior inference in belief networks with context-specific independence and identifies opportunities and unresolved challenges for extending it.

  • Conclusion: Contextual variable elimination computes posterior probabilities while allowing eliminated-variable tables to depend on different variable sets in different contexts.The algorithm is an instance of variable elimination adapted to context-specific independence.
  • Open problems: A central open problem is finding good elimination-ordering heuristics because the exact confactor forms matter, not only the belief-network graph.Existing triangulation heuristics are not directly applicable, and the ordering may not be feasible to compute a priori.
  • Open problems: Opportunistically eliminating variables in some contexts before others may improve efficiency without affecting correctness.The paper describes this as an ongoing direction rather than a completed evaluation.
  • Potential applications: Confactors may support approximation algorithms by preserving fine-grained distinctions and collapsing complementary factors with similar probabilities.The stated potential benefit is more compact confactor bases and reasonable posterior ranges.
  • Follow-up work: Subsequent work extended contextual-independence exploitation to clique trees and multi-agent coordination and planning.These developments are reported as follow-up research to the paper.

A.1 Water Network

The water-network experiment constructs contextual independence by thresholding similar conditional probabilities, producing a smaller contextual representation under a selected threshold.

  • Thresholding: A variable was declared redundant when probability differences across its values were below the 0.05 threshold.Choosing the midpoint of the reduced table kept each original probability within 0.025 of that midpoint.
  • Thresholding: Changing the threshold to 0.03 produced no contextual independence, whereas 0.07 caused the tabular representation to collapse.Threshold choices therefore materially affected both detected structure and representation size.
  • Thresholding: Using 80% or 99% instead of 51% as the threshold for accepting a change produced smaller tables but much larger runtimes.

A.2 Randomised Experiments

The randomized experiments generate contextual belief networks through random decision-tree splits and compare CVE and VE on representation size, runtime, and intermediate-space measures.

  • Example generation: Random networks are generated by imposing a total variable ordering and repeatedly splitting randomly selected decision-tree leaves on eligible predecessor variables.The resulting leaves represent contexts for the variable associated with each tree.
  • Experimental data: The randomized data include cases with five and ten randomly observed variables, alongside other query settings shown in the experiment figures.The appendix identifies these data as details underlying the main-paper runtime comparisons.
  • Measurement protocol: Runtime measurements used Java on a 700 MHz Pentium with 768 megabytes of memory, repeating each evaluation three times and retaining the smallest time.
  • Experimental parameters: The experiment varies n, the number of variables; s, the number of splits and distinct split variables; and p, the probability of splitting on an eligible variable.
  • Measured quantities: The evaluation records contextual-belief-network size, belief-network factor size, CVE and VE runtimes, and each method’s maximum intermediate table-size measure.CVE MTS is the maximum sum of table sizes created while eliminating one variable, whereas VE MTS is the maximum table size created.
Loading 1106.4864v1…