Upper Entropy for 2-Monotone Lower Probabilities

Tuan-Anh Vu; Sébastien Destercke; Frédéric Pichon

cs.LGMar 23, 2026

Upper Entropy for 2-Monotone Lower Probabilities

Authors: Tuan-Anh Vu, Sébastien Destercke, Frédéric Pichon

Organizations: UMR CNRS 7253 Heudiasyc, Université de Technologie de Compiègne, France · Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), Université d’Artois, UR 3926, France

Abstract

Uncertainty quantification is a key aspect in many tasks such as model selection/regularization, or quantifying prediction uncertainties to perform active learning or OOD detection. Within credal approaches that consider modeling uncertainty as probability sets, upper entropy plays a central role as an uncertainty measure. This paper is devoted to the computational aspect of upper entropies, providing an exhaustive algorithmic and complexity analysis of the problem. In particular, we show that the problem has a strongly polynomial solution, and propose many significant improvements over past algorithms proposed for 2-monotone lower probabilities and their specific cases.

Figures & tables

Panel of Figure 1 — Figure 1: Flow network in Example 2 .

Panel of Figure 2 — Figure 2: Illustration of Example 3

Figure 3: Plot of

f(x)

with

[l_{1},u_{1}]=[0.1,0.4],[l_{2},u_{2}]=[0.4,0.5]

and

[l_{3},u_{3}]=[0.2,0.6]

$f$	$\|\Omega\|$	Create $p^{0}$	Resolution
$x^{2}$	5000	$0.284\pm 0.006$	$0.013\pm 0.001$
	10000	$1.035\pm 0.018$	$0.024\pm 0.001$
	20000	$3.961\pm 0.072$	$0.206\pm 0.027$
$1-\sqrt{1-x}$	5000	$0.307\pm 0.003$	$0.009\pm 0.001$
	10000	$1.149\pm 0.016$	$0.017\pm 0.001$
	20000	$4.333\pm 0.014$	$0.147\pm 0.014$

Table 1: Initial point construction and resolution times (s).

$f$	Create $p^{0}$	Resolution
$x^{2}$	$0.010\pm 0.001$	$6.327\pm 0.291$
$1-\sqrt{1-x}$	$0.012\pm 0.001$	$4.326\pm 0.088$
$\frac{\mathrm{e}^{2x}-1}{\mathrm{e}^{2}-1}$	$0.019\pm 0.001$	$3.617\pm 0.074$

Table 2: Initial point construction and resolution times (s) for

|\Omega|=5\times 10^{5}

with the surrogate.

$\mathrm{margin}$	$\|\Omega\|$	Algorithm 4	Abellán & Moral
$0.1$	$10^{7}$	$0.305\pm 0.002$	$12.906\pm 0.036$
$0.1$	$10^{8}$	$3.133\pm 0.042$	$15.699\pm 0.144$
$0.2$	$10^{7}$	$0.265\pm 0.003$	$19.375\pm 0.047$
$0.2$	$10^{8}$	$2.729\pm 0.037$	$19.589\pm 0.245$
$0.3$	$10^{7}$	$0.281\pm 0.015$	$25.054\pm 0.060$
$0.3$	$10^{8}$	$2.843\pm 0.147$	$27.069\pm 0.179$

Table 3: Runtimes (s) of Algorithm 4 vs. Abellán & Moral

Imprecise Probability

See all 9 papers

Quantification of Credal Uncertainty: A Distance-Based Approach
Mar 28, 2026Xabier Gonzalez-Garcia, Siu Lun Chau, Julian Rodemann +6Uncertainty Quantification Aleatoric Uncertainty
Dept. of Statistics, CS & Mathematics, Public Univ. of Navarre · EPIC Lab, Nanyang Technological Univ. Singapore · Rational Intelligence Lab, CISPA Helmholtz Center for Information Security +7
On the QUEST for Uncertainty Quantification via Highest Density Regions
Jun 17, 2026Sam Goring, Tom Kuipers, Nicola Paoletti +1Uncertainty Quantification Aleatoric Uncertainty
King’s College London · Northeastern University London
Tight Sample Bounds for Renyi and Min-Entropy Estimation
Jul 18, 2026Arman Adibi, Piotr KrystaSample Complexity Information-Theoretic Lower Bounds
Department of Computer Science

Mar 28, 2026J/K move · Enter open · S save

Quantification of Credal Uncertainty: A Distance-Based Approach

Xabier Gonzalez-Garcia, Siu Lun Chau, Julian Rodemann, Michele Caprio+5

Dept. of Statistics, CS & Mathematics, Public Univ. of Navarre · EPIC Lab, Nanyang Technological Univ. Singapore · Rational Intelligence Lab, CISPA Helmholtz Center for Information Security+7

Uncertainty Quantification Aleatoric Uncertainty Integral Probability Metrics Uncertainty Decomposition Epistemic Uncertainty

Open paper AskPDF arXiv

Credal sets, i.e., closed convex sets of probability measures, provide a natural framework to represent aleatoric and epistemic uncertainty in machine learning. Yet how to quantify these two types of uncertainty for a given credal set, particularly in multiclass classification, remains underexplored. In this paper, we propose a distance-based approach to quantify total, aleatoric, and epistemic uncertainty for credal sets. Concretely, we introduce a family of such measures within the framework of Integral Probability Metrics (IPMs). The resulting quantities admit clear semantic interpretations, satisfy natural theoretical desiderata, and remain computationally tractable for common choices of IPMs. We instantiate the framework with the total variation distance and obtain simple, efficient uncertainty measures for multiclass classification. In the binary case, this choice recovers established uncertainty measures, for which a principled multiclass generalization has so far been missing. Empirical results confirm practical usefulness, with favorable performance at low computational cost.

Abstract

Imprecise Probability

Explore similar work

Quantification of Credal Uncertainty: A Distance-Based Approach

On the QUEST for Uncertainty Quantification via Highest Density Regions

Tight Sample Bounds for Renyi and Min-Entropy Estimation