Standard probability theory requires machine learning models to express their beliefs as precise, single-point probabilities. When a standard image classifier encounters an ambiguous image—say, a hybrid creature that looks 50% like a cat and 50% like a dog—it outputs a softmax vector of $[0.5, 0.5]$.
However, consider a second scenario: the model is shown a completely blank image, or an image from a data distribution it has never seen before. Because the softmax layer must normalize to 1, the model will often output $[0.5, 0.5]$ once again.
This reveals a fundamental flaw in precise probability models: they conflate aleatoric uncertainty (inherent randomness) with epistemic uncertainty (a lack of knowledge). There is a profound difference between knowing that an event has a 50% chance of occurring and having absolutely no data to form a prediction. As noted by de Campos et al. in the proceedings of ISIPTA 2019, forcing a model to commit to a single precise distribution makes it dangerously overconfident in scenarios with scarce or vague information.
To solve this, a growing body of research replaces single-point probability estimates with credal sets—convex sets of possible probability distributions. By moving from points to intervals, models can explicitly say, "I do not know."
The Core Mechanism: Credal Sets and Interval Width
Instead of representing a prediction as a single probability distribution $P$, an imprecise probability framework models predictions using a credal set $\mathcal{P}$. For any given event $A$, the model does not output a single number; instead, it bounds the event within a lower probability $\underline{P}(A)$ and an upper probability $\bar{P}(A)$:
$$\underline{P}(A) = \inf_{P \in \mathcal{P}} P(A), \quad \bar{P}(A) = \sup_{P \in \mathcal{P}} P(A)$$
This simple shift completely changes how uncertainty is interpreted:
- The Location of the Interval captures aleatoric uncertainty. If a coin is known to be fair, its interval collapses to a single point: $[0.5, 0.5]$.
- The Width of the Interval ($\bar{P}(A) - \underline{P}(A)$) directly quantifies epistemic uncertainty. If we have never seen the coin before, the credal set contains all possible distributions, yielding an interval of $[0, 1]$. The width is $1.0$, signaling total ignorance.
Hüllermeier et al. demonstrate that tracking this interval width allows models to perform "selective classification"—safely refraining from making a prediction when the epistemic uncertainty exceeds a critical threshold.
Mathematical Foundations and Inferential Complexity
Transitioning from precise points to sets of measures requires redefining the core operations of probabilistic reasoning. For instance, standard Bayesian conditioning cannot simply be applied to a set; instead, updating must happen axiomatically across the entire set of measures. Grove et al. established the foundational postulates required to update sets of probabilities consistently without losing the structural nuances of the underlying ambiguity.
When these concepts are extended to structured graphical models, traditional Bayesian networks evolve into Credal Networks. However, this representational flexibility introduces a significant computational trade-off.
Standard Bayesian Network Credal Network
[Node A: P(A)=0.7] [Node A: P(A) ∈ [0.6, 0.8]]
│ │
▼ ▼
[Node B: P(B|A)] [Node B: P(B|A) ∈ [0.1, 0.4]]
(Exact Polynomial Inference) (Optimization over Convex Hulls)
As de Campos et al. proved, moving from precise probabilities to interval-valued credal sets shifts the computational complexity "one step up" the polynomial hierarchy. Inference tasks like the maximin a posteriori (MmAP) problem become $\Sigma^P_2$-complete, even on simple graph structures like polytrees. Mauá et al. further demonstrated that the exact tractability of these networks depends heavily on how "independence" is defined across the sets, often making exact updates NP-hard and necessitating local propagation approximations.
Scaling to Deep Learning: Ensembles and Random Sets
To leverage these theoretical benefits in modern AI, researchers have developed architectures capable of outputting credal representations at scale.
Credal Deep Ensembles
Standard deep ensembles average the softmax outputs of multiple neural networks to produce a single point estimate. Wang et al. instead use the individual networks in an ensemble to define the boundaries of a convex credal set. By pairing the ensemble with robust optimization, their Credal Deep Ensembles (CreDEs) output tight lower and upper class probabilities, significantly improving out-of-distribution (OOD) detection.
Random-Set Neural Networks
Rather than predicting standard class probabilities, Random-Set Neural Networks (RS-NNs), introduced by Manchingal et al., predict Dempster-Shafer "belief functions" over sets of classes. The gap between the upper and lower bounds acts as an explicit indicator of model ignorance, providing substantial robustness against adversarial attacks.
Credal Bayesian Deep Learning
Bayesian Neural Networks (BNNs) traditionally place a single, fixed prior distribution over their weights. However, choosing this prior is often arbitrary. Caprio et al. resolved this by replacing single priors with a credal set of priors. This allows the network to behave like an infinite ensemble of BNNs, capturing prior model ambiguity directly.
Cautious Learning and Generalization Guarantees
Representing uncertainty via sets does more than just improve inference; it fundamentally alters how models learn.
In self-supervised and semi-supervised learning, models generate "pseudo-labels" for unlabeled data and then train on their own predictions. This often leads to confirmation bias, where a model reinforces its own overconfident mistakes. Lienen et al. and Hüllermeier et al. mitigate this by introducing cautious learning frameworks. When a model encounters an ambiguous sample, it assigns a set-valued pseudo-label (e.g., "this sample belongs to {Cat, Dog}"). This prevents the model from committing to an unfounded, precise class early in the training loop.
Self-Training Frameworks:
Standard Self-Training:
Model Ambigous Input ──> Overconfident Pseudo-label (Cat) ──> Reinforces Error (Confirmation Bias)
Conformal Credal Self-Supervised Learning:
Model Ambigous Input ──> Cautious Set Label ({Cat, Dog}) ──> Preserves Ignorance Safely
Finally, credal representations provide rigorous statistical safeguards. By combining imprecise probabilities with conformal prediction, Huang et al. developed a method to distill large cloud-based models into smaller edge models while guaranteeing that the edge model's credal intervals bound the true risk within a user-defined confidence level.
On the theoretical front, Shariatmadar et al. introduced Credal Learning Theory, proving that generalization bounds derived from a convex set of candidate distributions remain mathematically valid even under severe domain drift. By modeling the data-generating process as an imprecise set, the math inherently accounts for the environment changing over time.