AI summaryⓘ
The authors address a problem with Naive Bayes classifiers where traditional smoothing methods apply a fixed strength that doesn't adapt to details like feature variety or class imbalance, leading to bias especially in complex data. They propose a new approach called hierarchical empirical-Bayes Naive Bayes (HEB-NB), which learns smoothing levels from the data itself, improving how the model shares information across classes while keeping computations efficient. They also extend this adaptive smoothing to a relaxed model called HEB-AODE. Their theory shows that this method achieves better error bounds than traditional Laplace smoothing. Experiments on many datasets confirm that their method improves prediction accuracy and confidence calibration compared to standard techniques.
Naive BayesSmoothingDirichlet priorEmpirical BayesType-II maximum likelihoodHigh-cardinality dataAODE (Average One-Dependence Estimators)Error boundsExpected calibration errorLog-loss
Authors
Nguyen Thai Anh, Truong Viet Vu, Tran Thien Thanh, Vo Nguyen Quoc Bao, Ngo Hoang Tu
Abstract
The Naive Bayes (NB) classifier remains a standard choice for categorical data, yet its widely used smoothing rules, such as Laplace, Lidstone, Krichevsky-Trofimov, and the $m$-estimate, all prescribe a fixed smoothing strength that ignores feature cardinality, sample size, and class imbalance, inducing a non-vanishing bias on modern high-cardinality tabular data. We propose hierarchical empirical-Bayes Naive Bayes (HEB-NB), in which each class-feature conditional probability is smoothed by a Dirichlet prior whose concentration is learned data-adaptively via Type-II maximum likelihood, enabling principled information sharing across classes while retaining closed-form inference. We further introduce HEB average one-dependence estimators (HEB-AODE), showing that the adaptive smoothing transfers cleanly to structural relaxations of NB. Theoretically, we establish a non-asymptotic $\ell_1$ error bound for HEB-NB matching the empirical-distribution minimax rate plus a vanishing data-adaptive bias, together with a matching Laplace-tight lower bound that yields a finite-sample, risk-level strict separation from Laplace. We further derive a plug-in excess Bayes-risk bound via total-variation tensorization and a population top-1 expected calibration error (ECE) corollary. Empirically, across 31 UCI and OpenML benchmarks, HEB-NB attains the best average Friedman rank on probabilistic metrics, with up to 22.1% log-loss reductions on high-cardinality datasets and consistent improvements of HEB-AODE over vanilla AODE. Combining HEB-NB with mutual-information weighting reduces top-1 ECE by 41%-70%, demonstrating substantial gains in probabilistic accuracy and calibration.