Universalizing Weak Supervision
Authors: Changho Shin
Winfred Li
Harit Vishwakarma
Nicholas Carl Roberts
Frederic Sala
Venue: ICLR 2022 Poster (2022)
Keywords: Weak supervision

Abstract: Weak supervision (WS) frameworks are a popular way to bypass hand-labeling large datasets for training data-hungry models.
These approaches synthesize multiple noisy but cheaply-acquired estimates of labels into a set of high-quality pseudo-labels for downstream training. However, the synthesis technique is specific to a particular kind of label, such as binary labels or sequences, and each new label type requires manually designing a new synthesis algorithm. Instead, we propose a universal technique that enables weak supervision over any label type while still offering desirable properties, including practical flexibility, computational efficiency, and theoretical guarantees. We apply this technique to important problems previously not tackled by WS frameworks including learning to rank, regression, and learning in hyperbolic space. Theoretically, our synthesis approach produces a consistent estimators for learning some challenging but important generalizations of the exponential family model. Experimentally, we validate our framework and show improvement over baselines in diverse settings including real-world learning-to-rank and regression problems along with learning on hyperbolic manifolds.

Published as a conference paper ICLR 2022
UNIVERSALIZING WEAK SUPERVISION
Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Roberts, Frederic Sala Department of Computer Sciences University of Wisconsin-Madison {cshin23, wli525, hvishwakarma, ncroberts2, fsala]
ABSTRACT
Weak supervision (WS) frameworks are popular way to bypass hand-labeling large datasets for training data-hungry models. These approaches synthesize multiple noisy but cheaply-acquired estimates of labels into set of high-quality pseudolabels for down- stream training. However, the synthesis technique is specific to a particular kind of label, such as binary labels sequences, and each new label type requires manually designing new synthesis algorithm. Instead, we propose a universal technique that enables weak supervision over any label type while still offering desirable properties, including practical flexibility, computational efficiency, and theoretical guarantees, We apply this technique to important problems previously not tackled by WS frameworks including learning rank, regression, and learning in hyperbolic space. Theoretically, our synthesis approach pro- duces a consistent estimators for learning some challenging but important generalizations of the exponential family model. Experimentally, we validate our framework and show improvement over baselines in diverse settings including wooldw learning-to-re -to-nnkk and regression problems along with learning on hyperbolic manifolds.
INTRODUCTION
Weak supervision (WS) frameworks help overcome the labeling bottleneck: the challenge of building a large dataset for use in training data-hungry deep models. WS approaches replace hand-labeling with synthesizing multiple noisy but cheap sources, called labeling functions, applied to unlabeled data. As these sources may vary in quality and be dependent, crucial step is to model their accuracies and correlations. Informed by this model, high-quality pscudolabels are produced and used to train downstream model. This simple yet flexible approach is highly successful in research and industry settings (Bach et al. 2019 Ré al. 2020
WS frameworks offer three advantages: they are (i) flexible and subsume many existing ways to integrate side information, (ii) computationally efficient, and (iii) they offer theoretical guarantees, including estimator consistency. Unfortunately, these benefits come at the cost of being particular to very specific problem settings: categorical, usually binary, labels. Extensions, e.g., to time-series data (Safranchik et al.) [2020). to segmentation masks (Hooper et al.) 2021), require a new model for source synthesis, new algorithm, and more. We seek to side-step this expensive one-at-a time process via a universal approach, enabling WS to work in any problem setting while still providing the three advantageous properties above.
classification, structured prediction, regression, rankings, and more. Each of these settings scemingly demands different approach for learning the source synthesis model, which we refer to as the label model. For example, Ratner et al. (2019) assumed that the distribution of the sources and latent true label is Ising model and relied property of such distributions: that the inverse covariance matrix is graph-structured. It not clear how to lift such property to spaces of permutations to Riemannian manifolds.
The main technical challenge for universal WS the diversity of label settings:

---

Published as a conference paper ICLR 2022
Rerkings
Regression
Gooderk Regression
Other Task
Universal Supervision Framcwork
Embeidingg
x
y
1
Label Model
Universal Weak Supervision Framework
Parameter Extmation laceest alia viglacesthed
Label Inferenss
v
(L.
Ronk Model
Regunsioon Model
Model
EodModd
B(ca(A-y))
Figure I: Applications enabled by our approach (left) and weak supervision pipeline (right).
We propose a general recipe to handle any type of label. The data generation process for the weak sources is modeled with an exponential family distribution that represent a label from any metric space (V), dy). We embed labels from Y' into two tractable choices of space: the Boolean hypercube {=1}d and Euclidean space Idd The label model (used for source synthesis) is learned with an efficient method-of- approach in the embedding space. It only requires solving a number scalar linear or quadratic equations. Better yet, for certain cases, we show this estimator is consistent via finite sample bounds.
Experimentally, we demonstrate our approach on five choices of problems never before tackled in WS:
Learning rankings: on two real-world rankings tasks, our approach with as few as five sources performs better than supervised learning with a smaller number of true labels. In contrast, an adaptation of the Snorkel (Ratner et al. 2018) framework cannot reach this performance with as many as 18 sources.
on two real-world regression datasets, when using 6 or more labeling function, the perfor- mance of our approach is comparable to sully-sueer models.
Regression:
Learning in hyperbolic spaces: on geodesic regression task in hyperbolic space, we consistently out- perform fully-super learning, even when using only labeling functions (LFs).
Estimation in generic metric spaces: in a synthetic setting of metric spaces induced by random graphs we demonstrate that our method handles LF heterogeneity better than the majority vote baseline.
Learning parse trees: in semantic dependency parsing, we outperform strong baseline models.
each experiment, we confirm the following desirable behaviors of weak supervision: (i) more high-quality and independent sources yield better pseudolabels, (ii) more pseudolabels can yield better performance compared to training on fewer clean labels, (iii) when source accuracy varies, our approach outperforms generalizations of majority vote.
2 PROBLEM FORMULATION AND LABEL MODEL
We give background on weak supervision frameworks, provide the problem formulation, describe our choice universal label model, special cases, the embedding technique we use to reduce our problem to two easily- handled cases, and discuss end model training.
Background: WS frameworks are a principled way to integrate weak or noisy information to produce label estimates. These weak sources include small pieces of code expressing heuristic principles, crowdworkers, lookups in external knowledge bases, pretrained models, and many more (Karger et al. [001]] Mintz et al.)
2009 Gupta & Manning 2014 Dehghani al. 2017 Ratner al. 2018). Given an unlabeled dataset, users construct a set of labeling functions (LFs) based on weak sources and apply them to the data. The estimates produced by each LF are synthesized to produce pseudolabels that can be used to train downstream model.
2

---

Published as a conference paper ICLR 2022
Problem Formulation: Let ø1, #2, ..... In be dataset of unlabeled datapoints from X. Associated with these are labels from an arbitrary metric space y with metric dy[" In conventional supervised learning, we would have pairs (æ1. 91)..... (In, Vn); however, in WS, we do not have access to the labels. Instead, we have estimates of from m labeling functions (LFs). Each such LF X + ) produces an estimate of the true label y from a datapoint x. We write (i) E y for the output of the ath labeling function estimate of the true label yi using the LF outputs (t). This estimate y. is used to train a downstream model. To produce it, we learn the label model P(X,, X, ,"".; The main challenge is that never observe samples of y; is latent.
8a applied to the ith sample. Our goal is to obtain (1))....
We can summarize the weak supervision procedure in two steps:
Learning the label model: use the samples (i) to learn the label model P( X² ..... (")
Perform inference: compute Úi P(y (i). (i)). or related quantity.
Modeling the sources Previous approaches, e.g., Ratner et al. (2019). select a particular parametric choice model p( , lyy) that balances two goals: model richness that captures differing LF accuracies and correlations, and (ii) properties that permit efficient learning, Our setting demands greater generality. However, we still wish exploit the properties of exponential family models. The natural choice is
T7U
p(A
A
A
Z exp
0a (a .0++
Σ (a,6)EE
(1)
Accuracy Potentials
Correlation Potentials
Here, the set E' is set of correlations corresponding to the graphical representation of the model (Figure right). Observe how source quality is modeled in (I). If the value of 0₂ is very large, any disagreement between the estimate X" and y penalized through the distance dx, y) and so has low probability. If A, is very small, such disagreements will be common; the source is inaccurate.
I
We also consider a more general version of (T). We replace -0 (X*, 3) with a per-source distance de..
For example, for y = { dg, (A", y) = - -vl. with 0, E generalizzs the Hamming distance. Similarly, for y = Rdd we can generalize -0al|>- - yll² with dg, Oa Raxd p.d., so that LF errors are not necessarily isotropic. In the Appendix B we detail variations and special cases of such models along with relationships to existing weak supervision work. Below, we give a selection of examples, noting that the last three cannot be tackled with existing methods.
- -y) (2, y), with
Binary classification: y' {++11, dy is the Hamming distance: this yields shifted Ising model for standard binary classification, as in Fu et al. (2020).
Sequence learning: y = [+1]d. dy is the Hamming distance: this yields an Ising model for sequences, as in Sala et al. (2019) and Safranchik et al. (2020).
Ranking: y = Sp. the permutation group on []....,p.. dy is the Kendall tau distance. This is a heterogenous Mallows model, where rankings produced from varying-quality sources. If 1, we obtain a variant of the conventional Mallows model (Mallows) 1957).
Regression: y R, dy is the squared & distance: it produces sources in Id with Gaussian errors.
Learning on Riemannian manifolds: y = M, Riemannian manifold (e.g.. hyperbolic space), dy is the Riemannian distance dM induced by the space's 's Riemannian metric.
Majority Vote (MV) and its Relatives A simplifying approach often used as baseline in weak supervision is the majority vote. Assume that the sources are conditionally independent (i.e. E' is empty in ([) and all accuracies are identical. In this case, there is no need to learn the model (I) instead, the most "popular"
We slightly abuse notation by allowing dy be d", where d is some base metric and i an exponent. This permits use, for example, the squared Euclidean distance-not itself metric-withour repeatedly writing the exponent c.
3

---

Published as a conference paper ICLR 2022
Problem
Set
Distance
MV Equivalent
Imíg)
End Model
Binary Classification
(=1)
E
Majority Vote
(L1)
Binary Classifier
Ranking
Sp
Kendall
Kemeny Rule
(+1)G)
Learning Rank
Regression
R
squared-22
Arithmetic Mean
R
Linear Regression
Riemannian Manifold
M
Riemannian
Fréchet Mean
R"
Geodesic Regression
Dependency Parsing
T
E2
Fréchet Mean
Raxa
Parsing Model
Table 1: A variety of problems enabled by universal WS, with specifications for sets, distances, and models.
label is used. For binary labels, this is the majority label. In the universal setting, natural generalization is
arg min zEY m E. dy(A",2).
DMV
(2)
Special cases of (2 have their name; for Sp. it is the Kemeny rule (Kemeny 1959). For das the squared Riemannian manifold distance, dMv is called the Fréchet or Karcher mean.
Majority vote, however, is insufficient in cases where there is variation in the source qualities. We must learn the label model. However, generically learning ( is an ambitious goal. Even cases that specialize (I) in multiple ways have only recently been fully solved, e.g., the permutation case for identical 0g 's was fully characterized by (200))))ee(2016) To overcome the challenge of generality, we opt for an embedding approach that reduces our problem to tractable cases.
Universality via Embeddings To deal with the very high level of generality, we reduce the problem to just two metric spaces: the boolean hypercube {-1,+1]4 and Euclidean space Rd To do so, let g Y + {=1]d (or y + IR)) be an injective embedding function. The advantage of this approach is that if g is sufficient statistics are preserved: for example, for g y + R -bady(X" y) = d ((()))) (A - (y)ll" so that if g is a bijection, we obtain a multivariate normal for c 2. g is not isometric, there is rich literature on low-distortion embeddings, with Bourgain's 's theorem as a cornerstone result (Bourgain 1985). This can be used to bound the error in recovering the parameters for any label type.
preserving-
probabilities are preserved under g. This is because the
by applying generalized majority vote or by learning the label model and performing inference-we can use the labels to train an end model. Table 2 summarizes examples of problem types, explaining the underlying label set, the metric, the generalization of majority vote, the embedding space Im(g), and an example of an end model.
End Model Once we have produced pseudolabels-
3 UNIVERSAL LABEL MODEL LEARNING
Now that we have a specification of the label model distribution (1) (or its generalized form with per-source distances), we must learn the distribution from the observed LFs X ..... A Afterwards, we can perform inference to compute ý or ply) ....... A or related quantity, and use these train a downstream model.
A simplified model with an intuitive explanation for the isotropic Gaussian case is given in Appendix D
Learning the Universal Label Model Our general approach is described in Algorithm I its steps can be seen in the pipeline of Figure| [ It involves first computing an embedding g(X²) into [=1]d or Rd; we use multidimensional scaling into Edd as our standard. Next, we learn the per-souree mean parameters, then finally compute the canonical paramelers 0g. The mean parameters are (g (X)))) which reduce to moments like Blg((*): Here de is some distance function associated with the embedding space. To estimate the mean parameters without observing y (and thus not knowing ((y)). exploit observable quantities and conditional independence. As long as we can find, for each LF, two others that are mutually conditionally independent, we can produce simple non-linear system each component of the moment). Solving this system recovers the mean parameters up to sign. We recover these as long as the LFs are better than random average (see Ratner et al. (219)).
the three sources (in
4

---

Published as a conference paper ICLR 2022
Algorithm 1: Universal Label Model Learning
Input: Output of labeling functions (i), correlation set E. prior for Y. optionally embedding function g-
Embedding: If g is not given, use Multidimensional Scaling (MDS) obtain embeddings g(\") E R va for a E (1.2..... ................................ , do
For b: (a, b) E E Estimate Correlations: È [g(A").g(A")
Estimate Accuracy: Pick b, (a, & E, (a, # (b,c)
if [m) [11}
vi. Estimate Õ..b P(g(A*); 1,9(X); = 1). On,,, On.e Estimate tu = P(o(A)); 1), lo
Accuracies QUADRATICTRUPLETSS h. Oaci O Eus Co Ler p., p.
else Vi, Estimate &. := E
Σz (()(())) (A)))) Eb.
Accuracies CONTINUOUS TRIPLEES((a.)) ca Ebre: P,
Recover accuracy signs (Fu et al. 2020)
end for return 0a, 0u.b by running the backward mapping on accuracies and correlations
The systems formed by the conditional independence relations differ based on whether y maps to the Boolean hypercube (=1}d or Euclidean space Rd In the latter case obtain a system that has simple closed form solution, detailed in Algorithm 2 In the discrete case (Algorithm 4 Appendix [), we need to use the quadratic formula to solve the system. We require an estimate of the prior p the label y: there are techniques do so (Anandkumar et al., 2014; |atner et al. 2019); we tacitly assume we have access to it. The final step uses the backward mapping from mean canonical parameters (Wainwright & Jordan [2008). This approach is general, but it is easy in special cases: for Gaussians the canonical 0 parameters are the inverse of the mean parameters.
Performing Inference: Maximum Likelihood Estimator Having estimated the label model canonical parameters 6₂ and 0. for all the sources, we use the maximum-likelihod estimator
ú arg min zEy
-
a=1 d3. (i),
Compare this approach to majority vote 2 observing that MV can produce arbitrarily bad outcomes. For example, suppose that we have m LFs, one of which has very high accuracy (e.g., large 01) and the others very low accuracy (e.g.. f2. 03.00..... fm 0). Then, A is nearly always correct, while the other LFs are nearly random. However, 2 weights them all equally, which will wash out the sole source of signal X!. On the other hand, (3) resolves the issue of equal weights on bad LFs by directly downweighting them.
Simplifications
While the above models can handle very general scenarios, special cases are dramati- cally simpler. In particular, in the case of isotropic Gaussian errors, where de, (X", = -O yll?: there is no need to perform an embedding, since we can directly rely on empirical averages like Di=1 de, (i), (i)). The continuous triplct step simplifies to directly estimating the covariance entries
9, the backward map is simply inverting this. More details can be found in Appendix D
4 THEORETICAL ANALYSIS: ESTIMATION ERROR & CONSISTENCY
We show that, under certain conditions, Algorithm produces consistent estimators of the mean parameters. We provide convergence rates for the estimators. As corollaries, we apply these to the settings of rankings and regression, where isometric embeddings are available. Finally, we give a bound the inconsistency due to embedding distortion in the non-isometric case.
Boolean Hypercube Case We introduce the following finite-sample estimation error bound. It demonstrates consistency for mean parameter estimation for a triplet of LFs when using Algorithm I To keep our pre- sentation simple, we assume: (i) the class balance P(Y y) are known, (ii) there two possible values
5

---

Published as a conference paper ICLR 2022
of Y. 91 and y2. (iii) we can correctly recover signs (see Ratner et (2019), (iv) we can find least three conditionally independent labeling functions that can form a triplet, (v) the embeddings are isometric.
Theorem 4.1. For any > O, for some 1/1 and y2 with known class probabilities p P(Y y1)) the quadratic triplet method recovers
= -(g(X>)) = 1|Y = y), 3, = P(g(X"); = 1| = y). = P(g(A);; = 1|Y = y) up to error O(( 0((11(20) 1d) 1//4 with probability at least - for any conditionally independent label functions da Ab, de and for all i [d].
2n
We state our result via terms like az P(g(>));(Y = v): these can be used to obtain E [X) and so recover È [dy(A", v)]-
Algorithm 2: CONTINUOUSTRIPLETS
Input: Estimates εu, ea Eb.c. prior p. index
Obtain variance Ey(Y), from prior p
To showcase the power of this result, we apply it to rankings from the symmetric group S, equipped with the Kendall tau distance d, (Kendall 1938). This estimation problem is more challenging than learning the conventional Mallows model (Mal-
(9(A))9(() + /ēabbl [aacc
E Y (é
Blg(X*) [V)] < e lév.cl
E [Y / Ra.el
gg < Raael
16
E 2 2 / Pa,b
return Accuracies ([o(A))9()) Elg(A (((l((())((())) (9()), Elo(A))(v))
lows, 1957)-and the standard Kemeny rule (Ke- meny 1959) used for rank aggregation will fail applied to Our result yields consistent estimation when coupled with the aggregation step (
We use the isometric embedding g into (+) For π E Sp. each entry ( corresponds to a pair (i.j) with < j. and this entry is 1 if in we have i < j and -1 otherwise. We can show for π, 7 E S, that E ((T))g((): = (2) 2d, (IT, 7), and so recover É Ig(A")) and thus É [d, (X*,y)]. Then,
Corollary 4.1.1. For any 5 > O. U > O, prior over and y2 with known class probability p. and using Algorithm [ and Algorithm 4 for any conditionally independent triplet Xa "e,6, X with parameters 0) with - 10)(01((1111 - e 05j2))
U > 0g 0, 0. > 4 (2). we can recover 0., Pr Og up to error O(gz (0 + ( W probability at least 1 - 6, where g2(U) = (-pe (aee-))// 1)(((11111
() u2) (-pe-
Note that the error goes is needed for generality. In the easier cases, where the quadratic approach is not needed (including the regression case), the rate is On 11/2). Next, note that the scaling in terms of the embedding dimension d ((lg((()))))) is efficient. The d2 function captures the cost of the backward mapping.
0(-11/4) This is outcome of using the quadratic system, which
Euclidean Space Rd Case The following is an estimation error bound for the continuous triplets method in regression, where we use the squared Euclidean distance. The result is for d but can be easily extended.
Theorem 4.2. Let R g(v)) be an estimate of the accurucies [g(\ (a(AA))g (ty)) using n samples, where all LFs are conditionally independent given Y. If the signs of recoverable, then with high probability
Elll ()())))())))) E (o(A") (o(i) [1a] = (( -10 [ * /max(ee eB emaz)) )
Here, O|min| min; E [9()))(()]] and Cmaz maxj, Cj
The error tends to zero with rate O(n 1/2) as expected.
Distortion & Inconsistency Bound Next, show how to control the inconsistency in parameter estima- tion as a function of the distortion. We write f to be the vector of the canonical parameters, the embedded distances), and μ. nz be the corresponding mean parameters. Let 1 e S dg(g(y), /ddd))/dyy( 8/) S for all y. v/ E y x y. Then, for constant Cmin (the value of which we characterize in the Appendix).
for their
distorted counterparts (obtained with consistent estimator
6

---

Published as a conference paper ICLR 2022
Theorem 4.3. The inconsistency in estimating 0 is bounded as 110 0'1 S Elluel//mmil emin.
5 EXPERIMENTS
We evaluated our universal approach with four sample applications, all new to WS: learning to rank, regres- sion, learning in hyperbolic space, and estimation in generic metric spaces given by random graphs.
Our hypothesis is that the universal approach is capable of learning a label model and producing high-quality pseudolabels with the following properties:
The quality of the pseudolabels is a function of the number and quality of the available sources, with more high-quality, independent sources yielding greater pseudolabel quality,
Despite pseudolabels being noisy, an end model trained on more pseudolabels can perform as well or better than a fully supervised model trained on fewer true labels,
The label model and inference procedure (3) improves the majority vote equivalent-but only when LFs are of varying quality; for LFs of similar quality, the two will have similar performance.
Additionally, we expect to improve on naive applications of existing approaches that do not take structure into account (such as using Snorkel (Ratner et al., 2018) by mapping permutations to integer classes). Application I: Rankings We applied our approach to obtain pseudorankings to train a downstream rank- ing model. We hypothesize that given enough signal, the produced pseudorankings can train a higher-quality model than using smaller proportion of true labels. We expect our method produces better performance than the Snorkel baseline where permutations are converted into multi-class classification. We also anticipate that our inference procedure
3 improves on the MV baseline 2 when LFs have differing accuracies.
Approach, Datasets, Labeling Functions, and End Model We used the isotropic simplification of Algo- rithm] I For inference, we applied (3). We compared against baseline fully-supervised models with only a proportion of the true labels (c.g.. 20%. 50%, ...). the Snorkel framework (Ratner et al., 2018) converting rankings into classes, and majority vote (2). We used real-world datasets compatible with multiple label types, including a movies dataset and the BoardGameGeeek dataset (2017) (BGG), along with synthetic data. For our movies dataset, combined IMDb, TMDb, Rotten Tomatoes, and MovieLens movie review data to obtain features and weak labels. In Movies dataset, rankings were generated by picking d = 5 film items and producing ranking based on their IMDb average rating. In BGG, we used the available rankings.
We created both real and simulated LFs. For simulated LFs, we sampled 1/3 of LFs from less noisy Mallows model, 2/3 of LFs from very noisy Mallows model. Details are in the Appendix HH] For real LFs, we built labeling functions using external KBs as WS sources based on alternative movie ratings along with popular- ity, revenue, and vote count-based LFs. For the end model, we used PTRanking Yuu) 2020 with ListMLE (Xia et al. 2008 loss. We report the Kendall tau distance (d-).
Results Figure2reports end model performance for the two datasets with varying numbers of simulated LFs. We observe that (i) as few as 12 LFs are sufficient to improve on a fully-supervised model trained on less data (as much as 20% of the dataset) and that (ii) as more LFs are added, and signal improves, performance also improves-as as expected. Crucially, the Snorkel baseline, where rankings are mapped into classes, cannot perform as well as the universal approach; it is not meant to be effective general label settings. Table 2 shows the results when using real LFs, some good, some bad, constructed from alternative ratings and simple heuristics. Alternative ratings are quite accurate: MV and our method perform similarly. However, when poorer-quality LFs are added, MV rule tends to degrade more than our proposed model,
anticipated. Application H: Regression We used universal WS in the regression setting. We expect that with more LFs, we can obtain increasingly high-quality pseudolabels, eventually matching fully-supervised baselines.
Approach, Datasets, Labeling Functions, End Model, Results We used Algorithm I which uses the continuous triplets approach[] For inference, we used the Gaussians simplificatin.. As before, compared
7

---

Published as a conference paper ICLR 2022
0.35
0.40
WS (Snorkel)
pestimation
Eestimation error
129
estimation
Boarr no Approach
0.35
(Majonity Votel
(0uns)
$5..30
50.30
Fuly supervised (20%)
Fully s.pervised (50%)
pamen
5 0.22
Fully supervised (100%)
0.25
0.20
12 15 Num LFs
Semplaa
Samplka
Sumples
(a) Movies dataset
(b) BGG dataset
(a) Parameter Estimation Error
End model performance with ranking LFs (Leftt: Movies, Right: BGG). Training a model on pseu- dolabels is compared to fully-supervised baselines on vary- ing proportions of the dataset along with the Snorkel base- line. Metric is the Kendall tau distance; lower is better.
Figure 2:
Figure 3: Regression: parameter estimation error (left two plots) and label estimation error comparing to majority vote baseline (rightmost) with increasing number of samples.
Setting
dr
MSE
Setting
d-
MSE
Fully supervised (10%)
0.2731
0.3357
WS (One LF, Rotten tomatoes)
0,2495
0.4272
Fully supervised (25%)
0.2465
0.2705
WS (One LF, IMDb score)
0,2289
0.2990
Fully supervised (50%)
0,2313
0.2399
WS (One LF,, MovieLens score)
0.2358
0,2690
Fully supervised (100%)
0,2282
0,2106
WS (3 LFs. MV (
0.2273
0,2754
WS scores bad LFs, MV (2)
0,2504
WS LFs, Ours)
0.2274
0.2451
WS (3 good + had LFs, Ours) 0,2437
Table 2:
End model performance with real- world rankings and regression LFs on movies. WS (3 scores, shows the result of our algorithm combining 3 LFs. In ranking. high-quality LFss perform well (and better than fewer clean labels), but mixing in lower-quality LFss hurts majority vote (2) more than our proposed approach. In regression, our method yields performance similar to fully-supervised with 50% data, while outperforming MV.
against baseline fully-supervised models with a fraction of the true labels (e.g., 20% 50%, ...) and MV We used the Movies rating datasets with the label being the average rating of TMDb review scores across users and the BGG dataset with the label being the average rating of board games. We split data into 75% for training set, and 25% for the test set. For real-world LFs, we used other movie ratings in the movies dataset. Details are in the Appendix H for our synthetic LF generation procedure.Fo For the end model, we used gradient boosting (Friedman, 2001). The performance metric MSE.
Figure 9 (Appendix) shows the end model performance with WS compared to fully supervised on the movie reviews and board game reviews datasets. We also show parameter estimation error in Figure As expected, parameter estimation error goes down in the amount of available data. Similarly, consistent, while majority vote is not. Table reports the result of using real LFs for movies. Here, MV shows even worse performance than the best individual LF Movie Lens Score. On the other side, label model lower MSE than the best individual LF, giving similar performance with fully supervised learning with 50% training data.
label estimator is
Application III: Geodesic Regression Hyperbolic Space Next, we evaluate our approach on the prob- lem of geodesic regression on Riemannian manifold M, specifically, a hyperbolic space with curvature K 50. The goal of this task is analogous to Euclidean lincar regression, except the dependent variable lies on geodesic in hyperholic space. Further background is in the Appendix H
Approach, Datasets, LFs, Results We generate y by taking points along a geodesic (a generalization of a line) parametrized by tangent vector 3 starting p, further affecting them by noise. The objective of the end-model is to recover parameters and 83, which is done using Riemannian gradient descent (RGD) to minimize the least-squares objective: p. 3 = arg ming Σn=, ((exp,(2x,0) 3;:)),)) where d(---) is the hyperbolic distance. To generate each LF Ay. we use noisier estimates of yf where the distribution A (0,03, and o3 ~ (41.64((142)4464411111 2j Bernoull(0.55 to simulate heterogeneity across LFs;
8

---

Published as a conference paper ICLR 2022
Fully supervised (80%)
Accuracy
1.0
Accuracy
1.0
Fully supervised (90%)
1.00
Fully supervised (100%)
0.5
0.5
WS (Ours)
Majority Vate
MajarRy Vate
0.99
Ws (Majority Vote)
10
20
4
2
Theta average
Theta average
(a) Heterogeneous LFs
(b) Homogenous LFs
Figure 4: Comparison between our approach, 2 and suply-supervised in geodesic regression. Metric is least- cast-equares objective; lower is better.
Figure 5: Comparison between our label model and ma- jority voting in generic metric space.
Metric is accuracy;
higher better.
the noise vectors are parallel transported to the appropriate space. For label model learning, we used the isotropic Gaussian simplification. Finally, inference used RGD to compute (3). We include MV (2) as a baseline. We compare fully supervised end models each with n E {80, 90, 1 labeled examples to weak supervision using only weak labels. In Figure we see that the Fréchet mean baseline and our approach both outperform fully supervised geodesic regression despite the total lack of labeled examples. Intuitively, this is because with multiple noisier labels, we can produce better pscudolabel than single (but less noisy) label. As expected, our approach yields consistently lower test loss than the Fréchet mean baseline.
Application IV: Generic Metrie Spaces We also evaluated our approach generic metric space generated by selecting random graphs G with fixed number of nodes and edges. The metric is the shortest-hop distance between a pair of nodes. We sampled nodes uniformly and obtain LF val- ues with (T). Despite the lack of structure, we still an- ticipate that our approach will succeed in recovering the latent nodes when LFs have sufficiently high quality. We expect that the LM improves on MV 2 when LFs have heterogeneous quality, while the two will have similar performance on homogeneous quality LFs.
structureless problem-
Datase/UUAS
y
X
A²
cs.pdr-ud
0.873
0.861
0.758
0.842
en ewte
0.795
0.792
0.733
0.792
en.lines-ud
0.850
0.833
0.847
0.825
on-partul-ud
0.866
0.869
0.866
0.817
Table 3: UAS scores for semantic dependency pars-
ing. Y is synthesized from off-the-shelf parsing LFs.
Approach, Datasets, LFs, Results We generated random graphs and computed the distance matrix yield- ing the metric. We used Algorithm 4 with isotropic Gaussian embedding and continuous triplets. For label model inference, we used (3). Figure 5 shows results on our generic metric space experiment. As ex- pected, when LFs have a heterogencous quality, LM yield better accuracy than MV. However, when labeling functions are of similar quality, LM and MV give similar accuracies.
Application V: Semantic Dependency Parsing We ran our technique on semantic dependency parsing tasks, using datasets English and Czech from the Universal Dependencies collection (Nivre al., 2020). The LFs are off-the-shelf parsers from Stanza (Qi et al. 2020) trained on different datasets in the same language. We model space of trees with metric given by the lz norm on the difference between the adjacency matrices. We measure the quality of the synthesized tree Y with the unlabeled attachment scores (UAS). Our results are shown in Table 3 As expected, when the parsers are of different quality, we can obtain a better result.
6 CONCLUSION
Weak supervision approaches allow users to overcome the manual labeling bottleneck for dataset construc- tion. While successful, such methods do not apply to each potential label type. We proposed an approach universally apply WS, demonstrating it for three applications new to WS: rankings, regression, and learning hyperbolic space. We hope our proposed technique encourages applying WS many more applications.
9

---

Published as a conference paper ICLR 2022
ACKNOWLEDGMENTS
We are grateful for the support of the NSF under CCF2106707 (Program Synthesis for Weak Supervision) and the Wisconsin Alumni Research Foundation (WARF).
REFERENCES
Imdb movie dataset.
ASSR-WEBB 10K.
Tmdb 5k movie dataset version 2.
BoardGameGeek Reviews Version 2.
httpet//www.aaggle..cm/////aaaat
boa Sbgardaagggeek--eeee reviews 2017.
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decom- positions for learning latent variable models. Journal of Machine Learning Research, 15:2773-2832,
2014.
Stephen H Bach, Daniel Rodriguez, Yintao Liu, Chong Luo, Haidong Shao, Cassandra Xia, Souvik Sen, Alex Ratner, Braden Hancock, Houman Alborzi, al. Snorkel drybell: A case study in deploying weak supervision at industrial scale. In Proceedings of the 2019 International Conference on Management of Data, pp. 362-375, 2019.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proc. of the eleventh annual conference on Computational learning theory, pp. 92-100. ACM, 1998.
J. Bourgain, On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 5221-2) 1985.
Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, and Manolis Zampetakis. Optimal learning of mal- lows block model. In Alina Beygelzimer and Daniel Hsu (eds.), Conference on Learning Theory, COLT 2019, 2019.
Ioannis Caragiannis, Ariel D. Procaccia, and Nisarg Shah. When do noisy votes reveal the truth? ACM Trans. Econ. Comput., 4(3), March 2016. ISSN 2167-8375. doi: 10.1145/2892555. URL https:
//doi. 00044//229555
Arun Tejasvi Chaganty and Percy Liang. Estimating latent-variable graphical models using moments and likelihoods. In International Conference on Machine Learning, pp. 1872-1880, 2014.
Mayee F. Chen, Benjamin Cohen-Wang Stephen Mussmann, Frederic Sala, and Christopher Ré. Comparing the value of labeled and unlabeled data in method-of- oftthod-of--ommnts latent variable estimation. International Conference Artificial Intelligence and Statistics (AISTATS), 2021.
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, and Silvio Lattanzi. On reconstructing hidden permu- tation. In 17th Int') l Workshop on Approximation Algorithums for Combinatorial Optimization Problems (APPROX' 14), 2014.
Andrew Davenport and Jayant Kalagnanam. A computational study of the kemeny rule for preference aggregation. In Proceedings of the 19th national conference on Artifical intelligence (AAAI 04), 2004.
Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation observer emror-rates using the em algorithm. Applied statistics, pp. 20-28, 1979.
10

---

Published as conference paper ICLR 2022
Mostafa Dehghani, Hamed Zamani, Aliaksei Severyn, Jaap Kamps, and W. Bruce Croft. Neural ranking models with weak supervision. In Proceedings of the 40th International ACM SIGIR Conferenceon Re- search and Development Information Retrieval, 2017.
M.A. Fligner and J.S. Verducci. Distance based ranking models. J.R. Statist. Soc. B, 48(3), 1986.
URL httpp:://wwwz jstor- ezproxyy......... www.ay.ibbary..... www.wwssce www.. htt.://w....aa...........///aaa.
#mmetadata info tab taattttabtt___teee contents
Jerome Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp-
1189-1232, 2001.
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 the 37th International Conference on Machine Learning (ICML 2020), 2020.
Sonal Gupta and Christopher D Manning. Improved pattern learning for bootstrapped entity extraction. In Proceedings of the Eighteenth Conference on Computational Natural Language Learning, pp. 98-108, 2014.
Sarah Hooper, Michael Wornow, Ying Hang Seah, Peter Kellman, Hui Xue, Frederic Sala, Curtis Langlotz, and Christopher Ré. Cut out the annotator, keep the cutout: better segmentation with weak supervision. In Proceedings of the International Conference on Learning Representations (ICLR 2021), 2021.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 446-456. PMLR, 2015.
Manas Joglekar, Hector Garcia-Molina, and Aditya Parameswaran. Evaluating the crowd with confidence. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 686-694, 2013.
Manas Joglekar, Hector Garcia-Molina, and Aditya Parameswaran. Comprehensive and reliable crowd assessment algorithms. In Data Engineering (ICDE), 2015 IEEE 31st International Conference on, pp- 195-206 IEEE, 2015.
David R Karger. Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing systems. In Advances in neural information processing systems, pp. 1953-1961, 2011.
J. Kemeny. Mathematics without numbers. Daedalus, 88(4))577-591, 1959.
Maurice Kendall. A new measure of rank correlation. Biometrika, pp- 81-89, 1938.
Claire Kenyon-Mattn Mathieu and Warren Schudy. How rank with few errors. In Proceedings of the thirty-ninth anmual ACM symposium on Theory of computing (STOC '07), 2007.
C. L. Mallows, Non-Null Ranking Models. I. Biometrika, 44, 1957. doi: 10.109//biomec444.2211144 URL 2.114
ht httppe///ool.oorg//..00/////ooo
J. Marden. Analyzing and modeling rank data. Chapman and Hall/CRC, 2014.
Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. Distant supervision for relation extraction without labeled data. 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: Volume 2-Volume pp- 1003-1011. Association for Computational Linguistics, 2009.
Sumit Mukherjee. Estimation exponential families on permutations. The Annals of Statistics, 44(2): 853-875 2016.
11

---

Published as a conference paper ICLR 2022
Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Jan Hajič, Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman. Universal Dependencies v2: An ever- growing multilingual treebank collection. In Proceedings of the 12th Language Resources and Evalu- ation Conference, pp. 4034 4043, Marseille, France, May 2020. URL org/2020 Trec- 1.497
R. L. Plackett. The analysis of permutations. J. Applied Statistics, 24:193-202, 1975.
Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. Stanza: A Python natural language processing toolkit for many human languages. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, 2020. URL https://nlp
stanford. www.eeu.uuaaaa wwwpe/ppppp...eeeeeeeee wttps//g222sssazzaaaa pdf
Aditi Raghunathan, Roy Frostig, John Duchi, and Percy Liang. Estimation from indirect supervision with linear moments. In International conference on machine learning, pp. 2568 25777, 2016.
A. J. Ratner, Christopher M. De Sa, Sen Wu, Daniel Selsam, and C. Ré. Data programming: Creating large training sets, quickly. In Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, 2016.
A. Ratner, B. Hancock, J. Dunnmon, Sala, S. Pandey, and C. Ré. Training complex models with multi-task weak supervision. In Proceedings of the AAAI Conference on Artificial Intelligence, Honolulu, Hawaii, 2019.
Alexander Ratner, Stephen Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the 44th International Conference on Very Large Data Bases (VLDB), Rio de Janeiro, Brazil, 2018.
Christopher Ré, Feng Niu, Pallavi Gudipati, and Charles Srisuwananukorn. Overton: A data system for monitoring and improving machine-learned products. In Proceedings of the 10th Annual Conference on Innovative Data Systems Research, 2020.
Esteban Safranchik, Shiying Luo, and Stephen Bach. Weakly supervised sequence tagging from noisy rules. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 5570-550 5578, Apr. 2020.
Frederic Sala, Paroma Varma, Jason Frics, Daniel Y. Fu, Shiori Sagawa, Saelig Khattar, Ashwini Ramamoor- thy, Ke Xiao, Kayvon Fatahalian, James Priest, and Christopher Ré. Multi-resolution weak supervision for sequential data. In Advances in Neural Information Processing Systems 32, pp. 192-203, 2019.
Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. 2014.
P. Varma, F. Sala, A. He, A. J. Ratner, and C. Ré. Learning dependency structures for weak supervision models. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), 2019.
Martin Wainwright and Michael I Jordan. Graphical models, exponential families, and variational infer- ence. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008
Fen Xia, Tie Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach learning to rank: theory and algorithm. In Proceedings of the 25th international conference on Machine learning, pp- 1192-1199, 2008
Hai-Tao Yu. Pt-ranking: A benchmarking platform for neural learning-to-rank, arXiv preprint arXiv:2008. 13368, 2020.
12

---

Published as conference paper ICLR 2022
The appendix contains additional details, proofs, and experimental results. The glossary contains conve- nient reminder of our terminology (Appendix Aj. We provide detailed related work section, explaining the context for our work (Appendix B). Next, we give the statement of the quadratic triplets algorithm (Ap- pendix [. Afterwards, we give additional theoretical details: more details on the backward mapping, along with an extended discussion on the rankings problem. We continue with proofs of Theorem 4.1.1 and and Theo- rem 4.2 (Appendix D. Finally, we give more details on the experimental setup (Appendix H and additional experimental results including partial rankings (Appendix) ! J
A GLOSSARY
The glossary is given in Table 4 below.
Symbol
Definition
X
feature space
y
label metric space
dy
label metric
T1, D2
nn
unlabeled datapoints from X'
21 32 ................................ In
latent (unobserved) labels from y
8
8
labeling functions / sources output of labeling functions
\3 22
n
number of data points
number of LFs output of ath labeling function applied to ith sample 2; canonical parameters in model 1
(i)
O2. 0a.
(Xaa (0),)) (
mean parameters in (I)
injective mapping g : + Rd or (=1]d
9
P
number of items in ranking setting ol
Ca.b
Ou
P(g(A)) = 1, g(*())); 1)
la
P(g(A));
S,
symmetric group on {1...,p} p}
permutation E Sp Table 4: Glossary of variables and symbols used in this paper.
(..))
Kendall tau distance on permutations (Kendall 1938)
RELATED WORK
Existing weak supervision frameworks, starting with Ratner et al. (0066), select a particular model for the joint distribution among the sources and the latent true label, and then use the properties of the distribution to select an algorithm to learn the parameters. In Ratner al. (2016), factor model is used and a Gibbs-sampling based optimizer the algorithm of choice. Ratner al. (2018), the Ising model. The algorithm used to
Weak Supervision
model is discrete Markov random field (MRF), and in particular, learn the parameters solves a linear system obtained from a component of the inverse covariance matrix. In the inverse covariance matrix is removed, and
Sala et al. (2019) and Fu et al. (2020), the requirement a set of systems among as few as three sources are used instead. These systems have closed-form solutions. All of these models could be represented within framework. The quadratic triplets idea is described, but
13

---

Published as a conference paper ICLR 2022
not analyzed, in the appendix of Fu al. (2020), applied to just the particular case of Ising models with singleton potentials. Our work uses these ideas and their extensions to the general setting, and provides theoretical analyses for the two sample applications we are interested in.
All of these papers refer to weak supervision frameworks; all of them permit the use of various types of information as labeling functions. For example, labeling functions might include crowdworkers Karger et al. (201T). distant supervision Mintz et al. (2009), co-training Blum & Mitchell (1998), and many others. Note that works like Dehghani al. (2017) provide one type of weak supervision signal for rankings and can be used as a high-quality labeling function in our framework for the rankings case. That is, our work can integrate such sources, but does not directly compete with them.
The idea of learning notions like source accuracy and correlations, despite the presence of the latent label, is central to weak supervision. It has been shown up in other problems as well, such as crowdsourcing Dawid & Skene (1979): Karger et al. (2011) topic modeling Anandkumar al. (2014). Early approaches pectation maximization (HM), but in the last decade, a number of exciting approaches have been introduced based on the method of moments. These include the tensor power method approach of Anandkumar al. (2014) and its follow-on work, the explicitly crowdsourcing setting of Joglekar et al. (2013) 2015). and the graphical model learning procedures of Chahgantyy & Liang (2014); Raghunathan et al. (016)) Our approach can be thought of as an extension of some of these approaches to the more general setting we consider.
Comparison With Existing Label Models There are several existing label models; these closely resemble (1) under particular specializations. For example, one of the models used for binary labels in Ratner et al. 2019); Varma et al. (2019) is the Ising model for X2 , E
y
{+1}
p(
AT v)
exp
D +
Σ (a,))EE
Oa + +yy).
A difference is that this is joint model; it assumes y is part of the model and adds singletoon potential prior term to it. Note that this model promotes agreement X rather than penalizes disagreement -X" v), but this nearly equivalent.
Rankings and Permutations One of our chief applications is to rankings. There are several classes of distributions over permutations, including the Mallows model (Mallows 1957) and the Plackett-Luce model (Placketi 1975). We are particularly concerned with the Mallows model in this work, as it can be extended naturally to include labeling functions and the latent true label. Other generalizations include the gener- alized Mallows model [Marden] 2014) and the Mallows block model (Busa-Fekett et al. 2019). These generalizations, however, do not cover the heterogenous accuracy setting we are interested in.
A common goal is to learn the parameters of the model (the single parameter 0 in the conventional Mallows model) and then to learn the central permutation that the samples are drawn from. A number of works in this direction include Caragiannis et al. (2016); Mukherjee (2016); Busa- Fekete al. (2019). Our work extends results of this flavor to the generalization on the Mallows case that we consider. In order to learn the center permutation, estimators like the Kemeny rule (the procedure we generalize in this work) are used. Studies of the Kemeny rule include Kenyon--aatahi Mathieu & Schudy (2007): Caragiannis et al. (2016).
C EXTENSION TO MIXED LABEL TYPES
In the body of the paper, we discussed models for tasks where only one label type is considered. As a simple extension,
operate with multiple label types. For example, this might include classification task where weak label sources give their output as class labels and also might provide confidence values; that is, a pair of label types that include discrete value and continuous value. The main idea is to construct finite
14

---

Published as conference paper ICLR 2022
product space with individual label types. Suppose there k possible label types, i.c. ,/.32, .v. We construct the label space by the Cartesian product
y = 3/ x 3/2 x ... x Vk-
All that is left is to define the distance:
(y 122
Σ dz (proj, (yi), proj,
where proj, is projection onto the i-th factor space. Then, using this combination, we extend the exponential family model II. yielding
P(A
exp
(60 dy: (proj,(A"),
proj. (v))
a=
==1
Σ
0 dy: (Aroj, proj, ()))..
( ==1
We can learn the parameters 0 procedure (3) can be extended to
(0) a. by Algorithm
using the same approach. Similarly, the inference
Úū arg min 2EY
dag
(z))
There are two additional aspects worth mentioning. First, the user may wish to consider the scale of distances in each label space, since the scale of one of the factor spaces' distance might be dominant. To weight each label space properly, we can normalize each label space's 's distance. Second, we may wish to consider the abstention symbol as an additional element each space. This permits LFs to output one or another type of label without necessarily emitting a full vector. This can also be handled; the underlying algorithm is simply modified to permit abstains as in Fu et al. 2020).
D UNIVERSAL LABEL MODEL FOR ISOTROPIC GAUSSIAN EMBEDDING
We illustrate the isotropic Gaussian version the label model. While simple, it captures all the challenges involved in label model learning, and it performs well in practice. The steps shown in Algorithm 3
Why does Algorithm 3 obtain the estimates of # without observing the true label y? To see this, first, note that post-embedding, the model
working with is given by
P(1 \") exp
-allo(A9)) - 9(v)1++ + Σ -0asllo(29) - (1)
#=1
(a.))E
the embedding is a bijection, the resulting model indeed is multivariate Gaussian. Note that the term "isotropic" here refers to the fact that for d > 1, the covariance term for the random vector Aa is multiple of I.
Now, observe that if (a,b) of E. have that E [||I- - {|a1 E [I[(>> - -(x- -
E [[|X> + y/|?]. Note that can estimate the left-hand side E [[| [d1[2] from samples,
15

---

Published as conference paper ICLR 2022
Algorithm 3: Isotropic Gaussian Label Model Learning
1: Input: Output of labeling functions X (i), correlation set E
2: for E (1.2...., do
3: for E (1, m., \ do
4: Estimate Correlations:yl... [d(> 10)] Et= d())
5: end for
6: Estimate Accuracy: Pick b, (a, E, (a, E, (b.
È. [d((". .v) + 1/2(B [d(A", >²)] E [d(A", X9] [=])
7: Form estimated covariance matrix Σ from accuracies and correlations; Compute è <- Đ-1
8: end for
9: return 0,, 0,b
while the right-hand side contains two of our accuracy terms. We can then form two more equations of this type (involving the pairs a, c and b, c) and solve the resulting linear system. Concretely, we have that
E [1lx(A*) )[* E [Ilx(>*)
=1 E [llg(A*) y||²]
E [11)(>*) [( = E [1lg(A*) =11 E [llg(A*) -31l
[1lg(A*) -(19113] = [lla(A*) = [llg(A>) - -
To obtain the estimate of E [Il=(X*) =l we add the first two equations, subtract the third, and divide by two. Two.This produces the accuracy estimation step in Algorithm 3 To obtain the estimate of the canonical parameters 0, it is sufficient to invert our estimate of the covariance matrix. In practice, note that we need not actually compute an embedding: we can directly work with the original metric space distances by implicitly assuming that there exists isometric embedding.
ADDITIONAL ALGORRITMMIC DETAILS
Quadratic Triplets We give the full statement of Algorithm which the accuracy estimation algorithms for the case Im(g) (+1)4
Inference simplification in R For the simplification of inference in the isotropic Gaussian embedding, we do not even need to recover the canonical parameters; in the label model learning step. For example, if d 1, we can write these accuracy mean parameters as É [9(X+)g()) and put them into a vector É ky The correlations can be placed into the sample covariance matrix (x ((x") Then,
enough use the mean parameters estimated
i = E ()) "0,
(5)
This is simply the mean of a conditional (scalar) Gaussian.
F ADDITIONAL THEORY DETAILS
We discuss further details for several theoretical notions. The first provides more details how to obtain the canonical accuracy parameters 0g from the mean parameters E [d~(>", y)] in the rankings case. The second involves discussion of learning rank problems, with additional details the weighted estimator 33)
16

---

Published as a conference paper ICLR 2022
Algorithm 4: QUADRATICTRIPLETS
Input: Estimates Ou,b, Oa,e, Ob,e: lay lo, le prior p. index
for y in 3/ do
Obtain probability p/ = P(Y =y) from prior
Set (0n,s(1 -p') (La -p2)6s)/(pz :::==ppptt -p'la)
Set + (0o,e(1 p)) + (Ea -p2)lo)/(p' -p'a)
Solve quadratic (pβy + le -p36 - -my - pl)(---))('aappp =
P(g(A")/ u) 4
P( y) (0n,s(1 - -p') (Le -P((o(>)/( 1))6)/(()P(()))) = -p) P(g(A>/ = y) - (0a,c(1 - -²) - (la -pP((((())))) = ()) -p'aa end for return Accuracies
= -)) P(oNN))) = y). P(g(x))))))
More on the backward mapping for rankings We note, first, that the backward mapping is quite simple for the Gaussian cases in R. it just involves inverting the mean parameters. As intuitive example, the interior of the multivariate Gaussian density is E-1, the inverse covariance matrix. The more challenging aspect is deal with the discrete setting, and, in particular, its application to rankings. We do so below.
note that the canonical parameter
We describe how recover the canonical accuracy parameter 9₂ for label function A given accuracy estimates P()()); = 1|Y = y) for all E y. By equation (1), the marginal distribution of X is specified by
p(*)) exp( - (Sp(==()")00es())) (ng()))
(6)
Since this is an exponential model, it follows from Fligner & Verducci 1986) that
E[D] (t))((M())
di
where = E, (g(A"); # {(y);} and (t) is the moment generating function of D under (5). E[D] can be easily estimated from the accuracy parameters obtained from the triplet algorithm, and the inverse of (6) can then be solved for. For instance, in the rankings case, it can be shown (Fligner & Verducci, 1986) that
Z(0). Additionally, we have that the partition function satisfies (Chierichetti al. 2014
M 0) p!
Oj
Z(6)
e
jšk
It follows that
0j
M(I)
Ke!
JŠK
Using this, we can then solve for (6) numerically.
Rank aggregation and the weighted Kemeny estimator Next, we provide some additional details on the learning to rank problem. The model (1) without correlations can be written
p(1
X
[v)
exp Σ Oad-(2
17

---

Published as a conference paper ICLR 2022
Thus, if we only have one labeling function, we obtain the Mallows model (Mallows) 1957) for permutations, whose standard form is p(X"lv) Mallows model and its relatives. The permutation y (called the center) fixed and n samples of X are drawn from the model. The goal is to (1) estimate the parameter 0 and (2) estimate the center y. This neatly mirrors our setting, where (1) is label model learning and (2) is the inference procedure.
1/Z cxp(-81d-AA', y)). Permutation learning problems often use the
However, our problem is harder in two ways. While we do have n. samples from each marginal model with parameter 0, these are for different centers V1, .......... Un so we cannot aggregate them or directly estimate 0, That is, for LF a, get to observe X (1), (2), ..,,,.... (n)). However, these all come from different conditional models P(- P(-B))) with a different yi for each draw. the uninteresting case where the y 's are identical, we obtain the standard setting. On the other hand, we do get observe m views (from the LFs) of the same permutation Yi- But, unlike in standard rank aggregation, these do not come from the same model-the 0, accuracy parameters differ in (2). However, if 0₂, identical (same accuracy) for all LFs, we get back to the standard case. Thus we can recover the standard permutation learning problem in the special cases of identical labels or identical accuracies but such assumptions are unlikely to hold in practice.
Note that our inference procedure (3) is the weighted version of the standard Kemeny procedure used for rank aggregation. Observe that this is the maximum likelihood estimator on the model ( specialized to permutations. This is nearly immediate: maximizing the linear combination (where the parameters are weights) produces the smallest negative term on the inside of the exponent above.
Next, we note that it is possible to show that the sample complexity of learning the permutation using this estimator is still ((log(m/=)) by using the pairwise majority result in Caragiannis al. (2016).
Finally, a brief comment on computational complexity: it is known that finding the minimizer of the Kemeny rule (or our weighted variant) is NP-hard (Davenport Kalagnanam [004). However, there are PTAS available for it (Kenyon-Mathien & Schudy| (007)) In practice, our permutations are likely to be reasonably short (for example, in our experiments, we typically use length 5) so that we can directly perform the minimization. In cases with longer permutations, we can rely the PTAS.
G PROOF OF THEOREMS
Next we give the proofs of the proposition and our two theorems, restated for convenience.
G.1 DISTORTION BOUND
Our result that captures the impact of distortion on parameter error is Theorem 4.3. The inconsistency in estimating 0 is bounded as |10 (0-00 0' elluil/emin-
Before we begin the proof, we restate, in greater detail, some of our notation. We write po,ay for the true model
Po:dy (A....,, X (y)
Z exp Σ
1
m
0ady(A
Σ
-1,sd)(11,29))
(a.))E
and p for models that rely on distances in the embedding space
po.d, ( Ay = 2 exp
Σ -0 (a.))E
We also write 0 to be the vector of the canonical parameters 02 and Pu,b in po:dy and 0' to be its counter- part for por, Let μs be the vector of mean parameters whose terms are E[dy(X", v)] and E)dy {*)]
18

---

Published as conference paper ICLR 2022
Similarly, we write p' for the version given by psr,d, Let θ be subspace so that 0,0' O. Since our exponential family is minimal, we have that the log partition function A()) has the property that v² (²)(() the covariance matrix and is positive definite. Suppose that the smallest eigenvalue of V ((0 for 0 E θ is Cmi--
For our embedding, suppose we first normalize (ie, divide by constant) our embedding function so that
dg(g(v). g(v'))
dy
for all y. y. y x V. other words, our embedding function y never expands the distances in the original metric space, but, of course, it may compress them. The distortion measures how bad the compression can be, Let be the smallest value so that
1-E5 dg(g(v).9())) <
dy(
for all v.y' E ) x y. If is isometric, then we obtain = 0. On the other hand, as e approaches 1, the amount of compression can be arbitrarily bad.
Proof. We use Lemma 8 from Fu et al. (2020). It states that
110
0'1
||
w'll
Emin
E
|||/|.
Emin
To the latter, note that || n'll <
[]x(1 / < || - (1 -)) |lalle, where
a is the p
element-wise ratios, and where we applied our distortion bound.
G.2 BINARY HYPERCUBE CASE
Theorem 4.1. For any 8 > O, for some y11 and y2 with known class probabilities = P(Y = v1), the
quadratic triplet method recovers as = P(g(\>); = -|-Y = y), B, = P(g(>*); = 1|Y = y)
P(g(X); = 1 = y) up error O(( 1((1m(2df/) /5) 11/44) with probability least for any conditionally independent label functions da Ao, de and for all i E [d].
Proof. Define
P(g(>)); 1 = v) P(g(>)), 1/Y + F p(a(A)) - = -) P(g()); -1-y /0). P= P(Y -(Y=w)
0 P(Y + +v)
0
and
1 - 1, =)
P(g(\*); 1, 1,9(1)) =-1)
0 = P(o(2), = - -1,9(1), 1) P(g(>), = - 1,9(1),) = --11)
By conditional independence, we have that
1 "(P(( O.a
(10)
Note that express
P(g(>); = 1/2 # 3) P(g(X*); =1 P(g())) = 11=11110000
= PYY = v)
P(Y # v)
P(Y #
19

---

Published as conference paper ICLR 2022
We can therefore rewrite the top row of jet [ai; -ra,] where of estimating the entries of O,'s 's and qi s. we consider the top-left entry (10 get the following system of equations
P(al)*)
and P(Y=v) P(V*y) After
P(Y pv)
for every pair of a, b and c, to
mmb
to: + 9. - rr -arra;
p
0.c
1047 + 06 -6r Gro: 1-p p
t3,1% + do a.r Tr..
1-P p
where 8t and are the top-left entries of n and n4. respectively, p= P(Y = y). and (1-p)
For ease of notation, write of as qu and so on. Rearranging the first and third equations gives expres- sions for a and y in terms of B.
Quk I-p
+ 1.r 9a96
t 9ut
One + f 9o
18 Qar
Substituting these expressions into the second equation of the system gives
BB + Oue
3 +
One
1-p Qogc Goge dar
g.r3 One
1-p gode
ParB +
I-p Qaa9
Ô.c
1-p
1 qor Gor
t3
9ur
t d5r
t qo0
p
We can multiply the equation by (t.3 )² to get
Oah
Onc
t(gurB
1-p da (q.r +
qo)ce) + 4oGo((tB (gr)2)
-
Ôbc
Oab
( +
(ode) (1.3 - (ur) g.r( + 1-p (a(i)) (1.3 - pur)
Ôac,
(tB - 9
p
Oab
Onc
909c) MarB + (1- (aab)( Onc
Om:
(aaior + ( 2oro) +
1
1-p -Gb0c)
1-p
+qago 32 2q + =8312)
Öbc
Ôbc
- gort8² +
(o4c)tB 9. 96rl
1-p p
Ôeb
Oab
- gart,3 +
9 3- - q0rl
9.96)
Ô
12 - 2gr -
p
20

---

Published as conference paper ICLR 2022
Ôac (2
32 dadcl Qadcr²
Óab
Obe
+B t
2a4 +
(1-p (olr) 24 Aequt
1-p
-ar (
(1 (10mg
Öbe
Oab
Oac
Qn - (od)ar)
der
(a9t)) (nler²
(2grrl
-pp
Oab
Obe
+
[ 11
(n
(04e) + 209.0162
p
One (odc) + 9 1-p
Oab
Oac
+qa
1 Qa(b)
46 = 0.
1-p
The only sources of error from estimating c's and O's. Let ee denote the error for the c's. Let so denote the eπrоr from O's. Applying the quadratic formula we obtain 3 (- + V 4a'c') ( (2(a)) where the coefficients are
Ônc t²
d' = - Gag.r2t
1-p
6' = (Dub.
(((((Gn)) 2.40)0e + (T- (vde)aa)) 2corl
Oub
Ovc
dar (1-0p gtgc)t qu9c(?)
Obc
qar ( Oab
(1-m), -aau))t Gagbr²
Onc. p
(2(ort)
Óab
Ôbc (vde) + "oleolir
Ónc + $nq00"
= [(
(n(h)) (
1- (1- Gudc))
1-
Ôab
Ôac
+
Qa46) 1-p
92.2
Let Ear, Ev denote the error for each coefficient. That is, Ewr = (a') where (a')* is the population- level coefficient, and similarly for b/ V.C' d. Let & and EO indicate the estimation error for the e and terms. Then
12
E.' =
Pps + 1-p- -0)
rt
EV 0
(Ec + E0)
1-p
Eer = (0=00((1))) >
2
12
p2
1-p
+ +
Ec +
(1-
-
E0
Because and are functions of p, we ignore the dependence on p. we get that
Ea' Ey = O(E.
Furthermore,
E(r)2 Olex) O tc)-
21

---

Published as a conference paper ICLR 2022
It follows that
cB = O(Ved +
Next, note that O and e are both the averages of indicator variables, where the c₁'s involve P(g(X)); and the Opdd' upper-left corners compute ())()); = 1, g(')) = 1). Thu
apply Hoeffding's s inequality
and combine this with the union bound to bound the above terms. We have with probability at least 1 5
(2g()) and similarly with probability at least 1 2n
2, EO, S v
(log(e//0) for all E [d]. It follows 2n
Ec,
that with probability at least 1 - 8, Ea ES E, O(( (2g(2)/)) 11/4).
We can now prove the main theorem in the rankings case.
Corollary 4.1.1, For any 5 0. U > O, prior over y1 and y2 with known class probability p. and U
using Algorithm [ and Algorithm 4 for any conditionally independent triplet X" , A. with parameters
> 0n. 0, 02 > 4 (2), we can recover 0.. 0b, Og up to error O(g2 ( + (log(2p" (26n)) 1/4) 0) with
probability least 8, where g2(U) = (-pe (1(()1((1))))))) ((((1---)))) E5 45)(((1 e0)s).
Proof. Consider a pair of items (a, b). Without loss of generality, suppose a inn and a > b. Define Oa,b P(a <x- bly1), d',b P(a > bly2) then our estimate for P(M(a.M) ((a)))) where Ma..s) Y(,,)) denotes the event that label function ranks (a, b) correctly would be
P(M(aN)) Y(ab)) = puoa + (1 (1-p)(1- á'a.b)
a'
which has error O(ex). Then, note that E[d(x" Y)) Ea,b P(M(,))) Y(,b))) Therefore, we can compute the estimate E[d(X", Y)] Ea,b B[A, M). which has error ((())
2n )114))
Recall from we have that
Eg D] ([log(M(())
dt where (1) is the moment generating function, and recall from
8 that
oj
M(1)
5Sk
It follows that
ke 0
je 40j
Eg [D]
= 1 1 e-
1 00
(11)
55k
-ke-
e2c
Eg Eo =
+
d0
(1 -1-e 002
(1 e 0j)2
iSk
Let (0) -ke- (1- + Ejst 01--- By the lemma below, Jk is non positive and increasing in 0 for 0 >> O. This means we can numerically compute the inverse function 7 with the stated error.
Lemma G.I. 9% is non-positive and increasing in for (ln(2).Additionn) 9h decreasing in k.
Proof. We first show non-positivity. For this, it is sufficient to show
e--05 Oj
c
(12)
e 88)2
- c 0-0
22

---

Published as conference paper ICLR 2022
holds for all j and 0 >> 0. This clearly holds for 1. Rearranging gives
- 5
The right-hand term is greater than equal I, so it suffices to choose 0 such that
j²e-00i11 ((j1) 1
ln(
2 j 1-1
It can be shown that the right-hand term decreases with j for j > 1, so suffices to take j = 2, which
implies 0 2 (n2).. By choice of f this is clearly true.
To show that gu increasing in 0, we consider
dg (x( = ke he-6((1 (1-6--00
-e--5se" 1)
+ Σ
(1 - -0--
(1 e -ji+
jsk
Similarly, it suffices to show
3 01 (1 c 2201)
01 20
(1 - E Ojj
(1 E -00
Rearranging, have
1 - 28
e 89
-0i-11 <
E 202
1 1- 5
Note that
29
1 c
fj
2 c -9j 94
1 1 200
20j
1 - e
20j
The term on the right greater than
for and j 2 Therefore, it suffices choose @ such that
2
j 16-1) 1)
< 2
0 In(2)")
j -
Once again, the term on the right is decreasing in j, so we can take j = 2, giving 2 4ln(2), which satisfied by our choice of 0.
Finally, the fact that 9& is decreasing in k follows from 12
G.3 EUCLIDEAN EMBEDDING CASE
Theorem 4.2. Let È gg))) be estimate of the accuracies EE (g())) using n samples, where all LFs are conditionally independent given Y. If the signs of a are recoverable, then with high probability
)g(n) E ((())))())))))) [12] o ((Tm2))) + (minl) / e
(
Here, Opmin|
min; E [o()))9()) and Cmaz max3, CjA--
23

---

Published as conference paper ICLR 2022
Proof. For three conditionally independent label functions Ae, Ab, de, our estimate of (gg()))(())) )g({)] is
Furthermore, if we define Za.b
Au.ul ea.ol"
we can write the ratio of elements of to as
((g(A))()))) Elg(A*) (v))]
|&ayl [@a,el
les,el
= -( (.a.baa
ka
leayl
|ea.el
Jés.cl
Tbe
(and the other definitions symmetric for Ke and kt). Now note that because assume that signs completely recoverable, (El(A>) Elg(A
" ((o(A*)
Next note that
[(o()"))(v)) - = 1301 (lg()))gg)))))))
By the reverse triangle inequality,
(())())))(vVI ([)(()))()))) -1
I - 2
[lo(A>)g(v) -Eo(A>))(()
where define min, + (w))]] (With high probability @|man| + [m|mn] but there is chance that E[g(X))g(()) and ((g()") [x))] have opposite signs.) For ease of notation, suppose we examine a particular (a, b) (1,2, Then,
(Blg(A )o(1) (ig((>
|212 ||
le12|le1s|
< (9(2)))) Ela(A )0)))
12za
[223
1 |éaal
|é12lléial
1222lless
c²
|223
Je23
Je2al
|223|
leaal
Je23
é12ê13
||223|
le23||
ê12
||1a
leiall
C13
||
le12ll
2
C23
C23
623
θ1261a
ê12
E13
<
|223
ezal +
eral
+
2
e12l
2
e23
623
C23
With high probability, all elements of and must less than emar max, Ej.k- We further know that elements of |e] are at least [immin//[[ () Now suppose (with high probability) that elements of [é] are
24

---

Published as conference paper ICLR 2022
least a² minl
and define Do,b bv,b ca.b. Then,
([ } ([ (((o)l1
maxx/Cmax mmaz)
1
A23 + a [minn
1 + a "min
|| 12
a² miii d |min
|||
memar Cmazi max))
2
(A + 4i3 A92)
6²
a mmin
@ [min)
2
a "Imin|
The original expression now
[ig(A*)(()) - (lo(A"))(v))
3 (4 + 42,0 DB.e)
max(Emaar emax)
2
c²
[mmii 1 Imin
2|
a1 min
2|
To bound the maximum absolute value between elements of è and e, note that
(4 + A2, + A2,,)) < ll - Ca,b,ellF, where ca a matrix with eaj in the (-th position. Moreover, is fact that Ctc.b.--e.bba Villea.b,e-aal S la,l where the rank of êa,b. Ca.b.c. Putting everything together,
((gg(>)g(())
max (emazy 2maz)
2
1
wn
||ea,b, - Ca,beel
mminn a minn
E[
|min
E 2
2
max Emazy emaz)
2
3
Illeadio - Ea, z
E[Y2J
y
(minn| a mmin
[min
Lastly, to compute [
-(g(A)) we use Jensen's inequality (concave version, due
to the square root) and linearity of expectation:
([" - Elg()))
1
max Emmax enaa)
1
2
E Ell ca
a1
24 [mén]] 2
E 2
mmin
min
We use the covariance matrix incquality as described in Tropp (204)), which states that
P(Ilé ell2 2 7) S max
2e =h 20 +txx
where max, Cao and C is universal constant.
To get the probability distribution over ||e,, - ea,be 12, we just note that P(llêa,b. - ea.boll2 2 7)
P(llē e| 2 ?²) to get
P(Ilea,b. ca.b.el 2 7) < 2c max (e 3e, -
25

---

Published as conference paper ICLR 2022
From this can integrate get
Blllea,b, ea,b, / P(llea,be 2a r)dy S 2e max
(o'C²
0²
0 a
.2
=
n²
Substituting this back in, we get
[|(B()(X)))()) (lg(A*)
max max(Emaz Emaz e max)
[mmén) ammin )2
Imin Immni 2
R. 2
|miin|
max (emax e
2
0²
[miin) Opmin )2
Imin [mini]
2[Y2]4
@ min
E
2
max emaz: emaz)
2 [mmn)]
(a [minn| + O|min| ) min (E (((2())
a [mii miiil
with high probability. Finally, clean up the almin| and @mmin terms. The terms involving and can be rewritten as
+ 2u min]
a min
0 [ini|
+ 20 min
[minn] + a imin
26 [mmin]
We suppose that Apminl Omiin
E e, + c) for some >> 0 with high probability. Then, this becomes less than
1 2a- Imnn
2ā mini
(1 4) 10 min|
+2(1
aa 1 min|
+ (1 e [min
4(1 e)
minn
min
[iminn
Therefore, with high probability, the sampling error for the accuracy is bounded by
max
(aeaa-maa- e
B(( - Elo(>")((v)lle) = O o²
5 |massol
[mmnn]
max
(e5x(e5 maax
[minl
Note that if all label functions conditionally independent, only need know the sign of one accuracy to recover the rest. For example, if we know if [9(()) is positive negative, we can use (lg()))(()) 3 ...., (lo())) (((()) ei. E(y to recover all other signs.
e1 B[g(A ([g(A") ((()))))))))
26

---

Published as a conference paper ICLR 2022
H EXTENDED EXPERIMENTAL DETAILS
In this section, we provide some additional experimental results and details. All experiments were conducted on a machine with Intel Broadwell 2.7GHz CPU and NVIDIA GK210 GPU. Each experiment takes from 30 minutes up few hours depending on the experiment conditions.
The following is basic background useful for understanding hyperbolic space models. Hyperbolic space is Riemannian manifold. Unlike Euclidean space, it does not have a vector space structure. Therefore it is not possible to directly add points. However, geometric notions like length, distance, and angles do exist; these are obtained through the Riemannian metrie for the space. Points in Smooth manifolds M are equipped with a tangent space denoted T,M. The elements (tangent vectors MyM) in this space are used for linear approximations of a function at a point.
Hyperbolie Space and Geodesic Regression
The shortest paths in a Riemannian manifold are called geodesics. Each tangent vector E TyM is equiv- alent to a particular geodesic that takes p to a point q. Specifically, the exponential map is the operation exp: Tp.M- - M that takes to the point g (v) that the tangent vector v points to. In addition, the length |||||| of the tangent vector is also the distance d(p, q) on the manifold. This operation can be reversed with the log map. which, given q E M, provides the tangent vector v = log,
The geodesic regression model is the following. Set some intercept E M. Scalars 2, E R are selected according to some distribution. Without noise, the output points are selected along a geodesic through p parametrized by 8: Vi exp,, (2; x (9), where / is the weight vector, tangent vector in (M)) that is not known. This is a noiseless model; the more interesting problem allows for noise, generalizing the typical situation in linear regression. This noise is added using the following approach. For notational convenience, we write exp,(") (v) as exp(p. v). Then, the noisy y are y = exp(cxp(p, I; x E)),;), where & E Toxp(n..)) M. This notion generalizes adding zero-mean Gaussian noise the y in conventional linear regression.
The equivalent of least squares estimation is then given by P, B arg ming.a Σ d(exp(q. ax;)) 9:)
Semantic Dependency Parsing We used datasets on Czech and English taken from the Universal De- pendencies Nivre et al. (2020) repository. The labeling functions were Stanza Qi et al. (2020) pre-trained semantic dependency parsing models. These pre-trained models were trained over other datasets from the same language. For the Czech experiments, these were the models cs.cltt, cs. c s.ffictree, cs.pdt, while for English, they were taken from en. gum, en lines, en en.partut, en.ewt. The metric the standard unlabeled attachment score (UAS) metric used for unlabeled dependency parsing. Finally, we used access to a subset of labels to compute expected distances, as in the label model variant in Chen et al. 2021
Movies dataset processing In order to have access to ample features for learning to rank and regression tasks, we combined IMDb (imd) and (MDb(mmd) datasets based on movie id. In the IMDb dataset, we mainly used movie metadata, which has information chiefly about the indirect index of the popularity (e.g. the number of director facebook likes) and movie (e.g. genres). The TMDb dataset gives information mainly about the movie, such as runtime and production country. For ranking and regression, we chose vaveraverage column from TMDb dataset as target feature. In rankings, column into rankings so the movie with the highest review has a top ranking. We excluded the movie scores in IMDb dataset from input features since it is directly related to TMDb vote average. But later included IMDb, Rotten Tomatoes, Movielens ratings as weak labels in Table
converted the vote -average
After merging the datasets, we performed feature engineering follows.
1. One-hot encoding: color, content content_rating, original language, genres, status
27

---

Published as conference paper ICLR 2022
2. Top (Irequency) 0.5% one-hot encoding; keywords, keywords, production.companiee. actors
3. Count: production countries, spoken languages
4. Merge (add) actor f.acebok likes, actor 2 facebook likes, actor 3.ccbbook likes into ac- tor facebook likes
5. Make binary feature regarding whether the movie's 's homepage is missing or not.
6. Transform date into one-hot features such as month, the day of week.
By adding the features above, we were able to enhance performance significantly in the fully-supervised regression task used as a baseline.
In the ranking experiments, we randomly sampled 5000 sets of movies as the training set, and 1000 sets of movies the test The number of items in an item set (ranking set) was 5. Note that the movies in the training set and test set are strictly separated, i.c. if a movie appears in the training set, it is not included in the test set.
Model and hyperparameters In the ranking setup, we used 4-layer MLP with ReLU activations. Each hidden layer had 30 units and batch normalization & Szegedy (015) was applied for all hidden layers. We used the SGD optimizer with ListMLE loss (Xia al.] (2008): the learning rate was 0.01.
In the regression experiments, we used gradient boosting regression implemented in sklearn with n.estimator==250. Other than neestimators, we used the default hyperparameters in sklearn's implemen- tation.
BoardGameGeek data processing In the BoardGameGieek dataset (boa 2017). we used metadata of board games only. Since this dataset showed enough model performance without additional feature engi- neering, we used the existing features: yearpublished, minplayers, maxplayers, playingtime, minplaytime, maxplaytime, minage, owned, irading, wanting, wishing, numcomments, numweights, averageweight. The target variable was average ratings (average) for regression, and board game ranking (Board Game Rank). Note that 'Board Game Rank' cannot be directly calculated from average ratings. BoardGameGeck has its own internal formula to determine the ranking of board games. In the ranking setup, we randomly sampled 5000 board game sets as the training set, and 1000 board game sets as the test set.
Simulated LFs generation in ranking and regression In rankings. we sampled from X²(i) (r.d with Bg. For more realistic heterogeneous LFs. I/3 (good) LFs Be are sampled from Uniform(0.2, 1). and 2/3 (bad) LFs' 8a are sampled from mniform((..00 0.01). Note that higher value of Ba yields less noisy weak labels. In regression, we used the conditional distribution A|Y to generate samples of A. Specifically, where A|Y N E), where j EAY Ey' y and Σ Σn EAY Ey Σy from the assumption (A, Y) ~ (0 E).
I ADDITIONAL SYNTHETIC EXPERIMENTS
We present several additional synthetic experiments, including results for partial ranking labeling functions and for parameter recovery in regression settings.
I.1 RANKING
To check whether our algorithm works well under different conditions, we performed additional experiments with varied parameters. In addition, we performed partial ranking experiment.
28

---

Published as a conference paper ICLR 2022
1e-2
1e-2
Unweighted
1.2
Unweighted
Mean KT Distance
2.0
Optimal Weights Estimated Weights
Mean KT Distance
1.0
Optimal Weights
Estimated Weights
1.5
0.8
0.6
1.0
0.4
0.5
0.2
0.0
0.0
2
6
10
12
14
16
18
2
10 12 14
16 18
Num LFs (m)
Num LFs (m)
(a) d = 10, = 250
(b) d = 20, = 250
Figure 6: Inference via weighted and standard Kemeny rule over full rankings (top) with permutations of size d = 10, 20. Error metric is Kendall tau distance (lower is better). Proposed weighted Kemeny rule is nearly optimal on full rankings.
Ranking synthetic data generation First, n true rankings Y are sampled uniformly at random. In the full ranking setup, each LF Ty is sampled from the Mallows (i) ~ -x, with parameters 8. Y and in the partial ranking setup
sampled from selective Mallows with parameters 3a, Y,, S, where each S; S [d] is chosen randomly while ensuring that each æ E [d] appears in at least a fraction of these subsets. Higher p corresponds to dense partial rankings and smaller p leads to sparse partial rankings. We generate 18 LFs with 10 of then having 3. ~ fni form (1.0...000 0.2) and rest have 3, ~ form 5). This was done order to model LFs of different quality. These LFs are then randomly shuffled so that the order which they are added is not a factor. For the partial rankings setup we use the same process to get 3, and randomly generate S, according to the sparsity parameter p. For a set of LFs parameters we run the experiments for 5 random trials and record the mean and standard deviation.
Full Ranking Experiments Figure synthett data results without an end model, i.e., just using the inference procedure as an estimate the label. We report the "Unweighted" Kemeny baseline that ignores differing accuracies. 'Estimated Weights' uses our approach, while 'Optimal Weights' is based with access to the true 6a parameters. As expected, synthesis with estimated parameters improves on the standard Kemeny baseline. The improvement for the full rankings case (top) is higher for fewer LFs; this is intuitive, as adding more L.ss globally improves estimation even when accuracies differ.
oracle
Partial Ranking Experiments In the synthetic data partial ranking setup, we vary the value of p (ob- servation probability) from 0.9 (dense) to 0.2 (sparse) and apply extension of the inference method to partial rankings. Figure shows the results obtained. Our observations in terms of unweighted vs weighted aggregation remain consistent here with the full rankings setup. This suggests that the universal approach can provide the same type of gains in the partial rankings.
I.2 REGRESSION
Similarly, we performed a synthetic experiment to show how our algorithm performs in parameter recovery.
Regression synthetic data generation The data generation model is linear Y 3 X. where our data is given by (X,Y) with X E R and Y E R. We generate such samples. Note that we did not add noise variable 6 ~ N00, d²) here since we do not directly interact with Y; the noise exists instead in the labeling functions (i.e., the weak labels).
29

---

Published as conference paper ICLR 2022
Unweighted
0.16
Unweighted
Mean KT Distance
0.05
Optimal Weights Estimated Weights
Mean K7 Distance
Optimal Weights
0.14
Estimated Weights
0.04
0.12
0.10
0.03
0.08
0.06
0.02
0.04
0.02
0.01
12
15
18
12
15
18
Num LFs (m)
Num LFs (m)
(a) = 10, n = 250,
0.9
(b) d = 10, n 250, p 0.7
0.30
Unweighted
0.350
Unweighted
Mean KT Distance
0.25
Optimal Weights Estimated Weights
Mean KT Distance
0.325
Estimated Weights
Optimal Weights
0.20
0.300
0.275
0.15
0.250
0.10
0.225
0.05
0.200
12
15
16
3
12 15 Num LFs (m)
18
Num LFs (m)
(c) = 10, n = 250, p 0.5
(d) d = 10, n 250, p = 0.2
Figure 7: Inference via weighted and standard majority vote over partial rankings with permutations size d = 10. Error metric is Kendall tau distance (lower is better). Proposed inference rule is nearly optimal on full rankings.
Parameter estimation in synthetic regression experiments Figure reports results on synthetic data capturing label model estimation error for the accuracy and correlation parameters (μ, and for directly estimating the label Y. As expected, estimation improves as the number of samples increases. The top-right plot is particularly intuitive: here, our improved inference procedure vastly improves over naive averaging it accesses sufficiently many samples to estimate the label model itself. On the bottom, observe, expected, that label estimation significantly improves with access to more labels.
J ADDITIONAL REAL LF EXPERIMENTS AND RESULTS
We present a few more experiments with different types of labeling functions.
J.1 BOARD GAME GEEK DATASET
the board games dataset, we built labeling functions using simple programs expressing heuristics. For regression, we picked several continuous features and scaled them to range and removed outliers. Similarly, for rankings, we picked what we expected to be meaningful features and produced rankings based on them. The selected features were ['owned', 'trading', 'wanting', 'wishing", 'numcomments"]
30

---

Published as conference paper ICLR 2022
μl estimation efror
Σ estimation error
Label estimation error
109
10
Baseline
Mu param error. L2
Vallue error MSE
Our Approach
10
Tot, param error,
10
10-3
10-1
10a
10a
10a
10a
10a
10'
Samples
Samples
Samples
(a) Numher of samples
μ estimation
estimation
Label estimation error
10
Mu param error, L.2
Proo L2
value error MSE
40-30-3
10-3
10
10
Bezzer 201
2 10-3
Baseline Approach
10
2
2 Num LFs (m)
2
2
2
2
Num LFs (m)
Num LFs (m)
(b) Number of LFs
Figure 8: Parameter and label estimation with varying the number of samples (top) and the number of labeling functions (bottom)
training examples
Kendall Tau distance (mean + std)
Fully supervised (5%) Fully supervised (10%) WS (Heuristics)
250
0.1921 + 0.0094
500
0.1829 + 0.0068
5000
0.1915 = 0.0011
Table 5: End model performance with true ranking LFs in BGG dataset.
In this case, we observed that despite not having access to any labels, we can produce performance similar to sully-supervised training on 5-10 of the true labels. We expect that further LF development will produce even better performance.
J.2 MSLR- WEB10K
To further illustrate the strength of our approach information retrieval (such as BM25) as weak supervision sources. The task is information retrieval, the dataset is MSLR-WEB WEB10Kms) and the model and training details identical to the other experiments. We used several labeling functions including BM25 and relied on our framework to integrate these. The labeling functions were written over BM25 and features such covered query term number, covered query
experiment using unsupervised learning methods
31

---

Published as conference paper ICLR 2022
of training examples
MSE (mean + std)
Fully supervised (1%)
144
0,4605 + 0.0438
Fully supervised with "bad" subset (10%)
1442
0.8043 + 0.0013
Fully supervised with "bad" subset (25%)
3605
0.46228 + 0.0006
WS (Heuristics)
14422
0.8824 + 0.0005
Table 6:
End model performance with true regression LFs in BGG dataset. The training data was picked based on the residuals linear regression (resulting "bad" subset scenario for a challenging dataset). We obtain comparable performance.
0.375
0.300
(Majority Vote)
0.350
0.275
WS (Ours)
MSE
MSF
Fully supervised (25%)
0.250
0.325
Fully supervised (50%)
Fully supervised (100%)
0.225
0.300
5
15
15
Num LFs
Num LFs
(a) Movies dataset
(b) BoardGameGeek dataset
Figure 9: End model performance with regression LFs (Left: Movies dataset, Right: BGG Dataset). Results
from training model pseudolabels are compared to fully-supervised baselines varying proportions of the dataset. Baseline is the averaging of weak labels. Metric (MSE); lower is better.
term ratio, boolean model, vector space model, LMIR.ABS, LIIR.DIR, LMIRJMM, and query-url click count.
As expected, the synthesis of multiple sources produced better performance than BM25 Dehghani et al. (2017) alone. Despite not using any labels, we outperform training on 10% of the data with true labels. This suggests that our framework for integrating multiple sources is better choice than either hand-labeling using a single source of weak supervision to provide weak labels. Below, for Kendall tau, lower better.
Kendall tau distance
NDCG@1
Fully supervised (10%)
0.4003 + 0.0151
0.7000 = 0.0200
Fully supervised (25%)
0.3736 + 0.0090
0.7288 + 0.0077
WS (Dehghani al. 2017))
0.4001 + 0.0063
0.7288
0.0077
WS (Ours)
0.3929 + 0.0052
0.7402 = 0.0119
Table 7: End model performance with true ranking LFs in MSLR-WED I0K dataset. Since the dataset has a lot of tie scores and the number of items uniform across examples, we sampled the examples with five unique scores (0, 1, 2, 3. 4). Also, in each example, items are randomly chosen so that each score occurs only once in each item set.
32


Reviews:
[{"review_id": "stSjQuj4DFH", "reviewer": "Reviewer_NZTU", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "A new general framework for weak supervision is proposed. The main idea is to learn embeddings over the labels tractably into two embedding spaces (Boolean/Euclidean). Then, estimators for the parameters of the labeling model is learned using MLE. It is proved that if the embeddings are isometric the estimators are consistent and convergence rates are proven for these estimators. Experiments are performed on varied tasks and the results compare the proposed approach with Snorkel to show improved performance in weakly supervised learning for these tasks.\n\nThe paper is well written and has a very general framework for weak supervision. The experiments show the benefits of this framework in varied tasks. Also, there are new problems that the proposed framework is applied to (not previously possible by other weakly supervised approaches). The paper seems well written, has both good experiments and theoretical guarantees. One minor point is perhaps there is not a lot in discussion in terms of prior work for someone who is not familiar with the specific area. Is snorkel the only possible comparison baseline (particularly since a lot of the tasks are novel and cannot be done by snorkel).\n", "summary_of_the_paper": "A novel general approach for weakly supervised learning.\n+ A new model for incorporating weak sources based on an exponential family parameterization\n+ Theoretical guarantees on the estimators for learning the parameterization\n+ Empirical results show that the proposed approach can apply weak supervision to novel problem types", "summary_of_the_review": "Overall, this seems like a strong paper with good theoretical justification and experimental results. The one possible weakness is perhaps lack of comparison baselines (though not sure if it is possible or not)", "strength_and_weaknesses": "", "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": "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": "bs8zAz6RDC_", "reviewer": "Reviewer_AswL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Strength\n* The proposed embedding-based approximate estimation approach is novel.\n* Theoretical bounds are derived to monitor the closeness of this approximate estimation.\n* Experiments are performed in multiple domains with different types of labels\n\nWeakness\n1. Writing can be substantially improved. \n\n A lot of context is missing in the main paper, which makes the paper very hard to follow. Specifically\n\n* Needs a bit more background introduction. \"LF\" (label function) in section 1 is defined in section 2. \n* How θa and θab are inferred from accuracies and correlations is not clear. Seems to be based on results from prior works. As this is the key innovation, would of great help to include a illustration of the construction of algorithms 1 and 3.\n* The meaning of correlation set E in equation (1) is undefined.\n* I find the advantage of a learned model over majority vote straightforward and well-studied, and can be compressed to include more background discussions.\n\n Experiments are lousily organized. Readers have to go to the appendix for a more comprehensive picture of the proposed approach.\n\n* Experiments in Figure 1,2 and 3 are repetitive and can be summarized.\n* A selection of experiments on estimation quality (figure 5, 6 and 7) would strengthen the main paper.\n\n2. Discussions and experiments on the universality aspect is lacking. This work claims to be a universal approach for WS, which boils down to an embedding-based approximation of distance function d(,). It is a question whether such an approximation could be made close enough to a usable level for truly universal application. It would be nice to remark at Theorem 4.2 on how accurate the embedding approximations have to be for θ to be accurate using a practical example. Is being able to tractably estimate θ but not being loyal to d(,) a superior outcome than using a not-so-close estimate of θ?\n\n-----------------------------------------\n\nUpdate: My concerns on writing and universality have been sufficiently addressed with the latest revision. ", "summary_of_the_paper": "This work studies a weakly supervised learning setup of aggregating multiple weak sources of labels into high-quality pseudo labels for learning. \n\nThe proposed approach is based on building graphical models with the true labels as latent variables following existing techniques, but generalizes existing works in 1) supporting more types of task labels such as ranking, regression and in non-Euclidean spaces through approximating the graphical model terms using dot product between embeddings, and 2) algorithms for efficient learning under the embedding approximation and theoretical bounds on the estimation error using embedding-based approximation. \n\nExperiments focus on comparing weakly supervised learning performance of learning a graphical model versus using majority vote on the newly supported tasks and fully supervised learning with varying amount of labels. Results show that learning the graphical model achieved better performance than majority vote and can achieve parity reach a certain level of fully supervision.", "summary_of_the_review": "My recommendation of this paper is based on the novelty with respect to previous works along this line of work, also considering the writing and experiment quality. I am not a domain expert and I didn't verify the correctness of equations and proofs.\n\nMy main concerns are 1) the proposed approach is not explained clearly (or am I missing the context?) and 2) the experiments included in the main paper seem shallow and repetitive. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ni4z4Te65zj", "reviewer": "Reviewer_xXw5", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n\n- The paper is clear and well written with proper notations.\n- The authors emphasize an important aspect of weak supervision (allowing different types of labels and unifying.)\n\nWeaknesses:\n\n- I find the theoretical contributions on the more trivial side. Finding the roots of the triplets methods is just plain algebra and error term easily follows from bernoulli assumption.\n- The dataset is constructed by the authors, so it is hard to evaluate its performance. The criteria metrics might not be fair since they are directly related to this paper's distance choices.\n- Since the paper claims to be a universal framework, I would expect using different types of labels in the same task (like if we have binary labels for some data and probabilistic outputs for others), or coexisting more than one task type is doable. However, in their formulation it is not, since the distances would need to be mapped on the same space or at least a similar range.\n- I believe Related Work section is significiant and should be in the main paper, not in the supplementary.\n\n\nQuestions:\n- How do you compare your dataset with [1]?\n- How do you compare method for varying  label density(low, middle, high) vs majority voting? Why snorkel works worse than majority voting in your experiments? \n- How would you adapt your method for the problems that use different label types at the same time? (rather than choosing one type of distance based on the problem)\n\n\n\n[1] Zhang, Jieyu, et al. \"WRENCH: A Comprehensive Benchmark for Weak Supervision.\" arXiv preprint arXiv:2109.11377 (2021).", "summary_of_the_paper": "The paper proposes a framework for weak supervision which works for both discrete and continuous labels. The proposed framework assumes the sources are coming from an exponential family distribution and generalizes the accuracy and correlation terms in previous approaches. They use a discriminative learning setting and use triplet methods in order to compute accuracies. They evaluated the performance for regression, ranking and hyperbolic and graph learning tasks. \n\nThe paper's main contribution is putting an exponential family distribution assumption which allows to use any metric space. In their experiments, they choose distances based on the problem and label type, mostly weighted L2 distance except hyperbolic dataset. \n\n\n\n\n", "summary_of_the_review": "In general, the paper is written clearly, connects previous work in a good way, so it is valuable in that sense. I am willing to chance my vote towards accept if the authors could clarify my concerns and convince me their work has sufficient contributions to be published.", "strength_and_weaknesses": "", "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": "MyYO-sEV1lw", "reviewer": "Reviewer_NJ4o", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "I commend the authors on their thoroughness and the aims of their approach - which are much needed in the field of weak supervision. I find some of the potential scenarios really interesting and appealing, particularly learning in hyperbolic space.\n\nMy concerns are threefold. The first has to do with novelty. There are many approaches in the past that also move past classification to consider ranking and regression. In general in loss factorizations of the form of \n\nLoss factorization, weakly supervised learning and label noise robustness\nGiorgio Patrini, Frank Nielsen, Richard Nock, Marcello Carioni Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:708-717, 2016.\n\nthat apply to most of those settings. In the following, the authors can also find the explicit generalization including classification, ranking or regression, with a similar notion of pseudolabels:\n\nCid-Sueiro J., García-García D., Santos-Rodríguez R. (2014) Consistency of Losses for Learning from Weak Labels. In: Calders T., Esposito F., Hüllermeier E., Meo R. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2014. Lecture Notes in Computer Science, vol 8724. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44848-9_13\n\nAnd even further generalizations from weak to superset learning, which arguably could be seen as including the former. \n\nHüllermeier E., Cheng W. (2015) Superset Learning Based on Generalized Loss Minimization. In: Appice A., Rodrigues P., Santos Costa V., Gama J., Jorge A., Soares C. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2015. Lecture Notes in Computer Science, vol 9285. Springer, Cham. https://doi.org/10.1007/978-3-319-23525-7_16\n\nIt is not clear to me how these overlap with this work. Also, the structure of the paper does not help in understanding this, with the related work being in the supplementary material. Finally, the title seems a bit to general for what it is shown in the paper. ", "summary_of_the_paper": "The authors present a framework that intends to extend the label types considered traditionally in learning from weak labels. ", "summary_of_the_review": "In its current form, the structure of the paper makes it difficult to assess the novelty. Also, there are previous approaches in the literature that seem to overlap with the aim of the paper. ", "strength_and_weaknesses": "", "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:

Meta-review: The paper propose a universal technique that enables weak supervision over any label type while still offering desirable properties, including practical flexibility, computational efficiency, and theoretical guarantees.

Over the course of the rebuttal, the authors have made a substantial overhaul on writing and experimentation. The universality claims are now better supported by bounds, and experiments cover comparison to snorkel, majority vote and supervised learning, on multiple applications. The authors are encouraged to move the related work section to the main body of the paper. The authors should also clarify to what extent the contributions they make pertain to Snorkel as opposed to weak supervision more generally. This may require revisiting both the introduction as well as perhaps the title.
Decision: Accept (Poster)