Dynamic Early Stopping for Naive Bayes

Aäron Verachtert, Hendrik Blockeel, Jesse Davis

Abstract

This paper introduces a dynamic early stopping approach for Naive Bayes classifiers, enabling models to terminate feature inspection once a confidence threshold is met. By incorporating learned "stop points," the proposed method achieves up to a 5x speedup and significant energy savings on mobile hardware with minimal impact on predictive accuracy.

Introduction

As machine learning transitions to battery-constrained mobile devices and sensors, energy efficiency is paramount. Standard Naive Bayes (NB) classifiers typically inspect every feature of an input, which can be redundant for many instances. While static feature selection reduces the workload, it applies a uniform constraint regardless of instance difficulty. We propose a dynamic method that decides on-the-fly when sufficient information has been gathered to make a prediction.

Methodology

The core innovation is the addition of stop points to the traditional Naive Bayes model. A stop point $(k, u, l)$ consists of a feature index $k$ and thresholds $u$ (upper) and $l$ (lower) for the accumulated log-probability score.

During inference, the algorithm iterates through features and checks these thresholds. If the score exceeds $u$, the positive class is predicted; if it falls below $l$, the negative class is predicted. Stop points are learned using a validation set, ensuring they are triggered by a significant portion of instances (Support Criterion) and do not degrade performance beyond a safety margin (Accuracy Criterion).

Experimental Results

The approach was evaluated on seven high-dimensional datasets, including text classification (RCV1-v2) and drug discovery (Thrombin).

Speedup and Accuracy

The dynamic model demonstrated substantial performance gains. Across various experimental settings, speedup factors reached as high as 5.27x. Crucially, this efficiency did not come at the cost of performance; the difference in weighted accuracy was typically less than 1%, and in some cases, accuracy improved by avoiding noisy features.

Figure 4: Speedup factors (top) and weighted accuracy (bottom) across different budgets. The dynamic approach achieves up to 5x speedup while maintaining high accuracy levels.

Energy Efficiency

Energy consumption is a critical metric for mobile deployment. When tested on a Raspberry Pi, the dynamic approach reduced energy consumption per prediction by over 80% on the IMDb dataset compared to standard static approaches. The computational overhead of the threshold checks is minimal, ensuring that the time saved by skipping features translates directly into energy savings.

Figure 2: Energy savings factor relative to feature budget. The dynamic stopping methods consistently provide higher efficiency than baseline models.

Discussion and Conclusion

Dynamic early stopping offers a computationally lightweight solution for enhancing the efficiency of Naive Bayes. Unlike more complex dynamic methods, the simple threshold checks used here do not introduce significant overhead. Future research will focus on extending this framework to multi-class classification and accounting for varying feature acquisition costs.

Summary updated

Abstract

Energy efficiency is a concern for any software running on mobile devices. As such software employs machine-learned models to make predictions, this motivates research on efficiently executable models. In this paper, we propose a variant of the widely used Naive Bayes (NB) learner that yields a more efficient predictive model. In contrast to standard NB, where the learned model inspects all features to come to a decision, or NB with feature selection, where the model uses a fixed subset of the features, our model dynamically determines, on a case-by-case basis, when to stop inspecting features. We show that our approach is often much more efficient than the current state of the art, without loss of accuracy.
BibTeX
@inproceedings{verachtert2016dynamic,
  author = {Aäron Verachtert and Hendrik Blockeel and Jesse Davis},
  title = {{Dynamic Early Stopping for Naive Bayes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure