Exploiting Qualitative Knowledge in the Learning of Conditional Probabilities of Bayesian Networks

Frank Wittig, Anthony JamesonUAI 2000

TL;DR

This paper introduces a novel method for incorporating qualitative domain knowledge (like "if X increases, Y tends to increase") into the learning of Bayesian Networks (BNs). By penalizing violations of these constraints during the learning process, they achieve BNs that are not only more interpretable but also more accurate, even with limited data.

What Problem Does This Paper Address?

Learning the conditional probability distributions (CPTs) for Bayesian Networks (BNs) from data is a crucial task in AI. Standard learning algorithms, like EM and APN, often struggle when BNs include hidden variables, leading to locally optimal solutions that might not reflect intuitive, qualitative relationships in the domain. This can result in BNs that are hard to understand and explain, even if they fit the observed data reasonably well. The authors aim to bridge this gap by allowing domain experts to inject their qualitative understanding into the learning process, guiding the algorithm towards more meaningful and accurate models.

Methods

The core of the paper is the integration of qualitative constraints into the BN learning objective function. They propose augmenting the standard log-likelihood score with a penalty term that quantifies the violation of specified qualitative influences.

  • Qualitative Influences: They formalize "qualitative influences" as monotonic relationships between variables, denoted as $S^?(X_w, X_z)$, where $?$ can be '+' (positive influence) or '-' (negative influence). This means an increase in $X_w$'s state should lead to a corresponding increase or decrease in $X_z$'s state, respectively.
  • Violation Term: A function, violation(θ, C), is defined to measure the extent to which a BN's CPTs (θ) violate a set of constraints (C). This term is designed such that it's zero when constraints are met and increases with the severity of violations.
  • Modified Scoring Function: The learning objective becomes maximizing log P(D|θ) - w * violation(θ, C), where w is a weight controlling the influence of the constraints.
  • Algorithm Adaptations:
    • APN (Adaptive Probabilistic Networks): The gradient-based APN algorithm is adapted by adding the gradient of the violation term to the standard gradient of the log-likelihood.
  • EM (Expectation-Maximization): A hybrid approach is proposed for EM. It alternates between standard EM steps (to improve data fit) and gradient-based steps (to reduce constraint violations). This is a heuristic but practical way to incorporate constraints.

Datasets

The paper uses synthetic data generated from two predefined BN structures. These structures were chosen to represent:

  1. A domain where the interpretability of a single hidden variable is important (inspired by a hypothetical assistance system).
  2. An abstract example to test the approach on networks with multiple hidden variables.

The synthetic data was generated from "original" BNs that perfectly satisfied the specified qualitative constraints. The authors generated 1,000 learning cases for the first structure and 200 for the second, along with separate test sets of 10,000 and 5,000 cases, respectively.

Key Insights and Ideas

  • Constraints as a "Soft" Prior: Qualitative constraints aren't treated as hard rules but as a soft prior that guides the search. The penalty term allows the learning algorithm to deviate slightly if it significantly improves data fit, but strongly discourages solutions that violate the expert's knowledge.
  • Improved Interpretability and Accuracy: The core insight is that by incorporating qualitative knowledge, the learning process is steered towards models that are not only more aligned with human intuition but also more accurate in their predictions.
  • Limiting Overfitting: The constraints act as a natural regularizer, preventing the model from overfitting to the training data by penalizing solutions that might fit the data perfectly but violate domain knowledge.
  • Robustness to Termination Point: The constrained learning process appears to be less sensitive to the exact termination point of the iterative algorithm, yielding good results even if the learning is stopped prematurely (but not too early).

Key Results

  • Constraint Fulfillment: BNs learned with the modified algorithms exhibited "essentially zero" constraint violations, while those learned without constraints showed "substantial violations."
  • Improved Test Data Fit: Constrained BNs achieved a better fit to unseen test data compared to unconstrained BNs. For Network Structure 1, they were 9% closer to the baseline fit of the original BN, and for Network Structure 2, they were 57% closer on average.
  • Reduced Overfitting: Unconstrained BNs showed a greater tendency to overfit the learning data compared to the constrained BNs.
  • Time Course Analysis: The hybrid EM approach showed an initial phase where unconstrained BNs might fit test data better, followed by a crossover where constrained BNs take the lead. This is attributed to the algorithm prioritizing constraint satisfaction early on.

Limitations and Future Work

  • Heuristic EM Adaptation: The adaptation of the EM algorithm is described as "theoretically less elegant" and heuristic, alternating between EM and gradient steps. The authors acknowledge that a more direct theoretical derivation for EM with constraints is a subject for future research.
  • Arbitrary Constraint Function: The specific form of the violation function (Equation 3) is acknowledged as partly arbitrary and would ideally require empirical research to determine more precise relationships between violations and expert judgments.
  • Generalization to Other Constraints: The paper focuses on "qualitative influences" but suggests the method can be extended to more complex qualitative relationships.
  • Larger Networks and Real Data: Future work includes testing the approach on larger networks and with empirically collected data, as well as systematically exploring the impact of various parameters (weight w, number of constrained variables).

Summary updated

BibTeX
@inproceedings{wittig2000exploiting,
  author = {Frank Wittig and Anthony Jameson},
  title = {{Exploiting Qualitative Knowledge in the Learning of Conditional Probabilities of Bayesian Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2000},
}

Loading related content...

Figure