On the computational complexity of the interval dependence problem in credal networks

Tools

de Angelis, Marco and Estrada-Lugo, Hector Diego and Ferson, Scott and Patelli, Edoardo; Potapov, Igor and Chumachenko, Dmytro and Proshkin, Volodymyr and Shendryk, Vira and Berezko, Oleksandr and McCafferty, James and Konovalov, Olexandr, eds. (2025) On the computational complexity of the interval dependence problem in credal networks. In: Digitalisation and Digital Transformation. Communications in Computer and Information Science (1). Springer Nature Switzerland AG, 113–118. ISBN 978-3-032-04731-1 (https://doi.org/10.1007/978-3-032-04731-1_15)

[thumbnail of de-Angelis-etal-2025-On-the-computational-complexity-of-the-interval-dependence-problem-in-credal-networks]
Preview
 Text. Filename: de-Angelis-etal-2025-On-the-computational-complexity-of-the-interval-dependence-problem-in-credal-networks.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo
Download (371kB)| Preview

Abstract

Credal networks are Bayesian networks with interval conditional probability tables CPTs. Even though algorithms that trade complexity in exchange for approximation have been developed to compute with credal networks in applications, the complexity of the interval dependence problem is still not very well understood. We investigate such computational complexity on the variable elimination algorithm on small-sized two-state credal networks by means of computer arithmetic. Automatic differentiation is coupled to interval arithmetic in a strategic attempt to isolate monotonic trends for a particular inferential or diagnostic query. The projection of interval uncertainty through the partial derivatives with respect to the parameters proves instrumental to reduce the dimensionality of the dependency problem. In fact, the parameters that are monotonic with respect to a particular query can then be collapsed to a singleton reducing the number of intervals to be propagated to yield the tightest bounds. The dependency problem of interval computation has at worst exponential complexity, so reducing the size of this problem can be vital to compute with credal networks. The considerations drawn in this work on a small network, can be readily generalised to larger networks, whilst the qualitative account of the parameter space can be utilised to build more elaborated algorithms.

ORCID iDs

de Angelis, Marco ORCID logoORCID: https://orcid.org/0000-0001-8851-023X, Estrada-Lugo, Hector Diego, Ferson, Scott and Patelli, Edoardo ORCID logoORCID: https://orcid.org/0000-0002-5007-7247; Potapov, Igor, Chumachenko, Dmytro, Proshkin, Volodymyr, Shendryk, Vira, Berezko, Oleksandr, McCafferty, James and Konovalov, Olexandr
CORE (COnnecting REpositories)