Dynamic Early Stopping for Naive Bayes

1 Introduction

Portable battery-powered devices such as tablets, smartphones, cameras, and intelligent sensors are ubiquitous in our world. With this comes an increasing need to deploy machine-learned models on such systems (see, e.g., [Badami et al., 2016]). However, these devices have constraints on their resources such as battery life, CPU power, memory and disk space. In particular, the CPU time needed to make a prediction with such models directly affects the energyefficiency of the device, and hence its autonomy. For this reason, studying how to design models that make predictions more efficiently has begun to attract attention [Seldin et al., 2013; Herbrich et al., 2015].

In this paper, we study this question for Naive Bayes. NB is a widely used learning method, in part because the learning phase is efficient and the learned model is often very accurate. However, in the prediction phase, NB can be relatively inefficient, as it inspects all features of the query instance before making a decision. This can be alleviated by performing feature selection: during training, a static subset of the features is selected such that the model based on this subset performs as well as a model based on all features.

We propose a novel model format and learner. Our model format incorporates certain "stopping conditions" into the basic NB model in order to determine dynamically, for each individual query instance, when to stop inspecting more features. This "dynamic stopping" approach can be combined with standard feature selection.

The basic idea is the following. As the NB model iterates over the features, it updates a score for each class; the class that scores highest in the end will be the one predicted. In some cases, one class may be so far ahead of the others that it seems unlikely that any other class will catch up. At that point, we can stop and predict the class that is currently ahead. Such an approach requires a very efficient stopping criterion, otherwise the computational effort of evaluating the criterion may outweigh the gain of not having to evaluate more features. We propose algorithms for determining when and where to include the stopping conditions and how to perform prediction with these models. Empirically, we find that this approach yields substantial efficiency gains compared to both static feature selection and several other baselines without loss of predictive performance.

2 Naive Bayes

Assume we want to learn a classifier that predicts the class Y from input variables X1↪ ▷ ▷ ▷ ↪Xm. For ease of explanation, we assume nominal variables, and we systematically use y and xi to denote a particular value from the domain of Y and Xi. The Naive Bayes classifier predicts the class y that maximizes p(y) Qmi=1 p(xi♣y). This prediction is Bayes-optimal if the Xi are conditionally independent given the class; if not, the classifier still works well in practice [Domingos and Pazzani, 1997].

Learning the Naive Bayes classifier is as simple as estimating p(y) and p(xi♣y) for all values of i, xi and y, and storing these estimates in a table. The estimates are usually based on frequency counts with Laplace smoothing. In practice, implementations often compute a sum of logs instead of this product, to avoid numerical underflow. That is, with l(·) = log ˆ p(·) and ˆ p(·) the estimate of p(·), practical implementations store the l values in a table during learning, and for prediction return argmaxy l(y) + Pmi=1 l(xi♣y).

For binary prediction, where Y can only have values 0 or 1, one can equivalently store for each value of each attribute the difference d(xi) = l(xi♣1)-l(xi♣0) and predict class 1 if and only if l(1)- l(0)+ Pmi d(xi) > 0. In this case, it is known that 0 is not always the optimal threshold, and it may be better to treat this threshold as a tunable parameter t [Thai-Nghe et al., 2010]. The decision criterion then becomes: predict class 1 if and only if

From here on, we focus on this implementation of Naive Bayes.

One way to speed up Naive Bayes is to not include all m attributes in the model, but only the k most informative ones. These can be chosen using standard feature selection methods, which typically use some function to score attributes according to expected informativeness and then select the k highest-scoring ones.

Another way to speed up Naive Bayes is to stop inspecting attributes as soon as it is clear that the outcome can no longer change. For the positive class, this occurs if the accumulated sum through attribute i is so far above t that it is impossible for the remaining attributes to bring it down to below t; that is

In other words, even if all the unobserved values maximally favor the negative class (d(xi) is maximally negative), the end result cannot be lower than t. A similar rule holds for the negative class when the accumulated sum is too far below t.

While this criterion is safe (stopping never gives a different outcome from continuing), it is unlikely to bring any efficiency gain. The stopping condition assumes a worst-case scenario for the unseen attributes. In the (unrealistic) bestcase scenario where the first attributes maximally favor class 1, one still expects the condition to be fulfilled only when i is approximately m◁2. In practice, i will be much closer to m. Thus, the typical savings would be less than half of the iterations, while the stopping condition makes each iteration more than twice as expensive.

3 RelatedWork

The same-decision probability is a measure to evaluate the probability that a prediction using only a subset of the available attributes will change after evaluating the remaining attributes [Choi et al., 2012]. For Naive Bayes, this probability can either be approximated or computed exactly [Chen et al., 2014]. By ordering the attributes by informativeness, the assumptions of the approximation techniques are violated which could adversely affect the same-decision probability estimate. In the worst case, computing an exact estimate is exponential in the number of remaining attributes. In contrast, our approach can be viewed as a simple heuristic that gains efficiency and seems to work well in practice but does not offer guarantees.

Another area of related work is cost-sensitive learning (e.g., [Elkan, 2001; Chai et al., 2004; Xu et al., 2013; 2014]). Typically, these approaches focus on whether the cost associated with acquiring an attribute value outweighs the expected improvement in performance. Our problem can be translated into a cost-sensitive setting by defining the cost of each attribute as the CPU time needed to incorporate its value into the prediction. Chai et al. (2004) focus on costs associated with acquiring and using attribute values at test time. Their dynamic strategy for selecting which attributes to acquire is computationally expensive as it evaluates at test time what the benefit of each unobserved feature would be. A more recent cost-sensitive approach is model cascades, which uses a sequence of progressively more expensive models to classify an example. The process stops once there is sufficient confidence in the prediction [Xu et al., 2013; 2014].

Both the same-decision probability and cost-sensitive Naive Bayes can be used to dynamically stop prediction. However, they both rely on performing calculations at prediction time to decide when to stop evaluating extra attributes, which could be computationally demanding. We propose a more efficient method in the next section.

4 Dynamic Early Stopping during Naive Bayes Prediction

In standard Naive Bayes, the learned model is a table that contains the d(·) values. Prediction with this model involves iterating over all included attributes, and updating a score for each class after observing the value of each attribute. The final prediction is made only after considering all attributes. In contrast, our proposed approach dynamically decides at test time how many attributes to consider when classifying each example.

4.1 Predicting with Stop Points

Algorithm 1 Prediction with Stop Points

Input:

d: table with log-coefficients of the NB model; S: list of stop points (k↪ u↪ l); t: decision threshold; x = (x1↪ ▷ ▷ ▷ ↪ xm): instance to be classified Output: prediction for x ∆ = d[0↪ 0] start = 1 for all (k↪ u↪ l) in S, from low to high k, do ∆ = ∆ + Pki=start d[i↪ xi] if ∆ > u then return 1 else if ∆ < l then return 0 start = k + 1 ∆ = ∆ + Pmi=start d[i↪ xi] if ∆ > t then return 1 else return 0

The key idea behind our approach is that instead of iterating over all features, the prediction can stop after the kth feature, if a certain stopping condition is fulfilled. To achieve this, we extend the Naive Bayes model with a list of stop points. Formally, a stop point is a tuple (k↪ u↪ l) where k is an attribute index, and u and l are upper and lower thresholds on an example's predicted probability of being positive after observing the first k attributes.

When making a prediction in a model with stop points, inference iterates over the attributes until it reaches a stop point. Then if p(y = 1♣x1↪ ▷ ▷ ▷ ↪ xk) > u or p(y = 1♣x1↪ ▷ ▷ ▷ ↪ xk) < l, inference is stopped and the current prediction is returned. Algorithm 1 shows pseudocode for prediction with this extended model. It assumes d[i↪ j] with i > 0 contains the d(·) value for value j of attribute i, and d[0↪ 0] contains l(1)-l(0) (see Equation 1); u and l here denote the bounds in log space.

4.2 Identifying Stop Points

Incorporating stop points into the model complicates the training algorithm. In addition to learning the table (like standard Naive Bayes), it also needs to learn the list of stop points (k↪ u↪ l). This entails deciding where to include stop points (k) and picking the stopping thresholds u and l for that position. As checking whether inference can be stopped includes a non-negligible computational cost, associating a stop point with each attribute would likely outweigh any potential efficiency gains. Therefore, we need to carefully consider whether it is worthwhile to add a stop point.

Our training algorithm will include a stop point (k↪ u↪ l) only if two criteria are fulfilled:

1. The support criterion: a sufficient proportion of the instances reaching that stop point is expected to fulfill the stopping condition, and
2. The accuracy criterion: the expected accuracy on these instances, if they are assigned the currently higherscoring class, is high enough.

Note that both criteria rely on expected values. These are estimated using a separate validation set.

In our implementation, the support criterion simply states that the estimated proportion of instances that fulfill the stopping condition (we call these "stopped instances") must be above a given threshold s, which is a parameter of the training algorithm.

The accuracy criterion is more complicated. The most intuitive criterion is the following (R1): For the stopped instances, the expected accuracy if they are assigned the currently highest-scoring class is at least as high as the expected accuracy if they would be assigned the highest-scoring class after seeing all features. In other words, early stopping does not hurt accuracy. We found this rule not to work well, apparently because it suffers from overfitting. This accounts for possible overestimation of the early-stopping accuracy. In addition, a second rule was added (R2): The expected accuracy on stopped instances should be p% higher than the full model's accuracy on all instances, where p is a parameter. This rule helps avoid that instances are stopped, not because their early-stopping accuracy is high, but because the accuracy of the full model happens to be low. Here, p is an additional countermeasure against overfitting. The accuracy criterion is the conjunction of R1 and R2.

The training algorithm determines stop points as follows. For each position k, it checks if a u and l can be found such that (k↪ u↪ l) meets both the support criterion and the accuracy criterion. The thresholds need to be set separately after each attribute because NB's probability estimates tend towards 0 or 1 as more attributes are observed. When multiple u and l are found, it chooses the lowest u and highest l, as this maximizes the proportion of instances that are stopped.

Algorithm 2 Training Naive Bayes with Stop Points

Input:

• T: training set

V : validation set

• M: ordering metric
• s: support parameter
• p: performance threshold

Output:

• d: Naive Bayes model
• S: list of stop points (k↪ u↪ l), where k is the position, u is the upper bound, and l is the lower bound
• t: decision threshold for instances that observe all attributes

Order X from most to least informative using M

d = TRAINNB(T ) // Train NB model with all attributes di = function mapping x to d's score for x after the first i attributes

V 0 = V // V 0 is the set of examples for which inference has not been stopped

// Find candidate bounds that meet the accuracy requirements

C = IDENTIFYCANDIDATETHRESHOLDS U = ¶v 2 C♣MEETSACCREQ(¶x 2 V 0 ♣di(x) > v♦)♦ L = ¶v 2 C♣MEETSACCREQ(¶x 2 V 0 ♣di(x) < v♦)♦ // Choose those that eliminate the most examples if U is empty then u = 1 else u = min(U) if L is empty then l = -1 else l = max(L) // If the support is high enough, insert stop point Out = ¶x 2 V 0 ♣di(x) > u _ di(x) < l♦ if ♣Out♣ ≥ s♣V 0 ♣ then add (i↪ u↪ l) to S V 0 = V 0 -Out t = PICKDECISIONTHRESHOLD(V 0 ) function MEETSACCREQ(S) return ACC(di↪ S) > (1 + p)ACC(dm↪ V ) & ACC(di↪ S) > ACC(dm↪ S)

Putting it all together Algorithm 2 provides pseudocode for the training algorithm. As input, it receives a training set T, a validation set V , an ordering metric M, a support threshold s, and an improvement threshold p. Using the training data T, a Naive Bayes classifier is trained using all the attributes. It statically orders the attributes according to M such that the most informative ones are evaluated first in an attempt to arrive at a decision as quickly as possible.

Next, the algorithm iterates over the attributes from most to least informative and considers introducing a stop point after each attribute k. It treats the predicted probability of each example in the validation data as a candidate upper (lower)

threshold 1 and identifies all thresholds such that classifying all examples in the validation data with a predicted probability above (below) the threshold as positive (negative) satisfies the two accuracy conditions. Of the thresholds that meet the accuracy requirements, it then picks the upper and lower thresholds that apply to the largest number of examples. If the two thresholds apply to at least s♣V ♣ examples in aggregate, a stop point (k↪ u↪ l) is added. After adding a stop point, all stopped examples are removed from the validation data.

5 Experimental Evaluation

The goal of our empirical evaluation is to answer the following questions:

1. For a fixed attribute budget k, how does the dynamic approach compare to the static one in terms of efficiency and accuracy?
2. How does our proposed approach compare to samedecision probability (SDP) [Choi et al., 2012] and costsensitive Naive Bayes (csNB) [Chai et al., 2004]? These represent two other ways to dynamically make a prediction based on only a subset of the attributes.

To answer the first question, we train two types of models for each attribute ordering. The baseline is a "static" model that always uses k attributes to make a prediction. Then we learn a dynamic model according to our proposed approach that can consider at most k attributes at prediction time. To explore a range of different operating conditions, we investigate various values of k.

5.1 Data Sets

We perform an evaluation using seven data sets from various domains, summarized in Table 1. Each data set has at least 1000 attributes. We treat each task as a binary classification problem and we discretize numerical features by computing the mean and standard deviation for each of these features on the training data. We construct four bins. The first bin contains 0, as most data sets are very sparse. The three remaining bins are: (-1↪ (θ - σ)]↪ ((θ - σ)↪ (θ + σ)]↪ and ((θ + σ)↪ +1).

1 This is analogous to the standard approach to discretizing a continuous feature in decision tree learning or building an ROC curve.

5.2 Methodology

This section discusses the methodology of our empirical evaluation. First, we discuss the experimental setup, and then we explain which evaluation metrics we use.

Experimental Details

We consider the following values for the budget k: 5, 10, 25, 50, 100, 200, 500, 1000. For our approach, we set p = 0▷05 and s = 0▷05 and did not try other values. For attribute orderings, we consider a greedy, hill-climbing wrapper-based feature selection method (Greedy) [Kohavi and John, 1997]; FCBF [Yu and Liu, 2003], a correlation-based feature selection method; information gain (IG) and chi square (Chi), which are standard filter-based feature selection criteria; and a novel metric tailored to Naive Bayes that estimates the difference in conditional probabilities (∆CP), which is defined as:

Intuitively, this is a weighted average of how discriminative a particular attribute is, given that Naive Bayes uses the conditional probabilities to build up its "confidence" in a given prediction.

Each data set is split into a training set, a validation set and a test set. As RCV1-v2 is usually treated as a temporal data set, we use the standard chronological split [Lewis et al., 2004], where the training set consists of the first 23,149 instances, the validation set consists of the next 23,149 instances, and the test set consists of the remaining instances. For the other data sets, we randomly select 40% of the examples for training, 20% for validation, and 40% for testing. We repeat this procedure ten times and report an average across all runs.

Evaluation Metrics

We want to measure two properties of the learned models: efficiency and predictive performance. For efficiency, we begin by using a Raspberry Pi system (Model B+, 512MB, with Power Bank battery pack supplying 5V at a maximum of 1A) running Raspbian and a Java Virtual Machine, and measure energy consumption using a Tenma digital multimeter 727730A. Energy consumption in kWh is calculated by multiplying the time it takes to make a prediction for all examples in the test set by the average electric current during prediction and the steady voltage of 5V.

Taking energy measurements with such a system is better than using a device like a smartphone, where it is harder to control which other applications are running. Due the constrained environment, this type of evaluation is very time consuming. It has been observed elsewhere [Verachtert et al., 2015] that CPU time correlates well with energy usage. After double-checking this claim, we therefore use CPU time for prediction as a proxy for energy usage.

Because several of our data sets have an imbalanced class distribution, simply reporting accuracy would lead to several cases where the majority classifier would achieve very good performance. Therefore, we use weighted accuracy as our metric, with a misclassification cost of 1 for a negative example and f(0)◁f(1) for a positive example, where f(y) is the frequency of class y in the validation set. We estimate the costs based on the class distribution in the validation data. The same weighted accuracy metric is used for the accuracy requirements in the training procedure. Note that using a ranking metric such as area under the ROC curve would be challenging for the dynamic approach as the number of attributes it considers depends on the example. Thus, the probability estimates may not be comparable across stop points.

5.3 Results and Discussion

Figure 1 shows the result of an experiment with the Raspberry Pi, using the IMDb.drama data set. The x-axis shows the budget, the y-axis the speedup factor (left) or relative energy efficiency (right) for the dynamic approach, relative to the static approach. This graph confirms two things: (a) on the Raspberry Pi, our approach can lead to significant energy savings; and (b) speedup is a good proxy for energy efficiency (the difference between these two is on average 0.03 in these data, with one outlier of 0.11 at budget 25). Because CPU time is much easier to measure, we henceforth focus on speedup factors, measured on desktops.

Figure 2 shows the speedup factor and the difference in weighted accuracy as a function of attribute budget for two representative data sets: YouTube and RCV1-v2. 2 For RCV1-v2, regardless of the ordering heuristic, the dynamic approach always results in faster prediction times than the static approach. In terms of accuracy, the curves for the static and dynamic approach for each ordering metric are largely overlapping, indicating that the runtime improvements come with no loss in predictive performance. For YouTube, the prediction times for the dynamic approach are slightly slower for small values of k, due to the extra cost associated with filtering out examples. However, for values of k > 25 the dynamic approach results in substantial savings in prediction time. Furthermore, these are the values of k that result in the best predictive performance. Again, we observe that using the dynamic approach results in nearly equivalent predictive performance as the static approach.

2 Full experimental results are available in the online supplement at http://dtai.cs.kuleuven.be/software/dsnb

Table 2 compares the static model with the attribute budget that maximizes the validation set weighted accuracy to the dynamic model with the same budget for each feature ranking method in terms of speedup factor (SF) and difference in weighted accuracy (∆wAcc). Across the 35 settings, the dynamic approach results in an improved runtime 34 times. Speedup factors vary from 0.97 to 5.27. For ∆wAcc, positive numbers indicate that the dynamic approach is better than the static one. The dynamic and static models tend to have similar weighted accuracy scores: sometimes one is better, sometimes the other, with the difference typically below 1%. In summary, the dynamic approach achieves substantial runtime gains without sacrificing predictive performance.

Our approach makes these energy improvements while also respecting the memory restrictions of a resource-constrained environment. Augmenting the model with the stop points requires storing one integer and two floating point numbers per stop point. In practice, this corresponds to an increased memory use (averaged over our data sets) of 15% for k = 10, 3% for k = 100 and 0.4% for k = 1000.

Finally, we compared our approach to csNB and SDP. These can also be used to make a decision whether to stop prediction, but require more calculations during the inference process. In our experiments, the computation time csNB needed to decide whether to make a prediction or see more attributes depended linearly on the number of remaining unobserved attributes, and was about 28 times that of simply incorporating all remaining attributes into the prediction. For SDP, we found that it is only faster than evaluating all remaining attributes when less than 10 attributes are left; with 20 attributes remaining, computing the SDP was more than 1000 times slower than simply evaluating the last 20 attributes. Consequently, neither of these approaches offers much of an improvement over static feature selection. In contrast, our approach results in substantial efficiency improvements. Essentially, the runtime cost csNB and SDP impose for dynamically deciding when to stop the prediction will only yield benefits when acquiring an attribute value is extremely expensive either in terms of energy (computation) or monetary cost.

6 Conclusion

As deploying machine-learned models becomes more prevalent on devices with constrained resources, it becomes important to reduce the CPU burden associated with making predictions. We tackled this problem for Naive Bayes by employing a dynamic strategy that stops the prediction process for test examples whose label is sufficiently certain. Empirically, we found that our dynamic approach can reduce the energy consumption per example by over 80% compared to a static approach, without significantly affecting accuracy. In the future, we would like to explore how to incorporate feature extraction costs into the model data sets, and measure the energy usage associated with predictions on a sensor.

Acknowledgments

A¨aron Verachtert and Hendrik Blockeel are partially supported by FWO-Vlaanderen (G.0179.10, G0682.11) and KU Leuven Research Fund (CREA/13/014, GOA/13/010). Jesse Davis is partially supported by the KU Leuven Research Fund (C22/15/015), and FWO-Vlaanderen (G.0356.12, SBO150033). We thank Jan Van Haaren, Wannes Meert, and the anonymous reviewers for their feedback.