On Robust Trimming of Bayesian Network Classifiers

1 Introduction

Bayesian classification plays a prominent role throughout machine learning [Wu et al., 2008; Laidlaw et al., 1998; Metsis et al., 2006]. In this setting, one has a model that specifies a probability distribution Pr over a set of variables, including class variable C and attributes or features F = {F1, . . . , Fn}. Given a particular instance, described as an assignment to features f = {f1, . . . , fn}, this model is used to compute the posterior probability Pr(C|f1, . . . , fn) which is then compared against a threshold T to classify the instance.

In practice, observing features often has a cost, and one typically needs to keep it within a given budget. For example, features in a medical diagnosis may be invasive, time-consuming, or expensive medical tests [Kononenko, 2001]. Similar issues arise in active sensing [Gao and Koller, 2011], adaptive testing [Mill´an and P´erez-De-La-Cruz, 2002; Munie and Shoham, 2008], and robotics [Kollar and Roy, 2008]. This problem has been studied from different angles, often under the umbrella of feature selection. For example, one may select features at learning time based on their relevance, redundancy, or classification accuracy [Kira and Rendell, 1992; Yu and Liu, 2004]. Alternatively, features may be selected at prediction time based on their expected misclassification cost or information gain [Bilgic and Getoor, 2011; Krause and Guestrin, 2009; Zhang and Ji, 2010]. Such probabilistic objectives are computed on the distribution of the Bayesian classifier.

This paper approaches the problem from a different perspective, which we call classifier trimming. In addition to selecting features that fit the budget, trimming adjusts the threshold T to induce a new classifier. Moreover, instead of simply optimizing the predictive accuracy, we want trimming to be robust. That is, we want to preserve the original classifier's general behavior. Our motivation is two-fold. First, Bayesian classifiers often incorporate significant expert knowledge in the form of priors, structural assumptions, and choice of distribution class [Lucas, 2001]. This is particularly true in medical applications where data is scarce [Bellazzi and Zupan, 2008]. Second, two classifiers with the same predictive quality can exhibit vastly different behavior and failure modes. For example, Zhao et al. [2017] describe two classifiers with a similar accuracy, but markedly different amounts of gender bias in their predictions. In either scenario, it is essential to retain the desired behavior of the original classifier during trimming.

Figure 1 depicts a classifier utilizing three features Q = {Q1,Q2,Q3} with a threshold of T = 0.07. Consider two possible trimmings of this classifier: one obtained by removing Q2 and adjusting the threshold to 0.10, the other with Q1 removed and the threshold changed to 0.30. The trimmed classifiers are clearly less expensive than the original one, but how do we quantitatively compare and choose between these trimmings? To answer this question, we introduce the notion of expected classification agreement (ECA). It is an expectation of the two classifiers agreeing on instances, measuring how much behavior from the original classifier is preserved.

Probabilistic graphical models, such as Bayesian networks, are often used to represent the Bayesian classifier's distribution. We propose an algorithm to find the best trimming of a Bayesian network classifier subject to a budgetary constraint. The algorithm selects features and chooses a new classification threshold in order to maximize the ECA. We also propose a specialized algorithm for the case of naive Bayes classifiers [Friedman et al., 1997; Cheng and Greiner, 1999] that exploits the naive Bayes independence assumptions for more efficient trimming. These novel trimming algorithms are based on the following progression of ideas. First, we show how an existing compilation algorithm to compute expected samedecision probability (E-SDP) can be modified to compute the ECA between a classifier and its trimming [Choi et al., 2017]. This objective was previously used for feature selection where the classification threshold remains fixed [Chen et al., 2015]. Second, we propose an upper bound on the ECA that can be computed more efficiently, enabled by our formulation that adjusts the threshold. Lastly, we use this upper bound to effectively trim classifiers with branch-and-bound search.

Finally, with evaluation on real-world data, we show that our approach finds robust trimmings and demonstrate the relationship between robustness and accuracy. We also illustrate the importance of optimizing the threshold for both classification similarity and efficiency of search. Moreover, we show that our trimming approach consistently returns a classifier that is significantly more similar to the original classifier than selecting features based on information gain.

2 Expected Classification Agreement

We use the standard notation where variables are denoted by upper case letters (X) and their instantiations by lower case letters (x). Sets of variables are denoted in bold upper case (X) and their joint instantiations in bold lower case (x). Concatenations of sets (XY) represent their union.

A binary Bayesian classifier is a tuple α = (C, F, T ), where C is a binary class variable, F are (possibly multi-valued) features, and T is a threshold. On a joint probability distribution Pr(.) over variables C and F, the classification function is

For example, with a threshold of 0.5, an instance will be classified into the more probable class after observing its features.

Next, we motivate and define our proposed closeness measure between classifiers, quantifying their expected agreement.

2.1 Example andMotivation

Consider again the scenario shown in Figure 1, where an instructor uses a quiz to test students' knowledge. The quiz contains three independent questions: Q1 is strongly indicative of being knowledgeable, Q2 is an easy question, and Q3 is a hard question (only 40% of the knowledgeable students answer it correctly). The subject of this quiz is quite difficult, and only 10% of the students are expected to master it, as reflected by the prior on class variable C. Hence, the instructor sets a lenient threshold of T = 0.07 to avoid failing students who may have grasped the subject.

According to this classifier, a student will pass the quiz precisely when their answer matches one of the following three (out of eight) outcomes: {Q1 =+,Q2 =+,Q3 =+}, {Q1=+,Q2=+,Q3=-}, and {Q1=+,Q2=-,Q3=+}. Moreover, the probability of seeing one of these outcomes is 32%: the fraction of students that are expected to pass the quiz. Suppose now that we drop questions Q1 and Q2, relying solely on question Q3 to evaluate students (using the same threshold). Since Pr(C = + | Q3) is always greater than T = 0.07, all students will pass the quiz, completely ignoring the test results. Alternatively, we can make more intuitive use of the test question and pass only the students who answered Q3 correctly. This is equivalent to comparing Pr(C=+ | Q3) against a new threshold of T = 0.15. Using this new threshold, we will now obtain the same student assessment on five test outcomes, 1 whose probabilities add up to 75%. This is the expected classification agreement (ECA). In particular, we say that the two classifiers α = (C, {Q1, Q2, Q3}, 0.07) and β = (C, {Q3}, 0.15) have an ECA of 75%.

2.2 Formalization

We now formalize the notion of ECA and classifier trimming.

Definition 1 Let α = (C,F, T) be a Bayesian classifier using distribution Pr(.). The classifier β = (C,F′ , T ′ ) is a trimming of α if it uses the same class variable C and distribution Pr(.) as α, and a subset of its features (i.e., F′ ⊂ F).

Definition 2 Let α = (C, F, T ) be a Bayesian classifier and let β = (C,F′ , T ′ ) be one of its trimmings. The expected classification agreement (ECA) between these classifiers is:

Here, f ′ is the subset of instantiation f pertaining to variables in F′ , and [.] is an indicator function (evaluates to 1 when its argument is true and to 0 otherwise).

Section 1 asks to compare trimmings of classifier α in Figure 1. The first trimming has ECA(α, (C, {Q1, Q3}, 0.10)) = 91% while the second has ECA(α, (C, {Q2, Q3}, 0.30)) = 68%.

We are now ready to define the classifier trimming problem more formally. The input to this problem is a binary Bayesian classifier α = (C, F, T ), a positive cost for each feature in F, and a budget B. The output is a subset of features F⋆ ⊆ F whose sum of costs is at most B and a threshold T ⋆ , leading to a trimmed classifier β⋆ = (C, F⋆ , T ⋆ ) that maximizes the ECA with α:

In other words, we wish to find a solution to the following optimization problem:

This problem can alternatively be described as feature subset selection using the following criterion.

Algorithm 1 ECA-TRIM(I, E, b)

Input:

α : Bayesian classifier (C,F, T); B : budget

Data:

I ← ∅, E ← ∅: set of included/excluded features b ←B: remaining budget

F⋆ ,M ⋆ , T ⋆ : optimal subset, MAA value, and threshold

Output: Optimal trimmed classifier β⋆ = (C, F⋆ , T ⋆ )

• 1: if b ≥ 0 then
• 2: (m, Tm) ← MAA(I)
• 3: if m > M ⋆ then M ⋆ ← m; F⋆ ← I; T ⋆ ← Tm
• 4: if minF∈F\(I∪E) cost(F) ≤ b then
• 5: m←UB(F \ E)
• 6: if m ≤ M ⋆ then return
• 7: F ←a feature fromF \ (I ∪E)
• 8: ECA-TRIM(I ∪ {F},E, b - cost(F))
• 9: ECA-TRIM(I,E∪ {F}, b)

Definition 3 Let α = (C, F, T ) be a Bayesian classifier. The maximum achievable agreement (MAA) for feature subset F′ ⊆ F is defined as:

The MAAα(F′ ) corresponds to the maximum ECA that is achievable by a trimmed classifier with features F′ . Hence, the classifier trimming problem reduces to searching for the subset of features that fits within the budget and maximizes the MAA. We will drop the subscript α when clear from context.

3 Searching for an Optimal Trimming

In this section, we describe our approach to search for an optimal trimming of Bayesian classifiers, or equivalently, selecting a feature subset with optimal MAA. 2 Our approach is based on a branch-and-bound search algorithm similar to Narendra and Fukunaga [1977] and Kolesar [1967]. As shown in Algorithm 1, we run a depth-first search through a binary tree where each node is branched into two nodes: one that includes and one that excludes a feature. Each node then represents the set of features that are included by the path from the root to that node. The algorithm computes the MAA at each node if the represented feature subset fits within the budget, keeping track of the best subset and its MAA at each point in search, as in Lines 1-3. In particular, this means that we compute the MAA even if the subset does not exhaust the budget, because MAA does not necessarily increase as the subset size grows.

2 Code available at https://github.com/UCLA-StarAI/TrimBN.

The essence of the algorithm is pruning subtrees without affecting the optimality of the solution. That is, the algorithm finds the optimal solution without generating the full binary tree. Suppose given any node, we know the largest value of MAA that its descendants can achieve (UB). Then we can safely prune the subtree rooted at that node if the bound does not exceed the current best score. This correspond to backtracking the search, as shown in Line 6 in Algorithm 1. Formally, let E be the set of features that were excluded by the path to a certain node. Each descendant node will then represent a subset of F \ E. Hence, if we can compute an upper bound on MAA for all subsets of F \ E, then we can successfully prune intermediate nodes in the search tree.

Figure 2 illustrates an example search execution. The tree is traversed depth-first, from left to right. If a node represents a feature subset within budget, its MAA is computed, and the score M ⋆ is updated accordingly. Otherwise, the upper bound is computed and compared against the current best value. For example, we backtrack the search after excluding F1, because the upper bound on MAA for subsets of {F2, F3, F4} is 0.95 which is smaller than the current M ⋆ = 0.97. Note that this particular subset has a cost of 4.0 and does not fit within the budget, but we still compute the bound on it for pruning. That is, the algorithm computes the upper bound on MAA of the set F \ E and it subsets, even if their cost may exceed the budget. We will later show experimentally that the pruning of subtrees makes these extra computations worthwhile.

4 MaximumPotential Agreement

We now introduce an upper bound for the MAA and show how it can be used in the search for an optimal trimming.

Definition 4 Consider a Bayesian classifier α = (C, F, T ) . Let F′ ⊆ F be a subset of its features, and let R = F \ F′ . The maximum potential agreement (MPA) is

Intuitively, the MPA is the expected agreement between a Bayesian classifier α and a hypothetical classifier γ that classifies an instance f ′ into the class that is more likely after observing the remaining features in R. Note that such classifier γ is not a Bayesian classifier as it does not test the posterior Pr(c | f ′ ) against a threshold. However, the MPA is still a useful computational tool due to its relationship to the MAA.

Proposition 1 The MPA is an upper bound on the MAA: MAAα(F′ ) ≤ MPAα(F′ ).

In addition, the MPA is monotonically increasing, a property that we utilize later in the proposed algorithms.

These two propositions together imply that the MPA of F′ also upper-bounds the MAA of all subsets of F′ .

Therefore, we can use the MPA as an upper bound on the MAA of a node's descendants in the branch-and-bound search algorithm for optimal trimming.

Lastly, we provide an observation that leads to a computational gain, especially in the case of naive Bayes models.

Proposition 3 If features F′ andF\F′ are independent given the class C, then MAAα(F′ ) = MPAα(F′ ).

The above property is useful because it is generally easier to compute MPA(F′ ) than MAA(F′ ), as we can maximize each instantiation f ′ separately. Moreover, in naive Bayes models, the quantity MAA that we wish to optimize is now monotonic. Thus, we need to compute this quantity only for those subsets that exhaust the budget, instead of every subset that fits within budget. Detailed proofs of above propositions can be found in the appendix.

5 Probabilistic Reasoning Algorithms

In this section, we first introduce the notion of same-decision probability and formalize its connection to the ECA. We then describe our proposed algorithms to compute the MPA and the MAA that exploit this connection.

5.1 Same-Decision Probability and ECA

Suppose we make a decision based on whether Pr(c | e) ≥ T , where e is the evidence collected thus far. We may ask whether to collect more evidence or to commit to the current decision. The same-decision probability (SDP) was introduced as a solution to this stopping problem [Choi et al., 2012]. It measures how likely we are to keep our current decision even after observing more variables X, and is defined as follows.

Definition 5 Consider a Bayesian classifier (C, F, T ) where F includes disjoint sets of features E and X. The samedecision probability (SDP) for X given e is defined as

A high SDP encourages one to stop collecting information and commit to the current decision, while a low SDP suggests otherwise. In the latter case, SDP also provides a solution to deciding which observations to collect next. In particular, observing a subset of variables Y in X that maximizes the expected SDP (E-SDP) will lead to the most robust decision in expectation. Hence, such subset maximally eliminates the need for further observations. This is formalized as follows.

Definition 6 Consider a Bayesian classifier (C, F, T ) where F includes disjoint sets of features E, Y and Z. The expected same-decision probability for Z given Y and e is defined as

While the ECA and E-SDP are conceptually different notions motivated by different considerations, they are quite similar computationally as they are both expectations. The ECA is equivalent to a variant of E-SDP (denoted SDPC,T,T ′ ) that uses two thresholds instead of one, by replacing the indicator term in Equation 1 with [CT (yze) = CT ′ (ye)].

Proposition 4 Let α = (C,F, T) be a Bayesian classifier and let β = (C, F′ , T ′ ) be one of its trimmings. We then have

where the expected SDP is computed w.r.t. classifier α.

Therefore, one can utilize an E-SDP algorithm to compute ECA during classifier trimming. For example, the E-SDP algorithm by Choi et al. [2017] can be modified to evaluate the above variant of E-SDP without extra computational overhead.

5.2 Computing the MPA

We now describe how we compute the MPA at each search step. First, the MPA can be expressed as follows:

Here, SDPC,T,0(R|f ′ ) is the expected probability that we will decide positive class if we observe features R given f ′ . Then 1 - SDPC,T,0(R|f ′ ) is its complement: the expected probability of negative classification. Exploiting this connection to SDP, our algorithm makes heavy use of the E-SDP algorithm by Choi et al. [2017], of which we provide a high-level description here and refer to the original paper for details. The algorithm is based on compiling a Bayesian network into a tractable circuit representation, called a Sentential Decision Diagram (SDD) [Darwiche, 2011]. Even though compiling the circuit is computationally heavy in general, computing the ESDP and hence the MPA is efficient once we have successfully compiled the circuit. Moreover, we can sometimes efficiently compile certain networks (e.g. high treewidth) in which traditional inference techniques become infeasible [Choi et al., 2013]. As a part of the process to compute SDPC,T (R | F′ ), the E-SDP algorithm calculates and saves the values Pr(f ′ ) and SDPC,T,0(R | f ′ ) for each f ′ . Given these values, computing the MPA for F′ is a straightforward evaluation of Equation 2.

With the ability to compute the MPA, we can now search for optimal trimmings of naive Bayes classifiers. The condition in Proposition 3 holds for all feature subsets of a naive Bayes model, and thus the MAA of a subset is always equal to its MPA. An optimal trimming is then found as shown in Algorithm 1 where both the upper bound and value of MAA are computed using the MPA algorithm described before.

1: Sort instances f ′ i in nondecreasing order of CPR(i) 2: m← ∑i POS(i) · MAR(i); m⋆ ←m 3: t⋆ ← [0, CPR(1)] 4: for i in 1, 2, . . . do 5: m←m-MAR(i) · (2POS(i) -1) 6: if m>m⋆ then 7: m⋆ ←m; t⋆ ← (CPR(i), CPR(i +1)] 8: returnMAA(F′ ) =m⋆ and any T ′ ∈ t⋆

5.3 Computing the MAA

Searching for an optimal trimming of arbitrary Bayesian network classifiers requires the computation of MAA, which involves tuning the trimmed classifier's threshold to maximize the ECA. First, we utilize the observation that a change in threshold affects the value of ECA only if the class probability given some instance lies on a different side of the threshold after the change. For example, recall the trimmed classifier using only Q3 from the quiz example in Section 2. We showed that a threshold of 0.15 will result in passing only the students who answered Q3 correctly. In fact, any threshold between Pr(C = +|Q3 = -) = 0.08 and Pr(C = +|Q3 = +) = 0.18 results in the same behavior and hence the same ECA. Therefore, the number of threshold values we need to consider is finite and in fact linear in the number of possible instances f ′ .

To compute the MAA using this observation, we first express the ECA as the following:

Then we can compute the ECA for any given threshold T ′ if we have the values of Pr(c | f ′ ), Pr(f ′ ), and SDPC,T,0(R | f ′ ) for each instance f ′ , which we can indeed easily obtain from an execution of the E-SDP algorithm for SDPC,T (R | F′ ).

Algorithm 2 shows the pseudocode to compute the MAA and the optimal threshold given these values from the E-SDP algorithm as inputs. Starting from T ′ = 0, the threshold is repeatedly incremented to just above the next lowest class probability given some feature instance f ′ . With each threshold change, the ECA value is also updated by subtracting the expected probability of positive classification given that instance and adding the complement of it, weighted by the marginal probability of that instance, as in Line 5. In other words, that instance f ′ is moved from the first sum to the second in Equation 3. At the end, the highest value of ECA and its corresponding threshold is reported.

Figure 3: A Bayes net over features {F1, F2, F3} and class C.

	C F3	Pr(F1 =+) 0.9	Pr(C =+) 0.6
C	F1 F2 F1 Pr(F2=+|CF1)	C F2	Pr(F3=+|CF2)
+	+ 0.6	+ +	0.4
+	- 1.0	+ -	1.0
-	+ 0.4	- +	1.0
-	- 0.5	- -	0.4

Table 4 offers a visualization of the algorithm. Here, we wish to compute MAA({F1, F2}) with respect to the Bayesian network classifier α = (C, {F1, F2, F3}, 0.55) in Figure 3. Each table row corresponds to a feature instance, sorted by the class probability. We consider five different cutoff points, and the ECA value at each cutoff point is the sum of expected probability of positive class for instances above the line and the expected probability of negative class below the line. In this case, MAA({F1, F2}) = 0.56 with the optimal threshold T ⋆ ∈ (0, 0.50], indicated by a dotted line in the table.

5.4 Complexity

Our proposed MPA and MAA algorithms, as described so far, appear to consider all possible feature instances, which is exponential in the size of the feature subset. Nevertheless, this can be improved by exploiting context-specific independence, a property having to do with the parameters of the classifier's probability distribution [Boutilier et al., 1996]. In particular, suppose given a context g (where G ⊆ F′ ), the remaining features F′ \G become independent of the class variable. Then in our MPA and MAA calculations, we only need to consider the context g instead of individually considering all instances of F′ that share this partial instantiation. The E-SDP algorithm by Choi et al. [2017] that we utilize is based on SDD compilation, which exploits some context-specific independence to simplify the circuit. 3 However, this is currently limited to certain cases, such as when some features have uniform parameters given a context, and does not exploit all simplification opportunities described above. Hence, compilation that fully exploits context-specific independence is an interesting future direction to further improve the efficiency of our algorithms.

3 We refer to Chavira and Darwiche [2008] and Choi et al. [2013] for more details on this simplification.

• (a) ECA and average accuracy for pima
• (c) Test agreement and accuracy

Figure 5: (a),(b) ECA and average accuracy achieved by feasible feature subsets. (c) evaluation of subsets with highest ECA and accuracy.

6 Experimental Evaluation

We now empirically evaluate our proposed algorithms on several naive Bayes and general Bayesian network benchmarks.

6.1 Accuracy vs. Agreement

We evaluate our method on real-world datasets from the UCI repository [Bache and Lichman, 2013], BFC 4 , and CRESST 5 . We randomly split each dataset into 80/20 train and test sets and learn a naive Bayes classifier using the training set. With the budget set as half the number of features and threshold as 0.5, we compute the ECA of each feasible feature subset. In addition, we compute the average classification accuracy of each feature subset using 10-fold cross validation on the training set.

Figure 5 shows the ECA and average accuracy achieved by each feasible subset, and the subsets with highest ECA and highest accuracy are highlighted. We can see that optimizing the ECA tends towards higher accuracy. More interestingly, we can observe a Pareto frontier where one cannot increase the ECA without sacrificing average accuracy, and vice versa. This suggests that one may need to make a tradeoff between classifier agreement (i.e., robustness) and accuracy when selecting features. Moreover, we evaluate the subsets with highest ECA and accuracy on the test set and report their empirical classification agreement and accuracy in Figure 5c. The subset chosen for optimal ECA on the training set also achieves high classification agreement on the test set. Surprisingly, on network heart, it also achieves higher test accuracy than the subset with the highest average cross-validation accuracy on the training set. A possible explanation is that choosing subsets based on their cross-validation classification accuracy does not generalize well to the test set. It may introduce additional overfitting that ECA does not suffer from: if the original model generalizes well, we also expect our trimmed classifier to generalize well. We also evaluated accuracy and agreement of feature selection by information gain, but it neither outperformed optimizing the ECA nor the average cross-validation accuracy. In addition, our method achieves higher accuracy on most splits of the heart data, which suggests that this may be a property of the dataset. In particular, the average crossvalidation accuracy of the original full classifier for pima was approximately 0.720, which was lower than the average accuracy of about 21% of the candidate subsets. As our method optimizes for agreement with this original classifier, which has relatively low accuracy, the resulting trimming may have lower accuracy than if we were to actively optimize for average accuracy. On the other hand, the original classifier for heart had average accuracy 0.866, which was lower than only 2% of the candidate subsets. Hence, in this case, optimizing the ECA to closely mimic the original classifier's behavior also results in relatively high classification accuracy.

4 http://www.berkeleyfreeclinic.org/

5 http://www.cse.ucla.edu/

6.2 Runtime

We also compare the efficiency of our algorithm against FSSDD, which is the feature selection algorithm based on ESDP [Choi et al., 2017]. Each naive Bayes classifier was trimmed with the budget set to 1/3 the number of features, each feature given unit cost, and classification thresholds in {0.1, 0.2, . . . , 0.9}. Table 6 shows the average running times in seconds and the number of times each algorithm computes the criterion value. The performance of our method is comparable to that of FS-SDD on smaller classifiers, and more efficient for larger ones. In particular, our algorithm could handle the largest network with around 4000 ECA computations, whereas an exhaustive search method by FS-SDD requires a significantly greater number of computations and could not be run to completion. Moreover, in 16% of experiment instances described above, the trimmed classifier with optimized threshold reported higher classification similarity (measured by the ECA) than the classifier using features selected by FSSDD, which keeps the threshold fixed. Note that our method optimizes the threshold of the trimmed classifier and thus is theoretically guaranteed to achieve classification similarity (measured by the ECA) no lower than feature selection using E-SDP. Hence, threshold optimization allows us to find more robust trimmings more efficiently. We also show the total number of subsets within budget, ( nm), to illustrate that branch-and-bound algorithms tend to require fewer number of evaluations than exhaustive search as the number of features increase. This justifies the extra MPA calculations done for pruning on subsets larger than the budget.

6.3 Trimming General Networks

Next, we evaluate the quality of trimmed classifiers on general Bayesian networks from the UAI 2008 evaluation and a tree-augmented naive Bayes model for mammography reports [Gimenez et al., 2014]. We run our method with T in {0.1, 0.2, . . . , 0.9} and the budget set to 1/3 the number of features. For the UAI networks, we randomly chose a root node to be the class variable and used the set of all leaf nodes as the feature set F. Each setting was repeated for three randomly selected class variables. For the mammography network, we used the (root) decision node as the class variable and chose 17 out of the 20 variables to be the feature set. Training data was not available for these networks, so we compare against feature selection by information gain instead of classification accuracy. Figure 7 highlights the results. The trimmed classifier by our algorithm consistently achieves higher expected classification agreement, demonstrating that robustness is not easily achieved by other feature selection methods. We also want to stress that the features selected using information gain differ for different class variables, but stay the same across different initial threshold values. On the other hand, our algorithm is sensitive to the original threshold, and thus results in trimmed classifiers with similar behavior as the original classifier with a particular threshold.

7 Conclusion

This paper developed a novel operator on Bayesian classifiers: to trim the set of features to fit within a budget, while simultaneously adjusting the classification threshold. Our objective was to optimize the expected classification agreement between the original classifier and its trimmed counterpart. By analyzing the properties of classifier agreement and its maximum potential agreement, we developed a branch-and-bound search algorithm to find optimal trimmings. Experiments on naive and general Bayesian networks demonstrated the effectiveness of our approach in finding robust trimmings of classifiers, especially compared to optimizing more traditional objectives such as expected SDP and information gain.

Acknowledgments

The authors wish to thank Adnan Darwiche for his contributions to an earlier version of this work, and Arthur Choi for helpful advice and discussions. This work is partially supported by NSF grants #IIS-1657613, #IIS-1633857 and DARPA XAI grant #N66001-17-2-4032.