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

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.