Towards conservative inference in credal networks using belief functions: the case of credal chains
Marco Sangalli, Thomas Krak, Cassio De Campos · 2025
Read Towards conservative inference in credal networks using belief functions: the case of credal chains by Marco Sangalli, Thomas Krak, Cassio De Campos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07619.txt.
Introduction
Marco Sangalli, Thomas Krak, and Cassio de Campos worked on careful inference in credal networks in 2025. Credal networks are probability graphs that allow ranges of values instead of single numbers, a way to own up to uncertainty. Belief functions from Dempster-Shafer theory offer another language for such ranges.
The team built a framework that pushes belief through the simplest such networks, chains. The method hands back safe intervals, bounded by belief and plausibility, while staying fast. Formal definitions ground the approach. Tests compare it against classical sensitivity analysis and show where belief inference wins and where it strains. The authors aim the lessons at credal networks beyond chains.
Catalog record
| CREATOR | Marco Sangalli, Thomas Krak, Cassio De Campos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-07619
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards conservative inference in credal networks using belief functions: the case of credal chains Marco Sangalli, Thomas Krak, Cassio De Campos Abstract This paper explores belief inference in credal networks using Dempster-Shafer theory. By building on previous work, we propose a novel framework for propagating uncertainty through a subclass of credal networks, namely chains. The proposed approach efficiently yields conservative intervals through belief and plausibility functions, combining computational speed with robust uncertainty representation. Key contributions include formalizing belief-based inference methods and comparing belief-based inference against classical sensitivity analysis. Numerical results highlight the advantages and limitations of applying belief inference within this framework, providing insights into its practical utility for chains and for credal networks in general. keywords Credal networks, belief functions, Dempster-Shafer theory, approximate inference 1 Introduction Bayesian networks (BNs), as probabilistic graphical models, provide a powerful framework for modelling probabilistic relationships among variables. Credal networks (CNs) generalize BNs by allowing for partially specified probabilistic information. It is well-known that inference in both BNs and CNs is in general computationally hard [ 9 , 3 ] . We consider the problem of computing inferences in CNs under complete independence [ 9 , 4 ] . There are, broadly speaking, two ways by which we might approach this problem. We might either try to identify specific inference problems and/or graph topologies that circumvent the hardness results; or, we can try to develop approximate methods. The first path is arguably difficult, since NP-hardness was already established for marginal inference on relatively simple graph structures like polytrees [ 2 ] and even trees with evidence [ 8 ] . Here we consider the second approach. In particular, we investigate the merit in leveraging the existing machinery from the theory of belief functions, also known as Dempster-Shafer (D-S) theory [ 6 , 12 ] , to approximately compute inferences for a given CN under complete independence. At first glance, this has several upsides. For one, we can fully use the existing computational and algorithmic tools from that theory, which has recently been investigated specifically in the context of Bayesian networks generalized to belief functions [ 13 ] , where the computational complexity of BN inferences is largely reduced. Moreover, a recent result [ 10 ] essentially implies that the global model that we obtain from this is guaranteed to be a conservative bound on the CN in which we are actually interested (even though this result does not hold for marginals, as we will see later). We work with the subcase of CNs that have the structure of a chain. We require that local models in the CN can be translated (possibly by conservative approximation) to belief functions. These choices are enough to unveil a number of facts about the idea of using D-S theory in inferences for CNs. We investigate different ways in which local models can be made into belief functions. In particular, we are interested in the quality of this approach; i.e. we would like to know (and reduce) how much information is lost with respect to the exact inference in the CN chains in which the local uncertainty models are specified using probability intervals. Since exact inference in such CNs is computationally tractable, we are able to directly compare these methods from D-S theory to the gold standard of the underlying model of interest and to reach conclusions about the quality of the approximations in chains and beyond. Despite optimizations that generate tighter bounds than the direct application of D-S theory, we conclude that—outside specific settings—such belief-based inference often generates too wide intervals to be a practically suitable approximation for the CN inferences of interest. 2 Preliminaries This section introduces the basic concepts of credal networks [ 1 ] , Dempster-Shafer theory [ 5 , 12 ] of belief functions, and other required concepts for this paper. 2.1 Bayesian and credal networks A Bayesian network (BN) is a probabilistic graphical model where a directed acyclic graph (DAG) encodes probabilistic relationships between random variables. Each node represents a variable, and edges indicate conditional dependencies. Credal networks (CNs) extend BNs by addressing uncertainty in probability specifications. Instead of fixed point estimates, CNs utilize sets of probability distributions (credal sets), allowing representation of multiple compatible probabilistic models. This approach provides a more comprehensive framework for reasoning under incomplete or ambiguous information, capturing broader uncertainty in probabilistic modelling through credal sets rather than single distributions. A basic example of a CN is one with the DAG structure A\to B , where A:\Omega\to E_{A} and B:\Omega\to E_{B} are two discrete random variables, E_{A}:=\{a_{1},\dots,a_{n}\} , E_{B}:=\{b_{1},\dots,b_{m}\} , and whose credal sets are specified using collections of intervals: \displaystyle\underline{p}^{A}_{i}\leq\mathbb{P}(A=a_{i})\leq\overline{p}^{A}_{i},\quad\underline{p}^{i}_{j}\leq\mathbb{P}(B=b_{j}|A=a_{i})\leq\overline{p}^{i}_{j}. Throughout, we consider CNs under complete independence [ 9 , 4 ] , which essentially means that the joint model that we consider can be expressed as the set of all BNs whose local models— \mathbb{P}(A) and \mathbb{P}(B|A) in this example—are compatible with these credal sets. Solving an inference problem for such a CN amounts to computing (tight) lower and upper bounds on some probabilistic quantity with respect to all the BNs in this set. For instance, in this example we may want to compute lower and upper bounds for \mathbb{P}(B=b_{j}) , which are given by \displaystyle\underline{\mathbb{P}}(B=b_{j}):=\min_{\mathbb{P}\in\text{CN}}\sum_{i=1}^{n}\mathbb{P}(B=b_{j}|A=a_{i})\mathbb{P}(A=a_{i}),\text{ and} \displaystyle\overline{\mathbb{P}}(B=b_{j}):=\max_{\mathbb{P}\in\text{CN}}\sum_{i=1}^{n}\mathbb{P}(B=b_{j}|A=a_{i})\mathbb{P}(A=a_{i}). In a chain X_{1}\to\dots\to X_{k} we may do something similar to infer bounds on \mathbb{P}(X_{k}=\tilde{x}) , using \displaystyle\underline{\mathbb{P}}(X_{k}=\tilde{x}):=\min_{\mathbb{P}\in\text{CN}}\sum_{x_{1},\dots,x_{k-1}}\mathbb{P}(x_{1})\mathbb{P}(x_{2}|x_{1})\dots\mathbb{P}(\tilde{x}|x_{k-1}), \displaystyle\overline{\mathbb{P}}(X_{k}=\tilde{x}):=\max_{\mathbb{P}\in\text{CN}}\sum_{x_{1},\dots,x_{k-1}}\mathbb{P}(x_{1})\mathbb{P}(x_{2}|x_{1})\dots\mathbb{P}(\tilde{x}|x_{k-1}), where the minimization and maximization are understood to be taken with respect to all the combinations of the local models specified in the CN. 2.2 Mass functions and belief functions Let (E,2^{E}) be a discrete measurable space, where 2^{E} represents the power set of E . A mass function [ 7 , 13 ] (also called basic probability assignment) m on E is a function m:2^{E}\to[0,1] such that • m(\emptyset)=0 • \sum\limits_{V\in 2^{E}}m(V)=1 . Each set V such that m(V)>0 is called a focal set of m . If the only focal set of m is E , the mass function is said to be vacuous . Meanwhile, if the only set with mass is not the whole space, m is said to be deterministic . If m gives masses only to singletons, it is said to be Bayesian ; there exists a 1-1 correspondence between Bayesian basic probability assignments and discrete probability distributions. Given a mass function m on E , its associated belief function Bel_{m}:2^{E}\to[0,1] is defined as Bel_{m}(W):=\sum\limits_{V\subseteq W}m(V)\>\text{ for all }W\in 2^{E}. (1) The plausibility function Pl_{m}:2^{E}\to[0,1] associated to the mass function m is defined as Pl_{m}(W):=\sum\limits_{V\cap W\neq\emptyset}m(V)\>\text{ for all }W\in 2^{E}. (2) These functions satisfy the conjugacy relation Pl_{m}(W)=1-Bel_{m}(E\smallsetminus W)\>\text{ for all $W\in 2^{E}$.} Operations with mass functions There are three important operations from D-S theory that we will use in this work: marginalization, vacuous extension, and Dempster’s rule of combination. Let (E,2^{E}) and (F,2^{F}) be two measurable spaces and consider Y\subseteq E\times F . We define the projection of Y on E as Y^{\downarrow E}:=\{e\in E:(e,f)\in Y\}\,. Let m be a mass function on E\times F . The marginalization of m to E is a mass function m^{\downarrow E} on E defined as [ 13 ] m^{\downarrow E}(V):=\sum_{\begin{subarray}{c}Y\subseteq E\times F\\ Y^{\downarrow E}=V\end{subarray}}m(Y)\quad\text{for all $V\in 2^{E}$}. (3) Let now m be a mass function on