Local Robustness Quantification for Naive Bayes Classifiers and Generative Forests: a General Approach

Adrián Detavernier; Jasper De Bock

Source-linked AI summary

Local Robustness Quantification for Naive Bayes Classifiers and Generative Forests: a General Approach

Adrián Detavernier, Jasper De Bock

arXiv:2609.11366v1Sep 10, 2026cs.LG

TL;DR

The paper addresses how to assess the trustworthiness of predictions from generative classifiers under uncertainty in their learned distributions. It develops Robustness Quantification methods for Naive Bayes Classifiers and Generative Forests using general local perturbations, including epsilon-contamination, total variation, and chi-squared divergence balls. Experiments show that the resulting robustness values serve as competitive indicators of prediction trustworthiness.

Problem
The paper addresses the need to assess the trustworthiness of individual predictions from generative classifiers when their learned distributions may be perturbed.
Method
The paper reduces Robustness Quantification to local optimization for Naive Bayes Classifiers and Generative Forests under general local perturbations, including epsilon-contamination, total variation, and chi-squared divergence balls.
Results
Experiments on benchmark datasets show that robustness values correlate with accuracy and are competitive indicators of trustworthiness, including for total variation and chi-squared divergence perturbations.
Takeaways & Limitations
Robustness values can accompany predictions as indicators of their trustworthiness for the studied generative classifiers and perturbation models.
Takeaways & Limitations
The behavior of robustness values varies across contexts and models, motivating study of which perturbations best suit particular settings.

Abstract

from arXiv · show

We provide methods for calculating the robustness of the predictions of two types of generative classifiers whose underlying distribution is a Probabilistic Graphical Model (PGM): naive Bayes classifiers and generative forests (a probabilistic extension of random forests). Following the paradigm of robustness quantification, we define the robustness of a prediction as the extent to which the distribution of the classifier can be perturbed without changing this prediction. We consider perturbations obtained by varying the local models of the PGMs within general neighborhoods and focus in particular on epsilon-contamination, total variation distance and chi-squared divergence balls. We test our methods on benchmark datasets, demonstrate that the robustness value of a prediction serves as an indicator for its trustworthiness and compare our approach with other such indicators.

1. Introduction

The paper develops Robustness Quantification (RQ) as a trustworthiness indicator for classifier predictions. It generalizes existing approaches to broader perturbations and finds the resulting robustness values competitive with uncertainty-based indicators.

RQ measures how much a classifier’s distribution can be perturbed before its prediction changes, with higher robustness intended to indicate greater trustworthiness.
The paper reduces RQ to an optimization problem and further reduces it to local optimizations for Naive Bayes Classifiers and Generative Forests.
The generalized framework considers epsilon-contamination, total variation distance, and chi-squared divergence perturbations of local models.
Experiments show that robustness values correlate with accuracy and are competitive with epsilon-contamination and uncertainty-based trustworthiness indicators.

2. Classification: Setting and Notation

The paper formalizes discrete classification as mapping finite feature vectors to classes. Generative classifiers estimate a joint distribution and select classes using conditional probabilities, while allowing prediction ties or undefined conditionals.

A classifier maps each finite feature vector to a class, with the predicted class ideally matching the instance’s true class.
Generative classifiers estimate a joint probability mass function and predict a class maximizing the conditional probability given the observed features.
The formal definition accommodates non-unique predictions and cases where the conditional probability is undefined because the feature probability is zero.

3. Robustness of a Prediction

RQ quantifies prediction stability under expanding sets of distributional perturbations. The paper defines robustness through the smallest perturbation size that permits an alternative prediction and derives a practical lower-expectation characterization.

A perturbation is a compact set of probability mass functions containing the learned distribution, commonly constructed as a neighborhood around it.
A prediction is robust when all distributions in the perturbation yield only that prediction as a compatible class.
RQ is the smallest perturbation size at which at least one distribution in the neighborhood predicts a different class.
Parametrized perturbations begin with the original distribution at size zero and expand monotonically as the parameter increases.
The practical characterization checks a lower-expectation condition rather than enumerating every perturbed model, and robustness is found at the smallest root of a non-increasing function.

4. Naive Bayes Classifier

For Naive Bayes Classifiers, the paper exploits conditional independence and independent local perturbations to simplify robustness calculations. The robustness value is obtained by finding the smallest perturbation size at which the resulting condition fails.

Naive Bayes assumes that features are conditionally independent given the class, yielding separate class and feature-given-class local mass functions.
The NBC perturbation consists of all Naive Bayes models whose local conditional feature distributions are selected from their corresponding local perturbation sets.
The perturbation parameter controls neighborhood size, allowing a robustness value to be assigned to each instance.
Independence among local models lets the paper simplify the general robustness condition for Naive Bayes Classifiers into local optimization conditions.
For an NBC, the robustness value is the smallest perturbation size at which the specialized robustness condition is no longer satisfied.

5. Generative Forests

Generative Forests combine generative decision trees into probabilistic circuits whose predictions can be assessed for robustness by perturbing local sum-node weights. The paper derives a recursive calculation that determines robustness efficiently from the forest structure.

5. Generative Forests: Generative Forests use a uniform mixture of Generative Decision Trees, represented as a probabilistic circuit with a root sum node.The mixture variant is selected because it has a single joint distribution, while each GeDT is a binary tree of leaf and sum nodes.
5. Generative Forests: Leaf distributions factorize over classes and features, while sum nodes form weighted averages that determine the forest’s joint distribution.Together, leaf models and all sum-node weights completely specify the distribution used for classification.
5. Generative Forests: The forest prediction is assessed by perturbing sum-node weights, generalizing earlier ε-contamination approaches without directly perturbing class or feature distributions.Root weights remain fixed so the importance of each GeDT stays equal; perturbations apply to non-root sum nodes.
5. Generative Forests: Robustness for a GeF reduces to computing a lower expectation through the forest’s recursive structure.For each competing class, the method evaluates a recursively defined function at the root and identifies the smallest perturbation radius that changes the prediction.
5. Generative Forests: The robustness value is the smallest δ at which the recursive root-node check fails for a competing class.This converts prediction robustness into a structured calculation over the forest rather than an exhaustive search over full joint distributions.

6. Local Perturbations

The paper models local uncertainty with neighborhoods around probability or weight functions and supports three perturbation families: ε-contamination, total variation distance, and χ2-divergence balls. Robustness calculations reduce to lower and upper probabilities or lower expectations over these neighborhoods.

6. Local Perturbations: The framework considers ε-contamination, total variation distance balls, and χ2-divergence balls as local perturbations of mass functions.For NBCs these neighborhoods apply to local class and feature distributions; for GeFs they apply to sum-node weight vectors.
6. Local Perturbations: The resulting formulas make the robustness calculations comparable across the three perturbation families while retaining model-specific local optimization problems.The section presents the formulas both for self-contained comparison with prior ε-contamination work and for the generalized neighborhoods.
6. Local Perturbations: For NBCs, robustness requires lower and upper probabilities of feature outcomes under each local perturbation.These bounds are defined as the minimum and maximum probability of an outcome over the neighborhood and are summarized in Table 1.
6. Local Perturbations: NBC robustness also requires lower expectations of indicator differences under perturbed class distributions.The coefficients α and β represent products of lower and upper probabilities that do not depend on the class-distribution perturbation.
6. Local Perturbations: For GeFs, each perturbed sum node requires minimizing a weighted average of its children’s recursive values.Because the considered sum nodes have two children, the minimization uses the ordering of the two child values and can be evaluated with lower-probability formulas.

7. Experiments

Experiments on 11 datasets evaluate robustness values against uncertainty metrics by measuring how accuracy changes when low-confidence predictions are rejected. The robustness measures are competitive overall, although the strongest metric depends on classifier, rejection rate, and performance measure.

Evaluation design: The evaluation uses accuracy-rejection curves, which track remaining-prediction accuracy as instances with the lowest robustness or highest uncertainty are progressively rejected.The experiments include six uncertainty metrics and robustness values for ε-contamination, total variation, and χ2-divergence perturbations.
Accuracy-rejection curves: On the examined dataset, the three robustness measures keep increasing through the highest rejection rates and outperform the other metrics overall.The figure shows accuracy-rejection curves averaged over 10 runs for GeFs on dataset D5.
Metric comparisons: Performance varies by rejection rate: ut can outperform the robustness measures around 40% rejection on the illustrated dataset.This illustrates why the authors avoid naming one universally best metric.
Metric comparisons: For NBCs, rχ2 performs best especially at higher rejection rates, whereas rTV performs best for GeFs especially at lower rejection rates.The comparison summarizes mean accuracy and dataset wins across rejection rates in Tables 3 and 4.
Overall findings: Robustness values are competitive trustworthiness indicators without requiring classifier retraining, unlike ensemble-based metrics such as ut, ua, and ue.The authors therefore regard them as a promising alternative when bootstrap retraining is computationally expensive or unavailable.

8. Conclusion and Future Work

The paper generalizes robustness quantification for naive Bayes classifiers and generative forests beyond ε-contamination to general local-parameter perturbations. Experiments support total variation and χ2-divergence robustness values as trustworthiness indicators, while future work should examine broader models, perturbations, and distribution-shift settings.

Conclusion: The main contribution generalizes robustness quantification from ε-contamination to arbitrary perturbations of local parameters in NBCs and GeFs.The paper derives formulas for total variation, χ2-divergence, and ε-contamination perturbations.
Conclusion: Experiments indicate that total variation and χ2-divergence robustness values can serve as indicators of prediction trustworthiness.
Future work: Future work includes studying other perturbations, other model classes, and how perturbation choice should vary across contexts and models.The authors specifically suggest evaluating the methods under noise or distribution shift.
Future work: Combining the new robustness metrics with uncertainty quantification is proposed as another direction because prior work found the two approaches complementary.

Appendix A. Computing Lower Expectations for GeFs

The appendix derives a recursive method for computing lower expectations over perturbed generative forests. It decomposes the optimization across independently perturbed local weights and combines child-node results through the forest structure.

Recursive computation: Theorem 8 computes the lower expectation of any function over a perturbed GeF through a recursively defined node function V.The theorem allows arbitrary perturbation sets for sum-node weights and a general root perturbation.
Relation to prior work: The construction is inspired by recursive lower-expectation methods for sum-product networks, but targets GeF perturbations and robustness calculations.The cited prior work is more general in model class but narrower in inference, while this appendix emphasizes the robustness-calculation setting.
Proof: At leaf nodes, the lower expectation reduces to the expectation under the unperturbed leaf distribution because no weights are present to perturb.
Proof: At sum nodes, induction combines the children’s recursive values while minimizing over the perturbed weight vector.
Proof: Independence among local weight perturbations allows separate minimizations over child subtrees, yielding the recursive decomposition.

Appendix B. Additional Details on the Experiments

The experiments use UCI datasets adapted for discrete-feature classification, with continuous features and missing-value instances removed. Unless predefined splits exist, datasets use capped 40% test sets; naive Bayes smoothing is selected by 5-fold cross-validation.

Experiments use UCI datasets, with continuous features and instances containing missing values removed to match the discrete-feature setting.
Unless a predefined split exists, each dataset uses a 40% test set capped at 500 instances.
Naive Bayes training selects its smoothing parameter by 5-fold cross-validation before fitting on the full training set.
Table 5 lists the datasets used in the experiments.

Appendix C. Uncertainty Quantification Metrics

The appendix compares robustness with uncertainty-based trustworthiness measures. These measures treat higher uncertainty as less trustworthy and support assessment through uncertainty-based acceptance–risk curves.

Uncertainty quantification complements robustness assessment, with higher uncertainty indicating a less trustworthy prediction.
The experiments compare robustness with six uncertainty measures, including predicted-class uncertainty, entropy, and confidence margin.
For uncertainty-based acceptance–risk curves, instances with the highest uncertainty are rejected first.