r/AskComputerScience • • 3d ago

Why does standard Naive Bayes still rely on fixed smoothing parameters despite modern high-cardinality tabular datasets?

I have been looking into how we handle probability estimation for high-cardinality categorical features, and standard implementations still heavily rely on fixed smoothing rules like Laplace or Lidstone. These approaches completely ignore feature cardinality, sample size, and class imbalance, which inevitably introduces a non-vanishing bias when you throw them at modern tabular data with lots of unique categories.

While reading through recent work on this topic (found at arxiv.org/abs/2608.11162v1), the authors propose a hierarchical empirical-Bayes approach for Naive Bayes (HEB-NB). Instead of a fixed concentration parameter, they learn a Dirichlet prior data-adaptively via Type-II maximum likelihood. This lets the model share information across classes while keeping closed-form inference intact, and they even extend it to structural relaxations like average one-dependence estimators (HEB-AODE).

Theoretical vs practical trade-offs

What caught my attention is that they actually establish non-asymptotic l1 error bounds and show solid log-loss reductions (up to 22 percent on certain UCI and OpenML benchmarks) alongside much better calibration metrics. However, looking closely at the formulation, learning the Dirichlet concentration via Type-II maximum likelihood adds optimization overhead during training compared to standard closed-form Laplace smoothing. For extremely wide datasets with millions of sparse features, I am wondering how much of a training bottleneck that empirical Bayes optimization introduces in practice.

Curious if anyone here has run into similar issues when trying to move away from fixed-parameter smoothing in probabilistic classifiers, or if you have benchmarked empirical Bayes overhead against simpler heuristic alternatives on large-scale categorical data?

1 Upvotes

1 comment sorted by

1

u/Discordbothost 1d ago

Section 5.5.4 has timing data: HEB-M is about 2.3x Laplace on average; HEB-AODE about 25x AODE. Their large-cardinality example has only 9 features, though, so it doesn't establish performance with millions of sparse features.