Additive Belief-Network Models

Paul Dagum, Adam GalperUAI 1993

TL;DR

This paper introduces Additive Belief-Network Models (ABNMs) as an approximation technique to make probabilistic inference in large, complex belief networks computationally tractable. ABNMs decompose complex conditional probability distributions into sums of simpler, additive terms, significantly reducing inference complexity while maintaining a good approximation of the original model.

What Problem Does This Paper Address?

Probabilistic inference in Bayesian belief networks, while powerful for modeling complex dependencies, becomes computationally intractable for large domains. This is because exact and approximate inference algorithms are NP-hard, requiring an exponential number of computations in the worst case. Existing methods to overcome this, like noisy OR-gates or probabilistic similarity networks, often impose strong structural constraints that limit their expressiveness. This paper addresses the need for a more general approximation method that can handle large domains while offering significant computational gains for inference and model induction.

Methods

The core innovation is the additive belief-network model (ABNM). This approach decomposes a complex conditional probability distribution, Pr[Y|X1, ..., Xp], into a sum of simpler terms, Pr[Y|Si], where Si are subsets of the predictors.

  • Additive Decomposition: The key idea is to express the conditional probability of a variable Y given its parents {X1, ..., Xp} as a weighted sum of conditional probabilities given subsets of these parents: Pr[Y|X1, ..., Xp] = Σ αᵢ Pr[Y|Sᵢ] where Sᵢ are subsets of {X1, ..., Xp} and Σ αᵢ = 1. This is analogous to additive models in statistics, where the effect of predictors is additive.

  • Generalization: ABNMs are more general than simple additive models, allowing for interaction terms (e.g., Pr[Y|Xᵢ, Xⱼ]).

  • Intercausal Dependence: The paper argues that additive decomposition is particularly justified when predictors exhibit "intercausal dependence" (e.g., a riot making a burglary more likely). In such cases, observing both causes doesn't necessarily increase belief as much as independent causes would, which additive models can capture.
  • Inference Algorithm: The authors propose an inference algorithm that leverages the additive decomposition. It works by dissecting the belief network at decomposable nodes (nodes with additive decompositions) into smaller subnetworks. Inference is then performed on these subnetworks using standard algorithms like Lauritzen-Speiglehalter (L-S), and the results are combined. This dissection significantly reduces the size of the largest cliques in the triangulated graph, a key factor in the L-S algorithm's complexity.
  • Parameter Estimation: The weights (αᵢ) are treated as probabilities and can be estimated using Bayesian updates with new evidence. The paper also discusses minimizing cross-entropy between the ABNM and the full belief network to find optimal parameters.

Datasets

The paper uses the ALARM network (specifically a subnetwork called AlarmX) for demonstrating the inference algorithm and evaluating the cross-entropy. No new datasets are introduced.

Key Insights and Ideas

  • Additive Decomposition as a Trade-off: ABNMs offer a principled way to trade off predictive accuracy for computational efficiency, particularly in large domains where exact inference is infeasible.
  • Intercausal Dependence Justifies Additivity: The presence of intercausal dependence between predictors makes additive decomposition a more suitable approximation, as it naturally handles situations where observing multiple causes doesn't yield a synergistic increase in belief.
  • Dissection for Tractable Inference: Decomposing the network at additive nodes breaks down large cliques into smaller ones, drastically reducing the computational burden of standard inference algorithms like L-S. This is a key insight for making inference tractable.
  • Generalization Beyond Simple Additivity: Allowing for interaction terms in the additive decomposition (e.g., Pr[Y|Xᵢ, Xⱼ]) makes ABNMs more expressive than basic additive models.

Key Results

  • Reduced Inference Complexity: In the AlarmX example, dissecting a node with an additive decomposition reduced the size of the largest clique from 5 nodes (size 3125) to 3 nodes (size 125), a significant reduction in computational requirements.
  • Good Approximation Quality: The paper reports a cross-entropy value of 0.311079 for the AlarmX example, indicating that the ABNM provided a comparable model to the full belief network.
  • Marginal Probability Accuracy: For the AlarmX example, the ABNM produced marginal probabilities for nodes that were very close to those of the full belief network, with only minor differences observed for one node.
  • Efficiency in Induction: The paper suggests that ABNMs can also improve the efficiency of model induction from data, especially when data is scarce, by reducing the number of parameters that need to be estimated.

Limitations and Future Work

  • Approximation Error: ABNMs are approximations, and while the paper demonstrates good results, there's an inherent loss of accuracy compared to the full model. The quality of the approximation depends on how well the additive decomposition captures the true dependencies.
  • Choosing the Decomposition: The paper acknowledges that a "poorly chosen decomposition" can introduce biases. Future work includes developing search strategies to find the optimal decomposition that minimizes cross-entropy.
  • Extension to Log-linear Models: The authors suggest extending ABNMs to log-linear models.
  • Further Testing: More extensive testing and validation of the methodology on various domains are planned.

Summary updated

BibTeX
@inproceedings{dagum1993additive,
  author = {Paul Dagum and Adam Galper},
  title = {{Additive Belief-Network Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1993},
}
Figure