Learning Hyper Label Model for Programmatic Weak Supervision
Authors: Renzhi Wu
Shen-En Chen
Jieyu Zhang
Xu Chu
Venue: ICLR 2023 poster (2023)
Keywords: Programmatic Weak Supervision
Data Programming
Label Model

Abstract: To reduce the human annotation efforts, the programmatic weak supervision (PWS) paradigm abstracts weak supervision sources as labeling functions (LFs) and involves a label model to aggregate the output of multiple LFs to produce training labels. Most existing label models require a parameter learning step for each dataset. In this work, we present a hyper label model that (once learned) infers the ground-truth labels for each dataset in a single forward pass without dataset-specific parameter learning. The hyper label model approximates an optimal analytical (yet computationally intractable) solution of the ground-truth labels. We train the model on synthetic data generated in the way that ensures the model approximates the analytical optimal solution, and build the model upon Graph Neural Network (GNN) to ensure the model prediction being invariant (or equivariant) to the permutation of LFs (or data points). On 14 real-world datasets, our hyper label model outperforms the best existing methods in both accuracy (by 1.4 points on average) and efficiency (by six times on average). Our code is available at https://github.com/wurenzhi/hyper_label_model

Published as a conference paper at ICLR 2023
LEARNING HYPER LABEL MODEL FOR PROGRAMMATIC WEAK SUPERVISION
Renzhi Shen-En Chen', Jieyu Zhang", Xu Chu! Georgia Tech Univeesitty of Washington
(renzhiwuß, achen3530, xu. chu@cc. Jgatech. edu jieyuz28cs washington.edu
ABSTRACT
To reduce the human annotation efforts, the programmatic weak supervision (PWS) paradigm abstracts weak supervision sources as labeling functions (LFs) and involves label model to aggregate the output of multiple LFs to produce training labels. Most existing label models require a parameter learning step for each dataset. In this work, we present hyper label model that (once learned) infers the ground-truth labels for each dataset in a single forward pass without dataset-specific parameter learning. The hyper label model approximates an op- timal analytical (yet computationally intractable) solution of the ground-truth la- bels. We train the model on synthetic data generated in the way that ensures the model approximates the analytical optimal solution, and build the model upon Graph Neural Network (GNN) to ensure the model prediction being invariant (or equivariant) to the permutation of LFs (or data points). On 14 real-world datasets, our hyper label model outperforms the best existing methods in both accuracy (by 1.4 points average) and efficiency (by six times on average). Our code is available
INTRODUCTION
The lack of labeled training data is major challenge impeding the practical application of ma- chine learning (especially deep learning) techniques. Therefore, practitioners have heen increasingly turned weak supervision which large amounts of cheaply generated noisy labels are used. There
are many forms of weak supervision sources, e.g. external knowledge bases (Mintz et al. 2009). ex-
isting pre-traines models (Das et al. 2020: Wu et al. 2022b), and heuristics/rules (Shin et al. 2015).
To unify different sources, the programmatic weak supervision (PWS) paradigm (Ratner al. 2016
2017 Zhang et al. 2022) was proposed. In PWS, the user expresses each available weak supervision signal from different sources with a labeling function (LF), a small program that takes in data point and outputs a noisy label. After that, each LF is applied to unlabeled data of arbitrary size to obtain a noisy label vector; then, label aggregation model (also referred as label model in literature) is used to aggregate all noisy label vectors to infer the unknown ground-truth labels. The inferred labels can then be used train any downstream end models. The PWS paradigm has been successful in various tasks (Wu et al. 2018 Fries et al. [2019; Lison et al. 2020 Wu et al. 2021 2020 Li et al.
2021 and industry scenarios (Mathew et al. 2021 Bach et al., 2019 Dunnmon et al. 2020).
The core challenge in PWS is how to aggregate all noisy label vectors to infer the ground-truth labels. Let label matrix X denote the noisy labels where each column X [:. j] denotes the noisy label vector from the jth LF and each row [ denotes the weak labels of the ith data point; Let denote the ground-truth label vector. Most existing label models assume an underlying distribution
p(yli)] (i), (Zhang al. 2022) where yji] is the label for the data point and 0 is the parameter
of the distribution. The parameter is first learned on the weak labels X = (X [1, [I, [|2. in unsupervised and typically iterative way, and then inference is made using p(3/ [1] [i.,)) In this approach, the parameter 0 is -ataset-specific and has to be learned for every different X (dataset).
In contrast to existing solutions, we propose a hyper label model with the goal of reducing assump- tions and parameter learning process. Specifically, aim develop hyper model that enjoys

---

Published as a conference paper at ICLR 2023
two desiderata: (1) it works with "minimal" assumption, f.e., we only assume the majority of LFs is setter-teen-randm while does not require the knowledge or assume any particular forms of un- derlying distribution p(y/(]]_X[ii :); (2) once the hyper model is learned, it can be used to infer y for any new X without additional dataset-specific parameter learning process. To shed light on this direction, first show, in theory, that without assuming underlying distribution, there is optimal and analytical (therefore no parameter learning) way to estimate of based on X, i.e., y = (X). However, such h' is intractable to compute since it involves averaging over a set whose size is suponentially-incraasiin
w.r.thhe size of X. Therefore, we propose to leverage the power of deep leamnngg to approximate this solution, i.e., we seek for an alternative function h parametrized by some neural networks, and once learned, it can estimate the label vector for new dataset without ad hoc sataset-specific learning process. Thus, we call the learned model hyper label model.
Materializing this idea involves two key questions: (1) How to generate training data? (2) How to design the model architecture? To generate training data, the straightforward solution is to use the analytical method to generate many pairs of (X, y)) where y h²(X), However, computing y" with h² (X) is of exponential complexity. We notice that for each X, h² (X) is an average of the label vectors from certain set. Taking advantage of this,
able to avoid directly generating
y that is of exponential complexity and design a way of generating an equivalent set of training data such that the trained model approximates h² (X).
The model architecture has two requirements. First, it should be able to accept input matrix X of arbitrary size the size of the matrix X can be different across datasets. Second, the output of the model (e.g. the predicted label vector) should be invariant to the permutations of columns in X as the order of the LFs should not impact the final predicted labels; The output of the model should be equivariant to the permutation of rows in X as when switching the order of the data points in X the predicted labels should be switched accordingly. We noticed that a Graph Neural Network (GNN) is able to accept an input graph of arbitrary size and is permutation equivariant to the nodes on the graph (and can also be made to be permutation invariant by taking the average of the nodes). Therefore, we propose to represent the input matrix X as a graph and then design GNN to satisfy the two requirements.
Contributions. We make the following contributions:
(1) We for the first time present an analytical method for label aggregation which is optimal in the sense that it minimizes certain form of the averaged prediction error, though directly using the analytical method is of exponential complexity.
(2) We train model to learn the analytical method. The trained model is hyper label model that can be used to infer the ground labels for unseen datasets in a single forward pass without needing any dataset-specific parameter learning.
(3) We design synthetic training data generation method and show that the hyper label model trained on the synthetically generated data learns to be the analytical method.
(4) We design an effective model architecture based on GNN so that the hyper label model is appli- cable arbitrary number of LF label vectors of arbitrary size and is invarianteeuuivariant the permutation of LF label vectors/data points.
(5) We show that our hyper label model outperforms the best existing methods over 14 real-world weak supervision datasets both accuracy (by 1.4 points on average) and efficiency (by a speedup of six times on average) for both unsupervised and semi-supervised label aggregation.
RELATED WORK
All existing methods (except majority vote) first learn some parameter 0 ad hoc for each new dataset and inference is then performed based on the learned parameter 0. The existing methods differen- tiate from each other in how to formulate the parameter and how to learn the parameter (Zhang
et al. 2022). For example, most methods assume an underlying distribution p :i :):0) (Rat- ner et al. 2016 2019 Fu et al., 2020) Wu et al., 2022a Yu et al., 2022) and focus on how to represent the distribution and how to learn the parameter 0 of the distribution. Another example is
that some approaches treat the accuracy of the LFs as parameters then use iterative methods to learn the accuracy parameters of the LFs (Arachie & Huang 2021a bl Dawid & Skene 1979) for each
2

---

Published as a conference paper at ICLR 2023
dataset. Different from all existing methods, hyper label model directly performs inference new datasets without needing an ad hoc -ataset-specific parameter learning process.
In principle, X could be any matrix in {+1, 0) 0)"x and can be any vector in {+1, -1"". For arbitrary X and y, there is no way to infer y from X with a better performance than random guess. Therefore, all label models implicitly or explicitly make some assumptions about the quality of the LFs. For example, assuming the accuracy of each LF is in certain range (Ratner et al.] (2016) or the accuracy of LFs are known or can be estimated in certain way (Arachie & Huang 202 Dawid & Skene 1979p. On top of this, most existing methods also make additional assumptions about modeling. Specifically, most existing methods assumes distribution p [ X (ē, :]: 8). then further
assumes the distribution taking certain form (e.g. probabilistic graphical models (PGM) (Ratner jt al., 2016 Fu et al. 2020, Yu et al.) 2022)). Our method only assumes the majority of the LFs better than random guess, which is "minimum" comparing to existing methods.
While our work focuses on PWS, there are other methods to reduce annotation cost. One important line of work is self-supervised learning where feature representations are learned from self-defined pseudolabels and can then be used for downstream tasks (Jaiswal et al. 2020; Misra Maaten
2020 Liu et al. (02T). Another popular approach is active learning that interactively selects the most informative data points to annotate (Settles) 2012).
3 PROBLEM SETUP
Given a binary classification task, let and denote the number of data points and the number
of LFs respectively. Let X E -1,,-1,0pax denote a label matrix where [i E {+1, -1,0) 0} denotes the weak label of the jth data point provided by the j"h LF. The values +1 and -1 denote the positive and negative classes respectively and 0 denotes abstention, ie. an LF does not have enough information to label a data point as either positive or negative (Ratner al. 2016). The goal of a label model is to infer the unknown ground -ruth label vector {+1, -1 using X, which typically requires learning process for each individual dataset, ie.,, X.
The tenter-than-randdor Assumption. As discussed in Section 2 in weak supervision literature, there are often assumptions on the quality of LFs so that one can make a meaningful estimation of y using X. Different methods make different assumptions (Ratner et al. 2016 Fu et al. 20200] Ratner al. 2019. Arachie & Huang 2021a). In this work, we assume that for each class, the majority of LFs are better than random. This assumption is realistic since the LFs are typically made by human and humans might occasionally make mistakes when developing individual LFs, resulting in a small portion of worse-than
LFs. Formally, this assumption can be expressed as:
m-
m
Σ 1=0
9(X,
m 2 and Σ g(X. 2
where g(X,y) y.J,e) c) denotes whether the jth LF is better-than--radom for class e:
L, En Lxpd & viA=c En 1 1x wiil=c
g(X,y,j.c)
(2)
0, otherwise;
We define oXX 3) when Equation ! is satisfied and oXX, y) otherwise. We say pair (X, y) is valid (or a vector y is valid for given X) when oXX, y) = 1. Intuitively, a constrains the space of the predicted label vector ý and we would only predict one of label vectors with oX, 9) = I for a label matrix X. Note the method we will propose is not tied to our netter-than-randon assumption, and it also works with any other assumptions to define a.
Our Goal. Most existing methods aim to learn an individual label model for each dataset. con- trast, our goal is to learn a hyper label model under our betler-than-randor assumption. The learned hyper model can be applied to any unseen dataset and produces a prediction of the label vector y in single forward pass without any form of dataset-specific parameter learning. Specifically, ex- isiting methods typically model the distribution p(y ji] [(, :]: 8), where X :] is an individual data point from dataset, i.e. one in the label matrix X (that represents all data points) and yli] is
3

---

Published as a conference paper at ICLR 2023
the corresponding label; The parameter should be learned for every new dataset before perform- ing inference on each data point using the distribution p [2. Instead, we aim to learn a hyper distribution p(y) X, @) over all possible datasets with hyper label model. Once the hyper label model has learned θ for any new dataset new. it could directly produce prediction using the distribution ply) new; Q) without needing to learn dataset-specific parameter 0.
AN ANALYTICAL OPTIMAL SOLUTION
We first show there is optimal and analytical (therefore dataset-specific parameter learning) method to estimate y based on X, i..., y" h" (X). This makes hyper label model possible.
For each label matrix X, let 2e (X) ( (X, y) = 1} denote the set of valid candidate ys for X. The expected error of an estimator (XX) of the y each X is:
< (X,
Σ MEHy((
x M(XIII
where (X) is a distribution of defined on set My (X) and ||. denotes L2 loss (i.e. squared error). p(y X)) is unknown and can be different in different real-world applications (datasets). With- out additional information apart from X, there is no way to determine the preference of some valid choices of y over other valid choices of y. so the uniform distribution (i.e. p' /'(y[X) Tış(xT is
tuitively good approximation for the unknown p(y) X). In fact, using the uniform distribution has optimalities both the worst case and the average case. To maintain the flow of the paper, we defer the formal definition and proof of the optimalities of using the uniform distribution to Appendix Replacing (X) by the uniform distribution, Equation becomes:
<X,,h) (X)( (X
Σ
y h(x)
<(X,)) h) can be interpreted as the average error of all possible outcomes. An estimator can be said to be the optimal if it minimizes the error c'(X, h), VX.
Theorem 1. VX, 1t" (X) = [ EyEu,(x) is an optimal estimator of the ground-truth in the sense that it minimizes e' eX,
We omit the proof as it is straightforward (The mean minimizes mean squared error.). Theorem makes sense intuitively: since is the only information we have, y can be any element in Ut (X) and there is information to support preferences of some elements over other elements in My (X), so the best prediction one can make is the average of all elements in (X...
5 LEARNING THE HYPER LABEL MODEL
Although we have the analytical form of the optimal estimator ht",, computing it is of exponential complexity as (X)) is exponentially large for any X. Therefore, we propose to train neural network model h to approximate the optimal estimator h.. The trained model is a hyper label model that can infer the labels for new dataset in a single forward pass. To materialize this idea, we need to answer the following questions: (1) What training data to use? (2) What model architecture to use? We discuss all these in the following sections.
5.1 TRAINING DATA GENERATION
Given a training set D ((X1,91),... y1).... and cross-entropy loss (cB(-,),, our learning objective is:
IDi
arg arg min C(h, D) arg min h
(ce(M(X))))
(5)
h
where we use notation [i] to index the jth item of the preceding vector. The key challenge is how to obtain the training dataset D. Naively, could generate random X and then use the analytical
4

---

Published as a conference paper at ICLR 2023
method to find y", which is however computationally intractable. Therefore, we design efficient data generation method that ensures the model trained on our generated data still approximates h- By the following theorem, we show that given X. uniformly sampling valid y. i.e. y Uy (X), to compose the training dataset 'D ensures the learned hyper label model is asymptotically close to the analytical solution.
Theorem 2. X- E -D, if the corresponding y is uniformly sampled and valid, when |D] + +00, then arg min; (h,, D) - h (x)) [x,( Eweu,
See proof in Appendix B Based on the theorem, we derive the following training data generation method such that for every X, the corresponding y is uniformly sampled and valid. Step 1: We first randomly generate the shape of X. by randomly draw m (and n) from uniform distribution (Tm, Hm] (and T... H..). We provide details of how to choose Lmn Hm, In and H, in Appendix F and empirically show the trained model generalizes very well outside of the given regions of shape (In fact, 13 datasets out from the 14 datasets we evaluate on are outside of the given regions of shape). Step 2: Given the shape of X. we then generate and the corresponding y with the values being sampled uniformly at random. Step 3: If o (X, y) 1, we keep it training data point. This process (Step 1, 2. and 3) is repeated untill we obtain enough training data. Apparently, since y is generated uniformly, for any two different and valid vectors y1 and y2 with (X, y1) = aXx, y2) 1, the probability of generating y equals to the probability of generating y/, i.e. p(y X) is uniform. The probability of generating valid pair in one trial is about 0.2 (see Appendix C
5.2 MODEL ARCHITECTURE DESIGN
Notably, the input of the model h is a matrix X of size n X m and the output vector á of size n. Thus, a reasonable instantiation of h should satisfy the following three properties: (1) Ability to accept arbitrary input size: The number of data points n and LFs m can vary for different datasets. The model h should be able to accept an input matrix X of arbitrary size. (2) Invariance to permutation of LFs: Intuitively, randomly shuffling the LFs should not change the prediction of any data point. Formally, let Pm. denote one arbitrary permutation of the integers in [0, l]. Invariance to permutation of LFs means that h[[[:, Pm]) = h(X), VPm. (3) Equivariance to permutation of data points: Smilarily, randomly shuffling the data points should not change the prediction of each data point. Formally, equivariance to permutation of data points means that :( (P)), VP. where P,, is defined similarly Pm.
We argue that a graph neural network (GNN) is a good fit here since it can accept input graph of arbitrary size and is permutation equivariant to the nodes (Sanchez- Lengeling fore, we attempt to represent the input matrix X as a graph and then use a GNN for h in order to satisfy the aforementioned properties. Specifically, the left-most matrix and graph in Figure D illustrate how we represent an input matrix of size 3 x 2 as graph. Entry X[i j]. the weak label of the 7th data point provided by the jth LF, is represented as a node Vi,, with value X(i. j]. There are two types of edges: solid yellow edge and dashed blue edge. Nodes from the same LF (i.e. same column in matrix X) are connected with solid yellow edges and nodes from the same data point (i.e. same row in matrix X) are connected with dashed blue edges. The graph representation G loses no information as one can recover X (or its permutation X [[Pm, Pmm) from G.
al. (02T). There-
V
V
Va3
VK
Avg Pool
X[O.0] [(0
ViD
GNN
V
V5.
MLP
v[0]
X[1.0] X[1.]]
V 1111
f
V.
y[1]
x[2.0] X(2,1]
DE.
y[2]
V20
V21
V.50
V2.
Figure 1: Overall network architecture
In graph G. if we only look at dashed blue edges, there would be n strongly connected com- ponents and each corresponds to one data point. Specifically, the strongly connected component SCC,= (V.o. V.,.... } corresponds to the t data point. The overall model architecture is shown in Figure first we encode the input graph with GNN of K layers where each node V is encoded
5

---

Published as a conference paper at ICLR 2023
with embedding Vi at the Ath layer; then after the final layer, obtain embedding for each SCC, (Lee. each data point) by pooling all of its nodes V.K - SCC, is passed satisfies all three mentioned properties (see Appendix D.I.
6. m ES V.K. : The embedding of each Multilayer perceptron (MLP) to obtain the final prediction. This architecture
We adopt the standard design of GNN. Since we have two types of edges. we perform message passing for neighboring nodes connected with each type of edges separately. Specifically, at the 1thh layer in the GNN, the embedding Vi for the node Vi,j is obtained as:
v = (W
Vk-1 9.
Σ W
1 m
V W
Σ Vi W( q.l
(6)
9. where Wf, . are weight matrices; Eg v denotes average pooling over neighboring
nodes of Vi connected with solid yellow edges and 1 E, V denotes average pooling over neighboring nodes of Vi, connected with dashed blue edges; Note we use average pooling because the graph can be of variable size as recommended by Sanchez-Lengeling et al. (202)) and we also include the node's previous embedding f in the average in case the node has no neighbors (this is equivalent
adding a self-edge to each node.). We also add the global context of the graph v9r Ej. V to enable message passing beyond neighboring nodes, following the standard practice (Gilmer et al., 2017, Battaglia et al., 2018); (....,)))) denotes an aggregation operation and we simple concatenation; f& denotes linear layer with Relu activation.
Handling Abstention. Handling abstention is straightforward in our approach. We can simply remove the corresponding nodes in our graph. For example, when the j LF abstains on the ith data point, we simply remove the node Vi, from the graph.
5.3 MODEL INFERENCE ON UNSEEN DATASET
The trained hyper label model can be applied to any new dataset with the inference being simply a single forward pass. During the forward pass, different data points (rows in matrix X) and different LFS (columns X) exchange information through message passing in GNN. This information ex- change step can be regarded as the counterpart of the dataset-specific training step of other methods.
Inference Complexity. The complexity of forward pass is dominated by the GNN. Although there are Omm²²) edges in the graph, there is no need to actually materialize the O(ma²) edges and the complexity of each GNN layer only (mm) In each GNN layer, for the three averaged pooling operations in Equation 6 the first with complexity (n)) needs to be computed once for each LF totaling m times so the complexity is (mm)); Similarly, the second one and the third one also have complexity of ((m)). Therefore, the time complexity for each GNN layer is O(mn).
5.4 LEVERAGING GROUND TRUTH LABEL IF GIVEN
We pretrain a model big on our sythetically generated data. When small set of ground-truth labels provided, our method can incorporate the labels by fine-tuning the model ho on the provided labels. Let denote the set of indices of the elements in that are provided. For example, when == [2. 3). it means y [2] and (3] are provided. Fine tuning is done by minimizing the cross-entropy loss Eier (cn()(()( (i). y (i] and h is initialized as the pretrained model bg- After fine-tuning we obtain a model h²' and then all labels are obtained by X'(X). We note the fine tuning process is dataset-specific, i.e. finetuning is done independently and specifically for each dataset X using the ground-truie truth labels of that dataset.
5.5 SUPPORTING MULTI-CLASS CLASSIFICATION TASK
We have only considered the binary labels and it turns out that our trained model for binary la- bels can be easily used to support multi-class classification datasets by decomposing multi-class task with C classes to be C' one-vs-rest binary classification tasks. For multi-class tasks, we have Xli (0, 2, ... C} where 0 still denotes abstention and other numbers denote all the classes.
We construct the label matrix for the th class as X = if X(i.j] = c. X, ]] = X [i 0, and otherwise X.(i,)] = -1 In this way, we obtain C label matrices (X1,... X.)-

---

Published as a conference paper at ICLR 2023
We apply pre-trained model hg on each label matrix of each class and obtain C predicted probability vectors (Pi....,PP)) Then, for the tt data point, its soft label over the C classes is p ).ll We show in experiments this simple method works well multi-class datasets (4 datasets out of the 14 datasets we use are multi-class datasets).
Pr P. ................................ E.
EXPERIMENTS
We evaluate the performance of all label models under both unsupervised and semi-supervised set- tings. We provide additional experimental results on the performance of end models trained on the generated labels by different label models in Appendix F.2 The code and instructions to reproduce the experiments are in supplementary materials.
Datasets. We use all 14 classification datasets in recent weak supervision benchmark (Zhang et al., 202T] that are from diverse domains (e.g. tion tasks). We highlight these datasets are only used for evaluation after our model is trained on synthetically generated data, and we never used these datasets during training. Table [ shows the statisties of all datasets. We also use the metrics provided by the benchmark (Zhang et al.,, 2021) for each dataset (as different datasets need different metrics depending on their application back- ground). All LFs are from the original authors of each dataset and are hosted in the benchmark project Zhang 2022a).
classifica-
Table 1: 14 classification datasets from the weak supervision benchmark (Zhang et al. 2021)
Dataset Census IMDB Yelp Youtube SMS Spouse CDR Commercial Tennis Basketball AGNews TREC SemEval ChemProt
#class 2
2
2
2
2
6
9
10
metric F1
acc
acc
F1
F1
F1
F1
F1
F1
a0c
aec
ALF
83
5
8 10
73
33
4.
6
9
68
164
26
#Data
31925
25000 38000
1956
5571 27766
14023
81105
8803
20256
120000
5965
2641
16075
We consider baselines for both unsupervised and semi-supervised label aggregation.
Unsupervised Baselines: (I) Majority Vote (MV). The predicted label of each data point is the most common label given by LFs. (2) Data Programming (DP) (Ratner et al.) (016)). DP uses a probabilistic graph model (PGM) where each LF is node and the hidden ground truth is latent variable. (3) Flyingsquid (FS) et al. 2020). FS also uses PGM but gives closed-form solution with some assumptions. (4) MeTaL (Ratner al.) 2019). McTaL infers the ground truth using a matrix completion model. The latest version of the popular Snorkel system (snorkel team 2022b) adopts MeTal. as its default label model. (5) NPLM (Yu et al. 2022). This method is also based on a PGM and assumes LFs are conditionally independent. It supports partial LFs that predict a subset of class labels and is designed to be very efficient. (6) Dawid and Skene's 's method (DS) (Dawid & Skene 1979). DS models the confusion matrix of each LF with respect to the ground truth labels. The confusion matrix is learned by an Expectation Expectation-Maximizzaaa Maximization algorithm. (7) Enhanced Bayesian Classifier Combination (EBCC) (Li et al. 2019). This method models the joint distribution of LFs as a mixture of multiple low dimensional tensors. (8) Constrained Label Learning ( (CLJ.) (Arachie & Huang 2021a). This method also minimizes the average prediction error where the error is defined using the unknown expected errors of each LFs. (9) HLM. This is our learned Hyper Label Model. Semi-supervised Baselines: (1) Semi- sup-riueeee DS (Dawid & Skene, 1979). This is the semi- supervised extension of the Dawid and Skene's 's method. (2) AMMCLCC (Mazzetto et al. (027)) This method uses labeled data to construct feasibility constraints and provides performance guarantees. (3) Random Forest. This method trains random forest classifier with X as the features using the provided labels. (4) Semi- seeii-seeeeiseed HLM. The semi-supervised version of our method HLM obtained by finetuning on the provided labels.
Note the baseline methods require a dataset-speciffc learning step, we use the transductive setting (data points used in unsupervised learning is also used to evaluate the learned model) following prior work (Mazzetto et al. 2021 Zhang 2022b).
Implementation. We provide the implementation details of method (e.g. setups and all pa- rameters in data generation/model architecture/model training/valldationn) in Appendix(Ejann imple- mentation details of the experiments (e.g. hardwarr/dnasevhseeiiiss/spp in Appendix Since

---

Published as a conference paper at ICLR 2023
model training is important, here we provide brief overview on training HLM. We generate each batch of data on- tee-thh-yyy fly with a batch size of 50, i.e. each batch consists of 50 pairs of generated (X, We train our model until training loss converges (loss doesn't 't decrease in 10* iterations), which takes about 5 x 10 iterations. We noticed that in different runs, the performance of the trained model can vary, we use synthetic validation set D' to select the best run out of ten runs. The validation set is generated with a different method from prior work (hhang et al. 2021).
6.1 UNSUPERVISED LABEL AGGREGATION
The performance of all methods on all datasets averaged over five runs are shown in Table 2 To maintain the table to be readable, we only show the error bars for the averaged scores. Again, for our method HIM, we note only synthetically generated data is used for training and the 14 datasets are only used to evaluate the trained model. We note MV and our method HLM are deterministic while the other methods can give different results with different seeds. For HLM, the error bar obtained by repeating the training process multiple times and then performing inference with different trained models.
Main results. First, our results align with the benchmark (Zhag et al. 202 where MeTaL is slightly better than MV. The difference in numbers from the benchmark (Zhang et al. 2021 is due to that we use a transdueive setting following (Mazzetto al. 202 Zhang 2022b). Second, HLM outperforms the best baseline CLL by 1 1.4 points on average. Third, HLM is the best on 8 out of 14 datasets; On the remaining 6 datasets, HLM the second best or is close to the second best method.
Table 2: Performance (F1
score depending on the dataset) all datasets
Dataset Consus IMDB Yelp Youtube SMS Spouse CDR Commercial Tennis Baskerball AGNews TREC SomEval ChemProt AVG.
MV
22.2
75.0
74.4
80.3
84.0 51.6
63.3
85.9
85.0
18.9
81.4
49.9
84.2
53.7
65.0:0.0
DP
11.1
74.4
71.9
84.5
83.8 50.3
33.9 77.5
85.1
17.1
81.7
47.2
73.5
56.2
60.6+0.11
FS
17.1
74.5
74.0
83.7
74.4 49.9
69.6 82.5
84.0
17.1
81.3
50.1
23.8
52.4
59.6:20.0
MeTal.
75.0
74.4 86.0
49.9
83.7
80.9
82.2
52.1
84.2
52.9
65.5.0.2
NPLM
0.0
55.2
68.3
45,2
0.0 34.3
0.0
76.5
85.0
0.0
81.3
36.5
30,2
48.4
40.1=0.0
DS
0.0
74.4
68.3
45.2
65.0 34.3
0.1
77.8
85.0
17.1
26.6
20.9
73.5
35.1
44.5.0000
EBCC
0.0
74.4
69.6
45.2
0.0
34.3
8.7
77.5
85.0
17.1
27.8
20.8
30.2
35.0
37.6:10.1
CLI
53.6
72.7
72.0
86.
84,2 50.0
64.9
84.8
83.5
17.5
80.7
59.0
84.2
53.1
67.6++0.0
HLM
56.1
75.0
74.4
91.4
51.6
71.0
83.6
84.3
17.1
81.4
59.8
84.2
52.3
69.0:0.22
Efficiency. We report the running time Table 3 When measuring the running time, we use GPU for methods that support GPU (MeTaL,, NPLM, and HLM).. CPU-only running times are in Appendix[F.] HLM requires less than seconds on every dataset. HLM is on average times (and can be up to 18 times) faster than the fastest baseline (except Majority Vote) and is on average 50 times faster than the baseline (CLL) with the best accuracy. This is because all prior methods (except Majority Vote) require unsupervised learning process while HLM performs prediction in single forward pass just like Majority Vote. We note that these 14 benchmark datasets are relatively small (as creating a large benchmark dataset with ground-truth labels is expensive). In industry scenarios, LFss can be applied on millions of data points to create labels (Bach et al. (201)). The runtime gain of HLM will be more significant and HLM will enable the LF development process to be more interactive.
6.2 SEMI-SUPERVISED LABEL AGGREGATION
For each dataset, we randomly sample Ng data points as the data points with known ground-truth labels and we evaluate on the remaining data points. When Ng. > 0.7n, we only select 0.7n data points to keep 30% of the data for evaluation in order to have a reliable evaluation score. We vary Ng from 10 to 10000. When finetuning HLM (with the method in Section 5.4), we use smaller learning rate Ir = 0.0001 to prevent overfitting (originally Ir = 0.001). Intuitively, when Ng is small, trust the pre-trained HLM more than the provided labels; when Ng: is large, trust the provided labels more than the pre-trained HLM. Therefore, we relate the number of finetuning epochs to ye by setting the number of epochs as /Ng.
8

---

Published as a conference paper at ICLR 2023
Table 3: Running time (seconds) of label aggregation all datasets
Dataset Census
IMDB
Yelp
Youtube SMS Spouse
CDR Commercial Tennis Baskethall AGNews
TREC
SemFEaal ChemProt AVG.
MV
<0.1
<0.1
<0.1
c0.1
<0.1
c0.1
<0.1 <0.1
<0.1
<0.1
<0.1
<0.1
<0.1
<0.1
<0.1
147.8
40.5
2.5
14.4
8.4
29.5
10.0
14.9
225.0
100.8
190.2
213.0
73.2
FS
21.1
1.7
3.7
0.2
0.8
3.7
0.6
14.9
22.1
16.3
69.0
26.4
12.2
MeTal.
0.5
0.3
0.4
0.4
0.4
0.3
0.4 0.4
0.4
0.4
0.5
3.6
4.6
3.6
1.2
NPLM
15.7
4.0
5.7
0.4
1.8
11.2
1.5
3.4
27.9
12.1
7.2
2.4
79.8
116.1
0.2
0.9
29.7
267.7
16.3
78.3
36.6
255.9
63.9
EBCC
3.9
5.1
52.5
2.2
2.8
2.3
5.8
3.0
2,5
6.0
18.0
9.0
9.8
84,8
14.8
CLL
33.7
2.9
6.6
0.5
3.8
1.4
6.0
7.4
1.1
2.0
28.5
12.4
20.5
21.3
10.6
0.1
0.2
0.2
The results are shown in Figure 2 When Ng. >> 40, semi-supervised HLM outperforms unsuper- vised HLM. Semi-supervised HLM outperforms the other three baselines when Ng 1000 and ties with AMCL-CC and Random Forest when Ng > 1000. We highlight semi-supervised HLM also the most efficient, e.g. when Ngr 10000, the running time averaged over all datasets is 3.1 seconds for semi-supervised HLM, 61.3 seconds for semi-supervised DS, 261.8 seconds for AMCL-CC, and 4.8 seconds for random forest.
Averaged score over datasets
Table 4: Ablation study. denotes re- placing the component precedes with a naive one.
70
85-
Unsupervised HILM
Semi cemi--upervised HLM
60
Semi supervised DS
Avg score
Random Forest
HLM
69.0
50-
data generation
64.2
* model architecture
61.8
10a
10a
10a 10*
Nor number gt labels
betler-than-random
67.6
Figure 2: Semi-supervised performance.
6.3 ABLATION STUDY
We perform ablation study (under unsupervised label aggregation setting) in three aspects: (1) We replace data generation method with the one proposed in (Zhang et al. 202I that was originally used to generate LFs to evaluate label models. (2) We replace our model architecture with a naive architecture based MIP and another architecture based
DeepSet (Zaheer et al. 2017) (see details in Appendix G). We report the best result of the two architectures.
(3) We replace our better-than than-random assumption Equation [ with straightforward assumption that each LF is better than random in each class. The results are shown in Table 4 Replacing each component reduces performance. In particular, replacing our assumption with the straightforward assumption decreases performance because the assumption that each LF is getter-than-ranee on each class is not satisfied in the real-world datasets.
7 CONCLUSION
We present hyper label model for programmatic weak supervision, which infers the ground-truth labels for each dataset single forward pass and does not require any ad-hoc -ataset-specific parameter learning step. The hyper label model approximates analytical optimal method (which computationally intractable due to its exponential complexity). We generate synthetic training data that ensures the trained hyper label model to approximate the analytical solution and design a model architecture based on GNN to ensure the model to be invariant to the permutation of LFs and equivariant to the permutation of data points. We experimentally verify the superiority of the hyper label model both accuracy and efficiency with both unsupervised and semi semi-supervised label aggregation settings over 14 benchmark datasets.

---

Published as a conference paper at ICLR 2023
REFERENCES
sklearn,
May
2022.
URL
https://
getpe//geeeaaaaeeeeeeaa oetpa//aeeeeeeootee.eeeeeeeeeeaa www.ee..ww.eeeaaaa....a ensemble.
CandonnoorestClassiieee html
[Online; accessed 2. May 2022].
Chidubem Arachie and Bert Huang. Constrained labeling for weakly supervised learning, In Un- certainty in Artificial Intelligence, pp. 236-246. PMLR, 2021a.
Chidubem Arachie and Bert Huang. A general framework for adversarial label learning. J. Mach. Learn. Res., 22:1 18-1, 2021b.
Stephen H Bach, Daniel Rodriguez, Yintao Liu, Chong Luo, Haidong Shao, Cassandra Xia, Souvik Sen, Alex Ratner, Braden Hancock, Houman Alborzi, et al. Snorkel drybell: A case study in de- ploying weak supervision industrial scale. In Proceedings the 2019 International Conference on Management of Data, pp. 0002-77,220 2019.
BatsResearch. yu-aistats22-code, May 2022a.
URL https://github. com/
BctsReeaaarch/ code
[Online; accessed 1. May 2022].
BatsResearch. mazzetto-icm/2l-codd.. Sepeeme
2022b. URL https: /ggthtitthhhggggg com/ [Online; accessed 5. Sep. 2022].
Bsteleesearhh/mmazztttooooooooo
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sunchez-Gonzz Gonzalz, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 100.:v:80060022200 2018.
Nilaksh Das, Sanya Chaba, Renzhi Wu, Sakshi Gandhi, Duen Horng Chau, and Xu Chu. Gog- gles: Automatic image labeling with affinity coding. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1717-1732, 2020.
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):20-28, 1979.
Frederik Michel Dekking, Cornelis Kraaikamp, Hendrik Paul Lopuhaä, and Ludolf Erwin Meester. Modern Introduction Probability and Statisties: Understanding why and how. Springer, 2005.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1eXXvv181000440 2018.
Jared A Dunnmon, Alexander Ratner, Khaled Saab, Nishith Khandwala, Matthew Markert, Hersh Sagreiya, Roger Goldman, Christopher Lee-Messer, Matthew P Lungren, Daniel L Rubin, et al. Cross-modal data programming enables rapid medical machine learning. Patterns, 10001100 2020.
Jason A Fries, Paroma Varma, Vincent S Chen, Ke Xiao, Heliodoro Tejeda, Priyanka Saha, Jared Dunnmon, Henry Chubb, Shiraz Maskatia, Madalina Fiterau, et al. Weakly supervised classifi- cation of aortic valve malformations using unlabeled cardiac mri sequences. Nature communica- tions, 10(1):1-10, 2019.
Daniel Fu, Mayee Chen, Frederic Sala, Sarah Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In International Conference on Machine Learning, pp. 3280-3291. PMLR, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR. 2017.
Godfrey Harold Hardy. John Edensor Littlewood, George Pólya, György Pólya, et al. "hölder's inequality and its extensions.". In Inequalities, 2nd ed., chapter 2.7-2.8, pp. 21-26. Cambridge university press, 1988.
10

---

Published as a conference paper at ICLR 2023
HazyResearch. flyingsquid, April 2022. URL httpss//ggthub..cm///ayyeeeeeeee Elyingsquid, [Online; accessed 26. Apr. 2022].
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wil- son. Averaging weights leads to wider optima and better generalization. arXiv preprint arXiv:1803.05407, 2018.
Ashish Jaiswal, Ashwin Ramesh Babu, Mohammad Zaki Zadeh, Dehapriya Banerjee, and Fillia Makedon. A survey on contrastive self-supervised learning. Technologies, 9(1):2, 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere. Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 1609, 044366, 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14X2.6/41226680, 2014.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. Advances neural information processing systems, 31, 2018.
Yinghao Li, Pranav Shetty, Lucas Liu, Chao Zhang, and Le Song. Bertifying the hidden markov model for multi-source weakly supervised named entity recognition. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp. 6178 0198,, 2021.
Yuan Li, Benjamin Rubinstein, and Trevor Cohn. Exploiting worker correlation for label aggregation in crowdsourcing. In International Conference on Machine Learning, pp. 1886-3895. PMLR, 2019.
Pierre Lison, Jeremy Barnes, Aliaksandr Hubin, and Samia Touileb. Named entity recognition without labelled data: A weak supervision approach. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1518-1533 2020.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang. Jing Zhang, and Jie Tang. Self- supervised learning: Generative or contrastive. IEEE Transactions on Knowledge and Data En- gineering, 2021.
manzilzaheer.
DeepSets, November 2022. URL http:://ggthabb.commmaaaaaaaaaap DeepSets [Online; accessed 9. Nov. 2022].
Jose Mathew, Meghana Negi, Rutvik Vijjali, and Jairaj Sathyanarayana. Defraudnet: An end-to-end weak supervision framework to detect fraud in online food delivery. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 85 35-99. Springer, 2021.
Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach, and Eli Upfal. Adversarial multi class learning under weak supervision with performance guarantees. In International Conference on Machine Learning, pp. 7534-7543, PMLR, 2021.
Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. Distant supervision for relation extraction without labeled data. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pp. 1003-1011, 2009.
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6707-6717, 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, (021(12):12403, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.

---

Published as a conference paper at ICLR 2023
Alexander Ratner, Stephen H. Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB En- dowment. International Conference Very Large Data Bases, volume 11, pp. 269. NIH Public Access, 2017.
Alexander Ratner, Braden Hancock, Jared Dunnmon, Frederic Sala, Shreyash Pandey, and Christo- pher Ré. Training complex models with multi-task weak supervision. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4763-4771, 2019.
Alexander J Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly. Advances in neural information processing systems, 29, 2016.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: 2019.
Benjamin Sanghez-Lengeling, Emily Reif, Adam Pearce, and Alexander B Wiltschko. A gentle introduction to graph neural networks. Distill, 6(9):e33, 2021.
Burr Settles. Active learning. Synthesis lectures on artificial intelligence and machine learning, 6 (1):1-114, 2012.
Jaeho Shin, Sen Wu, Feiran Wang. Christopher De Sa, Ce Zhang, and Christopher Ré. Incremental knowledge base construction using deepdive. In Proceedings of the VLDB Endowment Interna- tional Conference on Very Large Data Bases, volume 8, pp. 1310. NIH Public Access, 2015.
snorkel team. snorkel-extraction, April 2022a.
URL https://github...
snorkel team http///noookeeeee -xt iwwrraaction/bbe on/oon/llllo htt.://msseer/aoteeeeeaaaaa
gen learning. [Online; accessed 26. Apr. 2022].
snorkel team. snorkel, April 2022b. URL ht httpp://ggthubb.cm/mnnoteee
snorkel [Online; accessed 26. Apr. 2022].
sukrutrao. Fast-Dawid-Skene April 2022. URL http:///gihub...cmmmtttttt
Destt-Dawid-keee
[Online; accessed 26. Apr. 2022].
Renzhi Wu, Sanya Chaba, Saurabh Sawlani, Xu Chu, and Saravanan Thirumuruganathan. Zeroer: Entity resolution using zero labeled examples. In Proceedings of the 2020 ACM SIGMOD Inter- national Conference Management of Data, pp- 1149-1164, 2020.
Renzhi Wu, Prem Sakala, Peng Li, Xu Chu, and Yeye He. Demonstration of panda: A weakly su- pervised entity matching system. Proc. VLDB Endow. (4(12):2735-27388 oct 2021. ISSN 2150- 8097. doi: 10.14778/34763113477333 3376632]
URL htt.:/ppp////o...o/0000111/////1
Renzhi Wu, Alexander Bendeck, Xu Chu, and Yeye He. Ground truth inference for weakly super- vised entity matching, 2022a.
URL https: arxi rrxiva www.oorgg..........ooo /2110/002221111755
Renzhi Wu, Nilaksh Das, Sanya Chaba, Sakshi Gandhi, Duen Horng Chau, and Xu Chu. A cluster- then-label approach for few-shot learning with application to automatic image data labeling. ACM Journal of Data and Information Quality (JDIQ), 14(3):1-23, 2022b.
Renzhi Wu, Bolin Ding, Xu Chu, Zhewei Wei, Xiening Dai, Tao Guan, and Jingren Zhou. Learning to be statistician: Learned estimator for number of distinct values. Proc. VLDB Endow. 15 (2):272-284, feb 2022c. ISSN 8090. doi: 10.44778334994944899588
URL https:
1ttp://11.1777833380 0111///333449996668833 3489508
Sen Wu, Luke Hsiao, Xiao Cheng, Braden Hancock, Theodoros Rekatsinas, Philip Levis, and Christopher Ré. Fonduer: Knowledge base construction from richly formatted data. In Pro- ceedings of the 2018 international conference on management of data, pp. 1301-1316, 2018.
Peilin Yu, Tiffany Ding, and Stephen H. Bach. Learning from multiple noisy partial labelers. In
Artificial Intelligence and Statistics (AISTATS), 2022.
12

---

Published as a conference paper at ICLR 2023
yuan li,
URL Eruth- -atte--iiieenne----saaaa [Online; accessed
May
2022.
httes://gittuu.co.m wtt.:/.commppaa//// May 2022].
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Jieyu Zhang. Wrench Project Homepage, 2022a. URL httpss///github..cmm/eee.z..
w wrench [Online; accessed 12. May. 2022].
Jieyu Zhang. Wrench Github Issue. "Question train/val/test split when evaluating label model.", [Online; accessed
2022b. htRthttps://giit
cow/ wwwp:ieeeyneee/eeeeeetssssuss
12. May. 2022].
Jieyu Zhang, Yue Yu, Yujing Wang, Yaming Yang. Mao Yang, and Alexander Ratner. Wrench: A comprehensive benchmark for weak supervision. In Vanschoren and S. Yeung (eds.), Proceed- ings of the Neural Information Processing Systems Track Datasets and Benchmarks, volume 2021.
Jieyu Zhang, Cheng- Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. A survey on program- matic weak supervision. arXiv preprint arXiv:200.005433 2022.
Yudian Zheng, Guoliang Li, Yuanbing Li, Caihua Shan, and Reynold Cheng. Truth inference in crowdsourcing: Is the problem solved? Proceedings of the VLDB Endowment, 10(5):541-552, 2017.
13

---

Published as a conference paper at ICLR 2023
A OPTIMALITIES OF THE UNIFORM DISTRIBUTION
We aim to approximate an unknown distribution p(y (which can be different in different applications) with an fixed distribution (xy(-)) Since both distributions defined fi- nite set (,) we can use the probabilities of the elements in (X) to represent each of the two distributions. Specifically,
and ( as q = {q).... (x))) Similarly, we denote the uniform distribution (i.e. p (y) X) (x, as (un,.. ................................ (x)I Apparently, Vi, we have S pt S 1, 9: S u. [X]] E, 1, Σ; 9 = 1, and Σ, u, = 1. Using the uniform distribution u to approximate p is the optimal in both the worst case and the average case. The two optimalities are formally defined the following:
represent p(y| as p
(1) Worst-case Optimal: The uniform distribution u has the minimum maximum distance to the unknown distribution p:
= argmin max dist(p, q)
9
where "dist" can be the KL divergence or La distance Ya 1. Note the conventional name is "L," distance, but to avoid reusing the same notation for different meanings, we use the name "Lo" distance instead.
(2) Average-case Optimal: The uniform distribution a has the minimum expected KL divergence the unknown distribution p under mild assumption. Let P(p) denote the probability of the unknown distribution being a specific distribution p (e.g. P(u) would be denoting the probability of the unknown distribution being the uniform distribution i.e. p(p = u.). Formally:
argmin / KL(P, Pp))
argmin Ep KL(p q)]
(8)
under the assumption that P(p) is centrally symmetrie, formally:
J.
P(p) u
(9)
We provide formal proof for the two optimalities in the following:
Proof for Worst-case Optimal.
Proof. We first prove Equation 7 for KL divergence.
max KL 9)
Σ
ps log Pb
max P
(10)
1
max
p: log Pi + log
P
qi
The maximum of the first term is zero, as P: log < 0 due to p; 2 and logp; S 0. The maximum obtained when there is a j such that py and p. 0, Vi + j:
j also comes into play in the maximum of the second term. We have Σ, P. log Σ; P: max; log 1
Therefore, the maximum of of the second term is max, log 1 es max log 1. qs. which is obtained when j = arg max, log( (.), P; = and P. = 0, Vi j
g+
We can see that the maximum of both terms is achieved at the same time with j = arg max; log( L), Pj = and p. = 0, Vi # j. The maximum value is max, log 1 9.
Therefore,
max KL(p, q) = max log
(11)
= log min; 9:
> log [2 (X)
14

---

Published as a conference paper at ICLR 2023
The inequality is because min; 9: [x]] (otherwise, E. Es [x((x)] 1). The equality of the inequality is obtained when q the uniform distribution, i.e. q u. Therefore, u argmin, maxp KL(p, q).
Next, we prove Equation 7 for La distance Va 1.
The La distance is defined as:
La (P,
② 1pe - 1ilo///0
(12)
Take the derivative of La (p, 4) with respect a p::
0h (p. ②) =
1 (2, lp: - -/1)) app - 11000-)-1111 pf 2 q
(13)
Ei Ps 2: (21))//a-a((4 p;) otherwise
This means if PA where 8 > increases (p. q) and eventually replacing Pt. Pj with pt + Py- increases La (p. Let k arg max; - q; For each pair (Pk. P:) o k. we replace pk to be + and
2 Pj - 9j. (p.g) 2 (p.0)
Therefore, replacing ps. Pj with + 6,
P3
P: to be 0 and eventually we have pt and pj 0,,
Σ p. 1/
14:1"
(14)
i
Apparently, when & arg min, qs the right hand side is further maximized. Without loss of generality, we can assume 91 S 12 S ... < q (X))- Therefore:
max La (p. q1)
+
a )////a
(15)
i>1
By the Hölder's incquality (Hardy et al. 1988
Σ 2 (1) - 1)a- 4:)a = (1y - 1) () 91)aa
(16)
1>1
i>1
where equality in the inequality is obtained when Q2 = ..... -[(x(1111- Therefore:
max Las (p, 9) 2(11 - 21 + (1))(()) a1 - 2//0
2(1
1
1a + (X,,(X) - 1) 1-a (1 [x)(X) 1a91/a
My
(17)
=(1 (X)) - )a [x(x0) -1 11/0
(X))
M2 (X)
where the second inequality is because ((1 (11-1) 21 )0+ + My (X) (1-)))))1)))))) )
(1-
monotonically
decreases as gi increases and we have Q1 S [X][ because (i the minimum q, i.e. Q1 S 92 S
(X)I-
In summary, the minimum of maxp La (p q) is obtained when g2 =
(x))(X) and qx,,(x)i [x]] In other words, u.
Q1 X which means Q1 42 93 Therefore, u = argmin, maxp (p.q) q)
Proof for Average-case Optimal.
Proof.
Ep (L 9)1
KL PPP()dd
P(p) Σ lo dp
(18)
| P(p) Σ pi logpddp
P(p) Σ Pe log didp
15

---

Published as a conference paper at ICLR 2023
Since the first term is irrelevant to q. have:
J P(P) Σ
[p] q))
=constatt
Ps log q:dp
=constant
Σ log qi p(p)p,dp
(19)
Σ Ug log qi
=constant
where the last equation by the assumption that P(p) is centrally symmetric, i.e. I, P(p)pdp = u. Therefore:
Epp KL(p, 4)
constant
Σ
Uy log qi
constant
Σ
log 9:
(X)I
1
log II qi
(20)
constant
(X))
(X) log(l Σ, li ( (Xy)
1
constant
-oonstant + loollo((( (X)])
where the inequality is the inequality of arithmetic and geometric means. The equality of the in- equality is obtained when Q1 Q2
Q(,(X)) [((x))= ie. q u. Therefore,
= argmin, Ep[KL(p, 4)].
B PROOF FOR THEOREM 2
VX E D, if the corresponding is uniformly sampled and valid, when [D] + +o0, then arg min, C(h, D) hX(X)= [X Eyeu,(x) y.
Proof. For each X, let D(X) denote the subset {(X, (X, (X, loss on D(X) is:
of D. The cross entropy
[D(X] n Σ
log( 1 (())()) +
y log(1 1 1+ M()) 2
(21)
2
2
where denotes the number of rows in X; We use [j] to index the jth item of its preceding vector; We convert the region of y/[z] and h(X) from [-1, 1] to [o, by adding 1 then dividing by 2. By taking derivative and setting zero, the above equation minimized when:
|P(X) vili [D(X]
h(X)b1
Vj
222)
When D too (so that [D(X) +00), by the law of large numbers (Dekking et al.
I wiii E(ybi]|X). Since p(y(X) is uniform, E [
2005 h(X)si]
E
EvEu,(X) (X, أiا for Vj. This means h(X)- = Eyeu( y h*()).
C PROBABILITY OF GENERATING VAL.ID PAIR
To simplify analysis, in the following, only consider y that contains both -1 and +1, which has a probability Po 2. Pn ss 1 when n 2 100 (When generating data, we sample n from (Te, H.) [100, 2000] which we explain in Appendix Eb.
16

---

Published as a conference paper at ICLR 2023
Let S denote the set of all possible pairs of (X, y) and let u = ((X,)))o(.y)) 1] de- note the set of all valid pairs. S is made up by three subsets: U = ((X,y) =
D:x, = 2 or - g(x, y, = 3) and S: = S - -u- - Se. Apparently S. is also made up by three subsets, i.e. S. = Sa U Sog U
1, Se = {(x, y)1 مi=
Seg where Sai = {(x, y) -= g(X, v. 11) < 2 and Ej=
< 7)
Soz = {(X u) E (X, -1) < m and ا g(X. > 2 and Sea
((X,9) E/= y: -1) > z and Σコ= g(X, 9) < 7)
Lemma 3. |Sc,1 = |Sc, = |Scyl = [n
Proof. For each element (X,y) in San Σラ= g(X, y - < < and Σーー We can flip Xly - 1,:] be -X(y 1,:] and flip X -1, to be -x -. After flipping. we obtain pair (XX', y), and apparently (X' E U. This means for each element in S there is a corresponding element in U, so we have Sa,, S [2]. Similarly, for each element in U,
m
we can do flipping to get an element in Seg. so we also have [M] I |., Therefore, M = S..
Similarly, one can show that [24] = |Scyl and [M]| = |5
By Lemma 3 | = |Sc, + es,, + |5c 3/24/. When m is odd, apparently, Seel 0. Therefore, the probability of a randomly generated pair being valid is:
[24| S
1
p((,, y) E U Umm)
(23)
+ + S. + Sc
Next, we consider when is even. To simplify our analysis, approximately, p(g(X, y. 1))
and pX,(X, v. 1)) 1.2 This is because the probability that the number of correct elements exactly equal to the number of incorrect elements for each class is extremely small due to n being relatively large. Therefore, we have:
(m/2)
p((X,)) 3) (.mm)
(24)
2
Therefore:
(m/2)
1
p((X,)) y) E [M = (1
(25)
2m
4
Since m is uniformly sampled from [L,, Hml = [2, 60) (which we explain in Appendix we have:
p((X, EU)=
Σ
1 +
Σ
1
(1
m//2
1
Hm - Lm 4
Hm
Lm
2
4
m,m%2 - I. Sm Smm
m.m 22 -0 J. Sm SmSHu
m
1
1
Σ
(1
m2/2
1
2
Hm
Lm
2
m.m%2=0 Lmm Hm
00.232
(26)
This means the probability of generating valid pair in one trial is about 0.232.
D DISCUSSIONS
D.1 THE PROPOSED ARCHITECTURE SATISHIES THE THREE PROPERTIES
To see how the proposed architecture in Figure I satisfies the three properties mentioned in the begining of Section 5.2 First, GNN accepts arbitrary input size, so X can be of any size; Second, GNN is permutation equivariant to the nodes, so the output embeddings of GNN are equivariant to the permutation of data points and LFs. After average pooling for each data point over all LFs (each SCC with dashed blue edges), the network is invariant to the permutation of LFs and is still equivariant to the permutation of data points.
17

---

Published as a conference paper at ICLR 2023
D.2 CROWDSOURCING METHODS FOR WEAK SUPERVISION
The two crowdsourcing methods have the worst performance in Table 2 The reason that crowd- sourcing methods don't t work well on weak supervision datasets has not been investigated or dis- cussed in prior work, and we provide our conjecture. First, the label matrix in crowdsourcing tends to be extremely sparse as there can be many crowd workers while each crowd worker might anno- tate a few data points then quit (Zheng et al.] 2017]; In contrast, in weak supervision, each LF is applied to each data point, Second, since crowd workers are humans, the labels provided by the crowd workers tend to have higher accuracy; In contrast, a LF when applied on data unseen by the LF developer can predict very noisy labels. In other words, the existing crowdsourcing methods are designed to work in the sparse scenario with weak labels of higher accuracy, so that they don't 't work well in the weak supervision setting with denser and noisier label matrix.
E IMPLEMENTATION DETAILS OF HLM
Data Generation. When generating each pair (X, y), we first randomly generate n and m, the num- ber of rows/columns of matrix X. Note n is the number of data points and is the number of LFs. As we mentioned, we first sample n and m uniformly from [L,, H,] and [Lm; Hm] respectively. We set [L, H,] [100, 2000] where Ln 100 is because typically there are at least hundreds of data points otherwise it is not necessary to write LFs as one can just manually label all data points and set H 2000 due to memory limit during model training. We set [I.m, H..] = [2, 60) where Im = 2 is because when there is only one LF there is no need to aggregate and we set Hm = 60 due to memory limit during model training: We highlight our trained model generalizes well number of LFs and number of data points (see Table I that are not in the region [mm, Hm] and [L., Hn] as we have shown in experiments. Once we have n and m, we invoke the method mentioned in Section 5.1 to generate y).
Since our data is synthetically generated, there is no need to generate a fixed training set. Our training data is generated on the fly, i.e. during training when the data loader fetches the next pair of (X, y). new pair is immediately generated and returned.
Model Architecture. We implement our model architecture in Pytorch (Paszke et al. 2019). We use K = 4 layers of GNN. The embedding dimension of GNN is 32, i.e. each node in the graph is encoded with 32 dimensional embedding. The final MLP consists of three linear layers; the first two linear layers use Relu activation and the last linear layer uses Sigmoid activation.
Model Training, We use the Adam optimizer (Kingma & Bag 2014). We set amsgrad to be true for better convergence (Reddi et al. 2019) and keep all other parameters as the default values provided by Pytorch (e.g. learning rate Ir 0.001). We use a batch size of 50, i.e. each batch consists of 50 pairs of generated (X, y). We tested different batch sizes of 16 and 250 and observed no meaningful difference. We train our model until training loss converges (loss doesn't 't decrease in 10a iterations), which takes about one day with 5 x 10a iterations on K80 GPU. Note one iteration means one gradient update/one batch, and don't have the notion of epoch as training data is generated on-the-fly for each batch.
Validation. We also need to prevent our model from overfitting the training set. We highlight that, different from typical ML settings where one gets access to a validation set that is similar to the test set, in our setting we have no validation set that is similar to the test set. Again, when training our model, the real test datasets are unseen and we only have access to synthetic data. Our intuition that when the model overfits the sythetically generated training set D, its performance will be poor on data that is different from the training set, for example, on another sythetic dataset D' that is generated in a different way. We synthetically generate the validation set D' with size [D'| 100 according to the generation method proposed in (Zhang et al. 2021 In this method, LFs are independent from each other conditioned on the ground-trum label.
We note that the way we use the validation set is also different from typical setting. We train the model until training loss converges (this typically requires about 5 x 10* iterations), and repeat 10 runs (i.e. train our model 10 times from scratch). We then select the run with the highest averaged validation accuracy over all iterations (as validation accuracy might fluctuate over itcrations): We use the learned model at the final iteration of the selected in experiments. We provide our
18

---

Published as a conference paper at ICLR 2023
validation acouurucyy
2.6
3.5
number of iterations
Figure 3: Accuracy on the synthetic validation set D' vs number of training iterations. The purple line and yellow line are two different runs. The yellow run is selected as it is more stable with higher averaged validation accuracy.
reasoning of doing this: (1) We do not use the validation set to do early stopping (i.e. to select the best iteration in a run). In a typical ML setting, the validation set used to select the best epoch/iteration. This is possible because in typical MI setting the validation set is similar to the test set and the validation set provides very strong signal towards which itcration is a good iteration for the test set. In our case, the validation set D' can be very different from the test set, thus the selected iteration based on D' might not be a good iteration for the test set. (2) We use the validation set to select the best run. We observed that different runs, the curve of validation accuracy vs number of iteration can be different (e.g. the two runs in Figure B so the test accuracy of the model in different runs can be different. We would like select the best run using the validation D'. Intuitively, one run with better validation accuracy on average over all iterations is stably better (e.g. the yellow run in Figure B}. so we select the run with an best averaged validation accuracy over iterations. As an example, for the two runs in Figure 3 although the highest validation accuracy of purple run can be higher than that of the yellow run, the yellow run has a higher averaged validation accuracy over iterations and is much more stable, so we select the yellow run. We also observed this run to have less degree of fluctuation in validation accuracy, as shown in Figure 3 This suggests the model converges at a flat minima, which is known to generalize better (Li et al. 2018 Keskar ct al. 2016, Izmailov et al., 2018).
One natural question is that why it is possible to select the best run but it is not possible to select the best iteration. The reason is that selecting the best run out from 10 runs require much less information than selecting the best iteration out from 5 x 10 iterations. Since the validation set D can be very different from the test set, the information provided by D' is very limited.
An interesting phenomenon in the validation accuracy curve in Figure 3 for the yellow run is that validation accuracy first increases then decreases and finally increases. A similar trend was observed in prior work (of different task) that also trains model synthetic data and validate on a different data distribution (Wu et al. 2022c). We believe this is a double descent phenomenon (Nakkiran et al.) 202T) induced by the distributional difference between the training and validation sets.
F
ADDITIONAL EXPERIMENT RESULTS
F.1 RUNNING TIME
We report the rumning time for all methods in Table 5 For MV, DP, FS, DS, EBCC, and CLL, the running is on CPU as these methods do not support GPU. For MeTaL, NPLM and HLM, we report the running time on CPU and GPU.
F.2 END MODEL PERFORMANCE
We use the generated labels of each method to train end model for each dataset. We consider the three best performing baselines MV. MeTaL and CLL. We use the test split provided by the benchmark (Zhang al. 2) for each dataset because some datasets only have ground-truth labels for data points in the provided test split. We then randomly split the remaining data points to a training set and validation set with 3:1 ratio. The labels in the training set and validation set are generated labels by each label model, while the labels in the test set are ground-truth labels for evaluation. Following prior work (Ratner et al. 2016.
Zhang al. 2021), the probabilistic labels
19

---

Published as a conference paper at ICLR 2023
Table 5: Running time (seconds) of label aggregation on all datasets with CPU and GPU.
Dataset
Consus
IMDB
Yelp Youtube SMS Spouse CDR Commercial Teanis Basketball AGNews
TREC SomEval ChemProt AVG.
MV
<0.1
<0.11
<0.1
<0.1
<0.1 <0.1
<0.1
<0.1
<0.1
<0.1
<0.1
<0.1
<0.1
<0.1
<0.1
DP
147.8
18.8
40.5
2.5
14.4
8.4
29.5
8.5
10.0
14.9
225.0
100.8
190.2
213.0
73.2
TS
21.1
1.7
3.7
0.2
3.2
0.8
3.7
0.6
0.6
14.9
22.1
16.3
69.0
26.4
12.2
MeTaL-GPU 0.5
0.3
0.4
0.4 0.3
0.4
0.4
0.4
0.5
3.6
4.6
3.6
1.2
McTaL-CPU 1.1
0.3
0.4
0.4
0.9 0.3
0.9
0.4
0.4
0.4
0.5
16.7
18.1
16.5
4.1
NPLM-GPU
2.2
11.2
1.5
5.4
12.1
7.2
NPLM-CPU 156.7
56.0
5.7
0.4
19.8 1.8
6.3
11.2
1.5
3.4
29.9
49.9
25.9
132.6
35.8
2.4
79.8
116.1
3.6
267.7
4.6
36.6
EBCC
3.9
5.1
52.5
2.2
2.8 2,3
5.8
3.0
2.5
6.0
18.0
9.0
9.8
84.8
14.8
CLL
33.7
2.9
6.6
0.5
3.8
7.4
1.1
2.0
28.5
12.4
20.5
21.3
10.6
HLM-GPU
0.1
0.1
0.1
0.1
0.1
0,2
0.2
0.3
0.2
0.3
0.4
0.2
0.3
0.2
0.2
IILM-CPU
0.9
0.2 0.3
0.2
0.2
0.7
0.7
1.1
0.3
0.9
4.6
4.4
1.9
7.3
1.7
instead of the hard labels are used to train the end model when possible. We adopt the end models used (and their implementations provided by) the benchmark (Zhang et al. 2021 Zhang 2022a), i.e. pretrained BERT model (Devlin et al.] (018)) for textual datasets and a multi-layer perception (MLP) for datasets with numeric features. We report the results on test set Table 6 Again, to maintain the table to be readable, we only show the error bars for the averaged scores.
Table 6: Performance of end model trained with labels generated by each method.
Daraset
Census
IMDB
Yelp
Youtube SMS
Spouse CDR Commercial Temii Basketball AGNews
TREC SemEval ChemProt AVG.
End model MLP
BERT
BERT BERT
BERT BERT
BERT MLP
MLP
MLP
BERT
BERT
BERT
BERT
MV
31.7
74.7
74.2
90.9
83.5
51.6
62.9
90.1
83.5
13.4
81.9
63.9
76.8
$4.6
66.740.8
MeTal.
11.6
74.4
51.0
63.5
83.1
65.240.2
CLL
51.5
73.6
72.8
81.8
83.6
52.0
59.8
89.6
83,5
19.3
81.7
68.4
82.8
53.0
68.12003
56.3
74.7
93.0
82.4
52.3
64.1
87.1
83.5
17.0
80.8
68.4
82.8
69.4:10.3
Our results align with those in the benchmark (Zhang et al. 2021) where the end model trained on labels generated by McTaL is slightly worse than that by MV. Overall, HLM outperforms the other three methods. On Yelp. Spouse, and SemEval, HLM tied with MV in label quality (see Table 2 but has better end model performance HLM's probabilistic labels can be more informative. Note the scores of the end model can be higher than that of the generated labels (as also observed in the benchmark (Zhang al.) [222I) and prior work (Ratner et al. 2017)) because the end model incorporates additional information from the raw data.
G IMPLEMENTATION DETAILS OF EXPERIMENTS
Hardware. All of our experiments were performed on machine with 2.20GHz Intel Xeon(R) Gold 5120 CPU, K80 GPU and with 96GB 2666MHz RAM.
Datasets. We use the datasets prepared by the wrench benchmark on Github Zhhag 2022a Zhang et al. 2021). All the datasets and LFs are publicly released by previous work (Zhang et al. 2021 All datasets do not contain any personally identifiable information (Zhang et al. (2021).
Originally, each dataset include three files "train.json", "valid.json" and "test.json". Following the suggestion in a reported issue of the wrench benchmark (Zhang) 20226), we combine all three files to label aggregation.
get single matrix X and single ground- label vector y for the experiments We then split the datasets using the original split for the experiment on end model (Appendix (.2)) The information of the LFs well as the data for each dataset can be found in the wrench benchmark project on Github (Zhang) 2022a).
Baselines. For each baseline, of DS, DP, FS, MeTaL, EBCC, NPLM, and ACML-CC are from (sukrutrao) (2022). (snorkel team 2022a), (HazyResearch) 2022)
existing open-source implementations. The implementations
(snorkel team 2022b), (yuan li 2022). (BatsResearch) 2022a)
20

---

Published as a conference paper at ICLR 2023
and (BatsResearch) 2022b) respectively. For baselines that require class weights as priors, report the best results from using uniform weights and using the weights estimated by majority vote.
Setup in Semi-supervised Label Aggregation. When sampling Ngt data points as the data points with known labels, we make sure that each class has at least two data points. For random forest, the scikit-learn implementation (ris) 2022). When training the random forest classifier, use five fold cross validation to perform grid search for the "max "d_eppphhh parameter in range [2, 4, 8, 16, 32, None] and the "min_samples samples.spp split" parameter in range [2, 5J. The AMCL-CC method does not support abstention, to make it work we fill in the abstentions with labels provided by majority vote; AMCL-CC requires lot of memory on some datasets and involves solving constrained linear programming problem which may not have a solution. When AMCL-CC fails due to out-of- memory error or so-sutoooo--- error, we use the results from random forest. We repeat five runs and report results with error bars in Figure
Setup in Ablation Study. For model architecture, we test two baselines. The first one is based on MLP. The input is flattened vector of a fixed size matrix 2000 x 50 (padded with zero if the input matrix is smaller) and the network has linear layers. The second one is based on DeepSet (Zaheer et al., (017) where each row of X is treated as a set. We use open source implementation (manzilzaheer 2022). We replace each of our GNN layer with a DeepSet layer.
Setup in End Model Experiment. When training the end model, the training set and validation set both use generated labels by each method and the test set uses ground-truth labels. For the two end model MLP and BERT, we use the implementation provided by the benchmark (Zhang 2022a Zhang et al.] 2021). We use grid search to tune
for each end model based on validation set performance. We the search space the benchmark (Zhang et al. 2021 as We repeat five runs and report the scores averaged over runs in Table
summarized in Table 7
Table 7: Hyper-parameters and search space for the end models.
End Model
Hyper-parameter
Description
Range
batch_size
batch size
32,
Ir weight.decay ffn num layer ffn hidden size
learning rate
1e-5.le-41le.3.ee22.ee
MLP
weight decay
1e-5.1e-4.1e3331ee221..l 2
number of MIP layers
hidden size of MI. layers
100
batch size Ir
batch size
16,32
BERT
learning rate
20-5.3e-5,5e-5
21


Reviews:
[{"review_id": "yUAHWkFqypt", "reviewer": "Reviewer_SvzH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors proposed for the first time a theoretically motivated label model for programatic weak supervision (PWS), called a hyper label model based on GNN. The model can be used to aggregate any list of labeling functions (LFs) for any task and infer ground-truth labels in a single pass, without need any dataset-specific training of the label model. Empirical results are quite strong compared to SOTA.", "summary_of_the_review": "To the best of my knowledge, the paper is a significant contribution in PWS with a brand new idea of (pre)training a one-fits-all label model. Many readers should find the paper interesting.", "strength_and_weaknesses": "Strengths:\n\n1. The paper takes on a novel perspective for PWS, that trains a hyper label model that can be used off the shelf universally for any task, any list of LFs and any training data. The training is entirely unsupervised, theoretically founded (Sec 4) and tractably approximated by a data generation process (Sec 5).\n2. The model can either be used on its own (as a hyper label model), or further fine tuned if some ground truth labels are used. To me the idea is an interesting counterpart in PWS to the well studied concept of \"unsupervised pretraining\" in Vision and NLP. IMHO this is a very refreshing first step that can inspire a whole new branch of ideas and solutions in PWS. (Perhaps the authors can also comment their view on this, since my impression is that the paper wasn't positioned this way, e.g. no mention of related works in transfer learning?)\n\nWeaknesses: I think the paper is in a very good shape and only have some minor questions/comments/clarification.\n\n1. There seems to be a gap between the loss functions in the theoretical analysis (L2 loss in Eq. 4) and the one used in training GNN (CE in Eq. 5). Can the authors please comment on this? In particular, I wonder what happens if L2 loss is used for training (ablation?)\n2. Following the last question, have the authors considered/tried, in Step 2 (Sec 5.1), generating one X and several valid y's, and add (X, \\bar{y}) as a training point (using L2 loss as now \\bar{y} would not be binary anymore), and why not do this?\n3. The data generation process uses a uniform distribution throughout. Have the authors tried other distributions? In particular, in Step 2 (Sec 5.1), the method simply samples each cell in X i.i.d. uniformly from {-1, 1, 0} (if I wasn't mistaken?) Real world LFs have varying degree of accuracy and correlation (Snorkel's assumption), the data generation model seems oversimplified and can be very different from real data. For instance, would it make sense to pull a large set of real world X's (e.g. combining all X's from WRENCH datasets) and only simulate y?\n4. Given the difference between the synthetic vs real world distribution of X, I'm quite surprised that fine tuning didn't really improve much over the pretrained model (Fig 2). Do the authors have some intuitions?\n5. Why does one have to convert to one-vs-rest binary tasks in order to train multiclass hyper label model? Perhaps I miss the point, I didn't see any blocker from simply simulating multiclass y and using multiclass CE in Eq 5?\n6. The proposed model is referred to as hyper label model before Sec 6 and as LELA after, it would be good to unify them?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "RdcbJdALwWZ", "reviewer": "Reviewer_AEYU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a general method (hyper label model) to infer pseudo-labels in weak supervision that doesn't require learning parameters for each dataset separately. They characterize an optimal analytical model that is computationally intractable but gives true labels for any dataset under mild assumptions on labeling function -- better than random for each class. They give a novel hyper label model based on Graph neural networks to approximate this optimal analytical model. The choice of GNN is motivated by the setting -- it requires the model to be invariant to the permutation of LFs (or data points). They empirically evaluated the proposed solution on 14 real-world benchmark datasets for this problem and found that the proposed hyper label model works better than the baselines on most of the  datasets.\n", "summary_of_the_review": "The paper brings in a novel and valuable perspective on learning label models for weak supervision. The evaluation is satisfactory. I have a few questions and concerns listed above, except those I liked reading the paper.", "strength_and_weaknesses": "Strengths:\n1. I like the idea to have a single label model that can work across various datasets and the use of GNNs as label model so that the model is invariant to the permutations of LFs. \n2. The empirical evaluation on benchmark datasets is comprehensive and shows the benefit of their method.\n3. They give a method to generate training data to train the hyper label model so that it can work across various datasets. \n\nWeaknesses/Questions:\n1. The assumptions in Section 3 are reasonable. However I am not quite sure if the assumption per class is a weaker form or stronger form ? It seems stronger to me? Moreover won't majority vote alone give accurate inference under such assumption? Could you please share some analysis on this aspect and justify why would one need a hyper label model when this assumption is satisfied?\n\n2. What happens to the noise rates of different labeling functions? How are they getting accounted in the inference procedure? \n\n3. A single solution for all datasets might be too much to ask for and it is very much possible that by optimizing for generality one looses the specific advantages while optimizing for a specific setting. Are there ways to optimize the process for the dataset at hand?\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Po1I477g-7", "reviewer": "Reviewer_jYPK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a new approach that uses programmatic weak supervision. First, labeling functions are used to generate weak labels for each example. Then, a hyper label model is used to infer the ground-truth labels from the weak labels. The hyper label model is Graph Neural Network (GNN) that is trained on synthetic data, and it can be used on any new dataset without retraining. The paper also introduces a weaker assumption about the labeling functions:  the majority of labeling functions have to be better than random. The proposed approach is evaluated on 14 classification datasets and shows better results on average.", "summary_of_the_review": "Overall, I think the paper is good and interesting but I have some concerns about one of the contributions and some design choices. Please check the Strength And Weaknesses section for more information.", "strength_and_weaknesses": "**Strengths**\n-The general problem tackled in this paper is interesting. Reducing annotation cost is an interesting research direction because it is cheaper to create new datasets or extend existing datasets.\n- I like the proposed assumption “the majority of labeling functions are better than random” because it seems to be more realistic as claimed in the paper.\n- I like the assumptions about the model architecture: (1) ability to accept arbitrary input size; (2) invariance to permutation of labeling functions. (3) equivariance to permutation of data points\nThe paper presented well the motivations behind these assumptions and how the proposed GNN model respects these assumptions. \n- I like the idea of training the hyper label model on synthetic data to not increase the annotation cost. It is also possible to improve the hyper label model performances by generating more data. I also like the fact that the hyper label model is trained only one time and can be used on multiple datasets without retraining.  \n- The hyper label model can work with missing weak labels. \n- The proposed approach shows better performances on average on multiple datasets (Table 2). The evaluation is performed in both unsupervised and semi-supervised settings. The proposed method seems faster than most of the baselines. An ablation study shows the impact of each key contributions  \n\n\n**Weaknesses**\n- I think some parts of Section 4 are a bit misleading because p(y|X) is approximated by a uniform distribution, so theorem 1 is an optimal solution of an approximate problem. There is no strong evidence the uniform distribution is the best approximation for p(y|X), and should maybe be presented as a good approximation instead of the best. I agree that the uniform distribution has optimalities in both the worst case and the average case, but it does not mean it is always optimal. *[post rebuttal] The paper has been updated to take into account this comment and remove the misleading part.*\n- I am not sure I understand the motivation of using a GNN instead of a simpler set-based model like DeepSet [A]. I agree that a GNN respects the proposed assumptions but I am not sure to understand why modeling the edges is important. I think adding an experiment with a DeepSet could help to justify this design choice. *[post rebuttal] The rebuttal gives a motivation to this design choice.*\n- The paper claims the data generation process is efficient but the probability of generating a valid pair is about 0.2, which does not seem very efficient. Maybe it could be interesting to propose a better generation process or to not claim the data generation process is efficient. *[post rebuttal] The paper has been updated to remove the claim.*\n- The results about the training of the hyper label model are in the supplementary and not in the main paper. I think the main paper should show at least some of them because it seems to be a key contribution of the paper. I would suggest reducing Section 3 and 4, by moving some parts to the supplementary, to have space to present some results about the training of the hyper label model.\n- The related section does not mention some other approaches to reduce the annotation cost like self-supervised learning methods. I think the related work section should discuss some of the other methods.  *[post rebuttal] The related work section has been updated to cover other approaches.*\n\n[A] Zaheer M., Kottur S., Ravanbakhsh S., Poczos B., Salakhutdinov R., Smola A. Deep Sets. In NeurIPS, 2017.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CrNmHEsqAOy", "reviewer": "Reviewer_YMpc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a \"hyper label model\" for weak supervision that can infer ground-truth labels for any weak supervision dataset without retraining. The authors evaluate their hyper label model in accuracy and efficiency on 14 benchmark datasets. The hyper label model is more efficient and on average slightly more accurate.", "summary_of_the_review": "Overall I think this paper is strong, with a clear contribution and results. I have a few questions about the results and experiments, but they can be addressed fairly easily. I plan to give this paper a score of \"accept\" - contingent on having my questions answered in rebuttal.\n\nUpdate after the rebuttal: I am decreasing my score to a 5 because of concerns about the characterization of previous better-than-random assumptions.\n\nSecond update after the rebuttal: Raising my score to a 6 - I think the paper is would be a positive contribution to ICLR.", "strength_and_weaknesses": "+ Clear idea, clear evaluation.\n+ The method seems to be empirically well-suppported in terms of accuracy of the final model\n+ Theoretical support for existence of an optimal label model and conditions for finding one\n\n- Theoretical analysis is unclear in the case of class-imbalanced data (which is the common case in practice)\n- Experiments on efficiency a little incomplete (see Q's below)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster