TL;DR
This paper introduces a novel method for uncertain inference in expert systems that avoids strong conditional independence assumptions by leveraging multidimensional contingency tables. It presents a way to update joint probabilities based on new evidence, maintaining existing dependencies, and then directly calculating the conditional probability of a conclusion. This approach offers greater flexibility than traditional methods by handling complex associations between multiple pieces of evidence.
What Problem Does This Paper Address?
Expert systems often need to reason under uncertainty, a task traditionally handled by probabilistic models. A comprehensive way to represent these uncertainties is through multidimensional contingency tables, where each dimension corresponds to a piece of evidence or a conclusion. However, the number of cells in such tables grows exponentially with the number of variables, making it computationally infeasible to estimate all necessary probabilities for even a moderate number of evidence pieces (e.g., 19 pieces of evidence can lead to over a million cells).
Existing solutions often resort to strong assumptions of conditional independence between pieces of evidence, which can lead to theoretical problems if these assumptions are violated in real-world scenarios. Other approaches use parsimonious models (like log-linear models) but still require careful estimation of parameters. This paper tackles the challenge of performing uncertain inference using contingency tables without making strong independence assumptions, especially when new evidence updates the probabilities of existing pieces of evidence.
Methods
The core of the paper's contribution lies in its method for updating inferences from contingency tables when the probabilities of evidence states change. Instead of assuming independence, the method leverages the associations captured in the original contingency table, specifically through odds ratios.
Here's a breakdown of the approach:
- Multidimensional Contingency Tables: The foundation is a contingency table where each dimension represents a piece of evidence and the conclusion. Each cell stores the joint probability of a specific combination of states for these variables.
- Odds Ratios for Association: The paper highlights the odds ratio as a measure of association that is independent of marginal probabilities. By keeping the odds ratios from the original table constant, the method can maintain the existing dependencies between variables even as their marginal probabilities are updated.
- Updating Joint Probabilities: When new marginal probabilities for evidence become available (e.g., due to new observations), the method adjusts the contingency table sub-components (subtables) to reflect these new marginals while preserving the original odds ratios. This is achieved through an iterative proportional fitting algorithm.
- Calculating Conditional Probability: Once the updated joint probabilities for the evidence are obtained, the conditional probability of the conclusion is directly calculated from these new joint probabilities and the conditional probabilities present in the original contingency table.
The method is presented as general, applicable to multi-category evidence and any form of association, and does not require pre-defining which dimensions are evidence or conclusions.
Datasets
Not discussed in the paper. The paper uses a hypothetical example with a contingency table for two pieces of evidence (El and E2) and one conclusion (C) to illustrate its method.
Key Insights and Ideas
- Avoiding Independence Assumptions: The most significant insight is the ability to perform uncertain inference without relying on potentially unrealistic conditional independence assumptions. This makes the method more robust and applicable to complex real-world scenarios where evidence is often correlated.
- Odds Ratios as Anchors: Using odds ratios to maintain associations is a clever way to update probabilities. Odds ratios are invariant to changes in marginal probabilities, making them ideal for preserving the underlying structure of dependencies when new evidence shifts the likelihood of individual events.
- Iterative Proportional Fitting for Adjustment: The paper points to iterative proportional fitting as a practical algorithm for adjusting contingency tables to new marginal probabilities while preserving odds ratios. This is a well-established technique in statistical modeling, adapted here for inference engine purposes.
- Generalizability: The method's claim of generality across multi-category evidence and various association types is a strong point, suggesting a broad applicability beyond simple binary cases.
Key Results
The paper primarily focuses on presenting a method rather than reporting quantitative results from empirical evaluations on specific datasets. The key "result" is the demonstration of how the proposed method can:
- Calculate conditional probabilities of a conclusion given updated evidence probabilities.
- Maintain associations between pieces of evidence as captured by odds ratios from an original contingency table.
- Avoid the computational explosion of full contingency tables by working with relevant subtables and preserving key association measures.
An example is provided (Figure 2) showing how a subtable is adjusted from original marginal probabilities to new ones while keeping the odds ratio constant.
Limitations and Future Work
- Computational Cost: While the method aims to mitigate the problem of large contingency tables by focusing on relevant subtables, the paper acknowledges that situations may arise where even these subtables become too large for the iterative proportional fitting algorithm.
- Subtable Construction: The entire subtable must be explicitly constructed and stored, which could still be a limitation for very large systems.
- Model Selection: The paper notes that predicting which associations will exist in a marginal subtable is difficult. This implies that fitting parsimonious models might still require assumptions about certain effects being null or comparing multiple models.
- Future Research: The authors suggest future work is needed to compare the practical value of their approach with other methods (like Cheeseman's maximum entropy approach) and to improve the computational efficiency for full-scale implementations. They also mention that Cheeseman's procedure might be useful for cases where new marginal probabilities are given as intervals rather than point values.
Summary updated