Abstract
This paper considers the problem of removing costly features from a Bayesian network classifier. We want the classifier to be robust to these changes, and maintain its classification behavior. To this end, we propose a closeness metric between Bayesian classifiers, called the expected classification agreement (ECA). Our corresponding trimming algorithm finds an optimal subset of features and a new classification threshold that maximize the expected agreement, subject to a budgetary constraint. It utilizes new theoretical insights to perform branch-and-bound search in the space of feature sets, while computing bounds on the ECA. Our experiments investigate both the runtime cost of trimming and its effect on the robustness and accuracy of the final classifier.
Introduction
In high-stakes domains such as medicine and robotics, Bayesian network classifiers (BNCs) are often constructed using significant expert knowledge. While these models are powerful, they can be "expensive" to deploy if they require numerous inputs, such as invasive medical tests or high-latency sensor data. Traditional feature selection methods typically optimize for predictive accuracy. However, this approach can be insufficient because it ignores the expert-informed logic of the original model and may lead to different failure modes or biases.
This paper introduces "classifier trimming," a method to reduce the number of features to fit a budget while remaining robust to these changes. The goal is to ensure the leaner model behaves as much like the original, expert-informed model as possible.
Methodology: Expected Classification Agreement (ECA)
The authors propose a new objective function: Expected Classification Agreement (ECA). This metric measures the probability that a trimmed classifier—utilizing a subset of features and an optimized classification threshold ($T$)—will yield the same classification as the original, full-featured model.
The ECA-TRIM Algorithm
To find the optimal feature subset, the authors developed ECA-TRIM, a branch-and-bound search algorithm. The search space for feature subsets is large, so the algorithm utilizes a monotonic upper bound called the Maximum Potential Agreement (MPA) to prune the search tree efficiently.
The method leverages tractable circuits, specifically Sentential Decision Diagrams (SDDs), to compute these probabilistic objectives efficiently, even in complex networks. A critical component of the trimming process is Threshold Optimization, where the classification threshold of the new model is adjusted to better mimic the original model's behavior rather than relying on a default threshold.
Experimental Results and Insights
The researchers evaluated ECA-TRIM across various benchmarks, including UCI datasets and standard Bayesian networks like alarm and win95pts.
The Robustness-Accuracy Tradeoff
A key finding is the existence of a "Pareto frontier" between agreement and accuracy. As shown in the experimental data, the model that maximizes accuracy is not always the one that most closely mimics the original model's behavior.
Agreement as a Regularizer
Interestingly, optimizing for ECA can sometimes lead to better test accuracy than optimizing for accuracy directly. For example, on the heart dataset, the ECA-optimized model achieved a test accuracy of 84.9%, compared to 79.2% for the model optimized for accuracy. This suggests that ECA acts as a regularizer, allowing the trimmed model to "inherit" the generalization properties of the original expert model and protecting it from overfitting on small feature subsets.
Conclusion
ECA-TRIM provides a robust framework for feature selection that prioritizes behavioral consistency with a reference model. By dynamically adjusting thresholds and utilizing efficient branch-and-bound search, the method consistently produces classifiers that are more similar to the original expert models than those selected via standard information-theoretic methods. Future work includes extending this framework to multi-class variables and further optimizing circuit compilation for high-treewidth networks.
Summary updated