Statistical Analysis of an Adversarial Bayesian Weak Supervision Method
Authors: Steven An
Venue: NeurIPS 2025 poster ()
Keywords: weak supervision
bayesian
adversarial
convergence
consistency
Primary area: general_machine_learning
TL;DR: Convergence analysis and experiments of a new label model.

Abstract: Programmatic Weak Supervision (PWS) aims to reduce the cost of constructing large high quality labeled datasets often used in training modern machine learning models.  A major component of the PWS pipeline is the label model, which amalgamates predictions from multiple noisy weak supervision sources, i.e. labeling functions (LFs), to label datapoints.  While most label models are either probabilistic or adversarial, a recently proposed label model achieves strong empirical performance without falling into either camp.  That label model constructs a polytope of plausible labelings using the LF predictions and outputs the "center" of that polytope as its proposed labeling.  In this paper, we attempt to theoretically study that strategy by proposing Bayesian Balsubramani-Freund (BBF), a label model that implicitly constructs a polytope of plausible labelings and selects a labeling in its interior.  We show an assortment of statistical results for BBF: log-concavity of its posterior, its form of solution, consistency, and rates of convergence.  Extensive experiments compare our proposed method against twelve baseline label models over eleven datasets.  BBF compares favorably to other Bayesian label models and label models that don't use datapoint features -- matching or exceeding their performance on eight out of eleven datasets.

Statistical Analysis of an Adversarial Bayesian Weak Supervision Method
Steven An Computer Science Department University of California, San Diego
La Jolla, CA 92037 sla001@ucsd edu
Abstract
Programmatic Weak Supervision (PWS) aims to reduce the cost of constructing large high quality labeled datasets often used in training modern machine learning models. A major component of the PWS pipeline is the label model, which amal- gamates predictions from multiple noisy weak supervision sources, i.e. labeling functions (LFs), to label datapoints. While most label models are either proba- bilistic adversarial, recently proposed label model achieves strong empirical performance without falling into either camp. That label model constructs a poly- tope of plausible labelings using the LF predictions and outputs the "center" of that polytope as its proposed labeling. In this paper, we attempt to theoretically study that strategy by proposing Bayesian Balsubramani-Freet that implicitly constructs a polytope of plausible labelings and selects a labeling in interior. We show an assortment of statistical results for BBF: log- concavity its posterior, its form of solution, consistency, and rates of convergence. Extensive experiments compare our proposed method against twelve baseline label models over eleven datasets. BBF compares favorably to other Bayesian label models and label models that don't 't use datapoint features matching or exceeding their performance on eight out of eleven datasets.
(BBF), label model
Introduction
Large scale deep learning models often require labeled training set of substantial size. However, hiring experts to label every training point is not only expensive, but time consuming. Programmatic Weak Supervision (PWS) aims to ameliorate this problem by cheaply generating labels. This is done via combination of multiple weak supervision sources, called labeling functions (LFs). LFs can be computer programs [Ratner et al.) 2016). crowdsourcing workers, simple classifiers (like linear classifiers), etc. Since LFs are noisy and provide contradictory predictions on a datapoint, is incumbent the label model to combine the LF predictions to produce single labeling of the data.
The construction of the label model serves one of the main challenges in the PWS pipeline. Most label models are either probabilistic or adversarial. Probabilistic label models (Dawid and Skene 1979 Ratner et al. 2016 Zhang al., 2023) often specify a generative process for the labels/ outputs and compute the posterior label distribution for each datapoint. Much work has been devoted to this approach and there are many examples probabilistic label models that perform well empirically. Adversarial label models [Balsubramani and Freund 2015a| Mazzetto al. [021bb]
Mazuelas et al. 2022) assume the existence of an adversary who assigns the labels, construct polytope of plausible labelings, and then predict minimax optimal labeling to guard against the worst case. While they come with theoretical guarantees, e.g. An and Dasgupta (2024), these label models require (small amounts of) labeled data to construct the polytope. Arachie and Huang (019
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

propose label model that is adversarial and unsupervised, though we are unaware of theoretical guarantees for their method. There are also label models that fall into neither camp, e.g. Hyper Label Model (HyperI.M) [Wu et al. 2023), which constructs polytope of labelings in an unsupervised fashion and then picks the labeling that is in the "center". While HyperL.M is a strong performer in real-world settings, we are unaware of theoretical guarantees regarding its properties and performance. In this paper, we attempt to bridge the gap by proposing Bayesian Balsubramani- Freann (BBF), a Bayesian adversarial label model that is unsupervised, selects labelings like HyperLM, but also has theoretical guarantees such as consistency.
Say we have N datapoints X = {z1..... .NN Jo where 's label is 2, in 2 = (l..... K} K]. We Z, for each x E X. If our task is to determine whether an email is spam, 7(5 z)) might have large mass for a single j. On the other hand, if the question is whether someone will default on a loan, we may imagine n7 2)) being closer to uniform due to inherent uncertainty. Over all labels and datapoints, we compactly write ni x) as rj == (n/ xx): j E [K]. E [N]) E A where Ax is the set of distributions over K elements and A K is the concatenation of N of those distributions. Our goal is to pick a distribution from A & to approximate 17.
wish infer the underlying conditional label probability n(i x) = Pr(2 = j 2)
BBF approximates 77 by taking the mode of its posterior label distribution, which is itself specified by its generative process. First, BBF draws the distribution of labels on X, after which all datapoint labels are drawn simultaneously. Then, for each LF, its accuracy on X is drawn, following which the predictions it makes (on X) are drawn simultaneously. That is, once the accuracy b of LF h on X is drawn, any labeling of the N datapoints that attains accuracy b on X is equally likely to be selected as h's predictions. Compare this to a simplified version of other generative processes in the literature: once the datapoint labels and LF accuracies are drawn, whether an LF's prediction matches the label on a datapoint is a biased coin flip. Indeed, the frequentist versions of these models have similar difference:
(BF) |Balsbbramani and Freund 201 versus One-Coin
Dawid-Skens [Li and Yu 2014).
In this paper, we'll show that not only does BBF's prediction ghb have some nice properties, it has strong empirical performance.
1. Concavvty of Posterior) Given a small modification, BBF's posterior label distribution is log-concave.
2. (Form of Solution) gobl belongs to the same exponential family G as the BF solutions, defined in terms of the LF outputs.
3. (Consistency)) When the LF accuracy priors concentrate on the empirical accuracy, ghbs converges to g" E G that best approximates vî in KL divergence.
4. (Rates of Convergence) We provide bound for the rate at which ghb approaches g".
5. (Empirical Results) Comparison of gوu against twelve baseline label models on eleven real datasets. Consistency on real datasets is also shown.
2 Related Work
The PWS pipeline ranges from the creation of the LFs, aggregation of their predictions via label model, to the training of an end model using the label model's labeling of the data. For good survey that discusses all of these aspects, see Zhang et al. 22022] Since we focus on the label model in this paper, we'll give brief overview of them.
One line of work involving probabilistic label models starts from Dawid and Skene 1979], where confusion matrix and LF predictions
each LF is modeled
independent of each other given the datapoint label. The Dawid-Skene model has been lifted into the Bayesian setting and repeatedly
generalized: [Kim and Ghahramani 2012). [Li et al. 2019], [Zhang et al. 2023]. On the frequentist front, Ratner et al. 2016) builds upon Dawid and Skene's 's model by representing dependencies
between LFs in factor graph. Other probabilistic label models have been studied too, e.g. [Fu et al.)
2020 Kuang et al. 2022 Shin et al. 2022].
Adversarial labels models can take the form of minimax games where we the learner attempt to minimize the loss of our prediction (i.e. the label model's aggregated labeling) while an adversary tries to maximize our loss. A big part of these models is representing the subset of feasible labels,

---

i.e. a set of labels for which the true underlying conditional label probabilities lic. This was studied by [aasubramanni and Freund 2015a| for 0-1 loss, [An and Dasgupta, 2024] for log loss, where the set of feasible labels is gotten by bounding the accuracies of individual LFs. Arachie and Huang] [202T] estimate the I.F accuracies and then try to find the minimum norm labeling that induces those accuracies from the LF predictions. Alternate formulations of the minimax game can be found. In [Mazuelas et al. 2020]. uncertainty sets are considered, allowing for more general constraints on the set of feasible labels. Mazuelas al. [2022] consider generalized entropy as the loss function for the minimax game, which includes (-1 and log loss as special cases. Mazuelas et al. [2020] 2022], and and Dasgupta 2024], provide convergence results in terms of how well the LF accuracies are estimated, but only the latter show consistency. Mazzetto et al. 2021a] provide a generalization bound, though they require datapoints be drawn i..dd In contrast, the result of AAachie and Huang [202T] result requires that one know the actual LF accuracies on the unlabeled datapoints and for there to be an increasing number of LFs to drive down the prediction error. In this paper, we consider a fixed set of LFs and our analysis does not require the actual LF accuracies to be known.
Label models that are neural networks have also been proposed. For example. Wu et al. 2023 trained a graph NN that implicitly constructs polytope of labelings using LF outputs and returns the "center" as the aggregated labeling. On the other hand, Cachay et al. [2021] and Ren et al. [2020] incorporate datapoint features along with the usual LF predictions in computing the aggregated labeling. These last two works involve joint models, unified model that does the work of both label and end models.
3 Preliminaries
We now provide the formal setup for the problem and briefly discuss HyperL M and BF. We follow the notation Kim and Ghahramani 2012). Li et al. [2019] Zhang et al. 2023
We desire to label N unlabeled datapoints X = {I1....,,IN by combining the predictions from
W LFs, (1) , (WW, These LFs can predict one of the K labels in 2 = {I,... K} or abstain: i.e Mw) : X - Zu(]. "?" denoting abstention. In particular, our analysis makes no assumptions about the LFs, c.g. restrictions on their multiplicity, no requirements about their independence given certain events, etc. We'll abbreviate (/()) (ax) by Yiur- For every datapoint 24, we wish to infer
the (K dimensional) underlying conditional label distribution ij. E ÂK. Th = Pr(z: = j ax), the true probability of class for 24. Following Mazuelas et al. 2020).
(h 7N)= A
a vector of length NK. More notation will be introduced when necessary.
3.1 Hyper Label Model
To select its labeling, HyperI.M [Wu et al. 2023 first constructs finite set U of plausible labelings. Then, the labeling whose squared Fuclidean distance is minimized with respect to all elements of U is selected and used. Formally, suppose for this section only that Z = {=1]. U is subset of all possible hard labels nd such that the there are at least W/2 LFs that are better than random on each class. That is, for class +1 (and 1 respectively), there are least W/2 LFs that get > 50% of their predictions right when they predict- -1 (-1 respectively). Then, the HyperLM labeling is
1 U
g ghlm
arg mig _E[-1.I
| E...
U
FEU
BEU
By taking the convex hull of U. one can get a polytope of plausible labelings. Then, ghlm can be thought of as being the "center". To get ghlm in practice, the above authors train a graph neural network that takes LF predictions
input. MyperLM is empirically effective, e.g. see (Zhang ct al. 2023]. but Wu et al. [2023] did not present theoretical results about it's performance or other properties like consistency. We hope better understand HyperLM's strategy in this paper.
3.2 Balsubramani-Fremn with Log-Loss
The BalsubramaniiFrennt model (BF) also constructs a set of feasible labelings and then picks an element to use as its labeling. It has nice theoretical guarantees [An and Dasgupta 2024 but
3

---

there are two drawbacks, Not only does it need labeled data to construct P, not having enough labels makes P big and BF's performance poor.
We start by constructing a subset P C A& of all possible labelings such that the true labeling rj lies inside P. To approximate 17, we play zero-sum minimax game the learner, who tries minimize the worst case loss a potential adversary can inflict on us. That is, if we select labeling ğ E Ax. the adversary selects z E P that maximizes - logg.
We can construct P by using L labeled points to bound each LF's accuracy on X with error at most O(1/VI.). Formally, if ((w) makes Nw I N predictions, we can with T. labeled points construct
N K
bw - Ev by
1
ΣΣ ==
Ni (yin = S bw + Ew
N
with binomial confidence interval, where by is h(w)'s accuracy on X. Something similar can be done with the class frequencies: wj N Ei= "ly in the interval (wy] - E wi Ei]-
These constraints can easily be written in matrix form. Abuse notation and let Thur be the one-hot encoding of / (w() (I:;). Then, Viw (1(h(w)(z))
I)..... 1(1()) (z,) K)) where Tou is all zeros if 1((") (z;) = ?. We write all of h(')'s predictions as T. = (Fiw..... JNWw (Ax U (0x}) }) Note that the Vw vectors are the only vectors of length K that have special indexing with three indices. Other vectors of length N K (in A ) will follow the same style of indexing as Also, we write ē to mean the jth canonical basis vector in K dimensions concatenated N times. To write out constraints, compactly, define A E [0, 1] +[W+K))NX row wise where
N Fi A
for S W otherwise.
N Cm-
Finally, for brevity, define b= (bi..... bw wi,.... wK). Similarly, z:= :w. Ek). Then for elementwise inequalities, P can be written as
P = (EE As
(2)
Now, the zero-sum minimax game referred to earlier can be formally written as
min En log g min E log JEAN ZEP
(3)
PCP
where the equality is shown by An and Dasgupta 2024] and proven by them to be an easily optimizable convex program. Formally speaking, when one doesn't have enough labeled data, the elements of E are large, meaning P is large and BF is overly pessimistic. We will soon see how BBF addresses both drawbacks of BF by implicitly constructing polytope P and adopting label selection strategy similar to that of HyperLMM's.
4 Our Proposed Method
We now described proposed label model, Bayesian Balsubramani-Freet (BBF). At high level, we put prior distributions on quantities BF that are point estimates, specifically the class frequencies and LF accuracies. We'll deseribe the generative process, present the joint distribution, and discuss how to find BBF's posterior mode, which we'll take as BBF's prediction.
4.1 The Generative Process
To generate the labels and LF predictions, BBF is similar to iBCC [Kim and Ghahramani 2012 in that follows the same order (labels first, then LF predictions) and parameterizes LFs by a few parameters. Rather than model the underlying LF accuracy (r(h(w) = Y) like in iBCC, BBF tries to model the accuracy of an LF on X, i.e. ir,- (And similarly for Pr(Y = =j), wT.) We'll later see BBF's generative process and simplified version of iBCC's generative process side by side.

---

The first step in BBF's generative process is to draw the class frequency distribution F from a Dirichlet prior with hyperparameters ā' E R Then, the labels A K are drawn. We'll want to assign Ty N total mass for each class j E [K] That is, E will be drawn from
N
Lp = SEAR
N
Zig =
for each j E [K]
N
1=1
Rather than draw labelings at random from Ly, we'll '1l favor labelings with large entropy. This is necessary for our theoretical results. Our distribution for labelings will be denoted Entropy which assigns density Pr(ø F) x exp(-2" log 2) for E C+ and 0 otherwise.
The next step is to draw the accuracies for each LF. A first pass approach is to have a Beta prior with hyperparameters aw E R3 for LF A (w))ss accuracy b on X. This won't work in general because a Beta random variable's s support is [0, 1]. but the choice of E can make certain accuracies impossible. For example, if z N K, then regardless of what h (")) predicts. its accuracy can only be 1/ On the other hand, if 211 = and 2ij = 1/K for i 2 2 and j E [K] an LF that only predicts on Ii can have accuracies in 00, 1] while an LF that doesn't it abstain must have accuracy in the range [[N - 1)/KK, (N - 1)/N K + 1/N]. Thus, we need to restrict the range of accuracies that can be generated. For fixed labeling ž, define the range of permissible accuracies with
Umaa
min Zzj- max Zij and Umin [E[N],JE[K] [E(]]E
With this, we draw by from (elaz(pre), which is Beta(pw) with support restricted to [bmin bman] and density renormalized. Note that the number of predictions 1,(w) makes can depend on bw-
Finally, we draw predictions for each of the LFs. For readability, abuse notation and let N: (A K U (Ōx }) x + Rz be the function that counts the number of predictions made: N J INK. h((w)ss prediction is randomly drawn from the set of all possible predictions that achieve accuracy b
Lb = { (Ax (Ax (Ox)));
T 2 N
b
We now summarize the above and compare it to simplified version of iBCC's generative process. There, each LF is a biased coin and the datapoint labels/LF predictions are deterministic: 2 Viu Z. Le. the distribution of you = h (w) (a:)) with 2; = is described by v(b.. E Ak, which has b in the jth position and (1 b/)/(K 1) elsewhere.
BBF Generative Process:
One-Coin iBCC Generative Process
1. F Dirichlet(a)
1. F ~ Dirichlet(a))
2. For each datapoint i E [N]:
2. E ~~ Entropy(CCy (++)
(a) 2; ~ Calegorical(?)
3. For each LF w E [W]:
3. For each LF [W]:
(a) b Beta(pw)
(a) du Betaz(pu)
(b) For each datapoint E [N]:
(b) Th ~ Uniforrm(Con.))
i. yow ~ Categorical (u(bw, 2z))
4.2 The Joint Distribution
Now, we write out the joint distribution for BBF. Write Te [0, 1IW the vector of LF accuracies, / the 2W Beta hyperparameters, and Y the set of all LF predictions. We have that
br, ā. Pr(Y Σ,b) Pr(6) E, Pr() Pr(F d).
We now write each of the terms therein. First, Pr(7 @) x II == Tj B3
Then,
Pr(z) 7) exp(-ET log 2)
(
Pr(Y E, II
J bw
N
N(g)
j=1
5

---

To write the probability of the LF accuracies, we will need the Beta distribution's 's CDF at r [0, 1], written I, I, (3 for short. improve readability we drop the hyperparameters, but note that in each term of the following product, the difference of CDFs is specific to each L.F.
W
b 10 (1 bw p
Pr(b 2,
II 01
Ibmax Ienen
4.3 Computing the Posterior Label Distribution
In practice, we know the LF predictions Y {yt [W]. i E [N]} (along with the hyperpa- rameters) and want to know the posterior label distribution. Thus, we are interested in the quantity Pr(ž, 6, YY, a. p). It turns out that this quantity is only non-zero when every element of and F are deterministic functions of & (when Y is given). This is because the indicator functions in the joint distribution ensure the above is non-zero only when Tj = Ej Z/N and b Z/NN for every j E [K] and w E [W]. Now, if we use Tj, bu to replace the dot products, we have
W
1 (1 bw )ww
PT(E,,,1YY exp(-2" log 2) x II j=1
II w=1
(4)
Ibmax
In the Appendix, we show that the removal of the difference of Beta CDFs will make the RHS log-concave in E (with an appropriate choice of hyperparameters).
Lemma 4.1. The modified posterior label distribution for our proposed model written below is log-concave in when all elements of o p
exp(-2" log 2)
II
K
2
a--1
W X II
Pwi-1
(1
Dw
Pw2-1
N
((w))
N N(ww)
3=1
W=1
BBF's prediction goوl will be the mode of the modified posterior distribution, i.e. the solution to
K
z
max SEAN
- TT log E
Σ
(ay
1) log
N
j=1
W (pwi 1)log log
Fu
Tu N N(ww)
+ (Pw2 - 1) log
(5)
N(Tw))
which is concave maximization problem. This can be solved using off the shelf convex solver. note that maximizing the modified log posterior without both holding all predictions in memory and simultancously optimizing over all N variables is an open problem.
5 Statistical Analysis of Our Proposed Model
We now argue that BBF implicitly constructs a polytope P c AN of plausible labelings and selects labeling inside its prediction, la HyperLM. To start, compare BBF's objective (Equation 5 with BF's objective (Equation 3). Both are entropy maximization problems- BF constrains ह E while BBF has such constraints, but has extra terms in the objective. Observe that the BF problem as maxzea K [-2"T log x M1(3 E P)] where M is an extremely large constant. In order for ž' to be optimal M must appear, meaning z must be in P. We want to arguc that the sum of log-pdfs of Dirichlet and multiple Betas in the BBF objective serve as continuous approximation to M1(2 E P). Call E E/N and J E/N the class frequency/L.F accuracy induced by Σ. The sum of log-pdfs is maximized when the induced class frequencies/LFF accuracies K
rewrite
are close to the modes of the Dirichlet/Beta distributions. Iee. close to (a: 1) Ojr K),
(Pwa 2)/(pwx + Pw1 - 2) respectively for each [K] E [K]. Thus, for BBF, may regard its polytope p' as the z's whose induced accuracies are not too far from the mode. For LF accuracies, that is 2/N (pw1 2p/(pw + Pw1 - 2) < e for some cu. This is exactly the form of inequality used specify BF's polytope (Equation For sufficiently large ã, p. g.gh god will induce

---

class frequencies/LF accuracies close to the modes, which means  will be in the interior of P!. Note that unlike BF, BBF's performance affected by duplicate LFs in most cases. It is only in a special case that BBF is not affected by duplicate LFs. However, the following results for BBF do not depend on having a set of unique LFs. With that, we are ready to analyze BBF's form of solution, consistency, and its convergence rates.
go is a Weighted Majority Vote 5.1
Here, we show that ghb is completely specified by W + K real numbers and the LF predictions. In particular, for any datapoint zi, 9i is the softmax of weighted majority vote. Let Ō E RW+K be our weights, the first W being for the LFs, the last K for the class frequencies. We are claiming that
[w== Owl + Ow-s)
exp
exp((AT0),
bbf
96j
Σ j²== exp
EW O OwNiwwy' + Ow+3')
K S5'=1 exp( (AT((AAT))))) 0)
for some 0. By varying 6 over the reals, one gets exponential family of distributions:
g= = (g BWWK+
where 9 (xp((A ()))));;)
Lemma 5.1. For fixed LF predictions and hyperparameterss ã. 2 elementwise, the BBF prediction gibs gotten by solving Equation 5 is such that gobl eg.
Now, we analyze the behavior of gobs as ā, change and the LF predictions/jj remain fixed.
5.2 Consistency
While BBF's prediction must lie in G, rî in general doesn't lie in G. Thus, the best hope for is to get the best approximator of iī from G, i.c. g" = g = arg minzeg d(17, g) for distance function d(.,.). KL divergence will be the distance we choose. For μ7, Ø E A recall they are each concatenations of N distributions, so
N d([i V) Σ KL(T,T))
N
Usj
= i= 1=
Pij log
Now we'll informally argue that BBF is consistent insomuch as we can make glbj tend to g". In the beginning of this section, had argued that BBF implicitly constructs polytope P' and picks a labeling from inside P'. It turns out for a specific polytope and specific strategy of selecting labeling from inside, one can obtain g" Consider the polytope P {3 E A A = b.), the set of all labelings that induce the empirical LF accuracics/empirrcal class frequencies. An and Dasgupta 2024] showed (in Theorem 6) that if BF is given P* then BF will return gr, Our result for BBF shows how make the implicit polytope of BBF to tend to P whereupon g gob g" In the Appendix, show that BBF satisfies modified version of BF's KKT conditions (for fixed implicit polytope) where the complementary slackness condition is not satisfied. However, as we make BBF's implicit polytope tend to Pa the complementary slackness conditions will be satisfied, meaning BBF replicates the behavior of BF with P*. Only then is BBF unaffected by duplicate I.Fs.
To make BBF's implicit polytope tend to Pt we need to make it so whenever the induced class frequencies/L.F accuracies are not close to w7. by the resulting contribution from the sum of the
log-pdfs is small. For convenience, define og Σ Ozj-
Theorem 5.2. for each w E [W], Pwl: Pw2 + 00, | - 1 - bt (Pw1 + Pw2 - 2) + 0 and each j E []. Oj - do and |a,, 1 - w/(00 (00 K) + O, then Johl - g"
Note that this not the Bayesian notion of consistency. There, one has appropriately selected priors with fixed hyperparameters and the requirement is the number of observations (e.g. LF predictions) tends to infinity [Miller] 2018). For BBF, our proposed model only has observation, the set of all LF predictions on X, meaning cannot take advantage of the vast literature on Bayesian consistency.
7

---

5.3 Rates of Convergence
We'll now see g i rate of convergence to g". Specially, we'll bound . ( by a function of the weights that produce g", "" call them 0*, 0bh,, and how well ge estimates the actual LF accuracies/class frequencies.
Theorem 5.3. Suppose a, 2 elementwise. Then for elementwise absolute value,
d(g", 1 (10*) + 1 1TT [B- AAg
When the conditions of Theorem 5.2 hold, Jbb - 0*.
It's unclear to us how one bounds g or how well Ag approximates by, meaning we cannot say on what order BBF's convergence rate is. We note that duplicate L.Fs will increase the size of the bound as each duplicate LF adds an extra term. Now, if an unsupervised instantiation of ã' p induces gtbs such that Ag is close 6*, then the excess error will be small. Experimental results show that BBF performs well in the unsupervised setting and often has small excess error compared to g".
6 Experiments
Here, we compare the performance of BBF against other baseline methods on eleven real datasets while also showing BBF's consistency on real datasets. Experiments were run in Python 3.6.13 (PSF) [Van Rossum and Drake 2009] mainly using NumPy 1.19.5 (modified BSD) (Harris et al. 2020] with AMD Ryzen R9 5950x, 128GB RAM, and an Nvidia RTX 2080Ti. One may find the code in the supplementary materials or at httpps://githue com/ stevenan5/ Dfyesian-bf-nnuriiee
6.1 Methods
We compare our proposed method with twelve other methods, representing different approaches to creating the label model. For our method BBF, we set the prior hyperparameters as ā Ik. P (4,1) ) for each w E [W]. This follows the initialization of [Li ct al. [2019] for their Bayesian method, i.c. we assume each LF makes 4 correct predictions and 1 wrong prediction. Note that there are requirements on the I.F accuracies for BBF. Across all LFs used in the experiments, the accuracies range from 0.0366 to 1. To compute the BBF prediction, we optimize Equation using CVXPY 1.4.1 (Apache 2.0) [Diamond and Boyd 2016) by way of MOSEK 10.1.16 (personal academic license) [MOSEK ApS. 2022] with default parameters.
The other twelve methods are from the WRENCH benchmark version 1.1.2rc0 (Apache 2.0) Zhang al. 2021]. They are: majority vote (MV), Dawid-Skene (DS) (Dawid and Skene 1979 Data Programming (DP) [Ratner et al., 2016). generalization of DS that accounts for some LF depen- dencies, Flying Squid (FS) Fu et al. 2020). fast method that uses an Ising model. TaL [Ratner et al. 2019], matrix completion type method, iBCC [Kim and Ghahramani 2012]. the Bayesian generalization of DS, EBCC [Li et al. 2019 generalization of iBCC, but where each LF is modeled by multiple confusion matrices, FABLE [Zhang et al. [023). J generalization of EBCC which can account for datapoint features, Constrained Label Learning (CLL) [Aaccie and Huang 2021), polytope based method with an adversarial flavor, Hyper Label Model (HyperLM) [Wu et al. 2023] a graph neural network based method, WeaSEL [Cachay et al.. 2021], and Denoise [Ren al. 2020), two neural network based methods using attention with different losses. We ported CLL into WRENCH and following Arachie and Huang [202T], we initialized LF errors to be 0.01 if the LF coverage low (i.e. low number of datapoints predicted on) and R if the LF coverage was high. For all other methods that require initialization, we use the defaults provided in WRENCH.
6.2
Datasets
We used eleven datasets from WRENCH, which also provided the LF predictions. The following datasets had licenses we could find online and were different from WRENCH's license: YouTube, SMS (CC BY 4.0), SemEval (CC BY 3.0). For FABLE, Denoise, WeaSEL, we use the original datapoint features, unless they were textual, in which case RoBERTa [Liu et al. 2019 was used to extract them. The methods are evaluated in transductive setting, The provided vaain/vliiatiinn/estt
8

---

Table 1: Some dataset statisties. Note that we only count datapoints with at least one LF prediction.
Dataset
IMDB Youtube
SMS
CDR
Yelp
Commercial Tennis
TREC SemFiaa ChemProt AG News
# Class (K)
2
2
2
2
2
6
9
10
4
# LF (W) 5
10
73
33
8
4
6
68
164
26
9
# Datapoints (N) 21,914
1,843
2,246
12,562
31,512
81,105
8,803
5,738
2,527
13,768
82,591
Table 2: Comparison of our proposed method with baseline methods (higher is better). Bolded entries are indistinguishable via two-tailed paired t-test with p = 0.05.
Dataset
IMDB
YouTube
SMS
CDR
Yelp
Commercial
Tennis
TREC
SemEval
ChemProt
AG News
Loss
F1
F1
0-1
75.19
84.56
78.88
67.28
78.22
84.46
83.83
54.51
79.07
54.67
DS
65.08
83.56
65.30
57
75. 20
88.31
83.56
47.
73.53
52.66
81.79
DP
74.81
78.62
57.82
41.78
71.61
78.61
83.61
45.85
72.78
56.17
81.71
FS
75.51
83.07
70.55
69.12
78.67
80.56
83.31
50.10
12.15
52.37
81.28
MeTaL
74.78
76.31
18.39
17.69
70.14
78.62
83.62
13.73
51.38
55.86
81.84
iRCC
75.33
0.00
0.00
84.16
21.02
30.19
35.09
EBCC
75.32
0.00
0.00
24.81
76.57
76.83
81.19
21.02
30.19
35.09
27.81
CLI
74.80
84.79
78.83
64.33
77 80
36.38
42.31
59.34
84.21
52.37
80.97
HyperL.M
75.29
91.40
78.90
70.54
78.73 73
82.60
84.21
60.02
84.21
52.32
81.38
WeaSEL
53.07
61.85
26.45
38.50
61.91
30.00
3.74
20.81
11.14
21.41
32.29
Denoise
81.05
79.84
79.06
70.94
80,97
89.71
51.12
49.81
73.53
$7.85
87.61
Fable
74.97
87.80
78.75
62.40
85.91
83.59
53.64
73.61
54.42
81.38
BBF
74.67
89.71
78.77
62.39
77.67
85.02
79.87
59.88
84.21
52.47
81.40
Improve
5,86
6,84
0,18
3,66
2,75
5,25
0.38
5,51
5.14
3.18
6,23
9"
75.53
94.22
78.83
72.25
78.83
88.31
83.43
63.75
84.21
61.26
82.24
splits are combined and points with no LF predictions are removed. Each label model is given LF predictions on the datapoints (and the datapoint features themselves if used). No labeled data is provided to the label models. Label models without using any labels. Labels are only used to judge the quality of each label model's 's predictions by way of Fl score/0-1 loss. Tasks covered by the datasets range from sentiment/spam/bio relation/video frame/chemical relation/topic classification. See Table [ some statistics.
expected be initialized and provide a labeling
6.3 Comparison with Other Label Models
For every method that involves randomness, we run it ten times and display the average performance in T Bolded entries represent ones that are indistinguishable from the best result via two-tailed paired t-test with p 0.05. WeaSEL, Denoise, and FABLE are the only methods that datapoint features all others only use LF predictions. The second to last row, denoted "Improve" shows the improvement of the best label model over majority vote. The last row shows g" (computed via Theorem 6 of [An and Dasgupta 2024)). ) a proxy for the ceiling of BBF's performance. See the Appendix for the complete results (0-1 loss on all datasets, standard deviations of losses).
Against the highest performing Bayesian method FABLE, BBF often matches or outperforms, only significantly underperforming Tennis. This is notable because FABLE uses datapoint features and is much more expressive than BBF. On Tennis, the three LFs that each predicted on 99% of the datapoints closely matched each other, i.e. had > 85% matching predictions. This effectively reduces the number of constraints on BBF's implicit polytope because three constraints are almost duplicates.
Compared to HyperLM, BBF is competitive except for CDR and Tennis. On CDR, the number of LF predictions per datapoint was very low, averaging 2.3 predictions per datapoint despite there being 33 LFs. Two predictions per datapoint means BBF's implicit polytope has very few constraints per datapoint, likely diminishing the performance.
Against Denoise, we see the limitations of representing an LF by its accuracy even with g", BBF is worse on IMDB, SMS, Yelp, etc. For ChemProt specifically, we think BBF is worse than Denoise because the average LF accuracy is just under 0.47, which differs greatly from our mean prior accuracy of 0.8. For almost every other dataset, the average accuracy of the LFFs was within 0.1 of 0.8. SemEval was the outlier with average LF accuracy of 0.97.

---

10a
dllg", goon
10-1
KL Divergence
KL Divergence
10-1
10
dll"". gaar
10
10
10a
104
10a
10
102
10a
10*
103
Hyperparameter Scale (s)
Hyperparameter Scale (s)
(a) Yelp
(b) SemEval
Figure 1: Demonstrations of BBF's consistency real datasets.
For all other methods, BBF has similar if better performance on large majority of the datasets. The exceptions are on CDR against FS, Commercial against DS, Tennis against almost every method, and ChemProt against DP/FABLE. This is evidence of BBF's strength label model.
Since BBF employs a similar strategy to HyperLM, we now quickly discuss the performance differences between MyperLM and Denoise. On IMDB, Commercial, ChemProt, AGNews, HyperLM performs worse than Denoise, so much so that it's close to majority vote in performance. We hypothesize that the "center" of the polytope constructed by HyperLM might be close to the majority vote labeling. This is because we could not find a pattern between whether HyperLMM's assumptions were met, the number and/or quality of the LFs provided, and whether HyperLM underperformed against Denoise. In the cases where Denoise underperformed against HyperLM, we believe this is because Denoise might get stuck in poor local optima its strategy for learning is similar to that of bootstrapped co-training Blum and Mitchell 1998).
6.4
Consistency of BBF
+ 1, 1 s, bC,) + 1) with s > 0. By having take values in {10', i0?,..., 1,,1, we simulate the conditions of Theorem 5.2 Figure shows d(g", / //N on a log-log scale graph on two datasets. We see the convergence worst linear function of See Appendix for complete consistency results.
To show that BBF is consistent on real datasets, we choose
7
Limitations
We have seen a new label model that is adversarial, unsupervised, has strong empirical performance and enjoys nice theoretical guarantees. This was done by combining HyperLM and BF's strategies.
However, there are still some unsolved problems. On the empirical front, one must hold O(WN) items in memory and optimize NK variables simultaneously to get ghus._ This is infeasible when N is large. We also noticed in our experiments that || Ilx was small, meaning BBF can be poorly calibrated. On the theoretical front, are not able control @bbf, meaning we do not know at which rate go g a priori. Due to gbf not being a minimax optimal solution, we lose the guarantee that -1j logggh)
gtbbf < - log ghbf. Lec. we don't 't have bound for the cross entropy between and Joby which is only in terms of g hbs.
Acknowledgments and Disclosure of Funding
The author thanks the National Science Foundation for its support under grant IIS-2211386, Sanjoy Dasgupta for suggesting the Balsubramani-Freuus model be given a Bayesian generalization, and the anonymous reviewers for their time and feedback, which indubitably improved the paper.
10

---

References
Steven An and Sanjoy Dasgupta. Convergence Behavior of an Adversarial Weak Supervision Method. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 1-49. PMLR, 15-19 Jul 2024.
Chidubem Arachie and Bert Huang. Adversarial Label Learning. Proceedings the AAAI Conference on Artificial Intelligence, (((01):3183-31) Jul. 2019.
the
Chidubem Arachie and Bert Huang. Constrained Labeling for Weakly Supervised Learning, In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 236-246. PMLR, 27-30 Jul 2021.
Akshay Balsubramani and Yoav Freund. Optimally Combining Classifiers Using Unlabeled Data. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 211-225, Paris, France, 03-06 Jul 2015a. PMLR.
Akshay Balsubramani and Yoav Freund. Scalable Semi-Supervised Aggregation of Classifiers. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, page 1351-1359, Cambridge, MA, USA, 2015b. MIT Press.
Avrim Blum and Tom Mitchell. Combining Labeled and Unlabeled Data with Co-Training. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT 98, page 92-100, New York, NY, USA, 1998. Association for Computing Machinery.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Salva Rühling Cachay, Benedikt Boecking, and Artur Dubrawski. End-to-End Weak Supervision. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS 221, Red Hook, NY, USA, 2021. Curran Associates Inc.
Alexander Philip Dawid and Allan M. Skene. Maximum Likelihood Estimation of Observer Error- Rates Using the EM Algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1)) 1979.
Steven Diamond and Stephen Boyd, CVXPY: A Python-Embeddee Modeling Language for Convex O ptimization. Journal of Machine Learning Research, 17(83):1-53 2016.
Daniel Y. Fu, Mayee F. Chen, Frederic Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and Three-rious: Speeding up Weak Supervision with Triplet Methods. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JMLR.org, 2020.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Ferná ndez del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchand Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array Programming with NumPy. Nature, 585(7825):357 362, September 2020.
Kevin Sheppard, Tyler Reddy,
Hyun-Chul Chnn Kim and Zoubin Ghahramani. Bayesian Classifier Combination. In Neil D. Lawrence and Mark Girolami, editors, Proceedings of the Fiffeenth International Conference Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 619-627, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
Zhaobin Kuang, Chidubem G. Arachie, Bangyong Liang, Pradyumna Narayana, Giulia Desalvo, Michael S. Quinn, Bert Huang, Geoffrey Downs, and Yang Yang. Firebolt: Weak Supervision Under Weaker Assumptions. In Gustau Camps-Vall Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8214-8259. PMLR, 28 30 Mar 2022.
11

---

Hongwei Li and Bin Yu. Error Rate Bounds and Iterative Weighted Majority Voting for Crowdsoure- ing, 2014. (Rtthst:://axxii org/ htte//abs1411.... 4086
Yuan Li, Benjamin P. Rubinstein, and Trevor Cohn. Exploiting Worker Correlation for Label Aggregation in Crowdsourcing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3886-3895. PMLR, 09-15 Jun 2019.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A Robustly Optimized BERT Pretraining Approach, 2019.
Santiago Mazuelas, Andrea Zanoni, and Aritz Pérez. Minimax Classification with 0-1 Loss and Performance Guarantees. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 302-312. Curran Associates, Inc., 2020.
Santiago Mazuelas, Yuan Shen, and Aritz Pérez. Generalized Maximum Entropy for Supervised Classification. IEEE Transactions on Information Theory, (8(4):2530-2550 2022.
Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach, and Eli Upfal. Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7534-7543. PMLR, 18-24 Jul 2021a.
Alessio Mazzetto, Dylan Sam, Andrew Park, Eli Upfal, and Stephen Bach. Semi-Supervisee Aggregation of Dependent Weak Supervision Sources With Performance Guarantees. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3196-3200 PMLR, 13-15 Apr 2021b.
Jeffrey W. Miller. A Detailed Treatment of Doob's Theorem, 2018. URL https:://axxi..o/ abs/1801 03122
MOSEK Aps. MOSEK Optimizer API for Python. Release 9.3.20, 2022. URL https://docs mosek. nomek.com/9 3/ h/ppthonnai..p..... .dff
Alexander Ratner, Braden Hancock, Jared Dunamon, Frederic Sala, Shreyash Pandey, and Christopher Ré. Training Complex Models with Multi-Task Weak Supervision. Proceedings of the AAAI Conference on Artificial Intelligence, 53(01):4763-477 Jul. 2019.
Alexander J. Ratner, Christopher De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data Program- ming: Creating Large Training Sets, Quickly. In D. Lee, M. Sugiyama. U. Luxburg. I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, pages 3567-3575. Curran Associates, Inc., 2016.
Wendi Ren, Yinghao Li, Hanting Su, David Kartchner, Cassie Mitchell, and Chao Zhang. Denoising Multi-Source Weak Supervision for Neural Text Classification. In Trevor Cohn, Yulan He, and Yang Liu, editors, Findings of the Association for Computational Linguistics: EMNLP 2020, pages Online, November 2020. Association for Computational Linguistics.
Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Univer- salizing Weak Supervision. The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OeenReview.net, 2022.
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009. ISBN 1441412697.
Renzhi Wu, Shen-En Chen, Jieyu Zhang, and Xu Chu. Learning Hyper Label Model for Programmatic Weak Supervision. In The Eleventh International Conference on Learning Representations, 2023.
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner. WRENCH: Comprehensive Benchmark for Weak Supervision. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
12

---

Jieyu Zhang, Cheng- Yu Hsich, Yue Yu, Chao Zhang, and Alexander Ratner, A Survey on Program matic Weak Supervision, 2022. httpps:////rxi org/ abs/a/o2..... 05433
Jieyu Zhang, Linxin Song, and Alex Ratner. Leveraging Instance Features for Label Aggregation in Programmatic Weak Supervision. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 157-171. PMLR, 25-27 Apr 2023.
A Appendix Overview
Here, we provide the missing proofs along with extra experimental results. After a brief notation recap, the rest of the Appendix is organized follows:
Section C results involving the Bayesian Balsubramani-Freund (BBF) posterior label
distribution, log-coneavity (Lemma
Section D overview of the proof strategy used show the remaining theoretical results. A table of contents detailing major steps of the main proof is provided there. The proofs will be written for LFs that don't abstain, but they'll Il work for LFs that do abstain.
Section extra experimental results.
-Subsection extra tables showing 0-1 loss for all datasets as well as the standard
deviation losses.
Subsection extra experimental results showing BBF's consistency on real datasets.
B Notation Recap
The set of labels in consideration is = {z),.... ......,, NN which each have of K labels.
We would like to label N points in the set X
K] [K]. At our disposal are W labeling functions (LFs) (2)) ... (W); X + Z [?} where "?" denotes abstention. We seek to infer the
true conditional label probabilities for each point zy:
M Pr(z = xz)) so that T (Ma...., .Rk) E Ak-
For convenience, we'll concatenate all N of these distributions:
(T 7N) AN
Similarly, we'll represent LF predictions by N probability distributions which are each over K elements. For datapoint Ti, the one-hot encoding of LF h(")'s prediction is denoted
Tuu (1 (x::) = 1),... 1(h (w) (x.) K)) E A U {
where 0g is zeros vector of length K. We note that for the theory, Thw doesn't 't need to be vector of zeros and ones. It can be a bona fide distribution without any effect to the results shown below. The set of all predictions for this LF
The
(J Vim, (Nww (Ax U (Ox))*
Two sets of important quantities are the LF accuracies and the class frequency distribution. Suppose (w) predicts on N.. < points on X. What we refer to as the actual accuracy of LF ((w) on X is
b
Thy (1)( j)).
N
1=
In dot product form, this is T. //. The actual class frequency distribution X
N
w/
Mkj
13

---

Letting éj E A K be the concatenation of N copies of the jth canonical basis vector in K dimensions, the above can be written as Ej 1//N. We sometimes call the starred quantities empirical i.c. the empirical LF accuracies or the empirical class frequency distribution.
The computation of these values can be written as a matrix vector multiplication. This matrix will be called A E [0, [][[-]]W *X) Let the first W rows be /w/Nu for w E [W] and Eg (j E [K] for rows W +1,..... W + K. Then, Arj E [0, 1] 1] is (bf,.... li w.... , , To save space, we'll define
b = (bi,.... bi w (.k. w.)
This will also be done for enror bars: Ee [0, 1] where we might write the elementwise inequality
8 -5- Arj < 8* +
The Dirichlet prior (for BBF's class frequency) has hyperparameters a E R The Beta priors (for LF accuracies) has hyperparameters Pvo E R3.0- Variables that are important for the proofs below f, the generated class frequency distribution, and b, the generated LF accuracies. The generative process for BBF as follows:
1. F Dirichlet(a)
2. 8 Entropy(Cz)
3. For each LF E [W]:
(a) bw ~ Betaz(pw)
(b) Tw ~ Uniform(
C BBF Posterior Label Distribution Concavity (Lemma 4.1
We'll 'lll first manipulate the posterior distribution explicitly to bring about the terms shown in the main paper. Then, counterexample will be given to show that the BBF posterior is not log-concave in x (the labeling). Finally, show how modification makes the posterior log concave.
Z E A
Let Y be the LF predictions from our W LFs, ã E R be the class frequency Dirichlet hyperparame- ters, p be the Beta hyperparameters for each LF. If we include everything, the posterior probability for our parameters / (labeling), (LF accuracies), (class frequencies) is
Pr(ž, b, 7 Y P,(E,E,F.YYa.pp)
br Pr(Y,a,p) Pr(Y ā. Pr(a, Ø)
& Pr(E,E,F,Y,,.,)) Pr(a,p)
We'll now repeatedly apply the chain rule the numerator, then drop variables which are independent.
Pr(z, ,r, = Pr(Y 1,, Pr(b ž,F, Pr(ž F. a. Pr(f ā Pr(a, p)
Since the generation of the LF predictions Y only depends on E and 6, all other terms can be dropped. Similarly, 5 only depends on _ and only depends on 7, and F only depends ã. The above is then equal to
Pr Pr Pr(Y Pr(b Pr()
( ā) P)(a,
We have
Pr(E,b, Y. x Pr(Y b) (r(6 E. Pr(E1 P)
We can now show what each term is proportional to. Let (-) be the indicator function and recall that Tw E AN is LF w's predictions. Also, recall that 2, is the 7th canonical basis vector in K dimensions concatenated N times. (Elements (i 1)K + are 1 for i [N]. all other elements are 0.) Recall that we've abused notation and have (-)) count the number of predictions LF makes. L.. for
y E (A U {)x3)* N we have N(g) o INK- Observe the following:
Pr(Y| b2
I[
(( Joe
bw )w
Pr(ā1 exp(- log Z)
I[ j=l
N
14

---

Let Pel, Pu2 represent the first (a) and second (3) Beta hyperparameters for LF h(()).
K x
W
be 1 bw )auz -1
Pr(F
④
Pr(0
2,
x
II w=1
Ibmas
Ibmin
==1
where
bynan
max [K]]
2ij
and
Uyión
min Zij [E[N]jE[K]
and l is shorthand for the Beta CDF with hyperparameters 3.
1 = (a a B(a, 3)
1 B(a, 3)
L to- (1-
Putting everything together, the posterior is proportional to the following
W Pr(2,,,F1Y,, & II
W
bout
Dar Puw)
Fu = bw
II
((Tw)
Timax
Ibmin
w=1
w=1
K II
1 N
exp( -T
log
(eJE=T))
Now, we show that the posterior distribution as stated above is not log- log-concave. Specifically, the term 1/(Ibmar Ibmmn) is what gives us trouble that difference depends on ž.
Lemma C.1. The posterior parameter distribution (over ž, 5, F) of our model is not log-concave in Z.
Proof. We consider the case where Pr(z, Y,ā, L) > O, meaning 5 and F can be written terms of The problem comes from the distributions from which the accuracies are drawn, Betaz(a, 3). Suppose we fixed the LF index w and dropped its index in Tw. Also, say Pul and Pw2 to make things cleaner. Finally, lets suppose that LF (ww) predicts all N points. The pdf of Betaz(a, 3) for " [0, 1] then
NH 2) a 11 N 2)
(Tbmax To B(a,, (3)
For this distribution be log concave, the logarithm of the pdf must concave. Only looking the non-constant terms,
(a log
N xTzz + (8 11g
TT N 11-NN1
1
-lo((Dmms
Ibmenn
has to be concave.
We can show instantiation of the above fails to satisfy the inequality required for concavity. Define f(ž a, 3, 77 as the above. (Recall Iomax Iomen are functions of ε.) Take a = 10, B = 0.5, 5 = (0.9,0.1) 0.1) z = (0.55, 0.45) and y = (.5), (K = N = 1). For the pdf of Belaz(a, 3) to be log concave, we must have
s00 + 0) 3. 2 0f
() 3,7)
For the given values, the right hand side is bigger than the left hand side by about 0.612. Thus, we have an instance where the required inequality for log-concavity does not hold.
If we just remove the 1/(T - -B term from the Bayesian BF parameter posterior (Fquation then the resulting expression will be log concave. We'll still call the result a "posterior".
Lemma C.2 (Lemma 4.1p. If we remove the normalization constant for Belaz(a, 3), i.e. the Diaas -Tomi quantity, then the resulting "posterior" as follows is log-concave in given that each element of and & is at least I.
Pw1-1
Pw2
a--1
exp(-ZT log
II
T 7
II N
((T)))
N (HTw)
15

---

The condition stated in the above lemma is essentially the condition for Beta/Dirichlet pdf to be log-concave.
Before showing this, we need a supporting lemma.
Lemma C.3. Suppose 2 0, E e (Ax UOO) ) and N(J) 1 x> O. Then,
1 J'
f(V) (T)
log-concave in Proof. Since r is non-negative, suffices to show that
log
2
is concave. From Boyd and Vandenberghe 2004], page 84, we have non-decreasing function (log) and concave function (dot product). Therefore, their composition concave in ž.
Remark C.4. The above Lemma also holds if the argument inside the logarithm is 1 J E/N(ji because this is also concave in For our purposes, that difference will always be non-negative.
Proof of Lemma C.2
W II W=l
Aw1-1
Puz-1
K II
a--1
exp(-z" log
1
(6)
N
N
To show that the posterior is log-concave, suffices show every element of the product log- concave as the product of log-concave functions remains log-concaye
To begin, take the exponential term the left hand side (-E" log termm. This is clearly log- concave. For all the remaining terms, suffices to apply Lemma C.3 for each one. Note that we have used the assumption that Pw1s Pw2; aj for all [W] and [K]. Therefore, the posterior is log-concave in z as claimed.
D The Remaining Theoretical Results
We now prove the remaining results: convergence. From here onwards, we will drop the vector notation for 7), 9, 2, Yo when we will only need to reference the entire vector. There will be the odd situation where we' 'll need to reference vector within a vector, e.g. 7j E Ak, the true conditional label distribution for r,,
the form of the BBF prediction, consistency, and rates of
Recall that we take the mode of the modified BBF posterior label distribution. That is, / the solution to the following convex program:
W Σ w=1
y )
min ZEAN
log
(pwl - 1) log
N(TT)) v + (pw2 1)log
1
N N(Juv))
K
Σ
(ay 1) log
1 N
eg
(7)
Le. the modified log-posterior was log-concave, so we just negated get a minimization problem.
With the convex program to solve clearly defined, the overarching goal to bound the distance between 77 and ggو Recall that we using KL divergence that
d(i,, Ab5
LL Mi).
16

---

Once 1 and the LF predictions are fixed, we will derive the relationship between á. p. the hyperpa- rameters we control, and d(n). g fhf).. In the process of deriving such a bound, we'll be able to prove the remaining claimed results.
To set the stage, Lemma 5 of (An and Dasgupta 2024 shows that
d(n.g*Mf = d(n,9) 96) d(g", gh we can provide an upper bound for the L.HS in the form
d(n.g*b) gbbf) S d(n.g") A
then we know that d(y"; gb S A B. Since
d(n, 9 / -n log bbg + -1' log
suffices to demonstrate what the values of AA and B that
-17 log bbf < - T log g
Mif
+ A + B.
Theorem D.1 (Informal version of Theorem 5.3
-1' logg bbf S -9 TBST log 9 MJ + A B. bbr
for
A 1000//11 Ag A and
B B-10"1T16 - Aggh//
where the absolute values are elementwise and Obbs O" E ERR++K are the respective weights bringing about the predictions g²وو = ( and g" g00))
It's after proving this result that we have the machinery to prove that Mb has the same form of solution as BF and that BBF is consistent.
Proof Sketch of Theorem D. The idea to use the analysis done in (An and Dasgupta, 2024) to bound BBF's error. Namely, the cross entropy term the LHS of the theorem statement is not easy to analyze. Thus, we use a proxy: -b log bbf and upper bound that. However, unlike for gd it's not guaranteed that
-17 log g bbf <
TbST -g logg bbf
Thus, we show a term A which when added to the right hand side makes the above incquality always hold. Now, it suffices to upper bound -g log g/0 by
logg" + B.
To do this, we'll first define class of BF problems with polytope Paar, which has specific form. (This class BF problems will depend on the same LF predictions and as BBF), For fixed BBF hyperparameters p. we'll 'lll fix Poar. The solution to BF problem that uses Poers will be called ghar. Namely, har is the solution to
Vaar max min IT llogg min
loo
SEAN sEPbar
sEPbar
with respect to We'll show that TbT logggh/ - logg This is done by demonstrating that n06 almost satisfies the KKT conditions of Vhar. The KKT conditions are 'almost' satisfied in specific way so that we can use techniques showing how an interior point method can be used to solve convex programs to show the above inequality. Lee the terms after the entropy term in the BBF objective (Equation 7 are log-barrier approximation of Pbar.
Following the analysis of An and Dasgupta 2024 we'll then show that
borT log bar
-n log g + B
where B |0 AS.
Putting everything together, the chain of inequalities is as follows:
lngogg Nbs < NTTT log /6 /0 + + A -grar BarT log bar + A S -n) - logg" + A B.
bar
17

---

Once we specify the BF problem Vaar, we can show that the BBF solution has the same functional form as the BF solution. Recall that we can define set of predictions g = {g) 0 E R kW+ where
exp((A) (T))))) x exp((AT ())). EXp (ATO) (AT))
Pi
Lemma D.2 (Lemmag) 5.1 gho E g.
Proof Sketch. the last proof sketch, we mentioned how / almost satisfies all KKT conditions
for Voer- In particular, it satisfies the zero-gres troo-gradient condition. The zero- vero-gradiens condition is what determines the form of solution. So. since BF and BBF satisfy the same condition, they have the same form of solution. An and Dasgupta 2024 show (in Theorem 2) that gbو E G. so g E G.
Analysis of the KKT conditions that / satisfies is what will let us show BBF's consistency. What we'll need is that the prior distributions of BBF to concentrate around the empirical LF accuracies and empirical class frequency distribution. What will happen is that polytope being approximated in the BBF objective will tend to p { A Az = b.}. where
arg min log EEP
(The above result was shown in Theorem 6 by An and Dasgupta (2024 This means that gb g". the best approximator in KI. divergence to 1).
Theorem D.3 (Informal version of Theorem 5.2 ā and ò each tend to infinity elementwise and grow in such way that Ag b", then
g".
Proof Sketch. We'll show that as the BBF hyperparameters grow as in the theorem statement, the KKT conditions gbod satisfies tends to the KKT conditions that g satisfy. Lee. the KKT conditions for
= arg min
log z.
=EP-
Thus, ghbf g"
The steps of the above proofs are laid out as follows.
Subsection
D.I
demonstration of what A is.
Subsection
D.2
definition of Pour and associated BF problem.
Subsection D.3
some properties of BF with Phar, specifically the dual program and KKT
conditions.
Subsection D.4 some preliminaries on log- log-barrier approximations of convex program's feasible region. This will help simplify the argument showing how BBF is related to BF with Poar-
Subsection D3.5 demonstration of how BBF's objective contains log-barrier approximation Pour- It be proven here that -g T log g < -g -g log g where ghar is the solution BF with Pher. This is also where we'll show that bbf has the same functional form as the BF solutions (Lemma 5.1 in Subsubsection D.5.22
Subsection D.6
upper bounding -g harT log har, i.e. deriving the value of B.
Subsection D.7
formal proof of Theorem D.I
Subsection
D.8
proof BBF's consistency (Theorem 5.2
D.1 Bounding the Value of A
Say that the accuracies gotten from labeling dbd is T = Ay From An and Dasgupta 2024 Corollary 28, we know that Ag" b². From that same paper, Lemma 26 provides the following useful identity.
18

---

Lemma D.4. Suppose g = g0 E and v.vl D& are arbitrary.
(y - n') logg = (Ay Auf) 0.
Lemma D.5. A 1110bbs T
goggees كوو to be an upper bound for -n1 log goو we would need Proof. For - T log
T log g bb + logg bb 2
Choosing y and y/ gg from Lemma D.4 the above inequality is equivalent to (b* b) gbbf
where Anj - 6"t and Ag = While that quantity could be non-negative in and of itself, the following bound always holds.
- log goو + 10000 -ō) -n) logg9 d6
The second term the left hand side is our A.
D.2 BF with Polytope Poar
In this section, we want to define class of BF problems by way of polytope with specific form. This will allow us to use techniques associated with the barrier method (an interior point method used solve convex programs, [Boyd and Vandenberghe 2004], Chapter 11) Bayesian BF.
Recall that given the LF predictions and 1). the polytope that BF uses is constructed by bounding the LF accuracies and the class frequency distribution. These bounds can be written linear inequalities where any point satisfying all inequalities lies within the polytope. Moreover, we want to have be in the polytope. Equivalently, want any estimate of L.F accuracies/class frequencies to contain b".
So. say that the LF accuracies/class frequencies estimated by the Bayesian BF solution is b == hbf Pear will defined by taking the constraint b" I A I b" and expanding the bounds until said bounds barely contain b. Specifically, for an arbitrary 1 > 8 > 0 and each E [W + K]. define
4 = 10; > (b) De) + 5 and o = (b2 > We claim that & (b^ - E,,
by ( bt) +
,,- +
For fixed index i, if bg b, then xet), +et
9 b" b. + and c 5.
The thh interval is
(bi - 7 by + + (b) - by T. 6, 8) = (6. - -5.b 5)
which clearly contains b. A similar argument can be made when b, > b and the case of by bद is trivial. Formally, the polytope Poar which brings about par as the optimal BF solution is
Pour E b' - < Az < + t
The BF problem that har the solution as follows
har arg min x log 2.
(8)
25 Pbar
We shall connect the Lagrangian of the Bayesian BF objective (Equation 7 at optimality to the KKT conditions of the above BF problem. Before we do that, we provide an easy example that illustrative of the argument that will be used.
19

---

D.3 Dual Program and KKT conditions for BF with Poar
In this section, we will show the dual problem of the BF problem consideration as well as the KKT conditions. We'll need these in order to relate BBF to BF with Phar
The dual problem is easily derivable following the argument given for BF (following Theorem of An and Dasgupta 2024). D. Say that Ow+ K the zeros vector of length W + K.
Lemma D.6. The dual problem for Equation 8 is
N
K
max 0,0' 0,0220w=
TT (- -ct +o" t (b" (C)- Σ
- log
Σ j=1
exp (IA T (o'
-o'-o)lis) o)lis)
Before stating the KKT conditions for the problem in Equation define E {0, 1] 1]NNNK where [D=]] شー=1 Ztj. The constraint D = In ensures that each of the Et's sum to 1. We will not
need non non-negativyty constraints for each of the Zij 's because their functional form guarantees their non-negativity.
Lemma D.7. The KKT conditions for the BF problem in Equation are:
D 2 b² - 00
[W + K]
((ww)
Uw T + - - S S0, WE [W + K
N(ww)
D) T = ÜN
0, 2 Öw-K
Tw [[Az]u - by ( = 0, w E [W + K]
d' [Az] + bn ()) = 0, w E [ + K]
V= log + to (Az - b" - -ct) o (- Az + b" -c)
+ (Dz [ = ÜNK.
Recall that notation has been abused and that 6" E [0, 1]W WK contains empirical LF accuracies and empirical class frequencies.
D.4 Preliminaries for Barrier Method Type Analysis
The content in this section closely follows Boyd and Vandenberghe (2004) Section 11.2.2. This exposes the general schema of the argument we II use to relate BBF to BF, but there are differences.
Suppose we had convex program
min fo(x)
(w)<0
Aa=b
where x E IRd with feasible constraints. Call this our original problem. we define the indicator
function /_ R + {0, )o} as
0 uf 0
(w)
8o
otherwise,
then the above problem can be written as
p" -in Az
min fo(x) + (f)(x)))
(10)
So long as the program is feasible, the indicator function forces the optimal æ to satisfy the constraint (x) < O. The logarithmic barrier is essentially a relaxation of the indicator function becomes continuous. Namely, /_ (u) can be approximated by
i_ (u) log(-u) u)
20

---

for t > O. which is convex and non -oncesee.., If we say log(0) := oc, I- (u) and I- (u) are defined
on the same domain. We easily see that if u 0 is fixed, then t - 0o, T- (u) (u). We may approximate the problem with the indicator function (Equation 10p with
1
pt)) min fo(x)) (o)(-fi(x)).
(11)
Then, as t - oc, p(t) - p". Call the above problem the log- bog-barrier problem.
Let x" be the optimal solution of Equation Aqquation9amme 9 x (t) be the optimal solution of Equation 11 can show the following result by analyzing the Lagrangian of Equation I1 the point x (t). This argument below is the one we use for our results about g and goar.
One
Lemma D.8. Suppose x² (t) is the optimal solution to the convex program with bog-barrier straints (Equation
1T). Then,
1. x² (t) is primal feasible for the original convex program (Equation 9
2. x² (1) shows the existence of dual feasible variables a(1) - (1) (for fi(() < <) and D (for Ax = for the original problem.
3. fo(x*) S fo( (t)) & +
Proof. Consider the program in Equation 11 at optimality. There, its Lagrangian must have zero gradient at x= (t). We mean that there exists Rd where
v.D(x, v fo(z) log(-fi(z)) DJ (Ar -Trr b) 0zs
when x² (1) is substituted for x. Evaluating, that's
Vfo(2) (I((x(()) (ii(x'()) (1)) AT Ö
Since the original problem has feasible solution. fi (t)) < 0 because that is the only time i_ not infinite or undefined. By assumption, fi (t)) < 0, x (t) is also primal feasible for the original problem. If we substitute x (t) for a (1) for a and for v, we have shown the following equations are satisfied.
so that o(t) = (1 > 0. Because
[1(z) <0
Ar - b= 0
ff((r) E
+f((=)+ofic) + + (Ax --l--)] b)] 0a.
One immediately observes that these are the KKT conditions for the original problem (Equation 9
where instead of the usual complementary slackness condition fi (x) = 0, we have it equal to
We now want to show that att), i dual feasible for the original problem. The Lagrangian for the original problem is
L(,,a, = fo(x) + a (x) + T (Ax - b). The zero gradient condition that satisfied above means that
V (1), da- Since x² (t) is the minimizer of ((,, D), (1) and 2 are dual feasible for the original problem. Now, show the final claim, bounding fo(x= (t)). Because (t) and i are dual feasible, the dual function for the original program at those values is
g(o(t), D) fo(x" (f)) a (t)f((zz(( + TT (Ax" (t) b).
21

---

Because Ar = b is one of the constraints to the log barrier function, the last term is O. By definition, the second term will evaluate to - Thus, g(or(t), 7) fo(ø" (t)) Now, by weak duality,
1 - fo(x").
g(o((), S p- = fo(x") meaning fu(x (t))
This proves the upper bound the third claim. To see the lower bound of the third claim, recall that x= (t) is primal feasible for the original problem and therefore is no smaller than the optimal minimum of the original problem fo (2*).
Because we will use a similar argument for gh and glurr we now draw equivalences for the results in the above Lemma. grarr will be the solution of the "original" convex program while ghb is solution to a problem that implicitly encodes log-barrier constraints. Claim 2 of the above Lemma will imply that /dh/ can be written in the form of BF solution. Claims 1 and 3 will not only aid in our proof of Bayesian BF's consistency, but also show that the entropy of for upper bounds the entropy of g Namely -ghh log gD < -g log gor.
D.5 BBF's Objective has a Log-Barrier Approximation to Poar
In this section, we'll show that the BBF prediction / satisfies a modified version of the KKT conditions of Voar (Lemma D.7). Like in the above section, the only difference is that ga will satisfy a modified version of the complementary slackness conditions. This will be done in two steps. First, we'll ignore the class frequency prior (i.e. suppose that it is constant) and show that BBF with only LF accuracy priors satisfies those modified KKT conditions. Then, we'll extend the argument so the class frequency prior is considered.
So, we start with version of BBF where the class frequency pdf is not considered.
W Σ w=1
lo (N (N(TEe) vitz) + (Puz - 1) log (1-
min SEAR
2 log 2
N( Vw
In restricting to dealing with LF accuracies, we note that the matrix A will have only W rows, one for each LF prediction. To simplify the notation, define the following:
The
V
a'
Pwel -1 1, and 3',
Pw2
N(Tw)
Then, the convex program we first analyze can be rewritten
min #EAN
2 log 2
Σ Joln log (7w( + Ba log (1 - 7w (2))]
(12)
We first argue that b6f is primal feasible for the BF problem with polytope Piar. Then, we analyze the optimal objective of Bayesian BF with LF accuracies (Equation 12h in the lens of the aforementioned problem's KKT conditions (Lemmal) D.7).
Lemma D.9. The optimal solution Mot to the Bayesian BF objective with LF accuracies (Equa- tion 12 is primal feasible for the BF problem with Poar (Equation 8)
Proof. This true by construction Paar. One can follow the argument given Section D.2
Theorem D.10. Fix 1 >> For each LF w E [W], define the following
t 1(b; > (br - 71)) + 8,
et = 1 > b - b%a) + 5,
7t2
1 -t-
bn Bl B-10- + b + att)
og (7rg - bb + a
1
0/1
and Tw
1y (- x + bb - -mm) )
b () - bbt -
22

---

If gho is the optimal solution for Equation 12 where ow Sw > 1 for each w E [W], then the
following deformed KKT conditions of Equation are satisfied.
V
b c+ 1 0,
E [W]
N
Ue + biw -w S 0,
w E [W]
N(Fw)
D2 I, = ÜN
0,0' Z Öw
(w([A2] - by (+) = tw
E [
d (-[[A1)) + +b (w)
[W]
En
(02=0=(2=--0000 (Dz- [w)) ÜNK. V. [z 2ogo a (Az - b² - o (- Az -) + (Dz
Note that w only ranges [W] and not [W + K] (as seen Lemma D.7 because the final K indices for the class frequency constraints, which aren't 't considering right now.
Proof. We argue for this by analyzing the objective of our problem (Equation is very similar to the demonstration argument gave in Lemma D.8
12) at optimality. This
we evaluate the zero-gradee erroggradient condition in the theorem statement, we get
İNK + log + A AT D 5 Ōxk.
(13)
We'll show that the gradient of the Bayesian BF objective (Equation [2] will be of this form. When the BBF objective is at optimality, the following will hold for some R.V.
ÜNK = V. T log z
W
aw
log
(Nww)) )
Fu
+ 3r, log (1 ( N(ww)
Vu==
)
+ + -Tx)
Evaluating,
ÖNK INN + log
W
Yu N(T
8r
Yeu N (TTw)
)
+ DTE
((W V
Now V
where the division is elementwise. Observe that by definition, / (1w) corresponds to row w of matrix A. Le. that term is related to the bound on LF ((wr)ss accuracy. Define
fa = -w + by e and fw = Yw (2) b +
one sets these functions to each be less than or equal to 0, then one can see they represent upper and lower bounds for LF (wr)ss accuracy. Using that notation and multiplying each term in each summand by gives
ŌNK = INK + +log 2 + D
W
Su (z) Tw (2)
+
You (z)
(z)
((w))
(=)
N(Fae
N
Moving forward, we'll replace by bbf and use the following shorthand of 7/ to denote You (gghf)) V g bod (N
Now, define
7/- Bla (i
1' fl (ghh))
and top
0% (2t - 6t + Ew)
Blo + 6" + 6w)
23

---

Using this definition, the above is simplified to
ÖNK- INK + logg thf + + Σ
W
(- N (Nww)
(-
yu
Die (
Ey fi (gbbe)
far (gbbf)
N (Nww))
w=1
Define now
1
du (gbhtt
and 0w
My --1 + by
Gw
Io an (e (gbbf)
two (
6
By Lemma D.9 goوو / E Poar. which means that by construction, (g La (g are both negative. Since aws Sw > 1 for each w E [W] by assumption, the t's are strictly positive. This means that the and o' values are all strictly positive.
We can then write
W Σ d
ÜNK INK + logg ub +
) ow
((w) )
To that this matches the form of Equation 13 observe that yw / (gw w column of A This means have verified the zero gradient condition of the deformed KKT conditions in the theorem statement.
) is the w row of A the
We now verify the remaining conditions. The first three conditions state that / must be primal feasible with respect to the BF problem with Poar That was shown in Lemma D.9 The third condition is a relaxation of requiring g gaوl to be concatenation of N distributions, each over K elements. It is satisfied because g e Ax. defining the o's, we showed that they were strictly positive. Hence, the fourth condition is satisfied. Finally, one see that the modified complementary slackness conditions hold by substituting Yu y g bbf /N (Iww) for [Az], and observing the definition of Ow, du
Remark D.11. It doesn't it matter what the value of & is as these dual variables ensure that the solution BF problem is a distribution, i.c. is in A N. Thus, we will ignore & when talking about BF's dual variables.
D.5.1 Extending the argument for class frequencies
Now, we analyze BBF as presented in Equation 7 Abusing notation, define a' aj The modified version of our objective (coming from Equation 12 is
W
min =EAN
log =
Σ
(Pmm log (mh(()) + (Pw2 - 1) log (1 - Yon (=))]
K
N }
Σ ag log j=1
(14)
The goal show that by adding the last sum, we satisfy a modified version of the KKT conditions with upper and lower bounds the class frequency constraints. Unsurprisingly the addition is 2K more primal constraints, the 2K more dual variables, and a modified zero- zero-gradient condition.
Before stating the result, we remind the reader of some notation and introduce some notation. w ee 7) the empirical class frequency. Let A' be the matrix in {0, 1) where row is J This will make the notation in the KKT conditions simpler. Define ,T(2) NeJ= 2 as the frequency of class j with the labeling. Similar to above, n.J (و9 where we now take /قو to be the solution of Equation Finally, define an = -=j= a'y.
Theorem D.12. Fix 1 > O. For each class j E [K]. define the following
5 = [w] > n. (wF TH)) + C = 1 > ( - wj) + 8,
x;
T/ db(TT w + +
Fg (a) a3) + w + +5))
24

---

1
0/3 0/ [ (,)
and = Ty TT( wj w
Suppose that each element of and ā is smaller than 1. Then, if g gh is the optimal solution to Equation 7 then the following deformed KKT conditions of Equation (found at Lemma D.7 are
satisfied. The U a, o' values as defined in Theorem D.10
N NTTe Vu
6/ cw S 0,
E [W]
w E [W] Vn 2 + 6% cw S
N (F
( 2 w3 5 0
j jE [K]]
1
N / W/ 97 0 0 jE [K]
Dz T, = ÖN
0,0' N Ow
v, 2 ÖK
Tw ([A2]u
by ( =
w E [W]
6' (11=2] by ( ty
[W]
(y([A'z], w/ - (7) =
j E [K]
Tj
c/(([A's),, ww 97
j E [M]
V log - o [Az b* - ( -E-)
(-Ax
o +u (- - T (D2 - -Tn]] = ÖNK-
Proof. We essentially follow the same proof as Theorem D.10 Namely, we choose the same c's, t's, and a's. For this proof, we focus on lines 3, 4, 7, 10, 11, 12. Line 12 is the zero gradient condition, which we start with. The gradient of term in the BBF objective we're we're interested in is
K
Σ
K
a' ReJ=
(- 1
(-N-))
V
a' log
N 8
Once again the division is elementwise. suffices to show that the above is equal the terms involving in the zero-gradient condition because we have shown the correspondence of the other terms in Theorem D.10 By adding we can the above is equal
Σ
K
a'
(-Ne)
1 N
a O'
N
N
NC
Now, define
f;(=)=-<(( + w 9j and 1==)= wj -
Like before, setting these to be less than form the class frequency constraints of BF. Now, it suffices to choose the r's and v's. The above expression can be rewritten as
Σ
K
(2) 1 -f((2)
(- (-Nes + -a66 (=)
(N&))
1
(2)
T2(2)
-f((2)
1=1
As the pero-gradient condition holds for the optimal solution to Equation Then, with x5 = nz (i we define
7 we substitute Abf for
n =
db(Tī - w + (,)
25

---

and
zj (ab
T3
(g
(a6 - af)( w + 55t
The above can then be written as
TylJ( (-Nes) TzSS((Oo)) (tes)
Now, define
v/1 Tfff( and By -== Tzfr(ghhF)
The above simplifies to
Σ -
cj
+
N Ss)
Since row j of A' is defined C., the zero-gradient condition is satisfied.
To see that the 7's and v's non non-negative and that ghd is primal feasible (lines and 4 of the claimed KKT conditions), one can use the argument provided in Theorem D.10 In that same way, the modified complementary slackness conditions are also satisfied.
Corollary D.13. o' defined in Theorem D.10 and v, v' from Theorem D.12 are dual feasible for BF with Pour (Equation 8.
Proof. The zero-gradient condition in the statement of Theorem D.12 states that the Lagrangian,
L(2,0, a,,',,, v, v,,', ,), has to have 0 gradient at the primal/dual optimal variables. Since we have both the primal and dual variables that make the gradient of the Lagrangian zero, it follows that g bbʃ is
the minimizer of the Lagrangian L(:; a, a', v', & for the dual variables from Theorem D.12 This implies that those a, o', U, , E are dual feasible.
D.5.2 db is a prediction
Corollary D.14. bbf can be written in the BF form.
This follows from the zero gradient condition in Theorem D.10 being satisfied quence of Theorem D.12 Le. one solves for as is done in the proof of Theorem in [An and Dasgupta 2024). We have seen that this condition for BF is how one derives the BF prediction format. Because the same condition is met here, bbf has the same form.
Proof.
D.5.3 Relating the Entropy of MM with gar
Like in Lemma D.8. we can bound the value of the objective (zT log 2) when evaluated at gb Corollary D.15. Let bar be the optimal solution to the BF program in Equation &
W
barT log g
bar Σ
L.fT log.g bb$ -g barT log bar
< -
w.
3
for tws fy defined in Theorem D.10 Tj, T/ as defined in Theorem D.12
Proof. To see the second inequality, recall that g bbf is primal feasible for the BF program in Equation 8 while gaar is the optimal solution that program. Le. primal feasibility implies
MiT log Muf 2 ghrr log
For the first inequality, we would like to analyze the difference between our primal feasible solution's objective p6ST log 2 versus the optimal minimum per log bor, By weak duality, g barT log bar
is larger than any dual function value. Continuing from the discussion in Corollary D.13 the (BF)
26

---

U, dual function is equal to Light, ,0, 0' U, .. where the dual variables are defined in Theorem D.10 and D.12 Namely,
g(a, o' goost logg gh +o T - -c) + bb- --" - + + + + - In).
+ v (A'g
By primal feasibility of gh , the last term O. By the modified complementary slackness conditions, the above is equal to
w Σ
K
g /T log bbg
oogg
E
w=
Putting this together with weak duality, we have
+
barT log g bar 2 g BbfT
log 9
bbf
Σ
Σ
L
Rearranging gives claim.
D.6 Error Bound for g gaar
The last piece we need before being able to prove Theorem 5.3 is a bound on - g har We now will show B such that
har
9 T log.gbar bar S -1) log 9" + B.
Since g is the solution of a bona fide BF problem, we can use the analysis of [An and Dasgupta 2024] to get bound in the form we'd like.
Theorem D.16. For gaar the optimal solution of Equation g and some ge E g.
-1) log bar S -1) loggg" ref + 10
where b = Ag
Proof. This proof heavily relies on the proof of Theorem 7 in [An and Dasgupta 2024 It suffices to find the dual of the BF program in Equation 8 then do sensitivity analysis where the reference problem has constraints A& = b*. One is able get the following bound where gref o' and o, 2 O.
-1) log har S -n log + T
Here, the e encapsulates both ex as defined above as well as ç (i.e. since we concatenate the LF accuracies and class frequencies). Then, observe that Aggh bal 8 max(e* . where the absolute value and maximums are done elementwise. Therefore, the above bound can become
" T log bar < -17 go
10
The 8 term disappears because can be arbitrarily small.
In partieular, will choose 9" gre. Corollary D.17.
17 log g Bar -nn log + + --6-6 (00)
Therefore,
B 16 -00 11
27

---

D.7
Formal Proof of BBF Error Bound
Now, we have all the pieces prove Theorem 5.3 We'll explicitly state all the assumptions for completeness. This follows the proof sketch for Theorem D.I provided earlier, but we fill in the missing details.
Theorem D.18 (Theorem 5.3 Fix all LF predictions and n. Also, fix ā B and p R Say
that S the solution to the BBF objective in Equation 7 The error of g is such that
d'g's g) s (10*) 10 6-- Ag
where the absolute value is elementwise.
Proof. Lemma of [An and Dasgupta 2024
shows that
d(n.9'' d(n.g") d(g" 1b)).
So, we have a bound that looks like
d(n. ) z d(n). 9 ) + A + B,
then it's clear that d(g", , S A+ B. This is equivalent to showing a bound of the form
-1 log g bbf $ -7 logg" +A+B.
which we'll now do.
From Lemma
D.5 we know that
-1) log g bbf < /TT logg bbf + /106s/T - Ag
Now, Corollary D. 14 shows that the first term of the RHS above is upper bounded by
barT log gor.
Penultimately, Corollary D.17 shows that
g par log.g". bar
-1) logg" + |Ag - -b%
Putting everything together, we have
-nj logg dbs < -n1 logg" + -10" 10bb/1) - Ag
D.8 Consistency of BBF
An and Dasgupta 2024 showed that it is possible (via Theorem 6) to compute g" the prediction in that minimizes d(n)))). particular, by Theorem from the above paper, g" is the BF prediction when one solves BF with polytope p = f A Az = b*). Recall that for BBF to be consistent, there must be way for prediction to tend to g". Indeed, we'll show that under the correct conditions, BBF can approximate BF with P arbitrarily well. This means that كos g", which is what means to be consistent.
We'll Il prove consistency as follows. First, we'll show that as the BBF priors concentrate in a certain way (or rather the BBF hyperparameters tend to infinity certain way), we'll have Ag - 6* (In particular, we need the LF accuracy (resp. class frequency) priors to concentrate around the empirical LF accuracies (resp. class frequency).) This fact will play an important role ensures all the following things happen. Then, one recalls or observes that Sh can be interpreted as being an approximation to gharr the optimal solution of BF with Poar. It'll then be shown that as Ag b*. a g har At the same time, by the way Poar is constructed, g gaar + g" which means that ghf MS -*
Since we have abused notation in the previous sections, let 0f be aj - where 0j is the jth hyperparameter to the Dirichlet prior in BBF's generative process. Like above, we'll have of = Σj az. (Recall that we had used ag S denote Pw1 L, Pw2 1 respectively.)
28

---

Lemma D.19.
Suppose for each w E [W] and E [K] that d Pw az - 0c. Moreover suppose
that
K
|o' ( + 8wm) + and ai - w
0
8'
Byba
K Σ
d' - 1 by
and
dj
d -
w
j'=1
j'ti
for each w and j. Then, Ag - b"
Proof. To simplify the argument, we'll add the Beta and Dirichlet normalizing factors into the BBF objective. This does not change the argument in a substantial way because of two factors. First, we are concerned with the mode of Beta and Dirichlet distributions, adding or removing the normalizing factor does not change the mode. Second, the proof depends on the fact that the non-entropy terms tend to infinity (whereas the entropy term remains bounded). Removing the normalization terms does not prevent the other terms from going to infinity.
So, abuse notation and say B(a,,3 (3) is the Beta function while B(ū) is the multivariate Beta function. The modified BBF objective that we are considering
W
min SEAR
log 2
Σ
La log (nw(2)) + 8y log (1 - (wo())) - log Pw2)
K
Σ 3=1
o' log (Tz( + log B(ā) (15)
Before getting started, recall that the mode of the Beta distribution is d'y/(al By). Similarly, the jth element of the mode of Dirichlet distribution is a' /o". Moreover, as a' P' of increase, the variance decreases so that the density (and therefore the log density) increases unboundedly. So, suppose that a' & a. are very large (for E [W].j E [K]. Since the BBF objective is minimization, this means that the negative log-pdfs of the Beta (resp. Dirichlet) distributions are small when the value of (z)2) (resp. T. (z)) is close the mode. Moreover, how small these values can get is unbounded below.
Therefore, the optimal cannot just minimize the entropy term. To minimize the BBF objective, the other terms must also be made small. Morcover, minimizing these log-pdfs are the priority since they're re larger in absolute magnitude compared to the entropy term. By assumption, (and with little rearranging), one can see that the mode for the th Beta function (w"h summand) tends to By Similarly, the jth mode of the Dirichlet mode tends to wT. So, to make all the non-entropy terms small, z must be chosen so that Az is close to b* (which one recalls is an abuse of notation and is concatenation of the LF accuracies bü, and class frequencies w.).. Since there is set of 2's such that Az is 'close' to b", one can choose a from that set to minimize the entropy term. Now, a' Fy, oz increase, the pdfs concentrate, meaning Az b² in order for the objective to be minimized.
Now, we show that ك/و + gg
Lemma D.20. Take the same assumptions as Lemma D.19 Then, as Agghs - b², bob - bar
Proof. Recall from our discussion of barrier method type analysis in Subsection D.4 that the comple- mentary slackness condition is what controls how close we are approximating the "original problem'. That is, a convex program with a lor-barrier approximation to a feasible region (f( < 0 in that example) produces an approximate solution the original problem. Reprinting, the following the "original problem':
p²
min fo(Ø) f0
Az=b
29

---

with solution x². The problem with the log- barrier approximation to fi S 0 is
p(() min fo(x) 1 log( (f(())))))
Ar=b
with solution x= (t). The result was that as + oo, (t) as the latter problem approximated the original problem arbitrarily well.
The same idea applies here for our case. To be explicit, what happens is that the problems being solved eventually match, which is why x² x1) + x². In our case, the KKT for the BBF problem will match the KKT conditions for BF with P Pour- Upon inspection of Theorem D.12 must show that tw. ku Ty, Jj each tend to infinity as Ag + ba for the BBF problem and BF with Poor to match (and to prove our claim).
We start with tw and t. Reprinted, they are
T
1 Vic
tw (- + by + c
d' (1
b Ew)
For each of these terms, the denominator has o' or 5,,5, which can be arbitrarily small as is arbitrary. Recall from Lemma D.19 that The yu gh (N + b In particular, we can write Y in terms a and fyn Letting & be term account for the deviation (as [Agh doesn't equal by)),
interested in the case where En 6 6. In the other case,
0' + ay + 8
Tw
b"
Now, by assumption, a',, + bū (" + B.). This means that both a', and a', + tend to (, + +%)) or g a &y, + oo. To reduce clutter, we drop the reference w, noting that all quantities we're dealing with are scalars. Replacing to with the fraction involving &, we have
5 (a + 8') + + + a + 5 (a' + 3" +
a'tC
a'
Recall that was arbitrary, meaning we can absorb anything in front of For the numerator, we can clearly see that it tends to as a' - cc. For the denominator, since a' + tends to b* b' + BB) and can be arbitrarily small, the denominator tends to and l' tends to co. Similarly for two we use 1 Yo = (a + ()( 3' to get
9'
8'
to - - (a' + 3') +
and the same argument from above works, this time using + 0 and a', + 10' + B')
Now, shows that T. = e] g /NN + wÿ. Like before, we write
T, and Ty. which proceeds in very similar way as the above. Lemma D.19
a¹ +
a/j
Since zj wy, and at + wj'y we have & O. As above, we're interested in the case when the denominator not just 6. Written out.
wj.
x; db( - w/ +
3 w +8) (a,, + obw +
+5 a6( o
The numerator tends to constant while the first three terms in the denominator tend to 0 while can be made arbitrarily small. Hence TJ
oc.
To see that Ty also tends to infinity, observe that of ab -aj. that can apply the above argument with very minor changes.
Theorem D.21 (Theorem 5.2 Under the conditions of Lemma D.19 BBF consistent. Le. godl g" This happens because goof 0".
30

---

Table 3: Comparison of our proposed method with baseline methods with respect accuracy. Bolded entries are indistinguishable via two-tailed paired t-test with = 0.05.
Dataset
IMDB
YnuTuhe
SMS
CDR
Yelp
Commercial
Tennis
TREC
SemFvall
ChemProt
AG News
MV
73.68
$5.02
93,94
72.36
72.38
90.61
86.85
51.51
79.07
51.67
81.38
DS
50.31
$3.88
87.18
45.17
72.97
93.57
86.54
47.86
73.53
52.66
81.79
DP
72.75
74145
81.52
64.41
57 86
89.79
86.37
45.85
72.78
56.17
81.71
74.45
$3.
91.90
73.62
74.01
87.31
85.95
50.10
12.15
52.37
81.28
MeTaL
72.43
70.54
79.67
60.20
54.47
89.79
86.57
43.73
54.58
55.86
81.84
iBCC
71.11
15.69
84.55
60.92
68.30
83.31
87.19
21.02
30.19
35.09
26.57
EBCC
T4.43
84.35
62.98
69.65
83.31
87,30
21.02
30.19
35.09
CLL
72.77
$5.19
93.86
71.24
72.01
19.99
19.92
59.31
84.21
52.37
80,97
HyperI.M
75.03
90.99
93.88
72.58
74.42
88.20
87.20
60.02
84.21
52.32
81.38
WeaSEL
50.49
60.81
54.13
51.64
57.16
15.15
57.79
20.81
11.14
21.41
32.29
Denoise
80.26
81.45
94.02
73.17
75.04
94.24
76.87
49.81
73.53
57.85
87.61
FABLE
72.16
S7.71
93.94
71.64
69.11
92.55
86.56
53.64
73.61
51.42
81.38
BBF
72:47
89.47
93.86
71.29
71.81
90.85
84.56
59.88
84.21
52.47
81.40
g"
74.50
93.92
93:90
76.52
74.77
93.59
86.64
63.75
Proof. We have just proven in Lemma D.20 that /b + goar It suffices to show that under the assumptions of our claim, ghar + g"
To do that, it suffices to show that Pour P (=e A A: b*} under the assumptions of the theorem statement. This is because An and Dasgupta (2024) showed Theorem that solving BF with P gives g". Recall that Pa Paar was defined as follows:
Porr E=E - 5
It would suffice to show that ct,E both converge to O. We now remind the reader of the definitions of e and - For [W K] and by [Aghb]]..
G = 1 (b) by) + and 1 6,)0,0))000
6.
By definition, at least one of these is equal to 8, which is some arbitrary but small positive number. In Lemma D.19 we showed that b; + bj. Thus, given the assumptions of the theorem, e e, are each either already 8, tend ö. This means that every element in e and is arbitrarily small, showing that Pour + P* as the BBF hyperparameters grow. As BBF is essentially solving the BF problem that gives g", gh
bbf will have the same weights as g", i.c. gbbf + 8".
E Extra Experimental results
In this section, present extra experimental results. Specifically, the accuracies of label models for which scores were reported in the main paper and the standard deviations the scores and 0-1 losses reported. Also, present the BBF consistency experiments for all datasets used in the main paper.
E.1 0-1 Loss and Standard Deviations
In the main paper, followed Zhang al. (023) and included mix of F1 scores and 0-1 loss depending on whether the dataset had two classes. Here, we provide the accuracies achieved by each label model on every dataset, regardless of whether there are classes or
In Table 3 we see the accuracies of our proposed method and the other baseline methods. Against FABLE, our proposed method has similar or better performance most datasets. On Commercial, Tennis, and ChemProt, the performance of BBF was slightly worse than FABLE. With respect to HyperLM, BBF similar better the majority of datasets, only being worse IMDB, YouTube, CDR, Yelp.
Here are the standard deviations for Fl score (Table 4 and 0-1 loss (Table For brevity, we only show standard deviations for methods that had randomness. We see that WeaSEL had the largest standard deviation while the standard deviation for other methods were not very large.
31

---

Table 4: Comparison of Fl score standard deviations for random baseline methods.
Dataset
IMDB
YouTube
SMS
CDR
Yelp
Commercial
Tennis
DP
0.07
1.50
0.73
7.63
1.66
0.00
0.00
MeTaL
0.16
0.00
0.73
6.18
0.45
0.00
0.00
EBCC
0.00
0.00
0.00
0.00
0.03
0.00
0.02
WeaSEL
10.89
6.67
6.29
13.42
7.77
4.63
17.22
Denoise
1.13
0.43
0.38
0.10
1.33
1.06
41.74
FABLE
0.26
0.37
0.00
0.16
0.16
0.23
0.06
CLL
0.00
0.00
0.00
0.07
0.00
0.15
4.02
Table 5: Comparison of accuracy standard deviations for random baseline methods.
Dataset
IMDB
YouTTube
SMS
CDR
Yelp
Commercial
Tennis
TREC
SemEival
ChemProt
AG News
DP
0.16
2.63
0.55
1.92
3.90
0.00
0.00
0.80
0.25
0.46
0.25
McTaL
0.16
0.00
0.47
1.23
1.01
0.00
0.00
1.96
3.45
0.51
EBCC
0.00
0.00
0.00
0.00
0.04
0.00
0.06
0.00
0.00
0.00
0,00
WeaSHI
4.68
7.63
12.11
5.73
3.68
8.93
5.84
3.40
2.16
4.91
2.69
Denoise
1.24
0.34
0.11
0.11
2.27
0.51
13.99
0.08
0.00
0.20
Fable
0.28
0.33
0.00
0.06
0.11
0.03
0.17
0.24
0.68
0,01
CLL
0.00
0.00
0.00
0.05
0.01
0.11
5.07
0.01
0.00
0.00
0.03
E.2
Experimental Results for BBF's Consistency
this section, we present experimental results showing the consistency of BBF on real datasets. The eleven datasets used in the main paper are considered again in the same setting we allow BBF to label all datapoints (by combining the provided train/ validationtts splits). Recall from our previous section that for hbf + g", need the prior distributions for LF accuracies and class frequencies to concentrate around their empirical values. This is done by using the labels of the datapoints to compute bt and wj. The hyperparameters for the Beta distributions
set with scale factor
Pwil =b
Pw2 s(1 b%h + and a2 sw
One is added so the conditions of Lemma D.19 are satisfied. We vary the scale by taking values in {101 100} for trials total for each dataset. To check for consistency, we measure the average KL divergence between Abf and Namely, N d(n, g =b)). The provided graphs have log-log scale and show that the rate of convergence is linear.
32

---

A gg
KL Divergence
101
10a
10a
Hyperparameter Scale (s)
Figure Convergence of gh to g" on the IMDB dataset with respect to scale factor s.
ddlg".gua
10-1
KL Divergence
10
10-3
101
10a
10a
Hyperparameter Scale
Figure 3: Convergence of bbf to g* on the Youtube dataset with respect to scale factor s.
33

---

hdlg"
10-1
KL Divergend gencee
10-2
10-3
101
10a
10a
104
10a
Hyperparameter Scale
Figure Convergence of 5b4 g" on the SMS dataset with respect to scale factor
à "dtt".@eo
2 10-1
KL Divergence
10-1
10-2
10a
10a
10
10*
10*
Hyperparameter Scale (s)
Figure 5: Convergence of كو to g" on the CDR dataset with respect to scale factor
34

---

hdlg".guu
10-1
KL Divergence
101
102
10a
104
10a
Hyperparameter Scale
Figure 6: Convergence of gb g" on the Yelp dataset with respect scale factor
40
3x-10
KL Divergence
2.x 10
10-1
10a
10
10
10*
10*
Hyperparameter Scale (s)
Figure 7: Convergence of كوو to g" on the Commercial dataset with respect to scale factor
35

---

10-1
KL Divergence
10-2
10
101
10a
10a
Hyperparameter Scale (s)
Figure 8: Convergence of gh to g" on the Tennis dataset with respect to scale factor s.
gdlg".gua
KL Divergence
10-2
101
10a
10a
Hyperparameter Scale
Figure 9: Convergence of g bbf to g" on the TREC dataset with respect to scale factor s.
36

---

10
KL Divergence
10-2
101
10a
10a
Hyperparameter Scale (s)
Figure 10: Convergence of g hbf to g" on the SemEval dataset with respect to scale factor s.
gdlg".gua
100
XL Divergence
10-1
101
10a
10a
Hyperparameter Scale
Figure 11: Convergence of Ahf to g" on the ChemProt dataset with respect to scale factor s.
37

---

KL Divergence
10A
10a
10a
Hyperparameter Scale
Figure 12: Convergence b6t to g" on the AG News dataset with respect to scale factor s.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have ensured that the abstract's scope/claims matches the scope and claims the main paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have included section on limitations at the end of the main paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
39

---

Justification: We provide informal statements and provide motivation for why our claims are true in the main paper. the Appendix, the complete formal statement and proof are included for every theoretical result. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have stated the hyperparameter settings when they deviate from the default and also noted when the defaults were used. We have also stated the package versions for packages that perform functions that affect the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
40

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The exact code and hyperparameter settings used to produce the results is provided the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
publit//giide//Cdeettbbmsss ios.essoabiiiioooooooiooo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips //iiss.c/ppul
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We have provided all details needed to reproduce the results stated in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We performed two tailed paired t-test with 0.05 when comparing the performance models that were random in nature (Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
41

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The relevant hardware specifications for the computer used were stated in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpu://neurips. cc http:///s....ppbiieiccccccccceee
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics and our work conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This work is mainly theoretical in nature and does not have direct paths to negative applications/negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
42

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [No]
Justification: We do not believe that the model described in this paper is one that has a high risk for misuse because is method combine existing classification models. We also do not release any data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have cited the original papers for code packages in the main paper and included their licenses. For the datasets we use in this paper, they are all repackaged, though we include the original license if we found it online.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
43

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code used to run the paper along with documentation on how to set it up is included in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper did not do any crowdsourcing, nor did it do research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper did not do any crowdsourcing, nor did it do research with human subjects.
Guidelines:
44

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not used in any capacity for any aspect of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy hett:ee//earrpps.cc//oofeeeeeree for what should or should not be described.
45


Reviews:
[{"review_id": "P0TyzX60Gu", "reviewer": "Reviewer_uvqR", "summary": "This paper introduces the BBF method (for Bayesian Balsubramani-Freund), an unsupervised Bayesian label model for weak supervision, where inputs $x_i$ with unknown labels $y_i$ are annotated by multiple noisy label functions (LFs). It weights the various LF to create a posterior on the $y_i$, by first drawing class priors, sampling latents $(y_i)$, and compute accuracy posterior for each LF on these latents before combining them in some adversarial fashion.\n\nThe method comes with theoretical guarantees and offers decent empirical performance.\nIf I understand correctly, Theorem 5.2 states that, if the class prior is a Dirac on  the right class proportion and if the accuracy posterior for each LF concentrates to the right one, then this method find the optimal blend of the LFs (based on the KL divergence to the true labeling). Theorem 5.3 seems to offer some speed for this convergence, it seems to corresponds to how much the estimated accuracies of the LFs implied by the model (which is captured by $Ag^{bbf}$) matches the true ones ($b^*$).", "questions": "How would this paper potentially lead to a groundbreaking finding?", "limitations": "Yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n- A method with theoretical guarantee and decent empirical performance.\n\n**Weaknesses**:\n- It was hard for me to follow the paper, understand the motivations of both the setting, and the various steps in the algorithm.\n- The empirical results are decent but not groundbreaking\n- I do not really know how \"nice\" the consistency and convergence results are, they seems to depend on quite restrictive assumptions. Basically, it is assumed that the priors having already done the heavy lifting. And the convergence result is more of a \"calibration result\" as per Bartlett et al. JASA 2006 (with this paper in mind, the consistency result can be viewed as a \"Fisher consistency\" result)", "was_revised": true, "final_justification": "While I appreciate the authors effort to answer my concerns, I still have trouble to \"get it\" and understand why this paper matters. I do not doubt that this paper is technically solid, but motivations and clarity should be improved imho in order to meet the NeurIPS bar.", "rebuttal": "Thank you for your time and effort in reading our paper and writing this review.\n\nWith respect to the experimental results, we would like to provide more context/some alternate perspectives and discuss how they might inform future research.  We provide three perspectives and then discuss them together.  \n\n**Bayesian**: Bayesian Balsubramani-Freund (BBF) shows that one does not need to create more complex generative processes to improve performance.  Out of the Bayesian label models we are aware of in the literature, FABLE [1] is the best.  BBF is quite competitive with FABLE and is often better despite the fact that it has a very simple model for labeling functions (LFs) and uses less information.  Specifically, FABLE models each LF with *multiple* confusion matrices (of size \\\\(K^2\\\\) each) and also uses the datapoint *features* \\\\(x_i\\\\).  Compare that to BBF which uses models an LF by its accuracy only and only uses the LF predictions \\\\(h^{(w)}(x_i)\\\\) and does *not* use the datapoint features.  (The other Bayesian models do not use datapoint features. iBCC [2] models each LF as a single confusion matrix, while EBCC [3] models each LF w/multiple confusion matrices.)\n\n**Adversarial**:  In the last row of Table 2, we see \\\\(\\vec{g}^\\*\\\\), the best approximation of \\\\(\\vec{\\eta}\\\\) in KL divergence.  We’ll take that as a proxy to the best possible F1 score/0-1 loss that can be achieved by BBF.  For many of the datasets, we see that even \\\\(\\vec{g}^\\*\\\\), the best case scenario for BBF, is still not good enough to beat Denoise.  In other words, the ceiling for BBF’s performance is too low if the goal is to always beat Denoise in performance. Thus, we would need to raise the ceiling,  This is done by modeling the LFs in a more complex way.   I.e. have more general constraints (and not just a constraint on an LF’s accuracy).  For example, Mazuelas et al. [4] provide a framework to accommodate more general constraints.  BBF is a good first step — being competitive with Denoise, a label model that is a neural network that uses the datapoint features \\\\(x_i\\\\) as part of its input, something BBF doesn’t have.   \n\n**Improving labels models in general**: BBF can be thought of as a member of the class of label models that use the “HyperLM strategy” of selecting a labeling.  Specifically, it constructs a polytope of labelings then picks something inside of it.  BBF’s empirical performance, in our opinion, shows that it is a decent if not good representative of the “HyperLM strategy”.  This gives credence to the idea that analyzing BBF theoretically will help us get a formal grasp on what the “HyperLM” strategy is.  In our case, reducing it to a mix of Bayesian/adversarial label model.\n\n**Discussion**: One direction of research is to change the generative process of BBF to make it more complex.  One possible route to follow is to create analogues of iBCC, EBCC, and even FABLE.  (Mazuela’s [4] formulation the polytope of labelings is quite general and many other approaches can be taken.) The hope is that this will raise the ceiling of performance enough so that the resulting label model can exceed Denoise’s performance.  In a more abstract direction, we hope that our theoretical contributions will provide more insight on the “HyperLM strategy”, which in turn may lead to new label models that use the same strategy but have better performance than Denoise.   All in all, BBF’s experimental results provide another piece of evidence that there is still more work to be done in the scenario where label models are only given LF predictions and *not* datapoint features.   \n\n————\n\nWith respect to consistency our consistency result, we would like to provide more context.   The majority of label models proposed in the Programmatic Weak Supervision setting are probabilistic in nature.  And as we are interested in adversarial label models, we wish to see them used in practice more.  However, one of the concerns for adversarial models is that they may be too pessimistic.  One line of argument one can provide is via consistency/convergence results, e.g. like from our paper or from An and Dasgupta [5].  Those results show that as the estimates for LF accuracies (and class frequencies) get more and more accurate, the outputs of BBF and Balsubramani-Freund (BF) improve.  Thus, anyone considering using either model knows that they do reasonable things.  \n\nIn particular, An and Dasgupta [5] use the consistency result for BF to show that there doesn’t exist a problem (a set of LF predictions and underlying label distribution (\\\\(\\vec{\\eta}\\\\)) where BF is always outperformed by the Dawid-Skene model [6].  \n\n[1] Zhang, J., Song, L., Ratner, A., Leveraging Instance Features for Label Aggregation in Programmatic Weak Supervision, AISTATS 2023\n\n[2] Kim, H.-C. and Ghahramani, C., Bayesian Classifier Combination, AISTATS 2012\n\n[3] Li, Y., Rubinstein, B., Cohn, T., Exploiting Worker Correlation for Label Aggregation in Crowdsourcing, ICML 2019\n\n[4] Mazuelas, S., Romero, M., Grunwald, P., Minimax Risk Classifiers with 0-1 Loss, JMLR 2023\n\n[5] An, S. and Dasgupta, S., Convergence Behavior of an Adversarial Weak Supervision Method, UAI 2024\n\n[6] Dawid, A. P., Skene, A. M., Maximum Likelihood Estimation of Observer Error-Rates Using the EM Algorithm, Applied Statistics 1979"}, {"review_id": "12y9qH14UE", "reviewer": "Reviewer_nt5S", "summary": "This paper introduces a Bayesian label model for programmatic weak supervision. This approach (named BBF) combines the polytope‐center strategy of HyperLM with the minimax guarantees of Balsubramani–Freund in a fully unsupervised Bayesian approach. \n\nThe authors first show that BBF has a log-concave posterior distribution over labels. They also show that the learned solution of their approach is contained within an exponential family of weighted combinations of weak labeler outputs. The authors provide consistency guarantees on their approach.", "questions": "Q1: Can you provide guidelines for choosing the hyperparameters for each of the priors in practice? \n\nQ2: Could the authors compare against some subset of the minimax based approaches, assuming a fixed constant accuracy for each labeler (e.g., say 0.75 for binary classification tasks)?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n* The provided Bayesian approach is well motivated and the authors provide a theoretical analysis on (a) what the posterior form is and (b) the consistency of the resulting method.\n\nWeaknesses\n* The authors only show consistency when the priors of labeler accuracies concentrates around the empirical accuracy. While the authors claim this approach to be fully unsupervised (contrasting with prior minimax approaches that require labeled data to compute labeler accuracies), this consistency only arises when priors are properly specificed – which would indeed likely require labeled data without other domain knowledge.\n* Lack of discussion with [1, 2], which both are relevant constrained optimization or minimax approaches (albeit not Bayesian in nature) in PWS and both provide guarantees\n* No comparison with any of the minimax-based approaches above or in the related work – while their formulation does require labeled data, they can be run assuming a fixed accuracy as a hyperparameter, which is not too dissimilar from specifying the uniformative prior distributions in BBF; I believe such an experiment would greatly strengthen the support for using such a proposed Bayesian approach for PWS\n* As highlighted by the authors, scalability is a concern – the number of parameters of the approach scales with the input data, which is certainly undesirable\n* Empirically, the performance of the approach isn’t that strong – it’s almost always outperformed by HyperLM and does not noticeably improve upon the MV baseline\n\n[1] Arachie, et. al. Constrained labeling for weakly supervised learning.\n\n[2] Mazetto, et. al. Adversarial multi class learning under weak supervision with performance guarantees.", "was_revised": true, "final_justification": "While the authors provided some clarifications in the rebuttal, I still feel that the framing of the paper around how the approach doesn't require labeled data, while alternative adversarial PWS approaches do to estimate labeler accuracies, is incorrect. The paper requires pre-specifying a prior distribution around LF accuracies (which can only be estimated with labeled data for a principled approach). The author's argument about empirical performance can similarly be made about [1], and no empirical comparison with [1] is made. As such, I choose to maintain my score as a borderline reject: there are interesting contributions from the paper, but the claims about how the method do not require labeled data while every other adversarial PWS approaches do is **too strong**, and the paper lacks comparisons to such approaches.\n\n[1] Arachie, C. and Huang, B., Constrained labeling for weakly supervised learning.", "rebuttal": "Thank you for your time and effort in reading our paper and writing this review.\n\n**With respect to points made in the weaknesses section:**\n\nWe will add some discussion to the paper with respect to the papers you bring up.  \n\nArachie and Huang [1] provide a guarantee, though it only holds when the empirical LF error rate is known, our \\\\(b^\\*\\\\).  In that paper, they are silent about how the performance of their method changes as the quality of the LF accuracy estimate improves.\n\nMazzetto [2] is going for a more classic generalization bound scenario where the points are drawn iid.  Our bound is more general insofar as that requirement is not necessary for the proof to work.  Moreover, the setup for their minimax game is more akin to the setup of Balsubramani-Freund [3] rather than HyperLM's. \n\n**With respect to your questions:**\n\n**Q1:** \nIf one has labeled data at their disposal, they may use those to instantiate the Betas/Dirichlet priors. E.g. lets say a labeling function (LF) gets \\\\(v_w\\\\) out of \\\\(v\\\\) labeled points correct.  The Beta prior for \\\\(h^{(w)}\\\\)'s accuracy could be \\\\(\\rho_{w1} = 1+v_w\\\\), \\\\(\\rho_{w2} = 1+(v-v_w)\\\\).  If there are no labeled datapoints available, one can use our choices of hyperparameters (\\\\(\\rho_{w1} = 4\\\\), \\\\(\\rho_{w2} = 1\\\\)), which was also used by EBCC [4] and seems to work well.  One pitfall to avoid is to have the hyperparameters be too large in size when there is no guarantee that it is tending toward the empirical accuracies.  This can happen if one uses the majority vote (MV) labeling as the ground truth.  For example, say that \\\\(h^{(w)}\\\\) gets \\\\(m_w\\\\) points “correct” when using the MV labeling as the ground truth.  One could instantiate the Beta hyperparameters as \\\\(\\rho_{w1} = 1+m_w\\\\), \\\\(\\rho_{w2} = 1+(N-m_w)\\\\) which will give you a bad result.  This is consistent with the theory because if $N$ is large, then the Beta is very concentrated and the resulting BBF prediction will have accuracy close to \\\\(A\\vec{g}^{MV}\\\\), \\\\(\\vec{g}^{MV}\\\\) being the majority vote labeling, which might be far from \\\\(b^\\*\\\\), the empirical accuracies of the LFs.  This also holds true for instantiating the Dirichlet hyperparameters for the class frequency distribution.  The strategy of using the majority vote labeling to instantiate the Dirichlet hyperparameters is done in EBCC and won’t work for our method.  \n\n**Q2:** We can’t just set the accuracy to 0.75 and run these adversarial methods that need accuracy estimates.  As Arachie and Huang [1] note, this will result in an infeasible problem.  This is akin to having an underdetermined system \\\\(Ax=b^\\*\\\\) and trying to propose a new RHS \\\\(b\\\\) that will ensure the system has >=1 solution.  For the methods that have been discussed it seems that Arachie and Huang's method is the only one that can tolerate choices arbitrary choices accuracies.  That is, they learn some labeling \\\\(\\vec{g}^{CLL}\\\\) by minimizing \\\\(||A\\vec{g}^{CLL}-b||_2^2\\\\).  For Balsubramani-Freund (in An and Dasgupta [5]) and Mazzetto et. al. [2], the feasible set cannot be empty as they choose predictions from the set of \\\\(x\\\\) that satisfy \\\\(Ax=b\\\\).   Moreover, the size of the feasible set heavily influences the performance of the method.  E.g. suppose we started with \\\\([0.75, 0.75]\\\\) as our accuracy interval for each LF and widened it until the the feasible sets for BF/Mazzetto et. al. become non-empty.  That’s akin to choosing \\\\(\\epsilon_w\\\\) for each LF to get intervals of \\\\([0.75-\\epsilon_w, 0.75 + \\epsilon_w]\\\\).  From our own toy experiments, the size of \\\\(\\epsilon_w\\\\) heavily affects the performance of BF.  E.g. for \\\\(K=2\\\\) classes, if the accuracy interval is too wide, then the resulting max entropy solution will be close to the uniform label distribution.  In that case, if the intervals are so large that accuracies of \\\\(0.5\\\\) are included, choosing the uniform label distribution will satisfy the constraints and give the maximum entropy.   How to choose the \\\\(\\epsilon_w\\\\)'s without any labeled data while maintaining good performance is an interesting but, in our opinion, difficult open question.  \n\n[1] Arachie, C. and Huang, B., Constrained labeling for weakly supervised learning, UAI 2021\n\n[2] Mazzetto, A. et. al., Adversarial Multiclass Learning under Weak Supervision\nwith Performance Guarantees, ICML 2021\n\n[3] Balsubramani, A. and Freund, Y., Optimally Combining Classifiers Using Unlabeled Data, COLT 2015\n\n[4] Li, Y., Rubinstein, B., Cohn, T., Exploiting Worker Correlation for Label Aggregation in Crowdsourcing, ICML 2019\n\n[5] An, S. and Dasgupta, S., Convergence Behavior of an Adversarial Weak Supervision Method, UAI 2024"}, {"review_id": "bsx3LG6Mqw", "reviewer": "Reviewer_K6Pv", "summary": "The paper theoretically studies a new label model that is neither probabilistic nor adversarial but performant in practice by proposing BBF. A series of statistical results are presented for BBF, including log-concavity of its posterior, consistency and rates of convergence. Empirically, BBF compares favorably over other label models. Overall, the paper offers valuable theoretical insights of a new category of performant label model, and proposed a practical method, it makes a solid contribution both theoretically and empirically.", "questions": "see W1", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strong points:\n1. The paper offers novel theoretical insights into HyperLM’s strong performance in real-world by proposing Bayesian Balsubramani-Freund (BBF). This make a solid contribution to the programmatic weak supervision field as this is the first theoretical analysis of a new category of label model that is performant in practice.  \n2. The paper shows BBF has some nice properties including log-concavity of posterior, form of exponential family solution, consistency, and rates of convergence.\n3. Writing is clear and also strong empirical results are also shown.\n\nWeak points:\n1. I did not find any major weakness for this paper and one minor point is that, in experiments, since some methods involve randomness, it would also be nice to present the variance as in practical applications variance is also important.", "was_revised": true, "final_justification": "paper looks good to me.", "rebuttal": "Thank you for your time and effort in reading our paper and writing this review.\n\nWe will include a table in the Appendix of the standard deviations of the errors (as that is what was recorded).  The standard deviations are already in the Supplementary Material, but one has to go dataset by dataset, label model by label model.  We have however consolidated them into one table which we paste below.  Label models which are deterministic have their rows omitted.\n\n\t\\begin{tabular}{cccccccccccc}\n\t\t\\toprule\n\t\tDataset & IMDB & YouTube & SMS & CDR & Yelp & Commercial & Tennis & Trec & SemEval & ChemProt & AGNews \\\\\n\t\t\\midrule\n\t\tSnorkel & $0.07$ & $1.50$ & $0.73$ & $7.63$ & $1.66$ & $0.00$ & $0.00$ & $0.80$ & $0.25$ & $0.46$ & $0.25$ \\\\\n\t\tMeTaL & $0.16$ & $0.00$ & $0.73$ & $6.18$ & $0.45$ & $0.00$ & $0.00$ & $1.96$ & $3.45$ & $0.51$ & $0.26$ \\\\\n\t\tEBCC & $0.00$ & $0.00$ & $0.00$ & $0.00$ & $0.03$ & $0.00$ & $0.02$ & $0.00$ & $0.00$ & $0.00$ & $0.00$ \\\\\n\t\tWeaSEL & $10.89$ & $6.67$ & $6.29$ & $13.42$ & $7.77$ & $4.63$ & $17.22$ & $3.40$ & $2.16$ & $4.91$ & $2.69$ \\\\\n\t\tDenoise & $1.13$ & $0.43$ & $0.38$ & $0.10$ & $1.33$ & $1.06$ & $41.74$ & $0.08$ & $0.00$ & $0.20$ & $0.47$ \\\\\n\t\tFABLE & $0.26$ & $0.37$ & $0.00$ & $0.16$ & $0.16$ & $0.23$ & $0.06$ & $0.47$ & $0.24$ & $0.68$ & $0.04$ \\\\\n\t\t\\bottomrule\n\t\\end{tabular}"}, {"review_id": "Q8yTTGaCcC", "reviewer": "Reviewer_BbRK", "summary": "The paper suggests BBF, a label model that aggregates labeling functions predictions for weak supervision.\nThe paper investigates the model theoretically and empirically.\nIn empirical evaluation the model outperforms other Bayesian label models.", "questions": "The assumptions on the labeling functions themselves are not clearly given.\nShould they all be weak classifiers?\nSchapire, Robert E. \"The strength of weak learnability.\" Machine learning 5 (1990): 197-227.\nShould they be independent given the concept? Any other constraint preventing using the same labeling function ten times?\n\n\nAssumptions never exactly match reality.\nIt will be interesting to add lower bounds of the models on the datasets and their comparison to actual performance in Table 2.\n\nThe EM algorithm influenced the entire area, via Dawid & Skene and more. \nIt will be nice to add a comparison to it.\nEspecially, is the process a single step or iterative?\nDempster, Arthur P., Nan M. Laird, and Donald B. Rubin. \"Maximum likelihood from incomplete data via the EM algorithm.\" Journal of the royal statistical society: series B (methodological) 39.1 (1977): 1-22.\nDawid, Alexander Philip, and Allan M. Skene. \"Maximum likelihood estimation of observer error‐rates using the EM algorithm.\" Journal of the Royal Statistical Society: Series C (Applied Statistics) 28.1 (1979): 20-28.\n\nThe learning framework is not clear.\nYou report F1 which requires labels, yet possibly after the modeling, which is OK.\nHowever, you mention using accuracy in the modeling yet write “No labeled data is provided to the label models.”\nIf you need labels in the modeling, this is a semi-supervised framework so please specify how many labels are needed.\nIf you use a different method (e.g., disagreement minimization Amit, Idan, Eyal Firstenberg, and Yinnon Meshi. \"Framework for semi-supervised learning when no labeled data is given.\" U.S. Patent No. 11,468,358. 11 Oct. 2022.) then the term accuracy is confusing and method should be explained more.\nIf it is simply accuracy with respect to a proxy, it should be written when accuracy is used.\n\nHyperLM and Denoise share the top results.\nIt will be beneficial to try and explain the intuition of these results.\nIt is especially interesting since it seems that when one of the models is not the top performer, its performance tends to be very bad.\nIt hints that the datasets differ in some properties with a large impact on performance.", "limitations": "See weaknesses", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The authors do a mathematical analysis of their model.\nOn the other hand they also do intensive empirical evaluation.\n\nThe benchmark uses many models and datasets, and the method shows improvement over Bayesian models.\n\nAssumptions, setting,  and therefore the proof are not presented clearly.\nI tried to point out a few unclear points.\n\nAlso, there might be certain assumptions and constraints of the models used in the benchmark, hence their straight forward usage might be under performing.\nFor example, “On Tennis, the three LFs that each predicted on 99% of the datapoints closely matched each other” hints that the labeling functions are not conditionally independent given the concept. Hence, performance might be better on a subset of the functions.\n\nA general comment, not part of the judgment:\n“then regardless of what h(w) predicts, its accuracy can only be 1/K.” - Isn’t it since some labels can be positive for a sample yet the LF can hit only a single label?\nIf so, adjusting them might help improve performance and bound.\n\nI like the paper and I think that its weaknesses can be taken care of during the rebuttal.\nIf so, I’ll be happy to accept.", "was_revised": true, "final_justification": "Clarity was the main problem, now being resolved.\nHence, I'm happy to change my recommendation to accept.", "rebuttal": "Thank you for your time and effort in reading our paper and writing this review.\n\n**Paper formatting concerns**\n* For concerns not explicitly addressed here, we will take your suggestions and revise the paper.  \n* We showed the F1 score to follow the FABLE paper [1].  We have recorded the accuracies in the Supplementary Material (code/results/error_tables.txt) and will add a table in the Appendix wherein only the accuracies will be reported.\n* Class frequency distribution is just class probability\n* Whether or not a labeling with higher accuracy is more likely to be selected than one of lower accuracy depends on the prior accuracy and the generated label.  Once an accuracy \\\\(b\\\\) has been generated for an LF, the only labelings with accuracy \\\\(b\\\\) can be generated.\n* We favor labelings with high entropy so that the posterior label distribution has a unique mode.  That is, the prior distributions and LF predictions define the polytope that BBF is implicitly constructing.  We want to somehow define a point in the interior and having the label distribution be proportional to its entropy is one way of achieving this in a non-ad hoc fashion.  I.e. suppose that the BBF priors were super concentrated.  Then, the implicit polytope being constructed by BBF looks like  \\\\(A\\vec{g} = b\\\\) for some vector of LF accuracies \\\\(b\\\\).  If the labelings were not proportional their entropy, then the posterior label density would have equal density on every \\\\(\\vec{g}\\\\) satisfying that equation. \n* We will add a line in Table 2 for difference between best method & majority vote.  \n* With respect to the addition of a supervised model, we would contend that the last line in Table 2 is similar in spirit.  It is the best possible labeling that Balsubramani-Freund (BF) or Bayesian Balsubramani-Freund (BBF) can output.  Further all datapoints with labels (known to us) in the datasets are given to the label models we tested.  I.e. we merged the train/test/validation splits a la FABLE [1] and gave the models the labeling function (LF) predictions on those datapoints (and datapoint features \\\\(x_i\\\\) if the label model could use them).  Thus, we don’t think we can give an apples to apples comparison with a supervised method without doing a split on the merged dataset and rerunning all the experiments.  Something similar to what you’re suggesting was done in [2].  There, BF performed quite well against supervised methods where each method was given the same training data.\n\n**On the weaknesses you bring up**\n* There are no assumptions on the labeling functions, except that they predict on at least 1 datapoint.  Since we show that BBF's solution (i.e. the posterior labeling's mode) is the solution to a slightly deformed version of the Balsubramani-Freund (BF) model's KKT conditions, one can have as many duplicates of LFs as they would like without harming the model performance.  \n* We agree it would be interesting to see lower bounds for each model’s performance.  Unfortunately, we are not aware of any.\n* We provide a row in Table 2 for Dawid-Skene (DS) where EM is run to convergence.  An and Dasgupta [3] provide a theoretical comparison between (BF) and the one-coin version of DS (each labeling function (LF) is modeled as a biased coin) where 1 E step is taken to get the DS prediction.  In particular, the two methods draw their predictions from the same set and BF’s consistency implies there is no problem (set of LF predictions and underlying label distribution \\\\(\\\\vec{\\\\eta}\\\\) where DS always outperforms BF.\n* The learning framework is as follows.  We are given datapoints \\\\(\\\\{x_1, \\\\ldots, x_N\\\\}\\\\) and some LFs \\\\(h^{(1)}, …, h^{(W)}\\\\) and are expected to provide labels \\\\(\\\\{z_1, \\\\ldots, z_N\\\\}\\\\) for those datapoints.   For BBF in specific, we only need to give it the LF predictions on \\\\(\\\\{x_1, \\\\ldots, x_N\\\\}\\\\) and set the hyperparameters for its Beta and Dirichlet priors.  It will then output its predictions of the datapoint labels.  To model the LF accuracies without any labeled data, we assume that every LF has made 4 correct predictions and 1 wrong one for a \\\\(Beta(4,1)\\\\) prior.  Something similar is done in EBCC [4].  There, LFs are modeled as confusion matrices.  They assume that each LF has made 4 correct predictions under every class and made every mistake once.  For the \\\\(K=2\\\\) class case, each LF is assumed to correct predict \\\\(+\\\\) 4 times (4 true positives), predict \\\\(-\\\\) when the class was \\\\(+\\\\) once (1 false negative), correctly predict \\\\(-\\\\) 4 times (4 true negatives), and incorrectly predict \\\\(+\\\\) when the class was \\\\(-\\\\) once (1 false positive).  They use a row stochastic confusion matrix with Dirichlet priors -- \\\\(Dirichlet(4,1)\\\\) for the first row and \\\\(Dirichlet(1,4)\\\\) for the second row.   In the experiments, the labels \\\\(\\\\{z_1, \\\\ldots, z_N\\\\}\\\\) are only used to compute the F1 scores/accuracies once every label model has outputted their predictions.  One could use labeled data to set the Beta and Dirichlet priors for BBF (and similarly for EBCC), but we do not pursue this path for the experiments in our paper.  \n* To differentiate HyperLM and Denoise, we first want to emphasize that HyperLM only uses the LF predictions \\\\(h^{(w)}(x_i)\\\\) and does not use the datapoint features \\\\(x_i\\\\).  Denoise on the other hand uses both LF predictions and datapoint features.  \n    + With respect to HyperLM, we checked whether its modeling assumption was met for each of the eleven datasets.  We did not find a pattern between the LFs satisfying HyperLM’s assumption and whether HyperLM performed better/worse than Denoise.  On the datasets where HyperLM decidedly performed worse than Denoise, i.e. IMDB, Commercial, ChemProt, AGNews, we found that the performance was similar to that of Majority Vote.  We hypothesize that the “center” of the polytope constructed by HyperLM might be close to the majority vote labeling.  It is unclear to us what might cause this, because there are datasets w/ a low number of LFs where HyperLM does well (Tennis), and there’s a dataset where the LF accuracies are high but HyperLM has performance similar to Majority Vote (AGNews, 82% average accuracy for LFs).  Thus, we don’t think it’s a combination of whether the HyperLM modeling assumption was met/how many LFs there are/how accurate the LFs are.\n    + On the other hand,  Denoise utilizes an attention mechanism to provide the weights for a convex combination of the LF predictions.  To train the attention mechanism, they minimize the cross entropy between the current prediction and some “pseudo-clean” labeling.  When the algorithm starts, the majority vote labeling is taken as the “pseudo-clean” labeling.  As the model gets trained, the label model's old predictions gets used as the “pseudo-clean\" labeling.  This similar to bootstrapped co-training [4].  One possible explanation is that Denoise gets stuck in poor local optima — which could explain its poor performance against HyperLM and even majority vote.  \n\n[1]  Zhang, J., Song, L., Ratner, A., Leveraging Instance Features for Label Aggregation in Programmatic Weak Supervision, AISTATS 2023\n\n[2] Balsubramani, A., Freund, Y., Scalable Semi-Supervised Aggregation of Classifiers, NeurIPS 2015\n\n[3] An, S. and Dasgupta, S., Convergence Behavior of an Adversarial Weak Supervision Method, UAI 2024\n\n[4] Blum, A., Mitchell, T., Combining labeled and unlabeled data with co-training, COLT 1998"}]

Author rebuttal:

Meta-review: Claims and findings: This is a paper on weak supervision, an area that seeks to efficiently obtain high-quality labels from noisy weak sources. There has been a huge proliferation of label models (the models used to aggregate the votes from the sources), and the authors propose and analyze a new one with useful properties. 

Strengths: The proposed label model is interesting. On the one hand, it is quite rich, while on the other it is amenable to theoretical analysis in a way that a lot of newer label models are not. In particular the results on the form of the posterior and the one on consistency are interesting; these resemble the more theoretically-flavored results from An and Dasgupta, but the authors consider more practical settings. 

Weaknesses: The paper isn't super well-written and there's various clarity issues that have been spotted by the reviewers. However, all of this feels fixable for the camera ready. 

Decision: While the paper needs to improve its writing, there is enough valuable content here to warrant accepting it. 

Rebuttal discussion: The authors clarified many of the questions of the reviewers; with these clarifications the paper will be in good shape.
Decision: Accept (poster)