Abstract
This paper introduces a novel framework for "trimming" Bayesian network classifiers—a process of removing expensive or invasive features while ensuring the reduced model maintains behavioral consistency with the original. Unlike traditional feature selection that prioritizes predictive accuracy, this approach optimizes for Expected Classification Agreement (ECA). By leveraging threshold optimization and a branch-and-bound search algorithm guided by tractable probabilistic circuits, the authors demonstrate a robust method for reducing model complexity without sacrificing the expert knowledge embedded in the original classifier's decision logic.
Introduction
In high-stakes domains such as medicine and robotics, Bayesian classifiers are frequently constructed using significant expert priors and structural assumptions. However, at the point of prediction, certain features may be prohibitively costly to observe, such as invasive medical procedures or resource-intensive sensor data.
Standard feature selection methods typically aim to maximize accuracy on a reduced feature set. However, the authors argue that accuracy alone is an insufficient metric for model reduction. Two models can achieve identical accuracy while exhibiting vastly different behaviors—failing on different cases or manifesting different biases. For a trusted, complex model, the goal of reduction should be to find a replacement that "agrees" with the original's decisions as closely as possible under a fixed budget.
Methodology
The proposed classifier trimming framework rests on three primary pillars:
- Expected Classification Agreement (ECA): This metric quantifies the probability that a trimmed classifier will return the same label as the original model across the distribution of all possible instances.
- Threshold Optimization: Traditional feature selection often keeps the classification threshold fixed (e.g., 0.5). Trimming treats the threshold $T'$ of the reduced model as a variable to be optimized, re-centering the model's logic around the remaining features to maximize agreement.
- Branch-and-Bound Search (ECA-TRIM): To navigate the exponential search space of feature subsets, the authors employ a search algorithm guided by a new upper bound called Maximum Potential Agreement (MPA). For Naive Bayes models, this bound is equivalent to the Maximum Achievable Agreement (MAA), enabling highly efficient pruning.
Technically, the framework utilizes Sentential Decision Diagrams (SDDs)—a type of tractable probabilistic circuit—to compute agreement metrics efficiently. This allows the system to handle the complex probabilistic dependencies inherent in general Bayesian networks.
Experimental Evaluation
The researchers evaluated the ECA-TRIM algorithm against several benchmarks, including standard UCI datasets (pima, heart, hepatitis) and complex general networks (alarm, win95pts).
Key findings include:
- Behavioral Preservation: Trimmed classifiers remained sensitive to the original model's specific thresholding logic, whereas Information Gain (IG)-based selection was often "blind" to the original threshold.
- Computational Efficiency: The branch-and-bound approach provided massive speedups. For the hepatitis dataset, ECA-TRIM found the optimal solution by evaluating only 8% of possible subsets, while exhaustive search timed out.
- Accuracy vs. Agreement: The paper identifies a Pareto frontier between these two metrics. Interestingly, on the heart dataset, optimizing for agreement with a high-quality original model actually yielded better test accuracy than direct accuracy optimization, suggesting that ECA may be less prone to overfitting.
Conclusion
Robust trimming offers a principled way to simplify Bayesian classifiers while preserving their underlying decision logic. By treating the classification threshold as a control knob and optimizing for agreement, the method ensures that reduced models remain faithful to the expert-tuned originals. Future work includes extending the framework to multi-class problems and further optimizing the underlying SDD compilation for massive, high-treewidth networks.
Summary updated