  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.
