Hierarchical Empirical-Bayes Naive Bayes: Minimax Smoothing and Calibration with AODE Extension

The paper proposes hierarchical empirical-Bayes Naive Bayes (HEB-NB), a smoothed categorical NB classifier 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. The authors also introduce HEB average one-dependence estimators (HEB-AODE), showing that the adaptive smoothing transfers cleanly to structural relaxations of NB."

The paper argues that standard smoothing rules—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. In high-cardinality regimes where K f ≳ N c, pseudo-counts dominate empirical counts, so that Laplace smoothing incurs a deterministic, non-vanishing bias whose order matches the sampling-variance scale and saturates at Θ(1) once K f exceeds N c.

The HEB-NB estimator models each class-conditional PMF as θ c,f ∼ Dirichlet(m c,f θ̄ f), with the concentration m c,f learned by Type-II ML (Minka fixed-point iteration). Two prior-mean variants are proposed: HEB-U (uniform prior mean) and HEB-M (pooled marginal prior mean). The paper shows that "Limit cases recover Laplace smoothing and the full-shrinkage endpoint of Micci-Barreca TE, so HEB-NB unifies both within a single hierarchical-Bayes family while preserving the time and memory complexity of categorical NB up to a constant factor."

Theoretically, the paper establishes:

• Theorem 1: A non-asymptotic l1 error bound for HEB-NB: E∥θ̂ HEB − p⋆∥1 ≤ √((K−1)/N) + ρ N ∥θ̄ − p⋆∥1, matching the empirical-distribution minimax rate plus a vanishing data-adaptive bias. For Laplace, the bound is √((K−1)/N) + 2(K−1)/(N+K).

• Lemma 1: A clamping-induced sanity bound on the shrinkage factor, ρ N ≤ m max/N, ensuring the bias vanishes asymptotically.

• Theorem 2: A matching Laplace-tight lower bound: sup p⋆∈Δ̄ K−1 E∥θ̂ Lap − p⋆∥1 ≥ 2(K−1)/(N+K), proving its bias is Laplace-tight at the simplex vertex.

• Corollary 1: A finite-sample, risk-level strict separation between HEB-NB and Laplace at the vertex prior p⋆ = e1, with the gap being strictly positive on N ≥ N0, K ≥ 2, θ̄1 ∈ (0, 1).

• Corollary 2: An excess Bayes-risk bound via joint total-variation tensorization, E[R(ĝ)] − R⋆ ≤ ∥π̂ − π∥1 + Σ f E y∼π̂ ∥p̂ y,f − p y,f∥1, which does not require any uniform lower bound on P(X).

• Theorem 3: A population top-1 expected calibration error (ECE) bound.

Empirically, the paper evaluates on 31 UCI and OpenML benchmarks. Key results:

• HEB-M attains the best mean Friedman rank on log-loss (r̄ = 2.26) and Brier (r̄ = 2.26) among seven smoothing methods.

• HEB-M significantly dominates 13 of 24 (HEB-M, baseline) × metric pairs under the Nemenyi protocol at α = 0.05.

• HEB-AODE significantly improves over vanilla AODE on F1, log-loss, and Brier (paired Wilcoxon p ≤ 0.029 on each).

• On high-cardinality benchmarks, HEB-AODE reduces log-loss by 9.7% on amazon-employee and 22.1% on click-prediction.

• Combining HEB-M with sqrt-mutual-information weighting (HEB-M+GR) cuts top-1 ECE by 41%–70% versus Laplace on the high-cardinality benchmarks.

The paper also reports that the per-fold overhead of HEB-M relative to Laplace is 2.3×, and that the unclamped Type-II ML maximiser empirically scales as √(N c log K f), with the upper clamp binding on only 4.9% of fitted pairs.

Improvements to AI Systems:

1. Adaptive smoothing for high-cardinality categorical features

Replace fixed smoothing (Laplace, Lidstone, m-estimate) in any Naive Bayes–style classifier with HEB-NB’s data-driven Dirichlet concentration. This eliminates the non-vanishing bias that plagues high-cardinality tabular data (e.g., user IDs, ZIP codes, rare SKUs), improving log-loss and Brier scores without manual tuning.

2. Hierarchical information sharing across classes

Use the pooled marginal prior mean (HEB-M) to share statistical strength among classes, especially for rare classes with few samples. This reduces overfitting in imbalanced classification tasks, yielding more reliable probability estimates for minority classes.

3. Closed-form, scalable uncertainty calibration

Apply HEB-NB’s Type-II ML concentration learning to any generative classifier. The resulting posterior means produce better-calibrated probabilities (lower top-1 ECE) than Laplace, with only 2.3× per-fold overhead—making it practical for real-time inference on large tabular datasets.

4. Principled structural relaxation with HEB-AODE

Extend the adaptive smoothing to average one-dependence estimators, allowing dependencies among features without manual smoothing choices. This improves F1, log-loss, and Brier on high-cardinality benchmarks (e.g., 22.1% log-loss reduction on click-prediction) while retaining closed-form inference.

5. Risk-aware feature weighting for calibration

Combine HEB-M with sqrt-mutual-information weighting (HEB-M+GR) to reduce top-1 ECE by 41–70% versus Laplace on high-cardinality data. This yields a calibrated classifier suitable for decision-making under uncertainty (e.g., medical diagnosis, fraud detection).

6. Theoretical guarantees for deployment

Leverage the non-asymptotic l1 error bound and excess Bayes-risk bound to certify classifier performance without assuming uniform feature densities. This enables safe deployment in safety-critical applications where worst-case error must be bounded.

What the improved AI system can do:

• Achieve state-of-the-art probabilistic classification on high-cardinality tabular data (e.g., e-commerce, genomics, network logs) with no manual smoothing hyperparameters.

• Provide well-calibrated probability estimates for rare classes and imbalanced datasets, improving decision thresholds and downstream cost-sensitive decisions.

• Scale to millions of features and samples with memory/time complexity identical to standard Naive Bayes (up to a constant factor).

• Offer a unified, theoretically grounded framework that bridges Laplace smoothing and full-shrinkage estimators, with provable minimax-rate error and vanishing bias.

• Automatically adapt smoothing strength to feature cardinality, sample size, and class imbalance—eliminating the need for cross-validation or heuristic tuning.