Scaling the Explanation of Multi-Class Bayesian Network Classifiers

Yaofang Zhang; Adnan Darwiche

cs.AIMar 15, 2026

Scaling the Explanation of Multi-Class Bayesian Network Classifiers

Authors: Yaofang Zhang, Adnan Darwiche

Organizations: Department of Computer Science University of California, Los Angeles

Abstract

We propose a new algorithm for compiling Bayesian network classifier (BNC) into class formulas. Class formulas are logical formulas that represent a classifier's input-output behavior, and are crucial in the recent line of work that uses logical reasoning to explain the decisions made by classifiers. Compared to prior work on compiling class formulas of BNCs, our proposed algorithm is not restricted to binary classifiers, shows significant improvement in compilation time, and outputs class formulas as negation normal form (NNF) circuits that are OR-decomposable, which is an important property when computing explanations of classifiers.

Figures & tables

Figure 1: An example Bayesian network. The root variable A is in red, and the leaf variables D, E, F are in green. For simplicity, all variables in this network are binary.

Panel of Figure 2 — Figure 2: (a) An AND-decomposable NNF for the negative instances of $y_{1}$ , and (b) its negation, which is an OR-decomposable NNF of the class formula for $y_{1}$ .

Panel of Figure 3 — Figure 3: (a) An OBDD compiled by [ 27 ] . Solid (or dashed) arrows denote feature set to true (or false). (b) An equivalent OR-decomposable NNF.

Figure 4: A jointree and an f-tree (the sub-tree in the box) for the network in Figure 1 . The nodes are labeled by their clusters and the edges are labeled by their separators. The nodes that include the target variable A are in red, and the nodes that include the features are in green.

network	# features	# unique target $Y$
win95pts	16	33
cpcs54	13	12
andes	19	86
andes	22	86
tcc4e	27	16
tcc4e	30	15

Table 1: Overview of the 554 benchmark problems. With the same network, target, and features, there are two problems with different thresholds.

network	avg $\omega^{\mathcal{T}}$	width $\omega$	$\|\mathbf{X}\|$	$\|\mathbf{X}\|+\omega$
win95	17.1	9	16	25
cpcs54	18.1	14	13	27
andes	27.7	18	22	40

Table 2: Compilation width compared to brute force method. For all networks, all leaves are chosen as features, and

|\mathbf{X}|

denotes the number of features. For each network, the compilation width

\omega^{\mathcal{T}}

is averaged over the the set of targets used in the benchmark. Column

|\mathbf{X}|+\omega

shows the width for brute force method.

	Time (s)		Size (# Nodes)
Y	baseline	proposed	baseline	proposed
TK	11,708	12	47	5
CNBG	24,374	30	2,893	2,453
MDA	26,614	1936	5,454	2,894
VKE	27,495	262	2,107	1,725

Table 3: Time and size comparison for the 4 roots (

Y

) and all leaves in the andes network. Threshold is

0.5

for all problems.

Panel of Figure 6 — Figure 6: The network structure and f-tree of a BNC about the diagnosis of disease. Note that the f-tree shown in (b) is also a jointree of the network.

Figure 7: An OR-decomposable NNF that represents the class formula of disease type 2.

Figure 8: An OR-decomposable NNF representing

\lnot\Delta_{0}

Explainable Artificial Intelligence

Explainable artificial intelligence develops ways to make AI decisions understandable, testable, and useful to people.

See all 324 papers

Parallel Adaptive Multi-Objective Evolutionary Learning of Discretized Bayesian Network Classifiers for Clinical Data
May 27, 2026Damy M. F. Ha, Thalea Schlender, Yvette M. van der Linden +2Bayesian Networks Multi-Objective Evolutionary Optimization
Leiden University Medical Center · Centrum Wiskunde & Informatica
Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding
Sep 4, 2026Arthur Ledaguenel, Florent Capelli, Jean-Marie LagniezExplainable Artificial Intelligence Abductive Reasoning
CRIL, Université d’Artoi · LISIC, ULCO
Neural Logic Networks for Interpretable Classification
Aug 11, 2025Vincent Perreault, Katsumi Inoue, Richard Labib +1Boolean Function Learning Neural Network Interpretability
Department of Mathematics and Industrial Engineering Polytechnique Montréal · National Institute of Informatics, Tokyo

May 27, 2026J/K move · Enter open · S save

Parallel Adaptive Multi-Objective Evolutionary Learning of Discretized Bayesian Network Classifiers for Clinical Data

Damy M. F. Ha, Thalea Schlender, Yvette M. van der Linden, Peter A. N. Bosman+1

Leiden University Medical Center · Centrum Wiskunde & Informatica

Bayesian Networks Multi-Objective Evolutionary Optimization Clinical Decision Support Clinical Outcome Prediction

Open paper AskPDF arXiv

Bayesian Networks (BNs) are of interest from an explainable AI viewpoint, offering transparent probabilistic models for decision support. Baymex is a recently introduced multi-objective evolutionary algorithm for learning discretized BNs, enabling experts to trade-off different objectives of interest, such as likelihood, model complexity, and prior beliefs. While Baymex has been shown to outperform state-of-the-art BN learning approaches, Baymex still 1) requires a lot of computation time and 2) has only been evaluated on synthetic data. To improve scalability, we introduce a parallelization strategy as well as a mechanism that enables adaptively steering optimization toward networks that overfit less. We furthermore reconfigure Baymex to train a BN classifier through multi-objective optimization of cross-entropy loss and the BIC complexity term so as to evaluate its performance on real-world clinical classification tasks. Besides observing speedups up to over 54 times on a 16-core CPU, comparisons against clinically familiar baselines (decision trees, logistic regression, naive Bayes, and random forests) on two open-source (RADCURE and SUPPORT) and one in-house dataset, show that Baymex obtains statistically similar or better predictive performance while producing compact, clinically inspectable BNs. Importantly, Baymex finds multiple plausible BN classifiers that contain predictors consistent with established clinical factors.

Abstract

Explainable Artificial Intelligence

Explore similar work

Parallel Adaptive Multi-Objective Evolutionary Learning of Discretized Bayesian Network Classifiers for Clinical Data

Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding

Neural Logic Networks for Interpretable Classification