Source-linked AI summary
A Symbolic Approach to Explaining Bayesian Network Classifiers
Andy Shih, Arthur Choi, Adnan Darwiche
TL;DR
The paper addresses how to explain positive or negative decisions made by Bayesian network classifiers. It compiles their decision functions into tractable symbolic ODDs, then computes two minimal explanation types; the approach covers naive and latent-tree classifiers. Its scope includes structural assumptions affecting compilation complexity.
Problem
Classifier decisions increasingly require explanations, but Bayesian network classifiers need a symbolic and tractable representation for efficient reasoning about why a decision was made.
Method
The paper compiles naive and latent-tree Bayesian network classifier decision functions into ODDs and computes minimum-cardinality and prime-implicant explanations.
Results
The proposed ODD compilation supports efficient computation of both explanation types for Bayesian network classifiers and applies more generally to symbolic decision functions.
Takeaways & Limitations
The framework provides symbolic explanations identifying either the active features responsible for a classification or the fixed features sufficient to preserve it.
Takeaways & Limitations
Compilation complexity depends on assumptions about latent-tree structure, while actual time and space usage can vary with classifier parameters and variable ordering.
Abstract
from arXiv · showhide
We propose an approach for explaining Bayesian network classifiers, which is based on compiling such classifiers into decision functions that have a tractable and symbolic form. We introduce two types of explanations for why a classifier may have classified an instance positively or negatively and suggest algorithms for computing these explanations. The first type of explanation identifies a minimal set of the currently active features that is responsible for the current classification, while the second type of explanation identifies a minimal set of features whose current state (active or not) is sufficient for the classification. We consider in particular the compilation of Naive and Latent-Tree Bayesian network classifiers into Ordered Decision Diagrams (ODDs), providing a context for evaluating our proposal using case studies and experiments based on classifiers from the literature.
1 Introduction
The paper frames classifier explainability as a need for symbolic, tractable reasoning about Bayesian network decisions. It proposes compiling decision functions into ODDs and introduces minimum-cardinality and prime-implicant explanations.
- Motivation: AI deployment has increased the need to explain classifier decisions, including decisions involving loans, admissions, and medical recommendations.The paper connects why-questions with assigning blame and responsibility in contexts such as legal systems.
- Decision functions: A classifier’s decision function is a symbolic yes/no mapping from discrete features, independent of how the classifier is implemented.The authors seek a tractable representation that supports symbolic and efficient reasoning about classifier behavior.
- Compilation: Ordered Decision Diagrams extend OBDDs to multi-valued discrete features while retaining tractability and OBDD properties.Prior work showed that naive Bayes decision functions can be compiled into ODDs.
- Contributions: The paper proposes compiling decision functions into ODDs to enable efficient classifier explanations through two explanation types.The paper’s introduction identifies this compilation-and-explanation framework as its central contribution.
- Minimum-cardinality explanations: Minimum-cardinality explanations identify a minimal subset of currently positive features responsible for preserving the current classification.They are motivated by distinguishing positive test results that are necessary from those that can be changed without altering the decision.
- Prime-implicant explanations: Prime-implicant explanations identify the smallest fixed subset of features that makes all remaining features irrelevant to the current decision.Features outside this subset may be toggled arbitrarily while maintaining the classifier’s decision.
2 Compiling Bayesian Network Classifiers
The paper compiles Bayesian network classifiers into symbolic, tractable decision diagrams whose decisions match the original classifiers. It develops compilation procedures for naive Bayes and latent-tree classifiers, with complexity bounds and an NP-hardness result for naive Bayes compilation.
- Decision functions: An ODD represents a classifier’s decision function, mapping feature assignments to positive or negative decisions independently of implementation.For naive Bayes, navigating the diagram on observed test results reaches a yes/no leaf matching the classifier’s output.
- Decision functions: ODDs support efficient reasoning, including counting positive instances and Boolean operations, which enables efficient explanation generation.This tractability is the computational basis for generating explanations from compiled classifiers.
- Naive Bayes classifiers: Naive Bayes compilation expands the decision graph by features and merges nodes representing equivalent classifiers, retaining the established complexity bounds.The simpler procedure may be less efficient in practice than the earlier algorithm, despite having the same bounds.
- Latent-tree classifiers: The proposed latent-tree procedure iteratively selects internal nodes, expands over their descendant leaves, and shrinks the classifier through adjusted class priors.Its node-selection strategy yields explicit size and time bounds for the resulting ODD.
- Latent-tree classifiers: The latent-tree ODD has size O(b^4) and compilation time O(nb^3n), with improved bounds under additional structural assumptions.Under the stated root-and-subtree assumptions, the bounds become O(b^2n) for size and O(nb^2n) for time.
- Complexity: Compiling an ODD for a naive Bayes decision function is NP-hard, although actual time and space can be much lower depending on classifier parameters and variable order.The paper therefore does not expect a significantly better general upper bound on compilation time.
3 Minimum Cardinality Explanations
Minimum-cardinality (MC) explanations identify the smallest set of active features responsible for a classifier’s decision. For OBDD-represented decision functions, the paper gives a linear-time method for computing them and illustrates their use on admissions and voting classifiers.
- Definition: MC-explanations identify which positive or negative features are responsible for a classifier’s current decision.They are defined through minimal positive or negative instances under feature-set inclusion.
- Admissions example: The admissions example uses work experience and good GPA as a cardinality-2 explanation for admission.The student would still be admitted without prior application and without passing the entrance exam.
- Admissions example: Rejected admissions decisions can have multiple MC-explanations, each identifying a different feature that could change without reversing rejection.For one rejected student, the explanations permit either passing the entrance exam or being a first-time applicant while preserving rejection.
- Computation: Algorithm 3 computes MC-explanations by restricting the decision function to the instance, complementing negative decisions, and applying cardinality minimization.The resulting decision function encodes exactly the MC-explanations for the selected decision.
- Computation: Linear time and space in the OBDD size are guaranteed for computing MC-explanations, with linear-time counting and enumeration under OBDD operations.The output explanation function is also an OBDD.
- Votes case study: On the votes dataset, the classifier achieved 91.0% accuracy and compiled to a 630-node OBDD.For a correctly classified Congressman, five MC-explanations of cardinality 3 were reported, and four yes-votes could be reversed under one explanation.
4 Prime Implicant Explanations
Prime-implicant (PI) explanations identify a minimal subset of the current feature assignment that makes all remaining features irrelevant to the decision. The paper represents and computes these explanations with ODDs, including instance-specific algorithms and classifier case studies.
- Definition: PI-explanations are minimal partial instances whose fixed features allow all outside features to vary without changing the current decision.Their length is the number of features fixed in the partial instance.
- Admissions example: For the admissions classifier, a rejected student has a single PI-explanation: poor entrance exam and poor GPA.Those two conditions suffice for rejection regardless of the remaining feature values.
- Admissions example: For an admitted student, three PI-explanations have different lengths, unlike the single MC-explanation previously obtained.They correspond to different partial assignments with don’t-care features.
- Representation: ODDs encode PI-explanations using three values for each feature: 0, 1, and ∗ for don’t care.Positive-instance explanations come from prime implicants of the decision function, while negative-instance explanations use its complement.
- Computation: Algorithm 5 computes only prime implicants compatible with the target instance, avoiding recursive calls for incompatible explanations.The paper reports that it can be twice as fast as first computing all prime implicants and then filtering them.
- Votes case study: For the votes classifier, one decision has 30 PI-explanations, including two shortest explanations of 9 features.Across all classifier decisions, the paper reports 506 PI-explanations.
5 More On Monotone Classifiers
For monotone classifiers, MC-explanations and shortest PI-explanations coincide under the paper’s matching relation. MC-explanations additionally have no greater length or count and can be computed in linear time from OBDDs.
- Matching: The paper defines matching by completing a PI-explanation’s missing features negatively for positive instances and positively for negative instances.This relates partial PI assignments to complete MC assignments.
- Theorem: For monotone decision functions, every MC-explanation matches a shortest PI-explanation, and every shortest PI-explanation matches an MC-explanation.These are the two claims of Theorem 4.
- Consequences: Therefore, MC-explanations coincide with shortest PI-explanations for monotone decision functions.The admissions classifier exemplifies this correspondence, whereas the votes classifier is not monotone.
- Consequences: MC-explanations are no longer than PI-explanations and are no more numerous.Given an OBDD, MC-explanations can be computed in linear time, a guarantee not provided for PI-explanations.
- Generalization: PI-explanations extend directly to multi-valued features and arbitrary classifiers, while MC-explanations can be generalized through on-value and off-value partitions.The original MC definition is directed toward monotone classifiers with binary features.
6 Related Work
The paper situates its symbolic explanations alongside model-agnostic explainers, especially anchors. Anchors provide probabilistic stability guarantees, whereas PI-explanations require the decision to remain fixed under every completion.
- Model-agnostic explainers: Model-agnostic explainers such as LIME treat classifiers as black boxes and locally explain an instance’s classification.The paper contrasts this setting with its symbolic decision-function approach.
- Anchors: An anchor is a subset of an instance likely to preserve the classification under feature completions drawn from a distribution.The paper characterizes anchors as a probabilistic extension of PI-explanations.
- Anchors: A PI-explanation has an SDP of 1.0 because every completion of its unspecified features preserves the classification.Anchors are expected to have high, rather than necessarily perfect, SDP.
7 Conclusion
The paper compiles latent-tree Bayesian network classifiers into tractable ODD-based decision functions and computes two explanation types for classifier decisions.
- MC-explanations minimize the number of positive features while preserving an instance’s classification.
- PI-explanations identify the smallest feature set that renders remaining features irrelevant to the classification.
- For monotone classifiers, MC-explanations and PI-explanations coincide.
A Proofs
The proofs establish bounds and complexity consequences for compiling Bayesian-network decision functions into ODDs, including NP-hardness and linear-time symbolic operations.
- Compilation bounds: The decision graph has total size O(nb^4) under the stated leaf-count bounds and expand-then-merge procedure.The proof bounds each expanded graph by b^4 leaf nodes before accounting for repeated calls and merging.
- Compilation bounds: The construction’s time complexity is O(nb^4 log(nb^4)) because merging nodes takes logarithmic time in the decision-graph size.
- Complexity: Compiling the decision function is NP-hard because polynomial-time compilation would enable linear-size model counting and solve number partitioning.
- Symbolic operations: An OBDD can be complemented, conjoined with a conjunction of literals, and i-minimized in time linear in its size.
- Explanation equivalence: For monotone decision functions, shortest MC- and PI-explanations correspond through the positive features preserved in the classification.