Unified Risk Analysis for Weakly Supervised Learning
Authors: Chao-Kai Chiang
Masashi Sugiyama
Venue: Accepted by TMLR ()

Abstract: Among the flourishing research of weakly supervised learning (WSL), we recognize the lack of a unified interpretation of the mechanism behind the weakly supervised scenarios, let alone a systematic treatment of the risk rewrite problem, a crucial step in the empirical risk minimization approach. In this paper, we introduce a framework providing a comprehensive understanding and a unified methodology for WSL. The formulation component of the framework, leveraging a contamination perspective, provides a unified interpretation of how weak supervision is formed and subsumes fifteen existing WSL settings. The induced reduction graphs offer comprehensive connections over WSLs. The analysis component of the framework, viewed as a decontamination process, provides a systematic method of conducting risk rewrite. In addition to the conventional inverse matrix approach, we devise a novel strategy called marginal chain aiming to decontaminate distributions. We justify the feasibility of the proposed framework by recovering existing rewrites reported in the literature.

Published in Transactions on Machine Learning Research (01/2025)
Unified Risk Analysis for Weakly Supervised Learning
Chao-Kai Chiang
chaokai@k. ac.jp sugi@k.uttokyo.ac. ac..p
Masashi Sugiyama
Department of Complexity Science and Engineering
Graduate School of Frontier Sciences
The University of Tokyo
5-1-5 Kashivanoha, Kashiwo-shi, Chiba 277-8561, Japan
Reviewed on OpenReview: https: // openreview. net/ formm id= RGadAwwuu
Abstract
Among the flourishing research of weakly supervised learning (WSL), we recognize the lack of a unified interpretation the mechanism behind the weakly supervised scenarios, let alone a systematic treatment of the risk rewrite problem, a crucial step in the empirical risk minimization approach. In this paper, we introduce a framework providing a compre- hensive understanding and a unified methodology for WSL. The formulation component of the framework, leveraging contamination perspective, provides a unified interpretation of how weak supervision is formed and subsumes fifteen cxisting WSL settings. The induced reduction graphs offer comprehensive connections over WSLs. The analysis component of the framework, viewed as a decontamination process, provides a systematic method of con- ducting risk rewrite. In addition to the conventional inverse matrix approach, we devise a novel strategy called marginal chain aiming decontaminate distributions. We justify the feasibility of the proposed framework by recovering existing rewrites reported in the literature.
1 Introduction
Accurate labels allow one to generalize to unseen data via empirical risk minimization (ERM) and analyze the generalization error in terms of the classification risk. In practice, there are various situations in which acquiring accurate labels hard or even impossible. One obstacle preventing us from acquiring accurate labels is labeling restrictions, such as imperfect supervision due to imperceptibility, time ronsts, amno- tation costs, and even data sensitivity. Another obstacle is the disruption by unavoidable noise from the environment.
To address the first obstacle of riction,, various formulations have been studied under the notion of weakly Sugiyama et al.
supervised learning (WSL) (Zhou 2018
2022). Based on various types of available label
information, it evolves to thriving topics, including the conventional settings (Lu et al.] 2019
2020
2021
Elkan & Noto 2008: du Plessis et al.
2014
2015
Niu et al.
2016 Kiryo et al. 2017 Sansone et al.
2019
that investigating the potential of unlabeled data, complementary-labn learning (Ishida et al. 2017 7
2019
Yu et al. 2018 Feng et al. 2020aa
Katsura & Uchida 2020; Chou et al. 2020), partial-label learning Cour
et al. 2011 Wang et al.] 2019 Lv al. 2020 Feng al. 2020b Wu al. 2022). learning with confidence
information Ishida et al.
2018 Cao et al.] 2021a b Berthon et al. 202 Ishida et al. 2023) and learning
with comparative information (Bao et al. 2018 Shimada et al. 2021 Feng et al., 2021 Cao et al, 2021b).
Developing to resolve the second obstacle of noise, learning with noisy labels (LNL) can be categorized inlo two major formulations; one is called mutually contaminated distributions (MCD) (Scott et al. 2013 Menon ct al. 2015 Katz-Samuels et al. 2019h which class-conditional distributions contaminate each other, and the other is named class-con cons-conniiional random label noise (CCN) (Natarajan al.] 2013 2017) where label
is flipped by random noise.

---

Published in Transactions on Machine Learning Research (01/2025)
Despite fruitful results and tremendous impact, recognize lack of global understanding and systematic treatment of WSL. From the perspective of formulation, there are only scattered links among WSLs. Lu et al. (2019) and Feng et al. (2021) showed that parameter substitution could reduce unlabeled-umlabedd mnlaeled and positive-umlabeled settings. Figure 1 in Wu et al. (2023) showed relationships among four WSL. of partial- and complementary-labebe A similar observation can be found in the intersection of WSLs and LNLs. Several WSLs were shown to be special cases of the MCD model, and some other WSLs are special cases of the CCN model. For details, please refer to the discussions in Sections 8.2.3 and 9.2.4 of (Sugiyama et al. (2022.. These connections encourage to consider the possibility that there exists a unique interpretation that explains the mechanism behind WSL. Luckily, from the methodological viewpoint, most of the existing WSL research adopted certain forms of the ERM approach. A crucial shared step is to perform the risk rewrite, a way of rephrasing the uncomputable risk to a computable one in lerms of the data-generating distributions. A successful rewrite is the starting point of many downstream tasks, including but not limited to the following: Devising a practical or robust objective for training, comparing the strengths and properties of loss functions, proving the consistency, and analyzing generalization error bounds. However, many rewrite forms (summarized in Tables 5 look independent as if they are tailored to fit each problem's 's unique form of supervision and are not adaptable to each other. These seemingly non- adaptable estimators post a practical challenge: When facing new form of weak (or noisy) supervision, we do not have a guideline or general strategy to leverage developed methods to address the new situation.
to
These observations raise the following questions we aim to answer in this paper: What is the essence of WSL? From a formulation perspective, can a unique interpretation be found to explain the mechanism behind WSL? Does a methodology exist to address many WSLs possible?
This paper proposes framework with the following contributions to answer the research questions.
To the best of our knowledge, the framework is the first systematic attempt to address how and why WSLs are related. The framework consists of formulation component and an analysis component, and subsumes fifteen weakly supervised scenarios. Table TO summarizes the results obtained from our framework. This paper brings forth the next two new insights.
2. The formulation component, modeling from a contamination perspective, provides a coherent inter- pretation of the weakly supervised lata-generating processcs. It produces a comprehensive relation- ship graph, shown in Figure [ consisting of Tables 7 and Figure] summarizes the WSLs and reveals connections between scenarios that were previously unknown to the community. Figure [ is our answer to the second rescarch question. Figure 1 also unveils a distinctive confidenco-based type of WSLs that do not belong to the prominent MCD or CCN categories.
3. The analysis component, leveraging the deconlamination concept, establishes generic methodology for conducting risk rewrites for all WSLs discussed in this paper. Thus, rewrite derivations that previously seemed irrelevant now be systematically analyzed, and the final research question is answered. In addition, the analysis component also applies to new scenarios.
4. Regarding the technical contributions, the proposed framework distinguishes two approaches, the inversion method and the marginal chain method presented in Theorems [ and 2 implement the decontamination idea. The marginal chain method is newly developed invertibility- loss correction approach. We also illustrate the subtle adjustments to develop simplified and intuitive proofs for the existing risk rewrites. These allernative proofs have their own logic stemming from the proposed framework.
The idea of decontamination has been widely implemented and investigated. There are two major approaches, loss correction, and label correction, in LNL. Closest to the current paper, Cid-Suciro (2012). van Rooyen & Williamson (017)): Katz-Sanuels et al. (2019), Patrini et al.] (2017), and van Rooyen & Williamson (2015) exploited the inverse matrix, sometimes known as the backward method (Patrini et al. 2017). to construct a corrected training loss to obtain an unbiasod estimator. There were deep learning mothods leveraging the contamination assumption, sometimes called the forward method (Patrini et al., 2017), to train a classifier
Patrini et al. 2017 Yu et al. 2018 Sukhbaatar & Fergus 2015: Goldberger & Ben-Reuven 2017 Berthon
2

---

Published in Transactions on Machine Learning Research (01/2025)
et al.
2021
Besides modifying the loss function, one has two other strategies to manipulate the corrupted The (iterative) pseudo-label method modified the labels for training (Ma et al. 2018 Tanaka et al.
labels.
2018
Reed et al.] 2015). Filtering clean data points for training is the other option (Northcutt et al. 2017
2021
Jiang et al. 2018: Han et al. 2018 Yu et al. 2019). Apart from classification, a different rescarch
branch studies conditions and methods lor recovering the base distributions (Katz-Samuels et al. 2019
Blanchard Scott 2014, Blanchard et al. 2016).
The current work is close to the loss correction approach in LNL. Most previous loss correction methods exploited invertibility to construct the corrected losses. In contrast, the marginal chain approach propose in this paper adopts the conditional probability formula to build the corrected losses. Many of the existing work targeted either the MCD or the CCN models. Scott & Zhang (2020), Berthon et al. (2021), Patrini
Ren-RRevenn 2017), Sukhbaatar & Fergus (2015), Yu et al. (2018). Natarajan ett al. 22013 Natarajan et al. (2017). Northoutt al. (2017). and Northoutt et al. (2021) were based on the CCN model, and KKatz-Samuchs et al. (2019), Blanchard & Scott (2014), and Blanchard et al. (2016) were based on the MCD model. [Meon et al. (2015), van Rooyen & Williamson (2017). and Katz-Samuels et al. (2019) studied multiple noise models at the same time. However, the current paper investigates the connections between MCD, CCN, and confidence-basee based scttings simultancously through the lens of matrix decontamination as broadly as possible to identify a generic methodology for WSLs. Different from the current paper aiming for risk minimization, research also studied various performance measures, such as the balanced error rate (Scott& & Zhang, 2020 2019; Menon et al.] 2013 du Plessis et al.] 2013), the area under
ee al. 2017), Goldberger
the receiver operating characteristic curve (Charoenphakdeee et al. 2019 Sakai et al. 2018 Menon et al.
2015), and cost-sensitive measures (Charoenphakdee al.] 2021
Natarajan et al. 2017). We choose the
classification risk as the only mcasure due the focus of this paper.
The remaining sections are organized as follows. Section 2 reviews ERM in supervised learning, the risk rewrite problem, and the existing results. Section 3 presents the proposed framework. We show that the proposed framework provides a unified way to formulate diverse weakly supervised sconarios in Scction g Section
5 demonsttates how to instantiate the framework to conduct risk rewrite. We demonstrate the applicability of the proposed framework to new scenarios in Section 6 Finally, we conclude the paper and
discuss outlooks in Section 7 The current organization of Sections 4 and 5 aims at connecting multiple
WSLs under one framework. We note that this paper can serve multiple purposes for the study of WSLs. A summary of possible use cases of the paper is provided in Appendix
2 Preliminaries
Let (y, 2) be a data example where the instance x E X and the label y/ E V. For binary classification, the label space Y is n). and for multiclass classification with K classes, y'= =1, ..... K) := [X]. The joint distribution is TP (Y, X), the class prior is P PYY), the class-conditional distribution is P (X[Y), and the class probability function is P (Y] Given a space of hypotheses G, denote the loss of hypothesis E G predicting of (v, (xxx) To accommodate concise expressions and readability for all WSLs considered in this paper simultaneously, we use alias notations when the context is unambiguous. Table [ provides a set of common notations used in this paper.
We use (y, x) instead of the convention (x. to represent a data example because, the current paper, we focus on discussing different types of supervision. Placing the label before the instance emphasizes the type of supervision under investigation in thcorems and derivations.
2.1 Supervised Learning and the ERM Method
In supervised learning with K classes, the observed data is of the form
Bg iid. PxiY= Vy [K].
3

---

Published in Transactions on Machine Learning Research (01/2025)
Table
Alias of Common Notations.
Name of the notation
Expression
Aliases
Binary classes
[p,n}
Multiple classes
{I....,K] K]
[K]
Compound set of [K]
2 {0, [K]}
S
Joint distribution
P(Y y, X
Py=y,a Py=y,x: or Py,x
Hypothesis and its space
gEg
Loss of
(x=v(((x)
by. (x(), or (r(g())
Classification risk
Ry.x (lr(g(X))
R(g)
The j-th entry of vector V
(V);
V2
Class prior
P(Y = =v)
Ty
Marginal
P(X)
Px
Class-conditional
(X =)
Pxly, Px|Y=y: or PzIY=y
Confidence
P (Y = y X = x)
ry(X), (z), or r(X) if y =
Notation x. denotes the shorthand of (y, The goal of learning is to find classifier g E 9 that minimizes the classification risk
R(g) = Bx (er
Σ
(v= dr.
(1)
xEX
To find such a classifier, ERM first constructs an empirical risk estimator with the data in hand:
Fly Ty mgly=v(((>))
k(g)
(2)
The estimator approximates R(g) consistently since can be shown that (2) approaches 1 as + 0c
Tewari & Bartlett. 2014 Kiryo et al. (017)) and (Sugiyama al. 2022 Chapter 3). Then, ERM takes R(g) the training objective and optimizes it find the optimal classifier
g" arg min R(g)
SEg
in the hypothosis space & as the output of ERM.
2.2 The Risk Rewrite Problem and Existing Results
Scctions 2.2.1 to 2.2.17 review the lcarning scenarios including WSLs, MCD, and CCN that will be discussed in this paper. knowledgeable reader may refer directly summary Tables through and proceed Section
In every WSL scenario, the goal of learning the same as supervised learning. However, the observed data is longer as perfectly labeled in supervised learning. That said, there differences in the formulations of the observed data and the ways of ostimating the classification risk. We begin with reviewing WSLs derived from binary classes. For K- = 2, we denote y : np.
2.2.1 Sesitie-Unllbeleen (PU) learning
The observed data in PU learning du Plessis et al. 2015 is of the form
{a Pp Lid. J=l ~ Pp = Px
(4)
Pu iid. Pu = un Px|Y= + Px { {x)) s==1

---

Published in Transactions on Machine Learning Research (01/2025)
where z) is viewed as the shorthand of xu, symbolizing the unlabeled data The unlabeled data set { consists of a mixture of samples from Px and Px|Y=n with proportion Tp- Since the information
of negatively sampled data is unavailable, (2) is uncomputable, causing directly optimizing (3) infeasibility.
Therefore, to make ERM applicable, the risk rewrite problem (Sugiyama ct al. 2022 asks:
Can one rephrase the classification risk R(g) 1 terms of the given data formulation?
du Plessis et al.
2015 rewrote the classification risk in terms of the data-generaling distributions Pp and
Pu as
R(g) Ep pp xph.l + By [kn.
(5)
2.2.2
Positive-confidencee (Pconf) Learning Learning
The observed data Pconf learning [shidd et al. 2018 is of the form
(m;)r(r;))
where
i... T2 ~ Pp = P
(6)
r(z,) = Py=p|x==-
The function r(z) represents how confident an example a would be positively labeled. rewrote the classification risk as
Ishida et al.
20188
R(g) Tp lp + 1-r(X) 4n r(X)
(7)
2.2.3 Unlabbled (UU) learning
The observed data in UU learning (Lu et al. 2019 is of the form
{x Ji=i
i.d. Pu, = (1 m1 Px|Y=p + Px|Y=n
iid. Pu, := 72 Px|r=p (1 (1-72) 72) P
where x! (resp. =//²) being the shorthand of (u1, (resp. (u2, represents I; (resp. xy) belonging to the unlabeled data whose mixture parameter is 7 (resp. 72). Notice diffcrence that the mixture proportion of the unlabeled data in PU learning is Tp- Lu el al. (2019) rewrote the classification risk in terms of the data-gen tattaggneraaing distributions Pu, and Pu, as follows: Assume + # 1. Then,
(1 - 72) 4p +
-2
-21 Tp
(1 - 71 7)) ln
R(g) = Eu,
Ln
+ Eu,
Lp +
(9)
71 72
1 1- 21 72
1- 71 72
1 1 7/1 72
2.2.4 Similar- Unlabeled (SU) learning
The observed data in SU learning [Bao al. 2018) is of the form
(1t, the iid. :s:= P
PxiY==
o + m²
(10)
th Hid. Pu: up Pxir=p nu Pxiy= {
The word "similar" means the examples every (a", x²1) pair have the same label; either both are positive, or both are negative. Under the assumption Tp * Tu. Bao et al. (2018) rewrote the classification risk
R(g) = mm T Es ((X) [(X)
+ Eu [C_ (X)],
(11)
2
"Seemingly being redundant, but it. helpful use ay) distinguish from the positively labeled instance (p.a.)

---

Published in Transactions on Machine Learning Research (01/2025)
where
1 (X),,
((X) =
(x(X)
"p nn
"p An
(_(X)
(p(X)
+
up
En (X).
up nn
"p nn
2.2.5 Dusimilar-Unlabeei (DU) learning
The observed data in DU learning Shimada et al 2021 of the form
{ [ d' ==1
iid.
PD == Pxpr= Twm=Pxxye PxTY=n + PXIX=IXXIX=
2
(12)
{ { j=1 Po: Tp Px|r=p + Tn Px|Y=n
pu itd.
The word "dissimilar" means the examples every (x x²") pair have distinct labels. Under the assumption (2021) rewrote the classification risk as
"p * Ruz Shimada
((X) + [(X') + EU (X)),
R(g)= Tn
(13)
2
where
((X)
(x(X)
(x(x),
Tp
nn
Tp nu
(X)
=
Up
p (X)
n
L (X).
Tp Tn
Tp
Tu
Note that ((X) has been defined in the SU setting. We repeat it here for clarity.
2.2.6
(SD) learning
The observed data in SD learning (Shimada et al. 2021 is of the form
the l.d. }" i=1 Ps: P x p Px =n
Px
o + m
(14)
{(0g) 22) )
}
nh i.d. PD Px P Y + PxIy=XX'II
2
Under the assumption Tp * Mns Shimada el al. (2021
rewrote the classification risk as
R(g) = (T + = Es (X) + C+ (X')
+
2T ED
(15)
2
2
where
(x(X)
Tp (x(()
Th
(x)))
Tp
nn
Tp
kn
(x
Wn
(X)
e, (X).
Up nn
Tp
nn
Note that L4 (X) and C_ have been defined in the DU and SU settings. We repeat them here for clarity.
2.2.7 Pairwise Comparison (Pcomp) Learning
The observed data in Pcomp learning Feng et al. 2021 is of the form
{ {2P0 (x]",,"" _epe") }"me
Ape i.d. Ppc = x + x Ap P P
PXIY=PPxIY= x
mB n
+ m
(16)

---

Published in Transactions on Machine Learning Research (01/2025)
The pairwise comparison encodes meaning that each are "can not be more negative" than x:c in the (oPe ,xPe') pair. That is, the labels in (xPe ,x are of the form (), (p. n), or (n, n). Feng et al. (0021 rewrote the classification risk as
R(g) = Esu 1pp - Tpln] + Bint m-mp + En)s
(17)
where the expectations are computed over the following distributions
S Ppc f
Psup =
Pint
PpC dr.
DEX
2.2.8 Similarity- Confidence Learning (Sconf) Learning
The observed data Sconf learning
Cao et al. 2021b of the form
{
100 200' ir (2 22d ) )'m
where
lid.
Is Px = ==mp Px|y=p + Fn Px Y=n
5 lid. Px = up Px Px + Tn Px Y
(18)
(1 ag.e) = PY=ur=Y'=pp" X=oos Xozeee
X=
Cao et al. 2021b rewrote the classification risk as
r(X,') nn Cx(XXX)++ + Tp x(X,X)
(o(X,,)).
R(g) = Ex.x'
(19)
Tp
Tn
where
C,(X,X)) (p(X)+++(Xx Ep(x')
Cx(X, (x( (x')
2.2.9 Lomplementary-Label (CL) Learning
One can also formulate weak supervision from multiclass classification. For K classes, denote y == [K].
The observed data in CL learning Tshida et al.
2019 is of the form
(5,,)))) Lid.
P3, K
Σ Pv.x
(20)
Y#8
As is named "complementary." 5 [K] represents that the true label y of x cannot be s. Ishida et al. 2019 rewrote the classification risk
K
R(g) Eg.x
Σ Ey (K 1)63
(21)
7

---

Published in Transactions on Machine Learning Research (01/2025)
2.2.10 Multi-Complementary-Laad (MCL) Learning
The observed data in MCL learning Feng et al. 2020a] is of the form
Ed=1 Pis
K-1
Eyes Prx, | d.
((, (i) Ltd.
Ps.x
(18
(22)
0,
otherwise.
Generalized from CL, C [K] in MCL is set of classos of size d [K - representing multiple exclusions.
In other words, CL is the special case of MCL with d = 1. Feng et al. (2000a) rewrote the classification risk as
K-1
| K
R(g) = Σ Pls
-d 3,
S|=d
Σ v
83
(23)
S
d=1
BES
2.2.11 Provably Consistent Partial-Label (PCPL) Learning
The observed data in PCPL learning (Feng et al.
2020b is of the form
i.d. Ps,x
Σ Pr,x.
(24)
2K-1
YES
A partial-label C [K] is a set classes containing the true label y of x. Feng et al. (020b rewrote the classification risk as
K Σ
Py=uix Ly
R(g) = Bs,
Enes Py=olx )
(25)
2
-y=1
2.2.12 Proper Partial-Label (PPL) Learning
The observed data PPI. learning
[Wu et al. 2023 of the form
(s;, lid. Ps.x C(S,X)
Σ PY.
(26)
YES
The weight - in PCPL is generalized to C(S,X), function of the partial-label and the instance, allowing one to characterize the "properness" of a partial-label. Wu et al. 2023) rewrote the classification risk as
Pr=eix -ly
R(g) Es.x
Σ yES
(27)
Eaes Py=a|x
2.2.13 Single-Class Confidence (SC- Learning
The observed data in SC-Conf learning
Cao et al. 2021a is of the form
(1;,
(x(
where
l.d. 04 Px with ys E [K], Tu (x+)) = Py= for each [K].
(28)
The constraint of SC-Conf is that the examples are sampled from specific class ys- The key to risk rewrite is the availability of confident information (x) about each class. Cao et al. 2021a) rewrote the classification
risk
(X) Ma (X)
R(g) T., EX
(29)
8

---

Published in Transactions on Machine Learning Research (01/2025)
2.2.14 Subset Confidence (Sub-Cor Conf) Learning
The observed data in Sub-Conf learning
(Cao et al. 2021a is of the form
(x ................................ (k(1)) (
where
24 1.d. PXIEE,, with V. c [K], Tk (*,) Py=,|X= for each [K].
(30)
Sub-Conf is a relaxed setting of SC-Conf where the samples come from a set of classes V Cao et al. 202 rewrote the classification risk as
(x( Tya (X) (x)
R(g) = Ty, EXIYEX,
Σ
ly
(31)
where Ty, Ejey, My, and ry, PrExIX = =sEx Pr=jix
2.2.15
Soft-Label Learning
Ishida al. 2023 formulated soft-label learning under the binary setting, which the observed data is of
the form
(2,,
where
1..dd. Px == Pr=p. + Py=u,;
(32)
r r(z;)= : Py=plX=m
It is straightforward to obtain corresponding formulation under the multiclass setting:
where
24 Px Py=kx
(33)
1=1
rk (x;) P for each [K].
The difference between SC-Conf and multiclass soft-label (resp. the difference between Peonf and binary soft-label) is the sample distribution æ. We rewrote the classification risk as
R(g) Ex
Σ (x)e
(34)
2.2.16 Summary of Existing WSL Formulations and Risk Rewrites
We summarize the weakly supervised scenarios discussed and their risk rewrite results. The formulations are divided into the binary classification settings in Table and the multiclass classification settings Table 3 We list the formulations in chronological order, according to their publication order. Tables and are the corresponding rewrites.

---

Published in Transactions on Machine Learning Research (01/2025)
Table Binary WSL formulations.
WSL
Formulation
Equation
ha ~ Pp == P
L.d.
PU
{aj)y= L.d.
Pu == Tp Px|M=p + nu Pxpv=n
where
Pconf
#i L.d. Pp r(z;) Pp
= :
PX|Y=p!
6
{a Me iid. Pu, (1 (1-7)) Px|Y=p 71 Px|r=
UU
8
{a ye Lid Pu, 7/2 Px|r=p + (1 - 72) Px|Y=n
no lid. ps:= T T.p Px1y xp Px'Iy y + T Y = Px v=n
a 25 } }:
SU
==1
TB + T
10
{2 th lid. Pu: Fp PxIY=p + Tn PXIY=n-
{< na Lid. Pp PXIX= + +
DU
12
{ My lid. Pu:= Px Tn Px|Y=n
(2) } n l.d. ps:= := TxPXX Xx' Y=p + Y P
Tp + m
SD
14
nd Lid. 1=1
PD PXIY=p P. X'1Y= =u + PXjY=n EXIY==PX'YS PXIYE
{a0) [x)0 x a.fo') }
Ape iid
PPC
Pcomp
PXxIv=pPxxI PT xp Px + 7 x Pximvnn
16
T + Tp + n
s0 so' 4 24 ,
80 24 ) the
)mmh where
a/c Lid.
Px = Tp Px| + Px|y=n:
Sconf
18
aid l.d.d Px = Tp Px + Ta Px
100 2xx = Py= - (x==ft X'=pp"
10

---

Published in Transactions on Machine Learning Research (01/2025)
Table 3: Multiclass WSL formulations.
WSL
Formulation
Equation
CL
(:), PS,
L.d.
Py.
(20
Y#S
Ed=1 Pisl=d
kK1
ExgsPrx,
if is = d,
(:),, iid.
(1g)]
MCL
Ps,x
22
0,
otherwise.
((),, Lid. Ps,x
Σ Prxx
PCPL
2k-1-1
24
YES
(1,,, Lid. Ps,x = C(S,))
Σ
Py,x.
PPL.
266
YES
where
SC-Conf
Ii lid. Px|Y= with ys E [K], Tx(x,)) = Py= for each l E [K].
28
(I;,)i .... rx (x:))=== where
Sub-Conf
W.d. PxIvEy, with 01 C [K], rk(2;) = Py=b|x=e; for each E [K].
30
(..). Tx(,))) where
Soft-label
Ia lid Px
33
rk(x,) Px= for each & [K].
11

---

Published in Transactions on Machine Learning Research (01/2025)
Table 4: Risk rewrites for binary WSLs.
WSL
Risk rewrite for R(g) x x (x(x)( (1)
Equation
PU
R(g) Ep pppp Tppn] Ev [6m]
Pp + 1 - r(x) fn
Pconf
R(g) Tp
r(x)
(1 - pT Ep
72
~
(1 - 71 TT ln
UU
R(g) Eu,
lu
+ Euu,
lp +
(9)
1- 7/1 - 7/2
1 72
92
1- 71 72
91 72
[(X) + -(X"))
R(g) = (T]) + x Bs
+ Eu (C_ (x])),, where
2
SU
L(X): = Tp nu
(x))
(x(X),
"p
nn
(_( Tp nn
nu
(x(X)
Zp (x(X)).
Tp Tu
((X) + ((X')
R(g) 2T ED
Eu (X)], where
DU
((X) is defined in the SU setting, and Tu
13
(+) == Tp
Tp (x(X)
La(X).
Tp TT
(X) + C+ (X')
L_ (X) + (X")
R(g) = (Tp + n Es
+ 2Tp ED
where
SD
2
2
15
(X) and f_(X') are defined in the SU and DU settings.
R(g) ESup 1pp - Tplal Eint 1- fnl, where
Psup == f XEE
dro
Pcomp
17
Pinf
PPC dr.
JEEX
r(X, X')
Tn (x) + lp(X")
"p -r(X, X') (x))
+ (x')
Sconf
R(g) Ex,x'
190
Tp un
Tp
nn
2
12

---

Published in Transactions on Machine Learning Research (01/2025)
Table 5: Risk rewrites for multiclass WSLs.
WSL
Risk rewrite for R(g) By,x [ey (x(x)) 11
Equation
CL
R(g) Es,x Ly=1
Σ by (K 1)6s
21
K-1 R(g) Σ
S
MCL
Pist E5 11,
P
Σ by
23
[
d=1
LVS
RES
Py= Ey
PCPL
R(g)) = = Es.
25
2
Enes Py=alx
y=
Py-uix ly
PPL
R(g) = Es,x
270
Enes Pr=alx
WES
K (X)
SC-Conf
R(g) = Ty ExIy=
Σ
Ey
29
(X)
y=
K
(x)
Sub-Conf
R(g) ny. EXIVER
Σ
cv
31
(X)
K
Soft-label
R(g) = Ex
Σ (X)e
34
L==1
From the above tables, finding a way to reexpress the classification risk R(g) ① in terms of the data- generating distributions becomes the crux when applying ERM for most WSL studies. The rewrites also replace loss functions y defining ( with various modified losses (shown inside the expectations). These modified loss functions are sometimes called corrected losses, which is why the approach is also called loss correction. Proposing generic methodology that finds properly corrected losses to achieve risk rewrite different scenarios is main topic we would like to elaborate on in this paper.
2.2.17 Learning with Noisy Labels (LNL) Formulations
Next, we review two related formulations in LNL, the MCD and CCN settings, in Table The observed instances in MCD and CCN are still labeled by {p, n} but are polluted by certain noise models. We use Y to represent a polluted label, compared to an unpolluted Y. In MCD, a small portion of the negatively labeled data 7p P contaminates the positively labeled data Px Likewise, a small portion of the positive data PX contaminates the negatively labeled data Pxjy=n (Scott al. 2013 In the CCN setting, a label Y is flipped to become Y with probability PYIr. NNtarajaa et al. 2013 Although they are formulated for the study of noisy labels, their formulations share sumlar structures with many WSLs above. In Section we will use the similarities to categorize WSLs and provide a bird's eye view reveal connections among WSLs.
13

---

Published in Transactions on Machine Learning Research (01/2025)
Table MCD and CCN formulations.
Scenario
Formulation
{<P) Ltd. Px|p=p:= := (1-1)) Yx + T/p Px|Y=n-
MCD
{ 1= Ltd. Px|Y=== = Y/u PXIV=p + (1 Va) Px
(7,,, L.d. Py=j.xx= E P Vū E {p.
CCN
kE(p.n)
3 A Framework for Risk Rewrite
We illustrate the proposed framework in this section. Its job is to provide unified treatment and understand- ing of WSL. It consists of a formulation component and an analysis component. The analysis component suggests a generic methodology to solve the risk rewrite problem. Moreover, diving into the formulation component's logic, we can interpret multiple WSL formulations and the diverse risk rewrites from a single perspective.
Before introducing the framework, first define several abstract notations that will be used throughout the paper. There are three main characters and one supporting character in the framework. The main characters are the vector of data-generating distributions P, the vector of risk-defining distributions P, and the vector of base distributions B. The supporting character is the vector of loss functions L. The reason for using vectorized pseudonyms is that the proposed framework uses matrix multiplication as a basic mathematical operation. P contains distributions that produce the observational data. For instance, PP;):) in PC learning (Table 2) and Ps=k.x is the k-th entry of P in CL learning (Tablle 3h. We use classification risk (1) to illustrate our framework. So P consists of joint distributions Px,.. We can look at Tables 2 and B and see that there are basic elements that define a data-generating distribution. These are class-cond class-conditionals Pxiy in Table 2 and joint distributions Px, in Table 3 Since these basic elements do not necessarily coincide with the entries of P, we denote them as B. consists of loss functions and its k-th entry is (y=x(g(X)
= Band
3.1 The Formulation Component of the Framework
The construction of the formulation component is to study the connections among WSLs and provide a foundation for developing the generic methodology. We draw inspiration from Section 2.2 Each WSL formulation represents type of weaken information of the joint distribution Py,x in supervised learning. For instance, unlabeled data discards the label information (Lu et al., 2020 is a label that cannot be the ground truth (Ishida et al. 2017 7 comparative relationship of two ground truth labels (Bao et al.) 2018
2021 J the complementary-labde
Yu el al. 2018), and the similarity encodes
Shimada et al. 2021 Cao et al. 2021b). Thus, we are motivated to search for a general way to link data-genorating distributions with the joint distribution.
We start by linking the gettaggnne distributions P and the base distributions B. This involves finding matrix correspondences Tables and We assume that matrix Moor formalizes the link:
P Moon
(35)
Taking PU learning 4 for example, Meorr aims to connect P P (Pt)) with B = (PxIr To keep the framework as abstract possible, would like to defer the discussion of all other P and B until we realize their corresponding Meorr in Section
The matrix formulation has two advantages. First, it provides a unified way to characterize a wide range of WSL settings. By studying the entries of a matrix, we can easily link one WSL scenario to another to form
We reserve P. P. and for vectors of distributions and L and L. for vectors of loss functions. We address them "the distributions" and "the losses" avoid the verbose "the vector of distributtonns/lss
14

---

Published in Transactions on Machine Learning Research (01/2025)
reduction graphs of WSLs. As the first main topic of this work, Section 4 shows, for given WSL setting, how to find the corresponding matrix Meor, and Tables 7 summarize fifteen WSL settings covered by our matrix formulation and depict reduction graph rooted from Meore- The following subsection illustrates the second advantage of aiding the construction of a generic methodology for conducting risk rewrite.
3.2 The Analysis Component of the Framework
Note that the conventional expression 1 can be simplified, by the imner product, to be R(g) - -Zex L Pdr. It is immediately possible rewrite the risk under gettratnnn distributions P by showing L P = where L is called the vector of corrected losses and its role will be clarified later. Therefore, it is imperative to establish the connection between P and P. The goal can be achieved by linking B and P since assumed that P = B in the previous subsection. Recall from the beginning of this section that the base distributions B are of the forms Pxjy or Px,y, and the risk-defining distributions P are of the form Рx,.. Given their label-relevant nature (i.e., they are either the joint distribution or the class- conditonndiionlls)) we assume that there exists transformation matrix Must that satisfies MustP. Thus, (35 becomes
have
P Meorr Merst.
(36)
Having the freedom choose Must allows the framework handle different base distributions B and adapt to various performance measures that define P, as we will discuss in Sections 5.1.1 5.2.1 and 6.
respectively.
The reason why connecting P with P 036 helps the construction of the corrected losses is that if we manage to find a way to compensate for the combined effect of Meor and Must, we can implement the compensation mechanism on the "corrected" losses L. Specifically, suppose there exists a matrix Mt core satisfying
P = M
(37)
Then, the corrected losses defined by
L = L MM
(38)
core
allows us to rephrase the classification risk as
J Pdr
[
Jrex I M Pdr
[ L Lddd==Rop =
R(g),
(39)
providing rewrite for R(g) with respect to P.
The above procedure describes a generic methodology for the risk rewrite problem. As the second main topic, we instantiate the framework by presenting the corresponding matrices M1 core and Must for each learning
scenario Section 5 to demonstrate its applicability.
3.3 Intuition of the Framework
The key equations discussed in Sections
3.1 and are
3.2
33
36
p Meou B
Mcor Must
LTP
38
M Moo Must P L
37
The logic behind them succinct and interpretive. First, from a formulation perspective, viewing matrix Moore as a contamination matrix that corrupts the basc become the contaminated P (35), we inter- pret this contomination mechanism as sacrificing certain information exchange for certain saved costs or privacy, reflecting the essence underlying WST formulations. In addition to formulating the data-generating
15

---

Published in Transactions on Machine Learning Research (01/2025)
mechanism, the link between B and the risk-defining distributions P (36 connects P and P to motivate the methodology design. This novel viewpoint of connecting the data distributions via the explicit two-stage formulation facilitates the unification work in this paper.
Second, regarding the methodological design, becomes casier to devise a countermeasure when the con- nection between P and is good shape. The design I,T = I." M involves M which captures common idea behind risk rewrite: Restoration of the risk-defining distributions and the original loss functions is accomplished by the decontamination (37 provided by L. Furthermore, the instantiations of LT L Moor (38) justify that the apparently different forms of corrected losses reported in the literature (i.c., referred papers that contribute to Tables and and those referred to as recoveries in Section F) essentially stem from M In summary, the proposed framework is abstract and flexible enough that we use in the current paper to formulate the contamination mechanisms and provide a generic methodology for wide range of WSLss
3.4 Building Blocks: The Inversion and the Marginal Chain Approaches
We describe two building blocks, the inversion method and the marginal chain method, that will be used to devise Motr that satisfies (37) in cach scenario we study later.
Proposition 1 (The inversion method). Let P and P be vectors. Suppose P p= MP holds for invertible malria M. Then, choosing M M-1, have P = Mt Moor P.
Proof. For any invertible M, it is casy to see that, by assigning Mt porr = M-1, one has
M P = M M-
We remark that this simple strategy adopted in many LNL works. A handful of related papers are Cid-Sueiro 2012). Blanchard & Scott (2014) Menon et al. (2015), van Rooyen & Williamson (2015), Patrini et al. [2117] van Rooyen & Williamson (2017), and Katz-Samulls et al. (2019). Hence, it can be applied to WSLs that are special cases certain LNL scenarios.
Proposition 2 (The marginal chain method). Let Y k [K] be a class label, where [K] is the set of classes associated with the classification risk. Let S = {81, (2,, .2...... s/s( 2|R] be the set of class sets and S be the random variable of the observalional oulcome. Denole
Py
Ps=mi
P=
: Py=K-X
and P=
Ps=eispi
Then,
P
P Ps=
Ps=ei V=K.X
Ps=mn
P3=
P Ps Y=K.X
M =
(40)
PS=
P==
Ps=ass IY=K.X
satisfies P MP, and
Py- Py-l|s=0a
Py-
Py=a/s=aix
Py=as==ix
P
Mt
(41)
corr
Py=K
PY=K
P
16

---

Published in Transactions on Machine Learning Research (01/2025)
satisfies P M
The role of S is to represent weak supervision that encodes some combinatorial information about the unobscrvable true label Y. We will discuss this concept in detail in Sections 4.2 and 5.2
Proof. It suffices to show (MP), = P for any j E [[S]]. Taking the inner product the j-th row of M and P, we have
K
P Ykk PY=kx
Σ
Ps=
PP==,,
k=1
that verifies 440
Next, we prove P Moore by showing (Morre)) P). = PP. For each E [K],
K S=
(M = -(Morr =
Σ
Py=is
V= Pr=
j=1
XP
b
PY=Lx = P..
(42)
Besides finding the inverse matrix, we propose new approach called the marginal chain to achieve 37
The development of this approach begins with the observation that Ps=,,, in P = MP distribution where is marginalized out. inspires an idea that one could perform another marginalization to restore the original distribution Py.: specifically, by marginalizing out S. The design of Mf in (41) aims carry out the idea. As shown by (a) and (b) in the proof, two consecutive marginalization steps on Y and then $ give the name of the marginal chain.
Both the inversion and marginal chain methods have strengths and weaknesses. The inversion method only requires P as a real vector but needs the invertible assumption on the contamination matrix M. contrast, the marginal chain method exploits that P, in fact, is a distributional vector, allowing it to find a decontamination matrix M even for a non-invertible M. restriction of the marginal chain method is that the construction of M is regulated by probability equations.
We are ready to justify the proposed framework through the following two sections. Section discusscs weakly supervised scenarios that can be subsumed by the formulation component (35). Section 5 verifies the analysis component by instantiating (38) to conduct the risk rewrite for each scenario mentioned in Section 4 In both sections, we divide the scenarios into three categories. The first two are WSLs that can be viewed as special cases in either the prevalent MCD or CCN settings. The third category contains confidenco-based scenarios. The notations listed in Table I will still be functional. For all notations and their abbreviations
required in the coming sections, please refer to Appendix B
4 Contamination as Weak Supervision
In this section, we instantiale the contamination matrix for each weakly supervised scenario listed in Table 2 and Table 3 Tables 7 summarize the contamination matrices developed in this section. Each table also represents a reduction graph of WSL scttings. These reduction graphs cluster WSL settings into three main categories, providing a hierarchy of relationships. With this hierarchy, we can understand, compare with, and relate to different settings even grow the hierarchy by adding branches. Next are the notations
17

---

Published in Transactions on Machine Learning Research (01/2025)
for reading the graphs. For two contamination mechanisms, U and V, use Mu - My to denote " "Mu is reduced to My" or "My is realized as Mv"; and Mt ~ My means "My is generalized to My
The proposed framework provides a generic strategy for formulating multiple weakly supervised scenarios. Thus, the proofs will have a certain degree of similarity. To avoid repeating similar proofs, we provide proofs that appear for the first time. For auxiliary lemmas and results whose proofs are similar to the previous ones, we refer the omitted proofs in Appendix C In particular, the omitted proofs in Section 4.1 can be
found in Appendix C.I. and those in Section 4.2 can be found in Appendix C.2
Table 7:
Contamination matrices of MCD category in Section 4.1
WSLs
Entry Parameter
Contamination Matrix
Reduction path
MCD
Tps Yn
MMCD
45
Meorr MMCD
UU
Y1: 7/
Muu
49
Moorr Muu MMCD
PU
71 = 0, 12 = Tp
Mpu
55
MUu - MPU
SU
71
*p
F
7/2 Up
Msu
51
Muu + Msu
Pcomp
71 mpta 72
-
MPcomp
52
Muu + MPcomp
" 4m
DU
71
1/2, 72 = 4p
MDu 53
MUu + MDU
SD
7/2 1/2
MSD 54
MUu + MSD
Sconf
Mscout
555
Meorr Msconf
Table 8: Contamination matrices of CCN category in Section 4.2
WSLs
Entry Parameter
Contamination Matrix
Reduction path
CCN
Prix,x 59
Mccx
60
Moorr McCN
Generalized CCN
PSIV.X
61
MęCON
64
Moor + McON m MgOCN
PPL
C(S, X)I [Y S]
65
MpP1.
66
MRCON MpPI.
PCPL
I (Y E S]
MPCPL
68
MgCCN + MpPL + MPCPL
MCL
4 LY $
775
MMCL.
(11
M&CCN MpPL. MMCLL
(3)
McCON + MpPt + MMCL + McL
CL
S = 1, - Y E S]
Mct.
76
Table 9: Contamination matrices of confidence-basel/ calegory in Section
WSLs
Entry Parameter
Contamination Matrix
Reduction path
Sub-Conf
Pyemix Py=Mix
Msub
80
Mcor + -Muu
SC
). = {y6} in Msub
Msc
81
Msub + Msc
Pconf
K 2, ys = P in Msc
Mpconf
Msub Msc + MPcouf
Soft.
Msan
84
Msub Mson
18

---

Published in Transactions on Machine Learning Research (01/2025)
4.1 MCD Scenarios
As listed in Table 6 in binary classification, the MCD model (Menon el al. 2015 corrupts the clean class- conditionals Px|Y=p and Px|V=n via parameters and In as follows:
P Pp == (1 - (p) Px|Y=p + Tp Px|Y=
(43)
Px Px|Y=n= :n Px|r=p (1 (1-7)) Px|Y=
where Tp: 7n [0, and 7p "h 1. Viewing the contamination largets Px|r=p and Px|Y=u the base distributions
PXIIV=P
B
Px(r=n
and denoting the vector of data-generating distributions
Px
P
Px Px|E=n
express
43 in the following matrix form
Px|
1 1-
7p )
(XxI==))
(44)
P Px|p=n
1 1- 7/
PXIY=n
Comparing
44
with P Moor
35 we find that the contamination matrix Moor is realized as
(1
(1-7p 7/p
MMCD
(45)
% - %a
in the MCD setting.
4.1.1 Unlabeled- (UU) Learning (Lu et al. 2019)
Next, show how to characterize UU learning by contamination matrix. Naming
Tp P Px + Tn Pxiy=n
as Pu is feasible since Tp Px|y=p Fn Px Px generates data that statistically equals to data sampled from Py,x with labels removed. Viewing "p the mixture rate of samples from Px and Pxxy==: Pu is parameterized by Tp. Therefore, we interpret (S) recalled as follows, as formulating two unlabeled data distributions w.r.t. mixture rates (1 mmm and 72, respectivcly:
Pu, (1 (1-70) 7) Px + 71 Px|v=m
Pu. 72 Pxjy=p + (1 - 72) PxiY=n-
Taking the class-conditionals as the base distributions
B = (XxI==D
(46)
Px|r=n
and converting S to the matrix form, express the data-generating distributions of UU learning
Pc.
p =
(47)
Pia
19

---

Published in Transactions on Machine Learning Research (01/2025)
Pun
11-2 71
) 1-72
71
(xxx=
(48)
Pua
72
7/2
Pxi
and we arrive at the following lemma.
Lemma 3. Let B (46) be the base distributions and P n1 72 [0, such that n + 72 # the contamination matric
47
be the nato-gennrrating distributions. For
1-72
Y1
MUU
(49)
72
1-72
characterizes the data-gen mata-generoting process of UU learning
via
(48)
Comparing 448 with the formulation framework P Meon B
35
we see that in UU learning, M Moore is
realized as Muu:
Meor - MUu.
Like MCD, we assume "1 + 72 + 1. Our assumption is equivalent to that of MCD since the case of swapping Peorr and Qeorr in Menon et al. (2015) corresponds to 71 + 72 > in our case. For details, refer to the discussion in Section 2.2 of Menon al. (2015). The need for 71 + # 1 can be explained by examining the entries in MUU. The constraint "/1 + 72 guarantces distinet rows in MUu, implying the obscrved data sets sampled from two distinct distributions. On the contrary, allowing "1 + "22 ends up observing one unlabeled data set (i.e., Pu, Pv₂) since 71 72- Lu et al. (2019) proved in Section 3 that it is impossible to conduct risk rewrite one only observes one unlabeled data set.
Assigning "1 = "pp and 72 = tn implics that MCD and UU have essentially the same data-generating process from the contamination perspective, as (44 and (48) have the identical right-hand sides (i.e., the same contamination targets and the same contamination matrix). However, they bear different meanings in respective research topics (i.e., distinct notions the left-hand sides of the equations): In MCD, one still observes data with labels, nonetheless noisy, while in the UU setting, one observes two distinct unlabeled data sets. We use ">" to denote their relation in the UU row of Table 7
Connecting UU learning with MCD, and later the generalized CCN with CCN in Section 4.2.1 allows us to categorize WSLs from the LNL perspective into Sections 4.1 and 1.2 In the rest of this subsection, we collect WSLs whose base distributions are class-conditionass and show Myu instantiates their formulations via respective assignments of 71 and 72-
4.1.2 Positive-Unlabeled (PU) Learning (Kiryo et al.] 2017)
Recall from [4 that Pp = Px and Pt = Px. The following lemma describes the contamination matrix of PU learning.
Lemma 4. Let B 46 be the base distributions and
PP
P:=
Pu
be the dala-generaling distributions. Define the conlamination matria
MPU ==
(50)
Tp
Tn
Then, P Mpu B, and Mp characterizes the data-generating process of PU learning
20

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. We apply the same proof strategy as in Lemma g
By definitions,
(xxI==)
1 Pxpr=p + Px|y=
Mpy = Ap Tn
PXxY==
Tp Px|x=p nn Px|Y=n
Since 1- Px|Y=p +0- P0 = Pxiy=p and Tp" Pxx + Px|Y== Px, obtain Mpy = P. 0
Comparing with (35 we that the contamination matrix Meorr is instantiated MPU 50 in PU learning. Further, MPU can be obtained by assigning "/1 0 and 72 Tp in MUU 149 and hence, obtain the reduction path
M Moon
+ MUU - Mpu-
4.1.3 Similar-Unlabeled (SU) Learning (Bao et al.- 2018
Recall Ps [10 generates the pair of data points (x, who share the same label. In addition to the pairwise distribution Ps, a pointwise distribution
Px
Y + PX
Pg
mp + T
is also defined for single data point (Bao et al. generating distribution when constructing the contamination matrix in the following lemma. Lemma 5. Let B 40 be the base distributions and
2018 Lemma 1). Therefore, we choose Pg as the data-
P = Ps PU
Then, the contamination matriz
ap 7
Msu
F
(51)
Ap
which satisfies P M, characterizes the data- mata-generrlling distributions P.
=2 and 72 = Tp Mou 499, and hence, we obtain the
Further, Msu can be obtained by assigning 71 x reduction path
Moorr + Muu + Msu.
4.1.4 Pairwise Comparison (Pcomp) Learning (Feng et al. 2021
In SU learning, we formulate the pointwise data-generating distributions Pg and Pu; likewise, we use the following pointwise distributions of Prc (16) formulate Pcomp learning:
[ dr Tp Y=p + T JEEX
Psup
Tp + m2
Pint = / dxc
m >XPx1yy=
+ F. 7 X
T +
21

---

Published in Transactions on Machine Learning Research (01/2025)
Lemma 6. Let B 46 be the base distributions and
Psup
P
Pinf
Then, the conlamination malrix
Tpt
MPcomp
(52)
In apt
which satisfies MPcomp B, characterizes the data-generating distributions P.
Further, Pcomp be obtained by assigning 7/2 tpt obtain the reduction path
m and
72
mp
in MLu 49
and hence,
# tm
Meorr MUn + MPcomp
4.1.5
(SDU) Learning (Shimada et al. 2021
Dissimilar-umlabllee (DU) learning and similar- (SD) learning are two critical components of SDU lcarning. Hence, we present the matrix formulations of MpU and MsD. Similar to the strategy taken Sections 4.1.3 and 4.1.4 we use the following pointwise distribution
[ PD dx' PulY=p + Pa ==n
Pb
2
Shimada al. 2021 (36) in Appendix A.1) the following formulations.
We formulate the contamination matrix of DU learning via the following lemma. Lemma 7. Let (46 the base distributions and
PB P =
Pu
Then, the contamination matriz
1/2
1/2
MDU =
(53)
Tp
Tu
which satisfies == MDuB, characterizes the data-gemerating distributions P.
Furthermore, since Muu 49 reduces to Mpu by assigning 7/1 = 1/2 and 72 = Tpp we have the reduction path
Moorr + MYU + MDU-
The next lemma formulates the contamination matrix of SD learning. Lemma 8. Let B (46) be the base distributions and
Ps p
PD.
22

---

Published in Transactions on Machine Learning Research (01/2025)
Then, the contamination matriz
MSD
"
(54)
1/2
1/2
which satisfies P= Ms characterizes the data gettaggenngtingg distributions P.
=²
Moreover, because Mue (49) reduces to MSD via -
and 7/2 = 1/2, we obtain the reduction path
Moor
MUc MSD.
4.1.6 Similarity-Confidence (Sconf) Learning (Cao et al., 2021b)
Recall from the Sconf setting 18 that (x, is pair of data sampled i.dd. from Px,x PxPxx On seeing Px, one might wonder if it is sufficient to express the data-generating distribution simply Px = P + Py=n.x. This approach, however correct, does not consider all available information in the Sconf setting. Similar to Mvu that uses parameters "/ and 72 to characterize the data-generating process CU learning, we use the following lemma that includes the confidence r(x, x') == Py=v' to characterize Sconf learning. Let us abbreviate r(X, X') as r, Px|y= as Px and Px.jy=n as x n-
Lemma Assume Tp # 1/2. Let B 46 be the base distributions and
Pxxxx
p:=
PxPx
Then, the contamination matrix
Xp 0 Px 2
Mp xp x 8-
MSoonf
T-
(55)
1 Px Xl - P px
Tu ( x Ppce)))
which satisfies p = Mscont B, characterizes the genttaggnngaiing distributions P.
Proof.
Note that once
Tn
PxPx (TTPx'1p - P Pxpp + (T -xpx'1 Px
(56)
Tp
and
Tp -
PxPx - Pxlp + (m/P''pp - =2Pp'(1)) Px
(57)
is obtained, reorganizing the terms gives
( Ix - px(nn
Ty P1 -x
Pxxxx) PxPxx
Pxx
p-
(58)
Tu up
Tu(
|n 2 p
Fu P - P
Px
and finishes the proof.
Therefore, will focus on proving (56) and 57 According (2) of Cao al. (202bb) the confidence r(X,X) measuring how likely X and X' share the same label, is shown to be
x=) x2 x Px X'Ip + x,,PX Px
Px
23

---

Published in Transactions on Machine Learning Research (01/2025)
It implies
rXxxx = T/PxIPPX' + P
and
(1 (1-r)PxPx: = (PxIpPP'' PxIoXxx11
If up 1/2, Fp -r and r- nn # 0. As a result, 56 is achieved as follows
r Tu
PxPx
r- r- -1 (1-r) PxPx
Ap
Tp
PPppPPP'l + TiPPx|
Tp (PxipPx'la + P
Tn
TppxIpPP' P
n 2 PPPlaPX'1 x/pPp|?? Px'lp-
Also, 57
is achieved by having
Tp
T - -r) -r) PxPx
Pxxx =
n
Tn
"p
Tp (PxipPx11 + PPxiaPX'l -xpxxppPx Px - PP XxPxxPPX'1 Px
= Pxxxpxx11 - - Px'Ip + TxPx11 - xmpxx1
The equality 58 implies that the inner product of the first row (resp. the second row) of Msconf and B represents a way (resp. another way) of obtaining Px Although one might suspect that it is redundant to formulate Px twice, we show in Section 5.1.6 this expression is crucial to rewrite the classification risk via the proposed framework. Furthermore, comparing = MScont 588 with P M B (35 we have the reduction path
Meorr + MSoonf-
Note that Mscont does not fit the intuition of mutual contamination perfectly; we list Sconf learning in this subsection as all settings share the same base distributions B 46).
4.2 CCN Scenarios
The formulation component 135 also applies to the CCN model. Unlike MCD contaminating class- conditionals (distributions of X), CCN corrupts class probability functions (labeling distributions). Next, we
show how to formulate CCN via. 35 and extend the formulation to characterize diverse weakly supervised
settings.
In binary classification, CCN Natarajaa et al, 2013 2017 corrupts the labels by flipping the positive (resp. negative) labels with probability Py=a|Y=p.X (resp. Py=p1 ==))). Specifically,
Py=pIx == Pv=ply=p.x Py=pix + Py Pv=ply=n,x Py=n|x
(59)
Py-njx Pv-n|y=p.x Pr Py Py-njy=n, Py=n|x
define the contaminated class probability functions. Taking the contamination targets Py=pix and Py=u|x as the base distributions
Py=pix
B:=
P Py=n|x
24

---

Published in Transactions on Machine Learning Research (01/2025)
and denoting the label-generating distributions Py=ple and Pv-n x
P: Py=plx
Py=alx
we express 59 in the matrix form as follows
Py
PrepllY=pxx P
Pr=pix Py=ulx
Py=u|x PY=nlY=pixx Py=ulY=ux
Comparing with the abstract form P = Meorr 35
we see that
McON = PPr-pY==PX Pr=ply=ux
(60)
(rrnny=nix Py=n|Y=n,X
instantiates the contamination matrix Moorr in the CCN setting.
4.2.1 Generalized CCN
The concept of contaminating a single label can be extended to generating a compound label in the multiclass classification setting. Let 2 be the power set of the label space y = [K]. Define S = 2" {0,3} as the observable space of compound labels [ Since a compound label E S consists of an arbitrary number of class indices, one can view the probability of observing S for given X governed by several class probabilitics PY= x- Therefore, generalizing the CCN formulation process of compound label S
we define the label-generating
K PSIX Σ PSYYAAXPY-NIX
where the role Pspr, is the probability of converting a single label Y to a compound label e S. Moreover, CCN, the distribution Px not contaminated. Thus, by multiplying Px on both sides, we obtain the gata-gener distribution
K Ps. Σ Ps
(61)
Viewing x as a contamination probability, we arrange P Ps=a Y into a matrix in the following lemma to formulate the contamination matrix for our generalized CCN (gCCN) selting.
Lemma 10. Let the elements in S be $2........8 }. For the gCCN setting, denote the data tettaggnnrottig distributions as
Ps=si
p==
(62)
P Ps=siapix
and the base distributions as
Py=1,
=
=
(63)
Py=K,x
Removing and y is that the empty does contain any label information trivial case.
25

---

Published in Transactions on Machine Learning Research (01/2025)
Define
P==
P==
Ps= Y=K P p= Y=K.X
Ps= P==
MACON =
(64)
Ps=sg|V=LLX Ps=ss P
Then, P= B.
The lemmn implies that. MgCON is the contamination matrix characterizing P of the gCCN setting. Also, note that P = A B essentially the matrix form of 66 Moreover, MgCON generalizes MceN 660) by extending the label spaces: Both the clean label Y and the contaminated label Y belong {p. in CCN, while in the gCCN setting, the clean label Y E {1, K and the compound label S (s1, s
Proof. For each [[S]], we have
(MrCoo Σ P
Σ Ps Ps Y = PSmaJ,X Pj.
Comparing P = Mgccx B with the formulation framework P = Mcorr B 35 we have the reduction path
M + McCN ~ MgCCN.
Similar to Mut 49 which induces multiple contamination matrices as special cases of the MCD model, MgcoN also derives several contamination matrices formulating partial- or complementary-label settings, as we will show in the rest of this subsection.
4.2.2 Proper Partial-Label (PPL) Learning (Wu et al. 2023
For a given example <y,z) and compound label s E S, we call s a partial-label of x if E Statisti- cally speaking, we assume PYes|s.x = 1. Formally, according to Definition 1 of Wu et al. (2023), the contamination probability can be defined as
PSJY.X == C(S S).
(65)
via a function C:Sx X R. we call such partial-label scenario proper.
Since the discussion above only involves specifying Ps v,x, replace the entries of M MscoN
66
according
to 65 to construct MpPL:
= E si]
C(s,, XYT = 22E 81]
((s, es]
X)s2 = 1 e 52]
X)s = 2
X)1 = K e s2]
(66)
: C(sss) [ 1 sissl
C(sss) X)I [Y 2 2E
C(sss) [Y K Essi]
The following lemma justifies MpPL as the contamination matrix for PPI learning.
Lemma 11. Let the elements in S be {si, .2. (|ss}. s(ss) For each j E [[S]], let the j-th entry of P be
P; = Ps Ps=sj.x = C(S = 8j, X) Σ Pr=k,x,
kE*;
26

---

Published in Transactions on Machine Learning Research (01/2025)
which denotes the data-genentn gent-ggnnnrtingg distribution of (s,, Assume the base distributions B and the con-
lamination malriz MrPL are given by 63 and (60), respectively. Then, MPPL salisfies P = MpP1, B and
characterizes PPL learning 26).
The entry replacement that converts 64 to 66 through 65
gives the reduction path
Moor + MgOON + MPPL.
4.2.3 Provably Consistent Partial-Label (PCPL) Learning (Feng al., 2020b)
In PCPL, the probability of each partial-label is assumed to be sampled uniformly from all feasible partial- labels. Since there are 2k-1-1 feasible partial-labels for every y, the label-converting probability P P
is 2x T yf E
It corresponds lo assign C(S, X) 1 1-1 in 65). Hence, we obtain
C(S, & SS] 2K-1-1 (Y E),
(67)
which reduces the label-converting process of PPL. to that of PCPL, and recovers (5) of Feng et al.
2020b
Then, replacing entrics
66
via
67
we obtain the contamination matrix of PCPL learning
1|Y = E s1]
[[Y = 2 E $1]
[[ = K E s
I| = 1 E $2)
I[Y = 2 E s2)
I = K E s2)
MrCP1 = 2K-1-1
(68)
[|Y=1e8
I[ sisss
I[ = Ke ess)
and the reduction path
Moorr MACON + MpP1. > MPCPL-
MPCP1. characterizing the data-generating process of PCPL is justified by the following lemma, whose proof follows the same steps that for Lemma
Lemma 12. Let the elements in be {s1, S.... s(s)}. For each j [[S]], let the j-th entry of P be
= Ps 2K-1
Σ P kEs,
which denotes the data-generating distribution of (8j, X). Assume the base distributions B and the contam- ination matrix MpCPI. are given by 633 and 68 respectively. Then, MpcPI. satisfies P MMcr1, B and
characterizes PCPL learning 24
4.2.4 Multi Multi-Complementtyy-Lbbell (MCL) Learning (Feng et al. 2020a)
Recall the discussions in Sections 2.2.9 and 2.2.10 that a complementary-labne contains the exclusion infor- mation of a true label. That is, for data example (y,4), we call a set of class indices ă E S = 2 {0,3)
an MCL of x s does not contain y.
Denote S {5i, .2,... The equivalence
K
Σ ΣK-1 Pisi
1 Exes Py.x, if [|| d, (KF
1
Σ
Py.x [|S] -d
s
=d
K-1 [3]
0,
otherwisc
d=1
YΦS
4There (1 -
combinations whose union with {v} partial-label of y-
27

---

Published in Transactions on Machine Learning Research (01/2025)
allows us to define the data-generating distribution of MCL
22
P PSBIiX
P ::=
(69)
Ps PS=EN,X
where for each j E [N],
K-1
P Pls,imd
P P=aaiX
Σ [8 Y
Px =d.
(70)
K
Let 2), be fixed. The dlatageeeraatng process of MCL proposed by Feng et al. (2020a) is that one first sam- ples a size with probability Pis]=a- and then samples a uniformly at random from {$d,1, Sd,2. Sd.N. S, where 5d,- mcans set of size d excluding and Na is the total number of those sets. Note that Na ( since remove y from Y and then choose set of size d to form sa... Furthermore, cated lower index system to distinguish { $d,2 Sd from S = (51. $ SN) since d ranges from 1 to K and SK-1 Na >K- (K 2 -8]. According to this mechanism, we construct MMOL:
need more compli-
Pist- I[Y $1] (1-T1) I [[ = 82]
P P [[ = 51
P K & 51
Pisiital
P Pis
[Y = = 82]
P
[Y = K 82]
(P1)
(71)
Pis (px)
P T = 2 5N] (px))
Pis=lanl T ( K & kN]
T kx]
The following lemma justifies MMCL as the contamination matrix for MCL learning.
Lemma 13. Suppose the base distributions B. the conlamination matrir MMCL, and the dala-generuling and 70 respectively. Then, MMCL satisfies P = MaC1, B and
distributions P are given by 63
71
characterizes MCL
The subtle connection can be established via relation between partial-label and complementary-label. Recall
At the first sight, MMCL 71 does not resemble MrcrL 68 MPrL
66
2 (0.3) S (51, .5.
where 8, is a MCL. From the partial-label perspective, we can establish the following set equality relationship:
2d (0, = S = 131, 82, ...
]ND = {81 = 31,,1, 82 = 82.............................. SN = y V(
(72)
This is because for every 5 E S, there is a s such that s = Va The intuition behind 72 is that & is an MCL of v, then s = 8 must be a partial-label x. Therefore, we can also use the set partial-labels {si, S2, .........'' SN} to denote S. The following lemma exploits this relation show that MMCL indeed a special case of MPPL-
Lemma 14. Assign each (s, k) entry of MpP1.
66 with
P 1 JY
C(s,X)I[Y E
E ss.
(73)
(1111)
28

---

Published in Transactions on Machine Learning Research (01/2025)
Then, the resulting matrir
P 1 si] (141-1)
P = 2 si]
Pis-io [Y K E sil (11-11)
(11--1)
P1 (1gg
[ =1 E 82]
Ple = 2
[Y = K E
(12l-1)
MaCL
(74)
Ps 1x 1x
P 2 E sNl (1on111)
PIs--oN I y= K E SNl (xll11)
is equivalent to MMCL
71 under the relationship
72
Proof. Note that for every j E [M], = 13. This implics P(9|=1a11 = Pist=1s31 (1-1-))
(K= and
I[ Esy] = I 3y] hold for every j [N]. Therefore, for each (j, entry in MaeL and MMCL 71 have
Pis 1s 1
Pis B [[Y $ syl.
1[ ke s,]
(75)
K-1
1,,1-1
The assignment rule
73
implies the reduction path
Mcorr McCCN + MPPL MMCL-
Comparing
73
with 67 of PCPL, that MCL and PCPL can be viewed as different ways of composing
Py.x to generate a partial-label, with weights Pisiia and 2x -_ respectively.
4.2.5 Complementary-Label (CL) Learning (Ishida et al. 2019)
As special case of MCL (Section 2.2.10 we can construct the contamination matrix Mct. from MMOL- The set of all CLs is composed of MCL with size 1: {1}, ........ {K]. Therefore, assign values in MMCL (71) as follows. For each S, Pis =|я = 1 if |s|
and P| 0f 1. Dropping all-zero rows, we
obtain from 71 the contamination matrix of CL. learning
* = $ (H
, 2 (1) R 22 (2H
* = K $ (1))
* = 1 & (2)
x = K & (2)
McL.
I = & (K))
TY = 2 [KH
T = K K& (KH
K-
1
1
(76)
K -
and the reduction path
Moorr + MsOON MpPL + MMCL + McL.
Furthermore, is easy verify that given 63 for any j E [K],
(McLB)
Prx P
K
Y#1
which corresponds to formulation 20 Hence, have the following.
29

---

Published in Transactions on Machine Learning Research (01/2025)
Lemma 15. McL (6 is the contamination matriz characterizing the data-generating distribution P3.x 20 of Cl. learning.
4.3
Confidence-bent based Scenarios
At first sight, there seems to be no connection between "contamination" and single-class classification ct al. 2021a). However, the following derivation
Cao
Py=uIx PY=j,x Py=jix
Py=uiX Py=Jix Py= Px PY=
(77)
reveals a way to contaminate a clean joint probability Py=j,x to the joint probability Py= of designated class Ys via confidence weighting Py-velX As will see in the rest of this subsection, the confidence weights Pr=jii are the key elements in formulating the contamination matrices for the confidence-based WSL settings.
4.3.1 Subset Confidence (Sub-Conf) Learning (Cao et al., 2021a)
Let Vd+ C [K] be subset of classes. Viewing Vd8 a "superclass", such that every instance of (y.x) will be labeled Y4 if y E Va, we can define its class prior as PYEx, = := Evey, Ty and its class probability function as PYExIX = Evex. Py=yix Substituting the designated class ys in (7) with the superclass V.
PrEZIX PY= = PrEZIx, Py=jiX
Py=jix Py=jjx PYEM..
(78)
shows that no matter what joint distribution Py=j,X to begin with, the confidence weight Pvex, x twists Py=jix that joint distribution so that every observed data appears to be sampled from the same superclass distri- bution P...x The following lemma leverages the observation to specify the contamination matrix Msub
characterizing Sub-Conf learning.
Lemma 16. Denote the base distributions as
PY=L.X
B:
P
(79)
PY=K,x
and the data-genngattig distributions as
Preei.
p==
PYEE.
Inserting the confadence weights into the identily malria, we define the contamination malria
Pyev.xx Pr=ix
Msub =
(80)
Pyevux
PY-Kix
Then, P = Msab B, and Msub characterizes the data-generating process of Sub- Conf learning 30
Proof. For each [K]. (MSwL PYEE.. follows from 78 Thus, P == M. B. It further implics all observed instances are labeled with the same superclass V'. meaning we can drop the observed labels, and the observed examples { is equivalent to set of i.i.d. samples from PxiYEr, 30
30

---

Published in Transactions on Machine Learning Research (01/2025)
Comparing P Msut B with the formulation framework P Mcorr learning, Meorr is realized as Msab:
35
observe that in Sub-Conf
Meorr 7 Msub.
4.3.2 Single-Clin Class Confidence (SC-Conf) Learning (Cao et al. 2021a)
We compare the formulation of SC-Conf (28 with Sub-Conf (30 and observe that SC-Conf a special case of Sub-Cou Conf when V&+ {y,} being a singleton. Thus, we straightforwardly obtain the matrix formulation of SC-Conf from Lemma 16 be replacing V in (50) with y/:
Lemma 17. Let the base distributions B be defined by 79 and the data-generating distributions be defoned by
Py Pr=
p==
Py Pr=vox
Define the contamination matrir
Py-ve Prsiix
0
Msc
(81)
P Py=kıx
substituting V% in 80
with ya- Then, P Bsc and Msc characterizes the dato-generating process of
SC-Conf learning 28
Since SC-Conf is a special case of Sub-Conf, we have the reduction path
Mcorr + Msub + Msc-
4.3.3 Positive-confidence (Pconf) Learning (Ishida et al. 2018)
Comparing 6 with 28 we that Pconf is special case of SC-Conf when K 2 and ys p since
(x( 1-Tp A further modification to 81 we obtain the contamination matrix Mrcout characterizing Pconf learning.
Lemma 18. Let = (Pr=pix and ::= (PY=pi) PY=p.x)
Define
PY==ux)
Propix Pyepix
MPcouf =
(82)
Pv=pix
Pyanix
Then, = MPcont B, and Mpoout characlerizes the dola-generuling process of Peonf learning
The entry replacement that converts 81
82
implies the reduction path
M
Msub
MSC - Mr
31

---

Published in Transactions on Machine Learning Research (01/2025)
4.3.4 Soft-Label Learning (Ishida et al. 2023)
The difference between the soft-label and the previous confidence-based settings (Sub-Conf, SC-Conf, and Peonf) how & sampled. The sample distriibutions condition on the label information in the previous settings, while that in soft-label is Px. Replacing the confidence weight Prew in 77 with 1 Pr=
Py=ix
Py=jix PY=j.x = Px
explains how to convert Py=j, to Px. Therefore, filling the j-th diagonal entry of the identity matrix with PY=sıx' obtain the contamination matrix Msoft for soft-label learning:
Lemma 19. Let the base distributions B be defined by (79. Denote the data- aata-generating distribution as
Px
P =
(83)
x
Define the contamination matris
0
Py-11x
Msoft
(84)
PY=xix
Then, Msott B, and Msott characterizes the data-generating process in 33
Unlike SC-Conf and Pconf, which special cases of Sub-Conf with V& taking only one label, the generation be viewed assigning V/+ [K]. Considering the entire label space results
procoss of soft-label in PYε[KIx 1; it coincides with the meaning of Px that samples regardless of the labels. Although techmically the soft-label setting is not a special case of Sub-Conf (recalling the V/. C [K] assumption from
Section 4.3.1b, Msaft (84p is reduced from Mgub 800 by realizing PresiX as Pye[K]IX = 1. Therefore, we
obtain the following reduction path
M
MSub > Msoft.
5 Risk Rewrite via Decontamination
We have demonstrated the capability of the proposed formulation component (35 in the last section. This section shows how the proposed framework provides unified methodology for solving the risk rewrite problem. Specifically, given each contamination matrix described in Section 4 we show how to construct the corrected losses (38) to perform the risk rewrite via (39). We then recover each rewrite to the corresponding form reported the literature to justify its feasibility. Because this paper focuses on a unified methodology for rewriting the classification risk instcad of the designs of practical training objectives, we assume the required parameters given or can be estimated accurately from the observed data.
Similar to the previous section, only provide proofs that appear for the first time to avoid repeating similar proofs. For auxiliary lemmas and results whose proofs are similar to the previous ones, we refer to the omitted proofs in Appendix D In particular, the omitted proofs in Section 5.1 can be found in
Appendix D.I. those in Section 5.2 can found in Appendix D.2 and those in Section 5.3 can be found in
Appendix D.3
5.1
MCD Scenarios
We apply the framework conduct the risk rewrites for WSLs formulated Section and summarized
in Table 7 A general approach is to show that the inversion method discussed in Proposition 1 provides the decontamination matrix M required in 338
32

---

Published in Transactions on Machine Learning Research (01/2025)
5.1.1 Unlabeled-Unlabed (UU) Learning
We justify the proposed framework for UU learning via the following steps.
Step 1: Corrected Loss Design and Risk Rewrite.
The three milestoncs in the proposed framework (1) finding the contamination matrix Meorr that char- acterizes the dala-generating process 35 of weakly supervised scenario, (2) finding the deconlamination
matrix M that compensates for the contamination effect (37). which is then used in (3) the construction
of corrected losses (38 for the risk rewrite (39
Section 4.1.1 has reached the first milestone 135
as
488
of the form P Muu B finds
71
71
MUu =
72
1 72
Pur
PXx
that connects the data- tatta-eneraaing distributions
and the base distributions B
PUa
Px
PY=
Note that not the risk-defining distributions P the second milestone. To further link P with P, we still need a Must that satisfies B = MustP. Introducing the prior matrix IT
PY=m.x we need an additional step before reaching
Tp
0
we see that choosing Must == IT-1 fulfills the need:
0
Tn
Prepix Py Py-miX Py
Tp
0
Pr=ppx) PY=n,x
(XX
MussP P
=.
Px(Y=n)
Hence, we can instantiate p Moory Murst
36 as
Pu:
PY=pii
Moull
(85)
PUa
Pr
in UU learning.
Next, Proposition to derive the docontamination matrix M to reach the second milestone
137
Corollary 20. Assume Muu in 85 is invertible. Then, defining the decontamination matriz for UU learning as
Mtu = 1LMUU
gives rise MtpP=P.
Proof. Suggested by Proposition the inverse matrix IM cancels out the contamination brought by MIuIl- in Assigning M HIMU and repeating the proof of Proposition we have
Mbu H = MMM -p=
that completes the proof.
Now we will move on to the third milestone. With M in hand, we devise the corrected losses L to achieve the risk rewrite for UU learning. We denote the corrected loss at the k-th entry of L as 4 := ( B In UU learning, y (U1, U2}. The following theorem proves
where & E y is class of the observed data rewrite in Section 2.2.3
5rehe definition of the corrected loss &g is contrast the original l, (x=x(((X))
33

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 21. Let 71, 72 0 and ?1 72 + 1.
Then, Mou defined in Corollary 20 is feasible. Moreover,
the vector of corvected losses suggested by (38)
(Ru,
lu,) = L. = IT Mou
with
(1 - -72)
=2 lu
tu,
cp
1 7/1 7/2
- 7/1 7/2
tu2
71 Ap
lp
(1 71 F e
(86)
71 722
7/1 7/2
achieves the following risk rewrile:
R(g) Bc, [Cu.] + Eus [!uz].
(87)
Proof.
Since ?1 + 72 # 1,
-1
1 1-70
-11
MTU-
11-11
71
I- 12
I- 72
72
72
1-71 72
I-
exists. Thus, it is feasible for us to define Mlu == IlMÚU according to Corollary 20 construct
Following
(38
we
L =L
and obtain
(Ru, Bvz) = L CIMut
(88)
1 1-72 I-
-21
= Cp
En
Tp
1-11-72
-
1-71
7 72
(1-72)
- "p
(ep
En)
1- 72
12
(1 (1-21 )m 1-71 72
I- 72
that gives (86).
Next, with the critical component L in hand, applying 339
we obtain
R(g) = / Pdx
(89)
x
[ (Pu, bu, Pu, lus) dx
= Ev, [Tv.] + BUs [tva]
where the first equality holds since according to Corollary 20
- LT P
34

---

Published in Transactions on Machine Learning Research (01/2025)
do not need to specify the instance in lp and ln to be x xn since the equality holds for any instance We only need to distinguish x from 2 when the corrected losses multiply the data distributions. In particular, the detailed form of rewrite 199 using S is
In 88
R(g) EU, [&v,]
BU, [RUz]
(1 1/2 72 (X
-/2 (x(x
ExunNPs
71 72
1
~7ppp (p(xx)) +
(1 - TT lu (x(
+ EguawPu
1 - 71 - 7/2
7/1 7/2
The freedom from specifying in (X"",,, allowing us to exploit the advantage of matrix multiplication while constructing the corrected losses. The freedom also enables separated treatments for the data distributions (e.g., formulating P = MuulI- and the corrected losses (e.g., devising L L Mou).
88 eliminates the notational burden of distinguishing (y(X") from
Step 2: Recovering the previous result(s).
Lastly, we verify the feasibility of our rewrite by showing that our rewrite corresponds to an existing result. By parameter substitution, we replace ?1 with - 8, 72 with 0', Ta with Tp. lp with ((g(X)), and l. with ((-g(X)). Then, 86 becomes
FT E(g(X))
00 Tp) f( ((-9(X)) 4(o(x)),
0 0'
l
8 Tp)
- 0) TT l(g(X)) L(-9(X)).
((-(X)))
0 0'
recovering the corrected loss functions (8) and the constants reported in Theorem 4 of Lu al. (2019).
5.1.2 Sisttie-Unllbbllen (PU) Learning
Recall that all WSLs discussed in Section share the same base distributions B 46). Further, as shown in Table the contamination matrix of every WSL scenario beneath UU learning except Mscont is a child of MUU on the reduction graph. It means P MculI- (85) is a general form for every child scenario reuse Theorem 21 to conduct the risk
in Table (with different realizations of 71 and 72)- Hence, rewrite for every child scenario on the reduction graph. PU learning is the first of such examples.
Step 1: Corrected Loss Design and Risk Rewrite.
By the following corollary, we prove the rewrite (5) in Section 2.2.1
Corollary 22. For PU learning, the classification risk can be rewritten as
R(g) Ep [4r] Eu [Lu].
(90)
where
E Tplp Tphn
(91)
Lu l.
Step 2: Recovering the previous result(s).
Since Pp is - and Pu is Px, we swap the notations to obtain
R(g) Ep [tp] + Eu [Pu]
= Ep [Tppp TTpul + Eu [fn]
= T,,Ex [tp] Ex [en] + Ex [fn]
from 90
which corresponds the risk estimators (2) in Kiryo et al. (2017) and (3) du Plessis et al.
2015
35

---

Published in Transactions on Machine Learning Research (01/2025)
Moreover, with an additional symmetric assumption of 4p + L, one further obtains
R(g) = Tp xpExiy=p pp - Tp Ex|== [en] + Ex [en]
Tpxxxy=p [pp] xpExx== [] 6p] + Ex [Cn]
TpEx [cp] Tppxxy=p [1] + xp 1pl Ex [ea]
2xpEx|V= [pp) - -x + Ex [en]
This expression recovers several risk rewrites such as (4) of Kiryo al. (2017): (3) of Niu et al. (2016). (2) of du Plessis el. al. 2005 and (3) of du Plessis al. 2014
5.1.3 Similar-Unlabeler (SU) Learning
According to Table 7 Msu a child of Muu on the reduction graph. Thus, we can follow the same steps
illustrated Section 5.1.2 justify the proposed framework.
Step 1: Corrected Loss Design and Risk Rewrite.
The following corollary combines (86) and 87 to conduct the risk rewrite.
Corollary 23. Assume Fp # 1/2. For SU learning, the classification risk can be rewritten as
R(g) Eg [3s] + Bu [Lu]
where
Pp + n
Pp + T
fg
l
l
2xp
2TP
(92)
l
Cp
+
l
2Tp
2T
Step 2: Recovering the previous result(s). To recover Theorem of Bao al. (2018), we first need restore Eg from Eg in Corollary 23 The following lemma provides
for to do
Lemma 24. Given B
46 and following the SU learning notations, have
Ps Pu
MsuB
where
" Paivende de Tp x
22 -2 Pary de'
Mau ==
Up
Proof. Since SPex Poly=pda'' = and Seex Poll=ndd''s 1, have M/u MsU, and hence Msu
Ps
Msy B
The last equality follows from Lemma
Pu
6 As the (-1 loss symmetric.
36

---

Published in Transactions on Machine Learning Research (01/2025)
Lemma 24
allows to slightly revise the derivation 89
follows:
J Pd fddx=fa
R(g)
I. MMM Bd
2ZEX
Tbseex P Parr=ada da' "
i Sarex Porizend'
SSEX ($s
bu)
PallY=p' Pa|Y=n
dr
Tp
Un
(a)
J.ee Palgdr'ds + /
Pu Pulo dr
nEX Ja'EX
Es [6g] + Eu [6v]
where equality (a) follows from the SU formulation 10 Then, denoting
((X) =
(X)
(x(),,
(98)
Tp
Tp nn
(_( =
n
(x(X) +
Tp
nT (x(X)
(94)
Tp Tn
up
and continuing with 92 we obtain
Es [&s]
(mp + 2) Es
(Cp en)
2TP
(m + m Es [C(X)]
((X) + ((X')
(nß + = Rs
and
Ey [Lu]
Eu
TT
Ep
up
ln
2Tp
2Tpp -
Ey (f_()
(95)
that prove rewrite 11 in Section 2.2.4 and recover Theorem 1 of Bao et al. The following lemma justifies equality (b).
2018 by matching notations
Lemma 25. Let (x, Ps defined by 100. Then, Es
[(X)
Es
C(X')
The derivation demonstrates the flexibility of the proposed framework in which a slight modification of Msu recovers the pairwise distribution Ps required for Eg [-]. Moreover, the technique developed here significantly
reduces the proof length in Appendix B Bao et al. 2018 Later in Section 5.1.5 apply the same trick
to recover Thcorem of Shimada ct al. (2021) for SDU learning.
We remark that the result. recovered in this paper is merely Theorem of Bao et al. (0018 but not the last expression (5) of Bao et al. (2018), which later was implemented as the objective (10) for optimization.
is because, pointed out by Negishi (023), the additional assumption Ps(x, 2') Ps (x) required for achieving (5) of Bao et al. (2018) is impractical. We note that the remedy proposed by Negishi (2023) can be analyzed by the proposed framework, but omit it due to the amount of overlap with the analyses in
Sections 5.1.1 and 5.1.3
7The matching to the notations Bao al. 2018 follows: Tp is T4. No is n... m क. is ws. Ps is ps, Pu is P. Ep is {(f(X)++1) f, is e(f(X), L(X) by definition is žς (R(f(X), -(((())))))))(())))))))))))))))) and (f(()) by definition is 2n (X(()) + ((())
37

---

Published in Transactions on Machine Learning Research (01/2025)
5.1.4 Pairwise Comparison (Pcomp) Learning
We follow the steps illustrated in Section 5.1.2 to justify the proposed framework since, by Table MPcomp is reduced from MvU.
Step 1: Corrected Loss Design and Risk Rewrite.
The following corollary combines (86) and (87) to achieve rewrite L7 in Section 2.2.7
Corollary 26. For Peomp learning, the classification risk can be rewrillen
R(g) Essu [ksup] + Bine [Cnnt]
where
Esap lp Tpla: li = -T + ln
(96)
Step 2:
Recovering the previous result(s).
It is straightforward to recover Theorem of Feng et al, 2021 by matching notation R Since x a variable and can be substituted by x', we express Corollary 26 as
R(g)= EgwPsup ((((a) Tp (x)] + P (Cn(x') mnlp(x'),,
(97)
recovering (5) of Feng et al. (2021).
5.1.5
(SDU) Learning
We justify the applicability of the proposed framework for DU and SD separately. Firstly, we start with DU learning, which is similar to SU learning in the sense that pairwise information provided. From we see that the pairwise distributions are treated similarly. Thus, following the same steps conduct the risk rewrite for DU learning.
Lemmas 5 and 7
in Section 5.1.3
Step 1: Corrected Loss Design and Risk Rewrite for DU Learning. The following corollary is variant of Corollary 23
Corollary 27. Assume up # 1/2. For DU learning, the classification risk can be rewritten
R(g) = ED [ + Eu [Lu]
where
8 = 2Tp
pp
en
kn
Tp
n
up
tv =
Ep
(98)
nu
7p
mn
Tp
Step 2: Recovering the previous result(s) for DU Learning.
We reuse the trick in Lemma for restoring the pairwise distribution Ps to restore Pp needed here, allowing us to recover the rewrite (15) in Theorem of (hhiadaa et al. (2021) and the first result Theorem 7.3 of Sugiyama et al. (2022). The derivation resembles that of SU learning. We start with the next lemma,
adapted from Lemma 24
Lemma 28. Given B
46 and following the DU learning notations, we have
(PB
Mby B
P.
Pu
8Te matching fallows: Psup B+ (x), Pint fh- (x), Eo ((f())) +1), and b, {(((), -1).
38

---

Published in Transactions on Machine Learning Research (01/2025)
where
[Lvex Pa dz'
Seex Pe'ix-yaar
Mbu =
2
Tp
nn
We apply Lemma 28 to slightly revise the derivation of
89 as follows:
[ dr
[ I. MuubuBe Bdr
R(g)
1esx(e (Eb Re)
Swee Paivende
Leex Porr
P2ll== dx Palyy=n)
Ap
Jee J'EE
/ Polidd' do +
Pu Pulude
ZEX
ED [cb] Eu [eu],
where the second to last equality follows from the DU formulation
12
Denoting
(X)
Tp
(X)
Tn
en (X),
(99)
Tp
recalling ((X) from
93 and continuing with 98
we have
ED [p]]
2m ED
lp
ln
Fu Tp
Tn
Tp
2m mn F.D
-[(X)]
(a)
((X) + L(X')
2np xu ED
and
Eu [u]] = Eu
Tp
6p +
Tn
ln
Tn
Tp
Eu (X)]
(100)
that prove rewrite 13 in Section 2.2.5
By matching notations, we recover (15) in Theorem
Shimada
al. 2021
Equality (a) follows from the next lemma.
Lemma 29. Let (z,x²) PD defined in 12). Then, EDD
[(X)
EDD
C(X") 2
Secondly, we consider the rewrite of SD learning. To do so, we apply the knowledge acquired from SU and DU learning (Corollaries 23 and
Step 1: Corrected Loss Design and Risk Rewrite for SD Learning. We provide another variant of Corollary 23 to conduct the risk rewrite.
Corollary 30. Assume Tp + 1/2. For SD learning, the classification risk can be rewrillen as
R(g) Eg [63] + EB [&p],
where
( Tn)
Tp
lp
E
Tpp
Tp
Tn
2mp
n
Ra lp
+
Tp
lu
(101)
Top
Tp
Tu
9Te matching to the notations of Shimada et al. ps(x,r"); Pp (2(),²)) Po (x),, Ep E(((
2001 is as follows: Tp is T+, Ta is m_, x3 #2 ma. mm mp. Ps
+1), {(f()), -1), ((X) is (((()), (- is C((X), +1), and
(X) is (((())-1)
39

---

Published in Transactions on Machine Learning Research (01/2025)
Step 2: Recovering the previous result(s) for SD Learning.
We apply the same strategy as in Lemma 28 to obtain the needed Ps and PD- We begin with the next lemma, adapted from Lemma 24 to recover (16) in Theorem of Shimada et al. (002 and the second result in Theorem 7.3 of Sugiyama et al. [2022).
Lemma 31. Given B
46 and following the SD learning notations, we have
Ps
MSD =
= P.
PD
where
T Fexx P dal
2 Barex Pari "D am
7pt Seic Porrande de'
MaD ==
Sacex Prrvand
We apply Lemma 31 to slightly revise the derivation of as follows:
89
[
R(g)
I. Pdr
T. M.S
da
FEX
JOEX
Sarex Peiv=pde " *f+TR
S. Pary " +
Jeex
(Gg PD)
(Pal Pajy-
dæ
Jere Pa'
Serex Pelr-paal 2
2
J. I J
Ps Eg dx'dx
PD En dr'de
JEX J'EX
Es [
+ EED (nll
where the second to last equality follows from the SD formulation 94h and continuing with (101).
14
Recalling C+ (X) 99
and L- (X)
Es [Eg]
(Tp 2 Es
Tp
Ep
En
TT
Wn
Tp
(mg
Es
(X))
(X) + (X')
(n m
Eg
and
Ep [65]
2n.
Tp
Lp
Tp
Tn
Tp
2T
[X)]
C (x) (X')
TT ED
2
prove rewrite 15 in Section 2.2.6 We also recover (16) in Thcorem of Shimada al. 20221) via matching notations. The required matches can be found in the paragraph before Lemma 29 The equality (b) holds
by applying Lemma 25 with ((X) replaced by (X)),, and (c) follows from Lemma 29 with C(X) replaced
by (X).
An intriguing observation worth mentioning is that the losses L, (X) and (x) applied to decontaminate the unlabeled data in SU and DU learning (15) and (100 are now used to decontaminate the similar and the dissimilar data SD learning, respectively. One can also quickly draw the same conclusion from Table 4 Knowing the reason behind this observation would help to transfer one corrected loss developed in scenario to another weakly supervised scenario.
40

---

Published in Transactions on Machine Learning Research (01/2025)
5.1.6 Similarity-Coffidence (Sconf) Learning
Since Msconf (55 is not child of Muu 49 on the reduction graph, a direct application of Theorem 21 is infeasible. Nevertheless, we demonstrate how our framework applied to rewrite the classification risk for Sconf learning. We make small adjustment to the framework that instead of showing L L M M L P, show that for loss vector L with certain property.
FEX J.EX P L Mscont
(102)
The idea behind this approach to accommodate z' sampled from Px (18). Suppose, informally, we have the equation above. Then, the right-hand side of (102) will produce P we can compute a dccontamination matrix M satisfying Scont Mscont and assign L == -. -MMM Scont- Lastly, integrating over x on both sides, we obtain the key equation
J P
/ JZEX
Jwex
L dr
for risk rewrite.
Step 1: Corrected Loss Design and Risk Rewrite.
Let us follow the notations in Section 4.1.6] We begin with technical lemmas and leave their proofs Appendix D.1. The first technical lemma shows how to achieve (102..
Lemma 32. Assume the formulation P = Mscont B (58) is given. Suppose vector of corrected losses L of the form (z) Ea(t)) is independent of x'. Then, we have
S. L dx' L Mssont
(103)
where
x P2'P1 P.P
T. PPP P 2'11 da'
Se.
da
So.
Mscout
r-
P Paijn
2
Sx. P.P - P dr
da'
T
The second technical lemma computes the decontamination matrix. Lemma 33. Let
M
nn
Scont
0
Tp T
Tp Ti
Then,
M Mccon Mscont
Next, follow the sketch above to instantiate the corrected losses
L T===1 L Mi
ep(x)
Tp To- Tpp Tp- Tn
(a(x))
Sennf
Kp Ap-mt no
Putting M Mooon:: L, and 103 together, have the following rewrite.
Theorem 34. Assume up # 1/2. The classificntion risk of Sconf learning can be expressed by
r Tn (X) + Tp - en(x))
R(g) = Ex,x'
(104)
TTp
Tp n
41

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. Integrating both sides of 103 over and applying Lemma 33
obtain
JrEx /
P dr'de = J. L Mssont P dr
JEEX JEE
S I. M-
Scout Mscont P dx R(g).
and P with (PxPx PxPxx
On the other hand, substituting I. with
Tp nn Lx(x))
mp-
J 2'EX
/
L dr'dx
JSEX J'EX
PaP
r- Tn lp(x) +
Tp Lu(x)
dx dx
mpp
nn
Tp Tp
Ex,x'
r- nn
Ep (X)
+
Tp en (X)
Tp - Tn
"p
kn
completes the proof of the theorem.
Step 2: Recovering the previous result(s).
From the above derivation, we have achieved the first half of the rewrite in rephrased as
19 Notice that
56 can be
r- --
PxPx = (m2Px P Px + (T -xpppp Px
Tp
and that 57 can be rephrased as
Up --rr
PxPx = (T. x2Px)p) Px + (T/Pxip - P Px
nn
Thus, when Tp * 1/2, repeat the proof steps in Lemma to rephrase 58
STp (n (m Pximm
Np - 1
PxPx PxPx:
(Pxil
r-
Tu (1 P pxix)
me Pxip P(
Px
Bp
Comparing the equation above with P = Mscout B, we see that it is still feasible to formulate P with X and X' in MSeonf and B of 58 swapped. Then, repeating the same argument in Step with x and x' swapped, we obtain
R(g) = Ex
r Ta
(p(X')
T.p - (x
(105)
Up Tn
Tn
Therefore, the following combines
104 and 105 to obtain
R(g) = 1 (R(g)= + R(g))
2
= Ex.x'
r Tn (x(X)
+
Tp -
(x(X)
+ Ex,x
r- lp(X') +
Tp -
En (X')
2
Ap nT
Tp
2
Tp Tn
Tp n
r nn (X) (x()
Tp r (x(X) +
(x')))
= Ex,x'
Tp
2
Tp mn
2
that recovers rewrite
19
Section
2.2.8
By matching notations, we recover Theorem of Cao et al.
(2021b) 10
10 matching the notations of Cao al. (x(X) f(g(X),-) -1).
2021b follows: up w.. ma n-, r 8, Ep(X) is E(g(X), +1). and
42

---

Published in Transactions on Machine Learning Research (01/2025)
5.2 CCN Scenarios
The proposed Iramework is now applied to conduct the risk rewrites for WSLs discussed in Section 4.2 and summarized in Table Counterintuttively we demonstrate that finding an inverse matrix (e.g., Proposi- tion 1 is not the only way to solve the risk rewrite problem. Introduced in Proposition 2 the new technique exploited in this subsection, marginal chain, calculates the decontamination matrix for 37 via applying the conditional probability formula twice during a chain of matrix multiplications.
5.2.1 Generalized CCN
We justify the proposed framework for genoralized CCN learning via the following steps. Derived equations will be applied to solve the risk rewrite problem for WSLs discussed in Section
Step Corrected Loss Design.
Let us follow the notations in Section 4.2.1 Same what have illustrated in the beginning of Section 5.1.1
the proposed framework achieves three milestones to rewrite the risk. We apply Lemma 10 to achieve the first milestone, P = M.CeN P. This is done by noting that for generalized CCN, P = MgceN B and B = P
are given by Lemma 10 (i.e., do not need to handle Must discussed in Section 3.2 matrix when B P)-
since Must is the identily
The second milestone is to find M CCN to achieve Mt M P = P. Since MgCON
64 is identical to M (40
a direct application of Proposition 2 gives the decontamination matrix
Py=1ss=n,
Py=
Py=
Py=
Py=
Py P
M 8CON
(106)
Py=K|S=S Py=K|S=m,x
Py=
that satisfies the McCONP= requirement.
The final milestone is achieved by instantiating the corrected loss (38 as L = LTM 5CCN. We denote the k-th entry of I e with [K] and the j-th entry of L. Es=sy with j E [[S]].
Despile Proposition simplicity, the construction of M MyCON is somewhad. surprising. M to our best knowledge, contributes to a first loss correction result relaxing the invertibility constraint. Unlike M (Corollary 200, which needs to compute inverse matrix, one can construct M MyceN by calculating each entry Pr|s.x (066, to which, we point out a systematic way in Section 5.2.2
Step 2: Classification Risk Rewrite.
With L in hand, the following theorem provides an intermediate form risk rowrite.
Theorem 35. Let P and P are given by 62 and ITP-ITP and
633) respectively. Denote L = LM Then,
R(g) = / Pdr / L Pdx.
(107)
Proof. Since M is given by Proposition M MCCoN P. Thus, following the framework (39 have 7 T L M M T implying 107
Theorem 35 will be applied to derive the respective rewrites for WSLs discussed in Section 4.2 in the rest of this subsection. In particular, we explain how to realize Mt gOCN 106 for a given CCN scenario. Then, the risk rewrite (107) automatically carries over for the scenario considered, and the respective L specifies the corrected losses in the rewrite.
43

---

Published in Transactions on Machine Learning Research (01/2025)
5.2.2 Proper Partial-Label (PPL) Learning
M MyceN provides abstraction for us to construct the corrected losses L. Nexl, we focus on deriving the actual form of Py|s,x in Mt MyceN 1106 to explicitly express ls for PPL.
Step 1: Corrected Loss Design and Risk Rewrite.
Let us follow the notations Section 4.2.2 The following lemma specifics the form of Pr|s,x instantiate
M M RCON
Lemma 36. MPTL corresponds to realizing M McCN
1066) with
gCON
Py yy= (Y = iE
(108)
Eoes, Pr=
Proof. Recall that the decontamination matrix of MgcCN 64) is MccCN (066) and MpPL is a reduction of MgCON via PsJy, = C(S S] (65). Thus, find out the (i,j) entry of M need find out
the form of P subject to 65
Applying Theorem 1 Wu et al.
2023 directly gives
Py PY
S
Eoes, Pr=a|x
which completes the proof. For completeness, we provide a derivation as follows.
Note that PSJY.x C(S E
65
implies
Σ Ps,y=bjx
Σ
Ps Pay=
BE
bEV'S
= Σ
C(s [b E S) Py
bEy's
= 0.
Therefore, Psix Eaes
EaesPs Ps,Y=ulX + EvErS Ps, EoEs Ps,Y=alx.
Utilizing this fact, we obtain
PY|S.X = PssYIx
PSsIixPYix
Psxx
Eoes Ps PY=
C(S,X)I( E Py
Enes C(S,X)I a SJ PY=a|x
Py E S]
ELES PY=alx
that finishes the proof for Theorem of Wu et al.
2023
We have shown that MePL is derived from M MOCNN- Thus, we can follow Theorem
35 to construct the
corrected losses using (108) and obtain the risk rewrite (27) for PPL in Section 2.2.12
Corollary 37. Given MPPL defined by (105), we denote the corrected losses L = L MMMpL- Then, for
PPL learning, the classification risk can be rewrillen as
R(g) Es,x [ts]
where
L Σ Py=ix ly Eneg Prmaax
(109)
44

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. Given 108), the j-th entry of L is of the form
Py Py-ixx = =iE sp
{s=a, (L MMMp),
Σ
PY=
Encoy PY=alx
Prmijx Bx=
ZOEZ;
PY=a|X
SE8,
Then, since MPPL is a realization of Mi
SCCN according to Lemma 36 we contimee 107
to express the risk
88
R(g) -f Pdx
[8|
P P Es.x [$s]
JZEX
JEEX
j=1
Step 2:
Recovering the previous result(s).
We finish this part by pointing out Corollary 37 recovers Theorem of Wu et al. (2023
5.2.3 Provably Consistent Partial-Label (PCPL) Learning
It is fairly straightforward to apply the proposed framework to rewrite the classification risk. However, it is more involved in recovering the existing result.
Step 1: Corrected Loss Design and Risk Rewrite.
The argument for obtaining the risk rewrite for PCPI. is similar to that of PPL. From Section 4.2.3 we know that PCPL is special case of PPL that only differs in the choice of X). Since C(S.X) ) is independent of (108), MPcpr, and MPPL are identical. Hence, following the notations in Section 4.2.3 and repeating the proof of Corollary 37, we obtain the risk rewrite for PCPL:
Corollary 38. The decontamination matrir MFCPL for PCPL equals MPPL- If we define the corrected losses L = L MMCCLI the classification risk for PCPL learning be rewritten
R(g) Es,x [ts]
where
is Σ Pr=ix ly=i.
(110)
Eoes Pr=olx
Step Recovering the previous result(s).
In order recover (8) Feng al. (2020b), we need reorganize the sum in (10) by leveraging a unique property of pair of partial-labels (s, s') that complement each other. The following technical lemma states the required property, with proof deferred to Appendix D.2
Lemma 39. Let s') be pair of partial-labels satisfying s = Vlss' Then,
Py=ixxl==
Ps-axts=s + Pssss Ps
Encs Py=o|X
1=1
Denote 8f = 1/ for every 83 E S. Then, Lemina
39
implies
[s]
[S]
2P xPs=,,xls=s, Σ
Σ
(Ss= + Ps=ofxxls=s) j=1
[s]
Py-jixly=
Σ
Ps Ps=zyi
X
Enes, Py=aix
45

---

Published in Transactions on Machine Learning Research (01/2025)
Hence, continuing from Corollary 38
Es [(s] =
JOEN
Ps Ps 8 s=., dr
i=1
[5|
K
Pyziobyzi dr
Ps Psmapa
ZEN
8
LaEsy Py=alo
Py=ilx
Es,x
Σ
by
EaEs Py=alx
shows that the rewrite from the framework recovers recover (8) of Feng al. (2020b
25 in Section 2.2.11
By matching notations, we also
5.2.4 Multi-CompeenentryyLbbell (MCL) Learning
Step 1: Corrected Loss Design and Risk Rewrite.
Let follow the notations in Section 4.2.4 As discussed in Scction 4.2.4
MCL is special case of PPL.
Thus, we can modify Lemma 36 based on the notations in Section 4.2.4 to construct the decontamination
matrix M MCL for MCL. Then, following the same steps for proving Corollary 37 we instantiate L. to conduct the risk rewrite for MCL:
Corollary 40. The (i,j) entry of the decontamination matriz M of the form
Py=i|S=8,,X Py x
(111)
Eags, Pr=a|x
Define the corrected losses L.T T. T.M MCL. Then, for MCL learning, the classification risk be rewrillen
R(g) Es,x [ts]
where
Eg Σ PY=iX lyzi. Logs Prmaax
(112)
Step 2: Recovering the previous result(s).
Although legitimate, the risk rewrite (112) following the marginal chain approach appears different. from Theorem of Feng al. (2020a), which we resort the inversion approach (Proposition [ that finds another decontamination matrix, termed MMLL to recover. As preparation step, we denote Na the nunber of mulli--ommlleeennlay-bbbee with size d and group rows of MMCL 71 by the size of labels follows.
P|
22
MMCL
(113)
P
The matching the notations Feng al. (020b) is follows: Ps.x Y), PY-ij ply d1x)) and Ey is
())
46

---

Published in Transactions on Machine Learning Research (01/2025)
where for d E [K 1], each block is of the form 12
I I = 1 $ sa.1]
T = & 84,1]
T = K & &a.1]
I 1 Sa,21
[ = 2 E 8a,2
I = K & 5d222
Ma ))
(114)
[[Y 1 Sd,Nal
I[ $ Na,Nel
I[ K & Nd.
To maintain the equality P = MMCLP established in Lemma 13 we also rearrange P 69
(PS=nni N
Ps PS= t. -.-PEEX-INN-II>))
(115)
As sanity check, we see that for any d' E [K 1] and jr E [Na),
Σ [[ $ S
P|3--0' (K-1)
K-1
Σ
Pla
|y.xI[|aayy== d]
(K-1)
Y
P3=sa
(116)
The next lemma is crucial for us to devise the deconlamination matrix MCL via the inversion approach. We defer its proof to the later part of this sub-subsection.
Lemma 41. Let i y be fired. Then, for every d E [K -K-1. 1].
K -
i (5-=5aa Ps X118|=d
PY
1
d
Moreover, the inverse malria -J² of Ma
114 is of the form
I = 1 84,1]
1 d
5d,2]
1 d K- E sa,N.]
k = 2 sa.1]
1 d
K = 2 E 5x22
1 K kA,N.)
(117)
1 I K E 3r1
1- K = K E 54.2]
1 K-l = K E 8aNN
Applying the lemma, we construct
MMCL [Mi² M₂²
Mx-1)
(118)
and obtain MMOr. P- = P since P = MMCLP
116 and
K-1
K-1 Σ d=1
M MMCL.
Σ d=1
Ma
Pi M
Ma
Pis
m-=== =1
We remark that MT plays the same role as M realized by matrices (designed to convert P back to P and used to construct the corrected losses L). Distinct symbols
111 as they both are decontamination
12Comparing to (1 where we use one index to denote total [S] partial-labels, MA uses a pair of indices and to denote
the j-th partial-lahel with size d. easy verify that K Na KK-1 (K-1) 2 2 (S).
47

---

Published in Transactions on Machine Learning Research (01/2025)
are merely used to reflect the difference that MaCL results from the marginal chain method while MMCL comes from the inversion approach. Then, applying the framework 38 L T, J.MM.. leads to
UP=L'MMNLL P.
With the corrected losses L hand, the following theorem provides the risk rewrite inversion approach and recovers Theorem 3 of Feng et al. (2020a)
23 for MCL via the
Theorem 42. For MCL learning, the classification rish can be expressed as follows.
K-1
R(g) E [65l
Σ
1 13)
where
K - 1
fg = Σ
Cy=i
8
|S|
8E8
Proof. We first establish
R(g)
I Pdx
=gg,x [E5)
Jx
since T-p=LT where P specified in 115 and L
L M with the S-th entry being Eg. Also, Thus, decomposing the probability by the size
recall that Ps,x = Dd=1 P sx Section 4.2.4 of 8, have
K-1
E s.x
[Es]
Σ
PI [s)
d=1
Lastly, M MCL
118 and M
117 imply, when S= Fd.j:
fg= = (T =
Σ Er=i 1 K d
my my= i ka.s)
Σ
K
Ey=
K-1
Σ
ly=i-
d
1=1
iEFo,
A simple reorganization and substituting with |S] shows
K
K
|
f== 1==(y= Ey + Σ
EY=i
ty=
Σ
ly=i
Σ
fy=
|8|
[$|
iES
iE8
18
i
Now we return to the postponed proof.
We start with identifying M Denote (B.,1...., Ba,N,,, the set of multi- complementary-labess of size d, as Sa. Let us focus on the sized-d data-generating distribution
Proof. of Lemma 41
P X
Pa
P X|
13e matching notations Ex(f(x)) f).
Feng et 2020a is as follows: P3,x1181dd is p(x, 8/s d), Pig-d p(s = d), and Eg
48

---

Published in Transactions on Machine Learning Research (01/2025)
Note that Pa corresponds to extracting the entries from 115) that generate sized-d data and then dividing them by P(5]=d- Thus, P = MMCLL P in Lemma 13 implies Pa MaP and its j-th entry is expressed as
P X1SI--
Σ
1[ =i sagl Py=ix
(119)
(K-1
The equality hints to us that if one manages to collect certain multi-complementtr--abeeee s' to form an = C3 Py=ix for some constant C3, then a reciprocal operation recovers Py=i,X we need (recall we want find M achieving ' Pa P). To achieve such goal, we fix on class i* and collect elements in S& that do not contain i' to form E = {Baylāa. Sa, 1" & Sa,j) to connect Ps.Xi|ss=d with P as follows. Summing (119) over all elements E we oblain
equation resembling Σx Px
K 1[
Σ Ps X = REEU
Σ REER
K-1
==1
K 2 d
( 1K-1) P
P Py= +
K-1 d
The last equality holds since there are KK- mutti-compleeentary--baall s Sg such that i # i and neither of them is in (i.e., $ 8 and it $ 8), and there (K=²) mulli-complenenttar--bbbbbb 3 Sa such that = i" and is not in 5. Then, we regroup the sums by pulling Px out of (K Px=')r to combine with (k-3) Σ Py=i,x It leads to
Σ P PS= REE!
1 (K-1)
(
K K
Py Pr=ix
(K-2) Py P
d-1
K-
Px K-1 Pv=r.x
(120)
K-1
Denoting S = {Ra.j Bai E it E sash as Iy and rearranging terms in the above equation according to the reciprocal idea illustrated above, we have
K-1
K K-1-d
Pymix
Σ REEF
PS=E,X||S
Px
(121)
d
K-1
K
Px
Σ
P P
K - 1 Px
BEI!"
K -
Px
Σ SET
P PS
Equality (a) holds since ( and X are independent Feng et al. 2020a), which implies
Px Px]iSi=d Σ P
Σ
P
P P
BES,
BEEr
SE2
Continuing the derivation, we have
N₂
Na
K
PY=P.
Σ
P S=
Σ
TV = Eas P
j=1
1=1
Σ
1| - = saall
K --1
P P3=
(122)
49

---

Published in Transactions on Machine Learning Research (01/2025)
proving the first part of the lemma.
The derivation of turning 120) to [11 is a reciprocal action. Thus, if we view 1 1- - = E sa.)
the [] entry of some matrix M', (122) be interpreted P.- = (M'P)), suggesting Ma 1 since Pa MaP. We formalize this intuition in the next lemma.
Lemma 43. Let M' be of the form 117 and recall Ma is defined by 114 Then, M' I, meaning
M' M
The above lemma finishes the proof of Lemma
Let d be fixed. Denoted by Ai,s, the (i, k) entry of M' is the inner product of i-th row of M' 117 and the k-th column of Ma [114]
Proof. of Lemma 43
A
Σ
K -
IlV = =
(K-1)
I[ k Bayl
Σ
N₂
Gik-
In the following, we will show that the calculation results in the identity matrix
1, if
A 0, ili
to complete the proof.
When i i k, we have 4 possible cases: (i) Both i and h are in sd.. (ii) Both of them are not in Sd.j. (iii) E 8d.j and h & Baj, and (iv) & Bag and & E Saz- For cases (i) and (iv), the coefficients Ci are 0 since [k & [a,] 0 if & E Saj. For case (ii), the coefficient Ci is T. The number of such Baj is (kx²)) since we are counting the ways of forming set of size d from K 2 elements. For case (iii), the coefficient C is (1 (1- ) - The number of such sd.j is (#-1) since we are counting the ways of forming a set of size d d from 2 elements. Thus, i # hi;
K K-2)
+ 1
-
K
K-2) d -
Ai,
K
d
(KT
K 2
(-
(=((3-))
d
d-1
d-1 =0
K
-K
(K7))
d
since
(K 2 d
K -
d d = -KK=))
-
-
K -2
+
d
d d-1
When i = k, we have 2 possible cases: (i) Both i and &s are in Sd,j (ii) Both are not in 8d.j- For case (i), the cocfficient Gs is O. For case (ii), the cocfficient Cr, is (* and the number of such 8d, is (K-1), as we want to form a set of size d from K - candidates. Therefore, if i = hi
1 K K-1 =1
A K- (
We want claborate more on the role of Thcorem of Wu et al. (2023) in the analyses discussed Section 5.2 Firstly, as shown in the proof of Lemma
41 it aids the execution of the inversion approach
(Proposition 1. The properness C(S, X)II |Y S) 65 be instantiated define the entries of M, 114
50

---

Published in Transactions on Machine Learning Research (01/2025)
which in turn establishes the key equation (100) enabling to identify the entries of M
122 Composing
MJ², we obtain MMLL crucial element. lor applying our framework 38
Secondly, Theorem 1 of Wu et al.
20023 contributes to the marginal chain approach (Proposition 2 as
well. The key equations 108 and 1111 realised from Theorem of Wu et al. (2023) provide the entries
of Mppr. (Lemmna 36 Section 5.2.2) MPCPI (Section 5.2.3), and Mr (Section 5.2.4 when applying (38
Therefore, the combined advantage of our framework and Theorem of Wu et al. 2023 provides CCN
scenarios unified analyses whose key steps can also be rationally interpreted. Moreover, as will be shown
later, we compare the marginal chain and the inversion approaches via a CL example in Section 5.2.5 CT.
example the simplest way to convey the differences between the two methods without burying the essence in complicated derivations.
5.2.5 Complementary-Label (CL) Learning
Step Corrected Loss Design and Risk Rewrite.
Note that the parameters chosen for the construction of McL
76 in Section 4.2.5 reduces MMCL 113 to
be M1 of 114h. That is, assigning P(š)=d 1 for d = 1, P Pis
for > 1, and $1,5 {i} for all [K]
in 113
have
0 1
1
1 0
1
MMCL M1
.MM.-
K
Hence, the proof steps of Theorem
42
carry over to CL learning. With a simple rearranging on
K
Σ
ly=
S
iES
8ES
K
8y=i
8y=
|S|
1=1
#ES
and assigning |S| = 1, we arrive at 21 Corollary For CL learning, the classification risk can expressed
R(g) E Egx
[2
Es,
Σ tY (K - 1)eg
Step 2: Recovering the previous result(s). The rewrite above recovers Theorem ofIshida et al. (019) we substitute with and lg with (()).
Moreover, if we choose d 1 and $1 =o} for all [K], the decontamination matrix provided by [177 becomes
(K -
-(K 2)
1
M
(123)
:
1
- -(K -
which translates the corrected losses L L M as
LT (-(K 2) + +111,
recovering (9) of Ishida et al. 2019
51

---

Published in Transactions on Machine Learning Research (01/2025)
Comparing inversion with marginal chain via example.
We use a simple CT. example to demonstrate the differences between the inversion (Proposition and the marginal chain (Proposition 2 approaches and explain how the intuition of decontamination is implemented. Here, we focus on comparing how a decontamination matrix M achieves Moor P = P (37) since when the equality is established, the downstream construction of the corrected losses and the risk rewrite follow the framework. For this example, let us choose K and simplify Py= as Pk- Applying (66 the contamination process defining the data-generating distributions is expressed as
Pa +P
0
1
P1
3
pi +p
P Mc
0
P2
3
1
1
0
P3
P1 +p
3
1
1
0/
P4
21 PP
Equation
123
simplified from
117
provides the dccontamination matrix from the inversion approach:
2
1
1
2
1
M CT.
1
2 1
Then, the inversion approach (Proposition achieves the docontamination
37
by showing
2
1
0
P1
MGIP
1
2
1
1 0
P2
(124)
1
1
-2
1
1
1
0
Pa
1
2
1
1
1
0/
Pa
3
0
0
P1
P1
0
P.
0
P3
P3
3
P4
P4
On the other hand, equation 111
produces the decontamination matrix from the marginal chain approach:
0-p1
P1 Pi PP
Pa Ps
P1+72 +
P1+P2 +Pa
P2
D-p2
P2
P2
M
Po PatPatai
Pi +
Pg
O.pg
PstrstPs
P1 +Ps
Prtpitpi
P1+P2+P3
P4
P4
Pi P
Pi P1 +:4
Pi P1
52

---

Published in Transactions on Machine Learning Research (01/2025)
Then, the marginal chain approach (Proposition
2
achieves the decontamination
37 by showing
P1
P1
P1
Pa
P2
P1+Pa+77
P1+
3
O-p2
Pi PP
Ma. P
Pa Pattat
P1 PP
P1
P4
Pt P2 PP
3
(125)
Pg
Pa
P 3
Pa+
PP+
P2 P2
Pi P
P4
P4
94
0-P4
Ps
pa
Pp
P2
Ps
putp:
P1
P2
P2
P.
2a patatts
P3
p4 +24
P1
we see that the intuition of decontamination realized differently. The inversion approach [144] directly cancels out the effect of Mearr without relying any property of P. In contrast, the marginal chain method 125 leverages the fact that P is probability vector and carries out procedure similar to importance reweighting to resolve the contamination. Both methods have respective merits, and we hope the comparison will inspire new thoughts leveraging certain properties of P for the corrected loss design and the study of decontamination.
Comparing (24) and 125
5.3
Confidence-based Scenarios
The proposed framework is now applied to conduct the risk rewrites for WSLs discussed in Section 4.3 and summarized in Table g
5.3.1 Subset Confidence (Sub-Conf) Learning
Step 1: Corrected Loss Design and Risk Rewrite.
Let us follow the notations in Section 4.3.1 Recall that Lemma by showing P Ms To reach the second milestone (37). we apply Proposition to construct the decontamination matrix M to cancel out the contamination ion caused by MSub 80) as follows.
16 has reached the first milestone 36
Lemma 45. Assume PYEvIX > 0 for all possible oulcomes of X. Choosing
PY=ix
Previx
Maab == M
(126)
PY=Kix Pycouix
0
we have M P= P, where P and Ms P are given by Lemma 16
Proof. The assumption PyeMIX implies Msab is invertible. As suggested by Proposition I
we define
Mg. = Ma Then,
PrzII Pyc
Presux Py-
0
0
M Mgn..Muu
0
PY=KIX Previx
Pyevax P
implies Mt. p= M5-1 Msub P P= P that proves the lemma.
53

---

Published in Transactions on Machine Learning Research (01/2025)
With M in hand, the next theorem defines the corrected losses L and achieves the risk rewrite (31 Theorem 46. For Sub-Conf learning, the classification risk can written as
(x) l
R(g) = .yy EXIYER
(x)
Proof. Given Lemma 45
can define L == L MSub that
PY=iI l I L M&MM),,, Prexix
for each E [K] and
TP=L'M Mub P.P.
Therefore, we can apply 39
to obtain 31 as follows.
K Py=iXx 44 -reE, PxIvex,dz
R(g) = [
JEEX
L Pdd
Jxex
L Pdx
ZEN 1=1 Previx
PY=iX ly PYExIX
PXIEEEXIYEM,
(X)
Ty, TxIEEY
Σ
ly
Ty (X)
The last equality follows the notations in Section 2.2.14
Step 2: Recovering the previous result(s).
Notation matching gives
K
r ( r x
R(g) = -Ty, (((alee
((((x),))
recovering Theorem of Cao et al. 202 la 14
5.3.2 Single-Class Confidence (SC-Conf) Learning
Step 1:
Corrected Loss Design and Risk Rewrite.
The SC-Conf derivation resembles that in Section 5.3. since Msc is child of Msub on the reduction graph. Thus, following the notations in Section 4.3.2
assuming Py=wIx > for all possible outcomes of X, and
replacing the set 34 in M 126 with singleton ya, have
Pysux Py=mIx
0
Mt
PY=KIX Py=mix
satisfying M P. We also obtain L L McC and -TP= LTP by inheriting the proof of Lemma
Then, a modification to Theorem 46 by replacing L! Presix
Py l, with
TTT = (L (LTMML (LTT)))
Pr=ijx ls (x( PY
Typ (X) 4
proves the risk rewrite 29 for SC-Couf learning:
14e matching follows: Pxires, p(rly E 16), rx(X) is r'(X), (X) is (X), and ())(X),
54

---

Published in Transactions on Machine Learning Research (01/2025)
Corollary 47. For Conf learning, the classification risk can be written
K
(x(
R(g) = Ty. E
li
Ny X
Step Recovering the previous result(s).
By matching notations, we obtain
K
(x)
R(g) Tyy (p(elua)
((((2))
plhe (x)
recovering Theorem of Cao et al.
22221a]
5.3.3 Positive-confddene (Pconf) Learning
Step 1: Corrected Loss Design and Risk Rewrite.
Let follow the notations in Section 4.3.3 Recall that Mreonf child of Msc the reduction graph
with K = 2 and Vs p. Thus, assuming Py=plx 0 for all possible outcomes of X and replacing K and in Section 5.3.2 accordingly, we obtain the decontamination matrix
Py=pix Py-plx
()
M Poon ==
1-r(x) r(x)
Py=nix Py-pix
and the rewrite reviewed in Section 2.2.2
Corollary 48. For Peonf learning, the classification risk can be written as
R(g) Bp ( + 1- 1-r(X) En
r(X)
Step Recovering the previous result(s). By matching notations, we obtain
R(g) = E4 ((o(z)) + 1- r(x) 1(x(2)
E( -((x))
r(x)
recovering Theorem of Ishida et al. 2018 16
5.3.4 Soft-Label Learning
Step 1: Corrected Loss Design and Risk Rewrite.
We follow the notations in Section 4.3.4 As discussed in Section 4.3.4 Mson is a special case of Msub
when V/ = [K] Thus, reducing Mgab 126 by assigning Pyexux Pye[klix 1, we obtain the the dccontamination matrix
Py-
M
Soft
0
PY=KIX
Then, we follow the same argument Theorem 46 to achieve the rewrite
34 by the next corollary.
Corollary 49. For soft-labed learning, the classification risk be wrillen
K
R(g) = Ex
Σ Py = Ex Σ
1=1
18eThe matching ls follows: Px|Y= is p(>1(u)) rx( is (X),, ruu (X) is (X),), and e, la (()
16e matching is follows: Sp is n., Px p p(x// +1), Py-plx r(x), Py rrx)), Ep B(g(z)), and tn is f( ((-g(z)).
55

---

Published in Transactions on Machine Learning Research (01/2025)
Step 2: Recovering the previous result(s).
Ishida et al. (2023) did not focus on the classification risk rewrite problem. We can modify Corollary 49 to provide a risk rewrite for binary soft-label learning mentioned by lshida et al. (2023). Taking K = 2, we have
R(g)= = Ex [Pr=pix& + P = Ex (x()) + (1 r())),)
6
New Risk Rewrites
The proposed framework can be applied to derive risk rewrites for new scenarios. In this section, we show how the proposed framework accommodates a different performance metric and adapts to a noisy environment.
6.1 The Balanced Error Rate
In the previous sections, we chose the most common metric, the classification risk, to elaborate our framework. Here, we demonstrate that the framework adapts to another common but different performance metric. The balanced error rate (BER) is defined as
REER (g) = Ex [4((((x))) + Ex [x(e()))
(127)
2
(Soot Zhang 2020). Next, we show how apply the framework to obtain the risk rewrite of UU learning under BER.
("00
(1/Tp
0
Recall that in Section 5.1.1 for classification risk, Murt =
was chosen to link the base
1//Tn/
P
PPY=piX
distributions B
and the risk-defining distributions P
PxxY==/
Pr
(XXI==)) Pxx
Pr=pi
1/Tn//
Py=ui
PxxY=p/22
By definition (177), the risk-defining distributions become
Since the base distributions B
PxxY
(2 0
remain unchanged, we must redefine Must =
0 2 so that
PX
2 0)
Pxxix=p/2
PxIY=n
Px|r=n/2
satisfies B Mtrtr for the BER setting.
2 0 in hand, we can follow Step 1 in Section 5.1.1 to obtain the
With the newly defined Mins =
0 2
data-generating process
Puu PU2
(2
0)
Px|x=p/2
Muu
0 2
PxiY=n/2
1/2
Then, by assigning M
Myl and following the similar derivation in the proof of achieve the risk rewrite for UU learning under BER:
1/2
Theorem 21
RBER (g) Bv, [?v,] Eu, [Fv.]]
56

---

Published in Transactions on Machine Learning Research (01/2025)
where
1 72
-72
2p +
En
2(1 - 71 72)
2(1 72)
LC2
-11
Lp
1 1-
Ln.
2(1 - 71 72)
2(1 71 - 722)
6.2 Learning with Label Noise
In this section, we show that the framework can casily handle the risk rewrite under label noise. We will take PU learning The scenario is formulated as follows. According to Lemma 4 the data-generating process of the noisy PU learning is of the form
example. We P to denote the clean distributions and Q for the noisy ones.
Qp. Qw
(XIX'=P)
2x1x'
where = Qy' and m/= =n We choose the MCD setting (Section 2.2.17 to formulate the label noise:
@xIx'=p) QxIx
1 app
o
PXXY==) PXI
d
1 1
where af 2 and a 2 are parameters describing the degree of noise perturbation. As in the previous soction, also choose BER as the performance metric.
By cascading matrices, the framework effortlessly links the dala-generating distributions and the risk-defining distributions:
@p.
1 df 0
of 1-
(o 2)
Px|x=p/2
Qui
PxIY=u/22
Knowing the contamination process, we apply the inversion method (Proposition lamination matrix
to construct the decon-
112
1/2 0
- 0/1
-ap
) a/)
MPU BER
1/2
1 0s 0
d'1
-
1/TT/
(1- (1-0( + to
o
2(1 2(1-a6 o
2[1 21100 1 of
C1
c0)
C2
1-06
Ca
21--6--0-
2-ー -
Then, applying equations
38 and
39
we can rewrite the BER for PU learning as
R ABEn(g)
Ex- [1r]] Ex- [Qv]
where
Ep = cipp + czhn,
tvr = c2lp + cgkn-
In the two subsoctions above, we have shown that the proposed framework can address risk rewrite under a different performance metric and a complex system. In the outlook part of the next section, we will further discuss the patential of the framework.
57

---

Published in Transactions on Machine Learning Research (01/2025)
7 Conclusion and Outlook
We set out. with the questions wishing determine if there is common way to interpret the formation of weak supervision and search for generie treatment to solve WSL, to understand the essence of WSL. In response, proposed a framework that unifies the formulations and analyses of set of WSL scenarios to provide a common ground to connect, compare, and understand various weakly-superrised signals. The for- mulation component of the proposed framework, viewing WSL from a contamination perspective, associates a WSL tata-aenn process with a base distribution vector multiplied by contamination matrix. By instantiating the contamination matrices of WSLs, we revealed comprehensive reduction graph, Figure [I] connecting existing WSLs. Each vertex contains a contamination matrix and the section index of the WSL scenario which the matrix characterizes. Each edge represents the reduction relation of two WSLs. We can see three major branches from the abstract Meorr, corresponding to Tables 7 and Section 4 The analysis component of the proposed framework, tackling the problem from a decontamina- tion viewpoint, working with the technical building blocks Theorems [ and constitute a generic treatment to solve the risk rewrite problem. Section discussed in depth how the analysis component conducts risk rewrite and recovers existing results for WSL.s
discussed in
Mpu (50) Sec. 2.2.1
MDU (53) Sec. 2.2.5
Muu (49)
Msu (51) Sec. 2.2.4
Sec. 2.2.3
MSD (54)
MMCD (45) Sec. 2.2.17
M Mpcomp (52)
Sec. 2.2.6
Sec. 2.2.7
M Msconf (55) Sec. 2.2.8
Mcorr (35)
MPCPL (68) Sce. 2.2.11
M MgcCN (64)
MpPL (66) Sec. 2.2.12
Sec. 4.2.1
MMCL. (71) Sec. 2.2.10
MCI. (76)
MCCN (60) Sec. 2.2.17
Sec. 2.2.9
Msc (81) Sec. 2.2.13
M MPconf (82) Sec. 2.2.2
Msub (80)
Sec. 2.2.14
Msoft (84)
Sec. 2.2.15
Figure 1: Depicting the reduction map from Tables 7 and 9
The application of the proposed framework results in set of theorems. We summarize them in Table 10 The Formulation column consists of the results of the formulation component 35 The Decontamination
38 and (39)). The Recovery column justifies the framework by recovering results from the literature. Crucial results are marked red. Since the analyses of different scenarios are subsumed under a single framework, we now have basis for transferring technique developed for one scenario another. In addition, these alternative proofs provide different ways of dissecting the risk, which turn could aid in the development of a training objective by examining multiple risk decomposition approaches.
and the Corrected losses columns correspond to the results of the analysis component (137
58

---

Published in Transactions on Machine Learning Research (01/2025)
Table 10:
Theorem Structure.
Model
Formulation (Find M p MB.)
Decontamination
Corrected losses (Rewrite via
Recovery
(Find M s.t.
P M P.)
L
M and P.)
Abstract
35
37
38
and 39
model
Proposition
and Proposition
MCD
UU
Lemma
Corollary 20
Thcorem
21
(Notation swap.)
PU
Lemma
(Immediate reduction.) )
Corollary
22
(Notation swap.
SU
Lemma
(Immodiate reduction.
Corollary
23
Lemmas 24 and
Peomp
Lemma
(Immediate reduction.)
Corollary
26
(Notation swap,
DU
Lemma
(Immediate reduction.
Corollary
27
Lemmas
28 and 29
SD
Lemma
(Immediate reduction.
Corollary
30
Lemma 31
Sconf
Lemma
Lemmas 32 and 33
Theorem
(Notation swap.)
CCN
gCCN
Lemma
106
and Proposition Lemma Corollary
Theorem
35
(Notation swap.)
PPL
Lemma
36
Corollary
37
(Notation swap.)
PCPL
Lemma
12
38
Corollary
38
Lemma 39
MCL
Lemma
13
Corollary
40
Corollary 40
Theorem 42
Temmas 41 and
43
CL
Lemma
(Immediate reduction.)
Corollary 44
(Notation swap.)
Sub-Conf
Lemma
16
Lemma 45
Theorem
46
(Notation swap.)
SC-Conf
Lemma
17
(Immediate reduction.)
Corollary
47
(Notation swap.)
Pconf
Lemma
1
(Immediate reduction.)
Corollary
48
(Notation swap.)
Soft
Lemma
(Immediate reduction.)
Corollary
49
(N/A.)
The proposed framework abstract and flexible; hence, we would like to discuss potential from the following aspects. Firstly, the performance measure focused on in this paper is the classification risk. With proper choices of P and L, our framework can be extended other performance metrics, such as the balanced
error rate, one- mee-eeruus-ret risk, and cost-sensitive measures (Rifkin & Klautau, 2004 Zhang 2004 Brodersen
et al. 2010 du Plessis et al. 2014 Menon et. al. 2015 Blanchard et al.) 2016 Natarajan et al. 2017 Scott
& Zhang 2020 We have demonstrated the applicability of the proposed framework for the balanced eтror
rate in Section 6 Secondly, we can explore the formulation capability by exploiting the power of matrix operations. Cascading matrices allow us to formulate complex scenarios, such as data containing preference relations collected a noisy environment. Matrix addition allows us categorize different contamination mechanisms into cases to capture the structural properties of problem. A complicated scenario could undergo sophisticated formulation procedure, but once have the resulting contamination matrix, the problem boils down to calculating the corresponding decontamination matrix. Thirdly, the MCD scenarios discussed in this paper (Sections 4.1 and 5.1p belong to binary classification. A way of extending an MCD formulation to multiclass classification is lo extend MMaD (45) from a 2 x 2 matrix to K x K one, in which K2 K mixture rates are used to characterize the extended MgMCD: the (i,j) entry Yi if A and Ei Ti. for the i-th entry on the diagonal. Fourthly, the label-flipping probabilitics Pyly Natarajan et al. (2017) and Feng et al. (2020b) assume that the contaminated label Y is independent of X condition on the ture label Y. The formulation matrices, MceN (60) and MgCCN (64). in contrast, take X into consideration. This formulation enables us to tackle the instance-dependent problem (Berthon el al. 2021 and the effect of sampling strategies such as SAR and SCAR (Elkan Noto 2008 Coudray et al, 2023) in the future. Fifthly, we hope that the analysis technique developed in Section 5.2, which combines marginal chain and properness, opens up new possibility search for invertibility-fre methods for the risk rewrite problem. We also project its potential in research regarding the broader sense of contamination
59

---

Published in Transactions on Machine Learning Research (01/2025)
and decontamination. Sixthly, the properness of Wu et al. 2023) provides efficient technique to compute PyJs,x needed in MgCeN T06b. It. would be intriguing to know if there are any other alternatives. Finally but not least, the proposed framework operating under matrix multiplication belongs to broader question of under what cireumstances does a function f exist with = if P
Acknowledgments
The authors were supported by the Institute for Al and Beyond, UTokyo. The first author would like to thank Professor Takashi Ishida (UTokyo) for valuable insights and discussions in extending the coverage of the framework, and the colleagues Xin-Qiang Cai, Masahiro Negishi, Wei Wang, and Yivan Zhang (in alphabetical order) for comments in improving the manuscript.
References
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. In Proceedings of the 35th International Conference on Machine Learning, 1CML 2018, pp. 461 470, Stockholmsmässan, Stockholm, Sweden, 2018.
Antonin Berthon, Bo Han, Gang Niu, Tongliang Liu, and Masashi Sugiyama. Confidence scores make dependet label-noise learning possible. In Proceedings of the 38th International Conference on Machine Learning, ICML, 2021, Virtual Event, pp. 825-836 2021.
Gilles Blanchard and Clayton Scott. Decontamination of mutually contaminated models. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, pp. 1 9, Reykjavik, Iceland, 2014.
Gilles Blanchard, Marek Flaska, Gregory Handy, Sara Pozzi, and Clayton Scott. Classification with asym- metric label noise: Consistency and maximal denoising. Electronic Journal of Statistics, (0(2):2780-28))
2016.
Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M. Buhmann. The balanced accuracy and its posterior distribution. In 20th International Conference on Pattern Recognition, ICPR 2010, pp. 3121 3124, Istanbul, Turkey, 2010.
Yuzhon Cao, Lei Feng, Senlin Shu, Yitian Xu, Bo An, Gang Niu, and Masashi Sugiyama. Multi-class classification from single-class data with confidences. CoRR, abs/2106.088644, 2021a. URL https:// arriv.orr/abs///106
Yuzhou Cao, Lei Feng, Yitian Xu, Bo An, Gang Niu, and Masashi Sugiyama. Learning from similarity- confidence data. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, Virtual Event, pp. 1272 1282, 2021b.
Nontawat Charoenphakdes, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for learning from corrupted labels. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, pp. 961-970, 2019.
Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classification with re- jection based on cost-sensitive classification. In Proceedings of 38th International Conference on Machine Learning, ICML 2021, Virtual Event, pp. 1507-1517, 2021.
Yu-Ting Chou, Gang Niu, Hsuan-Tien Lin, and Masashi Sugiyama. Unbiased risk estimators can mislead: A case study of learning with complementary labels. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, Virtual Event, pp. 1929-1938, 2020.
Jesús Cid-Suciro. Proper losses for learning from partial labels. In Advances Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012, pp. 1574-1582, Lake Tahoe, Nevada, USA, 2012.
60

---

Published in Transactions on Machine Learning Research (01/2025)
Olivier Coudray, Christine Keribin, Pascal Massart, and Patrick Pamphile. Risk bounds for positive- unlabeled learning under the selected at random assumplion. Journal of Machine Learning Research, URL httph:httt/mmltet httpp//rrr/pappr/////222220000
24:107:1- 14:10711-107:31, 2023.
html
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning 1111//1..5555199900001
Research, 12:1501-1536, 2011. URL https::/ddt acm.
Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Clustering unclustered data: Unsu- pervised binary labeling of two datasets having different class balances. In Proceedings of Conference Technologies and Applications of Artificial Intelligence, TAAI 2013, pp. 1-6, Taipei, Taiwan, 2013.
Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In Advances in Neural Information Processing Systems 27: Annual Conference on Newral Information Processing Systems 2014, pp. 703-711, Montréal, Québec, Canada, 2014.
Marthimus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In Proceedings of the 32nd International Conference on Machine Learning, JCML 2015, pp. 1386 1394, Lille, France, 2015.
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 213-220, Las Vegas, Nevada, USA, 2008.
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Tearning with multiple complementary labels. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, Virtual Event, pp. 3072 3081, 2020a.
Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consis- tent partial-label learning. In Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, Virtual Event, 2020b. URL https:// Abstract.
proceedings. httpr///...pppc/////////////aaaa
Lei Feng, Senlin Shu, Nan Lu, Bo Han, Miao Xu, Gang Niu, Bo An, and Masashi Sugiyama. Pointwise binary classification with pairwise confidence comparisons. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, Virtual Event, pp. 3252 3262, 2021.
Jacob Goldberger and Ehud Ben-Reuven. Training deep neural-networks using a noise adaptation layer. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, Conference Track Proceedings, Toulon, France, 2017. URL
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W. Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems 31: Arnual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, pp. 8536 8546, Montréal, Québec, Canada, 2018
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Pro- cessing Systems 2017, pp. 5639 5639-5649, Long Beach, California, USA, 2017.
Takashi Ishida, Gang Niu, and Masashi Sugiyama. Binary classification from positive-confidence data. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, pp- 5921-5932. Montréal, Québec, Canada, 2018.
Takashi Ishida, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. Complementary-label learning for arbitrary losses and models. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, pp. 2971 19800, Long Beach, California, USA, 2019.
61

---

Published in Transactions on Machine Learning Research (01/2025)
Takashi Ishida, Ikko Yamane, Nontawat Charoenphakdee, Gang Niu, and Masashi Sugiyama. Is the perfor- mance of my deep ner too good to be true? A direct approach to estimating the bayes error in binary classification. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, 2023. URL httpps///peenrevier wttp:/oooooooddddd/app......
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data-driven curriculum for very deep neural networks corrupted labels. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018, pp. 2309-2316 Stockholmsmässan, Stockholm, Sweden, 2018.
Yasuhiro Katsura and Masato Uchida. Bridging ordinary-label learning and complementary-labdl learning. In Proceedings of The 12th Asian Conference on Machine Learning, ACML 2020, pp. 161 176, Bangkok, Thailand, 2020.
Julian Katzela Gilles Blanchard, and Clayton Scott. Decontamination of mutual contamination mod- els. Journal of Machine Learning Research, 20:41:1 41:57, 2019. URL http://jmlr. httpjjiwr.rrgggpeeeee org/papers/v20.
17-576.html
Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positive-ullaeledd Icarn- ing with non-negative risk estimator. In Advunces in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp. 1675-1685, Long Beach, California, USA, 2017.
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. On the minimal supervision for train- ing any binary classifier from only unlabeled data. In 7th International Conference on Learning Rep- resentations, ICLR 2019, New Orleans, Louisiana, USA, New Orleans, Louisiana, USA, 2019. URL rett/forumm/66-BLxxeoooo
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised elassification from two unlabeled datasets: A consistent risk correction approach. In The 23rd International Conference on Arlificial Intelligence and Slalislics, AISTATS 2020, Online Evend, pp. 1115 1125, 2020. URL http: / //proceedings. mlr. wttp:peee//////11..c..ooo html.
Nan Lu, Shida Lei, Gang Niu, Issei Sato, and Masashi Sugiyama. Binary classification from multiple unlabeled datasets via surrogate set classification. In Proccedings of the 38th International Conference on Machine Learning, ICML 2021, Virtual Event, pp. 7134-7144, 2021. URL httpp://proceedings mlr.
press/viss gress/v139/lu211 htmm
Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. In Proceedings of the 37th International Conference on Mochine Learning, ICML 2020, Virtual Event, pp. 6500 6510, 2020.
Xingjun Ma, Yisen Wang, Michael E. Houle, Shuo Zhou, Sarah M. Erfani, Shu-Tao Xia, Sudanthi N. R. Wijewickrema, and James Bailey. Dimensionality-drive learning with noisy labels. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, pp. 3361-33701 Stockholmsmässan, Stockholm, Sweden, 2018
Aditya Krishna Menon, Brendan van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from cor- rupted binary labels via probabrobabylity estimation. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, pp. 125-134, Lille, France, 2015.
Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013, pp. 1196-1204, Lake Tahoc, Nevada, USA, 2013.
Nagarajan Natarajan, Inderjit S. Dhillon, Pradcop Ravikumar, and Ambuj Tewari. Cost-sensitive learning with noisy labels. Journal of Machine Learning Research, 18:155:1-155:8: 2017. URL httpp://jmlr org/ papers/v18/15- htmm html
62

---

Consistency Published in Transactions on Machine Learning Research (01/2025)
Masahiro Negishi. Pairwise-constraint classification in weakly supervised machine learning: Risk-consistent
approach and classifierconnsistent approach. Senior thesis, 2023.
Gang Niu, Marthinus Christoffel du Plessis, Tomoya Sakai, Yao Ma, and Masashi Sugiyama. Theoretical comparisons of positive-unlabeled learning against positive-negative learning, In Advances in Neural In- formation Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain, 2016.
Рp.
Curtis G. Northcutt, Tailin Wu, and Isaac L. Chuang, Learning with confident examples: Rank pruning for robust classification with noisy labels. In Proceedings of the Thirty- Thind Conference on Uncertainty in Ar- lificial Intelligence, UAI I 2017, Sydney, Australia, 2017. URL http:://uali http:///aaa..orr//aaa020//ppoood papers/35.poe pdf
Curtis G. Northcutt, Lu Jiang, and Isaac L. Chuang. Confident learning: Estimating uncortainty in datasct labels. Journal of Arlificial Intelligence Research, 70:1373 1411, 2021.
Giorgio Patrini, Alessandro Rozza, Adilya Krishna Menon, Richard Nock, and Lishen Qu. Making deep neural networks robust to label noise: A loss correction approach. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, pp. 2233-2241, Honolulu, Hawaii, USA, 2017.
Scott E. Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabi- novich. Training deep neural networks on noisy labels with bootstrapping. In 3rd International Conference on Learning Representations, ICLR 2015, Workshop Track Proceedings, San Diego, California, USA, 2015. URL http:://axxi..org/bbba
6596
Ryan M. Rilkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of Machine Learning Research, 5:101-141, 2004. URL htttp:////hlll..oo///pppptt///ts
Tomoya Sakai, Gang Niu, and Masashi Sugiyama. Semi-supervised AUC optimization based on positive- unlabeled learning. Machine Learning, 107(4):767 794, 2018.
Emanuele Sansone, Francesco G. B. De Natale, and Zhi-Hua Zhou. Efficient training for positive unlabeled learning. IEEE transactions on pattern analysis and machine intelligence, 41(11):2584-25) 2019.
Clayton Scott and Jianxin Zhang. Learning from multiple corrupted sources, with application to learning from label proportions. ColR,, abs/1910 Abs//191000465, 2019. URL http:://arraiv..rrr/b////00....
Clayton Scott and Jianxin Zhang. Learning from label proportions: A mutual contamination framework. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information
Processing Systems 2020, NewrIPS 2020, Virtual Event, 2020. URL https: https::/prooceeddggs... www.:eeeddnnng............ nwwrips. html
Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: and maximal denoising. In COLT 2013 The 26th Annual Conference Learning Theory, pp. 489-511, Princeton University, New Jersey, USA, 2013.
Takuya Shimada, Han Bao, Issei Sato, and Masashi Sugiyama. Classification from pairwise similari- ties/d dissimilatis and unlabeled data via empirical risk minimization. Neural Computation, 33(5::2234 1268, 2021.
Masashi Sugiyama, Han Bao, Takashi Ishida, Nan Lu, Tomoya Sakai, and Gang Niu. Machine Learning from Weak Supervision: An Empirical Risk Minimization Approach. Adaptive Computation and Machine Learning series. MIT Press, 2022. ISBN 9780262047074.
Sainbayar Sukhbaatar and Rob Fergus. Learning from noisy labels with deep neural networks. In 3rd International Conference on Learning Representations, ICLR 2015, Workshop Track Proceedings, San Diego, California, USA, 2015. URL http:://arsw...rgabbb/////
63

---

Published in Transactions on Machine Learning Research (01/2025)
Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization framework for learning with noisy labels. In 2018 IEFE Conference on Computer Vision and Paltern Recognilion, CVPR 2018, pp. 5552 5560, Salt Lake City, Utah, USA, 2018.
Ambuj Tewari and Peter L. Bartlett. Chapter 14 learning theory. In Academic Press Library in Signal Processing: Volume 1, pp. 775-816. Elsevier, 2014. doi: 00014-0.
Brendan van Rooyen and Robert C. Williamson. Learning in the presence of corruption. CoRR, abs/1504.00091, 2015. URL http://arxiv wtt.or//bb//54400000000
Brendan van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18:228:1 1-228:1-228:50, 2017. URL http://jmlr. http://iiw.rrrrpppppe///////////
html
Qian-Wei Wang, Yu-Feng Li, and Zui-Hua Zhou. Partial label learning with unlabeled data. In Proceedings of the svvntyyEigghtl International Joint Conference on Artificial Intelligence, IJCAI 2019, pp. 3755 3761, Macao, China, 2019.
Zhenguo Wu, Jiaqi Lv, and Masashi Sugiyama. Learning with proper partial labels. Neural Computation, 35(1):58 81, 2023. URL https: : org/10. 10. 1162//ecooooooee __tooo______ 01554
Xingrui Yu, Bo Han, Jiangehao Yao, Gang Niu, Ivor W. Tsang, and Masashi Sugiyama. How does disagree- ment help generalization against label corruption? In Proceedings of the 36th International Conference on Machine Learning, TCML 2019, pp. 7164-7173, Long Beach, California, USA, 2019.
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. Computer Vision ECCV 2018 15th Europeon Conference, Munich, Germany, Proceedings, Part I, pp. 69 69-85, 2018.
Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5:1225-1251, 2004. URL http://www..rr//ppparr///oo////a zhang04b.. pdf)
Zhi-Hua Zhou. A brief introduction to weakly supervised learning. National science review, 5(1):44-5) 53, 2018
64

---

use cases as Published in Transactions on Machine Learning Research (01/2025)
A Use Cases for This Paper
There are several ways to use this paper in the study of WSLs. We provide some common follows:
Use Case 1: you want a quick overview of WSL. Reading Section would provide a quick catch-up on the formulations and results of various WSL scenarios.
Use Case 2: you want to get the high-level idea of this paper. One could start with Section 3 which provides the abstract form of the proposed framework. Then, Sections 4.1.1 and 5.1.1 give the practical application of the framework to UU lcarning. If you are more familiar with PU learning, then are welcome to proceed to Sections 4.1.2 and 5.1.1 to see how our framework interprets PU learning. In addition, these reading steps will reveal the connection between UU and PU.
Use Case 3: you want know how to apply the framework to a specific scenario. One could read Sections 4.a.b and 5.a.b at the same time, and come back to the rest of Sections 4 and 5 only needed. Note that "a.b" represents the index of subsubsection.
Use Case 4: If you want to know the connections discovered and the analysis techniques developed in this paper. Section 4 provides detailed discussions of the formulations, and Figure Figure[summarizes summarizess the relationship. Section 5 provides detailed explanations of how our framework is applied to rewrite the classification risk.
The extensive analyses from Section are summarized in Table 10
B
Notations
Table 11: Notations and Aliases.
Name of the notation
Expression
Aliases
Convention
Example
(y,4)
(x,
Binary classes
{p.
{+1,-1}
Multiple classes
f1,...,K)
[K]
Compound classes of [K]
2 (0, [{]}
S
A subset of classes
V/. C [K]
Joint distribution
Pr(Y v, X =x)
Py=gas Py=y,x or Py,x
Pr(x,y)
Class prior
Pr(Y = y)
Tyy
Marginal
Pr(X)
Px
conditonniii
Pr(X Y 1))
Paly: Pxly, Pz|Y= or Pxir=y
Class probability
Pr(Y = y/ X x))
Py=glus Py=y|x or Pyix (x(X), ry rz(2,, or r(X) y =p
π(x))
Confidence
Pr(Y y X 2))
(x) or r(x)
Sample size probability
Pr([S| d)
Pisi=d 4isl
Hypothesis and its space
gEg
Loss
(g=n(g(x))
by, (x(X), or by (g(X))
((g(X),
Classification risk
Ey.x (g()))
R(g)
Ex,y (e(g(X),, Y)]
The j-th entry of vector V
(V),
V,
Indicator function of E
[[E]
Complement of set s
V's
Identity matrix
MCD paramcters
Yp and %n
UU parameters
m1 and
1 O and 0'
CCN parameters
PrIY.
PSIY. or PsIx.
P+ and p-
65

---

Published in Transactions on Machine Learning Research (01/2025)
C Omitted Proofs in Section 4
Omitted proofs in Section f are provided in this appendix. We first restate claim in the main body of the paper, and then provide the corresponding proof.
C.1 Omitted Proofs in Section 4.1
Proof of Lemma 5
Lemma 5. Let B 40 be the base distrituatios and
Ps Pu
P =
Then, the contamination matrix
mp 43+x3
Msu
(51)
Wn
which satisfies P B, characterizes the Sata-generating distributions P.
Proof.
The proof steps follow that of Lemma
By definitions,
PXIX=P PxlY=n
Msu
*
+
Tp
nn
Since
ap
Px + T TTPXY== =Ps
2
P P
P P
7 +
m
mp +
+ m
and
Tp P + T. PX Px Pu.
the first entry of the resulting vector equals Ps and the second entry equals Pu, we achieve P = MsuB. 0
Proof of Lemma 6
Lemma 6. Let 46 be the base distributions and
Psup
P =
Pint
Then, the contamination matris
Tp tp
MPcomp =
(52)
22
p
22
which satisfies P MPcomp B, characterizes the dala-generating distributions P.
66

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. By definitions,
7pt
Up R
P
MPcomp
mp
Px|M=n
Fp
"p + nn
Since
Tp +
Tp x Y=p PXIV= PSuup
Px
Px|==p
P Px
Kp + nn
Tp + nn
Tp + T
and
2 Px Px|r=p+
P
+
Tn Px Px
" X
Px
=p
+ Tn TrPXI
Pinf
mp Au
Tp + nn
Tp nu
the first entry of the resulting vector equals Psup and the second entry of the resulting vector equals Pinf: which establishes MPcomp B P.
Proof of Lemma 7
Lemma 7. Let B 46 be the base distributions and
PD PU
=
Then, the contamination matriz
1/2
1/2
MDU-
(53)
Tp
Tn
which salisfies P MDu B, characterizes the dala-generating distributions P.
Proof. Similar to the proofs of Lemmas and
we begin with
MpUB = 1/2 1/2 Tp
(XxI==
Pxxy==n
nn
Since (PxiY=p + /2 -2-Pp and Tp TxpxXy=p + T. Tn Pxjr=n
Px Pu, have Mpu B P.
Proof of Lemma 8
Lemma 8. Let 4. the base distributions and
Ps PD
P
Then, the contamination matriz
MSD
(54)
1/2
1/2
which satisfies P = Ms characterizes the data gentt-ggnnratingg distributions P.
Proof. First, we begin with
PxXI==)
MSD
PxlY=u
1/2
1/2
Then, have the lemma by reusing the calculations in the proofs of Lemmas and
5
7
67

---

Published in Transactions on Machine Learning Research (01/2025)
C.2 Omitted Proofs in Section 4.2
Proof of Lemma 11
Lemma 11. Let the elements in S be {81, S/11. For each j [[S]], let the j-th entry of P be
Pj P C(S= x) Σ PY=k,x,
kER;
which denotes the data- data-generating distribution of [s,, X). Assume the base distributions B and the con- tamination matriz MpPL are given by 63 and 660, respectively. Then, MpPL satisfies P MpPL and chamelerizes PPL learning 26
Proof. For each j E [[S]],
(MrrI.), Σ
= P C(sj,
Σ PY P3. kEa,
k=1
Note that C(s,, X) EKEr, PY=k,x corresponds to 26 when the observed partial-label is 8j-
Proof of Lemma 12
Lemma 12. Let the elements in S be {81,82, 81,..) For each j E [[8]], let the j-th entry of P be
P P
PY=R,x kEa
2K-1
which denotes the data-generating distribution of (8), X). Assume the base distributions B and the contam- ination matrix MpCPL are given by (33) and 68), respectively. Then, MPCPL satisfies P MMCPL B and
characterizes PCPL learning 24
Proof. For each j E [[S]],
K
(MPcFI.B) = Σ km
I = k E s,l =
1
Σ REE;
Py=k.x Py.
2K-1
2k-1 -
Note that 2x EkEO, Py=k. corresponds to 24 when the obscrved partial-label is 8j.
Proof of lemma 13
Lemma 13. Suppose the base. distributions B. the contamination matrir MMCL, and the data-generating
distributions P are given by 63
71 and 700), respectively. Then, MaCL satisfies MMCLB B and
chamacterizss MCL
92
68

---

Published in Transactions on Machine Learning Research (01/2025)
Proof. For each [M], we have
11
(MMCLL))
[Y $ syl Pr.
|8y1
Ed=1
11 [
dj P13 I Y & 8n) Pr.x
(--1
1831
i=d
I [ 3,] Py [|3 d
|8,1
Pla Playl=z I=d (K-1)
Σ Py.xI [|,,] | d
18,1
Y48,
P S=
D Omitted Proofs in Section 5
Omitted proofs in Section S are provided in this appendix. We first restate a claim in the main body of the paper, and then provide the corresponding proof.
D.1 Omitted Proofs in Section 5.1
Proof of Corollary 22
Corollary 22. For PU learning, the classification risk can be rewritten as
R(g) lEp [pp Ey [Zu].
(90)
where
E. = Tplp Tphn fU = l.
(91)
Proof. According to Table 7 Mpu is a child of Muu on the reduction graph. Thus, replacing the subscripts {U1, U2} of P and L with (P, U} and assigning 7i and 722 = Яp as what we choose in Section 4.1.2
we follow the proof of Theorem 21 to conduct the risk rewrite: We first obtain the corrected losses 91 by
plugging the assigned values into 186) Then, repcating the steps in 88 we achieve 190
Proof of Corollary 23
Corollary 23. Assume Tp # 1/2. For SU learning, the classification risk can be rewritten as
R(g) Eg [C]] + Eu [&u]
where
Ap
2 + nr
+ F
2
fg
lp
2Tp 1 Ln
2mp
1
(92)
2 =
nn
lp
+
up
ln
2T, -
2mp
Proof. By Table 7 Msu is a child of MVc. Substituting the subscripts (U1, U2} with subscripts (Š, U} and choosing 71 = = = and 7/2 = Tp as we did in Section 4.1.3 we obtain the corrected losses (92) by plugging the assigned values into (8 We note that n. + 1/2 ensures the choices of ?1 and 12 above satisfy the
71 + 7/2 # assumption discussed in Section 4.1.1 Then, we achieve the rewrite R(g) Eg [&g] + Eu [uu
by repeating the derivation for 89
69

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Lemma 25
Lemma 25. Let (x, Ps defined by 10
Then, Es
L(X)
-Es
C(X')
2
Proof. For clarily, we simplify Ps as c1 xxxxx +02 PXI = Px with The lemma follows from
=
and
02
m² xp 7,
Es [C(X)
= - JOEX J WEX
Psl(x) dx' dæ
= -I SSEX JOEXJRER D'E
((x) da' dr
=Q I Pa|x=pB((1) de
{ PolY=p de' + / Pa(x=a((x)) de f PolY=n da' N'EX
JEEX
JEE
= Px)x=p((z)) de + t / Pa)r=n(((x) dr,
BEX
ZEN
and similarly,
Es [[(x')] = / ParM-pf(z'' dr' +cs Parly-n((x') dæ'.
N'EN
x'EX
Proof of Corollary 26
Corollary 26. For Peomp learning, the classification risk can be rewritten as
R(g) = Esup [Lsup] + Eint [Cint],
where
Saup = Ep Tpla:
l - Tnl + ln
(96)
=2
Proof. Since Mue reduces to Mpcomp with 71 + the subscripts {U1, U2} with (Sup, Inf] and instantiate 86 with the assigned values to obtain the corrected losses lsup and linf (96). Then, repeating the same steps in (80). we have the corollary.
and 72 न.+ according to Table we replace
Proof of Corollary 27
Corollary 27. Assume Tp # 1/2. For DU learning, the classification risk can be rewritten as
R(g) EB (Tp] + Eu [Zu]
where
1
2mp un
fp
en
Ku
Tp
nu
up
Tp
lp
Wn
(98)
nn
up
mp
Tp
Proof. By Table 7 MDU reduced from Muu. Thus, replacing (U1, U2} with (D, U}, and assigning Y1 = 1/2 and 12 Tp. we obtain the corrected losses (98) by plugging the assigned values into (86) Note that
Tp * 1/2 implies that the 71 and 722 assignments are feasible. Then, repeating the steps we have the corollary.
70

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Lemma 28
Lemma 28. Given B
46 and following the DU learning nolations, we have
PD
Mbu =
P.
Pu
where
[eex Privende
Jaex Pari
Mbu- =
2
Tp
nn
Proof. Since Seex Pa'ly=ndz' = 1 and Ja'x Pa Pa'lY=ndr' = 1, we have Mau = MDC and hence M
PD
MbUB-
The last equality follows from Lemma
PU
Proof of Lemma 29
Lemma 29. Let (x,xx) PD defined in 12). Then, ED
[(X)
ED
((X')
2
Proof. Recall PD = (P P + Pe Following the similar argument in Lemma 25
[()
JEEX I (Paly=pP2/ + P
((x) 4
Ed
dæ' dz
2
FEE
/ (Pz|Y=p +
((x) dx
Pa|Y=u))
SEE
4
and
[(X')
/ (PolY=n + PaIYY=))
[(x')
ED
4 dr'
prove the lemma.
Proof of Lemma 30
Corollary 30. Assume Tp # 1/2. For SD learning, the classification risk can be rewritten as
R(g)
1Eg [1]] EB [bl
where
Eg (T
x
Tp
l
T 0
TT
Fn
Th
ED 2n
Ty
T f
(101)
Tp
Kp
Proof. By Table 7 MsD is reduced from Mvu. Thus, replacing {U1, U2} with (Š, D), and assigning x² and 72 1/2, we obtain the corrected losses 1011 by plugging the assigned values into 16). Note
that Tp # 1/2 implies that the 7n and f2 assignments are feasible. Then, repeating the steps in 89 we
have the corollary.
71

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Lemma 31
Lemma 31. Given B
46 and following the SD learning notations, we have
Ps
M/D
-P.
PD)
where
nhe meSvex Paiivnnd 33+03
MSD
Jaeex Po du'
Sarex Pr
2
Proof. Since SPEX Parl= = and Szex Pary=an 1, we have MDD MSD and hence M&D B
Ps
MSD
The last equality follows from Lemina
Pp.
Proof of Lemma 32
Lemma 32. Assume the formulation P = Mscont B (58) is given. Suppose vector of corrected losses L," of the form (z) E2(z)) independent of x'. Then, we have
S LTP dx' L L Mssont
(103)
JEX
where
[z.
P - P dx
Sr. x P.PP 2 dr
Msconf
Pulln P dx'
Se. spP P dr Fpp
ui
Proof. of Lemma 32 We replace P using P Mscont the integral over x' into Mscont to obtain
58
Since L. is independent of x',
( - P.P
Ep 7 Parp - PPPP)) -0
J Ld
J
IT
P-
(Pxp) dr Px
Fu P 2/ - P.P..
Fu (12 PrPP.lp n Pn
up
P 2 da
P P2 da'
Sgr
Sg.
TT PpPxIp Tn TnPxin
T
P- nm 2P 2.
2 P P dx
Se.
dr
To
up
TxPx
Since Txpx11 = Px,Y= and PxIx = Px,y=m
= P. Furthermore, comparing the equality
the above derivation with 103
we have
2P Pa - P a dr
[T. PPP 2 dr
Ser
M
2 Pa n n pe dr
Sr.
a3P - P. dr' Fp
that completes the proof.
72

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Lemma 33
Lemma 33. Lef
Meconf
up
Tp r
"p
Then,
Scont Mscont I.
Proof. We prove the lemma by examining each entry of Mr Mccnn Mscout- The value of (1, 1) entry is
T nn
Polp
P a
dx'
1
Parppd'' - z Pelada')
p xf
xp Tn x
"p
2 m
"p
1.
"p
Tn
The (, entry has value
Tp r
T
Palp
P
n. x
dx
1
2
P Øf
Parpde'' - = f Perude))
"p
Tp nu
x
"p
"p nn
2 π
"p
Tn
The (1, 2) entry is zero since Sar (T
T.. p) dx' = 0. Similarly, since S2. (T Palla TTp dx' = 0,
the (2, 1) entry is also zero.
D.2 Omitted Proofs in Section 5.2
Proof of Corollary 38
Corollary 38. The decontomination matrix M MECPL for PCPL equals MPPL If we define the corrected losses as L = L MPMPLI the classification risk for PCPL learning can be rewritten as
R(g) = Es.x [ts]
where
Ls Py=ii ly iES
(110)
Eoes PY=alx
Proof. The proof follows the standard argument: First, find out MPCPL then construct the corrected losses to rewrite the risk.
Note that the only difference C(S, X) between the formulations of PCPL and PPL cancels itself out in the derivation of Py= (please refer to the proof of Lemma 36 for detailed derivation), the (i,j) entry of MFcri coincides with that of M for all i and j, proving the first assertion.
Since MPCPI, reduced from MpPL., we can exploit Lemina 36
Since MPPL and MPCPL are identical, L LTMPLL- = LT MPCPL gives 110
Pr-exI = i sy]
is=e, (LTMP))))
Σ
byzt
Enco, Pr=alx
i=1
Pymijx -lysi. lyzi.
Σ
Enco, PY=aix
iEs,
73

---

Published in Transactions on Machine Learning Research (01/2025)
Being identical to MPPL also means that MpCPL is derived from M goON Thus, can continue rewrite the risk by repeating the proof of Corollary 37
107 to
[s]
B(g)
Pdx
Ps S e,, dx Es,x [es]
2
XEX
jml
Proof of Lemma 39
Lemma 39. Let (s, 8') be a pair of partial-labels salisfying & = Vrss Then,
K Py=jxxly=
Ps-axes=s + Psas = Ps=s,
[=1 Laes Py=e|X
Proof. Given MPCPL
68
we apply P = BPCPL to obtain
K kk=l
I k
s
PY=
PS=
2K-1
We also have
Es=s'' Eieg Prsiixl== Eneo Pr=a|X
according to 110
Since
-==1 T[V = PY =Px Lk=1 T = k Py=kx Eaco Prmaax
5K
Exes: Prmaax
ΣK kk 1|Y = s Pr
Eier Pr-ixly= Eneo PY=alx
Ps=d
2k-1-1
Me 1[Y = ke PY=ki Eier Py=iixl== Enco Py=olx
K
2K-1
Thus,
Σ 11==1 = = Py Eie, Py= Eoes PY=
Pssmxxls=a Ps
2k-1 -1
K Ek=l 1|Y = Py Lier Py Pyzijxly=
2k-1-1
Enso Pr=olx
Eics Pr-jjxly= + E Pr=axly=
Ps=ax
Ener Py=olx
K Py-ijxly=i
= P
Enes Py=u|x
proves the lemma.
74

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Corollary 40
Corollary 40. The (1,3) entry of the deconlamiiation matrix MML of the form
Py=i(s=o,,X Py P
=
(111)
Eafz, Pr=alx
Define the corrected losses L = L. JMMMX Then, for MCL learning, the classification risk can be rewritten
R(g) -s, [ts)
where
L3 Σ PY=1X ly=i.
(112)
Lags Pv-a|x
FES
Proof. The proof follows the standard strategy in Section 5.2 We will first find out M and then construct the corrected losses I. to rewrite the risk.
Based on the notion in
71 denote the (j, entry of MMCL.
P
[[Y =
C(s,, = =i 5,] = PS=5, V=IXX.
(128)
K |8,1
Expressing MMCL via 128 allows us to apply the argument for 106 to show that the (i.j) entry of M is of the form Py Py=jSS= -= (i.e., Proposition we obtain
Specifically, assigning (M), 40)
as P Y and applying marginal chain
(M MMOLP)
Σ
M MMLCL)
(MMCL)j, Ps
i.j k=1
j=1
Σ Py P j=l
Ps x
PY=LX P..
Then, we follow the same argument in Lemma
36 to calculato Py= subject to
128 Note that
Ps|v.x C(S Y $ S] in 128 implies
Σ Psyy=Mj = Σ
X Pr=bix
beS
beS
Σ C(S Y b 8) Py be
0.
Thus, Psix Exes P3 + Eass PByy=alx Eogs P PB,y=alx The fact further implies
PsyYIx
P Py|s.x
Psix
Eags P Py=alx
C(S,X)I & Prix
Enes C(S,X)I Y = a & S Py=aIx
P $
Eags Py=alx
75

---

Published in Transactions on Machine Learning Research (01/2025)
Therefore, for Y and S = 8j. achieve
Pr=ixx_[Y= = syl
Py Py=(S==,,,X
Eagz, Pr
that proves
With M MaL hand, we repeat the same argument in Corollary 37 obtain
L 8== = (L (ben),,,,
Σ
K
Py Py=jx = syl
ty=
Eagz, Pr=alx
Py=ijx fy=
E
Engz, Prma|x
i88;
and
J Pd
R(g)
L M
MCL MMCL P da
JAEX
[S|
L. dr
P s= s=z, dr = Es,x ['l
JaeX
JEX j=1
to complete the risk rewrite of MCL.
D.3 Omitted Proofs in Section 5.3
Proof of Corollary 47
Corollary 47. For SC- Conf learning, the classification risk can be written as
K
(x)
R(g)= Ny, Ex
Σ
Ty X l
Proof. The corollary follows from notation substitution and the same argument for Theorem 46 replace Msuh with Msc, Y' with yss and Py l with Py-ex l,
Specifically,
Pyesix Py-mix"
Proof of Corollary 48
Corollary 48. For Pconf learning, the classification risk can be wrillen
r(X) ln
R(g) mp Ep ep +
r(x)
Proof. Since
Py-pix Pyspix
Px-pix Pyzpix
Mccnnt Myeonf
= I
Py-pix Pvenix
Pr Pv=pix
we define LT = T Moout and apply
39 to rewrite the risk as follows
B(g) = [ LT = LT Pdr
Jrex &p (
/
)
Prrppix dr
JAEX
Pr=pix
Ep + 1 1-r(X)
= Py-pEXIY=P
r(X) fn
= BppBp Ep 1- r(X)
en
r(X)
76

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Corollary 49
Corollary 49. For soft-label learning, the classification risk can written as
K
K
R(g) = Ex
Σ
Py-ipls
= Ex
Σ (x))
Proof. Defining LT L Mbon and recalling P
83
we apply 139
obtain
K
R(g) = I
Pd
L Pdx =
Σ
P Pr=ixli Pxdr
xEX
Jex
i=1
Ex
77


Reviews:
[{"review_id": "L73EBAMjy1", "reviewer": "Reviewer_DJLT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- The paper presents the first framework to show the connection between different WSL methods. This approach provides an insightful viewpoint to study different WSLs and understand the underlying mechanisms.\n- The developed framework is powerful and recovers existing results.\n\nWeakness:\n\n- The paper only considers the classification risk as the performance measure. As a comparison, existing methods consider various performance measures such as the balanced error rate, the receiver operating characteristic curve and the cost-sensitive measures.\n- It is not clear to me whether the proposed framework also implies new WSL methods that can outperform the existing WSL methods in terms of accuracy and scalability.\n- For multi-class classification problems, page 57 shows that one needs to compute a K by K matrix, and therefore it does not apply to problems with a large number of classes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a unified risk analysis for weakly supervised learning (WSL). The framework involves a formulation component and an analysis component. The former provides a unifying interpretation for WSL data generation process, and produces three reduction graphs to show the connection between different WSL formulations. The latter uses the decontamination concept to build a general method to conduct risk rewrites for different WSLs. The paper presents theoretical analysis to show that the risk rewrites in the framework recover existing results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper includes some proofs in the main text. To further improve the organization, it may be better to include all the proofs in the appendix.\n\nPage 7: it seems that the definition of $P_{sup}$ and $P_{inf}$ are the same as both $x$ and $x'$ play the same role. The authors should check it.\n\nPage 64： there are several missing periods at the end of equations\n\nPage 74: \"as follows.\" should be \"as follows\"", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "a7Poj6n5md", "reviewer": "Reviewer_NSQr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper provides a good review of existing WSL frameworks.\n\n2. The authors propose a unified framework for many formulations of WSL, which helps readers better understand that there is a common way to express WSL problems and solve them.\n\nWeaknesses:\n\n1. The main body of this paper is too heavy for readers to follow.\n\n2. The main techniques (matrix analysis, combinatorics, etc) used in this paper are quite standard. \n\n3. Although the authors provide a good way to interpret the formulation of WSL, it is unclear to the readers why/how it is important to the community from an empirical perspective.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies weakly supervised learning (WSL). The authors first provide a comprehensive review of many existing binary and multiclass formulations of WSL, and then on top of them they propose a general framework that can capture all different types of WSL, which is depicted in Figure 1.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to invite the authors to make some changes to the paper in the following aspects.\n\n1. (Weakness 1) The technical proofs of the lemmas and theorems can be simplified or moved to the appendix. Otherwise readers might find it difficult to follow the high-level idea of the paper.\n\n2. (Weakness 2) The motivating questions mentioned on page 2, such as \"can a unique interpretation be found to explain the mechanism\nbehind WSL\", as well as the main theoretical techniques used to address them make this paper more like a technical report rather than a journal paper. Could the authors provide more discussions on what insights the proposed framework or the techniques can bring to the community?\n\n3. (Weakness 3) Could the authors provide some discussions on how the proposed framework can make a difference in the machine learning community, from an empirical perspective?", "broader_impact_concerns": "No concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fWyLQCbFLe", "reviewer": "Reviewer_vtCp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The approach of viewing supervised problem formulation as a contamination process and problem analysis as a decontamination process is both novel and conceptually engaging.\n\n2. By providing a structure that covers various WSL settings, the framework supports researchers in analyzing different weak supervision scenarios under a consistent methodology.\n\n3. This framework could be useful in advancing empirical risk minimization across different weakly supervised contexts, potentially reducing the complexity of handling multiple WSL settings separately.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a unified framework for weakly supervised learning (WSL), utilizing a contamination-based perspective for constructing supervised problems and a decontamination approach for analysis. The framework aims to encompass diverse WSL scenarios under a single methodology, addressing both theoretical consistency and practical applications.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The paper introduces a substantial amount of notation and theoretical constructs early on, particularly in Section 3, without sufficiently defining key terms like the data-generating distribution, $P$ and $\\bar{P}$. This could make it difficult for readers to follow the framework. I recommend defining these concepts clearly and concisely at the start of Section 3 to improve readability.\n\n2. I suggest that the authors offer more specific guidance on potential future research directions. Rather than presenting this as just a general framework, I think it would be beneficial if the authors gave a few concrete paths forward for both theoretical analysis and practical applications in WSL. For instance, could this framework inspire new types of risk analysis or model improvements?\n\n3. The core idea of using a matrix to correct data labels aligns closely with the noise adaptation layer [R1] proposed by Goldberger et al., where a matrix is also used to modify class labels to handle noise. Could you clarify how your approach differs from or expands upon the noise adaptation layer?\n\n[R1] Jacob Goldberger and Ehud Ben-Reuven. Training deep neural-networks using a noise adaptation layer. ICLR, 2017.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a unifying framework for many weakly supervised learning scenarios such as Positive Labeled (PL) or Unlabeled-Unlabeled (UU) learning. The core idea is to associate each learning setting with a transformation matrix which transforms the 'vector' of class-wise distributions into the 'vector' of distributions associated with each partial labels. Whilst the paper is relatively long, the flow is reasonably natural. 

Whilst the truly new results for specific WSL settings in the present submission are limited to risk rewrites (which might explain why the reviewers unanimously oppose acceptance at the ICLR journal to conference track), I believe the unifying formulation introduced in this paper has the potential to become an established standard (which explains the unanimous decision to accept). Further down the road, this could help prove deeper results about and draw connections between various WSL settings and help positively shape the direction of future research. Overall, this is an excellent paper and contribution to the community. Thus, I am happy to recommend a survey certification in addition to the acceptance decision.
Decision: Accept (poster)