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

# Local Robustness Quantification for Naive Bayes Classifiers and Generative Forests: a General Approach
Source: [https://arxiv.org/html/2609.11366](https://arxiv.org/html/2609.11366)
Jasper De BockEmail:[jasper\.debock@ugent\.be](mailto:[email protected])Affiliation:Foundations Lab for imprecise probabilities Ghent University Ghent, Belgium

###### Abstract

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\.

††volume:TBD††year:2026††workshop:Probabilistic Graphical Models \(PGM\)††editor:Gustau Camps\-Valls, Manuele Leonelli and Gherardo Varando###### keywords

trustworthy classification, generative forests, naive Bayes classifier, imprecise probabilities

## 1Introduction

Say that you are writing a paper and the deadline is approaching, so you have to quickly finish the paper and submit it\. However, the central proof of the paper is not working yet, so, to save time, you decide to consult a Large Language Model \(LLM\) to write the proof for you\. You get the proof from the LLM, but you realize that time’s up and that you are not able to check the proof before submitting the paper\.111Disclaimer: this situation is purely hypothetical and does not reflect the actual practices of the author\(s\)\.Would you trust the proof of the LLM? Would you take the risk? Or would you only do it if the LLM is extremely confident about the proof? If such a \(hopefully unrealistic\) situation arises, it would be very useful if the LLM were to give us some indication of the trustworthiness of its output\. Similarly for other high\-stakes settings, such as medical diagnosis, it would be very useful if a model were able to assess the trustworthiness of its own predictions such that the user could take this information into account when making decisions based on these predictions\.

In this paper, we consider one possible approach that attempts to accompany the individual predictions of a classifier with an indication of their trustworthiness: Robustness Quantification \(RQ\)\([Detavernier and De Bock, 2025](https://arxiv.org/html/2609.11366#bib.bib3)\)\. RQ in particular quantifies the so\-called*robustness*of a classifier’s predictions, which is the extent to which the model can be perturbed without changing the prediction, the idea being that predictions with high robustness are more trustworthy because they are less sensitive to errors made while training the model\. RQ has so far been studied for classifiers based on several types of Probabilistic Graphical Models \(PGMs\): the Naive Bayes Classifier \(NBC\)\([Detavernier and De Bock, 2025](https://arxiv.org/html/2609.11366#bib.bib3)\), for Generative Forests \(GeFs\)\([Correia et al\., 2020a](https://arxiv.org/html/2609.11366#bib.bib13)\), and for Bayesian networks and Markov random fields\([De Bock et al\., 2014](https://arxiv.org/html/2609.11366#bib.bib10)\)\. These results have furthermore shown that the robustness of a prediction, defined in this way, can be a useful indicator for its trustworthiness, in the sense that predictions with a higher robustness value tend to be correct more often than predictions with a lower robustness value\.

In this work, we show how RQ can be reduced to an optimization problem\. Additionally, we use ideas from imprecise probability theory\([Augustin et al\., 2014](https://arxiv.org/html/2609.11366#bib.bib14)\)and credal classification\([Corani et al\., 2014](https://arxiv.org/html/2609.11366#bib.bib9)\)to provide general methods for reducing this optimization problem to local optimizations if the PGM is an NBC or GeF that is perturbed by local perturbations of its local probability or weight functions, respectively\. In doing so, we generalize existing methods that focussed onε\\varepsilon\-contamination perturbations\. We illustrate this generality by considering as perturbations total variation distance and chi\-squared divergence balls, and we show in our experiments that the resulting robustness values still correlate with accuracy, and moreover that they are competitive with those obtained withε\\varepsilon\-contamination and with indicators of trustworthiness that are based on uncertainty\.

## 2Classification: Setting and Notation

To formalize the setting, namely classification with discrete features, we introduce some notation\. The goal of a classifier is to predict the classccof an instance, which is an element of a finite set of classes𝒞\\mathcal\{C\}\. When the class is unknown, we refer to it as the class variableCC\. To make this prediction, we typically have some information about the instance in the form of a set of features𝒇\\bm\{f\}\. Each of the features is denoted by a variableFiF\_\{i\}and takes valuesfif\_\{i\}in a finite setℱi\\mathcal\{F\}\_\{i\}, withi∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}, whereNNis the number of features\. We will collect all the features of an instance in a vector, and refer to this vector as the feature vector or just the features of the instance\. The feature vector of an instance is given by𝒇=\(f1,…,fN\)\\bm\{f\}=\(f\_\{1\},\\dots,f\_\{N\}\), wherefif\_\{i\}is the value of theii\-th feature for this instance\. All such possible feature vectors are collected in the set𝓕=ℱ1×⋯×ℱN\\bm\{\\mathcal\{F\}\}=\\mathcal\{F\}\_\{1\}\\times\\dots\\times\\mathcal\{F\}\_\{N\}\. Every instance is thus determined by the combination of a classccand its features𝒇\\bm\{f\}\. A classifierh:𝓕→𝒞h:\\bm\{\\mathcal\{F\}\}\\to\\mathcal\{C\}can therefore be seen as a function that maps feature vectors to classes\. In the ideal scenario, the predicted classc^≔h⁡\(𝒇\)\\hat\{c\}\\coloneq h\(\\bm\{f\}\)is the same as the true class of the instance\. In practice, however, this is not always the case\. That is exactly why assessing the trustworthiness of the predictions of a classifier is important\.

This contribution focusses on generative classifiers that first estimate a joint probability mass functionppon𝒞×𝓕\\mathcal\{C\}\\times\\bm\{\\mathcal\{F\}\}, and then predict the classc^\\hat\{c\}that maximizes the conditional probabilityp⁡\(c\|𝒇\)=p⁡\(c,𝒇\)/p⁡\(𝒇\)p\(c\|\\bm\{f\}\)=\\nicefrac\{\{p\(c,\\bm\{f\}\)\}\}\{\{p\(\\bm\{f\}\)\}\}, withp⁡\(𝒇\)≔∑c′∈𝒞p⁡\(c′,𝒇\)p\(\\bm\{f\}\)\\coloneq\\sum\_\{c^\{\\prime\}\\in\\mathcal\{C\}\}p\(c^\{\\prime\},\\bm\{f\}\)\. Thisc^\\hat\{c\}may not be unique though, orp⁡\(c\|𝒇\)p\(c\|\\bm\{f\}\)might be ill\-defined ifp⁡\(𝒇\)=0p\(\\bm\{f\}\)=0, which is why formally, given a set of features𝒇\\bm\{f\}, a generative classifierhp:𝓕→𝒞h\_\{p\}:\\bm\{\\mathcal\{F\}\}\\to\\mathcal\{C\}chooses the predicted classc^\\hat\{c\}from the set

𝒞^p,𝒇≔\{arg⁡maxc∈𝒞⁡p⁡\(c\|𝒇\)if​p​\(𝒇\)\>0𝒞if​p​\(𝒇\)=0\}=argmaxc∈𝒞p\(c,𝒇\)\.\\hat\{\\mathcal\{C\}\}\_\{p,\\bm\{f\}\}\\coloneq\\left\.\\begin\{cases\}\\arg\\max\_\{c\\in\\mathcal\{C\}\}p\(c\|\\bm\{f\}\)&\\text\{if \}p\(\\bm\{f\}\)\>0\\\\ \\mathcal\{C\}&\\text\{if \}p\(\\bm\{f\}\)=0\\end\{cases\}\\right\\\}=\\arg\\max\_\{c\\in\\mathcal\{C\}\}p\(c,\\bm\{f\}\)\.\(1\)In practice,𝒞^p,𝒇\\hat\{\\mathcal\{C\}\}\_\{p,\\bm\{f\}\}will of course typically be a singleton, in which casec^\\hat\{c\}is completely determined bypp, but our methods also work for features for which this is not the case\.

## 3Robustness of a Prediction

The distributionpplearned by a probabilistic classifier is typically not the true data generating distribution; data subject to distribution shift, the use of a specific model architecture, or randomness in the training process/model parameters can all lead to deviations ofppfrom the true distribution, and hence to a suboptimal prediction\. So, what if we would slightly change the distributionppthat the model learned? Would the prediction change? How much would we have to change the distribution before the prediction changes? RQ answers this last question by quantifying how much the learned distributionppof the model can be changed without changing the resulting prediction of the classifier\. To formalize this idea, we consider perturbations of the mass functionpp, which are simply sets of mass functions that containpp\.

LetΩ\\Omegabe a finite set of outcomes and letΣΩ\\Sigma\_\{\\Omega\}be the set of all probability mass functions onΩ\\Omega: maps fromΩ\\Omegato\[0,1\]\[0,1\]that sum up to one\.

###### Definition 1\.

Consider a mass functionp∈ΣΩp\\in\\Sigma\_\{\\Omega\}on a finite set of outcomesΩ\\Omega\. A*perturbation*ofppis a compact set𝒫⊆ΣΩ\\mathcal\{P\}\\subseteq\\Sigma\_\{\\Omega\}of mass functions onΩ\\Omegasuch thatp∈𝒫p\\in\\mathcal\{P\}\.

This is a general and deliberately vague definition since it does not specify how the perturbation is constructed\. In practice, we will usually construct such a perturbation as a neighborhood aroundpp, withp∈Σ𝒞×𝓕p\\in\\Sigma\_\{\\mathcal\{C\}\\times\\bm\{\\mathcal\{F\}\}\}a mass function learned by a probabilistic classifier\.

Given a perturbation𝒫\\mathcal\{P\}ofppand set of features𝒇\\bm\{f\}, we can now construct the set of possible predictions𝒞^𝒫,𝒇≔⋃p′∈𝒫𝒞^p′,𝒇\\hat\{\\mathcal\{C\}\}\_\{\\mathcal\{P\},\\bm\{f\}\}\\coloneq\\bigcup\_\{p^\{\\prime\}\\in\\mathcal\{P\}\}\\hat\{\\mathcal\{C\}\}\_\{p^\{\\prime\},\\bm\{f\}\}that are compatible with at least one of the perturbed modelsp′∈𝒫p^\{\\prime\}\\in\\mathcal\{P\}\. The predictionc^\\hat\{c\}is said to be robust w\.r\.t\. the perturbation𝒫\\mathcal\{P\}if the only such compatible prediction isc^\\hat\{c\}itself\.

###### Definition 2\.

Lethph\_\{p\}be a generative classifier corresponding to a mass functionpp\. Letc^\\hat\{c\}be the prediction according tohph\_\{p\}for the set of features𝐟\\bm\{f\}, let𝒫\\mathcal\{P\}be a perturbation ofpp, and let𝒞^𝒫,𝐟\\hat\{\\mathcal\{C\}\}\_\{\\mathcal\{P\},\\bm\{f\}\}be the set of possible predictions w\.r\.t\. the perturbation𝒫\\mathcal\{P\}\. Thenc^\\hat\{c\}is*robust*w\.r\.t\. the perturbation𝒫\\mathcal\{P\}if𝒞^𝒫,𝐟=\{c^\}\\hat\{\\mathcal\{C\}\}\_\{\\mathcal\{P\},\\bm\{f\}\}=\\\{\\hat\{c\}\\\}\.

For readers that are familiar with imprecise probabilities and credal classification, these ideas should be familiar\. In that context, our perturbations would typically be called credal sets and𝒞^𝒫,𝒇\\hat\{\\mathcal\{C\}\}\_\{\\mathcal\{P\},\\bm\{f\}\}would be an example of a corresponding credal classifier: a classification procedure that outputs a set of classes\.222Many different imprecise decision criteria can be used to associate such a set of classes with a credal set[Troffaes \(2007\)](https://arxiv.org/html/2609.11366#bib.bib19)\. Our approach, which simply gathers the predictions of the different distributions in the credal set, essentially corresponds to the use of E\-admissibility; it has the advantage of having an intuitive sensitivity\-analysis interpretation\. Credal classification instead typically uses another decision criterion, called maximality, for which the corresponding set of classes can more easily be determined using optimization techniques\. For the purposes of determining robustness, however, this choice does not matter\. For readers familiar with maximality, this should follow easily from Theorem[2](https://arxiv.org/html/2609.11366#Thmtheorem2)further on\.Robustness of an instance then corresponds to this credal classifier being determinate, in the sense that its output contains only a single class\. An important observation in credal classification, which inspired the development of RQ\([De Bock et al\., 2014](https://arxiv.org/html/2609.11366#bib.bib10)\), is that traditional classifiers tend to perform worse on instances where their credal counterparts remain indeterminate\([Corani and Zaffalon, 2008](https://arxiv.org/html/2609.11366#bib.bib18)\)\.

The ideas behind RQ are similar, but it has different aims\. First, RQ is not interested in determining𝒞^𝒫,𝒇\\hat\{\\mathcal\{C\}\}\_\{\\mathcal\{P\},\\bm\{f\}\}, but focusses solely on robustness \(determinacy\)\. Second, instead of determining whether a prediction is robust w\.r\.t\. a given fixed perturbation, RQ instead wants to quantify*how*robust it is\. RQ does this by controlling the size of the perturbation in a parametrized manner and increasing this size until the prediction of the model is no longer robust, or thus until at least one distribution in the neighborhood predicts a different class\. This smallest perturbation size for which the prediction is no longer robust is then used as a numeric measure of robustness\. To formalize this, we consider*parametrized perturbations*\.

###### Definition 3\.

Consider a mass functionp∈ΣΩp\\in\\Sigma\_\{\\Omega\}on a finite set of outcomesΩ\\Omega\. Let𝒫δ\\mathcal\{P\}^\{\\delta\}be a perturbation ofppfor allδ∈Δ⊆ℝ≥0\\delta\\in\\Delta\\subseteq\\mathbb\{R\}\_\{\\geq 0\}, whereΔ\\Deltais a set of possible values forδ\\deltathat includes zero\. Then the family𝒫Δ≔\(𝒫δ\)δ∈Δ\\mathcal\{P\}^\{\\Delta\}\\coloneq\\left\(\\mathcal\{P\}^\{\\delta\}\\right\)\_\{\\delta\\in\\Delta\}is called a*parametrized perturbation*ofppif the following conditions hold: \(1\) ifδ=0\\delta=0, then𝒫0=\{p\}\\mathcal\{P\}^\{0\}=\\\{p\\\}; and \(2\) ifδ1≤δ2\\delta\_\{1\}\\leq\\delta\_\{2\}, then𝒫δ1⊆𝒫δ2\\mathcal\{P\}^\{\\delta\_\{1\}\}\\subseteq\\mathcal\{P\}^\{\\delta\_\{2\}\}\.

Clearly, the bigger the value ofδ\\delta, the bigger the perturbation, in the sense that it contains more distributions\. Concrete examples of such parametrized perturbations are given in Section[6](https://arxiv.org/html/2609.11366#S6)\. Next, we formalize the numeric measure of robustness\.

###### Definition 4\.

Lethph\_\{p\}be a generative classifier corresponding to a mass functionpp, and letc^\\hat\{c\}be the prediction according tohph\_\{p\}for the set of features𝐟\\bm\{f\}\. Let𝒫Δ\\mathcal\{P\}^\{\\Delta\}be a parametrized perturbation ofpp, withΔ⊆ℝ≥0\\Delta\\subseteq\\mathbb\{R\}\_\{\\geq 0\}the possible values for the parameterδ\\delta\. Then the*robustness \(value\)*r𝒫Δ​\(𝐟\)r\_\{\\mathcal\{P\}^\{\\Delta\}\}\(\\bm\{f\}\)w\.r\.t\.𝒫Δ\\mathcal\{P\}^\{\\Delta\}of an instance with features𝐟\\bm\{f\}is the infimumδ∈Δ\\delta\\in\\Deltafor which the predictionc^\\hat\{c\}is no longer robust w\.r\.t\. the perturbation𝒫δ\\mathcal\{P\}^\{\\delta\}\. If there is no suchδ\\delta, then we setr𝒫Δ​\(𝐟\)=\+∞r\_\{\\mathcal\{P\}^\{\\Delta\}\}\(\\bm\{f\}\)=\+\\infty\.

Henceforth, whenever we use the notation𝒫δ\\mathcal\{P\}^\{\\delta\}for a perturbation, we implicitly assume that it is part of a parametrized perturbation𝒫Δ\\mathcal\{P\}^\{\\Delta\}for some setΔ\\Deltaof possible values forδ\\delta\.

This definition faithfully captures the ideas behind RQ, but it isn’t the most practical one because, at first sight, checking whether a prediction is robust w\.r\.t\. a perturbation would require us to determine the predictions of all the distributions in the perturbation\. To address this issue, we now proceed to provide an equivalent, more practical, characterization of robustness\. This characterization is expressed in terms of the lower expectation of a perturbation𝒫\\mathcal\{P\}, defined for any real\-valued functionffonΩ\\Omegaby

E¯𝒫​\(f\)≔minp′∈𝒫⁡Ep′​\(f\),\\underline\{E\}\_\{\\mathcal\{P\}\}\\left\(f\\right\)\\coloneq\\min\_\{p^\{\\prime\}\\in\\mathcal\{P\}\}E\_\{p^\{\\prime\}\}\\left\(f\\right\),\(2\)whereEp′​\(f\)=∑x∈Ωp′​\(x\)​f​\(x\)E\_\{p^\{\\prime\}\}\\left\(f\\right\)=\\sum\_\{x\\in\\Omega\}p^\{\\prime\}\(x\)f\(x\)is the expectation offfw\.r\.t\. the mass functionp′p^\{\\prime\}\. IfΩ=𝒞×𝒴\\Omega=\\mathcal\{C\}\\times\\mathcal\{Y\}for some set𝒴\\mathcal\{Y\}, then for anyc∈𝒞c\\in\\mathcal\{C\}, we use𝕀c\\mathbb\{I\}\_\{c\}to denote the function that takes the value 1 ifx∈\{c\}×𝒴x\\in\\\{c\\\}\\times\\mathcal\{Y\}and 0 otherwise\. IfΩ=𝓕×𝒴\\Omega=\\bm\{\\mathcal\{F\}\}\\times\\mathcal\{Y\},𝕀𝒇\\mathbb\{I\}\_\{\\bm\{f\}\}is defined similarly\.

###### Theorem 5\.

Lethph\_\{p\}be a generative classifier corresponding to a mass functionpp, letc^\\hat\{c\}be the prediction according tohph\_\{p\}for the set of features𝐟\\bm\{f\}, and let𝒫\\mathcal\{P\}be a perturbation ofpp\. Thenc^\\hat\{c\}is*robust*w\.r\.t\. the perturbation𝒫\\mathcal\{P\}if and only if

∀p′∈𝒫,∀c∈𝒞\\\{c^\}:p′​\(c^,𝒇\)−p′​\(c,𝒇\)\>0,\\forall p^\{\\prime\}\\in\\mathcal\{P\},\\forall c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\\colon p^\{\\prime\}\(\\hat\{c\},\\bm\{f\}\)\-p^\{\\prime\}\(c,\\bm\{f\}\)\>0,\(3\)or, equivalently, if

minc∈𝒞\\\{c^\}⁡E¯𝒫​\[\(𝕀c^−𝕀c\)​𝕀𝒇\]\>0\.\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\underline\{E\}\_\{\\mathcal\{P\}\}\\big\[\(\\mathbb\{I\}\_\{\\hat\{c\}\}\-\\mathbb\{I\}\_\{c\}\)\\mathbb\{I\}\_\{\\bm\{f\}\}\\big\]\>0\.\(4\)

###### Proof\.

By Definition[2](https://arxiv.org/html/2609.11366#Thmtheorem2)and Equation \([1](https://arxiv.org/html/2609.11366#S2.E1)\),c^\\hat\{c\}is robust w\.r\.t\.𝒫\\mathcal\{P\}if and only if𝒞^p′,𝒇=\{c^\}\\hat\{\\mathcal\{C\}\}\_\{p^\{\\prime\},\\bm\{f\}\}=\\\{\\hat\{c\}\\\}for allp′∈𝒫p^\{\\prime\}\\in\\mathcal\{P\}\. This holds if and only if∀p′∈𝒫,∀c∈𝒞\\\{c^\}:p′​\(c^,𝒇\)−p′​\(c,𝒇\)\>0,\\forall p^\{\\prime\}\\in\\mathcal\{P\},\\forall c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\\colon p^\{\\prime\}\(\\hat\{c\},\\bm\{f\}\)\-p^\{\\prime\}\(c,\\bm\{f\}\)\>0,which proves the first equivalence of the theorem\. Since𝒫\\mathcal\{P\}is compact, the previous condition is equivalent to requiring that the minimum of this difference over allc∈𝒞\\\{c^\}c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}and allp′∈𝒫p^\{\\prime\}\\in\\mathcal\{P\}is positive:minc∈𝒞\\\{c^\}⁡minp′∈𝒫​p′​\(c^,𝒇\)−p′​\(c,𝒇\)\>0\.\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\min\_\{p^\{\\prime\}\\in\\mathcal\{P\}\}p^\{\\prime\}\(\\hat\{c\},\\bm\{f\}\)\-p^\{\\prime\}\(c,\\bm\{f\}\)\>0\.Sincep′​\(c^,𝒇\)−p′​\(c,𝒇\)=Ep′​\[𝕀c^​𝕀𝒇−𝕀c​𝕀𝒇\]p^\{\\prime\}\(\\hat\{c\},\\bm\{f\}\)\-p^\{\\prime\}\(c,\\bm\{f\}\)=E\_\{p^\{\\prime\}\}\\big\[\\mathbb\{I\}\_\{\\hat\{c\}\}\\mathbb\{I\}\_\{\\bm\{f\}\}\-\\mathbb\{I\}\_\{c\}\\mathbb\{I\}\_\{\\bm\{f\}\}\\big\], this is equivalent tominc∈𝒞\\\{c^\}⁡E¯𝒫​\[\(𝕀c^−𝕀c\)​𝕀𝒇\]\>0,\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\underline\{E\}\_\{\\mathcal\{P\}\}\\big\[\(\\mathbb\{I\}\_\{\\hat\{c\}\}\-\\mathbb\{I\}\_\{c\}\)\\mathbb\{I\}\_\{\\bm\{f\}\}\\big\]\>0,as claimed\. ∎

Consequently, checking whether a prediction is robust w\.r\.t\. a perturbation𝒫\\mathcal\{P\}only requires us to check Equation \([4](https://arxiv.org/html/2609.11366#S3.E4)\) of Theorem[5](https://arxiv.org/html/2609.11366#Thmtheorem5)\. Furthermore, note that the functionR:Δ→ℝ:δ↦minc∈𝒞\\\{c^\}⁡E¯𝒫δ​\(\(𝕀c^−𝕀c\)​𝕀𝒇\)R:\\Delta\\to\\mathbb\{R\}:\\delta\\mapsto\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\underline\{E\}\_\{\\mathcal\{P\}^\{\\delta\}\}\\left\(\(\\mathbb\{I\}\_\{\\hat\{c\}\}\-\\mathbb\{I\}\_\{c\}\)\\mathbb\{I\}\_\{\\bm\{f\}\}\\right\)is non\-increasing, since the bigger the perturbation, the smaller the lower expectation\. Finding the robustness value therefore amounts to finding the infimumδ\\deltafor whichR⁡\(δ\)=0R\(\\delta\)=0; that is, we need to find the smallest root of a non\-increasing function\. In practice, the functionRRwill often be continuous and strictly decreasing, which makes this root\-finding problem even easier to solve\. Several methods exist for finding roots of such functions efficiently, which make the quantification of robustness feasible in practice\.

Now that we have the theoretical tools to quantify the robustness of predictions of classifiers, we will apply these tools to two specific types of generative classifiers\.

## 4Naive Bayes Classifier

The first type of generative classifier we will be looking at is the Naive Bayes Classifier \(NBC\)\. This is a very simple model that is often used as a good baseline for more complex classifiers\. The central assumption on which the Naive Bayes Classifier is based is that the features are conditionally independent given the class\. This implies that there is a mass functionpC∈Σ𝒞p\_\{C\}\\in\\Sigma\_\{\\mathcal\{C\}\}and, for allc∈𝒞c\\in\\mathcal\{C\}andi∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}, a mass functionpFi\|c∈Σℱip\_\{F\_\{i\}\|c\}\\in\\Sigma\_\{\\mathcal\{F\}\_\{i\}\}such that

p⁡\(c,𝒇\)=pC​\(c\)​∏i=1NpFi\|c​\(fi\),for all​c∈𝒞​and​𝒇∈𝓕\.p\(c,\\bm\{f\}\)=p\_\{C\}\(c\)\\prod\_\{i=1\}^\{N\}p\_\{F\_\{i\}\|c\}\(f\_\{i\}\),\\quad\\text\{for all \}c\\in\\mathcal\{C\}\\text\{ and \}\\bm\{f\}\\in\\bm\{\\mathcal\{F\}\}\.\(5\)We now consider a specific parametrized perturbation for such NBCs; it is a parametrized version of the model of the Naive Credal Classifier\([Zaffalon, 2002](https://arxiv.org/html/2609.11366#bib.bib11)\)—a generalization of an NBC based on imprecise probabilities\. In particular, we consider a local perturbation𝒫Cδ\\mathcal\{P\}\_\{C\}^\{\\delta\}ofpCp\_\{C\}and local perturbations𝒫Fi\|cδ\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}ofpFi\|cp\_\{F\_\{i\}\|c\}for allc∈𝒞c\\in\\mathcal\{C\}and alli∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}, and let

𝒫NBCδ≔\{p′∈Σ𝒞×𝓕:pC′∈𝒫Cδ,pFi\|c′∈𝒫Fi\|cδ,p′\(c,𝒇\)=pC′\(c\)∏i=1NpFi\|c′\(fi\)\}\\mathcal\{P\}\_\{\\mathrm\{NBC\}\}^\{\\delta\}\\coloneq\\Big\\\{p^\{\\prime\}\\in\\Sigma\_\{\\mathcal\{C\}\\times\\bm\{\\mathcal\{F\}\}\}\\colon p^\{\\prime\}\_\{C\}\\in\\mathcal\{P\}\_\{C\}^\{\\delta\},\\ p^\{\\prime\}\_\{F\_\{i\}\|c\}\\in\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\},\\ p^\{\\prime\}\(c,\\bm\{f\}\)=p\_\{C\}^\{\\prime\}\(c\)\\prod\_\{i=1\}^\{N\}p\_\{F\_\{i\}\|c\}^\{\\prime\}\(f\_\{i\}\)\\Big\\\}\(6\)be the corresponding perturbation ofpp\. This is simply the set of all NBCs whose local models are taken from𝒫Cδ\\mathcal\{P\}\_\{C\}^\{\\delta\}and𝒫Fi\|cδ\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}\. The superscriptδ\\deltaindicates that these perturbations are part of a parametrized perturbation where the parameterδ\\deltacontrols the size of the perturbations, enabling us to associate a robustness value with each instance\.

Since the local models of the NBC are independent, and all models in the perturbation𝒫NBCδ\\mathcal\{P\}^\{\\delta\}\_\{\\mathrm\{NBC\}\}are also NBCs, we can use this structure to simplify the condition for robustness given by Theorem[5](https://arxiv.org/html/2609.11366#Thmtheorem5)even further\.

###### Theorem 6\.

Lethph\_\{p\}be a Naive Bayes classifier with local modelspCp\_\{C\}andpFi\|cp\_\{F\_\{i\}\|c\}for allc∈𝒞c\\in\\mathcal\{C\}and alli∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}and corresponding joint mass functionppdefined by Equation \([5](https://arxiv.org/html/2609.11366#S4.E5)\)\. Letc^\\hat\{c\}be the prediction according tohph\_\{p\}for the set of features𝐟\\bm\{f\}\. Consider local perturbations𝒫Cδ\\mathcal\{P\}\_\{C\}^\{\\delta\}and𝒫Fi\|cδ\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}for allc∈𝒞c\\in\\mathcal\{C\}and alli∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}\. Thenc^\\hat\{c\}is robust w\.r\.t\. the corresponding perturbation𝒫NBCδ\\mathcal\{P\}\_\{\\mathrm\{NBC\}\}^\{\\delta\}ofppif and only if

minc∈𝒞\\\{c^\}⁡E¯𝒫Cδ​\(𝕀c^​∏i=1Np¯Fi\|c^​\(fi\)−𝕀c​∏i=1Np¯Fi\|c​\(fi\)\)\>0,\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\underline\{E\}\_\{\\mathcal\{P\}\_\{C\}^\{\\delta\}\}\\left\(\\mathbb\{I\}\_\{\\hat\{c\}\}\\prod\_\{i=1\}^\{N\}\\underline\{p\}\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\)\-\\mathbb\{I\}\_\{c\}\\prod\_\{i=1\}^\{N\}\\overline\{p\}\_\{F\_\{i\}\|c\}\(f\_\{i\}\)\\right\)\>0,\(7\)wherep¯Fi\|c^​\(fi\)=minpFi\|c^′∈𝒫Fi\|c^δ⁡pFi\|c^′​\(fi\)\\underline\{p\}\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\)=\\min\_\{p^\{\\prime\}\_\{F\_\{i\}\|\\hat\{c\}\}\\in\\mathcal\{P\}\_\{F\_\{i\}\|\\hat\{c\}\}^\{\\delta\}\}p^\{\\prime\}\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\)andp¯Fi\|c​\(fi\)=maxpFi\|c′∈𝒫Fi\|cδ⁡pFi\|c′​\(fi\)\\overline\{p\}\_\{F\_\{i\}\|c\}\(f\_\{i\}\)=\\max\_\{p^\{\\prime\}\_\{F\_\{i\}\|c\}\\in\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}\}p^\{\\prime\}\_\{F\_\{i\}\|c\}\(f\_\{i\}\)\.

###### Proof\.

By Theorem[5](https://arxiv.org/html/2609.11366#Thmtheorem5)c^\\hat\{c\}is robust w\.r\.t\.𝒫NBCδ\\mathcal\{P\}\_\{\\mathrm\{NBC\}\}^\{\\delta\}if and only if

minc∈𝒞\\\{c^\}⁡minp′∈𝒫NBCδ​p′​\(c^,𝒇\)−p′​\(c,𝒇\)\>0\.\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\min\_\{p^\{\\prime\}\\in\\mathcal\{P\}\_\{\\mathrm\{NBC\}\}^\{\\delta\}\}p^\{\\prime\}\(\\hat\{c\},\\bm\{f\}\)\-p^\{\\prime\}\(c,\\bm\{f\}\)\>0\.\(8\)Due to Equation \([5](https://arxiv.org/html/2609.11366#S4.E5)\) and the structure of𝒫NBCδ\\mathcal\{P\}\_\{\\mathrm\{NBC\}\}^\{\\delta\}in Equation \([6](https://arxiv.org/html/2609.11366#S4.E6)\), this is equivalent to

minc∈𝒞\\\{c^\}minpC′∈𝒫Cδmin∀c∈𝒞,∀i∈\{1,…,N\}:pFi\|c′∈𝒫Fi\|cδpC′\(c^\)∏i=1NpFi\|c^′\(fi\)−pC′\(c\)∏i=1NpFi\|c′\(fi\)\>0\.\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\min\_\{p^\{\\prime\}\_\{C\}\\in\\mathcal\{P\}\_\{C\}^\{\\delta\}\}\\min\_\{\\forall c\\in\\mathcal\{C\},\\forall i\\in\\\{1,\\dots,N\\\}:\\ p^\{\\prime\}\_\{F\_\{i\}\|c\}\\in\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}\}p^\{\\prime\}\_\{C\}\(\\hat\{c\}\)\\prod\_\{i=1\}^\{N\}p^\{\\prime\}\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\)\-p^\{\\prime\}\_\{C\}\(c\)\\prod\_\{i=1\}^\{N\}p^\{\\prime\}\_\{F\_\{i\}\|c\}\(f\_\{i\}\)\>0\.\(9\)To minimize this difference, we want to minimize the first \(positive\) term and maximize the negation of the second \(negative\) term\. Because of the independence of the local mass functions in the above expression, we can rewrite it as

minc∈𝒞\\\{c^\}⁡minpC′∈𝒫Cδ⁡\(pC′​\(c^\)​∏i=1NminpFi\|c^′∈𝒫Fi\|c^δ⁡pFi\|c^′​\(fi\|c^\)−pC′​\(c\)​∏i=1NmaxpFi\|c′∈𝒫Fi\|cδ⁡pFi\|c′​\(fi\|c\)\)\>0\.\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\min\_\{p^\{\\prime\}\_\{C\}\\in\\mathcal\{P\}\_\{C\}^\{\\delta\}\}\\left\(p^\{\\prime\}\_\{C\}\(\\hat\{c\}\)\\prod\_\{i=1\}^\{N\}\\min\_\{p^\{\\prime\}\_\{F\_\{i\}\|\\hat\{c\}\}\\in\\mathcal\{P\}\_\{F\_\{i\}\|\\hat\{c\}\}^\{\\delta\}\}p^\{\\prime\}\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\|\\hat\{c\}\)\-p^\{\\prime\}\_\{C\}\(c\)\\prod\_\{i=1\}^\{N\}\\max\_\{p^\{\\prime\}\_\{F\_\{i\}\|c\}\\in\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}\}p^\{\\prime\}\_\{F\_\{i\}\|c\}\(f\_\{i\}\|c\)\\right\)\>0\.\(10\)By using the definitions of the local lower and upper probabilities and local lower expectations, the above condition is equivalent to

minc∈𝒞\\\{c^\}⁡E¯𝒫Cδ​\(𝕀c^​∏i=1Np¯Fi\|c^​\(fi\)−𝕀c​∏i=1Np¯Fi\|c​\(fi\)\)\>0,\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\underline\{E\}\_\{\\mathcal\{P\}\_\{C\}^\{\\delta\}\}\\left\(\\mathbb\{I\}\_\{\\hat\{c\}\}\\prod\_\{i=1\}^\{N\}\\underline\{p\}\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\)\-\\mathbb\{I\}\_\{c\}\\prod\_\{i=1\}^\{N\}\\overline\{p\}\_\{F\_\{i\}\|c\}\(f\_\{i\}\)\\right\)\>0,\(11\)as claimed\. ∎

So, for NBCs the robustness value of an instance can be found by finding the smallest valueδ\\deltafor which the condition of Theorem[6](https://arxiv.org/html/2609.11366#Thmtheorem6)is not satisfied anymore\.

## 5Generative Forests

Even in times when deep learning models are dominating the field of machine learning, tree\-based models are still very much relevant\([Grinsztajn et al\., 2022](https://arxiv.org/html/2609.11366#bib.bib1)\), while being more interpretable and easier to train\. For this reason, and because of their easy to work\-with structure, we choose to also apply RQ to tree\-based models\. To be able to apply our approach, we opt for Generative Forests \(GeFs\), that, in contrast to most tree\-based models, are generative classifiers\. A Generative Forest is either an ensemble of Generative Decision Trees \(GeDTs\)\([Correia et al\., 2020b](https://arxiv.org/html/2609.11366#bib.bib7)\)or a uniform mixture of GeDTs\([Correia et al\., 2020a](https://arxiv.org/html/2609.11366#bib.bib13)\); a GeDT can be seen as generative version of a Decision Tree \(DT\)\. Because the mixture variant has a single joint distribution, it is more suitable for our purposes than the ensemble one\. We will therefore focus on the mixture variant\.

GeDT\+\+vv\+u1u\_\{1\}u2u\_\{2\}ttsswv,u2w\_\{v,u\_\{2\}\}wv,u1w\_\{v,u\_\{1\}\}wu1,sw\_\{u\_\{1\},s\}wu1,tw\_\{u\_\{1\},t\}GeF\+\+rr\+\+vv\+\+v′v^\{\\prime\}\+\+v′′v^\{\\prime\\prime\}\+\+v′′′v^\{\\prime\\prime\\prime\}…\\dotswr,vw\_\{r,v\}wr,v′w\_\{r,v^\{\\prime\}\}wr,v′′w\_\{r,v^\{\\prime\\prime\}\}wr,v′′′w\_\{r,v^\{\\prime\\prime\\prime\}\}Figure 1:Visualization of the structures of a GeDT and a GeF\.A GeDT can be seen as a very simple Probabilistic Circuit \(PC\) with, in our case, a binary tree structure containing only leaf and sum nodes\. A GeF combines several GeDTs into one PC, where the root node is a sum node of which all the children are the root of a GeDT, as shown in fig:GeFs\_fig\. Ifvvis a node in a GeF, then its children are collected inch⁡\(v\)\\mathrm\{ch\}\(v\), its descendants inde⁡\(v\)\\mathrm\{de\}\(v\)\(excludingvvitself\), and its sum node descendants \(excluding the leaf nodes\) insde⁡\(v\)\\mathrm\{sde\}\(v\)\. Note that each node in a such a tree is the root of a subtree containing all its descendants and itself\. If a node has no children, so\|ch⁡\(v\)\|=0\|\\mathrm\{ch\}\(v\)\|=0, then it is a leaf node; otherwise it is a sum node\. A sum nodevvhas for each of its childrenu∈ch⁡\(v\)u\\in\\mathrm\{ch\}\(v\)a weightwv,u≥0w\_\{v,u\}\\geq 0such that∑u∈ch⁡\(v\)wv,u=1\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}=1\. For the root noderrwe set all weights equal, sowr,v=1\|ch⁡\(r\)\|w\_\{r,v\}=\\frac\{1\}\{\|\\mathrm\{ch\}\(r\)\|\}for allv∈ch⁡\(r\)v\\in\\mathrm\{ch\}\(r\)\. The vector of all weights of a sum nodevvis denoted bywvw\_\{v\}and the collection of all weight vectors of the sum nodes in a GeF rooted atvvis denoted byw¯v≔\{wv\}××u∈sde⁡\(v\)\{wu\}\\overline\{w\}\_\{v\}\\coloneq\\\{w\_\{v\}\\\}\\times\\bigtimes\_\{u\\in\\mathrm\{sde\}\(v\)\}\\\{w\_\{u\}\\\}\.

A selling point of GeDTs and GeFs is that they can specify complex joint distributionsp∈Σ𝒞×𝓕p\\in\\Sigma\_\{\\mathcal\{C\}\\times\\bm\{\\mathcal\{F\}\}\}in such a way that they can be easily computed\. They do so by associating simple joint distributions with each of their leaves and then using the sum nodes to take weighted averages of these simple distributions\. Following[Correia et al\. \(2020a\)](https://arxiv.org/html/2609.11366#bib.bib13), for each leaf nodell, its distributionplp\_\{l\}is taken to be factorized over the class and features, meaning thatpl​\(c,𝒇\)=pl,C​\(c\)​∏i=1Npl,Fi​\(fi\)p\_\{l\}\(c,\\bm\{f\}\)=p\_\{l,C\}\(c\)\\prod\_\{i=1\}^\{N\}p\_\{l,F\_\{i\}\}\(f\_\{i\}\)for allc∈𝒞c\\in\\mathcal\{C\}and𝒇∈𝓕\\bm\{f\}\\in\\bm\{\\mathcal\{F\}\}, wherepl,Cp\_\{l,C\}is a local mass function on𝒞\\mathcal\{C\}andpl,Fip\_\{l,F\_\{i\}\}a local mass function onℱi\\mathcal\{F\}\_\{i\}for alli∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}\. In the case of a sum node, its joint distributionpvp\_\{v\}is a weighted sum of the joint distributions of its children, given bypv​\(c,𝒇\)=∑u∈ch⁡\(v\)wv,u​pup\_\{v\}\(c,\\bm\{f\}\)=\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}p\_\{u\}for anyc∈𝒞c\\in\\mathcal\{C\}and𝒇∈𝓕\\bm\{f\}\\in\\bm\{\\mathcal\{F\}\}\. In this way, the collection of all weightsw¯v\\overline\{w\}\_\{v\}of a GeDT or GeF rooted atvv, together with the local models of the leaves, completely determine its joint distributionpvp\_\{v\}\. To make this explicit, we denote the joint distribution of the tree rooted atvvbypw¯vp\_\{\\overline\{w\}\_\{v\}\}, leaving the dependency onpl,Cp\_\{l,C\}andpl,Fip\_\{l,F\_\{i\}\}implicit\. In particular, the joint distribution of a GeF with rootrris denoted bypw¯rp\_\{\\overline\{w\}\_\{r\}\}\.

The main goal of GeFs is to classify each instance based on its set of features𝒇\\bm\{f\}\. Letrrbe the root node of a GeF with joint distributionpw¯rp\_\{\\overline\{w\}\_\{r\}\}, then the predicted classc^=hpw¯r​\(𝒇\)\\hat\{c\}=h\_\{p\_\{\\overline\{w\}\_\{r\}\}\}\(\\bm\{f\}\)is chosen from𝒞^pw¯r,𝒇\\hat\{\\mathcal\{C\}\}\_\{p\_\{\\overline\{w\}\_\{r\}\},\\bm\{f\}\}as defined in Equation \([1](https://arxiv.org/html/2609.11366#S2.E1)\)\. We now want to assess the robustness of this prediction by constructing neighborhoods of the learned distributionpw¯rp\_\{\\overline\{w\}\_\{r\}\}\. As we also did for the NBC, we do this by perturbing their local parameters\. Previous work on calculating the robustness of predictions of GeFs did this by perturbing the weights of the sum nodes usingε\\varepsilon\-contamination\([Correia et al\., 2020a](https://arxiv.org/html/2609.11366#bib.bib13)\)\. We adopt a similar approach but generalize it to allow for arbitrary local perturbations\. Note that, in contrast to the NBC, we won’t be perturbing any probability distributions over classes or features directly here, but only indirectly by perturbing the weights of the sum nodes\.

Given a sum nodevvin a GeDT or GeF with weightswvw\_\{v\}, we consider a perturbation𝒲vδ\\mathcal\{W\}\_\{v\}^\{\\delta\}ofwvw\_\{v\}as defined in Definition[1](https://arxiv.org/html/2609.11366#Thmtheorem1)\. In this work, we choose not to perturb the weights of the root noderrof a GeF to keep the importance of each GeDT equal\. This means that we choose𝒲rδ=\{wr\}\\mathcal\{W\}\_\{r\}^\{\\delta\}=\\\{w\_\{r\}\\\}for allδ\\delta\. When we perturb the weights of all or multiple nodes in a GeF rooted atrr, then we are essentially perturbingw¯r\\overline\{w\}\_\{r\}\. The collection containing all possible combinations of perturbations of the weightsw¯r\\overline\{w\}\_\{r\}of the GeF rooted atrris given by𝒲¯rδ≔\{wr\}××v∈sde⁡\(r\)𝒲vδ\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}\\coloneq\\\{w\_\{r\}\\\}\\times\\bigtimes\_\{v\\in\\mathrm\{sde\}\(r\)\}\\mathcal\{W\}\_\{v\}^\{\\delta\}\. Now, since eachw¯r′∈𝒲¯rδ\\overline\{w\}\_\{r\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}has a corresponding joint distributionpw¯r′p\_\{\\overline\{w\}\_\{r\}^\{\\prime\}\}, each perturbation𝒲¯rδ\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}corresponds to a perturbation𝒫𝒲¯rδ≔\{pw¯r′:w¯r′∈𝒲¯rδ\}\\smash\{\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}\}\}\\coloneq\\big\\\{p\_\{\\overline\{w\}\_\{r\}^\{\\prime\}\}:\\overline\{w\}\_\{r\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}\\big\\\}ofpw¯rp\_\{\\overline\{w\}\_\{r\}\}\. The parameterδ\\deltaagain indicates that this perturbation is part of a parametrized perturbation, enabling us to associate a robustness value with each instance\.

By Theorem[2](https://arxiv.org/html/2609.11366#Thmtheorem2), to calculate the robustness of a GeF, we need to calculate the lower expectation over a given perturbation of its joint probability mass function\. We show that this can be done efficiently by using the structure of GeFs\. To that end, we first define a \(recursive\) function of the nodes in a GeF and prove that the value of this function at the root node of a GeF is enough to check the robustness\.

###### Theorem 7\.

Lethpw¯rh\_\{p\_\{\\overline\{w\}\_\{r\}\}\}be a GeF rooted at noderrwith mass functionpw¯r∈Σ𝒞×𝓕p\_\{\\overline\{w\}\_\{r\}\}\\in\\Sigma\_\{\\mathcal\{C\}\\times\\bm\{\\mathcal\{F\}\}\}corresponding to the weightsw¯r\\overline\{w\}\_\{r\}\. Letc^\\hat\{c\}be the prediction according tohpw¯rh\_\{p\_\{\\overline\{w\}\_\{r\}\}\}for the set of features𝐟\\bm\{f\}\. Consider local perturbations𝒲vδ\\mathcal\{W\}\_\{v\}^\{\\delta\}of the weightswvw\_\{v\}of all sum nodesv≠rv\\neq rand let𝒫𝒲¯rδ\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}\}be the corresponding perturbation ofpw¯rp\_\{\\overline\{w\}\_\{r\}\}\. Thenc^\\hat\{c\}is robust w\.r\.t\.𝒫𝒲¯rδ\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}\}if and only if

minc∈𝒞\\\{c^\}⁡V¯​\(r\)\>0,\\min\_\{c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\}\\underline\{V\}\(r\)\>0,\(12\)where the functionV¯\\underline\{V\}is defined recursively by

V¯​\(v\)≔\{\(pl,C​\(c^\)−pl,C​\(c\)\)​∏i=1Npl,Fi​\(fi\)if​v​is a leaf node​l,1\|ch⁡\(r\)\|​∑u∈ch⁡\(r\)V¯​\(u\)if​v​is the root node​r,min⁡∑u∈ch⁡\(v\)wv′∈𝒲vδ⁡wv,u′​V¯​\(u\)if​v​is any other \(sum\) node\.\\underline\{V\}\(v\)\\coloneq\\begin\{cases\}\\left\(p\_\{l,C\}\(\\hat\{c\}\)\-p\_\{l,C\}\(c\)\\right\)\\prod\_\{i=1\}^\{N\}p\_\{l,F\_\{i\}\}\(f\_\{i\}\)&\\text\{if \}v\\text\{ is a leaf node \}l,\\\\ \\frac\{1\}\{\|\\mathrm\{ch\}\(r\)\|\}\\sum\_\{u\\in\\mathrm\{ch\}\(r\)\}\\underline\{V\}\(u\)&\\text\{if \}v\\text\{ is the root node \}r,\\\\ \\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}^\{\\delta\}\}\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}\\underline\{V\}\(u\)&\\text\{if \}v\\text\{ is any other \(sum\) node\}\.\\end\{cases\}\(13\)

###### Proof\.

Since𝒲r=\{wr\}\\mathcal\{W\}\_\{r\}=\\\{w\_\{r\}\\\}in our case and the product that appears for the casev=ℓv=\\ellis equal toEpl​\(\(𝕀c^−𝕀c\)​𝕀𝒇\)E\_\{p\_\{l\}\}\(\(\\mathbb\{I\}\_\{\\hat\{c\}\}\-\\mathbb\{I\}\_\{c\}\)\\mathbb\{I\}\_\{\\bm\{f\}\}\), it follows from Theorem[8](https://arxiv.org/html/2609.11366#Thmtheorem8)in Appendix[A](https://arxiv.org/html/2609.11366#A1)thatV¯​\(r\)=E¯𝒫𝒲¯rδ​\(\(𝕀c^−𝕀c\)​𝕀𝒇\)\\underline\{V\}\(r\)=\\underline\{E\}\_\{\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{r\}^\{\\delta\}\}\}\\left\(\(\\mathbb\{I\}\_\{\\hat\{c\}\}\-\\mathbb\{I\}\_\{c\}\)\\mathbb\{I\}\_\{\\bm\{f\}\}\\right\)\. The result now follows directly from Theorem[5](https://arxiv.org/html/2609.11366#Thmtheorem5)\. ∎

Consequently, checking whether a prediction of a GeF is robust w\.r\.t\. a perturbation can be done by recursively calculating the functionV¯​\(r\)\\underline\{V\}\(r\)at the root node of the GeF for each of the classes in𝒞\\\{c^\}\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}, and finding the robustness value of an instance amounts to finding the smallest value ofδ\\deltafor which this is not the case\.

## 6Local Perturbations

In this section, we discuss several examples of how a mass function can be perturbed, and give the formulas needed to calculate the robustness of predictions w\.r\.t\. these perturbations\. Recall that the local perturbations that we consider in the paper are, in the case of the NBC,𝒫Cδ\\mathcal\{P\}\_\{C\}^\{\\delta\}ofpCp\_\{C\}and𝒫Fi\|cδ\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}ofpFi\|cp\_\{F\_\{i\}\|c\}for allc∈𝒞c\\in\\mathcal\{C\}alli∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}; and in the case of GeFs,𝒲vδ\\mathcal\{W\}\_\{v\}^\{\\delta\}of the weight vectorwvw\_\{v\}for each sum nodev≠rv\\neq r\. For the sake of ease of notation, we generically denote any of these as a perturbation𝒬δ\\mathcal\{Q\}^\{\\delta\}of a mass functionqqon a possibility spaceΩ\\Omega\. Then for the three types of perturbations that we consider in this work, namelyε\\varepsilon\-contamination, Total Variation \(TV\) distance balls andχ2\\chi^\{2\}\-divergence balls\([Gibbs and Su, 2002](https://arxiv.org/html/2609.11366#bib.bib5)\), the perturbations are defined as follows:

- •ε\\varepsilon\-contamination:𝒬εδ=\{\(1−δ\)​q\+δ​q′:q′∈ΣΩ\}\\mathcal\{Q\}^\{\\delta\}\_\{\\varepsilon\}=\\\{\(1\-\\delta\)q\+\\delta q^\{\\prime\}:q^\{\\prime\}\\in\\Sigma\_\{\\Omega\}\\\}, withδ∈\[0,1\]\\delta\\in\[0,1\];
- •TV distance:𝒬TVδ=\{q′∈ΣΩ:12​∑ω∈Ω\|q⁡\(ω\)−q′​\(ω\)\|≤δ\}\\mathcal\{Q\}^\{\\delta\}\_\{\\mathrm\{TV\}\}=\\\{q^\{\\prime\}\\in\\Sigma\_\{\\Omega\}:\\frac\{1\}\{2\}\\sum\_\{\\omega\\in\\Omega\}\|q\(\\omega\)\-q^\{\\prime\}\(\\omega\)\|\\leq\\delta\\\}, withδ∈\[0,1\]\\delta\\in\[0,1\];
- •χ2\\chi^\{2\}\-divergence:𝒬χ2δ=\{q′∈ΣΩ:∑ω∈Ω\(q′​\(ω\)−q⁡\(ω\)\)2q⁡\(ω\)≤δ\}\\mathcal\{Q\}^\{\\delta\}\_\{\\chi^\{2\}\}=\\\{q^\{\\prime\}\\in\\Sigma\_\{\\Omega\}:\\sum\_\{\\omega\\in\\Omega\}\\frac\{\(q^\{\\prime\}\(\\omega\)\-q\(\\omega\)\)^\{2\}\}\{q\(\\omega\)\}\\leq\\delta\\\}, withδ≥0\\delta\\geq 0\.

For each of the models, different optimization problems need to be solved to calculate the robustness of their predictions\. We now list all of these optimization problems and give for each of the three types of perturbations the formulas needed to solve these problems\. Even though there has already been work on calculating the robustness of predictions of NBCs and GeFs w\.r\.t\.ε\\varepsilon\-contamination, we nevertheless give the formulas to make the paper self\-contained and to make it easier to compare with the other perturbations\. For previous work on the robustness of NBCs w\.r\.t\.ε\\varepsilon\-contamination, we refer to the work of[Detavernier and De Bock \(2025\)](https://arxiv.org/html/2609.11366#bib.bib3)and for GeFs to the work of[Correia et al\. \(2020a\)](https://arxiv.org/html/2609.11366#bib.bib13)\. The formulas for the TV distance andχ2\\chi^\{2\}\-divergence balls are particular cases of more general formulas in recent work of[De Bock \(2026\)](https://arxiv.org/html/2609.11366#bib.bib6), which simplify in our particular context\.

Firstly, we know from Theorem[6](https://arxiv.org/html/2609.11366#Thmtheorem6)that for the NBC we need to calculate the lower and upper probabilities ofpFi\|c^​\(fi\)p\_\{F\_\{i\}\|\\hat\{c\}\}\(f\_\{i\}\)w\.r\.t\. the perturbations𝒫Fi\|cδ\\mathcal\{P\}\_\{F\_\{i\}\|c\}^\{\\delta\}, for allc∈𝒞c\\in\\mathcal\{C\}andi∈\{1,…,N\}i\\in\\\{1,\\dots,N\\\}\. These are particular instances of the task of computing the lower and upper probability of an outcome over a perturbation𝒬δ\\mathcal\{Q\}^\{\\delta\}of a mass functionqqonΩ\\Omega, which we denote byq¯𝒬δ​\(ω\)=minq′∈𝒬δ⁡q′​\(ω\)\\underline\{q\}\_\{\\mathcal\{Q\}^\{\\delta\}\}\(\\omega\)=\\min\_\{q^\{\\prime\}\\in\\mathcal\{Q\}^\{\\delta\}\}q^\{\\prime\}\(\\omega\)andq¯𝒬δ​\(ω\)=maxq′∈𝒬δ⁡q′​\(ω\)\\overline\{q\}\_\{\\mathcal\{Q\}^\{\\delta\}\}\(\\omega\)=\\max\_\{q^\{\\prime\}\\in\\mathcal\{Q\}^\{\\delta\}\}q^\{\\prime\}\(\\omega\)for anyω∈Ω\\omega\\in\\Omega\. For our three perturbations the formulas for these bounds are given in tab:lower\_upper\_probabilities\.

Table 1:The formulas forq¯𝒬δ​\(ω\)\\underline\{q\}\_\{\\mathcal\{Q\}^\{\\delta\}\}\(\\omega\)\(left\) andq¯𝒬δ​\(ω\)\\overline\{q\}\_\{\\mathcal\{Q\}^\{\\delta\}\}\(\\omega\)\(right\) for our three perturbations\.Next, still for the NBCs, by Theorem[6](https://arxiv.org/html/2609.11366#Thmtheorem6)we also need to calculate the lower expectation of𝕀c^​α−𝕀c​β\\mathbb\{I\}\_\{\\hat\{c\}\}\\alpha\-\\mathbb\{I\}\_\{c\}\\betaw\.r\.t\. the local perturbations𝒫Cδ\\mathcal\{P\}\_\{C\}^\{\\delta\}ofpCp\_\{C\}, for allc∈𝒞\\\{c^\}c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}, wherec^\\hat\{c\}is the predicted class by the NBC and withα,β≥0\\alpha,\\beta\\geq 0\. In the equation in Theorem[6](https://arxiv.org/html/2609.11366#Thmtheorem6),α\\alphaandβ\\betarepresent products of lower and upper probabilities that do not depend on the perturbation𝒫Cδ\\mathcal\{P\}\_\{C\}^\{\\delta\}, which is why we write them as constants here\. The formulas forE¯𝒫δ​\(𝕀c^​α−𝕀c​β\)\\underline\{E\}\_\{\\mathcal\{P\}^\{\\delta\}\}\\left\(\\mathbb\{I\}\_\{\\hat\{c\}\}\\alpha\-\\mathbb\{I\}\_\{c\}\\beta\\right\)for our three perturbations are given in tab:lower\_expectation\_f, whereμ\\muandσ2\\sigma^\{2\}are the expected value and variance of𝕀c^​α−𝕀c​β\\mathbb\{I\}\_\{\\hat\{c\}\}\\alpha\-\\mathbb\{I\}\_\{c\}\\betaunderpCp\_\{C\}, andμ2\\mu\_\{2\}andσ22\\sigma\_\{2\}^\{2\}are the expected value and variance of the restriction of this function to𝒞\\\{c^\}\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}under the mass functionpC∗p\_\{C\}^\{\*\}on𝒞\\\{c^\}\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}defined bypC∗​\(c\)=pC​\(c\)1−pC​\(c^\)p\_\{C\}^\{\*\}\(c\)=\\frac\{p\_\{C\}\(c\)\}\{1\-p\_\{C\}\(\\hat\{c\}\)\}for allc∈𝒞\\\{c^\}c\\in\\mathcal\{C\}\\backslash\\\{\\hat\{c\}\\\}\.

Table 2:The formulas forE¯𝒫Cδ​\(𝕀c^​α−𝕀c​β\)\\underline\{E\}\_\{\\mathcal\{P\}\_\{C\}^\{\\delta\}\}\\left\(\\mathbb\{I\}\_\{\\hat\{c\}\}\\alpha\-\\mathbb\{I\}\_\{c\}\\beta\\right\)for our three perturbations\.Lastly, for the GeFs, given a perturbation𝒲vδ\\mathcal\{W\}\_\{v\}^\{\\delta\}of the weights of a sum nodevv, we need to compute the minimum weighted average of the values of its children, where the value of a childu∈ch⁡\(v\)u\\in\\mathrm\{ch\}\(v\)is given by the functionV¯​\(u\)\\underline\{V\}\(u\)\. In the GeFs we consider, this average always consists of only two terms, since all sum nodes of which we perturb the weights have only two children\. If we letu1u\_\{1\}andu2u\_\{2\}be the two children ofvv, such that, without loss of generality,V¯​\(u1\)≤V¯​\(u2\)\\underline\{V\}\(u\_\{1\}\)\\leq\\underline\{V\}\(u\_\{2\}\), then this minimum reduces to:

minwv′∈𝒲vδ⁡wv,u1′​V¯​\(u1\)\+wv,u2′​V¯​\(u2\)=V¯​\(u1\)\+\(V¯​\(u2\)−V¯​\(u1\)\)​w¯v,u2,\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}^\{\\delta\}\}w\_\{v,u\_\{1\}\}^\{\\prime\}\\underline\{V\}\(u\_\{1\}\)\+w\_\{v,u\_\{2\}\}^\{\\prime\}\\underline\{V\}\(u\_\{2\}\)=\\underline\{V\}\(u\_\{1\}\)\+\(\\underline\{V\}\(u\_\{2\}\)\-\\underline\{V\}\(u\_\{1\}\)\)\\underline\{w\}\_\{v,u\_\{2\}\},\(14\)wherew¯v,u2=minwv′∈𝒲vδ⁡wv,u2′\\underline\{w\}\_\{v,u\_\{2\}\}=\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}^\{\\delta\}\}w\_\{v,u\_\{2\}\}^\{\\prime\}is the minimum ofwv,u2w\_\{v,u\_\{2\}\}w\.r\.t\. the perturbation𝒲vδ\\mathcal\{W\}\_\{v\}^\{\\delta\}\. Since the weight vector of a node is a mass function, finding this is equivalent to calculating a lower probability\. We can thus use the formulas in the left column of tab:lower\_upper\_probabilities to calculate this minimum for each of our three perturbations\.

## 7Experiments

We present some preliminary experiments333The source code is available at[https://github\.com/addtaver/RobustnessQuantification](https://github.com/addtaver/RobustnessQuantification)on 11 datasets to illustrate the potential of the robustness values defined in this paper\. In the following, we denote the robustness values forε\\varepsilon\-contamination, TV distance balls andχ2\\chi^\{2\}\-divergence balls asrεr\_\{\\varepsilon\},rTVr\_\{\\mathrm\{TV\}\}andrχ2r\_\{\\chi^\{2\}\}respectively\. For details on the experimental setup, training procedure and the datasets we used, we refer to Appendix[B](https://arxiv.org/html/2609.11366#A2)\. We also compare our three robustness values with another approach that is commonly used to assess the trustworthiness of predictions, namely Uncertainty Quantification \(UQ\)\. Details on the six UQ metrics we compare with \(umargu\_\{\\mathrm\{marg\}\},umaxu\_\{\\mathrm\{max\}\},uHu\_\{\\mathrm\{H\}\},utu\_\{\\mathrm\{t\}\},uau\_\{\\mathrm\{a\}\},ueu\_\{\\mathrm\{e\}\}\) are given in Appendix[C](https://arxiv.org/html/2609.11366#A3)\.

To evaluate the performance of our approach, we check how the accuracy of the model changes as we continuously reject the predictions with the lowest robustness \(or highest uncertainty\); the idea being that if robustness is a good indicator of the trustworthiness of a prediction, then the accuracy on the remaining predictions should increase as we reject more and more instances\. A curve showing for every percentage of rejected instances the accuracy on the remaining predictions, is called an*accuracy\-rejection curve*\(ARC\); fig:acc\_rej\_curve shows an example, where each line represents an average over 10 different runs\.

Figure 2:Accuracy\-rejection curve for dataset D5 for GeFs\.On this particular dataset, the three robustness measures seem to perform best overall since they keep increasing until the very end, more so than the other metrics shown\. However, if we would focus on specific Rejection Rates \(RRs\), then other metrics sometimes perform better\. Take for exampleutu\_\{\\mathrm\{t\}\}, which is clearly the best measure for RRs of around 40%\.

Focussing on specific RRs can be very relevant in practice if you only want to let the model make a prediction for the most trustworthyX%X\\%of instances\. To evaluate the performance of the robustness values in such use cases, we focus on specific RRs in the ARC and check what metric of trustworthiness performs best for each of these RRs\. The results are summarized in tab1 and tab2, where for each specific RR and trustworthiness metric the mean value of the accuracy at that RR over all datasets is shown, with the number of wins \(W\) for that metric at that RR next to it\. A win is defined as having the highest accuracy at that RR for a given dataset, and ties are solved by giving a win to all metrics that are tied for the highest accuracy\. We also included in the last row of these tables the average area under the ARC \(AU\-ARC\) for each metric over all datasets, which instead of focussing on specific RRs, gives an overall indication of the performance of a metric as an indicator of trustworthiness\. The AU\-ARC can also help us to summarize and compare ARCs in a more quantitative way, since comparing ARCs by eye can be very difficult, especially when there are many of them\.

Table 3:Each row, except the last one containing the AU\-ARC, shows the mean accuracy on the remaining instances and the number of datasets for which each metric had the highest accuracy at that RR for the NBC\.Table 4:Each row, except the last one containing the AU\-ARC, shows the mean accuracy on the remaining instances and the number of datasets for which each metric had the highest accuracy at that RR for the GeF\.If we focus on the two new robustness values in these tables, we see thatrχ2r\_\{\\chi^\{2\}\}seems to be the best performing metric for the NBC, especially for higher RRs, whilerTVr\_\{\\mathrm\{TV\}\}seems to be the best performing metric for the GeF, especially for lower RRs\. The robustness valuerεr\_\{\\varepsilon\}has similar AU\-ARCs as the others, seems to do very well in terms of the number of wins for the NBC, and is just lacking behind the other two for the GeF\. For the UQ measures, we see thatueu\_\{\\mathrm\{e\}\}andutu\_\{\\mathrm\{t\}\}seem to perform very well, since they tend to have a high number of wins and the highest AU\-ARCs for certain RRs\. Overall, since some of the differences in performance are rather small, we prefer to refrain from drawing strong conclusions about which is the ‘best’ metric, especially so since we observe that the relative performance of the different metrics depends on the model, RR and performance metric We can conclude however that all three robustness values are competitive as indicators of trustworthiness\. What makes this particularly interesting, is that the metricsutu\_\{\\mathrm\{t\}\},uau\_\{\\mathrm\{a\}\}andueu\_\{\\mathrm\{e\}\}use an ensemble that requires retraining the classifier on bootstrap samples of the training data\. This retraining can be computationally expensive though and is not always possible\. This makes our robustness values, which do not require retraining, a promising alternative\.

## 8Conclusion and Future Work

The main contribution of this paper is that we generalized existing RQ approaches for NBCs and GeFs, which only consideredε\\varepsilon\-contamination, to a more general approach that allows for any type of perturbation of the local parameters of these models\. To illustrate this, we applied our results to two specific types of perturbations, namely TV distance andχ2\\chi^\{2\}\-divergence balls, and provide the formulas needed to calculate the robustness of predictions w\.r\.t\. these perturbations \(and, for the sake of completeness, also forε\\varepsilon\-contamination\)\. Finally, our experiments demonstrate that our new robustness values w\.r\.t\. TV distance andχ2\\chi^\{2\}\-divergence balls can be used as indicators for the trustworthiness of predictions\.

Possible extensions of this work could be to consider other types of perturbations of the local parameters, or other types of models\. Since the behavior of the robustness values seems to be quite different for different contexts and models, it would also be interesting to study what perturbations are best suited for which contexts and models\. A start could be to study and compare our new methods in a context with noise or distribution shift, as previous work has shown that RQ is particularly well\-suited in such contexts in comparison with UQ\([Detavernier and De Bock, 2025](https://arxiv.org/html/2609.11366#bib.bib3);[Detavernier and De Bock, 2026](https://arxiv.org/html/2609.11366#bib.bib2)\)\.

Previous work\([Detavernier and De Bock, 2026](https://arxiv.org/html/2609.11366#bib.bib2)\)also shows that RQ and UQ can be complementary, and can be usefully combined to obtain even better assessments of trustworthiness\. It would therefore be interesting to employ our new RQ metrics in such combinations as well\.

## Acknowledgments

We would like to thank the anonymous reviewers for their time, kind words and helpful feedback\. The work of both authors was partially supported by Ghent University’s Special Research Fund, through Jasper De Bock’s Basic Research Funding project entitled “Modelling Uncertainty with Imprecise Probabilities”\.

## References

- Augustinet al\.\(2014\)T\. Augustin, F\. P\.A\. Coolen, G\. De Cooman, and M\. C\.M\. TroffaesIntroduction to imprecise probabilities\.John Wiley & Sons\.External Links:[Document](https://dx.doi.org/10.1002/9781118763117)Cited by:[§1](https://arxiv.org/html/2609.11366#S1.p3.1)\.
- Coraniet al\.\(2014\)G\. Corani, J\. Abellán, A\. Masegosa, S\. Moral, and M\. ZaffalonClassification\.InIntroduction to Imprecise Probabilities,pp\. 230–257\.External Links:ISBN 9781118763117,[Document](https://dx.doi.org/10.1002/9781118763117.ch10)Cited by:[§1](https://arxiv.org/html/2609.11366#S1.p3.1)\.
- Corani and Zaffalon \(2008\)G\. Corani and M\. ZaffalonLearning reliable classifiers from small or incomplete data sets: the naive credal classifier 2\.\.Journal of Machine Learning Research9\(4\)\.Cited by:[§3](https://arxiv.org/html/2609.11366#S3.p5.1)\.
- Correiaet al\.\(2020a\)A\. H\. C\. Correia, R\. Peharz, and C\. P\. de CamposTowards robust classification with deep generative forests\.External Links:2007\.05721Cited by:[§1](https://arxiv.org/html/2609.11366#S1.p2.1),[§5](https://arxiv.org/html/2609.11366#S5.p1.1),[§5](https://arxiv.org/html/2609.11366#S5.p3.1),[§5](https://arxiv.org/html/2609.11366#S5.p4.1),[§6](https://arxiv.org/html/2609.11366#S6.p2.1)\.
- Correiaet al\.\(2020b\)A\. Correia, R\. Peharz, and C\. P\. de CamposJoints in random forests\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 11404–11415\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2020/file/8396b14c5dff55d13eea57487bf8ed26-Paper.pdf)Cited by:[Appendix B](https://arxiv.org/html/2609.11366#A2.p2.1),[§5](https://arxiv.org/html/2609.11366#S5.p1.1)\.
- De Bocket al\.\(2014\)J\. De Bock, C\. P\. de Campos, and A\. AntonucciGlobal sensitivity analysis for MAP inference in graphical models\.InAdvances in Neural Information Processing Systems,Vol\.27,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2014/file/0966289037ad9846c5e994be2a91bafa-Paper.pdf)Cited by:[§1](https://arxiv.org/html/2609.11366#S1.p2.1),[§3](https://arxiv.org/html/2609.11366#S3.p5.1)\.
- De Bock \(2026\)J\. De BockComputing lower expectations with respect to total variation distance and chi\-squared divergence balls\.Note:[arXiv:2605\.30091](https://arxiv.org/abs/2605.30091)External Links:2605\.30091Cited by:[§6](https://arxiv.org/html/2609.11366#S6.p2.1)\.
- Depeweget al\.\(2018\)S\. Depeweg, J\. Hernandez\-Lobato, F\. Doshi\-Velez, and S\. UdluftDecomposition of uncertainty in Bayesian deep learning for efficient and risk\-sensitive learning\.InProceedings of the 35th International Conference on Machine Learning,J\. Dy and A\. Krause \(Eds\.\),Proceedings of Machine Learning Research, Vol\.80,pp\. 1184–1193\.External Links:[Link](https://proceedings.mlr.press/v80/depeweg18a.html)Cited by:[Appendix C](https://arxiv.org/html/2609.11366#A3.p2.1)\.
- Deratani Mauáet al\.\(2018\)D\. Deratani Mauá, D\. Conaty, F\. Gagliardi Cozman, K\. Poppenhaeger, and C\. Polpo de CamposRobustifying sum\-product networks\.International Journal of Approximate Reasoning101,pp\. 163–180\.External Links:[Document](https://dx.doi.org/10.1016/j.ijar.2018.07.003)Cited by:[Appendix A](https://arxiv.org/html/2609.11366#A1.p2.1)\.
- Detavernier and De Bock \(2025\)A\. Detavernier and J\. De BockRobustness quantification: a new method for assessing the reliability of the predictions of a classifier\.InProceedings of the Fourteenth International Symposium on Imprecise Probabilities: Theories and Applications,Proceedings of Machine Learning Research, Vol\.290,pp\. 126–136\.External Links:[Link](https://proceedings.mlr.press/v290/detavernier25a.html)Cited by:[§1](https://arxiv.org/html/2609.11366#S1.p2.1),[§6](https://arxiv.org/html/2609.11366#S6.p2.1),[§8](https://arxiv.org/html/2609.11366#S8.p2.1)\.
- Detavernier and De Bock \(2026\)A\. Detavernier and J\. De BockRobustness quantification and uncertainty quantification: comparing two methods for assessing the reliability of classifier predictions\.Note:[arXiv:2603\.22988](https://arxiv.org/abs/2603.22988)External Links:2603\.22988Cited by:[§8](https://arxiv.org/html/2609.11366#S8.p2.1),[§8](https://arxiv.org/html/2609.11366#S8.p3.1)\.
- Gibbs and Su \(2002\)A\. L\. Gibbs and F\. E\. SuOn choosing and bounding probability metrics\.International Statistical Review / Revue Internationale de Statistique70\(3\),pp\. 419–435\.External Links:[Link](http://www.jstor.org/stable/1403865)Cited by:[§6](https://arxiv.org/html/2609.11366#S6.p1.1)\.
- Grinsztajnet al\.\(2022\)L\. Grinsztajn, E\. Oyallon, and G\. VaroquauxWhy do tree\-based models still outperform deep learning on typical tabular data?\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 507–520\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2022/file/0378c7692da36807bdec87ab043cdadc-Paper-Datasets_and_Benchmarks.pdf)Cited by:[§5](https://arxiv.org/html/2609.11366#S5.p1.1)\.
- Hüllermeier and Waegeman \(2021\)E\. Hüllermeier and W\. WaegemanAleatoric and epistemic uncertainty in machine learning: an introduction to concepts and methods\.Machine learning110\(3\),pp\. 457–506\.External Links:[Document](https://dx.doi.org/10.1007/s10994-021-05946-3)Cited by:[Appendix C](https://arxiv.org/html/2609.11366#A3.p2.1)\.
- \[15\]M\. Kelly, R\. Longjohn, and K\. NottinghamThe UCI Machine Learning Repository\.External Links:[Link](https://archive.ics.uci.edu/)Cited by:[Appendix B](https://arxiv.org/html/2609.11366#A2.p1.1)\.
- Mobinyet al\.\(2021\)A\. Mobiny, P\. Yuan, S\. K\. Moulik, N\. Garg, C\. C\. Wu, and H\. Van NguyenDropConnect is effective in modeling uncertainty of bayesian deep networks\.Scientific Reports11\(1\)\.External Links:[Document](https://dx.doi.org/10.1038/s41598-021-84854-x)Cited by:[Appendix C](https://arxiv.org/html/2609.11366#A3.p2.1)\.
- Shaker and Hüllermeier \(2020\)M\. H\. Shaker and E\. HüllermeierAleatoric and epistemic uncertainty with random forests\.InAdvances in Intelligent Data Analysis XVIII,pp\. 444–456\.External Links:ISBN 9783030445843,[Document](https://dx.doi.org/10.1007/978-3-030-44584-3%5F35)Cited by:[Appendix C](https://arxiv.org/html/2609.11366#A3.p2.1)\.
- Troffaes \(2007\)M\. C\.M\. TroffaesDecision making under uncertainty using imprecise probabilities\.International Journal of Approximate Reasoning45\(1\),pp\. 17–29\.External Links:ISSN 0888\-613X,[Document](https://dx.doi.org/10.1016/j.ijar.2006.06.001)Cited by:[footnote 2](https://arxiv.org/html/2609.11366#footnote2)\.
- Zaffalon \(2002\)M\. ZaffalonThe naive credal classifier\.Journal of Statistical Planning and Inference105\(1\),pp\. 5–21\.External Links:[Document](https://dx.doi.org/10.1016/S0378-3758%2801%2900201-4)Cited by:[§4](https://arxiv.org/html/2609.11366#S4.p1.2)\.

## Appendix AComputing Lower Expectations for GeFs

In the paper we consider perturbations𝒲vδ\\mathcal\{W\}\_\{v\}^\{\\delta\}of the weightswvw\_\{v\}of a sum nodevvin a GeF, where we implicitly assume that they are part of parametrized perturbations𝒲vΔ\\mathcal\{W\}\_\{v\}^\{\\Delta\}, withδ\\deltataking values inΔ\\Delta\. For notational convenience, in the following result we will simply consider any perturbation𝒲v\\mathcal\{W\}\_\{v\}of the weights of a sum nodevv\. For the sake of generality, we also consider a general perturbation𝒲r\\mathcal\{W\}\_\{r\}ofwrw\_\{r\}for the root noderrof the GeF, rather than consider the trivial case𝒲r=\{wr\}\\mathcal\{W\}\_\{r\}=\\\{w\_\{r\}\\\}as in the paper\. We collect all possible combinations of perturbations of the weights of the sum nodes in the tree rooted atvvin𝒲¯v≔𝒲v××u∈sde⁡\(v\)𝒲u\\overline\{\\mathcal\{W\}\}\_\{v\}\\coloneq\\mathcal\{W\}\_\{v\}\\times\\bigtimes\_\{u\\in\\mathrm\{sde\}\(v\)\}\\mathcal\{W\}\_\{u\}, and we denote the corresponding perturbation of the joint mass functionpw¯vp\_\{\\overline\{w\}\_\{v\}\}by𝒫𝒲¯v\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}\.

###### Theorem 8\.

Consider a GeF rooted at a noderrwith for each sum nodevva weight vectorwvw\_\{v\}and a perturbation𝒲v\\mathcal\{W\}\_\{v\}ofwvw\_\{v\}\. For any \(not necessarily sum\) nodevv, let𝒫𝒲¯v\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}be the corresponding perturbation ofpw¯vp\_\{\\overline\{w\}\_\{v\}\}\. Then for any functiong:\(𝒞,𝓕\)→ℝg:\(\\mathcal\{C\},\\bm\{\\mathcal\{F\}\}\)\\to\\mathbb\{R\}:

V¯​\(v\)=E¯𝒫𝒲¯v​\(g\),\\underline\{V\}\(v\)=\\underline\{E\}\_\{\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}\}\\left\(g\\right\),\(15\)where, the functionV¯\\underline\{V\}node is defined recursively by

V¯​\(v\)≔\{Epv​\(g\)if​v​is a leaf node,min⁡∑u∈ch⁡\(v\)wv′∈𝒲v⁡wv,u′​V¯​\(u\)if​v​is a sum node\.\\underline\{V\}\(v\)\\coloneq\\begin\{cases\}E\_\{p\_\{v\}\}\(g\)&\\text\{if \}v\\text\{ is a leaf node\},\\\\ \\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}\}\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}\\underline\{V\}\(u\)&\\text\{if \}v\\text\{ is a sum node\}\.\\end\{cases\}\(16\)

For our proof of this result, we took inspiration from the work of[Deratani Mauá et al\. \(2018\)](https://arxiv.org/html/2609.11366#bib.bib4), who define a recursive function on the nodes of a sum\-product network to calculate conditional lower expectations\. Their result is on the one hand more general because it applies to sum\-product networks that are more general than GeFs, but on the other hand less general because it only applies to specific inferences\. Their focus is also on the complexity of computations, whereas our focus is on calculating the lower expectation\.

###### Proof\.

of Theorem[8](https://arxiv.org/html/2609.11366#Thmtheorem8)First, consider the case wherevvis a leaf node\. In this case, the functionV¯​\(v\)\\underline\{V\}\(v\)is given byV¯​\(v\)=Epv​\(g\)\\underline\{V\}\(v\)=E\_\{p\_\{v\}\}\(g\)\. Sincevvis a leaf node, there are no sum nodes in the tree rooted atvvand thus no weights to perturb, so𝒫𝒲¯v=\{pv\}\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}=\\\{p\_\{v\}\\\}\. Hence, the lower expectation ofggover𝒫𝒲¯v\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}is given byE¯𝒫𝒲¯v​\(g\)=minp∈𝒫𝒲¯v⁡Ep​\(g\)=Epv​\(g\)\\underline\{E\}\_\{\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}\}\\left\(g\\right\)=\\min\_\{p\\in\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}\}E\_\{p\}\(g\)=E\_\{p\_\{v\}\}\(g\), as claimed\.

For the case wherevvis a sum node, we prove the claim by induction on the structure of the tree rooted atvv\. Assuming that the claim holds for all children ofvv, we will show that it also holds forvv\. SinceV¯​\(v\)=min⁡∑u∈ch⁡\(v\)wv′∈𝒲v⁡wv,u′​V¯​\(u\),\\underline\{V\}\(v\)=\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}\}\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}\\underline\{V\}\(u\),it follows from the induction hypothesis, that

V¯​\(v\)=min⁡∑u∈ch⁡\(v\)wv′∈𝒲v⁡wv,u′​E¯𝒫𝒲¯u​\(g\)=min⁡∑u∈ch⁡\(v\)wv′∈𝒲v⁡wv,u′​\(minp∈𝒫𝒲¯u⁡Ep​\(g\)\)\.\\underline\{V\}\(v\)=\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}\}\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}\\underline\{E\}\_\{\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{u\}\}\}\\left\(g\\right\)=\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}\}\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}\\left\(\\min\_\{p\\in\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{u\}\}\}E\_\{p\}\\left\(g\\right\)\\right\)\.\(17\)Since each set of weightsw¯u′∈𝒲¯u\\overline\{w\}\_\{u\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{u\}corresponds to an elementpw¯u′p\_\{\\overline\{w\}\_\{u\}\}^\{\\prime\}of𝒫𝒲¯u\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{u\}\}, each minimization inside the sum is equivalent to minimizing over the perturbed sets of weights\. By applying this, and the definition of the expectation, we get

V¯​\(v\)=min⁡∑u∈ch⁡\(v\)wv′∈𝒲v⁡wv,u′​\(min⁡∑\(c,𝒇\)∈𝒞×Fw¯u′∈𝒲¯u⁡pw¯u′​\(c,𝒇\)​g​\(c,𝒇\)\)\.\\underline\{V\}\(v\)=\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}\}\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}\\left\(\\min\_\{\\overline\{w\}\_\{u\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{u\}\}\\sum\_\{\(c,\\bm\{f\}\)\\in\\mathcal\{C\}\\times F\}p\_\{\\overline\{w\}\_\{u\}^\{\\prime\}\}\(c,\\bm\{f\}\)g\(c,\\bm\{f\}\)\\right\)\.\(18\)Since the weights of a sum node are non\-negative, we can take for each of the children ofvvthe minimum out of the sum:

V¯​\(v\)=minwv′∈𝒲v⁡min⁡∑\(c,𝒇\)∈𝒞×F\(u∈ch⁡\(v\)\)​w¯u′∈𝒲¯u⁡\(∑u∈ch⁡\(v\)wv,u′​pw¯v′​\(c,𝒇\)\)​g​\(c,𝒇\)\.\\underline\{V\}\(v\)=\\min\_\{w\_\{v\}^\{\\prime\}\\in\\mathcal\{W\}\_\{v\}\}\\min\_\{\(u\\in\\mathrm\{ch\}\(v\)\)\\overline\{w\}\_\{u\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{u\}\}\\sum\_\{\(c,\\bm\{f\}\)\\in\\mathcal\{C\}\\times F\}\\left\(\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}p\_\{\\overline\{w\}\_\{v\}^\{\\prime\}\}\(c,\\bm\{f\}\)\\right\)g\(c,\\bm\{f\}\)\.\(19\)Since all perturbations of the weights are independent of each other, minimizing over all these perturbations separately is equivalent to minimizing over all perturbed sets of weightsw¯v′∈𝒲¯v\\overline\{w\}\_\{v\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{v\}in the tree rooted atvv\. Hence, we can rewrite the above as

V¯​\(v\)=min⁡∑\(c,𝒇\)∈𝒞×Fw¯v′∈𝒲¯v⁡\(∑u∈ch⁡\(v\)wv,u′​pw¯u​\(c,𝒇\)\)​g​\(c,𝒇\)\.\\underline\{V\}\(v\)=\\min\_\{\\overline\{w\}\_\{v\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{v\}\}\\sum\_\{\(c,\\bm\{f\}\)\\in\\mathcal\{C\}\\times F\}\\left\(\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}p\_\{\\overline\{w\}\_\{u\}\}\(c,\\bm\{f\}\)\\right\)g\(c,\\bm\{f\}\)\.\(20\)Finally, if we use the fact thatpwv′​\(c,𝒇\)=∑u∈ch⁡\(v\)wv,u′​pw¯u′​\(c,𝒇\)p\_\{w\_\{v\}^\{\\prime\}\}\(c,\\bm\{f\}\)=\\sum\_\{u\\in\\mathrm\{ch\}\(v\)\}w\_\{v,u\}^\{\\prime\}p\_\{\\overline\{w\}\_\{u\}^\{\\prime\}\}\(c,\\bm\{f\}\), and reuse similar arguments as before, we can finally rewrite the above as

V¯​\(v\)=min⁡∑\(c,𝒇\)∈𝒞×Fw¯v′∈𝒲¯v⁡pw¯v′​\(c,𝒇\)​g​\(c,𝒇\)=minp∈𝒫𝒲¯v⁡Ep​\(g\)=E¯𝒫𝒲¯v​\(g\),\\underline\{V\}\(v\)=\\min\_\{\\overline\{w\}\_\{v\}^\{\\prime\}\\in\\overline\{\\mathcal\{W\}\}\_\{v\}\}\\sum\_\{\(c,\\bm\{f\}\)\\in\\mathcal\{C\}\\times F\}p\_\{\\overline\{w\}\_\{v\}^\{\\prime\}\}\(c,\\bm\{f\}\)g\(c,\\bm\{f\}\)=\\min\_\{p\\in\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}\}E\_\{p\}\(g\)=\\underline\{E\}\_\{\\mathcal\{P\}\_\{\\overline\{\\mathcal\{W\}\}\_\{v\}\}\}\\left\(g\\right\),\(21\)as claimed\. ∎

## Appendix BAdditional Details on the Experiments

The experiments we presented in Section[7](https://arxiv.org/html/2609.11366#S7)were conducted on several datasets from the UCI Machine Learning Repository\([Kelly et al\.,](https://arxiv.org/html/2609.11366#bib.bib8)\)\. The datasets we used are shown in tab:datasets\. Next we give some details on how we cleaned these datasets and adapted the tasks to fit our setting\. First, we removed all continuous features from the datasets, because we focus on discrete features in this work\. Then we removed all instances with missing values from the datasets\. For some of the datasets, we performed more specific cleaning\. For the Solar Flare datasets and the Student Performance datasets, we adapted the task to one that leans more toward standard classification\. The former datasets are originally about predicting the number of solar flares that occur, and this for three types of flares; we made this classification task binary, with the aim to predict whether a solar flare occurs \(of any type\) or not\. For the Student Performance datasets, the original task is to predict the grade of a student, but we adapted this to a binary classification task as well, where we predict whether the student passes or fails\.

Table 5:Details of the datasets used in the experiments\.The training procedure for the models is as follows\. Unless the dataset comes with a predefined split, we split the datasets into a training and test set, where the test set is 40% of the whole dataset, and the size of the test set is maxed out at 500 instances\. The NBC is trained by first optimizing a smoothing parameter with 5\-fold cross\-validation on the training set and then training the model on the whole training set with this smoothing parameter\. For the details on how the GeFs are trained, we refer to the original paper of[Correia et al\. \(2020b\)](https://arxiv.org/html/2609.11366#bib.bib7), where we choose to combine 25 GeDTs and where the distributions of the leaf nodes are learned using the maximum likelihood principle\. The whole training procedure, including the splitting of the datasets, is repeated 10 times to reduce the effect of randomness on the results\. The ARCs are then calculated for each of the 10 runs and averaged out\.

## Appendix CUncertainty Quantification Metrics

Another approach to assess the trustworthiness of a prediction is to try to quantify the uncertainty of the prediction, where \(unlike for robustness\) a higher uncertainty corresponds to a less trustworthy prediction\.

In our experiments, we compare our robustness values with six commonly used uncertainty quantification measures\. The three straightforward measures are one minus the \(conditional\) predicted probability of the predicted class, denoted asumu\_\{\\mathrm\{m\}\}, the entropy of the predicted \(conditional\) distribution over the classes, denoted asuHu\_\{\\mathrm\{H\}\}, and the margin of confidence being the difference between the highest and second highest predicted \(conditional\) probabilities, denoted asucu\_\{\\mathrm\{c\}\}\. Besides these, we also use some more complex measures that are based on the information\-theoretic decomposition of uncertainty as is explained in the work of[Hüllermeier and Waegeman \(2021\)](https://arxiv.org/html/2609.11366#bib.bib12)\. To estimate these, an ensemble of 10 models is trained on a bootstrap sample of the training set of the same size as the original training set\([Depeweg et al\., 2018](https://arxiv.org/html/2609.11366#bib.bib16);[Mobiny et al\., 2021](https://arxiv.org/html/2609.11366#bib.bib15);[Shaker and Hüllermeier, 2020](https://arxiv.org/html/2609.11366#bib.bib17)\)\. The so\-called the*total uncertainty*utu\_\{\\mathrm\{t\}\}is estimated as the entropy of the average predicted \(conditional\) distribution over all models,*aleatoric uncertainty*uau\_\{\\mathrm\{a\}\}is then estimated as the average entropy of the predicted \(conditional\) distributions over all models and the*epistemic uncertainty*ueu\_\{\\mathrm\{e\}\}is estimated as the difference between the total and aleatoric uncertainty\.

For these uncertainty measures, the corresponding ARCs in our experiments are obtained by first rejecting instances with the highest uncertainty\.