# Uncertainty-Aware Partial-Label Learning

Tobias Fuchs  Florian Kalinke  Klemens Böhm

###### Abstract

In real-world applications, one often encounters ambiguously labeled data,
where different annotators assign conflicting class labels. Partial-label
learning allows training classifiers in this weakly supervised setting. While
state-of-the-art methods already feature good predictive performance, they
often suffer from miscalibrated uncertainty estimates. However, having well-
calibrated uncertainty estimates is important, especially in safety-critical
domains like medicine and autonomous driving. In this article, we propose a
novel nearest-neighbor-based partial-label-learning algorithm that leverages
Dempster-Shafer theory. Extensive experiments on artificial and real-world
datasets show that the proposed method provides a well-calibrated uncertainty
estimate and achieves competitive prediction performance. Additionally, we
prove that our algorithm is risk-consistent.

Weakly supervised learning, Partial-label learning, Uncertainty, Dempster-
Shafer theory

##  1 Introduction

Real-world data is often noisy, for example, human annotators might assign
different class labels to the same instance. Accordingly, training instances
can have multiple labels, known as candidates, of which only one is correct.
While in some cases it is possible to sanitize such data, cleaning is costly.
Instead, one wants to predict the class labels of unseen instances having sets
of candidates only, that is, without knowing the exact ground-truth labels of
the training data. Partial-label learning algorithms allow handling such
ambiguously labeled data (Hüllermeier & Beringer, 2005; Cour et al., 2011; Liu
& Dietterich, 2012; Zhang & Yu, 2015). These algorithms are a special case of
weakly supervised methods.

Quantifying uncertainty is crucial when predictions of machine-learning
algorithms impact actions or decisions. Consider, for example, safety-critical
domains such as the classification of medical images (Yang et al., 2009;
Lambrou et al., 2011; Senge et al., 2014; Kendall & Gal, 2017; Reamaroon et
al., 2019) or the control of self-driving cars (Xu et al., 2014; Varshney &
Alemzadeh, 2017; Hubmann et al., 2017; Shafaei et al., 2018; Michelmore et
al., 2020).

One option to discuss the (un)certainty of individual predictions is to have
the algorithm also output their respective confidences. This can either be a
value in a bounded interval indicating _how_ confident the algorithm is, or a
binary output indicating _if_ it is confident. In this work, we focus on the
latter, employing a binary notion of confidence. The more predictions that are
labeled confident are indeed correct, the better the calibration is. In other
words, the confidences are well-calibrated if almost all predictions that are
labeled as confident are also correct. This induces a trade-off between the
number and accuracy of confident predictions. In supervised classification,
calibration is often performed by post-hoc methods (Guo et al., 2017; Ao et
al., 2023). However, in the present setting, these methods are not applicable
as ground-truth is only partially available.

Further, in partial-label learning, quantifying confidence is highly non-
trivial as the uncertainty originates from multiple sources (Hora, 1996). On
the one hand, there is inherent uncertainty due to ambiguously labeled data
(_aleatoric uncertainty_). This ambiguity is influenced by both instances and
classes: In some regions of the instance space, annotators are more likely to
mislabel instances than in others. Additionally, some class labels are
inherently more similar than others. On the other hand, there is uncertainty
due to the lack of knowledge regarding the relevance of each candidate label
(_epistemic uncertainty_). Optimally, an algorithm does not mix both.

In fact, Fisher (1930, 1935) already notes that “not knowing the chance of
mutually exclusive events [epistemic uncertainty] and knowing the chance to be
equal [aleatoric uncertainty] are two quite different states of knowledge.”
One can reduce epistemic uncertainty with more data or better models;
aleatoric uncertainty is irreducible (Meyerowitz et al., 1994; Harmanec et
al., 1996; Klir & Wierman, 1999; Abellán et al., 2006; Sale et al., 2023;
Wimmer et al., 2023). To our knowledge, existing partial-label learning
approaches, for example, (Hüllermeier & Beringer, 2005; Liu & Dietterich,
2012; Zhang & Yu, 2015; Ni et al., 2021), model label information using
standard probability, which does not allow to discern aleatoric and epistemic
uncertainty.

We propose a partial-label learning approach based on Dempster-Shafer theory
that keeps both uncertainties separate and is well-calibrated. Our method
provides a significantly better trade-off of the number and accuracy of
confident predictions when compared to the state-of-the-art.

Contributions. We summarize our contributions as follows.

  * •

We introduce Dst-Pll, a novel partial-label learning algorithm that learns
from ambiguously labeled data. The algorithm effectively determines whether a
prediction is confident; its uncertainty is well-calibrated.

  * •

Extensive experiments on artificial and real-world data support our claims.
The experiments also show that our approach has a significantly lower runtime
than competitors while achieving competitive prediction quality. We make our
code and data openly available.111https://github.com/anon1248/uncertainty-
aware-pll.

  * •

We analyze Dst-Pll, give a closed-form expression of its expected decision
boundary, and prove its infinite-sample risk consistency. We believe these are
of independent interest. The runtime analysis shows that the proposed method
is dominated by $k$ nearest-neighbor search, which has an average time
complexity of $\mathcal{O}\\!\left(dk\log n\right)$ with $d$ denoting the
number of features and $n$ the number of training instances.

Structure of the paper. We define the problem in Section 2, Section 3 reviews
Dempster-Shafer theory and Section 4 discusses related work. We propose our
method in Section 5, Section 6 features experiments and Section 7 concludes.
All proofs and additional experiments are in the appendices.

##  2 Partial-Label Learning

Partial-label learning (PLL) targets classification in a general setting.
Rather than having only one label per training instance, data can be annotated
with multiple candidate labels, of which only one is correct.

######  Definition 2.1 (Partial-Label Learning).

Let $\operatorname{\mathcal{X}}=\mathbb{R}^{d}$ denote a $d$-dimensional real-
valued feature space and
$\operatorname{\mathcal{Y}}=\left[l\right]:=\left\\{1,\dots,l\right\\}$ the
finite set of $3\leq l\in\mathbb{N}$ classes. A training dataset
$\mathcal{D}=\left\\{\left(x_{i},s_{i}\right)\mid i\in\left[n\right]\right\\}$
of $n$ instances contains feature vectors $x_{i}\in\operatorname{\mathcal{X}}$
and a set of candidate labels $s_{i}\subseteq\operatorname{\mathcal{Y}}$ for
each $i\in\left[n\right]$. All instances $i$ have an unknown ground-truth
label $y_{i}\in\operatorname{\mathcal{Y}}$, and $y_{i}\in s_{i}$. Partial-
label learning aims to train a classifier $g$ that minimizes the empirical
loss.

As the ground-truth labels $y_{i}$ are hidden, one cannot evaluate the
empirical loss directly. Further, we note that the candidate labels $s_{i}$
can be partitioned into $s_{i}=\left\\{y_{i}\right\\}\cup z_{i}$ with
$y_{i}\notin z_{i}$, that is, $z_{i}\subset\mathcal{Y}$ are the false-positive
labels.

##  3 Dempster-Shafer Theory

Dempster-Shafer theory (DST; Dempster 1967; Shafer 1986) allows for dealing
with uncertainty by assigning probability mass to sets of events. We argue
that DST is a natural fit for partial-label learning: With DST, we can assign
probability mass to sets of candidates without specifying the probabilities of
individual labels; incorrect labels do not obtain any probability mass. In
contrast, existing partial-label learning approaches (Hüllermeier & Beringer,
2005; Cour et al., 2011; Liu & Dietterich, 2012; Zhang & Yu, 2015; Ni et al.,
2021) initially attribute some probability to each label candidate and
subsequently refine them. Their initial probabilities of the candidate labels
are either uniform or depend on the class priors. By doing so, most
probability mass is allocated to labels that are certainly incorrect, as only
one candidate is the true label.

###  3.1 Basic Probability Assignment

For a measurable space
$\left(\operatorname{\Omega},\operatorname{\mathcal{F}}\right)$ with sample
space $\operatorname{\Omega}$ and $\sigma$-algebra
$\operatorname{\mathcal{F}}$, we denote by
$\operatorname{\mathcal{M}}_{1}^{+}\\!\left(\operatorname{\Omega},\operatorname{\mathcal{F}}\right)$
the set of all probability measures on
$\left(\operatorname{\Omega},\operatorname{\mathcal{F}}\right)$.

A core component of DST is the _basic probability assignment_ (bpa). Given the
measurable space
$\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)$, a
basic probability assignment $\operatorname{m}$ assigns probability mass to
subsets of $\operatorname{\mathcal{Y}}$, that is,
$\operatorname{m}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right]$.
$\operatorname{m}$ satisfies $\operatorname{m}\\!\left(\emptyset\right)=0$ and
$\sum_{A\subseteq\operatorname{\mathcal{Y}}}\operatorname{m}\\!\left(A\right)=1$.222Note
that this differs from standard probability as
$\operatorname{\mathbb{P}}\\!\left(\operatorname{\mathcal{Y}}\right)=1$ for
any
$\operatorname{\mathbb{P}}\in\operatorname{\mathcal{M}}_{1}^{+}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)$
but $\operatorname{m}\\!\left(\operatorname{\mathcal{Y}}\right)\leq 1$. The
sets $A\subseteq\operatorname{\mathcal{Y}}$ with
$\operatorname{m}\\!\left(A\right)\neq 0$ are called _focal sets_ of
$\operatorname{m}$. For a bpa $\operatorname{m}$, belief and plausibility are
defined as

$\displaystyle\operatorname{bel}^{\left(\operatorname{m}\right)}$
$\displaystyle:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],$
$\displaystyle A\mapsto\sum_{B\subseteq
A}\operatorname{m}\\!\left(B\right)\text{,}$ (1)
$\displaystyle\operatorname{pl}^{\left(\operatorname{m}\right)}$
$\displaystyle:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],$
$\displaystyle A\mapsto\sum_{B\subseteq\operatorname{\mathcal{Y}},A\cap
B\neq\emptyset}\operatorname{m}\\!\left(B\right)\text{.}$ (2)

The set of all probability measures supporting $\operatorname{m}$ is

$\displaystyle\operatorname{\mathcal{C}}^{\left(\operatorname{m}\right)}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)$
$\displaystyle=\big{\\{}\operatorname{\mathbb{P}}\in\operatorname{\mathcal{M}}_{1}^{+}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)\mid$
$\displaystyle\operatorname{bel}^{\left(\operatorname{m}\right)}\\!\left(A\right)\leq\operatorname{\mathbb{P}}\\!\left(A\right)\leq\operatorname{pl}^{\left(\operatorname{m}\right)}\\!\left(A\right)\text{for
all $A\subseteq\operatorname{\mathcal{Y}}$}\,\big{\\}}\text{.}$

The set
$\operatorname{\mathcal{C}}^{\left(\operatorname{m}\right)}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)\subseteq\operatorname{\mathcal{M}}_{1}^{+}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)$
is called a _credal set_ (Abellán et al., 2006; Cuzzolin, 2021). Standard
probability describes the case when
$\operatorname{bel}\\!\left(A\right)=\operatorname{pl}\\!\left(A\right)$ for
all $A\subseteq\operatorname{\mathcal{Y}}$. Then, the element of the singleton
set
$\operatorname{\mathcal{C}}^{\left(\operatorname{m}\right)}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)$
is the probability measure used in the standard probability context.

A bpa $\operatorname{m}$ further allows quantifying aleatoric and epistemic
uncertainty. One popular measure of _epistemic_ uncertainty within DST is the
generalized Hartley measure (Dubois & Prade, 1985). _Aleatoric_ uncertainty is
commonly computed as the difference between the maximum entropy of a credal
set and the epistemic uncertainty (Meyerowitz et al., 1994).

###  3.2 Combination Rules

Dempster-Shafer theory provides rules to combine bpas from multiple
independent sources: Given $k$ bpas $\operatorname{m}_{i}$
($i\in\left[k\right]$), DST allows computing a combined bpa
$\operatorname{\tilde{m}}$. Two prominent combination rules are Dempster’s
original rule (Dempster, 1967), which is criticized for its unintuitive
results when facing high conflict (Zadeh, 1984), and Yager’s modified
combination rule (Yager, 1987a, b), which gives more intuitive results. The
following elaborates on the latter.

Yager’s rule first collects overlapping evidence by

$\displaystyle\operatorname{q}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],$
$\displaystyle\
A\mapsto\sum_{\begin{subarray}{c}A_{1},\ldots,A_{k}\subseteq\operatorname{\mathcal{Y}}\\\
\bigcap_{i=1}^{k}A_{i}=A\end{subarray}}\
\prod_{j=1}^{k}\operatorname{m}_{j}\\!\left(A_{j}\right)\text{,}$ (3)

which allocates conflicting evidence to the empty set, that is,
$\operatorname{q}\\!\left(\emptyset\right)\geq 0$. Second, it creates a bpa
$\operatorname{\tilde{m}}$ from $\operatorname{q}$ by allocating all conflicts
to the sample space $\operatorname{\mathcal{Y}}$:

$\displaystyle\operatorname{\tilde{m}}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],$
$\displaystyle A\mapsto\begin{cases}0&\text{if $A=\emptyset$,}\\\
\operatorname{q}\\!\left(\operatorname{\mathcal{Y}}\right)+\operatorname{q}\\!\left(\emptyset\right)&\text{if
$A=\operatorname{\mathcal{Y}}$,}\\\
\operatorname{q}\\!\left(A\right)&\text{else.}\end{cases}$ (4)

The probability allocated to the set of all possible alternatives
$\operatorname{\tilde{m}}\\!\left(\operatorname{\mathcal{Y}}\right)$ can be
interpreted as the degree of ignorance, which is also called non-specificity;
it is the probability mass not supporting a specific alternative within
$\operatorname{\mathcal{Y}}$.

##  4 Related Work

Imperfect, missing, or wrongly labeled data often renders the application of
supervised methods challenging and requires special care. Weakly supervised
learning tackles this setting and encompasses a variety of problem
formulations, for example, semi-supervised learning (Hady & Schwenker, 2013;
van Engelen & Hoos, 2020), learning with noisy labels (Bylander, 1994;
Natarajan et al., 2013), complementary label learning (Ishida et al., 2019;
Feng et al., 2020a), and PLL, which we target at. The first PLL approaches
establish common supervised learning frameworks in the partial-label context:
Grandvalet (2002) proposes a logistic regression formulation; Jin & Ghahramani
(2002) propose an expectation-maximization strategy; Hüllermeier & Beringer
(2005) propose a $k$-nearest-neighbors method; Nguyen & Caruana (2008) propose
an extension of support-vector machines; and Cour et al. (2011) introduce a
partial-label loss formulation allowing for the use of any supervised learning
method. However, these approaches (1) cannot model the relevance of candidate
labels in the labeling process or (2) are not robust to non-uniform noise. We
consider (1) and (2) to be the key challenges of PLL. While the lack of
knowledge about (1) contributes to epistemic uncertainty, (2) contributes to
aleatoric uncertainty.

More recent approaches address (1) and (2) in the following ways: Zhang & Yu
(2015); Zhang et al. (2016); Xu et al. (2019); Wang et al. (2019); Feng & An
(2019); Ni et al. (2021) leverage ideas from representation learning (Bengio
et al., 2013) and build manifold structures; Yu & Zhang (2017); Wang et al.
(2019); Feng & An (2019); Ni et al. (2021) extend the maximum-margin idea; Liu
& Dietterich (2012); Lv et al. (2020) propose extensions of the expectation-
maximization strategy; Zhang et al. (2017); Tang & Zhang (2017); Wu & Zhang
(2018) propose custom stacking and boosting ensembles; Lv et al. (2020)
introduce an improved partial-label loss formulation; and Feng et al. (2020b);
Lv et al. (2020); Xu et al. (2021); Wang et al. (2022); He et al. (2022)
employ deep learning for PLL.

These methods address (1) and (2), already featuring good predictive
performance. However, they often suffer from miscalibrated uncertainty
estimates as they mix epistemic and aleatoric uncertainty stemming from (1)
and (2), respectively. We consider (Hüllermeier & Beringer, 2005; Zhang & Yu,
2015; Zhang et al., 2016; Xu et al., 2019; Wang et al., 2019) as most closely
related to our proposed method as these approaches consider an instance’s
neighborhood to predict its class label. Following this, we propose an
extension of the $k$-NN classifier that keeps uncertainty from (1) and (2)
separate by leveraging Dempster-Shafer theory.

##  5 Our Method: DST-PLL

Algorithm 1 outlines Dst-Pll, which we summarize in the following. We denote
by
$\operatorname{NN}_{k}\\!\left(\tilde{x}\right)\subseteq\operatorname{\mathcal{X}}\times
2^{\operatorname{\mathcal{Y}}}$ the set of the $k$-nearest neighbors of
instance $\tilde{x}$ with their associated candidate labels. To predict the
class label of instance $\tilde{x}$, the algorithm first transforms
information from the neighbors
$\operatorname{NN}_{k}\\!\left(\tilde{x}\right)$ into bpas (Lines 3–6),
collects these into evidence set $\mathcal{E}$ (Line 8), and combines the bpas
using Yager’s rule (4) to obtain $\operatorname{\tilde{m}}$ (Line 10). Section
5.1 elaborates on these steps and Section 5.2 details how we extract a
prediction from $\operatorname{\tilde{m}}$ and estimate its confidence (Line
11). We prove the consistency of Dst-Pll in Section 5.3 and analyze its
runtime in Section 5.4.

Algorithm 1 DST-PLL (Our Proposed Method)

0: Partially-labeled dataset $\mathcal{D}=\left\\{\left(x_{i},s_{i}\right)\mid
i\in\left[n\right]\right\\}$, $x_{i}\in\operatorname{\mathcal{X}}$,
$s_{i}\subseteq\operatorname{\mathcal{Y}}$, number of nearest neighbors $k$,
instance $\tilde{x}\in\operatorname{\mathcal{X}}$ for inference with candidate
labels $\tilde{s}\subseteq\operatorname{\mathcal{Y}}$
($\tilde{s}=\operatorname{\mathcal{Y}}$ if $\tilde{x}$ is an unseen test
instance);

0: Predicted class label $\tilde{y}$, basic probability assignment
$\operatorname{\tilde{m}}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right]$
for instance $\tilde{x}$, variable $\tilde{c}\in\left\\{0,1\right\\}$
indicating whether the prediction is confident;

1: $\mathcal{E}\leftarrow\emptyset$

2: for
$\left(x_{i},s_{i}\right)\in\operatorname{NN}_{k}\\!\left(\tilde{x}\right)$ do

3: if $\tilde{s}\subseteq s_{i}$ or $\tilde{s}\cap s_{i}=\emptyset$ then

4:
$\operatorname{m}_{i}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],\
A\mapsto\begin{cases}1&\text{if $A=\tilde{s}$,}\\\ 0&\text{else}\end{cases}$

5: else

6:
$\operatorname{m}_{i}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],\
A\mapsto\begin{cases}1/2&\text{if $A=\tilde{s}$,}\\\ 1/2&\text{if
$A=\tilde{s}\cap s_{i}$,}\\\ 0&\text{else}\end{cases}$

7: end if

8: $\mathcal{E}\leftarrow\mathcal{E}\cup\left\\{\operatorname{m}_{i}\right\\}$

9: end for

10:
$\operatorname{\tilde{m}}\leftarrow\operatorname{yager\\_combination}\\!\left(\tilde{s},\,\mathcal{E}\right)$

11:
$\tilde{y},\,\tilde{c}\leftarrow\operatorname{extract\\_prediction}\\!\left(\tilde{s},\,\operatorname{\tilde{m}}\right)$

12: return $(\tilde{y},\,\operatorname{\tilde{m}},\,\tilde{c})$

###  5.1 Evidence from Partially-labeled Instances

Recall from Section 2 that instances can have multiple candidate labels. To
combine the $k$ neighbors’ evidence by Yager’s rule, we must define basic
probability assignments $\operatorname{m}_{i}$ for each neighbor
$i\in\left[k\right]$. Accordingly, the $\operatorname{m}_{i}$-s are defined
such that they support the candidate labels $\tilde{s}$ of instance
$\tilde{x}$ that overlap with their respective candidates $s_{i}$.

Basic probability assignment. Following the standard assumption that
neighboring instances in feature space are also close in label space, we
combine the evidence from the $k$ nearest neighbors
$\left(x_{i},s_{i}\right)\in\operatorname{NN}_{k}\\!\left(\tilde{x}\right)$ of
a given instance $\tilde{x}\in\operatorname{\mathcal{X}}$ with its candidate
labels $\tilde{s}\subseteq\operatorname{\mathcal{Y}}$
($\tilde{s}=\operatorname{\mathcal{Y}}$ if $\tilde{x}$ is a test instance).
For fixed $i\in[k]$, the candidate labels $s_{i}$ do not provide any valuable
information if they support all ($\tilde{s}\subseteq s_{i}$) or none
($\tilde{s}\cap s_{i}=\emptyset$) of the labels in $\tilde{s}$; we use a bpa
of $\operatorname{m}_{i}\\!\left(\tilde{s}\right)=1$ (Line 4). We set
$\operatorname{m}_{i}\\!\left(A\right)=1/2$ if $A=\tilde{s}\cap s_{i}$ or
$A=\tilde{s}$, else $\operatorname{m}_{i}\\!\left(A\right)=0$ (Line 6), where
$1/2$ equally weights evidence. We later elaborate further on the
implications. Note that we assume that the true label of instance $\tilde{x}$
is always in $\tilde{s}$, as is common in the literature (Cour et al., 2011;
Liu & Dietterich, 2012; Ni et al., 2021).

Belief and plausibility. The bpa $\operatorname{m}_{i}$ implies

$\displaystyle\operatorname{bel}^{\left(\operatorname{m}_{i}\right)}\\!\left(A\right)$
$\displaystyle=\begin{cases}1&\text{if $\tilde{s}\subseteq A$,}\\\
1/2&\text{if $\tilde{s}\cap s_{i}\subseteq A$ and $\tilde{s}\nsubseteq A$,}\\\
0&\text{if $\tilde{s}\cap s_{i}\nsubseteq A$,}\end{cases}\qquad$ (5)
$\displaystyle\operatorname{pl}^{\left(\operatorname{m}_{i}\right)}\\!\left(A\right)$
$\displaystyle=\begin{cases}1&\text{if $A\cap\tilde{s}\cap
s_{i}\neq\emptyset$,}\\\ 1/2&\text{if $A\cap\tilde{s}\cap s_{i}=\emptyset$ and
$A\cap\tilde{s}\neq\emptyset$,}\\\ 0&\text{if
$A\cap\tilde{s}=\emptyset$,}\end{cases}$ (6)

for each subset $A\subseteq\operatorname{\mathcal{Y}}$ and given
$\tilde{s}\subseteq\operatorname{\mathcal{Y}}$.

######  Remark 5.1 (Belief and Plausibility).

  * •

A set of candidates $A$ has maximal belief, that is,
$\operatorname{bel}^{\left(\operatorname{m}_{i}\right)}\\!\left(A\right)=1$,
if it covers $\tilde{s}$.

  * •

A set of candidates $A$ is plausible, that is,
$\operatorname{pl}^{\left(\operatorname{m}_{i}\right)}\\!\left(A\right)>0$, if
it supports at least one of the candidate labels in $\tilde{s}\cap s_{i}$.

  * •

There is a gap, that is,
$\operatorname{bel}^{\left(\operatorname{m}_{i}\right)}\\!\left(A\right)<\operatorname{pl}^{\left(\operatorname{m}_{i}\right)}\\!\left(A\right)$,
if $A$ supports some candidate in $\tilde{s}\cap s_{i}$ but does not cover all
candidates in $\tilde{s}\cap s_{i}$ or supports some candidate in $\tilde{s}$
but does not cover all candidates of $\tilde{s}$.

  * •

Class labels $y\in\tilde{s}\cap s_{i}$ are maximally plausible, that is,
$\operatorname{pl}^{\left(\operatorname{m}_{i}\right)}\\!\left(\left\\{y\right\\}\right)=1$.

Evidence weighting. A more general definition of $\operatorname{m}_{i}$
(Algorithm 1; Line 6) is $\operatorname{m}_{i}\\!\left(A\right)=\alpha$ if
$A=\tilde{s}$, $\operatorname{m}_{i}\\!\left(A\right)=1-\alpha$ if
$A=\tilde{s}\cap s_{i}$, and $\operatorname{m}_{i}\\!\left(A\right)=0$
otherwise, for some $\alpha\in\left(0,1\right)$. However, without further
assumptions, one cannot know how relevant the information from a particular
neighbor is. Setting $\alpha=1/2$ weights supporting and conflicting evidence
of all neighbors equally. In other words, if a neighbor’s evidence excludes
some candidate labels from consideration, it is of equal importance compared
to supporting some candidate labels. Therefore, we set $\alpha=1/2$.

Evidence combination. Given the set
$\mathcal{E}=\left\\{\operatorname{m}_{i}\mid i\in\left[k\right]\right\\}$, we
combine all $\operatorname{m}_{i}$-s using Yager’s rule (4). We implement this
efficiently with hash maps storing only the focal sets.

###  5.2 Decision Boundary

After the combination into $\operatorname{\tilde{m}}$, we extract a prediction
$\tilde{y}\in\tilde{s}$ in Line 11. To do so, we discern between two cases.

  1. 1.

Use
$\tilde{y}:=\arg\max_{y\in\tilde{s}}\,\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)$
if any $y\in\tilde{s}$ has non-zero belief, that is,
$\max_{y\in\tilde{s}}\,\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)>0$.

  2. 2.

Otherwise, we randomly choose $\tilde{y}$ from the subset
$\arg\max_{\emptyset\neq
A\subseteq\tilde{s}}\,\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(A\right)$
with the highest belief. When tied, use the subset with the smallest
cardinality.

We are _confident_ in our prediction $\tilde{y}$ if only one class label is at
least as plausible as our maximum single-item belief. Our notion of confidence
is binary. Formally, we define a confident prediction as follows.

######  Definition 5.2 (Confident Prediction).

Given a bpa $\operatorname{\tilde{m}}$, the prediction
$\tilde{y}\in\operatorname{\mathcal{Y}}$ is confident if and only if

$\big{\\{}y\in\operatorname{\mathcal{Y}}\mid\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)\geq\max_{y^{\prime}\in\tilde{s}}\,\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y^{\prime}\right\\}\right)\big{\\}}=\left\\{\tilde{y}\right\\}\text{.}$

Naturally, this only occurs in the first case of our prediction approach and
when $\tilde{y}\in\tilde{s}$. In the second case,
$\max_{y^{\prime}\in\operatorname{\mathcal{Y}}}\,\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y^{\prime}\right\\}\right)=0\leq\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(y\right)$
for all $y\in\operatorname{\mathcal{Y}}$. Intuitively, a class label is not
confident if its singleton is less plausible than the maximum belief in
another singleton.

######  Example 5.3.

Let $\tilde{s}=\operatorname{\mathcal{Y}}=\left\\{1,2,3\right\\}$ and
$\operatorname{\tilde{m}}$ be defined by

$\operatorname{\tilde{m}}:2^{\operatorname{\mathcal{Y}}}\rightarrow\left[0,1\right],\quad
A\mapsto\begin{cases}0.4&\text{if $A=\left\\{1\right\\}$,}\\\ 0.3&\text{if
$A=\left\\{1,2\right\\}$,}\\\ 0.3&\text{if $A=\left\\{1,3\right\\}$,}\\\
0&\text{else.}\end{cases}$ (7)

Then, $y=1$ is a confident prediction since
$\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{1\right\\}\right)=0.4$,
$\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{2\right\\}\right)=\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{3\right\\}\right)=0$,
$\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{1\right\\}\right)=1$,
and
$\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{2\right\\}\right)=\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{3\right\\}\right)=0.3$.
Our belief in class label $1$ is larger than the plausibility of $2$ or $3$.
The prediction is $y=1$, independent of
$\operatorname{\mathbb{P}}\in\operatorname{\mathcal{C}}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\operatorname{\mathcal{Y}},2^{\operatorname{\mathcal{Y}}}\right)$.

The following lemma provides a sufficient condition for a prediction to be
confident. It implies that Dst-Pll yields at least as many confident
predictions as majority-vote-based approaches as the latter require more than
one-half of the votes to be certain (see Definition 6.1).

######  Lemma 5.4.

Given an instance $\tilde{x}\in\operatorname{\mathcal{X}}$ with its candidate
label set $\tilde{s}$ ($\tilde{s}=\operatorname{\mathcal{Y}}$ if $\tilde{x}$
is a test instance) and its bpa $\operatorname{\tilde{m}}$,

$\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)>1/2\
\Rightarrow\ \text{$y$ is a confident prediction,}$ (8)

for all $y\in\tilde{s}$. The converse implication does not hold.

###  5.3 Consistency

In this section, we show that our method yields a consistent classifier. This
establishes the applicability of Yager’s rule.

Throughout this section, the sample space is
$\operatorname{\Omega}=\operatorname{\mathcal{X}}\times\operatorname{\mathcal{Y}}\times
2^{\operatorname{\mathcal{Y}}}$. It is equipped with the smallest Borel
$\sigma$-algebra
$\operatorname{\mathcal{B}}\\!\left(\operatorname{\Omega}\right)$, yielding
the measurable space
$\left(\operatorname{\Omega},\operatorname{\mathcal{B}}\\!\left(\operatorname{\Omega}\right)\right)$
with respect to which the probability measure
$\operatorname{\mathbb{P}}\in\operatorname{\mathcal{M}}_{1}^{+}\\!\left(\operatorname{\Omega},\operatorname{\mathcal{B}}\\!\left(\operatorname{\Omega}\right)\right)$
is defined. The random variables
$X:\operatorname{\Omega}\rightarrow\operatorname{\mathcal{X}}$,
$Y:\operatorname{\Omega}\rightarrow\operatorname{\mathcal{Y}}$, and
$S:\operatorname{\Omega}\rightarrow 2^{\operatorname{\mathcal{Y}}}$ govern an
instance’s features, true label, and candidate labels, respectively. We denote
the corresponding marginal measures by associating the corresponding index to
$\operatorname{\mathbb{P}}$, for example, $\operatorname{\mathbb{P}}_{X}$ is
the distribution of $X$. $\operatorname{\mathbb{P}}_{XY}$ denotes the joint
distribution of $\left(X,Y\right)$.

As is common in the literature (Cour et al., 2011; Liu & Dietterich, 2012;
Feng et al., 2020b; Lv et al., 2020), we fix a label (noise) distribution that
allows for further analysis of the proposed algorithm. Appendix D
experimentally verifies that Assumption 5.5 is satisfied on real-world
datasets.

######  Assumption 5.5.

Let $\tilde{x}\in\operatorname{\mathcal{X}}$ be the instance of interest with
hidden true label $\tilde{y}\in\operatorname{\mathcal{Y}}$ and
$l=|\operatorname{\mathcal{Y}}|\geq 3$ classes. Its $k$ partially-labeled
neighbors are
$\left(x_{i},s_{i}\right)\in\operatorname{NN}_{k}\\!\left(\tilde{x}\right)$.
Label
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\in\operatorname{\mathcal{Y}}\setminus\left\\{\tilde{y}\right\\}$
denotes the class label that cooccurs most frequently with label $\tilde{y}$.
We assume that the true label dominates the neighborhood, that is,

$\displaystyle\operatorname{\mathbb{P}}(S=\underbrace{s}_{=\
\left\\{y\right\\}\ \cup\ z},Y=y\mid X=x_{i})$ (9)
$\displaystyle=\begin{cases}0\\!&\\!\text{if $s=\operatorname{\mathcal{Y}}$ or
$s=\emptyset$,}\ {\hskip 53.8pt(i)}\\\ 0\\!&\\!\text{if $y\notin s$ or $y\in
z$,}\ {\hskip 56.3pt(ii)}\\\ 0\\!&\\!\text{if $\tilde{y}\in z$,}\ {\hskip
90.5pt(iii)}\\\ \frac{1}{2^{l-2}-1}\,p_{1}\\!&\\!\begin{aligned} \\!&\text{if
$y=\tilde{y}$, $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\in
z$,}\\\ \\!&\text{and $s\neq\operatorname{\mathcal{Y}}$,}\end{aligned}\
{\hskip 51.4pt(iv)}\\\ \frac{1}{2^{l-2}}\,p_{2}\\!&\\!\text{if $y=\tilde{y}$
and $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\notin z$,}\ {\hskip
38.45pt(v)}\\\ \frac{1}{2^{l-1}-1}\frac{1}{|s|}\,p_{3}\\!&\\!\begin{aligned}
\\!&\text{if $y\neq\tilde{y}$, $\tilde{y}\notin z$, $y\notin z$,}\\\
\\!&\text{and $s\neq\emptyset$,}\end{aligned}\ {\hskip 35.4pt(vi)}\\\
\end{cases}$

with $p_{i}\in(0,1)$, $p_{1}+p_{2}+p_{3}=1$, and $p_{1}\geq p_{2}\geq
p_{3}>0$.

Because $p_{1}+p_{2}>p_{3}$, Assumption 5.5 implies that
$\operatorname{\mathbb{P}}_{XY}\\!\left(Y=\tilde{y}\mid
X=x_{i}\right)>\operatorname{\mathbb{P}}_{XY}\\!\left(Y\neq\tilde{y}\mid
X=x_{i}\right)$ and imposes a smoothness assumption, that is, points that are
close in feature space are likely to have a similar class.

In the following, we elaborate on the six cases $(i)$ – $(vi)$.

######  Remark 5.6.

  * •

If a candidate set contains all ($s=\operatorname{\mathcal{Y}}$) or no labels
($s=\emptyset$), it does not distinguish any class labels. $(i)$ handles this
pathological setting by assigning zero probability.

  * •

The true label must be part of the candidates (Hüllermeier & Beringer, 2005;
Cour et al., 2011; Liu & Dietterich, 2012; Zhang & Yu, 2015) so that $(ii)$
has zero probability.

  * •

The true label $\tilde{y}$ of instance $\tilde{x}$ is not allowed to be a
false-positive label among $\tilde{x}$’s neighbors $x_{i}$; the existence of
$\tilde{y}$ among the candidate labels is a signal for the true label and
$(iii)$ assigns zero probability to $\tilde{y}\in z$.

In other words, $(ii)$ and $(iii)$ ensure that partitioning is always
possible.

  * •

In $(iv)$, $\tilde{x}$’s true label is also the true label of neighbor $x_{i}$
and the label $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$, with
which $\tilde{y}$ is most commonly confused, is also part of the candidate set
$s_{i}$. There are $2^{l-2}-1$ sets $s$ that contain both $\tilde{y}$ and
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ and are not
$\operatorname{\mathcal{Y}}$.

  * •

In $(v)$, $\tilde{x}$’s true label coincides with the true label of $x_{i}$.
Label $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ is not part of
the candidate set $s_{i}$ of neighbor $x_{i}$. There are $2^{l-2}$ sets $s$
that contain $\tilde{y}$ but not
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$.

  * •

In $(vi)$, a neighbor $x_{i}$ might have different labels altogether and be
irrelevant for explaining the true label of instance $\tilde{x}$. There are
$2^{l-1}-1$ sets that do not contain the true label $\tilde{y}$ (excluding the
empty set). Each of the $|s|$ candidates can be the neighbor’s true label.

Lemma 5.7 and 5.8 present main findings leading to Theorem 5.9, which
establishes risk-consistency.

######  Lemma 5.7.

Assume the setting of Assumption 5.5, let
$\tilde{x}\in\operatorname{\mathcal{X}}$ be the instance of interest,
$\tilde{y}\in\operatorname{\mathcal{Y}}$ its hidden true label, and compute
the basic probability assignment $\operatorname{\tilde{m}}$ with Algorithm 1.
Then, it holds that
$\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\left[\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\right]>0$.

As the belief is positive in expectation, we can reduce our analysis to the
first case of our decision rule in Section 5.2. The following lemma shows how
Assumption 5.5 propagates when applying Yager’s rule on all $k$ neighbors’
$\operatorname{m}_{i}$-s.

######  Lemma 5.8.

Assume the setting of Assumption 5.5, let
$\tilde{x}\in\operatorname{\mathcal{X}}$ be a fixed instance,
$\tilde{y}\in\operatorname{\mathcal{Y}}$ its hidden true label, and
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\in\operatorname{\mathcal{Y}}\setminus\left\\{\tilde{y}\right\\}$
the label that cooccurs most frequently with $\tilde{y}$ in the neighborhood
of $\tilde{x}$. It holds that

$\displaystyle\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\left[\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\right]>\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\left[\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}(\\{\tilde{y}_{c}^{\left(\tilde{y}\right)}\\})\mid
X=\tilde{x}\right]\text{.}$

In other words, the label that dominates the neighborhood obtains the highest
belief. To our knowledge, it is the first time that such a result has been
shown; it proves to be crucial for obtaining our main statement.

To put Theorem 5.9 into context, we recall the concept of risk consistency. As
Assumption 5.5 fixes distribution $\operatorname{\mathbb{P}}$, one can
quantify the classification risk of a classifier $g$ using the 0-1-loss
$\operatorname{\mathcal{L}}$, that is,
$\operatorname{\mathcal{R}}\\!\left(g\right)=\operatorname{\mathbb{E}}_{\left(X,Y\right)\sim\operatorname{\mathbb{P}}_{XY}}\\!\left[\operatorname{\mathcal{L}}\\!\left(g\\!\left(X\right),Y\right)\right]$.333We
note that one cannot compute the empirical risk as the ground-truth labels
$y_{i}$ are unknown in practice. Fixing a label distribution (Assumption 5.5)
allows computing the risk. The Bayes classifier is defined by
$g^{*}=\arg\min_{g:\operatorname{\mathcal{X}}\rightarrow\operatorname{\mathcal{Y}}}\,\operatorname{\mathbb{E}}_{\left(X,Y\right)\sim\operatorname{\mathbb{P}}_{XY}}\\!\left[\operatorname{\mathcal{L}}\\!\left(g\\!\left(X\right),Y\right)\right]$;
it has the least overall risk. A classifier $g$ is risk-consistent if
$\lim_{n\to\infty}\left(\operatorname{\mathcal{R}}\\!\left(g_{n}\right)-\operatorname{\mathcal{R}}\\!\left(g^{*}\right)\right)=0$.

######  Theorem 5.9.

Assume the setting of Assumption 5.5, let
$g_{n}:\operatorname{\mathcal{X}}\to\operatorname{\mathcal{Y}}$ be the
classification rule corresponding to Algorithm 1 as detailed in Section 5.2,
$g^{*}:\operatorname{\mathcal{X}}\to\operatorname{\mathcal{Y}}$ the Bayes
classifier, and $\tilde{x}\in\operatorname{\mathcal{X}}$ a fixed instance with
unknown true label $\tilde{y}$. Then, the following hold:

  1. (i)

$\operatorname{\mathbb{E}}_{\left(x_{i},s_{i}\right)_{i=1}^{n}\overset{\text{i.i.d.}}{\sim}\,\operatorname{\mathbb{P}}_{XS}}\\!\left[g_{n}\\!\left(\tilde{x}\right)\right]=\tilde{y}$,
and

  2. (ii)

$\lim_{n\to\infty}\left(\operatorname{\mathcal{R}}\\!\left(g_{n}\right)-\operatorname{\mathcal{R}}\\!\left(g^{*}\right)\right)=0$.

The theorem establishes the risk consistency of the proposed classifier and
demonstrates the usefulness of employing Dempster-Shafer theory in classifying
partially labeled data.

###  5.4 Runtime Complexity

Looking at Algorithm 1, we decompose the overall runtime of our approach into
$k$-times querying one nearest neighbor and creating its bpa (Lines 2–9), the
cost of Yager’s rule (Line 10), as well as extracting predictions in Line 11.

Using the ball-tree data structure (Omohundro, 1989), querying one neighbor
takes $\mathcal{O}\\!\left(d\log n\right)$ time on average. In the worst case,
query time is $\mathcal{O}\\!\left(dn\right)$. One builds a ball-tree in
$\mathcal{O}\\!\left(dn\log n\right)$ time.

We construct a bpa $\operatorname{m}_{i}$ by storing its focal sets within a
hash map and combine all $\operatorname{m}_{i}$-s as defined in (4). There are
at most $\min\\!\left(2^{k},2^{l}\right)$ focal sets of
$\operatorname{\tilde{m}}$: Each $\operatorname{m}_{i}$ has at most two focal
sets producing $2^{k}$ combinations and there are at most $2^{l}$ possible
subsets of $\operatorname{\mathcal{Y}}$. We take the minimum as both are upper
bounds. Looking up a focal set in the hash-map requires
$\mathcal{O}\\!\left(l\right)$ time. Extracting a prediction and its
confidence (Definition 5.2) requires $\mathcal{O}\\!\left(l^{2}\right)$ time.

Combining the above yields a worst-case complexity of
$\mathcal{O}\\!\left(dkn+l\left(\min\\!\left(2^{k},2^{l}\right)+\max\\!\left(k,l\right)\right)\right)$.
Since $k$ and $l$ are constant, the nearest-neighbor search dominates. The
average total runtime of the search is $\mathcal{O}\\!\left(dk\log n\right)$.

##  6 Experiments

This section collects our experimental results. Section 6.1 lists the tested
algorithms. We benchmark them on artificial data in Section 6.2 and on real-
world data in Section 6.3.

(a) Prediction performance.

(b) Confidence calibration.

(c) Runtimes of all approaches.

Figure 1: Evaluation on all nine UCI datasets (see Table 1) and all
experimental settings.

###  6.1 Algorithms for Comparison

While many PLL algorithms exist (see Section 4), we focus on methods commonly
used in the literature. In total, we consider nine competitors and chose their
parameters as recommended by the respective authors.

  * •

Pl-Knn (Hüllermeier & Beringer, 2005): $k=10$;

  * •

Pl-Svm (Nguyen & Caruana, 2008): Pegasos optimizer (Shalev-Shwartz et al.,
2007) and $\lambda=1$;

  * •

Clpl (Cour et al., 2011): linear SVMs with squared-hinge loss and $\lambda=1$;

  * •

Lsb-Cmm (Liu & Dietterich, 2012): $K=5l$ components, $\alpha=0.05$,
$\sigma^{2}=1$, and 100 iterations;

  * •

Ipal (Zhang & Yu, 2015): $k=10$, $\alpha=0.95$, and 100 iterations;

  * •

M3Pl (Yu & Zhang, 2017): $C_{\operatorname{max}}=1$, $\Delta=0.5$, a penalty
of $10\,000\text{\,}$, and $\delta=10^{-4}$;

  * •

Paloc (Wu & Zhang, 2018): RBF-kernel SVMs, hinge loss, $\lambda=1$, and
$\mu=10$;

  * •

Sure (Feng & An, 2019): $\lambda=0.3$, $\beta=0.05$, a convergence threshold
of $0.1$, and 100 iterations;

  * •

Dst-Pll (proposed): $k=10$ (as Pl-Knn and Ipal).

For the competitors, we define a confident prediction in one of the two
following ways.

######  Definition 6.1.

Given an instance of interest and associated non-negative scores
$\operatorname{score}:\operatorname{\mathcal{Y}}\rightarrow\mathbb{R}_{\geq
0}$ for each label, the prediction $\tilde{y}\in\operatorname{\mathcal{Y}}$ is
confident if and only if
$\operatorname{score}\\!\left(\tilde{y}\right)/\sum_{y\in\operatorname{\mathcal{Y}}}\operatorname{score}\\!\left(y\right)>1/2$.
If $\operatorname{score}\\!\left(y\right)=0$ for all
$y\in\operatorname{\mathcal{Y}}$, prediction $\tilde{y}$ is not confident.

######  Definition 6.2.

Given an instance and its real-valued distances to the decision boundaries
$\operatorname{dist}:\operatorname{\mathcal{Y}}\rightarrow\mathbb{R}$ for each
label (with $\operatorname{dist}\\!\left(y^{\prime}\right)>0$ indicating that
$y^{\prime}\in\operatorname{\mathcal{Y}}$ is possibly the true label and
$\operatorname{dist}\\!\left(y^{\prime}\right)<0$ that it is not), the
prediction $\tilde{y}\in\operatorname{\mathcal{Y}}$ is confident if and only
if $\operatorname{dist}\\!\left(\tilde{y}\right)>0$ and
$\operatorname{dist}\\!\left(y\right)<0$ for all
$y\in\mathcal{Y}\setminus\left\\{\tilde{y}\right\\}$.

Definition 6.1 requires scores for all possible classes, for instance, a
vector of probabilities or a majority vote. Note that for $k$-NN, the
definition agrees with the classification rule of Hellman (1970). We use the
definition with Pl-Knn, Lsb-Cmm, Ipal, and Paloc. The methods Pl-Svm, Clpl,
M3Pl, and Sure output the distance to the decision boundary for each class
label $y\in\operatorname{\mathcal{Y}}$. Here, we employ Definition 6.2. Recall
that our approach uses Definition 5.2.

###  6.2 Controlled Experiments

Setup. Following the default experimentation protocol (Cour et al., 2011; Liu
& Dietterich, 2012; Zhang & Yu, 2015), we conduct several controlled
experiments using datasets for supervised learning. One augments them by
adding $r\in\left\\{1,2,3\right\\}$ false-positive labels to a fraction
$p\in\left\\{0.1,0.2,...,0.7\right\\}$ of all instances uniformly at random.
In the case of $r=1$, one can vary the co-occurrence degree
$\varepsilon\in\left\\{0.1,0.2,...,0.7\right\\}$, that is, how often a
randomly determined class label co-occurs with a given true label. Parameters
$r$, $p$, and $\varepsilon$ control the difficulty of the PLL problem. Table 1
collects the nine supervised multi-class datasets from the UCI repository
(Bache & Lichman, 2013) that we use. Together with the 70 parameter settings,
these result in a total of 630 controlled experiments. We perform 5-fold
cross-validation for each experiment and report average performances and
standard deviations. To discuss significant differences, we use a paired
$t$-test with $\alpha=$5\text{\,}\%$$.

Table 1: UCI datasets. |  Dataset | Examples | Features | Classes
---|---|---|---|---
1 |  artificial-characters | $10\,218$ | $7$ | $10$
2 |  chess-kr-vs-k | $28\,056$ | $23$ | $18$
3 |  ecoli | $336$ | $7$ | $8$
4 |  first-order-theorem | $6118$ | $51$ | $6$
5 |  mfeat-fourier | $2000$ | $76$ | $10$
6 |  pen-digits | $10\,992$ | $16$ | $10$
7 |  semeion-handwritten | $1593$ | $256$ | $10$
8 |  statlog-landsat | $2859$ | $36$ | $6$
9 |  solar-flare | $1389$ | $20$ | $6$
Table 2: Trade-off $O_{\beta}$ between $O_{\operatorname{perf}}^{\left(\operatorname{mcc}\right)}$ and $O_{\operatorname{frac}}$ for all datasets regarding parameter $\beta\in\left\\{0.5,0.6,\dots,1.0\right\\}$. Approach |  Trade-off value $O_{\beta}$ for all nine UCI datasets |  Trade-off value $O_{\beta}$ for all five real-world datasets
---|---|---
| 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0
Pl-Knn | $0.554$ | $0.628$ | $0.702$ | $0.776$ | $0.851$ | $0.925$ | $0.403$ | $0.463$ | $0.523$ | $0.584$ | $0.644$ | $0.704$
Pl-Svm | $0.286$ | $0.291$ | $0.296$ | $0.301$ | $0.306$ | $0.310$ | $0.259$ | $0.285$ | $0.312$ | $0.338$ | $0.365$ | $0.392$
Clpl | $0.593$ | $0.601$ | $0.609$ | $0.617$ | $0.625$ | $0.633$ | $0.463$ | $0.483$ | $0.502$ | $0.521$ | $0.541$ | $0.560$
Lsb-Cmm | $0.704$ | $0.717$ | $0.730$ | $0.744$ | $0.757$ | $0.770$ | $0.586$ | $0.612$ | $0.639$ | $0.665$ | $0.692$ | $0.718$
Ipal | $0.775$ | $0.788$ | $0.802$ | $0.815$ | $0.829$ | $0.842$ | $0.667$ | $0.670$ | $0.674$ | $0.677$ | $0.680$ | $0.684$
M3Pl | $0.637$ | $0.648$ | $0.659$ | $0.671$ | $0.682$ | $0.693$ | $0.644$ | $0.655$ | $0.665$ | $0.676$ | $0.686$ | $0.697$
Paloc | $0.217$ | $0.223$ | $0.228$ | $0.233$ | $0.239$ | $0.244$ | $0.000$ | $0.000$ | $0.000$ | $0.000$ | $0.000$ | $0.000$
Sure | $0.063$ | $0.075$ | $0.088$ | $0.100$ | $0.112$ | $0.124$ | $0.000$ | $0.000$ | $0.000$ | $0.000$ | $0.000$ | $0.000$
Dst-Pll | $0.670$ | $0.723$ | $0.776$ | $0.829$ | $0.882$ | $0.935$ | $0.503$ | $0.569$ | $0.635$ | $0.701$ | $0.768$ | $0.834$

Figure 2: Prediction performance and confidence calibration on all five real-
world datasets.

Results. Figure 1(a) shows the test-set performance. We use Matthews
correlation coefficient (MCC; Matthews 1975) for evaluation and average the
results across all 630 configurations. Appendix D.2 contains additional
results using the accuracy metric. The error bars indicate the standard
deviations. While our approach is competitive, there is no approach that is
best across all datasets: For example, Ipal significantly outperforms our
approach on dataset 1; in contrast, we significantly outperform Ipal on
datasets 3 and 9. Overall, Dst-Pll performs similarly to Pl-Knn as both are
nearest-neighbor approaches.

Figure 1(b) compares all approaches’ calibration of confident predictions. It
shows the fraction and the average test-set MCC scores of confident
predictions. The error bars indicate the standard deviations. A perfect
classifier is confident about all predictions and also correct about all of
them. Our approach (Dst-Pll) provides, together with Pl-Knn, the most accurate
confident predictions regarding MCC score. However, we mark double the number
of predictions as confident on average compared to Pl-Knn, as we account for
different sources of uncertainty. Scoring-based methods that output a vector
of probabilities or a majority vote (see Definition 6.1) are better calibrated
in most cases, that is, closer to the top-right corner, than distance-based
methods (see Definition 6.2): Using the distance to the decision boundary as a
proxy for certainty about a prediction does not work well in the context of
partial-label learning.

Let $O_{\operatorname{perf}}^{\left(\operatorname{mcc}\right)}$ denote the MCC
score of confident predictions and $O_{\operatorname{frac}}$ the fraction of
confident predictions and define the weighted objective value as
$O_{\beta}=\beta\,O_{\operatorname{perf}}+(1-\beta)\,O_{\operatorname{frac}}$
with weighting parameter $\beta\in\left[0,1\right]$. Table 2 (left half) shows
the trade-off objective $O_{\beta}$ of all approaches.444We only consider
$\beta\in\left[0.5,1\right]$ as it is more important to have accurate
confident predictions ($\beta=1$) than to mark a big number of predictions as
confident ($\beta=0$). If it is roughly equally important to have accurate
confident predictions and a big number of them
($\beta\in\left\\{0.5,0.6,0.7\right\\}$), Ipal provides the best trade-off. If
one favors accurate confident predictions
($\beta\in\left\\{0.8,0.9,1.0\right\\}$), our approach is best. This
conclusion stays the same when considering test-set accuracy and MCC score
(see Appendix D.3).

Runtime. Figure 1(c) shows all methods’ runtimes for a varying number of
instances. Both axes are scaled logarithmically; a straight line indicates
linear growth. Our approach is only slightly slower than Pl-Knn. However, it
is more than two orders of magnitude faster than Lsb-Cmm, Ipal, M3Pl, and
Sure, while providing similar performance in most cases (see Figure 1(a)).

###  6.3 Real-world Experiments

Table 3: Real-world data with their size, the fraction of partially labeled instances, and the average candidate labels per instance. |  Dataset | Examples | Features | Classes | % Part. | Avg. Cand.
---|---|---|---|---|---|---
1 |  bird | $4966$ | $38$ | $12$ | $0.67$ | $2.15$
2 |  flickr | $2778$ | $1536$ | $12$ | $1.00$ | $2.75$
3 |  lost | $1122$ | $108$ | $14$ | $0.93$ | $2.22$
4 |  msrc | $1755$ | $48$ | $22$ | $0.92$ | $3.15$
5 |  yahoo | $22\,762$ | $163$ | $203$ | $0.72$ | $1.91$

Setup. In addition to artificially augmented data, we use five commonly used
real-world datasets: The BirdSong dataset (Briggs et al., 2012) requires audio
classification, MirFlickr (Huiskes & Lew, 2008) image classification, Lost
(Cour et al., 2011) and YahooNews (Guillaumin et al., 2010) face
classification, and MsrcV2 (Liu & Dietterich, 2012) object classification.
Table 3 lists the data sets and their properties. We perform 5-fold cross-
validation for each dataset and report average performances and standard
deviations. The approaches ClPl and Sure did not give results for the dataset
YahooNews due to memory constraints
($160\text{\,}\mathrm{G}\mathrm{i}\mathrm{B}$ of total memory); we set their
MCC score on this particular dataset to zero.

Results. Figure 2 shows the methods’ performances and confidence calibration
on the real-world datasets. The error bars indicate the standard deviation
regarding the 5-fold cross-validation. A perfect classifier has an MCC score
of one (left plot), is confident about all predictions (center plot), and is
also correct about all of them (right plot). Our approach has competitive
performance on most real-world datasets (Figure 2; left plot). Its performance
is most similar to Pl-Knn. However, our confident predictions are
significantly more accurate in most cases (Figure 2; right plot): In fact, on
the BirdSong and MsrcV2 datasets, confident predictions of our method are
significantly more accurate than those of any other method. On the MirFlickr
dataset, Dst-Pll is significantly more accurate with confident predictions
than all other methods except for Clpl, which performs similarly. Last, on the
YahooNews dataset, our algorithm is significantly more accurate with confident
predictions than all other methods except for Pl-Knn, which has similar
performance. We note that our method suffers from high variance on the Lost
dataset as there are close to zero confident predictions (Figure 2; center
plot).

Table 2 (right half) shows the trade-off objective $O_{\beta}$ for
$\beta\in\left[0.5,1.0\right]$.${}^{\text{\ref{fn:tradeoff}}}$ If having
accurate confident predictions and a big number of them is roughly equally
important ($\beta\in\left\\{0.5,0.6,0.7\right\\}$), Ipal provides the best
tradeoff on the real-world datasets. Our approach proves beneficial if one
wants accurate confident predictions ($\beta\in\left\\{0.8,0.9,1.0\right\\}$).

We defer the discussion on the impact of the parameter $k$ on the prediction
performance and the calibration of confident predictions to Appendix D.4.

##  7 Conclusions

We address the problem of partial-label learning. Current state-of-the-art
methods offer good predictive performance but often suffer from miscalibrated
uncertainty estimates. The proposed approach offers a well-calibrated
uncertainty estimate by leveraging Dempster-Shafer theory. Experiments
demonstrate the effectiveness of our algorithm; it provides competitive and
well-calibrated predictions. Further, we prove its risk consistency.

## References

  * Abellán et al. (2006) Abellán, J., Klir, G. J., and Moral, S.  Disaggregated total uncertainty measure for credal sets.  _International Journal of General Systems_ , 35(1):29–44, 2006.
  * Ao et al. (2023) Ao, S., Rueger, S., and Siddharthan, A.  Two sides of miscalibration: Identifying over and under-confidence prediction for network calibration.  In _Uncertainty in Artificial Intelligence_ , volume 216, pp. 77–87, 2023.
  * Bache & Lichman (2013) Bache, K. and Lichman, M.  UCI machine-learning repository, 2013.  URL https://archive.ics.uci.edu/.
  * Bengio et al. (2013) Bengio, Y., Courville, A. C., and Vincent, P.  Representation learning: A review and new perspectives.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 35(8):1798–1828, 2013.
  * Briggs et al. (2012) Briggs, F., Fern, X. Z., and Raich, R.  Rank-loss support instance machines for MIML instance annotation.  In _ACM Conference on Knowledge Discovery and Data Mining_ , pp. 534–542, 2012.
  * Bylander (1994) Bylander, T.  Learning linear threshold functions in the presence of classification noise.  In _ACM Conference on Computational Learning Theory_ , pp. 340–347, 1994.
  * Cour et al. (2011) Cour, T., Sapp, B., and Taskar, B.  Learning from partial labels.  _Journal of Machine Learning Research_ , 12:1501–1536, 2011.
  * Cuzzolin (2021) Cuzzolin, F.  _The Geometry of Uncertainty - The Geometry of Imprecise Probabilities_.  Springer, 2021.
  * Dempster (1967) Dempster, A. P.  Upper and lower probabilities induced by a multivalued mapping.  _The Annals of Statistic_ , 28:325–339, 1967.
  * Dubois & Prade (1985) Dubois, D. and Prade, H.  A note on measures of specificity for fuzzy sets.  _International Journal of General System_ , 10(4):279–283, 1985.
  * Feng & An (2019) Feng, L. and An, B.  Partial label learning with self-guided retraining.  In _AAAI Conference on Artificial Intelligence_ , pp. 3542–3549, 2019.
  * Feng et al. (2020a) Feng, L., Kaneko, T., Han, B., Niu, G., An, B., and Sugiyama, M.  Learning with multiple complementary labels.  In _International Conference of Machine Learning_ , volume 119, pp. 3072–3081, 2020a.
  * Feng et al. (2020b) Feng, L., Lv, J., Han, B., Xu, M., Niu, G., Geng, X., An, B., and Sugiyama, M.  Provably consistent partial-label learning.  In _Neural Information Processing Systems_ , 2020b.
  * Fisher (1930) Fisher, R. A.  Inverse probability.  _Cambridge Philosophical Society_ , 26(4):528–535, 1930.
  * Fisher (1935) Fisher, R. A.  The logic of inductive inference.  _Royal Statistical Society_ , 98(1):39–82, 1935.
  * Graham et al. (1994) Graham, R. L., Knuth, D. E., and Patashnik, O.  _Concrete Mathematics: A Foundation for Computer Science_.  Addison-Wesley, 1994.
  * Grandvalet (2002) Grandvalet, Y.  Logistic regression for partial labels.  In _Information Processing and Management of Uncertainty in Knowledge-based Systems_ , 2002.
  * Guillaumin et al. (2010) Guillaumin, M., Verbeek, J., and Schmid, C.  Multiple instance metric learning from automatically labeled bags of faces.  In _European Conference on Computer Vision_ , volume 6311, pp. 634–647, 2010.
  * Guo et al. (2017) Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , volume 70, pp. 1321–1330, 2017.
  * Hady & Schwenker (2013) Hady, M. F. A. and Schwenker, F.  Semi-supervised learning.  In _Handbook on Neural Information Processing_ , volume 49, pp. 215–239. Springer, 2013.
  * Harmanec et al. (1996) Harmanec, D., Resconi, G., Klir, G. J., and Pan, Y.  On the computation of uncertainty measure in Dempster-Shafer theory.  _International Journal Of General System_ , 25(2):153–163, 1996.
  * He et al. (2022) He, S., Feng, L., Lv, F., Li, W., and Yang, G.  Partial label learning with semantic label representations.  In _ACM Conference on Knowledge Discovery and Data Mining_ , pp. 545–553, 2022.
  * Hellman (1970) Hellman, M. E.  The nearest neighbor classification rule with a reject option.  _IEEE Transactions on Systems Science and Cybernetics_ , 6(3):179–185, 1970.
  * Hora (1996) Hora, S. C.  Aleatory and epistemic uncertainty in probability elicitation with an example from hazardous waste management.  _Reliability Engineering and System Safety_ , 54(2-3):217–223, 1996.
  * Hubmann et al. (2017) Hubmann, C., Becker, M., Althoff, D., Lenz, D., and Stiller, C.  Decision making for autonomous driving considering interaction and uncertain prediction of surrounding vehicles.  In _IEEE Intelligent Vehicles Symposium_ , pp. 1671–1678, 2017.
  * Huiskes & Lew (2008) Huiskes, M. J. and Lew, M. S.  The MIR flickr retrieval evaluation.  In _ACM International Conference on Multimedia Information Retrieval_ , pp. 39–43, 2008.
  * Hüllermeier & Beringer (2005) Hüllermeier, E. and Beringer, J.  Learning from ambiguously labeled examples.  _Intelligent Data Analysis_ , 10(5):168–179, 2005.
  * Ishida et al. (2019) Ishida, T., Niu, G., Menon, A. K., and Sugiyama, M.  Complementary-label learning for arbitrary losses and models.  In _ACM International Conference on Machine Learning_ , volume 97, pp. 2971–2980, 2019.
  * Jin & Ghahramani (2002) Jin, R. and Ghahramani, Z.  Learning with multiple labels.  In _Neural Information Processing Systems_ , pp. 897–904, 2002.
  * Kendall & Gal (2017) Kendall, A. and Gal, Y.  What uncertainties do we need in bayesian deep learning for computer vision?  In _Neural Information Processing Systems_ , pp. 5574–5584, 2017.
  * Klir & Wierman (1999) Klir, G. and Wierman, M.  _Uncertainty-based information: Elements of generalized information theory_ , volume 15.  Springer, 1999.
  * Lambrou et al. (2011) Lambrou, A., Papadopoulos, H., and Gammerman, A.  Reliable confidence measures for medical diagnosis with evolutionary algorithms.  _IEEE Transactions on Information Technology in Biomedicine_ , 15(1):93–99, 2011.
  * Liu & Dietterich (2012) Liu, L. and Dietterich, T. G.  A conditional multinomial mixture model for superset label learning.  In _Neural Information Processing Systems_ , pp. 557–565, 2012.
  * Lv et al. (2020) Lv, J., Xu, M., Feng, L., Niu, G., Geng, X., and Sugiyama, M.  Progressive identification of true labels for partial-label learning.  In _ACM International Conference on Machine Learning_ , volume 119, pp. 6500–6510, 2020.
  * Matthews (1975) Matthews, B. W.  Comparison of the predicted and observed secondary structure of T4 phage lysozyme.  _Biochimica et Biophysica Acta_ , 405(2):442–451, 1975.
  * Meyerowitz et al. (1994) Meyerowitz, A., Richman, F., and Walker, E.  Calculating maximum-entropy probability densities for belief functions.  _International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems_ , 2(04):377–389, 1994.
  * Michelmore et al. (2020) Michelmore, R., Wicker, M., Laurenti, L., Cardelli, L., Gal, Y., and Kwiatkowska, M.  Uncertainty quantification with statistical guarantees in end-to-end autonomous driving control.  In _IEEE International Conference on Robotics and Automation_ , pp. 7344–7350, 2020.
  * Natarajan et al. (2013) Natarajan, N., Dhillon, I. S., Ravikumar, P., and Tewari, A.  Learning with noisy labels.  In _Neural Information Processing Systems_ , pp. 1196–1204, 2013.
  * Nguyen & Caruana (2008) Nguyen, N. and Caruana, R.  Classification with partial labels.  In _ACM Conference on Knowledge Discovery and Data Mining_ , pp. 551–559, 2008.
  * Ni et al. (2021) Ni, P., Zhao, S., Dai, Z., Chen, H., and Li, C.  Partial label learning via conditional-label-aware disambiguation.  _Journal of Computer Science and Technology_ , 36(3):590–605, 2021.
  * Omohundro (1989) Omohundro, S. M.  _Five balltree construction algorithms_.  Berkeley, 1989.
  * Reamaroon et al. (2019) Reamaroon, N., Sjoding, M. W., Lin, K., Iwashyna, T. J., and Najarian, K.  Accounting for label uncertainty in machine learning for detection of acute respiratory distress syndrome.  _IEEE Journal of Biomedical and Health Informatics_ , 23(1):407–415, 2019.
  * Sale et al. (2023) Sale, Y., Caprio, M., and Hüllermeier, E.  Is the volume of a credal set a good measure for epistemic uncertainty?  In _Uncertainty in Artificial Intelligence_ , volume 216, pp. 1795–1804, 2023.
  * Senge et al. (2014) Senge, R., Bösner, S., Dembczynski, K., Haasenritter, J., Hirsch, O., Donner-Banzhoff, N., and Hüllermeier, E.  Reliable classification: Learning classifiers that distinguish aleatoric and epistemic uncertainty.  _Information Sciences_ , 255:16–29, 2014.
  * Shafaei et al. (2018) Shafaei, S., Kugele, S., Osman, M. H., and Knoll, A. C.  Uncertainty in machine learning: A safety perspective on autonomous driving.  In _Computer Safety, Reliability, and Security_ , volume 11094, pp. 458–464, 2018.
  * Shafer (1986) Shafer, G.  The combination of evidence.  _Intelligent Systems_ , 1(3):155–179, 1986.
  * Shalev-Shwartz et al. (2007) Shalev-Shwartz, S., Singer, Y., and Srebro, N.  Pegasos: Primal Estimated sub-GrAdient SOlver for SVM.  In _ACM International Conference on Machine Learning_ , volume 227, pp. 807–814, 2007.
  * Tang & Zhang (2017) Tang, C. and Zhang, M.  Confidence-rated discriminative partial label learning.  In _AAAI Conference on Artificial Intelligence_ , pp. 2611–2617, 2017.
  * van Engelen & Hoos (2020) van Engelen, J. E. and Hoos, H. H.  A survey on semi-supervised learning.  _Springer Machine Learning_ , 109(2):373–440, 2020.
  * Varshney & Alemzadeh (2017) Varshney, K. R. and Alemzadeh, H.  On the safety of machine learning: Cyber-physical systems, decision sciences, and data products.  _Big Data_ , 5(3):246–255, 2017.
  * Wang et al. (2019) Wang, D., Li, L., and Zhang, M.  Adaptive graph guided disambiguation for partial label learning.  In _ACM International Conference on Knowledge Discovery and Data Mining_ , pp. 83–91, 2019.
  * Wang et al. (2022) Wang, H., Xiao, R., Li, Y., Feng, L., Niu, G., Chen, G., and Zhao, J.  PiCO: Contrastive label disambiguation for partial label learning.  In _International Conference on Learning Representations_ , 2022.
  * Wimmer et al. (2023) Wimmer, L., Sale, Y., Hofman, P., Bischl, B., and Hüllermeier, E.  Quantifying aleatoric and epistemic uncertainty in machine learning: Are conditional entropy and mutual information appropriate measures?  In _Uncertainty in Artificial Intelligence_ , volume 216, pp. 2282–2292, 2023.
  * Wu & Zhang (2018) Wu, X. and Zhang, M.  Towards enabling binary decomposition for partial label learning.  In _International Joint Conference on Artificial Intelligence_ , pp. 2868–2874, 2018.
  * Xu et al. (2019) Xu, N., Lv, J., and Geng, X.  Partial label learning via label enhancement.  In _AAAI Conference on Artificial Intelligence_ , pp. 5557–5564, 2019.
  * Xu et al. (2021) Xu, N., Qiao, C., Geng, X., and Zhang, M.  Instance-dependent partial label learning.  In _Neural Information Processing Systems_ , pp. 27119–27130, 2021.
  * Xu et al. (2014) Xu, W., Pan, J., Wei, J., and Dolan, J. M.  Motion planning under uncertainty for on-road autonomous driving.  In _IEEE International Conference on Robotics and Automation_ , pp. 2507–2512, 2014.
  * Yager (1987a) Yager, R. R.  On the Dempster-Shafer framework and new combination rules.  _Information Sciences_ , 41(2):93–137, 1987a.
  * Yager (1987b) Yager, R. R.  Quasi-associative operations in the combination of evidence.  _Kybernetes_ , 16(1):37–41, 1987b.
  * Yang et al. (2009) Yang, F., Wang, H., Mi, H., Lin, C., and Cai, W.  Using random forest for reliable classification and cost-sensitive learning for medical diagnosis.  _BMC Bioinformatics_ , 10(1), 2009.
  * Yu & Zhang (2017) Yu, F. and Zhang, M.  Maximum margin partial label learning.  In _Asian Conference on Machine Learning_ , volume 106, pp. 573–593, 2017.
  * Zadeh (1984) Zadeh, L. A.  Book review: A mathematical theory of evidence.  _AI Magazine_ , 5(3):81–83, 1984.
  * Zhang & Yu (2015) Zhang, M. and Yu, F.  Solving the partial label learning problem: An instance-based approach.  In _International Joint Conference on Artificial Intelligence_ , pp. 4048–4054, 2015.
  * Zhang et al. (2016) Zhang, M., Zhou, B., and Liu, X.  Partial label learning via feature-aware disambiguation.  In _ACM International Conference on Knowledge Discovery and Data Mining_ , pp. 1335–1344, 2016.
  * Zhang et al. (2017) Zhang, M., Yu, F., and Tang, C.  Disambiguation-free partial label learning.  _IEEE Transactions on Knowledge and Data Engineering_ , 29(10):2155–2167, 2017.

##  Appendix A Proofs

This section collects our proofs. The proof of Lemmas 5.4 is in Appendix A.1,
Lemma 5.7 is proved in Appendix A.2, and Appendix A.3 contains the proof of
Lemma 5.8. We prove our main statement in Appendix A.4.

###  A.1 Proof of Lemma 5.4

($\Rightarrow$): Given $\tilde{y}\in\tilde{s}$, assume that
$\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)>1/2$.
By the definition of belief (1),
$\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)=\operatorname{\tilde{m}}\\!\left(\left\\{\tilde{y}\right\\}\right)$,
so $\operatorname{\tilde{m}}\\!\left(\left\\{\tilde{y}\right\\}\right)>1/2$.
As
$\sum_{A\subseteq\operatorname{\mathcal{Y}}}\operatorname{\tilde{m}}\\!\left(A\right)=1$,
it holds that
$\sum_{A\subseteq\operatorname{\mathcal{Y}},\,A\neq\left\\{\tilde{y}\right\\}}\operatorname{\tilde{m}}\\!\left(A\right)<1/2$.
Then, for all $y\in\tilde{s}$ with $y\neq\tilde{y}$,
$\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)=\sum_{A\subseteq\operatorname{\mathcal{Y}},\,A\cap\left\\{y\right\\}\neq\emptyset}\operatorname{\tilde{m}}\\!\left(A\right)<1/2$.
Hence,
$\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)<\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)$
for all $y\in\tilde{s}$ with $y\neq\tilde{y}$. By the definition of
plausibility (2),
$\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\geq\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)$.
Therefore,
$\operatorname{pl}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y\right\\}\right)\geq\max_{y^{\prime}\in\tilde{s}}\,\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{y^{\prime}\right\\}\right)$
is only satisfied for $y=\tilde{y}$.

($\nLeftarrow$): Example 7 provides a counter-example.

###  A.2 Proof of Lemma 5.7

The expected belief of $\tilde{y}$ is given by (29). The non-negativity of the
binomial coefficients implies that it is sufficient to show that

$\binom{k-h}{i}\prod_{a=1}^{l-2}\binom{k-h}{j_{a}}\geq\sum_{b=1}^{\min\left(i,j_{1},j_{2},\dots,j_{l-2}\right)}\left(-1\right)^{b+1}\binom{k-h}{b}\binom{k-h-b}{i-b}\prod_{c=1}^{l-2}\binom{k-h-b}{j_{c}-b}\text{,}$
(10)

where $k\in\mathbb{N}$, $h,i,j_{a}\in\mathbb{N}_{0}$ with $0\leq i<k-h$ and
$0\leq j_{a}<k-h$ with $a\in[l-2]$, and that the inequality is strict in at
least one case.

The proof of (10) proceeds by induction over $k$. Note that the choices of $i$
and $j_{a}$ are interchangeable (see Appendix B). Hence, w.l.o.g., we assume
for the remainder of this proof that $i\leq j_{a}$ for all
$a\in\left[l-2\right]$. Further, we set $k^{\prime}=k-h\in\mathbb{N}$.

_Proposition._ For $k^{\prime}\in\mathbb{N}$, it holds that

$\binom{k^{\prime}}{i}\prod_{a=1}^{l-2}\binom{k^{\prime}}{j_{a}}\geq\sum_{b=1}^{i}\left(-1\right)^{b+1}\binom{k^{\prime}}{b}\binom{k^{\prime}-b}{i-b}\prod_{c=1}^{l-2}\binom{k^{\prime}-b}{j_{c}-b}\text{,}$
(11)

with $0\leq i\leq j_{a}<k^{\prime}$ for all $a\in\left[l-2\right]$.

_Base case._ For $k^{\prime}=1$, it holds that $h=i=j_{a}=0$
($a\in\left[l-2\right]$). Then, all binomial coefficients on the l.h.s. are
$1$. The sum on the r.h.s. is empty and thus $0$. Hence, l.h.s. $>$ r.h.s.
($1>0$), which also renders (29) strictly positive.

_Induction step._ Let $k^{\prime}=k^{\prime}+1$. The l.h.s. yields

$\displaystyle\
\binom{k^{\prime}+1}{i}\prod_{a=1}^{l-2}\binom{k^{\prime}+1}{j_{a}}\stackrel{{\scriptstyle(i)}}{{=}}\left(\frac{k^{\prime}+1}{k^{\prime}+1-i}\prod_{a=1}^{l-2}\frac{k^{\prime}+1}{k^{\prime}+1-j_{a}}\right)\binom{k^{\prime}}{i}\prod_{a=1}^{l-2}\binom{k^{\prime}}{j_{a}}$
(12) $\displaystyle\stackrel{{\scriptstyle(ii)}}{{\geq}}$ $\displaystyle\
\left(\frac{k^{\prime}+1}{k^{\prime}+1-i}\prod_{a=1}^{l-2}\frac{k^{\prime}+1}{k^{\prime}+1-j_{a}}\right)\sum_{b=1}^{i}\left(-1\right)^{b+1}\binom{k^{\prime}}{b}\binom{k^{\prime}-b}{i-b}\prod_{c=1}^{l-2}\binom{k^{\prime}-b}{j_{c}-b}$
(13) $\displaystyle\stackrel{{\scriptstyle(iii)}}{{=}}$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\frac{k^{\prime}+1}{k^{\prime}+1-i}\binom{k^{\prime}}{b}\binom{k^{\prime}-b}{i-b}\prod_{c=1}^{l-2}\frac{k^{\prime}+1}{k^{\prime}+1-j_{c}}\binom{k^{\prime}-b}{j_{c}-b}$
(14) $\displaystyle\stackrel{{\scriptstyle(iv)}}{{=}}$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\underbrace{\frac{k^{\prime}+1}{k^{\prime}+1-b}\binom{k^{\prime}}{b}}_{\stackrel{{\scriptstyle(i^{\prime})}}{{=}}\binom{k^{\prime}+1}{b}}\underbrace{\frac{k^{\prime}+1-b}{k^{\prime}+1-i}\binom{k^{\prime}-b}{i-b}}_{\stackrel{{\scriptstyle(i^{\prime})}}{{=}}\binom{k^{\prime}+1-b}{i-b}}\prod_{c=1}^{l-2}\frac{k^{\prime}+1}{k^{\prime}+1-b}\underbrace{\frac{k^{\prime}+1-b}{k^{\prime}+1-j_{c}}\binom{k^{\prime}-b}{j_{c}-b}}_{\stackrel{{\scriptstyle(i^{\prime})}}{{=}}\binom{k^{\prime}+1-b}{j_{c}-b}}$
(15) $\displaystyle\stackrel{{\scriptstyle(v)}}{{=}}$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\frac{k^{\prime}+1}{k^{\prime}+1-b}\right)^{l-2}\binom{k^{\prime}+1}{b}\binom{k^{\prime}+1-b}{i-b}\prod_{c=1}^{l-2}\binom{k^{\prime}+1-b}{j_{c}-b}$
(16) $\displaystyle\stackrel{{\scriptstyle(vi)}}{{\geq}}$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\binom{k^{\prime}+1}{b}\binom{k^{\prime}+1-b}{i-b}\prod_{c=1}^{l-2}\binom{k^{\prime}+1-b}{j_{c}-b}\text{,}$
(17)

where $(i)$ holds as

$\displaystyle\binom{k^{\prime}+1}{i}=\frac{(k^{\prime}+1)!}{i!(k^{\prime}+1-i)!}=\frac{k^{\prime}+1}{k^{\prime}+1-i}\frac{k^{\prime}!}{i!(k^{\prime}-i)!}=\frac{k^{\prime}+1}{k^{\prime}+1-i}\binom{k^{\prime}}{i},$

the proposition yields $(ii)$, in $(iii)$ we rearrange the sum and collect
both products, and $(iv)$ expands the fractions. In $(v)$, we rearrange the
factor within the product and apply the $(i^{\prime})$-s, which hold by
similar calculations as $(i)$, and Lemma B.1 with $k=k^{\prime}+1$ implies
$(vi)$. These derivations and the observation that the base case guaranteed
the inequality to be strict conclude the proof.

###  A.3 Proof of Lemma 5.8

By comparing the closed-form expressions (with $m=i=t$) of $\tilde{y}$ and
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ given in (29) and
(34), respectively, we obtain

$\displaystyle\
\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\left[\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\right]>\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\left[\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}(\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\\})\mid
X=\tilde{x}\right]\Leftrightarrow\left(\frac{1}{2^{l-2}}p_{2}\right)^{k-h-m}>\left(\frac{1}{2^{l-1}-1}p_{3}\right)^{k-h-m}$
(18) $\displaystyle\Leftrightarrow$ $\displaystyle\
\frac{1}{2^{l-2}}p_{2}>\frac{1}{2^{l-1}-1}p_{3}\
\stackrel{{\scriptstyle(i)}}{{\Leftrightarrow}}\ \frac{2^{l-1}-1}{2^{l-2}}>1\
\Leftrightarrow\ 2^{l-2}>1\text{,}$ (19)

where $(i)$ holds as Assumption 5.5 guarantees that $p_{2}\geq p_{3}>0$. The
last statement is satisfied for $l\geq 3$, which shows that the dominance
assumption w.r.t. the label distribution propagates through the computation of
belief when using Yager’s rule. We note that the result is independent of
$p_{1}$ as a candidate set can not distinguish the belief in $\tilde{y}$ and
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ when these cooccur.

###  A.4 Proof of Theorem 5.9

With Assumption 5.5, the proof of Theorem 5.9 is a consequence of Lemma 5.7
and 5.8. We detail this in the following.

Part $(i)$. Let $\tilde{x}\in\operatorname{\mathcal{X}}$ be a fixed instance
with unknown true label $\tilde{y}$. Our algorithm is trained with $n$ samples
$\left(\left(x_{i},s_{i}\right)\right)_{i=1}^{n}\overset{\text{i.i.d.}}{\sim}\operatorname{\mathbb{P}}_{XS}$
that satisfy the label distribution in Assumption 5.5. Especially, the
dominance of the true label $\tilde{y}$ within $\tilde{x}$’s neighborhood of
$k$ instances $x_{i}$ holds. Since the expected belief in $\tilde{y}$ is
positive (Lemma 5.7), that is,
$\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\big{]}>0$, we are, in expectation, in the first case of our two-
case decision rule (Section 5.2). Furthermore, label $\tilde{y}$ has, in
expectation, the maximum belief among all labels because the dominance of
label $\tilde{y}$ in the neighborhood propagates to the belief in label
$\tilde{y}$ by Lemma 5.8, that is,
$\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\big{]}>\mathbb{E}_{\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}(\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\\})\mid
X=\tilde{x}\big{]}$. Therefore, in expectation, it must hold that, given an
instance $\tilde{x}$, we consistently predict the true label $\tilde{y}$, that
is,
$\operatorname{\mathbb{E}}_{\left(\left(x_{i},s_{i}\right)\right)_{i=1}^{n}\overset{\text{i.i.d.}}{\sim}\,\operatorname{\mathbb{P}}_{XS}}\\!\left[g_{n}\\!\left(\tilde{x}\right)\right]=\tilde{y}$.

Part $(ii)$. Given $n$ samples
$\left(\left(x_{i},s_{i}\right)\right)_{i=1}^{n}\overset{\text{i.i.d.}}{\sim}\operatorname{\mathbb{P}}_{XS}$
and the classifier $g_{n}$, the expected empirical risk is

$\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}}\\!\left[\hat{\operatorname{\mathcal{R}}}\\!\left(g_{n}\right)\right]=\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}}\\!\left[\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathcal{L}}\\!\left(g_{n}\\!\left(x_{i}\right),y_{i}\right)\right]=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}}\\!\left[\operatorname{\mathcal{L}}\\!\left(g_{n}\\!\left(x_{i}\right),y_{i}\right)\right]\overset{(i)}{=}0\text{,}$
(20)

which is zero by part $(i)$ of the statement as, in expectation, we
consistently predict the true label $y_{i}$ for any fixed label $x_{i}$. We
note that one cannot compute the empirical risk, in practice, as the ground-
truth labels $y_{i}$ are unknown. Fixing a label distribution in Assumption
5.5, however, allows us to deal with the classification risk directly rather
than using a proxy loss as common in the literature (Cour et al., 2011; Feng
et al., 2020b). By the law of large numbers, we have

$\lim_{n\to\infty}\hat{\operatorname{\mathcal{R}}}\\!\left(g_{n}\right)=\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathcal{L}}\\!\left(g_{n}\\!\left(x_{i}\right),y_{i}\right)=0\text{,}$
(21)

almost surely, because
$\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}}\\!\big{[}\hat{\operatorname{\mathcal{R}}}\\!\left(g_{n}\right)\big{]}=0$
as stated above. As $\operatorname{\mathcal{R}}\\!\left(g^{*}\right)\geq 0$,
we conclude

$0\leq\lim_{n\to\infty}\left(\operatorname{\mathcal{R}}\\!\left(g_{n}\right)-\operatorname{\mathcal{R}}\\!\left(g^{*}\right)\right)\leq\lim_{n\to\infty}\operatorname{\mathcal{R}}\\!\left(g_{n}\right)=0\text{,}$
(22)

which establishes $(ii)$.

##  Appendix B Auxiliary Results

This section lists results underpinning the findings in Appendix A. Section
B.1 introduces a closed-form expression of the expected belief. Section B.2
presents Lemma B.1, which is needed in the proof of Lemma 5.7.

###  B.1 Expected Belief

This section, first, presents a closed-form expression for the expected belief
in $\tilde{y}$ and $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$.
Second, we compare the computation with a simulation to numerically validate
our closed-form expression and the results in Appendix A.

Closed-form expression. Let $\tilde{x}\in\operatorname{\mathcal{X}}$ be the
instance of interest with hidden true label
$\tilde{y}\in\operatorname{\mathcal{Y}}$ and $k$ associated neighbors
$\left(x_{i},s_{i}\right)\in\operatorname{NN}_{k}\\!\left(\tilde{x}\right)$.
We recall that our label space $\operatorname{\mathcal{Y}}$ has $l\geq 3$
classes. Then, the expected belief in $\tilde{y}$ given instance $\tilde{x}$
is

$\displaystyle\
\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\big{]}\overset{(i)}{=}\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{\tilde{m}}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\big{]}$ (23) $\displaystyle\overset{(ii)}{=}$ $\displaystyle\
\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{q}\\!\left(\left\\{\tilde{y}\right\\}\right)\mid
X=\tilde{x}\big{]}\overset{(iii)}{=}\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\Big{[}\sum_{\begin{subarray}{c}A_{1},\ldots,A_{k}\subseteq\operatorname{\mathcal{Y}}\\\
\bigcap_{i=1}^{k}A_{i}=\left\\{\tilde{y}\right\\}\end{subarray}}\
\prod_{j=1}^{k}\operatorname{m}_{j}\\!\left(A_{j}\right)\mid
X=\tilde{x}\Big{]}$ (24) $\displaystyle\overset{(iv)}{=}$ $\displaystyle\
\underbrace{\sum_{h=0}^{k-1}\sum_{i=0}^{k-h-1}\sum_{j_{1}=0}^{k-h-1}\sum_{j_{2}=0}^{k-h-1}\dotsi\sum_{j_{l-2}=0}^{k-h-1}\sum_{\begin{subarray}{c}A_{1},\ldots,A_{k}\subseteq\operatorname{\mathcal{Y}}\text{;}\\\
B_{1},\ldots,B_{l}\subseteq\left[k\right]\\\ \text{with}\
|B_{1}|=h,|B_{2}|=i,\\\ |B_{q+2}|=j_{q}\ \text{for}\
q\in\left[l-2\right]\text{;}\\\ \tilde{y}\,\in\,A_{r}\ \text{for}\
r\,\in\,\left[k\right]\text{;}\\\ A_{r}\,=\,\operatorname{\mathcal{Y}}\
\text{for}\ r\,\in\,B_{1}\text{;}\\\
\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\in\,A_{r}\ \text{for}\
r\,\in\,B_{2}\text{;}\\\
\tilde{y}^{\left(\tilde{y}\right)}_{q+2}\in\,A_{r_{q}}\ \text{for}\
r_{q}\,\in\,B_{q+2}\\\ \text{and}\
q\,\in\,\left[l-2\right]\end{subarray}}}_{(v)}\\!\\!\\!\\!\underbrace{\big{(}\prod_{j=1}^{k}\operatorname{m}_{j}\\!\left(A_{j}\right)\big{)}}_{(vi)}\,\underbrace{\big{(}\prod_{j=1}^{k}\operatorname{\mathbb{P}}\\!\left(S=A_{j},Y=\tilde{y}\mid
X=x_{j}\right)\big{)}}_{(vii)}$ (25) $\displaystyle=$ $\displaystyle\
\sum_{h=0}^{k-1}\sum_{i=0}^{k-h-1}\sum_{j_{1}=0}^{k-h-1}\sum_{j_{2}=0}^{k-h-1}\dotsi\sum_{j_{l-2}=0}^{k-h-1}\underbrace{\sum_{\begin{subarray}{c}A_{1},\ldots,A_{k}\subseteq\operatorname{\mathcal{Y}}\text{;}\\\
B_{1},\ldots,B_{l}\subseteq\left[k\right]\\\ \text{with}\
|B_{1}|=h,|B_{2}|=i,\\\ |B_{q+2}|=j_{q}\ \text{for}\
q\in\left[l-2\right]\text{;}\\\ \tilde{y}\,\in\,A_{r}\ \text{for}\
r\,\in\,\left[k\right]\text{;}\\\ A_{r}\,=\,\operatorname{\mathcal{Y}}\
\text{for}\ r\,\in\,B_{1}\text{;}\\\
\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\in\,A_{r}\ \text{for}\
r\,\in\,B_{2}\text{;}\\\
\tilde{y}^{\left(\tilde{y}\right)}_{q+2}\in\,A_{r_{q}}\ \text{for}\
r_{q}\,\in\,B_{q+2}\\\ \text{and}\
q\,\in\,\left[l-2\right]\end{subarray}}}_{(viii)}\\!\\!\\!\\!\underbrace{\frac{1}{2^{k}}}_{(vi)}\underbrace{\left(\frac{1}{2^{l-2}-1}p_{1}\right)^{i}\left(\frac{1}{2^{l-2}}p_{2}\right)^{k-h-i}}_{(vii)}$
(26) $\displaystyle=$ $\displaystyle\
\sum_{h=0}^{k-1}\sum_{i=0}^{k-h-1}\sum_{j_{1}=0}^{k-h-1}\sum_{j_{2}=0}^{k-h-1}\dotsi\sum_{j_{l-2}=0}^{k-h-1}\Bigg{[}\underbrace{\binom{k}{k-h}\binom{k-h}{i}\prod_{a=1}^{l-2}\binom{k-h}{j_{a}}}_{(viii)}$
(27)
$\displaystyle\quad-\underbrace{\binom{k}{k-h}\sum_{b=1}^{\min\left(i,j_{1},j_{2},\dots,j_{l-2}\right)}\left(-1\right)^{b+1}\binom{k-h}{b}\binom{k-h-b}{i-b}\prod_{c=1}^{l-2}\binom{k-h-b}{j_{c}-b}}_{(viii)}\Bigg{]}$
(28) $\displaystyle\
\times\frac{1}{2^{k}}\left(\frac{1}{2^{l-2}-1}p_{1}\right)^{i}\left(\frac{1}{2^{l-2}}p_{2}\right)^{k-h-i}\text{.}$
(29)

In the following, we show that transformations $(i)$ – $(viii)$ hold.

  * •

In $(i)$, we apply Definition (1). The belief of any single-item set is equal
to the respective basic probability assignment value, that is,
$\operatorname{bel}^{\left(\operatorname{m}\right)}\\!\left(\left\\{y\right\\}\right)=\operatorname{m}\\!\left(\left\\{y\right\\}\right)$
for all $y\in\operatorname{\mathcal{Y}}$.

  * •

In $(ii)$, we apply Definition (4). For any $y\in\operatorname{\mathcal{Y}}$,
it holds that
$\operatorname{m}\\!\left(\left\\{y\right\\}\right)=\operatorname{q}\\!\left(\left\\{y\right\\}\right)$
as $\left\\{y\right\\}\neq\emptyset$ and
$\left\\{y\right\\}\neq\operatorname{\mathcal{Y}}$.

  * •

In $(iii)$, we insert Definition (3), that is, how all
$\operatorname{m}_{i}$-s as defined by Algorithm 1 are combined into
$\operatorname{q}$ using Yager’s rule (3).

  * •

In $(iv)$, we then compute the expected value by taking into account all
possible combinations of sets
$A_{1},\ldots,A_{k}\subseteq\operatorname{\mathcal{Y}}$ producing the
intersection $\left\\{\tilde{y}\right\\}$.

  * •

Term $(v)$ enumerates all cases where
$\bigcap_{r=1}^{k}A_{r}=\left\\{\tilde{y}\right\\}$. To produce this
intersection, label $\tilde{y}$ needs to be contained in all sets $A_{r}$. At
most $k-1$ sets can be the full label space, that is, $h$ sets satisfy
$A_{r}=\operatorname{\mathcal{Y}}$. The label
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ with which $\tilde{y}$
is most often confused has to be missing in at least one set $A_{r}$, that is,
$i$ sets $A_{r}$ satisfy
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\in A_{r}$. All
remaining labels
$\tilde{y}^{\left(\tilde{y}\right)}_{3},\ldots,\tilde{y}^{\left(\tilde{y}\right)}_{l}\in\operatorname{\mathcal{Y}}$
also have to be missing in at least one set $A_{r}$ each, that is, $j_{a}$
sets $A_{r}$ satisfy $\tilde{y}^{\left(\tilde{y}\right)}_{a+2}\in A_{r}$,
respectively.

  * •

Term $(vi)$ calculates the value that a given instantiation of all
$A_{1},\ldots,A_{k}$ has. Because we only sum over focal elements of the
$\operatorname{m}_{j}$-s ($j\in\left[k\right]$) by the construction of the sum
in $(v)$, term $(vi)$ simplifies to $1/2^{k}$. Recall that all focal sets have
a value of 1/2 (Algorithm 1; Line 6).

  * •

Expression $(vii)$ computes the probability that a given instantiation of all
$A_{1},\ldots,A_{k}$ has. The variables $h$, $i$, $j_{1}$, …, $j_{l-2}$
directly allow to quantify the probabilities in a way to apply Assumption 5.5,
which allows to simplify the expression.

  * •

As the summands within $(viii)$ do not depend on the $A_{1},\ldots,A_{k}$
anymore, we can simplify by counting their possible instantiations. We first
count the possible combinations of sets where we pick to intersect $h$-times
with the full label space and $\left(k-h\right)$-times with the neighbors’
candidate sets of which $i$ contain label
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ and $j_{a}$ contain
the remaining labels for all $a\in\left[l-2\right]$. Second, we need to
subtract all combinations that produce the whole label space within at least
one candidate set as the probability of
$s^{\prime}=\operatorname{\mathcal{Y}}$ is zero per Assumption 5.5. We do this
using an inclusion-exclusion strategy. We have $k-h$ sets with which we
intersect and that are not the full label space. Out of those $k-h$ sets, at
least one set ought to contain all possible labels leaving
$\binom{k-h-1}{i-1}$ and $\binom{k-h-1}{j_{c}-1}$ possibilities for the other
sets. This overcounts combinations though as multiple sets can contain all
labels. We employ the inclusion-exclusion strategy to remove combinations that
produce the same allocations of labels to sets.

Similar to (29), we also express the expected belief in the most frequently
cooccurring label $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ as

$\displaystyle\
\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{bel}^{\left(\operatorname{\tilde{m}}\right)}\\!\left(\left\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\right\\}\right)\mid
X=\tilde{x}\big{]}=\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{\tilde{m}}\\!\left(\left\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\right\\}\right)\mid
X=\tilde{x}\big{]}$ (30) $\displaystyle=$ $\displaystyle\
\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\big{[}\operatorname{q}\\!\left(\left\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\right\\}\right)\mid
X=\tilde{x}\big{]}=\operatorname{\mathbb{E}}_{\left(X,Y,S\right)\sim\operatorname{\mathbb{P}}}\\!\Big{[}\sum_{\begin{subarray}{c}A_{1},\ldots,A_{k}\subseteq\operatorname{\mathcal{Y}}\\\
\bigcap_{i=1}^{k}A_{i}=\left\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\right\\}\end{subarray}}\
\prod_{j=1}^{k}\operatorname{m}_{j}\\!\left(A_{j}\right)\mid
X=\tilde{x}\Big{]}$ (31) $\displaystyle=$ $\displaystyle\
\sum_{h=0}^{k-1}\sum_{t=0}^{k-h-1}\sum_{j_{1}=0}^{k-h-1}\sum_{j_{2}=0}^{k-h-1}\dotsi\sum_{j_{l-2}=0}^{k-h-1}\Bigg{[}\binom{k}{k-h}\binom{k-h}{t}\prod_{a=1}^{l-2}\binom{k-h}{j_{a}}$
(32)
$\displaystyle\quad-{\binom{k}{k-h}\sum_{b=1}^{\min\left(t,j_{1},j_{2},\dots,j_{l-2}\right)}\left(-1\right)^{b+1}\binom{k-h}{b}\binom{k-h-b}{t-b}\prod_{c=1}^{l-2}\binom{k-h-b}{j_{c}-b}}\Bigg{]}$
(33) $\displaystyle\
\times{\frac{1}{2^{k}}\left(\frac{1}{2^{l-2}-1}p_{1}\right)^{t}\left(\frac{1}{2^{l-1}-1}p_{3}\right)^{k-h-t}}\text{.}$
(34)

To produce the intersection
$\\{\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}\\}$ in Yager’s rule,
all $k-h$ sets with which we intersect need to contain
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$. The variable $t$
denotes how many out of $k-h$ sets contain the true label $\tilde{y}$.
Therefore, $\tilde{y}$ and
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ cooccur in a set in
$t$ cases, with which the probability $(\frac{1}{2^{l-2}-1}p_{1})^{t}$ is
associated. In $k-h-t$ sets, the true label is not contained, with which the
probability $(\frac{1}{2^{l-1}-1}p_{3})^{k-h-t}$ is associated according to
Assumption 5.5.

Figure 3: Comparison of simulating and calculating the expected belief in the
true label $\tilde{y}$ and in the most frequently cooccurring label
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ for
$k\in\left[100\right]$, $l=3$, $p_{1}=0.4$, $p_{2}=0.35$, and $p_{3}=0.25$.

Simulation. To simulate the expected belief, we randomly draw $k$ candidate
sets $s_{i}$ according to the label distribution in Assumption 5.5, apply
Algorithm 1, and report the belief of $\tilde{y}$ and
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$. We repeat this
$100\,000\text{\,}$ times and average the results. For $l=3$, $\tilde{y}=1$,
and $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}=2$, we obtain the
label distribution

$\displaystyle\operatorname{\mathbb{P}}\\!\left(S=\left\\{1,2\right\\},Y=1\mid
X=x_{i}\right)$ $\displaystyle=\phantom{\frac{1}{2}}\,p_{1}\text{,}$ (35)
$\displaystyle\operatorname{\mathbb{P}}\\!\left(S=\left\\{1\right\\},Y=1\mid
X=x_{i}\right)=\operatorname{\mathbb{P}}\\!\left(S=\left\\{1,3\right\\},Y=1\mid
X=x_{i}\right)$ $\displaystyle=\frac{1}{2}\,p_{2}\text{,}$ (36)
$\displaystyle\operatorname{\mathbb{P}}\\!\left(S=\left\\{2\right\\},Y=2\mid
X=x_{i}\right)=\operatorname{\mathbb{P}}\\!\left(S=\left\\{3\right\\},Y=3\mid
X=x_{i}\right)$ $\displaystyle=\frac{1}{3}\,p_{3}\text{,}$ (37)
$\displaystyle\operatorname{\mathbb{P}}\\!\left(S=\left\\{2,3\right\\},Y=2\mid
X=x_{i}\right)=\operatorname{\mathbb{P}}\\!\left(S=\left\\{2,3\right\\},Y=3\mid
X=x_{i}\right)$ $\displaystyle=\frac{1}{6}\,p_{3}\text{,}$ (38)

regarding a neighboring instance $x_{i}$ with $i\in\left[k\right]$. All other
probabilities that are not listed are zero. Naturally,
$\sum_{s^{\prime}\subseteq\operatorname{\mathcal{Y}}}\sum_{y^{\prime}\in\operatorname{\mathcal{Y}}}\operatorname{\mathbb{P}}\\!\left(S=s^{\prime},Y=y^{\prime}\mid
X=x_{i}\right)=p_{1}+2\frac{1}{2}p_{2}+2\frac{1}{3}p_{3}+2\frac{1}{6}p_{3}=1$.

Figure 3 compares the computation and simulation of the expected belief. The
values of the computation and simulation are indiscernible. Note that the
expected belief in any single-item set converges towards zero as $k$
increases. The more sets one intersects with in (3), the more likely it is to
produce the empty set. As shown in Lemma 5.8, the expected belief in
$\tilde{y}$ is greater than the belief in
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$, independently from
the number of neighbors $k\in\mathbb{N}$.

###  B.2 Auxiliary Lemma to the Proof of Lemma 5.7

This section presents an auxiliary inequality, which is used in the proof of
Lemma 5.7.

######  Lemma B.1.

Let $l\in\mathbb{N}$ with $l\geq 3$ denote the number of class labels and
$k\in\mathbb{N}$ the number of neighbors. Let further
$i,j_{a}\in\mathbb{N}_{0}$ with $0\leq i\leq j_{a}<k$ for all
$a\in\left[l-2\right]$. Then, it holds that

$\displaystyle\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\frac{k}{k-b}\right)^{l-2}\binom{k}{b}\binom{k-b}{i-b}\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}\
\geq\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\binom{k}{b}\binom{k-b}{i-b}\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}\text{.}$
(39)

###### Proof.

We first transform the statement as

$\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\frac{k}{k-b}\right)^{l-2}\binom{k}{b}\binom{k-b}{i-b}\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}\
\geq\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\binom{k}{b}\binom{k-b}{i-b}\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}$
(40) $\displaystyle\Leftrightarrow$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\left(\frac{k}{k-b}\right)^{l-2}-1\right)\binom{k}{b}\binom{k-b}{i-b}\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}\
\geq\ 0\text{.}$ (41)

We then write the latter as

$\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\underbrace{\left(\left(\frac{k}{k-b}\right)^{l-2}-1\right)}_{(i)}\binom{k}{b}\binom{k-b}{i-b}\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}$
(42) $\displaystyle=$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b}\right)^{c}\right)\frac{b}{k-b}\binom{k}{b}\binom{k-b}{i-b}\underbrace{\prod_{c=1}^{l-2}\binom{k-b}{j_{c}-b}}_{(ii)}$
(43) $\displaystyle=$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b}\right)^{c}\right)\underbrace{\frac{b}{k-b}\binom{k}{b}\binom{k-b}{i-b}\binom{k-b}{j_{1}-b}}_{\text{(iii)}}\prod_{c=2}^{l-2}\binom{k-b}{j_{c}-b}$
(44) $\displaystyle=$ $\displaystyle\
\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b}\right)^{c}\right)\frac{i}{k-j_{1}}\binom{k}{i}\binom{i-1}{b-1}\binom{k-b-1}{j_{1}-b}\prod_{c=2}^{l-2}\binom{k-b}{j_{c}-b}$
(45) $\displaystyle\overset{(iv)}{=}$ $\displaystyle\
\frac{i}{k-j_{1}}\binom{k}{i}\sum_{b=1}^{i}\left(-1\right)^{b+1}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b}\right)^{c}\right)\binom{i-1}{b-1}\binom{k-b-1}{j_{1}-b}\prod_{c=2}^{l-2}\binom{k-b}{j_{c}-b}$
(46) $\displaystyle\overset{(v)}{=}$ $\displaystyle\
\frac{i}{k-j_{1}}\binom{k}{i}\sum_{b=0}^{i-1}\left(-1\right)^{b}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b-1}\right)^{c}\right)\underbrace{\binom{i-1}{b}\binom{k-b-2}{j_{1}-b-1}}_{\text{(vi)}}\prod_{c=2}^{l-2}\binom{k-b-1}{j_{c}-b-1}$
(47) $\displaystyle=$ $\displaystyle\
\frac{i}{k-j_{1}}\binom{k}{i}\sum_{b=0}^{i-1}\left(-1\right)^{b}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b-1}\right)^{c}\right)\left(-1\right)^{-b}\binom{k-i-1}{j_{1}-1}\prod_{c=2}^{l-2}\binom{k-b-1}{j_{c}-b-1}$
(48) $\displaystyle\overset{(vii)}{=}$ $\displaystyle\
\frac{i}{k-j_{1}}\binom{k}{i}\binom{k-i-1}{j_{1}-1}\sum_{b=0}^{i-1}\left(\sum_{c=0}^{l-3}\left(\frac{k}{k-b-1}\right)^{c}\right)\prod_{c=2}^{l-2}\binom{k-b-1}{j_{c}-b-1}\geq
0\text{,}$ (49)

which shows the statement to be demonstrated as the last term is a sum of
products whose factors are all non-negative. Recall that $0\leq i\leq j_{a}<k$
for all $a\in\left[l-2\right]$. In the following, we show that all
transformations are sound.

  * •

Using Theorem 66, $(i)$ holds as

$\displaystyle\left(\frac{k}{k-b}\right)^{l-2}-1$
$\displaystyle=\left(\left(\frac{k}{k-b}\right)^{l-2}-\left(\frac{k}{k-b}\right)^{l-3}\right)+\left(\left(\frac{k}{k-b}\right)^{l-3}-\left(\frac{k}{k-b}\right)^{l-4}\right)+\cdots+\left(\frac{k}{k-b}-1\right)$
(50)
$\displaystyle=\left(\frac{k}{k-b}-1\right)\left(\left(\frac{k}{k-b}\right)^{l-3}+\left(\frac{k}{k-b}\right)^{l-4}+\cdots+1\right)$
(51)
$\displaystyle=\left(\frac{k}{k-b}-1\right)\sum_{c=0}^{l-3}\left(\frac{k}{k-b}\right)^{c}=\frac{b}{k-b}\sum_{c=0}^{l-3}\left(\frac{k}{k-b}\right)^{c}\text{.}$
(52)

  * •

In $(ii)$, we extract the first factor of the product such that it starts with
$c=2$.

  * •

Subsequently, we transform the binomial coefficients $(iii)$ as

$\displaystyle\ \frac{b}{k-b}\binom{k}{b}\binom{k-b}{i-b}\binom{k-b}{j_{1}-b}$
(53) $\displaystyle\overset{\text{\eqref{ext:binom-transform}}}{=}$
$\displaystyle\ \frac{b}{k-b}\binom{k}{i}\binom{i}{b}\binom{k-b}{j_{1}-b}$
(54) $\displaystyle\overset{\text{\eqref{ext:binom-coeff}}}{=}$
$\displaystyle\
\frac{b}{k-b}\frac{i!}{b!\left(i-b\right)!}\frac{\left(k-b\right)!}{\left(j_{1}-b\right)!\left(k-j_{1}\right)!}\binom{k}{i}$
(55) $\displaystyle\overset{(viii)}{=}$ $\displaystyle\
\frac{i}{k-j_{1}}\frac{\left(i-1\right)!}{\left(b-1\right)!\left(i-b\right)!}\frac{\left(k-b-1\right)!}{\left(j_{1}-b\right)!\left(k-j_{1}-1\right)!}\binom{k}{i}$
(56) $\displaystyle\overset{\text{\eqref{ext:binom-coeff}}}{=}$
$\displaystyle\
\frac{i}{k-j_{1}}\binom{k}{i}\binom{i-1}{b-1}\binom{k-b-1}{j_{1}-b}\text{,}$
(57)

where $(viii)$ rearranges terms.

  * •

Then, in $(iv)$, we move terms that are independent of $b$ outside of the
summation.

  * •

In $(v)$, we shift the summation to start at $b=0$.

  * •

Finally, by defining $r=j_{1}-b-1\in\mathbb{N}_{0}$, we express $(vi)$ as

$\displaystyle\binom{i-1}{b}\binom{k-b-2}{j_{1}-b-1}=$ $\displaystyle\
\binom{i-1}{b}\binom{r+k-j_{1}-1}{r}$ (58)
$\displaystyle\overset{\text{(\ref{ext:binom-minus-one})}}{=}$ $\displaystyle\
\left(-1\right)^{r}\binom{i-1}{b}\binom{j_{1}-k}{r}$ (59)
$\displaystyle\overset{(ix)}{=}$ $\displaystyle\
\left(-1\right)^{r}\sum_{\begin{subarray}{c}b^{\prime}\\!,\,r^{\prime}\in\,\mathbb{N}_{0}\\\
b^{\prime}+r^{\prime}=j_{1}-1\end{subarray}}\binom{i-1}{b^{\prime}}\binom{j_{1}-k}{r^{\prime}}$
(60) $\displaystyle\overset{\text{(\ref{ext:vandermonde})}}{=}$
$\displaystyle\ \left(-1\right)^{j_{1}-b-1}\binom{i+j_{1}-k-1}{j_{1}-1}$ (61)
$\displaystyle\overset{\text{(\ref{ext:binom-minus-one})}}{=}$ $\displaystyle\
\left(-1\right)^{j_{1}-b-1}\left(-1\right)^{j_{1}-1}\binom{k-i-1}{j_{1}-1}$
(62) $\displaystyle=$ $\displaystyle\
\left(-1\right)^{-b}\binom{k-i-1}{j_{1}-1}\text{.}$ (63)

Thereby, $(ix)$ holds as all summands that are introduced by
$\sum_{b^{\prime}+r^{\prime}=j_{1}-1}\binom{i-1}{b^{\prime}}\binom{j_{1}-k}{r^{\prime}}$
are zero. The only non-zero summand is for $b^{\prime}=b$ and $r^{\prime}=r$,
that is, $b+r=j_{1}-1$. In general, $\binom{m}{n}=0$ if $0\leq m<n$ for
$m\in\mathbb{R}$ and $n\in\mathbb{N}_{0}$.

∎

##  Appendix C External Theorems

This section collects identities and theorems that we use in the proofs of our
statements.

######  Definition C.1.

(Binomial coefficients; Graham et al. 1994, p. 154). When both arguments of a
binomial coefficient are natural, one defines

$\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}\text{,}$ (64)

for $n,k\in\mathbb{N}_{0}$ with $n\geq k\geq 0$. One extends this definition
using falling factorials
$r^{\underline{m}}:=\prod_{i=0}^{m-1}\left(r-i\right)$ for any
$r\in\mathbb{R}$ and $m\in\mathbb{N}_{0}$. Binomial coefficients are then
expressed as

$\binom{r}{m}=\frac{r^{\underline{m}}}{m!}\text{,}$ (65)

which allows for real arguments $r$.

######  Theorem C.2.

(Binomial theorem; Graham et al. 1994, p. 162). Given $x,y\in\mathbb{R}$ and
$n\in\mathbb{N}_{0}$, the binomial theorem states

$\left(x+y\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}\text{.}$ (66)

######  Theorem C.3.

(Graham et al. 1994, p. 164). As a special case of the binomial theorem, one
obtains

$\left(-1\right)^{k}\binom{-r}{k}=\binom{r+k-1}{k}\text{,}$ (67)

for $r\in\mathbb{R}$ and $k\in\mathbb{N}_{0}$.

######  Theorem C.4.

(Graham et al. 1994, p. 168). Given $r\in\mathbb{R}$ and
$m,k\in\mathbb{N}_{0}$ with $m\geq k$, it holds that

$\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}\text{.}$ (68)

######  Theorem C.5.

(Chu-Vandermonde identity; Graham et al. 1994, p. 169). Given
$s,t\in\mathbb{R}$ and $n\in\mathbb{N}_{0}$, the Chu-Vandermonde identity
states

$\binom{s+t}{n}=\sum_{k=0}^{n}\binom{s}{k}\binom{t}{n-k}\text{.}$ (69)

##  Appendix D Additional Experiments

This section contains additional experiments: Section D.1 provides experiments
justifying Assumption 5.5. Section D.2 compares the performance of all
approaches on the controlled experiments regarding accuracy. Section D.3
provides the calibration trade-off value $O_{\beta}$ regarding accuracy and
the parameter sensitivity is discussed in Section D.4.

###  D.1 Applicability of Assumption 5.5

Given a fixed instance $\tilde{x}$, Assumption 5.5 describes the label
distribution of the neighbors’ candidate sets. Thereby, we assume that the
true label $\tilde{y}$ dominates the neighborhood. Label
$\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$ cooccurs most often
with the true label $\tilde{y}$. Otherwise, we assume uniform noise among the
remaining noise labels.

Figure 4 demonstrates that those assumptions are satisfied for most of the
five real-world datasets (see Section 6.3). In most cases, the true label
$\tilde{y}$ occurs most often in the neighborhood of instance $\tilde{x}$.
There are one or two other labels with which $\tilde{y}$ is commonly confused,
which we model by $\tilde{y}^{\left(\tilde{y}\right)}_{\operatorname{c}}$.
Apart from that, all remaining noise labels are distributed uniformly.

(a) Dataset BirdSong.

(b) Dataset MirFlickr.

(c) Dataset Lost.

(d) Dataset MsrcV2.

(e) Dataset YahooNews.

Figure 4:  Counts of the class labels in the candidate sets $s_{i}$ of
instance $\tilde{x}$’s 10-nearest neighbors $x_{i}$.

###  D.2 Controlled Experiments

(a) Prediction performance.

(b) Confidence calibration.

Figure 5: Evaluation on all nine UCI datasets (see Table 1) and all
experimental settings.

Similar to the experiments in Section 6.2, we also provide performance results
for the accuracy metric. Figure 5(a) shows the test-set accuracy of all nine
methods on the nine artificially augmented datasets. While our method (Dst-
Pll) performs competitively, no approach consistently performs best across all
datasets. Our algorithm performs most similarly to Pl-Knn as both are nearest-
neighbor approaches.

Figure 5(b) shows the calibration of confident predictions regarding accuracy.
Pl-Knn and Dst-Pll provide the most accurate confident predictions (y-axis).
However, Dst-Pll gives roughly twice as many confident predictions (x-axis).

###  D.3 Calibration Trade-Off

Figure 6: Sensitivity of $k$ regarding the test-set MCC score, the fraction, and the MCC score of confident predictions. Table 4: Trade-off $O_{\beta}$ between $O_{\operatorname{perf}}^{\left(\operatorname{acc}\right)}$ and $O_{\operatorname{frac}}$ for all datasets regarding parameter $\beta\in\left\\{0.5,0.6,\dots,1.0\right\\}$. Approach |  Trade-off value $O_{\beta}$ for all nine UCI datasets |  Trade-off value $O_{\beta}$ for all five real-world datasets
---|---|---
| 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0
Pl-Knn | $0.582$ | $0.662$ | $0.742$ | $0.822$ | $0.902$ | $0.982$ | $0.445$ | $0.514$ | $0.583$ | $0.652$ | $0.721$ | $0.789$
Pl-Svm | $0.478$ | $0.521$ | $0.564$ | $0.608$ | $0.651$ | $0.694$ | $0.368$ | $0.416$ | $0.464$ | $0.513$ | $0.561$ | $0.609$
Clpl | $0.652$ | $0.672$ | $0.692$ | $0.712$ | $0.732$ | $0.752$ | $0.485$ | $0.509$ | $0.533$ | $0.556$ | $0.580$ | $0.604$
Lsb-Cmm | $0.743$ | $0.764$ | $0.786$ | $0.807$ | $0.828$ | $0.849$ | $0.619$ | $0.653$ | $0.686$ | $0.719$ | $0.752$ | $0.786$
Ipal | $0.818$ | $0.827$ | $0.836$ | $0.846$ | $0.855$ | $0.864$ | $0.684$ | $0.691$ | $0.698$ | $0.705$ | $0.711$ | $0.718$
M3Pl | $0.701$ | $0.725$ | $0.749$ | $0.773$ | $0.797$ | $0.821$ | $0.664$ | $0.679$ | $0.693$ | $0.708$ | $0.722$ | $0.737$
Paloc | $0.261$ | $0.262$ | $0.263$ | $0.264$ | $0.265$ | $0.266$ | $0.000$ | $0.000$ | $0.000$ | $0.000$ | $0.000$ | $0.000$
Sure | $0.132$ | $0.158$ | $0.184$ | $0.209$ | $0.235$ | $0.261$ | $0.040$ | $0.048$ | $0.056$ | $0.064$ | $0.072$ | $0.080$
Dst-Pll | $0.693$ | $0.751$ | $0.808$ | $0.866$ | $0.923$ | $0.981$ | $0.535$ | $0.607$ | $0.680$ | $0.752$ | $0.825$ | $0.897$

Similar to Section 6.2 and 6.3, Table 4 provides the trade-off value
$O_{\beta}$ between the accuracy of confident predictions
($O_{\operatorname{perf}}^{(\operatorname{acc})}$) and their fraction among
all predictions ($O_{\operatorname{frac}}$). The results are in agreement with
the findings in Table 2: Ipal is preferred when having accurate confident
prediction and a big number of them is roughly equally important
($\beta\in\left\\{0.5,0.6,0.7\right\\}$). When accurate confident predictions
are more important than a big number of them
($\beta\in\left\\{0.8,0.9,1.0\right\\}$), Dst-Pll provides the best trade-off.

###  D.4 Parameter Sensitivity

Figure 6 shows the sensitivity of the number of neighbors $k$ regarding the
test-set performance, the fraction of confident predictions, and the confident
prediction performance. The shaded areas indicate the standard deviation
regarding the 5-fold cross-validation. As for default $k$-nearest neighbor
classification, changes of $k$ have a relatively large impact. We show
parameter sensitivity for each of the five real-world datasets separately.
Naturally, different datasets have different optimal parameter settings. The
configuration $k=10$, which is also recommended within Pl-Knn (Hüllermeier &
Beringer, 2005) and Ipal (Zhang & Yu, 2015), provides a good trade-off between
the number of confident predictions and how accurate confident predictions
are. Indeed, this setting produces a good number of confident predictions on
most datasets (Figure 6; center plot). At the same time, it produces a good
MCC performance of confident predictions on most datasets (Figure 6; right
plot).

When increasing $k$, our method’s behavior on different datasets can be
grouped into two groups. On the BirdSong, MirFlickr, and YahooNews datasets,
increasing $k$ past ten neighbors also increases the amount of irrelevant
labeling information from those neighbors. Therefore, our approach produces
less confident predictions. At the same time, the MCC score of confident
predictions remains at roughly the same level. This is because irrelevant
labeling information from neighbors increases at most at the same rate as $k$.
In contrast, on the Lost and MsrcV2 datasets, the MCC score of confident
predictions drops sharply at a certain point while the number of confident
predictions decreases similarly. This is because irrelevant labeling
information increases more rapidly than $k$: The decrease of confidence in
predictions is slower than the increase of irrelevant candidate labels.