Optimal Feature Selection for Decision Robustness in Bayesian Networks

Optimal Feature Selection for Decision Robustness in Bayesian Networks

YooJung Choi, Adnan Darwiche, Guy Van den Broeck

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 1554-1560. https://doi.org/10.24963/ijcai.2017/215

In many applications, one can define a large set of features to support the classification task at hand. At test time, however, these become prohibitively expensive to evaluate, and only a small subset of features is used, often selected for their information-theoretic value. For threshold-based, Naive Bayes classifiers, recent work has suggested selecting features that maximize the expected robustness of the classifier, that is, the expected probability it maintains its decision after seeing more features. We propose the first algorithm to compute this expected same-decision probability for general Bayesian network classifiers, based on compiling the network into a tractable circuit representation. Moreover, we develop a search algorithm for optimal feature selection that utilizes efficient incremental circuit modifications. Experiments on Naive Bayes, as well as more general networks, show the efficacy and distinct behavior of this decision-making approach.
Keywords:
Machine Learning: Feature Selection/Construction
Uncertainty in AI: Bayesian Networks
Uncertainty in AI: Decision/Utility Theory
Knowledge Representation, Reasoning, and Logic: Tractable languages and knowledge compilation