Generating Graphoids from Generalised Conditional Probability

Nic WilsonUAI 1994

TL;DR

This paper introduces a generalized framework for conditional probability (GCPPs) to explore the fundamental properties of probabilistic conditional independence, known as graphoid properties. By defining new independence structures within GCPPs and establishing sufficient conditions for these structures to satisfy graphoid axioms, the authors provide a theoretical basis for understanding why probability and other uncertainty formalisms exhibit these properties and how to construct new ones.

What Problem Does This Paper Address?

Probabilistic reasoning relies heavily on the concept of conditional independence, which has been formally captured by the "graphoid" properties. These properties are crucial for efficient inference and representation in probabilistic graphical models. However, the underlying reasons why standard probability theory adheres to these properties, and how other uncertainty formalisms might also exhibit them, are not fully understood. This paper aims to bridge this gap by developing a generalized framework that can accommodate various uncertainty measures and investigating the conditions under which they naturally produce graphoid structures. This allows for a deeper understanding of probabilistic reasoning and opens avenues for building new qualitative reasoning systems.

Methods

The paper introduces Generalised Conditional Probability on Product Spaces (GCPPs) as a flexible framework for uncertainty measures. Within this framework, two types of independence structures, $I_p$ and $I'_p$, are defined based on the properties of the GCPP function. The core of the paper lies in identifying sufficient conditions for these independence structures to satisfy the graphoid properties (Trivial Independence, Symmetry, Decomposition, Weak Union, Contraction, and Intersection).

Key methodological contributions include:

  • Defining GCPPs: A general function $p: U^* \rightarrow D$ where $U^*$ represents combinations of variable values and $D$ is a set of uncertainty values (including 0 and $\infty$).
  • Defining Independence Structures ($I_p$ and $I'_p$): These are derived directly from the GCPP function's behavior under conditioning.
  • Investigating Graphoid Properties: The paper systematically examines each graphoid axiom, proposing specific conditions on the GCPP that guarantee its independence structure satisfies them.
  • Introducing "Conditional Coherence": A key concept that links the behavior of conditional probabilities, providing a bridge between $I_p$ and $I'_p$ and ensuring certain graphoid properties.
  • "p-connectivity": A novel condition related to the zero-values of the GCPP, which is shown to be crucial for satisfying the Intersection property.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Explaining Graphoids: The paper provides a theoretical explanation for why probability distributions (and other specific uncertainty formalisms like Dempster possibility functions) naturally satisfy graphoid properties. It's not magic, but a consequence of their underlying mathematical structure.
  • Beyond Non-Zero Probabilities: The Intersection property, often assumed to hold only for probability distributions that are strictly positive everywhere, is shown to hold under more general conditions related to the connectivity of non-zero values. This is a significant relaxation of previous assumptions.
  • Qualitative Reasoning: The framework naturally extends to qualitative conditional probabilities, suggesting that graphoid structures can be generated from comparative judgements of probability, not just numerical ones.
  • Constructing Uncertainty Calculi: The identified sufficient conditions can be used as building blocks to construct new uncertainty calculi that are guaranteed to generate semi-graphoids or graphoids.
  • The Role of Zero-Values: The paper highlights the critical role of where an uncertainty measure assigns zero (impossibility) in determining its independence structure.

Key Results

  • Sufficient Conditions for Graphoids: The paper presents several propositions detailing specific conditions on GCPPs that guarantee their associated independence structures satisfy various graphoid properties. For instance, "Conditional Coherence" is shown to imply Decomposition and Weak Union, and "p-connectivity" is linked to the Intersection property.
  • GCPPs as a Unifying Framework: Probability functions, Dempster possibility functions, kappa functions, and consistency functions are shown to be specific instances of GCPPs, demonstrating the generality of the proposed framework.
  • Equivalence with Qualitative Conditional Probability: The paper establishes an equivalence between GCPPs and Qualitative Conditional Probabilities (QCPPs), suggesting that graphoid properties can be derived from qualitative relationships.

Limitations and Future Work

  • Symmetry is Hard: The paper notes that finding simple, natural conditions for an independence structure to satisfy Symmetry is challenging. Proposition 3 offers a strong condition, but more general approaches are desired.
  • Approximate Independence: The example in Section 4 suggests that GCPPs, particularly with the $I_p$ definition, might not easily represent "approximate independence," which is a practical concern in real-world reasoning.
  • Computation: While the paper touches upon computation in Section 7, it acknowledges that this is a limited aspect and further work is needed.
  • More Examples: The authors express a need for more "sensible" examples of GCPPs that generate semi-graphoids, especially those with non-totally ordered uncertainty values.
  • Connections to Other Frameworks: The paper suggests exploring connections with other areas like comparative probability and Shenoy's product definition of independence.

Summary updated

BibTeX
@inproceedings{wilson1994generating,
  author = {Nic Wilson},
  title = {{Generating Graphoids from Generalised Conditional Probability}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure