# On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label
Learning

Kaifu Wang
University of Pennsylvania
<EMAIL_ADDRESS>
&Efthymia Tsamoura
Samsung AI
<EMAIL_ADDRESS>
&Dan Roth
University of Pennsylvania
<EMAIL_ADDRESS>

###### Abstract

Multi-Instance Partial Label Learning (MI-PLL) is a weakly-supervised learning
setting encompassing partial label learning, latent structural learning, and
neurosymbolic learning. Differently from supervised learning, in MI-PLL, the
inputs to the classifiers at training-time are tuples of instances
$\mathbf{x}$, while the supervision signal is generated by a function $\sigma$
over the gold labels of $\mathbf{x}$. The gold labels are hidden during
training. In this paper, we focus on characterizing and mitigating learning
imbalances, i.e., differences in the errors occurring when classifying
instances of different classes (aka _class-specific risks_), under MI-PLL. The
phenomenon of learning imbalances has been extensively studied in the context
of long-tail learning; however, the nature of MI-PLL introduces new
challenges. Our contributions are as follows. From a theoretical perspective,
we characterize the learning imbalances by deriving class-specific risk bounds
that depend upon the function $\sigma$. Our theory reveals that learning
imbalances exist in MI-PLL even when the hidden labels are uniformly
distributed. On the practical side, we introduce a technique for estimating
the marginal of the hidden labels using only MI-PLL data. Then, we introduce
algorithms that mitigate imbalances at training- and testing-time, by treating
the marginal of the hidden labels as a constraint. The first algorithm relies
on a novel linear programming formulation of MI-PLL for pseudo-labeling. The
second one adjusts a model’s scores based on robust optimal transport. We
demonstrate the effectiveness of our techniques using strong neurosymbolic and
long-tail learning baselines, discussing also open challenges.

##  1 Introduction

The need to reduce labeling cost motivates the study of weakly-supervised
learning settings [59, 57]. Our work aligns with this objective, focusing on
_multi-instance partial label learning_ (MI-PLL) [49]. MI-PLL is particularly
appealing, as it encompasses three well-known learning settings in the
relevant literature: _partial label learning_ (PLL) [17, 7, 3, 23, 37, 52, 54,
56, 47, 13], where each training instance is associated with a set of
candidate labels, latent structural learning [40, 34, 58], i.e., learning
classifiers subject to a transition function $\sigma$ that constraints the
classifiers’ outputs, and _neurosymbolic learning_ [24, 51, 9, 43, 15, 20],
i.e., training neural classifiers subject to symbolic background knowledge. An
MI-PLL example is illustrated below:

######  Example 1.1 (MI-PLL example).

We aim to learn an MNIST classifier $f$, using only samples of the form
${(x_{1},x_{2},s)}$, where $x_{1}$ and $x_{2}$ are MNIST digits and $s$ is the
maximum of their gold labels, i.e.,
${s=\sigma(y_{1},y_{2})=\max\\{y_{1},y_{2}\\}}$ with $y_{i}$ being the label
of $x_{i}$. The gold labels are hidden during training. We will refer to the
$y_{i}$’s and $s$ as _hidden_ and _partial_ labels, respectively.

0123456789$0$$20$$40$$60$$80$$100$MNIST classesPer-class accuracy

Figure 1: Accuracy of the classifier from Example 1.1. Blue, red and green
curves show accuracy at 20, 40 and 100 epochs. Learning converges in 100
epochs.

In this paper, we address an unexplored topic in the context of MI-PLL: that
of characterizing and mitigating learning imbalances. By learning imbalances
we refer to major differences in the errors occurring when classifying
instances of different classes (aka _class-specific risks_). Existing works in
supervised [28, 4] and weakly-supervised learning [47, 13] study imbalances
under the prism of long-tailed (aka imbalanced) data: data in which instances
of different classes occur with very different frequencies, [12, 14, 2].

However, those studies cannot characterize learning imbalances in MI-PLL. This
is because of two phenomena caused by the transition function $\sigma$: (i)
the partial labels can be imbalanced even if the hidden labels are uniformly
distributed; and (ii) different partial labels have very different supervision
powers. Let us illustrate the above via Example 1.1. Regarding (i), even if
both $y_{1}$ and $y_{2}$ are uniform in ${\\{0,\dots,9\\}}$, the partials are
long-tail when each training sample is formed by independently drawing pairs
of MNIST digits and applying $\sigma$ on their gold labels. In that case,
$s=0$ occurs with probability $1/100$, while $s=9$ occurs with probability
$17/100$ in the training data. Regarding (ii), partial label 0 provides much
stronger supervision than partial label 9: in the former case, we have direct
supervision, as $s=0$ implies $y_{1}=y_{2}=0$; in contrast, $s=9$ only implies
that either $y_{1}=9$ and $y_{2}$ is any label in ${\\{0,\dots,9\\}}$, or vice
versa. Figure 1 demonstrates this phenomenon by showing the per-class
classification accuracy across different training epochs when an MNIST
classifier is trained as in Example 1.1 and the hidden labels are uniform.
Hence, to faithfully characterise imbalances in MI-PLL from a theoretical
persepective, we need to account for the impact of $\sigma$.

On the practical side, mitigating learning imbalances has received
considerable attention in supervised and weakly-supervised learning with the
proposed techniques (typically referred to as long-tail learning) operating at
training- [4, 42, 41, 6, 2] or at testing-time [18, 31, 28]. However, there
are two main reasons that make those techniques not appropriate for MI-PLL.
First, they rely on (good) approximations of the marginal distribution of the
hidden labels. While approximating $\mathbf{r}$ may be easy in supervised
learning [28] as the gold labels are available, in our setting the gold labels
are hidden from the learner. Second, the state-of-the-art for training-time
mitigation [47, 4, 42, 41, 6, 2, 13] is designed for settings in which a
single instance is presented each time to the learner and hence, they cannot
take into account the correlations among the instances. The above gives rise
to a second challenge: _developing techniques for mitigating learning
imbalances in MI-PLL._

Contributions. We start by providing class-specific error bounds in the
context of MI-PLL. Complementary to previous work in supervised learning [4]
and standard single-instance PLL [7], our theory shows that $\sigma$ can have
a significant impact on learning imbalances, capturing the phenomena (i) and
(ii) described above, see Theorem 3.1. Our analysis also extends the
theoretical analysis in [49], by providing stricter risk bounds for the
underlying classifiers, while making minimal assumptions.

On the practical side, we first propose a statistically consistent technique
for estimating the marginal of the hidden labels given partially labeled ones.
We further propose two algorithms that mitigate imbalances at training- and
testing-time, respectively. The first algorithm assigns pseudo-labels to
training data based on a novel linear programming formulation of MI-PLL, see
Section 4.2. The second algorithm aims to use the marginal information to
constrain the model’s prediction on testing data, using a robust semi-
constrained optimal transport (RSOT) formulation [19], see Section 4.3. Our
empirical analysis demonstrates that our techniques can substantially improve
the accuracy over strong baselines from neurosymbolic learning [53, 49] and
long-tail learning [28, 13] by up to 14%, manifesting, at the same time, that
the straightforward application of state-of-the-art techniques to MI-PLL
settings is either impossible (e.g., [47]) or problematic (e.g., [13]). More
importantly, our analysis uncovers open challenges for imbalance mitigation,
that is computing marginals for training-time mitigation and developing robust
testing-time techniques.

##  2 Preliminaries

Data and models. Let $\mathcal{X}$ be the instance space and
$\mathcal{Y}=\\{l_{1},\dots,l_{c}\\}$ be the output space with
$|\mathcal{Y}|=c$. The joint distribution of two random variables $X,Y$ over
$\mathcal{X}\times\mathcal{Y}$ is denoted as $\mathcal{D}$, with
$\mathcal{D}_{X}$ denoting the marginal of $X$. Vector
$\mathbf{r}=(r_{1},\dots,r_{c})$ denotes the marginal of $Y$, where
$r_{j}=\mathbb{P}(Y=l_{j})$ is the probability of occurrence (or ratio) of the
$j$-th label. For a label $y=l_{j}(j\in[c])$, we express
$r_{y}=r_{l_{j}}=r_{j}$. We consider _scoring functions_ of the form
${f:\mathcal{X}\rightarrow\Delta_{c}}$, where $\Delta_{c}$ is the space of
probability distributions on $\mathcal{Y}$, e.g., $f$ outputs the softmax
probabilities (or _scores_) of a neural classifier. We use ${f^{j}(x)}$ to
denote the $j$-th output of ${f(x)}$. A scoring function $f$ induces a
_classifier_ $[f]:\mathcal{X}\rightarrow\mathcal{Y}$, whose _prediction_ on
$x$ is given by $f=\operatorname*{argmax}_{j\in[c]}f^{j}(x)$. We denote by
$\mathcal{F}$ the set of scoring functions and by $[\mathcal{F}]$ the set of
induced classifiers. The zero-one loss is given by
$L(y^{\prime},y)=\mathbbm{1}\\{y^{\prime}\neq y\\}$, while the zero-one risk
of $f$ is given by $R(f):=\mathbb{E}_{(X,Y)\sim\mathcal{D}}[L([f](X),Y)]$.
Finally, the risk of $f$ for the $j$-th class is defined as the probability of
$f$ mispredicting an instance of that class, i.e.,
${R_{j}(f):=\mathbbm{P}([f](x)\neq l_{j}|Y=l_{j})}$ . We refer to that risk as
the class-specific one.

Multi-Instance PLL. We denote the vector $(x_{1},\dots,x_{M})$ by $\mathbf{x}$
and the corresponding vector of gold labels by $\mathbf{y}$. Let
${\sigma:\mathcal{Y}^{M}\rightarrow\mathcal{S}}$ be a transition function.
Space $\mathcal{S}=\\{a_{1},\dots,a_{c_{S}}\\}$ is referred to as the partial
label space with ${|\mathcal{S}|=c_{S}\geq 1}$. We use
$p_{j}=\mathbb{P}(S=a_{j})$ to denote the probability of occurrence (or ratio)
of the $j$-th partial label $a_{j}$. We assume that $\sigma$ is known to the
learner. Let $\mathcal{T}_{\mathsf{P}}$ be a set of $m_{\mathsf{P}}$ partially
labeled samples of the form ${(\mathbf{x},s)=(x_{1},\dots,x_{M},s)}$. Each
partially labeled sample is formed by drawing $M$ i.i.d. samples
${(x_{i},y_{i})}$ from $\mathcal{D}$ and then applying
${s=\sigma(y_{1},\dots,y_{M})}$. The distribution of these training samples
$(\mathbf{x},s)$ is denoted by $\mathcal{D}_{\mathsf{P}}$. For a classifier
$f$, $[f](\mathbf{x})$ is a short for vector $([f](x_{1}),\dots,[f](x_{M}))$.
The _zero-one partial loss subject to $\sigma$_ is defined as
${L_{\sigma}(\mathbf{y},s):=L(\sigma(\mathbf{y}),s)=\mathbbm{1}\\{\sigma(\mathbf{y})\neq
s\\}}$, for any ${\mathbf{y}\in\mathcal{Y}^{M}}$ and ${s\in\mathcal{S}}$. We
focus on learning via empirical risk minimization. In particular, the learner
aims to find a classifier $f$ with minimum _zero-one partial risk subject to
$\sigma$_ defined as
$R_{\mathsf{P}}(f;\sigma):=\mathbbm{E}_{(X_{1},\dots,X_{M},S)\sim\mathcal{D}_{\mathsf{P}}}[L_{\sigma}(([f](\mathbf{X})),S)]$.

Vectors and matrices. $\mathbbm{1}\\{\cdot\\}$ denotes indicator functions.
For a integer $M\geq 0$, we define ${[M]:=\\{1,\dots,M\\}}$. A vector is
_diagonal_ if all of its elements are equal. We denote by $\mathbf{e}_{i}$ the
vector with all its elements being equal to 0 apart from its $i$-th one which
equals to 1. We denote the all-one and all-zero vectors in $\mathbb{R}^{n}$ by
$\mathbf{1}_{n}$ and $\mathbf{0}_{n}$, and the identity matrix of size
$n\times n$ by $\mathbf{I}_{n}$. Let ${\mathbf{A}\in\mathbbm{R}^{n\times m}}$
be a matrix. We use $A_{i,j}$ to denote the value of the ${(i,j)}$ cell of
$\mathbf{A}$ and $v_{i}$ to denote the $i$-th element of a vector
$\mathbf{v}$. We denote the vectorization of $\mathbf{A}$ by
${\mathrm{vec}(\mathbf{A}):=[a_{1,1},\ldots,a_{n,1},\ldots,a_{1,m},\ldots,a_{n,m}]^{\mathsf{T}}}$
and its Moore–Penrose inverse by $\mathbf{A}^{\dagger}$. If $\mathbf{A}$ is
square, then the diagonal matrix that shares the same diagonal with
$\mathbf{A}$ is denoted by $D(\mathbf{A})$. For matrices $\mathbf{A}$ and
$\mathbf{B}$, ${\mathbf{A}\otimes\mathbf{B}}$ and
${\langle\mathbf{A},\mathbf{B}\rangle}$ denote their Kronecker product and
their Frobenius inner product.

##  3 Theory: characterizing learning imbalances in MI-PLL

In this section, we characterize learning imbalances in MI-PLL from a
theoretical perspective by deriving class-specific risk bounds, see
Proposition 3.1. These bounds measure the difficulty of learning instances of
each class in $\mathcal{Y}$, indicating that, unlike in supervised learning,
imbalances in MI-PLL arise not only from label distribution imbalances but
also from the partial labeling process. In particular, learning imbalances can
still exist even if the hidden or the partial labels are uniformly
distributed. Differently from prior work [49], our theoretical analysis relies
solely on the i.i.d. assumption (see Section 2). To simplify our presentation,
here we focus on the case where $M=2$. Nevertheless, our analysis directly
generalizes for $M>2$.

Our theory is based on a novel non-linear programming formulation that allows
us to compute an upper bound of each $R_{j}(f)$. The first key idea (K1) to
that formulation is a rewriting of $R_{\mathsf{P}}(f;\sigma)$ and $R_{j}(f)$.
To start with, given the transition $\sigma$, the zero-one partial risk can be
expressed as

$\displaystyle
R_{\mathsf{P}}(f;\sigma)=\sum_{(l_{i},l_{j})\in\mathcal{Y}^{2}}\eqnmarkbox[olive]{true}{r_{i}r_{j}}\left(\sum_{(l_{i^{\prime}},l_{j^{\prime}})\in\mathcal{Y}^{2}}\eqnmarkbox[blue]{wrong}{\mathbbm{1}\\{\sigma(l_{i},l_{j})\neq\sigma(l_{i^{\prime}},l_{j^{\prime}})\\}}\eqnmarkbox[purple]{prob}{\mathbf{H}_{ii^{\prime}}(f)\mathbf{H}_{jj^{\prime}}(f)}\right)$
(1)

[yshift=0.55em]above,lefttrueprobability of the pair $(l_{i},l_{j})$
[yshift=0.55em]abovewrongthe partial label is misclassified
[yshift=-0.85em]below, leftprobconditional probability that the labels $l_{i}$
and $l_{j}$ are (mis)classified as $l_{i^{\prime}}$ and $l_{j^{\prime}}$

where $\mathbf{H}(f)$ is an $c\times c$ matrix defined as
${\mathbf{H}(f):=[\mathbbm{P}([f](x)=l_{j}|Y=l_{i})]_{i\in[c],j\in[c]}}$. In
other words, the ${(i,j)}$ cell in $\mathbf{H}(f)$ is the probability of $f$
classifying (correctly or not) an instance with label $l_{i}$ to $l_{j}$. Now,
let $\mathbf{h}(f)=\mathrm{vec}(\mathbf{H}(f))$ be the vectorization of
$\mathbf{H}(f)$. The partial risk ${R_{\mathsf{P}}(f;\sigma)}$ in (1) is a
quadratic form of $\mathbf{h}(f)$. Therefore, there is a unique symmetric
matrix $\mathbf{\Sigma}_{\sigma,\mathbf{r}}$ in $\mathbbm{R}^{c^{2}\times
c^{2}}$ that depends only on $\sigma$ and $\mathbf{r}$ such that (1) can be
rewritten as

$\displaystyle
R_{\mathsf{P}}(f;\sigma)=\mathbf{h}(f)^{\mathsf{T}}\mathbf{\Sigma}_{\sigma,\mathbf{r}}\mathbf{h}(f)$
(2)

Furthermore, for each $l_{j}\in\mathcal{Y}$, let ${\mathbf{W}_{j}}$ be the
matrix defined by
${(\mathbf{1}_{c}-\mathbf{e}_{j})\mathbf{e}_{j}^{\mathsf{T}}}$ and
${\mathbf{w}_{j}}$ be its vectorization. We can rewrite the class-specific
risk as

$\displaystyle R_{j}(f)=\mathbf{w}_{j}^{\mathsf{T}}\mathbf{h}(f)$ (3)

The second key idea (K2) to forming a non-linear program for computing class-
specific risk bounds is to upper bound the class-specific risk $R_{j}(f)$ of a
model $f$ with the model’s partial risk $R_{\mathsf{P}}(f;\sigma)$. The latter
can be minimized with partially labeled data $\mathcal{T}_{\mathsf{P}}$.
Putting (K1) and (K2) together, the worst class-specific risk of $f$ for the
$j$-th class is given by the optimal solution of the program below:

$\displaystyle\max_{\mathbf{h}}$
$\displaystyle\mathbf{w}_{j}^{\mathsf{T}}\mathbf{h}(f)$ (4)
$\displaystyle\mathrm{s.t.}$
$\displaystyle\mathbf{h}(f)^{\mathsf{T}}\mathbf{\Sigma}_{\sigma,\mathbf{r}}\mathbf{h}(f)=R_{\mathsf{P}}(f;\sigma)\quad$
(partial risk) $\displaystyle\mathbf{h}(f)\geq 0\quad$ (positivity)
$\displaystyle(\mathbf{I}_{c}\otimes\mathbf{1}_{c}^{\mathsf{T}})\mathbf{h}(f)=\mathbf{1}_{c}\quad$
(normalization)

Let’s analyze (4). The optimization objective states that we aim to find the
worst possible class-specific risk as expressed in (3). The first constraint
specifies the partial risk of the model. The second one asks the
(mis)classification probabilities to be non-negative. The last constraint,
where $(\mathbf{I}_{c}\otimes\mathbf{1}_{c}^{\mathsf{T}})\mathbf{h}(f)$
represents the row sums of matrix $\mathbf{H}(f)$, requires the classification
probabilities to sum to one. Let
${\Phi_{\sigma,j}({R}_{\mathsf{P}}(f;\sigma))}$ denote the optimal solution to
program (4). Formally, we have:

######  Proposition 3.1 (Class-specific risk bound).

For any $l_{j}\in\mathcal{Y}$, we have that
$R_{j}(f)\leq\Phi_{\sigma,j}({R}_{\mathsf{P}}(f;\sigma))$.

Characterizing learning imbalance. Theorem 3.1 suggests that the worst risk
associated with each class in $\mathcal{Y}$ is characterized by two factors.
The first one is the model’s partial risk $R_{\mathsf{P}}(f;\sigma)$, which is
independent of the specific class. The second factor is $\sigma$, as $\sigma$
impacts on the mapping $\Phi_{\sigma,j}$ from the model’s partial risk to the
class-specific risk. Therefore, the learning imbalance can be assessed by
comparing the growth rates of $\Phi_{\sigma,j}$. We use this approach below to
analyze Example 1.1.

Figure 2: Class-specific upper bounds obtained via (4). (left)
${\mathcal{D}_{Y}}$ is uniform. (right) ${{\mathcal{D}_{\mathsf{P}_{S}}}}$ is
uniform.

######  Example 3.2 (Cont’ Example 1.1).

Let $\mathcal{D}$ and $\mathcal{D}_{\mathsf{P}}$ be defined as in Section 2.
Consider the two cases:

  * Case 1

The marginal of the hidden label $Y$ is uniform. The left-hand side of Figure
2 shows the risk bounds for different classes obtained via solving program
(4). The bounds are presented as functions of different values of
${R}_{\mathsf{P}}(f;\sigma)$. In this plot, the curve for class “zero” (resp.
“nine”) has the steepest (resp. smoothest) slope, suggesting that $f$ will
tend to make more (resp. fewer) mistakes when classifying instances of that
class. In other words, class “zero" is the hardest to learn, as also shown to
be the case in reality, see Figure 1.

  * Case 2

The marginal of the partial label $S$ is uniform. Similarly, the right-hand
side Figure 2 plots the corresponding risk bounds, suggesting that the class
“zero" is now the easiest to learn.

Obtaining the label ratio $\mathbf{r}$. Computing the program (4) requires
knowing the transition $\sigma$ and the label distribution $\mathbf{r}$. While
$\sigma$ is assumed to be given, $\mathbf{r}$ may be unknown in practice. To
circumvent this, in Section 4.1, we present a technique for estimating
$\mathbf{r}$ using only partially labeled data $\mathcal{T}_{\mathsf{P}}$.

Computable bounds for $R_{j}(f)$. Using Proposition 3.1, we could further
derive a bound for $R_{j}(f)$ that can be computed using an MI-PLL dataset.
This can be done by using standard learning theory tools (e.g., VC-dimension
or Rademacher complexity) to show that, given a fixed confidence level
$\delta\in(0,1)$, the partial risk $R_{\mathsf{P}}(f;\sigma)$ will not exceed
a _generalization bound_
$\widetilde{R}_{\mathsf{P}}(f;\sigma,\mathcal{T}_{\mathsf{P}},\delta)$ with
probability $1-\delta$. An example is shown below.

######  Proposition 3.3.

Let $d_{[\mathcal{F}]}$ be the Natarajan dimension of $[\mathcal{F}]$. Given a
confidence level $\delta\in(0,1)$, we have that
$R_{j}(f)\leq\Phi_{\sigma,j}(\widetilde{R}_{\mathsf{P}}(f;\sigma,\mathcal{T}_{\mathsf{P}},\delta))$
with probability $1-\delta$ for any $j\in[c]$, where

$\widetilde{R}_{\mathsf{P}}(f;\sigma,\mathcal{T}_{\mathsf{P}},\delta)=\widehat{R}_{\mathsf{P}}(f;\sigma,\mathcal{T}_{\mathsf{P}})+\sqrt{\frac{2\log(\mathrm{e}m_{\mathsf{P}}/2d_{[\mathcal{F}]}\log(6Mc^{2}d_{[\mathcal{F}]}/\mathrm{e}))}{m_{\mathsf{P}}/2d_{[\mathcal{F}]}\log(6Mc^{2}d_{[\mathcal{F}]}/\mathrm{e})}}+\sqrt{\frac{\log(1/\delta)}{2m_{\mathsf{P}}}}$
(5)

Comparison to previous work. The most relevant work to ours is [49], which
provides the first theoretical framework that establishes the learnability for
MI-PLL. Our result extends [49] in three ways: (i) we bound the class-specific
risks $R_{j}(f)$ instead of bounding the total risk $R(f)$; (ii) our bounds do
not rely on $M$-unambiguity, in contrast to those in [49]; and (iii) the
program (4) leads to tighter bounds for $R(f)$. Before proving (iii), let us
first recapitulate $M$-unambiguity:

######  Definition 3.4 ($M$-unambiguity from [49]).

A transition $\sigma$ is _$M$ -unambiguous_ if for any two diagonal label
vectors $\mathbf{y}$ and $\mathbf{y}^{\prime}$ $\in\mathcal{Y}^{M}$ such that
$\mathbf{y}\neq\mathbf{y}^{\prime}$, we have that
${\sigma(\mathbf{y}^{\prime})\neq\sigma(\mathbf{y})}$.

Now, let us illustrate (iii) from above. By relaxing the constraints in (4),
we can recover Lemma 1 from [49] (which is the key to proving Theorem 1 from
[49]). In particular, if we: (1) drop the the positivity and normalization
constraints from (4) and (2) replace the partial risk constraint by a more
relaxed inequality
${\mathbf{h}(f)^{\mathsf{T}}D(\mathbf{\Sigma}_{\sigma,\mathbf{r}})\mathbf{h}(f)\leq{R}_{\mathsf{P}}(f;\sigma)}$,
we can obtain the following result:

######  Proposition 3.5.

If $\sigma$ is $M$-unambiguous, then the risk of $f$ can be bounded by

$\displaystyle
R(f)\leq\sqrt{{\mathbf{w}^{\mathsf{T}}(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))^{\dagger}\mathbf{w}R_{\mathsf{P}}}(f;\sigma)}=\sqrt{{c(c-1){R}_{\mathsf{P}}}(f;\sigma)}$
(6)

which coinsides with the Lemma 1 from [49] for $M=2$.

##  4 Algorithms: mitigating imbalances in MI-PLL

We now propose a portfolio of techniques for addressing learning imbalances in
MI-PLL. Our first contribution, see Section 4.1, is a statistically consistent
technique for estimating $\mathbf{r}$, assuming access to partial labels only.
We then move to training-time mitigation, see Section 4.2 and testing-time
mitigation, see Section 4.3. Our marginal estimation algorithm requires only
the i.i.d. assumption of MI-PLL; the algorithms in Section 4.2 and 4.3 work
even when the i.i.d. assumption fails to hold.

###  4.1 Estimating the marginal of the hidden labels

We begin with our technique for estimating $\mathbf{r}$ using only partially
labeled data $\mathcal{T}_{\mathsf{P}}$. Our technique for estimating
$\mathbf{r}$ relies on the observation that in MI-PLL, the ratio $p_{j}$ of a
partial label $a_{j}\in\mathcal{S}$ equals the probability of its pre-image
$\sigma^{-1}(a_{j})$, namely
${p_{j}=\sum_{(y_{1},\dots,y_{M})\in\sigma^{-1}(a_{j})}\prod_{i=1}^{M}r_{y_{i}}}$,
which is a polynomial of $\mathbf{r}$. We illustrate the above idea with the
following example.

######  Example 4.1.

Consider Case (2) from Example 3.2. Assume that the marginals of the partial
labels are uniform. Then, we can obtain $\mathbf{r}$ via solving the following
_system of polynomial equations_ :
${[r_{0}^{2},r_{1}^{2}+2r_{0}r_{1},\dots,r_{9}^{2}+2\sum_{i=0}^{8}r_{i}r_{9}]^{\mathsf{T}}=[1/10,1/10,\dots,1/10]^{\mathsf{T}}}$.
The first equation denotes the probability a partial label to be zero, which
is $1/10$ (uniformity). Due to $\sigma$, this can happen only when
$y_{1}=y_{2}=0$. Under the independence assumption, the above implies that
${r_{0}^{2}=1/10}$. Analogously, the second and the last polynomials denote
the probabilities a partial label to be one and nine.

Let $\Psi_{\sigma}$ be the mapping
${\mathbf{r}}\mapsto{\mathbf{p}}=[p_{j}]_{j\in[c_{S}]}$ as defined above. In
practice, the marginal $\mathbf{p}$ is unknown, but can be estimated by the
empirical distribution of a partially labeled dataset
$\mathcal{T}_{\mathsf{P}}$ of size $m_{\mathsf{P}}$, namely
${\bar{p}_{j}:=\sum_{k=1}^{m_{\mathsf{P}}}\mathbbm{1}\\{s_{k}=a_{j}\\}/m_{\mathsf{P}}}$.
As the $\bar{p}_{j}$’s can be noisy, the system of polynomials could become
inconsistent. Therefore, instead of solving the polynomial equation as in
Example 4.1, we find an estimate $\widehat{\mathbf{r}}$, so that its induced
prediction for the partial label ratio
$\widehat{\mathbf{p}}:=\Psi_{\sigma}(\widehat{\mathbf{r}})$ best fits to the
empirical probabilities $\bar{p}_{j}$’s by means of cross-entropy. Since this
requires optimizing over the probability simplex $\Delta_{c}$, we
reparametrize the estimated ratios $\widehat{\mathbf{r}}$ as
$\widehat{\mathbf{r}}=\operatorname{softmax}(\mathbf{u})$, leading to
Algorithm 1. We also provide a theoretical guarantee for the consistency of
Algorithm 1 in Appendix C.

Algorithm 1 Label Ratio Solver

Input: partial labels $\\{s_{k}\\}_{k=1}^{m_{\mathsf{P}}}$, transition
function $\sigma$, step size $t$, iterations $N_{\text{iter}}$

Initialize: logit ${\mathbf{u}}\leftarrow\mathbf{1}_{c}$; ${\bar{p}_{j}}$, for
$j\in[c_{S}]$

for $N=1,\dots,N_{\text{iter}}$ do

${\mathbf{\widehat{r}}\leftarrow\mathrm{softmax}(\mathbf{u})}$

for each ${j\in[c_{S}]}$ do

${\widehat{p}_{j}\leftarrow\sum\limits_{(y_{1},\dots,y_{M})\in\sigma^{-1}(a_{j})}\prod_{i=1}^{M}\widehat{r}_{y_{i}}}$

$\ell\leftarrow\sum_{j=1}^{c_{S}}\bar{p}_{j}{\log\widehat{p}_{j}}$

Backpropagate $\ell$ to update ${\mathbf{u}}$

return $\mathrm{softmax}(\mathbf{u})$

Algorithm 2 CAROT

Input: model’s raw scores $\mathbf{P}\in\mathbbm{R}^{c\times n}$, ratio
estimates $\widehat{\mathbf{r}}\in\mathbbm{R}^{c}$, entropic reg. parameter
$\eta>0$, margin reg. parameter $\tau>0$, iterations $N_{\text{iter}}$

Initialize: $\mathbf{u}\leftarrow\mathbf{0}_{n}$;
$\mathbf{v}\leftarrow\mathbf{0}_{c}$

for $N=1,\dots,N_{\text{iter}}$ do

$\mathbf{a}\leftarrow B(\mathbf{u},\mathbf{v})\mathbf{1}_{c}$;
$\mathbf{b}\leftarrow B(\mathbf{u},\mathbf{v})^{\mathsf{T}}\mathbf{1}_{n}$

if $k$ is even then

update $\mathbf{v}$ //see Section 4.3

else

update $\mathbf{u}$ //see Section 4.3

return $B(\mathbf{u},\mathbf{v})$

###  4.2 Training-time imbalance mitigation via integer linear programming

We now turn to training-time mitigation. We aim to find pseudo-labels
$\mathbf{Q}$ that are close to the classifier’s scores and adhere to
$\widehat{\mathbf{r}}$ and use $\mathbf{Q}$ to train the classifier using the
cross-entropy loss. There are two design choices: (i) whether to find pseudo-
labels at the individual instance level or at the batch level; (ii) whether to
be strict in enforcing the marginal ${\widehat{\mathbf{r}}}$. In addition, we
face two challenges: (iii) we are provided with $M$-ary tuples of instances of
the form ${(x_{1},\dots,x_{M})}$; (iv) $\mathbf{Q}$ must additionally abide by
the constraints coming from $\sigma$ and the partial labels, e.g., when $s=1$
in Example 1.1, then the only valid label assignments for ${(x_{1},x_{2})}$
are (1,1), (0,1) and (1,0). Regarding (i), finding pseudo-labels at the
individual instance level does not guarantee that the modified scores match
the desired distribution $\widehat{\mathbf{r}}$ [31]. Regarding (ii), strictly
enforcing ${\widehat{\mathbf{r}}}$ could be problematic as
$\widehat{\mathbf{r}}$ can be noisy.

To accommodate the above requirements, while avoiding the crux of solving non-
linear programs, we rely on a novel _linear programming_ (LP) formulation of
MI-PLL that finds pseudo-labels for a batch of $n$ scores. Let us introduce
our notation. We use ${(x_{\ell,1},\dots,x_{\ell,M},s_{\ell})}$ to denote the
$\ell$-th partial training sample in a batch of size $n$. We also use
${\mathbf{P}_{i}\in[0,1]^{n\times c}}$ and ${\mathbf{Q}_{i}\in[0,1]^{n\times
c}}$, for ${i\in[M]}$, to denote the classifier’s scores and the pseudo-labels
assigned to the $i$-th input instances of the batch. In particular,
${P_{i}[\ell,j]=f^{j}(x_{\ell,i})}$, while ${Q_{i}[\ell,j]}$ is the
corresponding pseudo-label. Each training sample is uniquely associated with a
Boolean formula of $R_{\ell}$ disjuncts of the form
${\Phi_{\ell}=\varphi_{\ell,1}\vee\dots\vee\varphi_{\ell,R_{\ell}}}$. Formula
$\Phi_{\ell}$ encodes the valid label assignments for the $\ell$-th partial
training sample subject to $\sigma$ and $s_{\ell}$ and is exclusively
determined by $\sigma$ and $s_{\ell}$. Each disjunct in $\Phi_{\ell}$ is a
conjunction of Boolean variables from
${\\{q_{\ell,i,j}\\}_{i\in[M],j\in[c]}}$, where $q_{\ell,i,j}$ is true if and
only if $x_{\ell,i}$ is assigned to the $j$-th label in $\mathcal{Y}$. We
assume a canonical ordering over the variables occurring in $\varphi_{\ell,t}$
and use $\varphi_{\ell,t,k}$ to refer to the $k$-th variable and
${|\varphi_{\ell,t}|}$ to denote the number of variables occurring
$\varphi_{\ell,t}$.

Based on the above, finding a pseudo-label assignment for
${(x_{\ell,1},\dots,x_{\ell,M})}$ that adheres to $\sigma$ and $s_{\ell}$
reduces to finding an assignment to the variables in
${\\{q_{\ell,i,j}\\}_{i\in[M],j\in[c]}}$ that makes $\Phi_{\ell}$ hold.
Previous work ([35, 39]) has shown that we can cast satisfiability problems
(as the one above) to linear programming problems. Therefore, instead of
finding a Boolean true or false assignment to each $q_{\ell,i,j}$, we can find
an assignment in ${[0,1]}$ for the real counterpart of $q_{\ell,i,j}$ denoted
by ${[q_{\ell,i,j}]}$. Via associating the ${[q_{\ell,i,j}]}$’s to the entries
in the $\mathbf{Q}_{i}$’s, i.e., ${Q_{i}[\ell,j]=[q_{\ell,i,j}]}$, we can
solve the following linear program to perform pseudo-labeling:

objective
$\displaystyle\min_{(\mathbf{Q}_{1},\dots,\mathbf{Q}_{M})}\sum_{i=1}^{M}\langle-\log(\mathbf{P}_{i}),\mathbf{Q}_{i}\rangle,$
(7) s.t.
$\displaystyle\begin{array}[]{rll}\sum_{t=1}^{R_{\ell}}[\alpha_{\ell,t}]&\geq
1,&\ell\in[n]\\\
-|\varphi_{\ell,t}|[\alpha_{\ell,t}]+\sum_{k=1}^{|\varphi_{\ell,t}|}[\varphi_{\ell,t,k}]&\geq
0,&\ell\in[n],t\in[R_{\ell}]\\\
-\sum_{k=1}^{|\varphi_{\ell,t}|}[\varphi_{\ell,t,k}]+[\alpha_{\ell,t}]&\geq(1-|\varphi_{\ell,t}|),&\ell\in[n],t\in[R_{\ell}]\\\
\sum_{j=1}^{c}[q_{\ell,i,j}]&=1,&\ell\in[n],i\in[M]\\\
\left[q_{\ell,i,j}\right]&\in[0,1],&\ell\in[n],i\in[M],j\in[c]\\\
|\mathbf{Q}_{i}\cdot\mathbf{1}_{n}-n\widehat{\mathbf{r}}|&\leq\epsilon,&i\in[M]\\\
\end{array}$

The minimization objective in (7) aligns with our aim to find pseudo-labels
close to the classifier’s scores. The independence among the classifier’s
scores for different $\mathbf{x}_{\ell,i}$’s– recall that a classifier makes a
prediction for each $\mathbf{x}_{\ell,i}$ independently of the other
instances– justifies the sum over different $i$’s in the minimization
objective. The first three constraints force the pseudo-labels for the
$\ell$-th training sample to adhere to $\sigma$ and $s_{\ell}$, where the
$\alpha_{\ell,t}$’s are Boolean variables introduced due to converting the
$\Phi_{\ell}$’s into _conjunctive normal form_ using the Tseytin
transformation [44]. The fourth and the fifth constraint wants the pseudo-
labels for each instance $x_{\ell,i}$ to sum up to one and lie in ${[0,1]}$.
Finally, the last constraint wants for each $i\in[M]$, the probability of
predicting the $j$-th pseudo-label for an element in
${\\{x_{\ell,i}\\}_{\ell\in[n]}}$ to match the ratio estimates at hand
$\widehat{r}_{j}$ up to some $\epsilon\geq 0$: the smaller $\epsilon$ gets,
the stricter the adherence to $\widehat{\mathbf{r}}$ becomes. The detailed
derivation of (7) is in the appendix.

To summarize, training-time mitigation works as follows: for each epoch, we
split the training samples in $\mathcal{T}_{\mathsf{P}}$ into batches. For
each batch ${\\{(x_{\ell,1},\dots,x_{\ell,M},s_{\ell})\\}_{\ell\in[n]}}$, we
form matrices ${\mathbf{P}_{1},\dots,\mathbf{P}_{M}}$ by applying $f$ on the
$x_{\ell,i}$’s and solve (7) to get the pseudo-label matrices
${\mathbf{Q}_{1},\dots,\mathbf{Q}_{M}}$. Finally, we train $f$ by minimizing
the cross-entropy loss between ${\mathbf{Q}_{1},\dots,\mathbf{Q}_{M}}$ and
${\mathbf{P}_{1},\dots,\mathbf{P}_{M}}$.

Remarks. Our formulation in (7) is oblivious to $\widehat{\mathbf{r}}$. In
particular, $\widehat{\mathbf{r}}$ can be estimated using either Algorithm 1
from Section 4.1 or any other technique, such as the moving average one from
[47]. Furthermore, the formulation in (7) allows us to find either hard or
soft pseudo-labels: we can treat (7) as an integer linear program via
enforcing $\left[q_{\ell,i,j}\right]$ to lie in ${\\{0,1\\}}$, instead of
${[0,1]}$.

###  4.3 CAROT: testing-time imbalance mitigation

We conclude this section with CAROT, an algorithm that mitigates learning
imbalances at testing-time by modifying the model’s scores to adhere to the
estimated ratios $\widehat{\mathbf{r}}$. Incorporating $\widehat{\mathbf{r}}$
into the model’s scores involves the design choices (i) and (ii) presented at
the beginning of Section 4.2– challenges (iii) and (iv) are specific to
training. Regarding (i), most existing testing-time mitigation algorithms
algorithms (e.g., [28]) modify a model’s scores at the level of individual
instances. Regarding (ii), as we explained in Section 4.2, strictly enforcing
${\widehat{\mathbf{r}}}$ could also be problematic, as now,
${\widehat{\mathbf{r}}}$ may be also different from the label marginal
underlying the test data.

Similarly to Section 4.2, we propose to adjust the model’s scores for a whole
batch of ${n>1}$ test samples (represented by a matrix
$\mathbf{P}\in\mathbbm{R}^{n\times c}$) so that the adjusted scores
$\mathbf{P}^{\prime}$ roughly adhere to ${\widehat{\mathbf{r}}}$. Precisely,
we propose to find $\mathbf{P}^{\prime}$ that optimizes the following
objective:

$\min_{\mathbf{P}^{\prime}\in\mathbbm{R}^{n\times
c}_{+},\mathbf{P}^{\prime}\mathbf{1}_{c}=\mathbf{1}_{n}}\langle-\log(\mathbf{P}),\mathbf{P}^{\prime}\rangle+{\tau\operatorname{KL}(\mathbf{P}^{\prime\mathsf{T}}\mathbf{1}_{n}\;\|\;n\widehat{\mathbf{r}}\,)}-\eta
H(\mathbf{P}^{\prime})$ (8)

The first term in (8) encourages $\mathbf{P}^{\prime}$ to be close to the
original scores. The second term encourages the column sums of
$\mathbf{P}^{\prime}$ to match $\widehat{\mathbf{r}}$, with $\tau>0$
controlling the level of adherence, where KL is the Kullback-Leibler
divergence. This formulation leads to a robust semi-constrained optimal
transport (RSOT) problem [19]. The entropic regularizer $\eta
H(\mathbf{P}^{\prime})$, where $H$ denotes entropy, allows to approximate the
optimal solution using the robust semi-Sinkhorn algorithm from [19], leading
to CAROT (Confidence-Adjustment via Robust semi-constrained Optimal
Transport), see Algorithm 2.

In Algorithm 2, ${B(\mathbf{u},\mathbf{v})}$ denotes an ${n\times c}$ matrix
whose $(i,j)$ cell is computed as a function of $\mathbf{u}$ and $\mathbf{v}$
by ${\exp(u_{i}+v_{j}+\log(P_{ij})/\eta)}$. In each iteration, the algorithm
alternates between updating the $c$-dimensional vector $\mathbf{v}$ and the
$n$-dimensional vector $\mathbf{u}$. The former update, which is computed as
${\mathbf{v}\leftarrow\frac{\eta\tau}{\eta+\tau}\left(\frac{\mathbf{v}}{\eta}+\log(n\widehat{\mathbf{r}})-\log(\mathbf{b})\right)}$,
forces ${B(\mathbf{u},\mathbf{v})}$ to adhere to $\widehat{\mathbf{r}}$; the
latter one, which is computed as
${\mathbf{u}\leftarrow{\eta}\left(\frac{\mathbf{u}}{\eta}+\log(\mathbf{1}_{n})-\log(\mathbf{a})\right)}$,
forces the elements in each row of ${B(\mathbf{u},\mathbf{v})}$ to add to one.
Matrix ${B(\mathbf{u},\mathbf{v})}$ converges to the optimal solution to (8)
when $N_{\text{iter}}$ goes to infinity, as claimed in [19].

Choice of $\eta$ and $\tau$. In practice, we use a small _partially labeled_
validation set to choose $\eta$ and $\tau$. Doing so, the validation set can
be obtained by splitting the training set of partially labelled data
$\mathcal{T}_{\mathsf{P}}$.

##  5 Experiments

Baselines. We consider the state-of-the-art loss semantic loss (SL) [53, 49,
15] for MI-PLL training and use the engine Scallop that performs MI-PLL
training using that loss [15]. Since there are no prior MI-PLL techniques for
mitigating imbalances at testing-time, we consider Logit Adjustment (LA) [28]
as a competitor to CAROT. The notation +A, for an algorithm
${\textsc{A}\in\\{\textsc{LA},\textsc{CAROT}\\}}$, means that the scores of a
baseline model are modified at testing-time via A. We do not assume access to
a validation set of gold labelled data, applying LA and CAROT using the
estimate $\widehat{\mathbf{r}}$ obtained via Algorithm 1. However, we use a
validation set of partially labelled data to run Algorithm 1. We also carry
experiments with RECORDS [13], a technique that mitigates imbalances at
training-time for standard PLL (again, no previous MI-PLL training-time
baseline exists). We use SL+RECORDS when a model has been trained using
RECORDS in conjunction with SL. RECORDS acts as a competitor to our LP-based
technique from Section 4.2. Notice that the imbalance mitigation technique
from [47], SoLar, cannot act as a competitor to our proposed techniques (see
Section 6 and Appendix E for a detailed discussion on SoLar). Finally, we
carry experiments using our LP-based technique. We use LP(ALG1) and LP(EMP),
when LP is applied using the estimate $\widehat{\mathbf{r}}$ obtained via
Algorithm 1 and via the approximation from [47], respectively.

Benchmarks. We carry experiments using an MI-PLL benchmark previously used in
the neurosymbolic literature [24, 25, 15, 20], namely MAX-$M$, as well as a
newly introduced, called Smallest Parent. Training samples in MAX-$M$ are as
described in Example 1.1. We vary $M$ to ${\\{3,4,5\\}}$ and use the MNIST
benchmark to obtain training and testing instances. In Smallest Parent,
training samples are of the form ${(x_{1},x_{2},p)}$, where $x_{1}$ and
$x_{2}$ are CIFAR-10 images and $p$ is the most immediate common ancestor of
$y_{1}$ and $y_{2}$, assuming the classes form a hierarchy. To simulate long-
tail phenomena (denoted as LT), we vary the imbalance ratio $\rho$ of the
distributions of the input instances as in [4, 47]: $\rho=0$ means that the
hidden label distribution is unmodified and balanced. Each cell shows mean
accuracy and standard deviation over three different runs. The results of our
analysis are summarized in Table 1 and Table 2 (an extended version of Table 1
is in the appendix).

Table 1: Experimental results for MAX-$M$ using $m_{\mathsf{P}}=3000$.

Algorithms |  Original $\rho=0$ |  LT $\rho=15$ |  LT $\rho=50$
---|---|---|---
$M=3$ | $M=4$ | $M=5$ | $M=3$ | $M=4$ | $M=5$ | $M=3$ | $M=4$ | $M=5$
SL | 84.15 $\pm$ 11.92 | 73.82 $\pm$ 2.36 | 59.88 $\pm$ 5.58 | 71.25 $\pm$ 4.48 | 66.98 $\pm$ 3.2 | 55.06 $\pm$ 5.21 | 66.74 $\pm$ 5.42 | 67.71 $\pm$ 11.58 | 55.74 $\pm$ 2.58
\+ LA | 84.17 $\pm$ 11.95 | 73.82 $\pm$ 2.36 | 59.88 $\pm$ 5.58 | 70.80 $\pm$ 4.52 | 66.98 $\pm$ 3.20 | 54.53 $\pm$ 5.74 | 66.57 $\pm$ 5.09 | 61.10 $\pm$ 3.95 | 52.47 $\pm$ 8.06
\+ CAROT | 84.57 $\pm$ 11.50 | 73.08 $\pm$ 3.10 | 60.26 $\pm$ 5.20 | 74.95 $\pm$ 3.45 | 67.44 $\pm$ 2.74 | 55.80 $\pm$ 4.47 | 68.16 $\pm$ 4.00 | 68.25 $\pm$ 6.14 | 57.29 $\pm$ 14.17
RECORDS | 85.56 $\pm$ 7.25 | 75.11 $\pm$ 0.77 | 59.43 $\pm$ 6.61 | 55.47 $\pm$ 20.45 | 53.34 $\pm$ 16.66 | 52.40 $\pm$ 7.95 | 70.20 $\pm$ 7.65 | 66.05 $\pm$ 13.90 | 59.93 $\pm$ 4.86
\+ LA | 87.63 $\pm$ 5.11 | 75.11 $\pm$ 0.77 | 59.28 $\pm$ 6.76 | 54.90 $\pm$ 20.16 | 54.46 $\pm$ 15.54 | 51.25 $\pm$ 9.09 | 70.09 $\pm$ 7.26 | 65.78 $\pm$ 14.18 | 59.93 $\pm$ 4.86
\+ CAROT | 90.97 $\pm$ 2.03 | 75.94 $\pm$ 0.91 | 60.45 $\pm$ 7.78 | 54.32 $\pm$ 21.85 | 62.74 $\pm$ 8.14 | 55.85 $\pm$ 4.61 | 71.46 $\pm$ 6.4 | 71.25 $\pm$ 8.70 | 63.64 $\pm$ 5.92
LP(EMP) | 94.97 $\pm$ 1.32 | 77.86 $\pm$ 4.22 | 55.27 $\pm$ 11.27 | 75.83 $\pm$ 5.26 | 69.67 $\pm$ 5.47 | 59.25 $\pm$ 7.27 | 77.16 $\pm$ 3.46 | 70.06 $\pm$ 10.73 | 56.79 $\pm$ 1.58
\+ LA | 94.69 $\pm$ 1.60 | 77.91 $\pm$ 4.16 | 55.34 $\pm$ 11.19 | 75.77 $\pm$ 5.32 | 68.92 $\pm$ 3.96 | 58.49 $\pm$ 5.74 | 77.1 $\pm$ 3.52 | 69.76 $\pm$ 10.31 | 56.81 $\pm$ 1.56
\+ CAROT | 95.07 $\pm$ 1.20 | 75.53 $\pm$ 7.42 | 53.07 $\pm$ 12.99 | 76.38 $\pm$ 4.72 | 69.74 $\pm$ 5.51 | 59.56 $\pm$ 8.14 | 77.58 $\pm$ 3.04 | 70.11 $\pm$ 10.34 | 57.09 $\pm$ 1.90
LP(ALG1) | 96.09 $\pm$ 0.41 | 78.34 $\pm$ 4.80 | 59.91 $\pm$ 6.63 | 74.51 $\pm$ 9.13 | 69.14 $\pm$ 1.82 | 56.81 $\pm$ 3.74 | 72.23 $\pm$ 11.49 | 69.28 $\pm$ 11.78 | 63.67 $\pm$ 7.04
\+ LA | 95.81 $\pm$ 0.74 | 78.97 $\pm$ 4.09 | 59.98 $\pm$ 6.56 | 74.26 $\pm$ 9.06 | 68.73 $\pm$ 2.23 | 56.37 $\pm$ 3.13 | 72.23 $\pm$ 11.49 | 69.21 $\pm$ 11.86 | 63.67 $\pm$ 7.04
\+ CAROT | 96.13 $\pm$ 0.38 | 80.78 $\pm$ 2.36 | 59.71 $\pm$ 6.35 | 77.05 $\pm$ 7.00 | 69.19 $\pm$ 1.81 | 59.76 $\pm$ 7.24 | 74.82 $\pm$ 10.18 | 74.30 $\pm$ 7.54 | 64.39 $\pm$ 6.43

Table 2: Experimental results for Smallest Parent using
$m_{\mathsf{P}}=10000$.

Algorithms Original $\rho=0$ LT $\rho=5$ LT $\rho=15$ LT $\rho=50$ Algorithms
Original $\rho=0$ LT $\rho=5$ LT $\rho=15$ LT $\rho=50$ SL 69.82 $\pm$ 0.53
67.94 $\pm$ 0.40 69.04 $\pm$ 0.03 74.65 $\pm$ 0.44  LP(EMP) 79.41 $\pm$ 1.33
79.24 $\pm$ 1.03 68.40 $\pm$ 1.90 70.29 $\pm$ 1.62 \+ LA 69.83 $\pm$ 0.53
67.93 $\pm$ 0.41 68.70 $\pm$ 0.30 74.62 $\pm$ 0.36  \+ LA 79.41 $\pm$ 1.33
79.24 $\pm$ 1.03 68.40 $\pm$ 1.90 70.29 $\pm$ 1.62 \+ CAROT 69.82 $\pm$ 0.53
67.93 $\pm$ 0.41 68.70 $\pm$ 0.41 74.15 $\pm$ 0.47  \+ CAROT 79.41 $\pm$ 1.33
79.28 $\pm$ 0.91 77.10 $\pm$ 1.74 80.71 $\pm$ 1.50 RECORDS 48.71 $\pm$ 3.90
48.15 $\pm$ 4.56 50.14 $\pm$ 1.10 55.12 $\pm$ 1.40  LP(ALG1) 80.23 $\pm$ 0.70
81.27 $\pm$ 0.71 81.99 $\pm$ 0.51 83.44 $\pm$ 0.48 \+ LA 54.12 $\pm$ 2.00
45.48 $\pm$ 2.31 56.83 $\pm$ 1.30 60.87 $\pm$ 1.20  \+ LA 80.20 $\pm$ 0.74
81.26 $\pm$ 0.72 81.99 $\pm$ 0.51 83.44 $\pm$ 0.48 \+ CAROT 68.16 $\pm$ 0.47
69.04 $\pm$ 0.74 71.70 $\pm$ 0.84 75.69 $\pm$ 0.90  \+ CAROT 68.90 $\pm$ 11.09
76.38 $\pm$ 5.68 82.00 $\pm$ 0.51 83.44 $\pm$ 0.48

Conclusions. Our empirical analysis reveals the following interesting
phenomena: (i) training-time mitigation can significantly improve the
accuracy; (ii) state-of-the-art on training-time mitigation might not
appropriate for MI-PLL; (iii) approximate techniques for estimating
${\mathbf{r}}$ can sometimes be more effective when used for training-time
mitigation; (iv) testing-time mitigation can substantially improve the
accuracy of a model; however, it tends to be less effective than training-time
mitigation; (v) CAROT may be sensitive to the quality of estimated ratios
$\widehat{\mathbf{r}}$.

Regarding (i), let us focus on Table 2. We can see that both LP(EMP) and
LP(ALG1) lead to higher accuracy than models trained exclusively via SL. For
example, when $\rho=5$ in Smallest Parent, the mean accuracy obtained via
training under SL is 67.94%; the mean accuracy increases to 79.24% under
LP(EMP) and to 81.27% under LP(ALG1). In MAX-4, the mean accuracy under SL is
55.48%, increasing to 78.56% under LP(ALG1). Regarding (ii), consider again
Table 2. We can see that when RECORDS is applied jointly with SL, the accuracy
of the model can substantially drop, e.g., when $\rho=5$ in Table 2, the mean
accuracy drops from 67.94% to 48.15%. In the MAX-$M$ scenarios, RECORDS seems
to improve over SL; however, for certain scenarios the accuracy drops
drastically (e.g., for $\rho=15$). The above stresses the importance of our
LP-based technique.

Figure 3: Impact of the label ratio quality on the performance of CAROT.

Let’s now move to (iii). In most of the cases, LP(ALG1) leads to higher
accuracy than LP(EMP). However, the opposite may also hold in some cases. One
such example is the MAX-$3$ scenario, for $\rho=50$: the mean accuracy for the
baseline model is 66.74%, increasing to 72.23% under LP(ALG1) and to 77.16%
under LP(EMP). A similar phenomenon is observed for $\rho=15$ for the same
scenario. This is an interesting phenomenon, as it suggests that there can be
cases where employing the gold ratios (Algorithm 1 produces estimates that
converge to the gold ratios, see Proposition C.1) may not always be the best
solution. A similar observation is done by the authors of RECORDS [13]. One
cause of this phenomenon is the high number of classification errors observed
during the initial stages of learning. Those classification errors can become
higher in our experimental setting, as in the MAX-$M$ scenarios, we only
consider a subset of the pre-images of each partial label to compute SL and
(7), in order to reduce the computational overhead of computing all pre-
images.

We conclude with CAROT. Tables 1 and 2 show that CAROT can be more effective
than LA. For example, in the MAX-$3$ scenarios and $\rho=50$, the mean
accuracy is 66.74% under SL, drops to 66.57% under SL+LA and increases to
68.16% under SL+CAROT. In Smallest Parent and $\rho=50$, the mean accuracy of
LP(EMP) increases from 70.29% to 80.71% under CAROT; LA has no impact. CAROT
also improves the accuracy of RECORDS models, often, by a large margin. For
example, for Smallest Parent and $\rho=15$, the mean accuracy of a RECORDS-
based trained model increases from 50.14% to 71.70% when CAROT is applied.
CAROT is also consistently better than LA when applied on top of RECORDS.
However, there can be cases where both LA and CAROT drop the accuracy of the
baseline model. One such example is met in Smallest Parent and $\rho=5$: the
mean accuracy under LP(ALG1) is 81.27% and drops to 76.38% when CAROT is
applied.

We analyse the sensitivity of CAROT under the quality of the input
$\widehat{\mathbf{r}}$, where quality is measured by means of the KL
divergence to $\mathbf{r}$. Figure 3 shows the accuracy of an MNIST model
(trained with the MAX-3 dataset), when CAROT is applied at testing-time using
500 randomly generated ratios $\widehat{\mathbf{r}}$ of varying quality. We
observe that CAROT’s effectiveness drops as the estimated marginal diverges
more from $\mathbf{r}$. Also, the performance can decrease by more than 10%
with only a small perturbation in the KL divergence. This instability may be
the reason CAROT fails to improve a base model.

##  6 Related work

An extended version and more detailed comparison against the related work is
in Appendix E.

Long-tail supervised learning. Two techniques on supervised learning that
relate to our work are LA [28] and OTLM [31]. Both aim at testing-time
mitigation. LA modifies the classifier’s scores by subtracting the gold
ratios, i.e., via ${\operatorname*{argmax}_{y\in[c]}f^{y}(x)-\ln(r_{y})}$.
CAROT can be substantially more effective than LA, see Section 5. OTLM assumes
that the marginal $\mathbf{r}$ is known, resorting to an OT formulation for
adjusting the classifier’s scores. In contrast, we propose a statistically
consistent technique to estimate $\mathbf{r}$, see Section 4.1, and resort to
RSOT to accommodate for noisy $\widehat{\mathbf{r}}$’s.

Long-tail PLL. Results showing that certain classes are harder to learn than
others in standard PLL were presented in [7]. We are the first to extend those
results for MI-PLL. The only two works in the intersection of long-tail
learning and (single-instance) PLL are RECORDS [13] and SoLar [47]. Both aim
at training-time mitigation. RECORDS modifies the classifier’s scores
following the same idea with LA. It employs a momentum-updated prototype
feature to estimate $\widehat{\mathbf{r}}$. Differently from our LP-based
technique, it does not take into account the constraints coming from MI-PLL.
Section 5 shows that RECORDS is less effective than our proposed techniques,
degrading the baseline accuracy on multiple occasions. On the other hand,
SoLar relies on standard OT for assigning pseudo-labels to partially labelled
instances, in contrast to our LP formulation (7). Also, SoLar uses a moving
average technique to estimate ${\mathbf{r}}$, as opposed to Algorithm 1. See
Section E for a detailed discussion on SoLar.

##  7 Conclusions

Our work is the first to theoretically characterize and mitigate learning
imbalances in MI-PLL. Our theoretical characterization complements the
existing theory in long-tail learning, identifying and addressing the unique
challenges in MI-PLL. Additionally, we contributed an ILP-based and an RSOT-
based mitigation technique that both outperform state-of-the-art in long-tail
learning. Our empirical analysis unveiled two topics for future research:
_computing marginal for testing-time mitigation_ and _designing more effective
testing-time mitigation techniques_. Another important future direction is to
extend our theoretical analysis to more practical scenarios by dropping the
i.i.d. assumption, which is the key to our label-specific bound formulation in
Eq. (4).

## References

  * [1] Stephen Boyd and Lieven Vandenberghe.  Convex optimization.  Cambridge University Press, 2004.
  * [2] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski.  A systematic study of the class imbalance problem in convolutional neural networks.  Neural Networks, 106:249–259, 2018.
  * [3] Vivien Cabannes, Alessandro Rudi, and Francis Bach.  Structured prediction with partial labelling through the infimum loss.  In ICML, page 1230–1239, 2020.
  * [4] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In NeurIPS, pages 1567–1578, 2019.
  * [5] Ming-Wei Chang, Lev Ratinov, and Dan Roth.  Guiding Semi-Supervision with Constraint-Driven Learning.  In Proc. of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 280–287, Prague, Czech Republic, 6 2007. Association for Computational Linguistics.
  * [6] Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer.  Smote: synthetic minority over-sampling technique.  Journal of Artificial Intelligence Research, 16(1):321–357, 2002.
  * [7] Timothee Cour, Ben Sapp, and Ben Taskar.  Learning from partial labels.  Journal of Machine Learning Research, 12:1501–1536, 2011.
  * [8] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In NeurIPS, 2013.
  * [9] Wang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou.  Bridging Machine Learning and Logical Reasoning by Abductive Learning.  In NeurIPS, pages 2815–2826, 2019.
  * [10] Kuzman Ganchev, João Graça, Jennifer Gillenwater, and Ben Taskar.  Posterior regularization for structured latent variable models.  Journal of Machine Learning Research, 11:2001–2049, 2010.
  * [11] Nitish Gupta, Sameer Singh, Matt Gardner, and Dan Roth.  Paired examples as indirect supervision in latent decision models.  In EMNLP, pages 5774–5785, 2021.
  * [12] Haibo He and Edwardo A. Garcia.  Learning from imbalanced data.  IEEE Transactions on Knowledge and Data Engineering, 21(9):1263–1284, 2009.
  * [13] Feng Hong, Jiangchao Yao, Zhihan Zhou, Ya Zhang, and Yanfeng Wang.  Long-tailed partial label learning via dynamic rebalancing.  In ICLR, 2023.
  * [14] Grant Van Horn and Pietro Perona.  The devil is in the tails: Fine-grained classification in the wild.  CoRR, abs/1709.01450, 2017.
  * [15] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si.  Scallop: From probabilistic deductive databases to scalable differentiable reasoning.  In NeurIPS, pages 25134–25145, 2021.
  * [16] Robert I. Jennrich.  Asymptotic properties of non-linear least squares estimators.  The Annals of Mathematical Statistics, 40(2):633–643, 1969.
  * [17] Rong Jin and Zoubin Ghahramani.  Learning with multiple labels.  In NeurIPS, pages 897–904, 2002.
  * [18] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis.  Decoupling representation and classifier for long-tailed recognition.  In ICLR, 2020.
  * [19] Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho.  On robust optimal transport: Computational complexity and barycenter computation.  In Advances in Neural Information Processing Systems, pages 21947–21959, 2021.
  * [20] Zenan Li, Yuan Yao, Taolue Chen, Jingwei Xu, Chun Cao, Xiaoxing Ma, and Jian Lu.  Softened symbol grounding for neurosymbolic systems.  In ICLR, 2023.
  * [21] Tianyi Lin, Nhat Ho, Marco Cuturi, and Michael I. Jordan.  On the complexity of approximating multimarginal optimal transport.  Journal of Machine Learning Research, 23(1), 2022.
  * [22] Wenpeng Liu, Li Wang, Jie Chen, Yu Zhou, Ruirui Zheng, and Jianjun He.  A partial label metric learning algorithm for class imbalanced data.  In ACML, volume 157, pages 1413–1428, 2021.
  * [23] Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama.  Progressive identification of true labels for partial-label learning.  In ICML, page 6500–6510, 2020.
  * [24] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  Deepproblog: Neural probabilistic logic programming.  In NeurIPS, pages 3749–3759, 2018.
  * [25] Robin Manhaeve, Giuseppe Marra, and Luc De Raedt.  Approximate Inference for Neural Probabilistic Logic Programming.  In KR, pages 475–486, 2021.
  * [26] Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini.  Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts.  In NeurIPS, 2023.
  * [27] Stephen Mayhew, Snigdha Chaturvedi, Chen-Tse Tsai, and Dan Roth.  Named Entity Recognition with Partially Annotated Training Data.  In Proc. of the Conference on Computational Natural Language Learning (CoNLL), 2019.
  * [28] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar.  Long-tail learning via logit adjustment.  In ICLR, 2021.
  * [29] Tsvetomila Mihaylova, Vlad Niculae, and André F. T. Martins.  Understanding the mechanics of SPIGOT: Surrogate gradients for latent structure learning.  In EMNLP, pages 2186–2202, 2020.
  * [30] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of Machine Learning.  The MIT Press, 2nd edition, 2018.
  * [31] Hanyu Peng, Mingming Sun, and Ping Li.  Optimal transport for long-tailed recognition with learnable cost matrix.  In ICLR, 2022.
  * [32] Hao Peng, Sam Thomson, and Noah A. Smith.  Backpropagating through structured argmax using a SPIGOT.  In ACL, pages 1863–1873, 2018.
  * [33] Gabriel Peyré and Marco Cuturi.  Computational optimal transport, 2020.
  * [34] Aditi Raghunathan, Roy Frostig, John Duchi, and Percy Liang.  Estimation from indirect supervision with linear moments.  In ICML, volume 48, pages 2568–2577, 2016.
  * [35] Dan Roth and Wen-tau Yih.  Global Inference for Entity and Relation Identification via a Linear Programming Formulation.  MIT Press, Introduction to Statistical Relational Learning edition, 2007.
  * [36] Rajhans Samdani, Ming-Wei Chang, and Dan Roth.  Unified expectation maximization.  In ACL, pages 688–698, 2012.
  * [37] Junghoon Seo and Joon Suk Huh.  On the power of deep but naive partial label learning.  In ICASSP, pages 3820–3824, 2021.
  * [38] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning: From Theory to Algorithms.  Cambridge University Press, USA, 2014.
  * [39] Vivek Srikumar and Dan Roth.  The integer linear programming inference cookbook.  ArXiv, abs/2307.00171, 2023.
  * [40] Jacob Steinhardt and Percy S Liang.  Learning with relaxed supervision.  In NeurIPS, volume 28, 2015.
  * [41] Jingru Tan, Xin Lu, Gang Zhang, Changqing Yin, and Quanquan Li.  Equalization loss v2: A new gradient balance approach for long-tailed object detection.  In CVPR, pages 1685–1694, June 2021.
  * [42] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan.  Equalization loss for long-tailed object recognition.  In CVPR, pages 11662–11671, 2020.
  * [43] Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael.  Neural-symbolic integration: A compositional perspective.  In AAAI, pages 5051–5060, 2021.
  * [44] Grigori S Tseitin.  On the complexity of derivation in propositional calculus.  Automation of reasoning, 298:466–483, 1983.
  * [45] Shyam Upadhyay, Ming-Wei Chang, Kai-Wei Chang, and Wen-tau Yih.  Learning from explicit and implicit supervision jointly for algebra word problems.  In EMNLP, pages 297–306, 2016.
  * [46] A. W. van der Vaart.  Asymptotic Statistics.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
  * [47] Haobo Wang, Mingxuan Xia, Yixuan Li, Yuren Mao, Lei Feng, Gang Chen, and Junbo Zhao.  Solar: Sinkhorn label refinery for imbalanced partial-label learning.  In NeurIPS, 2022.
  * [48] Kaifu Wang, Hangfeng He, Tin D. Nguyen, Piyush Kumar, and Dan Roth.  On Regularization and Inference with Label Constraints.  In ICML, 2023.
  * [49] Kaifu Wang, Efthymia Tsamoura, and Dan Roth.  On learning latent models with multi-instance weak supervision.  In NeurIPS, 2023.
  * [50] Lei Wang, Dongxiang Zhang, Jipeng Zhang, Xing Xu, Lianli Gao, Bing Tian Dai, and Heng Tao Shen.  Template-based math word problem solvers with recursive neural networks.  In AAAI, pages 7144–7151, 2019.
  * [51] Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter.  Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.  In ICML, 2019.
  * [52] Hongwei Wen, Jingyi Cui, Hanyuan Hang, Jiabin Liu, Yisen Wang, and Zhouchen Lin.  Leveraged weighted loss for partial label learning.  CoRR, abs/2106.05731, 2021.
  * [53] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck.  A semantic loss function for deep learning with symbolic knowledge.  In ICML, pages 5502–5511, 2018.
  * [54] Ning Xu, Congyu Qiao, Xin Geng, and Min-Ling Zhang.  Instance-dependent partial label learning.  In NeurIPS, volume 34, pages 27119–27130, 2021.
  * [55] Zhun Yang, Adam Ishay, and Joohyung Lee.  NeurASP: Embracing neural networks into answer set programming.  In IJCAI, pages 1755–1762, 2020.
  * [56] Peilin Yu, Tiffany Ding, and Stephen H. Bach.  Learning from multiple noisy partial labelers.  In PMLR, volume 151, pages 11072–11095, 2022.
  * [57] Jieyu Zhang, Cheng-Yu Hsieh, Yue Yu, Chao Zhang, and Alexander J. Ratner.  A survey on programmatic weak supervision.  ArXiv, abs/2202.05433, 2022.
  * [58] Yivan Zhang, Nontawat Charoenphakdee, Zheng Wu, and Masashi Sugiyama.  Learning from aggregate observations.  In NeurIPS, 2020.
  * [59] Zhi-Hua Zhou.  A brief introduction to weakly supervised learning.  National Science Review, 5(1):44–53, 08 2017.

##  Appendix A Extended preliminaries

Optimal transport. Let $Z_{1}$ and $Z_{2}$ be two discrete random variables
over ${[m_{1}]}$ and ${[m_{2}]}$. For ${i\in[2]}$, vector
${\mathbf{b}^{i}\in\mathbb{R}_{+}^{m_{i}}}$ denotes the probability
distribution of $Z_{i}$, i.e., ${\mathbbm{P}(Z_{i}=m_{j})=b^{i}_{j}}$, for
each ${j\in[m_{i}]}$. Let $U$ be the set of matrices defined as
${\\{\mathbf{Q}\in\mathbb{R}_{+}^{m_{1}\times
m_{2}}|\mathbf{Q}\mathbf{1}_{m_{1}}=\mathbf{b}^{2},\mathbf{Q}\mathbf{1}_{m_{2}}=\mathbf{b}^{1}\\}}$.
The _optimal transport_ (OT) problem [33] asks us to find the matrix
${\mathbf{Q}\in U}$ that maximizes a linear object subject to marginal
constraints, namely

$\min_{\mathbf{Q}\in U}\langle\mathbf{P},\mathbf{Q}\rangle$ (9)

Assume that we are strict in enforcing the probability distribution
$\mathbf{b}^{1}$, but not in enforcing $\mathbf{b}^{2}$. The _robust semi-
constrained optimal transport_ (RSOT) problem [19] aims to find:

$\displaystyle\min_{\mathbf{Q}\in
U^{\prime}}\langle\mathbf{P},\mathbf{Q}\rangle+\tau\text{KL}(\mathbf{Q}\mathbf{1}_{m_{1}}||\mathbf{b}^{2})$
(10)

where ${U^{\prime}=\\{\mathbf{Q}\in\mathbb{R}_{+}^{m_{1}\times
m_{2}}|\mathbf{Q}\mathbf{1}_{m_{2}}=\mathbf{b}^{1}\\}}$ and $\tau>0$ is a
regularization parameter. In practice, the solution of (10) can be
approximated in polynomial time using the _robust semi-Sinkhorn algorithm_
that is proposed in [19], which generalizes the classical Sinkhorn algorithm
[8] for OT.

##  Appendix B Proofs and details for Section 3

See 3.1

###### Proof.

This result directly follows from the definition of the program (4). ∎

See 3.3

###### Proof.

To start with, let $L_{\sigma}\circ[\mathcal{F}]$ be the function space that
maps a (training) example $(\mathbf{x},s)$ to its partial loss:

$\displaystyle L_{\sigma}\circ[\mathcal{F}]:=\\{(\mathbf{x},s)\mapsto
L_{\sigma}([f](\mathbf{x}),s)|f\in\mathcal{F}\\}$ (11)

The standard generalization bound with VC dimension (see, for example,
Corollary 3.19 of [30]) implies that:

$\displaystyle
R_{\mathsf{P}}(f)\leq\widehat{R}_{\mathsf{P}}(f;\mathcal{T}_{\mathsf{P}})+\sqrt{\frac{2\log(\mathrm{e}m_{\mathsf{P}}/d_{\mathrm{VC}}(L_{\sigma}\circ[\mathcal{F}]))}{m_{\mathsf{P}}/d_{\mathrm{VC}}(L_{\sigma}\circ[\mathcal{F}])}}+\sqrt{\frac{\log(1/\delta)}{2m_{\mathsf{P}}}}$
(12)

where $d_{\mathrm{VC}}(\cdot)$ is the VC dimension. For simplicity, let
$d=d_{\mathrm{VC}}(L_{\sigma}\circ[\mathcal{F}])$ and $d_{[\mathcal{F}]}$ be
the Natarajan dimension of $[\mathcal{F}]$. Using a similar argument as in
[49], given any $d$ samples in $\mathcal{X}^{M}\times\mathcal{O}$ using
${[\mathcal{F}]}$, we let $N$ be the maximum number of distinct ways to assign
label vectors (in $\mathcal{Y}^{M}$) to these $d$ samples. Then, the
definition of VC-dimension implies that:

$\displaystyle 2^{d}\leq N$ (13)

On the other hand, these $d$ samples contain $Md$ input instances in
$\mathcal{X}$. By Natarajan’s lemma (see, for example, Lemma 29.4 of [38]), we
have that:

$N\leq(Md)^{d_{[\mathcal{F}]}}c^{2d_{[\mathcal{F}]}}$ (14)

Combining (14) with the above equations, it follows that

$\displaystyle(Md)^{d_{[\mathcal{F}]}}c^{2d_{[\mathcal{F}]}}\geq N\geq 2^{d}$
(15)

Taking the logarithm on both sides, we have that:

$\displaystyle d_{[\mathcal{F}]}\log(Md)+2d_{[\mathcal{F}]}\log c\geq d\log 2$
(16)

Taking the first-order Taylor series expansion of the logarithm function at
the point $6d_{[\mathcal{F}]}$, we have:

$\displaystyle\log(d)\leq\frac{d}{6d_{[\mathcal{F}]}}+\log(6d_{[\mathcal{F}]})-1$
(17)

Therefore,

$\displaystyle d\log 2$ $\displaystyle\leq d_{[\mathcal{F}]}\log
d+d_{[\mathcal{F}]}\log M+2d_{[\mathcal{F}]}\log c$ (18) $\displaystyle\leq
d_{[\mathcal{F}]}\left(\frac{d}{6d_{[\mathcal{F}]}}+\log(6d_{[\mathcal{F}]})-1\right)+d_{[\mathcal{F}]}\log
M+2d_{[\mathcal{F}]}\log c$
$\displaystyle=\frac{d}{6}+d_{[\mathcal{F}]}\log(6Mc^{2}d_{[\mathcal{F}]}/\mathrm{e})$

Rearranging the inequality yields

$\displaystyle d$
$\displaystyle\leq\frac{d_{[\mathcal{F}]}\log(6Mc^{2}d_{[\mathcal{F}]}/\mathrm{e})}{\log
2-1/6}$ (19) $\displaystyle\leq
2d_{[\mathcal{F}]}\log(6Mc^{2}d_{[\mathcal{F}]}/\mathrm{e})$

as claimed. ∎

See 3.5

###### Proof.

As we discussed in the text, to find a loose bound of $R(f)$, we first define
$\mathbf{w}:=\sum_{i=1}^{c}r_{i}\mathbf{w}_{i}$ so that
$R(f)=\mathbf{w}^{\mathsf{T}}\mathbf{h}$. Then, we consider the following
relaxed program:

$\displaystyle\max_{\mathbf{h}}$
$\displaystyle\mathbf{w}^{\mathsf{T}}\mathbf{h}$ (20)
$\displaystyle\mathrm{s.t.}$
$\displaystyle\mathbf{h}^{\mathsf{T}}D(\mathbf{\Sigma}_{\sigma,\mathbf{r}})\mathbf{h}\leq
R_{\mathsf{P}}$

where $D(\mathbf{\Sigma}_{\sigma,\mathbf{r}})$ is the diagonal part of
$\mathbf{\Sigma}_{\sigma,\mathbf{r}}$, namely

$\displaystyle
D(\mathbf{\Sigma}_{\sigma,\mathbf{r}})=[r_{i}r_{j}\mathbbm{1}\\{i=j\\}\mathbbm{1}\\{i\not\equiv
j\;(\mathrm{mod}\;c)\\}]_{i\in[c^{2}],j\in[c^{2}]}$ (21)

In other words, $D(\mathbf{\Sigma}_{\sigma,\mathbf{r}})$ encodes all the
partial risks that is caused by repeating the same type of misclassification
twice. On the other hand, the $M$-unambiguity condition ensures that each type
of misclassification, when repeated twice, leads to a misclassification of the
partial label. Therefore,
$\mathbf{w}\in\mathrm{Range}(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))$.

The problem (20) is a special case of the single constraint quadratic
optimization problem. Then, the fact that
$\mathbf{w}\in\mathrm{Range}(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))$ implies
that the dual function of this problem (with dual variable $\lambda$) is

$\displaystyle g(\lambda)=\lambda
R_{\mathsf{P}}+\frac{\mathbf{w}^{\mathsf{T}}(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))^{\dagger}\mathbf{w}}{4\lambda}$
(22)

where $(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))^{\dagger}$ is the pseudo-
inverse, namely

$\displaystyle(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))^{\dagger}=[(r_{i}r_{j})^{-1}\mathbbm{1}\\{i=j\\}\mathbbm{1}\\{i\not\equiv
j\;(\mathrm{mod}\;c)\\}]_{i\in[c^{2}],j\in[c^{2}]}$ (23)

Therefore,

$\displaystyle\mathbf{w}^{\mathsf{T}}(D(\mathbf{\Sigma}_{\sigma,\mathbf{r}}))^{\dagger}\mathbf{w}=c(c-1)$
(24)

According to Appendix B of [1], strong duality holds for this problem.
Therefore, the optimal value is given exactly as

$\displaystyle\inf_{\lambda\geq
0}g(\lambda)=2\sqrt{\frac{c(c-1)}{4}R_{\mathsf{P}}}=\sqrt{c(c-1)R_{\mathsf{P}}}$
(25)

as claimed. ∎

##  Appendix C Theoretical guarantees for Algorithm 1

The estimate $\widehat{\mathbf{r}}$ given by Algorithm 1 can be viewed as a
method to find the maximum likelihood estimation, whose consistency is
guaranteed under suitable conditions. The most critical one is the
invertibility of $\Psi_{\sigma}$. The invertibility is satisfied by practical
transitions as the one from Example 1.1, but may fail to hold for certain
transitions even if the $M$-unambiguity condition [49] holds. We will provide
one such example later in this section.

Suppose our optimizer (the backprobagation step in Algorithm 1) can
effectively find the maximum likelihood estimator. For a real $\epsilon>0$,
let $\Delta_{c}^{\epsilon}$ be the shrinked probability simplex that is
defined as
${\\{\mathbf{r}\in\Delta_{c}|r_{j}\geq\epsilon\,\forall\,j\in[c]\\}}$. Let
$\widehat{\mathbf{r}}^{*}_{m_{\mathsf{p}}}:=\operatorname*{argmin}_{\widehat{\mathbf{r}}\in\Delta_{c}^{\epsilon}}\sum_{j=1}^{c_{S}}\bar{p}_{j}\log[\Psi_{\sigma}(\widehat{\mathbf{r}})]_{j}$
be the maximum likelihood estimation. We have that:

######  Proposition C.1 (Consistency).

If there exists an $\epsilon>0$, such that
$\mathbf{r}\in\Delta_{c}^{\epsilon}$ and $\Psi_{\sigma}$ is injective in
$\Delta_{c}^{\epsilon}$, then
$\widehat{\mathbf{r}}^{*}_{m_{\mathsf{p}}}\rightarrow\mathbf{r}$ in
probability as $m_{\mathsf{P}}\rightarrow\infty$.

###### Proof.

Let
$\Delta_{c_{S}}^{\sigma,\epsilon}:=\\{\Psi_{\sigma}(\mathbf{r})|\mathbf{r}\in\Delta_{c}^{\epsilon}\\}$
be the image of $\Psi_{\sigma}$ on $\Delta_{c}^{\epsilon}$. The set
$\Delta_{c_{S}}^{\sigma,\epsilon}$ is a compact subset in
$\mathbbm{R}^{c_{S}}$. For any partial label $a_{j}\in\mathcal{S}$, let
$H(a_{j},\mathbf{r}):=-\log([\Psi_{\sigma}(\mathbf{r})]_{j})$ be the point-
wise log-likelihood. The $M$-unambiguity condition ensures that each
coordinate of every vector in $\Delta_{c_{S}}^{\sigma,\epsilon}$ should be at
least $\epsilon^{M}$, and hence the function $H$ is bounded on
$\Delta_{c_{S}}^{\sigma,\epsilon}$. By Theorem 1 of [16], this ensures that
$\sum_{s}H(s,\mathbf{r})$ converges uniformly to
$\mathbbm{E}_{S}[H(S,\mathbf{r})]$. According to [46] (Theorem 5.7), the
uniform convergence further ensures that
$\Psi_{\sigma}(\widehat{\mathbf{r}}^{*}_{m_{\mathsf{p}}})\rightarrow\mathbf{p}$
in probability as $m_{\mathsf{P}}\rightarrow\infty$. Since $\Psi_{\sigma}$ is
invertible, this implies that
$\widehat{\mathbf{r}}^{*}_{m_{\mathsf{p}}}\rightarrow\mathbf{r}$ in
probability. ∎

Counterexample where invertibility fails to hold. Consider the following
transition function for binary labels ($\mathcal{Y}=\\{0,1\\}$) and $M=4$:

$\displaystyle\sigma(y_{1},y_{2},y_{3},y_{4})=\left\\{\begin{aligned}
1&,\quad\sum_{i=1}^{4}y_{i}\in\\{1,2,4\\}\\\
0&,\quad\text{otherwise}\end{aligned}\right.$ (26)

The $M$-unambiguity condition [49] holds since
$\sigma(0,0,0,0)\neq\sigma(1,1,1,1)$. On the other hand, the probability that
the partial label equal to 1 can be expressed as:

$\displaystyle\mathbbm{P}(s=1)=r_{1}^{4}+6r_{1}^{2}r_{0}^{2}+4r_{1}r_{0}^{3}=r_{1}^{4}+6r_{1}^{2}(1-r_{1})^{2}+4r_{1}(1-r_{1})^{3}$
(27)

which is not an injection, as we can see from the plot of the function
$t\mapsto t^{4}+6t^{2}(1-t)^{2}+4t(1-t)^{3}$ from below.

Figure 4: Plot of the function $t\mapsto t^{4}+6t^{2}(1-t)^{2}+4t(1-t)^{3}$.

##  Appendix D Details for Section 4.2

###  D.1 A non-linear program formulation

A straightforward idea that accommodates the requirements set in Section 4.2
is to reformulate (10) by firstly, extending $\mathbf{P}$ (resp. $\mathbf{Q}$)
to a tensor of size ${n\times c\times M}$ to store the scores (resp. pseudo-
labels) of $M$-ary tuples of instances and secondly, modifying $U^{\prime}$ so
that the combinations of entries in $\mathbf{Q}$ corresponding to invalid
label assignments are forced to zero product. The pitfall is that modifying
$U^{\prime}$ in this way does not allow us to employ Sinkhorn-like techniques
as the one in [21], leaving us only with the option to employ non-
linear111Non-linearity comes from the KL term, as well as by enforcing invalid
label combinations to have product equal to zero. programming techniques to
find $\mathbf{Q}$.

###  D.2 Deriving the linear program from (7)

Let ${(x_{\ell,1},\dots,x_{\ell,m},s_{\ell})}$ denote the $\ell$-th partial
training sample, where ${\ell\in[n]}$. For simplicity, we assume a single
classifier $f$ and use $L$ to denote the size of the output domain. Each
prediction is uniquely associated with a Boolean variable. In particular, we
denote by $q_{\ell,i,j}$ the Boolean variable that becomes true if and only if
$x_{\ell,i}$ is assigned with label $j$. Let
${\mathbf{y}_{\ell,1},\dots,\mathbf{y}_{\ell,R_{\ell}}}$ denote the vectors of
labels whose image under $\sigma$ is $s_{\ell}$, i.e.,
${\sigma(\mathbf{y}_{\ell,r})=s_{\ell}}$, for ${r\in[R_{\ell}]}$. Based on the
above, each vector of labels $\mathbf{y}_{\ell,r}$ is associated with a
conjunction of Boolean variables $\varphi_{\ell,r}$ from the set
${\\{q_{\ell,i,j}|i\in[m],j\in[L]\\}}$, while the training sample
${(x_{\ell,1},\dots,x_{\ell,m},s_{\ell})}$ is associated with the DNF formula
$\Phi_{\ell}=\bigvee_{r=1}^{R_{\ell}}\varphi_{\ell,r}$. In the discussion that
follows, we assume a canonical ordering over the variables occurring in
$\varphi_{\ell,r}$ and use $\varphi_{\ell,r,j}$ to refer to the $j$-th
variable and ${|\varphi_{\ell,r}|}$ to denote the number of (unique) variables
occurring $\varphi_{\ell,r}$.

Our objective is to construct a linear program whose solutions capture the
label assignments that abide by $\sigma$. In particular, the labels assigned
to each ${(x_{\ell,1},\dots,x_{\ell,m})}$ should be either of
${\mathbf{y}_{\ell,1},\dots,\mathbf{y}_{\ell,R_{\ell}}}$. The construction of
the linear program proceeds as in [39]. In particular, we first translate each
$\Phi_{\ell}$ into a CNF formula $\Phi^{\prime}_{\ell}$. Then, out of each
clause in $\Phi^{\prime}_{\ell}$, we add the corresponding linear constraints.

Starting from $\Phi_{\ell}=\bigvee_{r=1}^{R_{\ell}}\varphi_{\ell,r}$, the
first step of the Tseytin transformation associates a fresh Boolean variable
$\alpha_{\ell,r}$ with each disjunction ${\varphi_{\ell,r}}$ in $\Phi_{\ell}$
and introduces the constraint
${\Lambda_{\ell,r}:=\alpha_{\ell,r}\leftrightarrow\bigwedge_{j=1}^{|\varphi_{\ell,r}|}\varphi_{\ell,r,j}}$,
where ${r\in[R_{\ell}]}$. Recall that $\varphi_{\ell,r,j}$ refers to the
$j$-th variable occurring in $\varphi_{\ell,r}$ and hence, it is a variable
from ${\\{q_{\ell,i,j}|i\in[m],j\in[L]\\}}$. Then, $\Phi^{\prime}_{\ell}$ is
logically equivalent to the formula:

$\displaystyle\Phi^{\prime}_{\ell}:=$
$\displaystyle\underbrace{\bigvee_{r=1}^{R_{\ell}}\alpha_{\ell,r}}_{\Psi_{\ell}}\wedge\bigwedge_{r=1}^{R_{\ell}}\Lambda_{\ell,r}$
(28)

We proceed as follows. Similarly to [39], we will use the Iverson bracket to
map Boolean variables to their corresponding integer ones, e.g.,
$[q_{\ell,i,j}]$, denotes the integer variable associated with the Boolean
variable $q_{\ell,i,j}$.

The first inequality that will be added to the linear program corresponds to
formula $\Psi_{\ell}$. In particular, using Constraint (3) from [39],
$\Psi_{\ell}$ is associated with the inequality
${\sum_{r=1}^{R_{\ell}}[\alpha_{\ell,r}]\geq 1}$. The next inequalities
correspond to each $\Lambda_{\ell,r}$. Notice that $\Lambda_{\ell,r}$ can be
written as the conjunction of formulas:

$\displaystyle\alpha_{\ell,r}$
$\displaystyle\rightarrow\bigwedge_{j=1}^{|\varphi_{\ell,r}|}\varphi_{\ell,r,j}$
(29) $\displaystyle\bigwedge_{j=1}^{|\varphi_{\ell,r}|}\varphi_{\ell,r,j}$
$\displaystyle\rightarrow\alpha_{\ell,r}$ (30)

According to Constraint (10) from [39], (29) and (30) are associated with the
following inequalities:

$\displaystyle-|\varphi_{\ell,r}|[\alpha_{\ell,r}]+\sum_{j=1}^{|\varphi_{\ell,r}|}[\varphi_{\ell,r,j}]$
$\displaystyle\geq 0$ (31)
$\displaystyle-\sum_{j=1}^{|\varphi_{\ell,r}|}[\varphi_{\ell,r,j}]+[\alpha_{\ell,r}]$
$\displaystyle\geq(1-|\varphi_{\ell,r}|)$ (32)

Lastly, according to Constraint (5) from [39], we have an equality
${\sum_{j=1}^{L}[q_{\ell,i,j}]=1}$ for each ${\ell\in[n],i\in[m]}$, while we
require each score $q_{\ell,i,j}$ to be in $[0,1]$, for each
${\ell\in[n],i\in[M],j\in[c]}$.

Putting everything together, we have the following linear program.

minimize
$\displaystyle\min_{(\mathbf{Q}_{1},\dots,\mathbf{Q}_{m})\in\Delta^{m}}\sum_{i=1}^{m}\langle\mathbf{Q}_{i},-\log(\mathbf{P}_{i})\rangle,$
(33) subject to
$\displaystyle\begin{array}[]{rll}\sum_{r=1}^{R_{\ell}}[\alpha_{\ell,r}]&\geq
1,&\ell\in[n],\\\
-|\varphi_{\ell,r}|[\alpha_{\ell,r}]+\sum_{j=1}^{|\varphi_{\ell,r}|}[\varphi_{\ell,r,j}]&\geq
0,&\ell\in[n],r\in[R_{\ell}]\\\
-\sum_{j=1}^{|\varphi_{\ell,r}|}[\varphi_{\ell,r,j}]+[\alpha_{\ell,r}]&\geq-1(1-|\varphi_{\ell,r}|),&\ell\in[n],r\in[R_{\ell}]\\\
\sum_{j=1}^{L}[q_{\ell,i,j}]&=1,&\ell\in[n],i\in[m]\\\
\left[q_{\ell,i,j}\right]&\in[0,1],&\ell\in[n],i\in[M],j\in[c]\\\ \end{array}$

The program in Section 4.2 results after adding to the above program
constraints coming from the marginal $\widehat{\mathbf{r}}$.

##  Appendix E Extended related work

Long-tail learning. The term _long-tail learning_ has been used to describe
settings in which instances of some classes occur very frequently in the
training set, with other classes being underrepresented. The problem has
received considerable attention in the context of supervised learning with the
proposed techniques operating either at training- or at testing-time.
Techniques in the former category typically work by either reweighting the
losses computed out of the original training samples [4, 42, 41] or by over-
or under-sampling during training [6, 2]. Techniques in the latter category
work by modifying the classifier’s output scores at testing-time and using the
modified scores for classification [18, 31], with LA being one of the most
well-known techniques [28]. LA modifies the classifier’s scores at testing-
time by subtracting the (unknown) gold ratios. In particular, the prediction
of classifier $f$ given input $x$ is given by
${arg\max_{y\in[c]}f^{y}(x)-\ln(r_{y})}$ under LA. Our empirical analysis
shows that CAROT is more effective than testing-time mitigation techniques
from the above line of research.

Closest to our work is the study in [31]. Differently from CAROT, the authors
in [31] address with single-instance PLL and also assume that the marginal
$\mathbf{r}$ is known, using an optimal transport formulation [33] to adjust
the classifier’s scores. In contrast, CAROT relies on the assumption that
$\widehat{\mathbf{r}}$ may be noisy, resorting to a robust optimal transport
formulation [19] to improve the classification accuracy in those cases.

Partial Label Learning. As discussed in [49], MI-PLL is an extension to the
standard, isingle-instance PLL. The observation that certain classes are
harder to learn than others dates back to work of [7] in the context of PLL.
Our work is the first to provide such results for MI-PLL, unveiling also the
relationship between $\sigma$ and class-specific risks.

Long-tail PLL. A few recently proposed papers lie in the intersection of long-
tail learning and (single-instance) PLL, namely [22], RECORDS [13] and SoLar
[47], with the first one focusing on non-deep learning settings. RECORDS
modifies the classifier’s scores following the same basic idea with LA and
uses the modified scores for training. However, it employs a momentum-updated
prototype feature to estimate $\widehat{\mathbf{r}}$. RECORDS’s design allows
it to be used with any loss function and trivially be extended to support MI-
PLL. Our empirical analysis shows that RECORDS is less effective than CAROT,
leading to lower classification accuracy when the same loss is adopted to
train the classifier.

SoLar shares some similarities with our LP formulation (7), as it also assigns
pseudo-labels to the input instances at training-time based on the model’s
prediction $\mathbf{P}$, in order to (strictly) match the marginal
distribution $\widehat{\mathbf{r}}$. In particular, given single-instance PLL
samples of the form $\\{(x_{1},S_{1}),\dots,(x_{n},S_{n})\\}$, where each
$S_{\ell}\subseteq\mathcal{Y}$ is the partial label of the $\ell$ PLL
sample222In standard PLL, each partial label is a subset of classes from
$\mathcal{Y}$., SoLar finds pseudo-labels $\mathbf{Q}$ by solving the
following linear program:

$\displaystyle\min_{\mathbf{Q}\in\Delta}$
$\displaystyle\langle\mathbf{Q},-\log(\mathbf{P})\rangle$ (34)
$\displaystyle\text{s.t.}\quad\Delta$ $\displaystyle=\left\\{[q_{\ell
j}]_{n\times
L}\mid\mathbf{Q}^{\mathsf{T}}\mathbf{1}_{n}=\widehat{\mathbf{r}},\;\mathbf{Q}\mathbf{1}_{c}=\mathbf{c},\;q_{\ell
j}=0\;\text{if}\;y_{j}\notin S_{\ell}\right\\}\subseteq[0,1]^{n\times c}$

The program (34) shows that the information of each partial label $S_{\ell}$
is strictly encoded into $\Delta$. To directly extend (34) to MI-PLL, we have
two options:

  * •

Use an $n\times c^{M}$ tensor $\mathbf{P}$ to store the model’s scores, where
cell $P(\ell,j_{1},\dots,j_{c})$ stores the classifier’s scores for the label
vector $(j_{1},\dots,j_{c})$ associated with the $\ell$-th training MI-PLL
sample, for ${1\leq\ell\leq n}$. However, that formulation would require an
excessively large tensor, especially when $M$ gets larger.

  * •

Use separate tensors $\mathbf{P}_{1},\dots,\mathbf{P}_{M}$ to represent the
model’s scores of the $M$ instances, and set for each ${1\leq\ell\leq n}$, the
product ${P_{1}(\ell,j_{1})\times\dots\times P_{M}(\ell,j_{c})}$ to be $0$ if
$(j_{1},\dots,j_{c})$ does not belong to $\sigma^{-1}(s_{\ell})$, where
$s_{\ell}$ is the partial label of the $\ell$-th training MI-PLL sample.
However, that formulation would lead to a non-linear program.

Neither choice is scalable for MI-PLL when we have a large value of $M$333Yet
another non-linear formulation is presented in Section D based on RSOT (see
Section A).. To circumvent this issue, our work translates the information of
the partial labels into linear constraints, leading to an LP formulation.
Another difference between SoLar and work is that the ratio estimates
$\widehat{\mathbf{r}}$ can be obtained via Algorithm 1, while SoLar employs a
window averaging technique to estimate ${\mathbf{r}}$ based on the model’s own
scores [47].

Finally, although our CAROT algorithm also use a linear programming
formulation with a Sinkhorn-style procedure, it differs from SoLar in that it
aims to adjust the model’s scores at testing time rather than assigning
pseudo-labels at training time.

MI-PLL. There has been recently theoretical research on MI-PLL and related
problems [26, 58, 49]. Differently from us, the work in [26] deals with the
problem of characterizing reasoning shortcuts in MI-PLL. Intuitively, a
reasoning shortcut is a classifier that has small partial risk, but high
classification risk. For example, a reasoning shortcut is a classifier that
may have a good accuracy on the overall task of returning the maximum of two
MNIST digits, but low accuracy of classifying MNIST digits. The work has shown
that current neurosymbolic learning techniques are vulnerable to learning
reasoning shortcuts, proposing techniques to mitigate this phenomenon.

The authors in [49] were the first to propose necessary and sufficient
conditions that ensure learnability of MI-PLL and to provide error bounds for
a state-of-the-art neurosymbolic loss under approximations [15]. Our
theoretical analysis extends the one in [49] by providing (i) class-specific
risk bounds (in contrast to [49], which only bounds $R(f)$) and (ii) stricter
bounds for $R(f)$. In particular, as we show in Proposition 3.5, we can
recover the error bound from Lemma 1 from [49] by relaxing (4).

Constrained learning. MI-PLL is closely related to constrained learning, in
the sense that the prediction for the label (vector) is subject to the
constraint $\sigma(\mathbf{y})=s$ at the training stage. Training classifiers
under constraints has been well studied in NLP [40, 34, 32, 29, 45, 50, 11].
The work in [35] proposes a formulation for training under linear constraints;
[36] proposes a Unified Expectation Maximization (UEM) framework that unifies
several constrained learning techniques including CoDL [5] and Posterior
Regularization [10]. In particular, [27] employs a conceptually similar idea
by encoding prior information of the label frequency with a CoDL formulation
to enhance partial label learning for the Named Entity Recognition (NER) task.
The UEM framework was also adopted by [20] for neurosymbolic learning. Our LP
formulation is orthogonal to the UEM. These two could be integrated though.

It is also worth noting that a theoretical framework for constrained learning
[48] provides generalization theory suggesting that encoding the constraint
during both the training and testing stages results in a better model compared
to encoding it only during the testing stage. This theory could potentially be
extended to explain the advantage of LP-based methods and to characterize the
necessary conditions for CAROT to improve model performance.

Neurosymbolic learning. MI-PLL quite often arises in neurosymbolic learning
setting [24, 51, 9, 55, 43, 25, 15, 20]. However, none of the above lines of
research deals with learning imbalances.

##  Appendix F Experimental details

Computational infrastructure. The experiments ran on an 64-bit Ubuntu 22.04.3
LTS machine with Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz, 3.16TB hard disk
and an NVIDIA GeForce RTX 2080 Ti GPU with 11264 MiB RAM. We used CUDA version
12.2.

Software packages. Our source code was implemented in Python 3.9. We used the
following python libraries: scallopy444https://github.com/scallop-lang/scallop
(MIT License)., highspy555https://pypi.org/project/highspy/ (MIT License).,
or-tools666https://developers.google.com/optimization/install/python
(Apache-2.0 license)., PySDD777https://pypi.org/project/PySDD/ (Apache-2.0
license)., PyTorch and PyTorch Vision. Finally, we used part of the
code888https://github.com/MediaBrain-SJTU/RECORDS-LTPLL (MIT License).
available from [13] to implement RECORDS.

Classifiers. For the MAX-$M$ scenarios, we used the MNIST CNN also used in
[15, 24]. For the Smallest Parentscenarios, we used the ResNet model also used
in [47, 13].

Further details. For the Smallest Parent scenarios, we computed SL and (7)
using all the pre-image of each partial label. For the MAX-$M$ scenarios, as
the space of pre-images is very large, we only consider the top-1 proof [49]
both when running Scallop and in (7).

For the Smallest Parent benchmark, we created the hierarchical relations shown
in Listing 5 based on the classes of CIFAR-10.

⬇

land_transportation :- automobile, truck

other_transportation :- airplane, ship

transportation :- land_transportation, other_transportation

home_land_animal :- cat, dog

wild_land_animal :- deer, horse

land_animal :- home_land_animal, wild_land_animal

other_animal :- bird, frog

animal :- land_animal, other_animal

entity :- transportation, animal

Figure 5: Hierarchies for the Smallest Parent benchmark.

Table 3 presents the full results for the MAX-$M$ scenarios.

Table 3: Experimental results for MAX-$M$ using $m_{\mathsf{P}}=3000$.

Algorithms |  Original $\rho=0$ |  LT $\rho=5$ |  LT $\rho=15$ |  LT $\rho=50$
---|---|---|---|---
$M=3$ | $M=4$ | $M=5$ | $M=3$ | $M=4$ | $M=5$ | $M=3$ | $M=4$ | $M=5$ | $M=3$ | $M=4$ | $M=5$
SL | 84.15 $\pm$ 11.92 | 73.82 $\pm$ 2.36 | 59.88 $\pm$ 5.58 | 55.48 $\pm$ 23.23 | 66.24 $\pm$ 1.22 | 55.13 $\pm$ 4.20 | 71.25 $\pm$ 4.48 | 66.98 $\pm$ 3.2 | 55.06 $\pm$ 5.21 | 66.74 $\pm$ 5.42 | 67.71 $\pm$ 11.58 | 55.74 $\pm$ 2.58
\+ LA | 84.17 $\pm$ 11.95 | 73.82 $\pm$ 2.36 | 59.88 $\pm$ 5.58 | 55.48 $\pm$ 23.23 | 65.63 $\pm$ 1.75 | 55.13 $\pm$ 4.20 | 70.80 $\pm$ 4.52 | 66.98 $\pm$ 3.20 | 54.53 $\pm$ 5.74 | 66.57 $\pm$ 5.09 | 61.10 $\pm$ 3.95 | 52.47 $\pm$ 8.06
\+ CAROT | 84.57 $\pm$ 11.50 | 73.08 $\pm$ 3.10 | 60.26 $\pm$ 5.20 | 56.52 $\pm$ 21.70 | 66.70 $\pm$ 0.76 | 55.91 $\pm$ 3.42 | 74.95 $\pm$ 3.45 | 67.44 $\pm$ 2.74 | 55.80 $\pm$ 4.47 | 68.16 $\pm$ 4.00 | 68.25 $\pm$ 6.14 | 57.29 $\pm$ 14.17
RECORDS | 85.56 $\pm$ 7.25 | 75.11 $\pm$ 0.77 | 59.43 $\pm$ 6.61 | 77.98 $\pm$ 3.13 | 65.85 $\pm$ 0.62 | 55.07 $\pm$ 4.24 | 55.47 $\pm$ 20.45 | 53.34 $\pm$ 16.66 | 52.40 $\pm$ 7.95 | 70.20 $\pm$ 7.65 | 66.05 $\pm$ 13.90 | 59.93 $\pm$ 4.86
\+ LA | 87.63 $\pm$ 5.11 | 75.11 $\pm$ 0.77 | 59.28 $\pm$ 6.76 | 77.98 $\pm$ 3.13 | 65.43 $\pm$ 0.87 | 54.40 $\pm$ 4.44 | 54.90 $\pm$ 20.16 | 54.46 $\pm$ 15.54 | 51.25 $\pm$ 9.09 | 70.09 $\pm$ 7.26 | 65.78 $\pm$ 14.18 | 59.93 $\pm$ 4.86
\+ CAROT | 90.97 $\pm$ 2.03 | 75.94 $\pm$ 0.91 | 60.45 $\pm$ 7.78 | 78.31 $\pm$ 4.00 | 67.57 $\pm$ 1.74 | 55.46 $\pm$ 3.94 | 54.32 $\pm$ 21.85 | 62.74 $\pm$ 8.14 | 55.85 $\pm$ 4.61 | 71.46 $\pm$ 6.4 | 71.25 $\pm$ 8.70 | 63.64 $\pm$ 5.92
LP(EMP) | 94.97 $\pm$ 1.32 | 77.86 $\pm$ 4.22 | 55.27 $\pm$ 11.27 | 80.15 $\pm$ 1.69 | 70.73 $\pm$ 1.85 | 56.28 $\pm$ 2.03 | 75.83 $\pm$ 5.26 | 69.67 $\pm$ 5.47 | 59.25 $\pm$ 7.27 | 77.16 $\pm$ 3.46 | 70.06 $\pm$ 10.73 | 56.79 $\pm$ 1.58
\+ LA | 94.69 $\pm$ 1.60 | 77.91 $\pm$ 4.16 | 55.34 $\pm$ 11.19 | 80.08 $\pm$ 1.55 | 70.54 $\pm$ 1.82 | 55.31 $\pm$ 3.27 | 75.77 $\pm$ 5.32 | 68.92 $\pm$ 3.96 | 58.49 $\pm$ 5.74 | 77.1 $\pm$ 3.52 | 69.76 $\pm$ 10.31 | 56.81 $\pm$ 1.56
\+ CAROT | 95.07 $\pm$ 1.20 | 75.53 $\pm$ 7.42 | 53.07 $\pm$ 12.99 | 80.29 $\pm$ 2.33 | 70.88 $\pm$ 2.22 | 57.85 $\pm$ 4.05 | 76.38 $\pm$ 4.72 | 69.74 $\pm$ 5.51 | 59.56 $\pm$ 8.14 | 77.58 $\pm$ 3.04 | 70.11 $\pm$ 10.34 | 57.09 $\pm$ 1.90
LP(ALG1) | 96.09 $\pm$ 0.41 | 78.34 $\pm$ 4.80 | 59.91 $\pm$ 6.63 | 78.56 $\pm$ 1.52 | 69.71 $\pm$ 0.03 | 57.61 $\pm$ 3.09 | 74.51 $\pm$ 9.13 | 69.14 $\pm$ 1.82 | 56.81 $\pm$ 3.74 | 72.23 $\pm$ 11.49 | 69.28 $\pm$ 11.78 | 63.67 $\pm$ 7.04
\+ LA | 95.81 $\pm$ 0.74 | 78.97 $\pm$ 4.09 | 59.98 $\pm$ 6.56 | 78.48 $\pm$ 1.53 | 69.71 $\pm$ 0.03 | 57.47 $\pm$ 3.09 | 74.26 $\pm$ 9.06 | 68.73 $\pm$ 2.23 | 56.37 $\pm$ 3.13 | 72.23 $\pm$ 11.49 | 69.21 $\pm$ 11.86 | 63.67 $\pm$ 7.04
\+ CAROT | 96.13 $\pm$ 0.38 | 80.78 $\pm$ 2.36 | 59.71 $\pm$ 6.35 | 78.93 $\pm$ 1.85 | 70.32 $\pm$ 0.86 | 57.62 $\pm$ 3.08 | 77.05 $\pm$ 7.00 | 69.19 $\pm$ 1.81 | 59.76 $\pm$ 7.24 | 74.82 $\pm$ 10.18 | 74.30 $\pm$ 7.54 | 64.39 $\pm$ 6.43