UNIVERSALIZING WEAK SUPERVISION
Year: 2021

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 pseudolabels 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 estimator for learning a challenging but important generalization 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.

heading: 1 INTRODUCTION
text: 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, a crucial step is to model their accuracies and correlations. Informed by this model, high-quality pseudolabels are produced and used to train a downstream model. This simple yet flexible approach is highly successful in research and industry settings (Bach et al., 2019; Ré et 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), or to segmentation masks (Hooper et al., 2021), require a new model for source synthesis, a 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.
The main technical challenge for universal WS is the diversity of label settings: classification, structured prediction, regression, rankings, and more. Each of these settings seemingly demands a 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 an Ising model and relied on a property of such distributions: that the inverse covariance matrix is graph-structured. It is not clear how to lift such a property to spaces of permutations or to Riemannian manifolds.
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 can represent a label from any metric space (Y, dY). We
embed labels from Y into two tractable choices of space: the Boolean hypercube {±1}d and Euclidean space Rd. The label model (used for source synthesis) is learned with an efficient method-of-moments approach in the embedding space. It only requires solving a small number of scalar linear or quadratic equations. Better yet, for isometric embeddings, 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.
• Regression: on two real-world regression datasets, when using 6 or more labeling function, the performance of our approach is comparable to fully-supervised models.
• Learning in hyperbolic spaces: on a geodesic regression task in hyperbolic space, we consistently outperform fully-supervised learning, even when using only 3 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.
In 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.

heading: 2 PROBLEM FORMULATION AND LABEL MODEL
text: We give background on weak supervision frameworks, provide the problem formulation, describe our choice of universal label model, special cases, the embedding technique we use to reduce our problem to two easilyhandled 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., 2011; Mintz et al., 2009; Gupta & Manning, 2014; Dehghani et al., 2017; Ratner et 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 a downstream model.
Problem Formulation Let x1, x2, . . . , xn be a 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 (x1, y1), . . . , (xn, yn); however, in WS, we do not have access to the labels. Instead, we have estimates of y from m labeling functions (LFs). Each such LF s : X → Y produces an estimate of the true label y from a datapoint x. We write λa(i) ∈ Y for the output of the ath labeling function sa applied to the ith sample. Our goal is to obtain an estimate of the true label yi using the LF outputs λ1(i), . . . , λm(i). This estimate ŷ, is used to train a downstream model. To produce it, we learn the label model P (λ1, λ2, . . . , λm|y). The main challenge is that we never observe samples of y; it is latent. We can summarize the weak supervision procedure in two steps:
• Learning the label model: use the samples λa(i) to learn the label model P (λ1, λ2, . . . , λm|y), • Perform inference: compute ŷi, or P (yi|λ1(i), . . . , λm(i)), or a related quantity. Modeling the Sources Previous approaches, e.g., Ratner et al. (2019), select a particular parametric choice to model p(λ1, . . . , λm|y) that balances two goals: (i) 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 to exploit the properties of exponential family models. The natural choice is
p(λ1, . . . , λm|y) = 1 Z exp ( m∑ a=1
−θadY(λa, y)c︸ ︷︷ ︸ Accuracy Potentials
+ ∑
(a,b)∈E −θa,bdY(λa, λb)c︸ ︷︷ ︸ Correlation Potentials
) . (1)
Here, the set E is a set of correlations corresponding to the graphical representation of the model (Figure 1, right). Observe how source quality is modeled in (1). If the value of θa is very large, any disagreement between the estimate λa and y is penalized through the distance dY(λa, y)c and so has low probability. If θa is very small, such disagreements will be common; the source is inaccurate.
We also consider a more general version of (1). We replace−θadY(λa, y) with a per-source distance dθa . For example, for Y = {±1}d, dθa(λa, y) = −θTa (λa− y)abs, with θa ∈ Rd, generalizes the Hamming distance. Similarly, for Y = Rd, we can generalize −θa‖λa − y‖2 with dθa(λa, y) = −(λa − y)T θa(λa − y), with θa ∈ Rd×d 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 of which cannot be tackled with existing methods.
• Binary classification: Y = {±1}, dY is the Hamming distance, c = 1: this yields a shifted Ising model for standard binary classification, as in Fu et al. (2020).
• Sequence learning: Y = {±1}d, dY is the Hamming distance, c = 1: this yields an Ising model for sequences, as in Sala et al. (2019) and Safranchik et al. (2020).
• Ranking: Y = Sρ, the permutation group on {1, . . . , ρ}, dY is the Kendall tau distance, c = 1. This is a heterogenous Mallows model, where rankings are produced from varying-quality sources. If m = 1, we obtain a variant of the conventional Mallows model (Mallows, 1957).
• Regression: Y = R, dY is the `2 distance, c = 2 produces sources in Rd with Gaussian errors. • Learning on Riemannian manifolds: Y = M , a Riemannian manifold (e.g., hyperbolic space), dY is the
Riemannian distance dM , c = 1.
Majority Vote and its Relatives A simplifying approach often used as a baseline in weak supervision is the majority vote. Assume that the sources are conditionally independent (i.e. E is empty in (1)) and all accuracies are identical. In this case, there is no need to learn the model (1); instead, the most “popular” label is used. For binary labels, this is the majority label. In the universal setting, a natural generalization is
ŷMV = arg min z∈Y
1
m ∑m a=1 dY(λ a, z)c. (2)
Special cases of (2) have their own name; for permutations, it is the Kemeny rule (Kemeny, 1959) used to solve the rank aggregation problem. For Riemannian manifolds, ŷMV is called the Fréchet or Karcher mean.
Algorithm 1: Universal Label Model Learning Input: Output of labeling functions λa(i), correlation set E, prior p for Y , optionally embedding function g. Embedding: If g is not given, use Multidimensional Scaling (MDS) to obtain embeddings g(λa) ∈ Rd ∀a for a ∈ {1, 2, . . . ,m} do
For b : (a, b) ∈ E Estimate Correlations:∀i, j, Ê [ g(λa)ig(λ b)j ] = 1
n ∑n t=1 g(λ a(t))ig(λ b(t))j
Estimate Accuracy: Pick b, c : (a, b) 6∈ E, (a, c) 6∈ E, (b, c) 6∈ E. if Im(g) = {±1}d ∀i, Estimate Ôa,b = P̂ (g(λa)i = 1, g(λb)i = 1), Ôa,c, Ôb,c, Estimate `a = P̂ (g(λa)i = 1), `b, `c Accuracies← QUADRATICTRIPLETS(Oa,b, Oa,c, Ob,c, `a, `b, `c, p, i)
else ∀i, Estimate ea,b := Ê [ g(λa)ig(λ b)i ] = 1
n ∑n t=1 g(λ a(t))ig(λ b(t))i, ea,c, eb,c
Accuracies← CONTINUOUSTRIPLETS(ea,b, ea,c, eb,c, p, i) Recover accuracy signs (Fu et al., 2020)
end for return θ̂a, θ̂a,b by running the backward mapping on accuracies and correlations
Majority vote, however, is insufficient in cases where there is variation in the source qualities. We must learn the label model. However, generically learning (1) is an ambitious goal. Even cases that specialize (1) in multiple ways have only recently been fully solved, e.g., the permutation case for identical θa’s) was fully characterized by Mukherjee (2016). To overcome the challenge of generality, we opt for an embedding approach that reduces our problem to two 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}d and Euclidean space Rd. To accomplish this, let g : Y → {±1}d (or g : Y → Rd) be an injective embedding function. The advantage of this approach is that if g is isometric—that is, distance preserving—then probabilities are preserved under g. This is because the sufficient statistics are preserved: for example, for g : Y → Rd, −θadY(λa, y)c = −θad(g(λa), g(y))c = −θa‖g(λa) − g(y)‖c, yielding is a multivariate normal for c = 2. Even if g is not isometric, there is a rich literature on low-distortion embeddings, with Bourgain’s theorem as a cornerstone result (Bourgain, 1985). This makes it possible to bound the error in recovering the parameters for any label type.
End Model Once we have produced pseudolabels—either 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 exponent c, the generalization of majority vote, the embedding space Im(g), and an example of an end model.

heading: 3 UNIVERSAL LABEL MODEL LEARNING
text: 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 λ1, . . . , λm. Afterwards, we can perform inference to compute ŷ or p(y|λ1, . . . , λm) or a related quantity, and use these to train a downstream model. Learning the Universal Label Model Our general approach is described in Algorithm 1; its steps can be seen in the pipeline of Figure 1. It involves first computing an embedding g(λa) into {±1}d or Rd; we
use multidimensional scaling into Rd as our standard. Next, we learn the per-source mean parameters, then finally compute the canonical parameters θa. The mean parameters are E[dG(g(λa)g(y))c]; which reduce to moments like E[g(λa)ig(y)j ]. To estimate the mean parameters without observing y (and thus not knowing g(y)), we 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 a simple non-linear system over the three sources (in 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 on average (see Ratner et al. (2019)).
The systems formed by the conditional independence relations differ based on whether g maps to the Boolean hypercube {±1}d or Euclidean space Rd. In the latter case we obtain a system that has a simple closed form solution, detailed in Algorithm 2. In the discrete case (Algorithm 3, Appendix C), we need to use the quadratic formula to solve the system. We require an estimate of the prior p on the label y; there are techniques do so (Anandkumar et al., 2014; Ratner et al., 2019); we tacitly assume we have access to it. The final step uses the backward mapping from mean to canonical parameters (Wainwright & Jordan, 2008). This approach is general, but it is easy in the R2 embedding case: here, the canonical θ parameters are the inverse of the mean parameters.
Performing Inference: Maximum Likelihood Estimator Having estimated the label model canonical parameters θ̂a and θ̂a,b for all the sources, we use the maximum-likelihood estimator
ŷi = arg min z∈Y
1
m ∑m a=1 dθ̂a(λ a(i), z)c. (3)
Compare this approach to majority vote (2), observing that it can produce arbitrarily bad outcomes. For example, suppose that we have m LFs, one of which has a very high accuracy (e.g., large θ1) and the others very low accuracy (e.g., θ2, θ3, . . . , θm = 0). Then, λ1 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 λ1. 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 dramatically simpler. In particular, in the case of isotropic Gaussian errors, where dθa(λ
a, y) = −θa‖λa − y‖2, there is no need to perform an embedding, since we can directly rely on empirical averages like 1 n ∑n i=1 dθa(λ
a(i), λb(i)). The continuous triplet step simplifies to directly estimating the covariance entries θ̂−1a ; the backward map is simply inverting this. Similarly, the inference procedure can be done entirely in the embedding step, even for non-isotropic Gaussians.

heading: 4 THEORETICAL ANALYSIS: ESTIMATION ERROR & CONSISTENCY
text: We show that Algorithm 1 contains consistent estimators of the mean parameters under the condition that the embeddings are isometric. We provide convergence rates for the estimators. As corollaries, we apply these estimators to rankings and regression, where isometric embeddings are available. Finally, we give a bound on 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 1. To keep our presentation simple, we assume a prior y over two values y ∈ {y1, y2} (i.e., there are two possible values of y, but we do not know, for any sample, which of the two yi is). The result below treats the (assumed to be known) class balance P (Y = y1) as a constant and assumes that we can correctly recover signs. Theorem 4.1. For any δ > 0, for some y1 and y2 with known class probabilities p = P (Y = y1), the quadratic triplet method recovers αi = P (g(λa)i = 1|Y = y), βi = P (g(λb)i = 1|Y = y), γi = P (g(λc)i = 1|Y = y) up to error O(( ln(2m 2/δ) 2n )
1/4) with probability at least 1 − δ for all conditionally independent label functions λa, λb, λc and for all i ∈ [m].
Algorithm 2: CONTINUOUSTRIPLETS Input: Estimates êa,b, êa,c, êb,c, prior p, index i Obtain variance E [ g(Y )2i ] from prior p
Ê[g(λa)g(y)]← √ |êa,b| · |êa,c| · E [Y 2] / |êb,c|
Ê[g(λb)g(y)]← √ |êa,b| · |êb,c| · E [Y 2] / |êa,c|
Ê[g(λc)g(y)]← √ |êa,c| · |êb,c| · E [Y 2] / |êa,b| return Accuracies Ê[g(λa)g(y)], Ê[g(λb)g(y)], Ê[g(λc)g(y)]
To showcase the power of this result, we apply it to the case of (Sρ, dτ ), that is, rankings from the symmetric group Sρ equipped with the Kendall tau distance dτ (Kendall, 1938). The resulting estimation problem is more challenging than learning the conventional Mallows permutation model (Mallows, 1957)—and the standard Kemeny rule (Kemeny, 1959) used for rank aggregation will fail if appied to it. Our result yields consistent estimation when coupled with the aggregation step (3).
We use the isometric embedding g into {±1}( ρ 2):
For some π ∈ Sρ, each entry in g(π) corresponds to a pair (i, j) with i < j, and this entry is 1 if in π we have i < j and −1 otherwise. We can show that for π, γ ∈ Sρ, it holds that ∑ i=1 g(π)ig(γ)i = ( ρ 2 ) − 2dτ (π, γ).
Corollary 4.1.1. For any δ > 0, U > 0, prior over y1 and y2 with known class probability p, and using Algorithm 1 and Algorithm 3, for all conditionally independent λa, λb, λc, with parameters U > θa, θb, θc > 4 ln(2), we can recover θa, θb, θc up to error O(ρ2(ln(2m2)/(2δn))1/4/|g2(U)|) with probability at least 1− δ, where g2(U) = (−ke−U )/((1− e−U )2) + ∑2 j=1(j 2e−Uj)/((1− e−Uj)2).
Note that the error goes to zero as O(n−1/4). This is an outcome of using the quadratic system, which is needed for generality. In the easier cases, where the quadratic approach is not needed (including the regression case), the rate is O(n−1/2). Next, note that the scaling in terms of the number of LFs m is O((lnm)1/4)—this is efficient. The g2 function captures the cost of the backward mapping.
Euclidean Space Rd Case The following is an estimation error bound for the continuous triplets method. Theorem 4.2. Let Ê[g(λa)g(y)] be an estimate of the accuracies E[g(λa)g(y)] using ê computed from n samples, where all LFs are conditionally independent given Y . If we assume the signs of a are recoverable, then with high probability
E[||Ê[g(λa)g(y)]− E[g(λa)g(y)]||2] = O (( a−10|min| + a −6 |min| )√ max(e5max, e 6 max)/n ) .
Here, a|min| = mini |E[g(λi)g(y)]| and emax = maxj,k ej,k.
The error tends to zero with rate O(n−1/2) as expected.
Distortion & Inconsistency Bound Next, we show how to control the inconsistency in parameter estimation as a function of the distortion. We write θ to be the vector of the canonical parameters, θ′ for their distorted counterparts (obtained with a consistent estimator on the embedded distances), and µ, µ′ be the corresponding mean parameters. Let 1 − ε ≤ dg(g(y), g(y′))/dY(y, y′) ≤ 1 for all y, y′ ∈ Y × Y . Then, for a constant emin (the value of which we characterize in the Appendix). Theorem 4.3. The inconsistency in estimating θ is bounded as ‖θ − θ′‖ ≤ ε‖µ‖/emin.
We note that we can further control ε in the worst case; operating over triplets, we need only embed threepoint metric spaces at a time, yielding ε ≈ 1− 1/(log 3) ≤ 0.1 (Bourgain, 1985).

heading: 5 EXPERIMENTS
text: We evaluated our universal approach with four sample applications, all new to WS: learning to rank, regression, learning in hyperbolic space, and estimation in generic metric spaces given by random graphs.
103 105 Samples
10 3
10 2
M u
pa ra
m e
rro r,
L2
estimation error
103 105 Samples
10 3
10 2
To t,
pa ra
m e
rro r,
L2
estimation error
103 105 Samples
10 1
100
Y va
lu e
er ro
r, M
SE
Label estimation error Baseline Our Approach
(a) Parameter Estimation Error
Figure 3: Regression: parameter estimation error (left two plots) and label estimation error comparing to majority vote baseline (rightmost) with increasing number of samples.
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 on 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 ranking model. We hypothesize that given enough signal, the produced pseudorankings can train a higher-quality model than using a 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 Algorithm 1. For inference, we applied (3). We compared against baseline fully-supervised models with only a proportion of the true labels (e.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 BoardGameGeek dataset (2020) (BGG), along with synthetic data. For our movies dataset, we 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 a ranking based on their tMDb 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 F. For real LFs, we built labeling functions using external KBs as WS sources based on alternative movie ratings along with popularity, revenue, and vote count-based LFs. For the end model, we used PTRanking (Yu, 2020), with ListMLE (Xia et al., 2008) loss. We report the Kendall tau distance (dτ ).
Results Figure 2 reports 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 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, as we anticipated.
Application II: 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 1, which uses the continuous triplets approach 2. For inference, we used the Gaussians simplification. As before, we compared against baseline fully-supervised models with a fraction of the true labels (e.g., 20%, 50%, ...) and MV (2). 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 F for our synthetic LF generation procedure.For the end model, we used gradient boosting (Friedman, 2001). The performance metric is 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 3. As expected, our parameter estimation error goes down in the amount of available data. Similarly, our label estimator is consistent, while majority vote is not.
Table 2 also 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, our label model lower MSE than the best individual LF, giving similar performance with fully supervised learning with 50% training data.
Application III: Geodesic Regression in Hyperbolic Space Next, we evaluate our approach on the problem of geodesic regression on a Riemannian manifold M , specifically, a hyperbolic space with curvature K = −50. The goal of this task is analogous to Euclidean linear regression, except the dependent variable lies on a geodesic in hyperbolic space. Further background is in the Appendix F.
Approach, Datasets, LFs, Results We generate y∗i by taking points along a geodesic (a generalization of a line) parametrized by a tangent vector β starting a p, further affecting them by noise. The objective of the end-model is to recover parameters p and β, which is done using Riemannian gradient descent (RGD) to minimize the least-squares objective: p̂, β̂ = arg minq,α ∑n i=1 d(expq(xiα), yi)
2 where d(·, ·) is the hyperbolic distance. To generate each LF λj , we use noisier estimates of y∗i , where the distribution is N (0, σ2j ) and σ2j ∼ U[1.5+(15zj),4.5+(15zj)], zj ∼ Bernoulli(0.5) to simulate heterogeneity across LFs; 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
0 2 4 Theta average
0.5
1.0
Ac cu
ra cy
Majority Vote Label Model
(a) Heterogeneous LFs
0 2 4 Theta average
0.5
1.0
Ac cu
ra cy
Majority Vote Label Model
(b) Homogenous LFs
Figure 5: Comparison between our label model and majority voting in generic metric space. Metric is accuracy; higher is better.
baseline. We compare fully supervised end models each with n ∈ {80, 90, 100} labeled examples to weak supervision using only weak labels. In Figure 4 we see that the Fré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 a better pseudolabel than a single (but less noisy) label. As expected, our approach yields consistently lower test loss than the Fréchet mean baseline.
Dataset/UAS Ŷ λ1 λ2 λ3
cs pdt-ud 0.873 0.861 0.758 0.842 en ewt-ud 0.795 0.792 0.733 0.792 en lines-ud 0.850 0.833 0.847 0.825 en partut-ud 0.866 0.869 0.866 0.817
have heterogeneous quality, while the two will have similar performance on homogeneous quality LFs.
Approach, Datasets, LFs, Results We generated random graphs and computed the distance matrix yielding the metric. We used Algorithm (1) 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 expected, when LFs have a heterogeneous quality, LM yield better accuracy than MV. However, when labeling functions are of similar quality, LM and MV gives a similar accuracy.
Application V: Semantic Dependency Parsing We ran our technique on semantic dependency parsing tasks, using datasets in English and Czech from the Universal Dependencies collection (Nivre et 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 a space of trees with a metric given by the `2 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.

heading: 6 CONCLUSION
text: Weak supervision approaches allow users to overcome the manual labeling bottleneck for dataset construction. While successful, such methods do not apply to each potential label type. We proposed an approach to universally apply WS, demonstrating it for three applications new to WS: rankings, regression, and learning in hyperbolic space. We hope our proposed technique encourages applying WS to many more applications.

heading: 7 ETHICS STATEMENT
text: While our proposed approaches to universal weak supervision are algorithmic and foundational in nature, we note that the resulting tool could be used to inject bias into datasets. Indeed, the weak supervision concept replaces hand-labeling (which comes with its own biases) with sources that can be automatically and broadly applied. This could amplify the biases in dataset labels.
We believe that special care must be taken to prevent such amplification. This will require further study and effort, and we believe that all users of our proposed system should invest into checking sources and resulting datasets. One important mitigation strategy that is easily built into the proposed weak supervision system is that once a source is identified as containing unacceptable biases, its accuracy can be easily downgraded to zero ensuring that it is not relied on in the resulting dataset.

heading: A GLOSSARY
text: The glossary is given in Table 4 below.

heading: B RELATED WORK
text: Weak Supervision Existing weak supervision frameworks, starting with Ratner et al. (2016), 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 et al. (2016), a factor model is used and a Gibbs-sampling based optimizer is the algorithm of choice. In Ratner et al. (2018), the model is a discrete Markov random field (MRF), and in particular, an Ising model. The algorithm used to learn the parameters solves a linear system obtained from a component of the inverse covariance matrix. In Sala et al. (2019) and Fu et al. (2020), the requirement to use the inverse covariance matrix is removed, and 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 our framework. The quadratic triplets idea is described, but
not analyzed, in the appendix of Fu et 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. (2011), distant supervision Mintz et al. (2009), co-training Blum & Mitchell (1998), and many others. Note that works like Dehghani et 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) or topic modeling Anandkumar et al. (2014). Early approaches use expectation maximization (EM), 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 et al. (2014) and its follow-on work, the explicitly crowdsourcing setting of Joglekar et al. (2013; 2015), and the graphical model learning procedures of Chaganty & Liang (2014); Raghunathan et al. (2016). 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 λ1, . . . , y ∈ {±1}
p(λ1, . . . , λm, y) = 1
Z exp ( m∑ a=1 θaλ ay + ∑ (a,b)∈E θa,bλ aλb + θY y ) . (4)
A difference is that this is a joint model; it assumes y is part of the model and adds a singleton potential prior term to it. Note that this model promotes agreement λay rather than penalizes disagreement−λadY(λa, y)c, but this is 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 (Plackett, 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 generalized Mallows model (Marden, 2014) and the Mallows block model (Busa-Fekete 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 θ 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 et 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-Mathieu & Schudy (2007); Caragiannis et al. (2016).

heading: C EXTENDED ALGORITHMIC DETAILS
text: Quadratic Triplet We give the full statement of Algorithm 3, which is the accuracy estimation algorithms for the case Im(g) = {±1}d.
Algorithm 3: QUADRATICTRIPLETS Input: Estimates Oa,b, Oa,c, Ob,c, `a, `b, `c, prior p, index i for y in Y do
Obtain probability p′ = P (Y = y) from prior p Set β ← (Oa,b(1− p′) + (`a − pz)`b)/(p′z − p′`a) Set γ ← (Oa,c(1− p′) + (`a − pz)`c)/(p′z − p′`a) Solve quadratic (pβγ + `b`c − pβ`c − pγ`b −Oa,b(1− p))(p′α− p′`a)2 = 0 in z P̂ (g(λa)i|Y = y)← z P̂ (g(λb)i|Y = y)← (Oa,b(1− p′) + (`a − pP̂ (g(λa)i|Y = y))`b)/(p′P̂ (g(λa)i|Y = y)− p′`a) P̂ (g(λc)i|Y = y)← (Oa,c(1− p′) + (`a − pP̂ (g(λa)i|Y = y))`c)/(p′P̂ (g(λa)i|Y = y)− p′`a)
end for return Accuracies P̂ (g(λa)i|Y = y), P̂ (g(λb)i|Y = y), P̂ (g(λc)i|Y = y)
Inference simplification in R For the simplification of inference in the isotropic Gaussian embedding, we do not even need to recover the canonical parameters; it is enough to use the mean parameters estimated in the label model learning step. For example, if d = 1, we can write these accuracy mean parameters as Ê [ g(λi)g(y) ] and put them into a vector Ê [Σ]Λy . The correlations can be placed into the sample covariance
matrix Σ̂g(λ1),...,g((λm). Then, ŷ(i) := E [ y|λ1(i), . . . λm(i) ] = Σ̂TΛyΣ̂ −1 Λ [λ
1(i), . . . , λm(i)]. (5) This is simply the mean of a conditional (scalar) Gaussian.
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, we can operate with multiple label types. For example, this might include a 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 a discrete value and a continuous value. The main idea is to construct a finite product space with individual label types. Suppose there are k possible label types, i.e. Y1,Y2, · · · ,Yk. We construct the label space by the Cartesian product
Y = Y1 × Y2 × · · · × Yk. All that is left is to define the distance:
d2Y(y1, y2) = k∑ i=1 d2Yi(proji(y1), proji(y2)),
where proji is projection onto the i-th factor space. Then, using this combination, we extend the exponential family model (1), yielding
p(λ1, . . . , λm|y) = 1 Z exp ( m∑ a=1 k∑ i=1 −θ(i)a dYi(proji(λa), proji(y))ci
+ ∑
(a,b)∈E k∑ i −θ(i)a,bdYi(proji(λ a), proji(λ b))ci ) .
We can learn the parameters θ(i)a , θ (i) a,b by Algorithm 1 using the same approach. Similarly, the inference procedure (3) can be extended to
ŷj = arg min z∈Y m∑ a=1 k∑ i=1 d θ̂ (i) a (proji(λ a(j)), proji(z)) ci .
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 distance. Second, we may wish to consider the abstention symbol as an additional element in 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).

heading: D ADDITIONAL THEORY DETAILS
text: We discuss further details for several theoretical notions. The first provides more details on how to obtain the canonical accuracy parameters θa from the mean parameters E [dτ (λa, y)] in the rankings case. The second involves a discussion of learning to rank problems, with additional details on the weighted estimator (3).
More on the backward mapping for rankings We note, first, that the backward mapping is quite simple for the Gaussian cases in Rd: it just involves inverting the mean parameters. As an intuitive example, note that the canonical parameter in the interior of the multivariate Gaussian density is Σ−1, the inverse covariance matrix. The more challenging aspect is to deal with the discrete setting, and, in particular, its application to rankings. We do so below.
We describe how we can recover the canonical accuracy parameter θa for a label function λa given accuracy estimates P (g(λa)i = 1|Y = y) for all y ∈ Y. By equation (1), the marginal distribution of λa is specified by
p(λa) = 1
Z exp(−g(λa)T θag(y)). (6)
Since this is an exponential model, it follows from Fligner & Verducci (1986) that
E[D] = d log(M(t))
dt
∣∣∣∣ t=−θa , (7)
where D = ∑ i 1{g(λa)i 6= g(y)i} and M(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
M(−θ) = 1 ρ! Z(θ).
Additionally, we have that the partition function satisfies (Chierichetti et al., 2014)
Z(θ) = ∏ j≤k 1− eθj 1− eθ .
It follows that
M(t) = 1
k! ∏ j≤k 1− eθj 1− eθ . (8)
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, . . . , λm|y) = 1 Z exp (∑ a −θadτ (λa, y) ) . (9)
Thus, if we only have one labeling function, we obtain the Mallows model (Mallows, 1957) for permutations, whose standard form is p(λ1|y) = 1/Z exp(−θ1dτ (λ1, y)). Permutation learning problems often use the Mallows model and its relatives. The permutation y (called the center) is fixed and n samples of λ1 are drawn from the model. The goal is to (1) estimate the parameter θ1 and (2) estimate the center y. This neatly mirrors our setting, where (1) is label model learning and (2) is the inference procedure.
However, our problem is harder in two ways. While we do have n samples from each marginal model with parameter θi, these are for different centers y1, . . . , yn—so we cannot aggregate them or directly estimate θi. That is, for LF a, we get to observe λa(1), λa(2), . . . , λa(n). However, these all come from different conditional models P (·|yi), with a different yi for each draw. In the uninteresting case where the yi’s are identical, we obtain the standard setting. On the other hand, we do get to 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 θa accuracy parameters differ in (9). However, if θa is 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 (1), 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 y using this estimator is still Θ(log(m/ε)) by using the pairwise majority result in Caragiannis et 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, 2004). However, there are PTAS available for it (Kenyon-Mathieu & Schudy, 2007). 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 on the PTAS.

heading: E PROOF OF THEOREMS
text: Next we give the proofs of the proposition and our two theorems, restated for convenience.

heading: E.1 DISTORTION BOUND
text: Our result that captures the impact of distortion on parameter error is Theorem 4.3. The inconsistency in estimating θ is bounded as ‖θ − θ′‖ ≤ ε‖µ‖/emin.
Before we begin the proof, we restate, in greater detail, some of our notation. We write pθ;dY for the true model
pθ;dY (λ 1, . . . , λm|y) = 1
Z exp ( m∑ a=1 −θadY(λa, y)c + ∑ (a,b)∈E −θa,bdY(λa, λb)c )
and pθ′;dg for models that rely on distances in the embedding space
pθ;dg (λ 1, . . . , λm|y) = 1
Z exp ( m∑ a=1 −θ′adg(g(λa), g(y))c + ∑ (a,b)∈E −θ′a,bdg(g(λa), g(λb))c ) .
We also write θ to be the vector of the canonical parameters θa and θa,b in pθ;dY and θ ′ to be its counterpart for pθ′;dg . Let µ be the vector of mean parameters whose terms are E[dY(λa, y)c] and E[dY(λa, λb)c].
Similarly, we write µ′ for the version given by pθ′;dg . Let Θ be a subspace so that θ, θ ′ ∈ Θ. Since our exponential family is minimal, we have that the log partition function A(θ̃) has the property that ∇2A(θ̃) is the covariance matrix and is positive definite. Suppose that the smallest eigenvalue of ∇2A(θ̃) for θ̃ ∈ Θ is emin.
For our embedding, suppose we first normalize (ie, divide by a constant) our embedding function so that
dg(g(y), g(y ′))
dY(y, y′) ≤ 1
for all y, y′ ∈ Y × Y . In other words, our embedding function g 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− ε ≤ dg(g(y), g(y ′))
dY(y, y′) ≤ 1
for all y, y′ ∈ Y × Y . If g is isometric, then we obtain ε = 0. On the other hand, as ε approaches 1, the amount of compression can be arbitrarily bad.
Proof. We use Lemma 8 from Fu et al. (2020). It states that
‖θ − θ′‖ ≤ 1 emin ‖µ− µ′‖
≤ ε emin ‖µ‖.
To see the latter, we note that ‖µ − µ′‖ ≤ ‖µ(1 − µ ′ µ )‖ ≤ ‖µ‖(1 − (1 − ε)) = ‖µ‖ε, where µ′
µ is the element-wise ratios, and where we applied our distortion bound.

heading: E.2 BINARY HYPERCUBE CASE
text: Theorem 4.1. For any δ > 0, for some y1 and y2 with known class probabilities p = P (Y = y1), the quadratic triplet method recovers αi = P (g(λa)i = 1|Y = y), βi = P (g(λb)i = 1|Y = y), γi = P (g(λc)i = 1|Y = y) up to error O(( ln(2m 2/δ) 2n )
1/4) with probability at least 1 − δ for all conditionally independent label functions λa, λb, λc and for all i ∈ [m].
Proof. Define
µai = [ P (g(λa)i = 1|Y = y) P (g(λa)i = 1|Y 6= y) P (g(λa)i = −1|Y = y) P (g(λa)i = −1|Y 6= y) ] , P = [ P (Y = y) 0 0 P (Y 6= y) ] ,
and
Oabi =
[ P (g(λa)i = 1, g(λ b)i = 1) P (g(λ a)i = 1, g(λ
b)i = −1) P (g(λa)i = −1, g(λb)i = 1) P (g(λa)i = −1, g(λb)i = −1)
] .
By conditional independence, we have that
µai P (µ b i ) T = Oabi . (10)
Note that we can express
P (g(λa)i = 1|Y 6= y) = P (g(λa)i = 1) P (Y 6= y) − P (g(λ a)i = 1|Y = y)P (Y = y) P (Y 6= y) .
We can therefore rewrite the top row of µai as [αi, c a i −dαi] where cai = P (g(λa)i=1) P (Y 6=y) and d = P (Y=y) P (Y 6=y) . After estimating the entries of Oi’s and ci’s, we consider the top-left entry of (10) for every pair of a, b and c, to get the following system of equations
(1 + d2)αiβi + ĉ a i ĉ b i − ĉai dβi − ĉbidαi = Ôabi /p,
(1 + d2)αiγi + ĉ a i ĉ c i − ĉai dγi − ĉcidαi = Ôaci /p,
(1 + d2)βiγi + ĉ b i ĉ c i − ĉbidγi − ĉcidβi = Ôbci /p,
where βi and γi are the top-left entries of µbi and µ c i respectively. Dropping the i subscript for ease of notation and rearranging the first and third equations gives us expressions for α and γ in terms of β.
α = Ôab/p+ ĉadβ − ĉaĉb
(1 + d2)β − ĉbd ,
γ = Ôbc/p+ ĉcdβ − ĉbĉc
(1 + d2)β − ĉbd .
Substituting into (7) gives
(1 + d2) ĉadβ + Ôab/p− ĉaĉb (1 + d2)β − ĉbd · ĉcdβ + Ôbc/p− ĉbĉc (1 + d2)β − ĉbd + ĉaĉc
− ĉad ĉcdβ + Ôbc/p− ĉbĉc
(1 + d2)β − ĉbd − ĉcd ĉadβ + Ôab/p− ĉaĉb (1 + d2)β − ĉbd = Ôac/p.
We can multiply the equation by ((1 + d2)β − ĉbd)2 to get
(1 + d2)(ĉadβ + Ôab/p− ĉaĉb) · (ĉcdβ + Ôbc/p− ĉbĉc) + ĉaĉc(((1 + d2)β − ĉbd)2) −ĉad(ĉcdβ + Ôbc/p− ĉbĉc) · ((1 + d2)β − ĉbd)− ĉcd(ĉadβ + Ôab/p− ĉaĉb) · ((1 + d2)β − ĉbd)
= Ôac/p · ((1 + d2)β − ĉbd)2
⇒ (1 + d2) ( ĉaĉcd 2β2 + (Ôab/p− ĉaĉb)ĉcdβ + (Ôbc/p− ĉbĉc)ĉadβ + (Ôab/p− ĉaĉb)(Ôbc/p− ĉbĉc) )
+ĉaĉc ( (1 + d2)(1 + d2)β2 − ĉbd(1 + d2)β − ĉbd(1 + d2)β + ĉ2bd2 ) −ĉad ( ĉcd(1 + d 2)β2 + (Ôbc/p− ĉbĉc)(1 + d2)β − ĉbĉcd2β − ĉbd(Ôbc/p− ĉbĉc) )
−ĉcd ( ĉad(1 + d 2)β2 + (Ôab/p− ĉaĉb)(1 + d2)β − ĉaĉbd2β − ĉbd(Ôab/p− ĉaĉb) )
= Ôac/p · ( (1 + d2)(1 + d2)β2 − 2ĉbd(1 + d2)β + ĉ2bd2 )
⇒ β2 [ (1 + d2)ĉaĉcd 2 + ĉaĉc(1 + d 2)(1 + d2)− ĉaĉcd2(1 + d2)
−ĉaĉcd2(1 + d2)− Ôac/p · (1 + d2)(1 + d2) ]
+β [ (1 + d2) ( (Ôab/p− ĉaĉb)ĉbd+ (Ôbc/p− ĉbĉc)ĉad ) + ĉaĉc ( − ĉbd(1 + d2)− ĉbd(1 + d2) ) −ĉad ( (Ôbc/p− ĉbĉc)(1 + d2)− ĉbĉcd2 ) − ĉcd ( (Ôab/p− ĉaĉb)(1 + d2)− ĉaĉbd2
) +Ôac/p · ( 2ĉbd(1 + d 2)
)] + [ (1 + d2)(Ôab/p− ĉaĉb)(Ôbc/p− ĉbĉc) + ĉaĉcĉ2bd2
+ĉaĉbd 2(Ôbc/p− ĉbĉc) + ĉbĉcd2(Ôab/p− ĉaĉb)− Ôac/p · ĉ2bd2
] = 0.
The only sources of error are from estimating c’s and O’s.Let c′ denote the error for the c’s. Let O denote the error from O’s. The quadratic formula is β = −b± √ b2−4ac
2a where
a = (1 + d2)ĉaĉcd 2 + ĉaĉc(1 + d 2)(1 + d2)− 2ĉaĉcd2(1 + d2)− Ôac/p · (1 + d2)(1 + d2)
b = (1 + d2) ( (Ôab/p− ĉaĉb)ĉbd+ (Ôbc/p− ĉbĉc)ĉad ) + ĉaĉc ( − 2ĉbd(1 + d2) ) −ĉad ( (Ôbc/p− ĉbĉc)(1 + d2)− ĉbĉcd2 ) − ĉcd ( (Ôab/p− ĉaĉb)(1 + d2)− ĉaĉbd2
) +Ôac/p · ( 2ĉbd(1 + d 2) )
c = (1 + d2)(Ôab/p− ĉaĉb)(Ôbc/p− ĉbĉc) + ĉaĉcĉ2bd2 + ĉaĉbd2(Ôbc/p− ĉbĉc) +ĉbĉcd 2(Ôab/p− ĉaĉb)− Ôac/p · ĉ2bd2.
Let a, b, c denote the error from each term. Then
a = O
( (1 + d2)d2
1− p c′ +
(1 + d2)2
p · O
) ,
b = O
( d(1 + d2) ( O
p(1− p) + c′ p
)) ,
c = O
( (1 + d2) ( O p3 + c′ p3 )) .
Because d is defined with respect to p, if we ignore the dependence on p, we get that
a = b = c = O( c′ + O).
Furthermore, b2 = O( b), ac = O( a + c).
It follows that
β = O
( b + √ a + b + c
2a− a
) +O ( (−b± √ b2 − 4ac) a
a(a− a)
) .
= O( √ c′ + O).
Since O and c are Bernoulli random variables, by Hoeffding’s inequality and union bound, with probability at least 1− δ2 , ci ≤ √ ln(2m/δ) 2n for all i ∈ [m], and with probability at least 1− δ 2 , Oij ≤ √ ln(2(m2 )/δ) 2n for all i, j ∈ [m]. It follows that with probability at least 1− δ, α = γ = . . . = O(( ln(2m 2/δ) 2n ) 1/4).
We can now prove the main theorem in the rankings case.
Corollary 4.1.1. For any δ > 0, U > 0, prior over y1 and y2 with known class probability p, and using Algorithm 1 and Algorithm 3, for all conditionally independent λa, λb, λc, with parameters U > θa, θb, θc > 4 ln(2), we can recover θa, θb, θc up to error O(ρ2(ln(2m2)/(2δn))1/4/|g2(U)|) with probability at least 1− δ, where g2(U) = (−ke−U )/((1− e−U )2) + ∑2 j=1(j 2e−Uj)/((1− e−Uj)2).
Proof. Consider a pair of items (a, b). Without loss of generality, suppose a ≺y1 b and a y2 b. Define αa,b = P (a ≺λa b|y1), α′a,b = P (a λa b|y2) then our estimate for P (λa(a,b) ∼ Y(a,b)) where λ a (a,b) ∼ Y(a,b) denotes the event that label function i ranks (a, b) correctly would be
P̂ (λa(a,b) ∼ Y(a,b)) = pα̂a,b + (1− p)(1− α̂′a,b)
which has errorO( α). Then, note thatE[d(λa, Y )] = ∑ a,b P (λ a (a,b) ∼ Y(a,b)). Therefore, we can compute
the estimate Ê[d(λa, Y )] = ∑ a,b Ê[λi ∼ Y ]a,b which has error O( ( ρ 2 ) ( ln(6)/δ2n ) 1/4).
Recall from (7) we have that
Eθ[D] = d[log(M(t))]
dt
∣∣∣∣ t=−θ ,
where M(t) is the moment generating function, and recall from (8) that
M(t) = 1
k! ∏ j≤k 1− eθj 1− eθ .
It follows that
Eθ[D] = ke−θ 1− e−θ − ∑ j≤k je−θj 1− e−θj (11)
⇒ d dθ Eθ[D] =
−ke−θ (1− e−θ)2 + ∑ j≤k j2e−θj (1− e−θj)2 .
Let gk(θ) = −ke −θ (1−e−θ)2 + ∑ j≤k j2e−θj
(1−e−θj)2 . By the lemma below, gk is non positive and increasing in θ for θ > 0. It follows that by numerically computing the inverse function of (7), our estimate of θ has error O( ρ 2
|g2(U)| ( ln(2m2)/δ 2n ) 1/4).
Lemma E.1. gk is non-positive and increasing in θ for θ > 4 ln(2). Additionally, gk is decreasing in k.
Proof. We first show non-positivity. For this, it is sufficient to show
j2e−θj
(1− e−θj)2 ≤ e
−θ
(1− e−θ)2 . (12)
holds for all 1 ≤ j and θ > 0. This clearly holds for j = 1. Rearranging gives
j2e−θ(j−1) ≤ ( 1− e−θj
1− e−θ
)2 .
The right-hand term is greater than or equal to 1, so it suffices to choose θ such that
j2e−θ(j−1) ≤ 1
⇒ θ ≥ ln(j 2)
j − 1 .
It can be shown that the right-hand term decreases with j for j > 1, so it suffices to take j = 2, which implies θ ≥ 2 ln(2). By choice of θ this is clearly true.
To show that gk is increasing in θ, we consider
d
dθ gk(θ) = ke−θ(1− e−2θ) (1− e−θ)4 + ∑ j≤k j3e−θj(e−2θj − 1) (1− e−θj)4
Similarly, it suffices to show
j3e−θj(1− e−2θj) (1− e−θj)4 ≤ e −θ(1− e−2θ) (1− e−θ)4 .
Rearranging, we have
j3e−θ(j−1) ≤ 1− e −2θ
1− e−2θj
( 1− e−θj
1− e−θ
)4 .
Note that 1− e−2θ
1− e−2θj
( 1− e−θj
1− e−θ
)4 ≥ 1− e −θj
1− e−2θj .
The term on the right is greater than 12 for θ > 0 and j ≥ 1. Therefore, it suffices to choose θ such that
j3e−θ(j−1) ≤ 1 2
⇒ θ ≥ ln(2j 3)
j − 1 .
Once again, the term on the right is decreasing in j, so we can take j = 2, giving θ ≥ 4 ln(2), which is satisfied by our choice of θ.
Finally, the fact that gk is decreasing in k follows from (12).

heading: E.3 EUCLIDEAN EMBEDDING CASE
text: Theorem 4.2. Let Ê[g(λa)g(y)] be an estimate of the accuracies E[g(λa)g(y)] using ê computed from n samples, where all LFs are conditionally independent given Y . If we assume the signs of a are recoverable, then with high probability
E[||Ê[g(λa)g(y)]− E[g(λa)g(y)]||2] = O (( a−10|min| + a −6 |min| )√ max(e5max, e 6 max)/n ) .
Here, a|min| = mini |E[g(λi)g(y)]| and emax = maxj,k ej,k.
Proof. For three conditionally independent label functions λa, λb, λc, our estimate of E[g(λa)g(y)] is
|Ê[g(λa)g(y)]| = ( |êab||êa,c|E[Y 2]
|êb,c|
) 1 2
.
Furthermore, if we define xa,b = |êa,b| |ea,b| , we can write the ratio of elements of â to a as
ka = |Ê[g(λa)g(y)]| |E[g(λa)g(y)]| = ( |êij | |eij | · |êa,c| |ea,c| · |eb,c| |êb,c| ) 1 2 = ( xa,bxa,c xb,c ) 1 2 .
(and the other definitions are symmetric for kb and kb). Now note that because we assume that signs are completely recoverable, |Ê[g(λa)g(y)]− E[g(λa)g(y)]| = ∣∣∣∣|Ê[g(λa)g(y)]| − |E[g(λa)g(y)]|∣∣∣∣.
Next note that
|Ê[g(λa)g(y)]2 − E[g(λa)g(y)]2| = |Ê[g(λa)g(y)]− E[g(λa)g(y)]||Ê[g(λa)g(y)] + E[g(λa)g(y)]|.
By the reverse triangle inequality,
(|Ê[g(λa)g(y)]| − |E[g(λa)g(y)]|)2 =||Ê[g(λa)g(y)]| − |E[g(λa)g(y)]||2
≤ |Ê[g(λa)g(y)]− E[g(λa)g(y)]|2
= ( |Ê[g(λa)g(y)]2 − E[g(λa)g(y)]2| |Ê[g(λa)g(y)] + E[g(λa)g(y)]| )2 ≤ 1 c2 |Ê[g(λa)g(y)]2 − E[g(λa)g(y)]2|2,
where we define c as mina |Ê[g(λa)g(y)]+E[g(λa)g(y)]|. (With high probability c = â|min||+ |a|min|, but there is a chance that Ê[g(λa)g(y)] and E[g(λa)g(y)] have opposite signs.) For ease of notation, suppose
we examine a particular (a, b, c) = (1, 2, 3). Then,
(|E[g(λ1)g(y)]| − |Ê[g(λ1)g(y)]|)2
≤ 1 c2 |Ê[g(λ1)g(y)]2 − E[g(λ1)g(y)]|2 = 1 c2 ∣∣∣∣∣ |ê12||ê13||ê23| − |e12||e13||e23| ∣∣∣∣∣ 2
= 1
c2 ∣∣∣∣∣ |ê12||ê13||ê23| − |ê12||ê13||e23| + |ê12||ê13||e23| − |ê12||e13||e23| + |ê12||e13||e23| − |e12||e13||e23| ∣∣∣∣∣ 2
≤ 1 c2 (∣∣∣ ê12ê13 ê23e23 ∣∣∣||ê23| − |e23||+ ∣∣∣ ê12 e23 ∣∣∣||ê13| − |e13||+ ∣∣∣e13 e23 ∣∣∣||ê12| − |e12||)2 ≤ 1 c2 (∣∣∣ ê12ê13 ê23e23 ∣∣∣|ê23 − e23|+ ∣∣∣ ê12 e23 ∣∣∣|ê13 − e13|+ ∣∣∣e13 e23
∣∣∣|ê12 − e12|)2 . With high probability, all elements of ê and e must be less than emax = maxj,k ej,k. We further know that elements of |e| are at least a2|min|/E[Y
2]. Now suppose (with high probability) that elements of |ê| are at least â2|min| > 0, and define4a,b = êa,b − ea,b. Then,
(|E[g(λ1)g(y)]2| − |E[g(λ1)g(y)]|)2
≤ max(emax, e 2 max)
c2
( 1
a2|min|â 2 |min|E[Y
2]2 |423|+
1
a2|min|E[Y 2] |413|+
1
a2|min|E[Y 2] |412|
)2
≤ max(emax, e 2 max)
c2 (4223 +4213 +4212)
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) .
The original expression is now
|Ê[g(λa)g(y)]− E[g(λa)g(y)]|
≤
( max(emax, e 2 max)
c2
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) (42a,b +42a,c +42b,c) ) 1 2 .
To bound the maximum absolute value between elements of ê and e, note that( 2 ( 42ij +42a,c +42b,c )) 1 2 ≤ ||êa,b,c − ea,b,c||F ,
where ea,b,c is a 3× 3 matrix with ei,j in the (i, j)-th position. Moreover, it is a fact that ||êa,b,c−ea,b,c||F ≤√ r||êa,b,c−ea,b,c||2 ≤ √ 3||êa,b,c−ea,b,c||2 where r is the rank of êa,b,c−ea,b,c. Putting everything together,
|Ê[g(λa)g(y)]− E[g(λa)g(y)]|
≤
( max(emax, e 2 max)
c2
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) · 1
2 ||êa,b,c − ea,b,c||2F
) 1 2
≤
( max(emax, e 2 max)
c2
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) · 3
2 ||êa,b,c − ea,b,c||22
) 1 2
.
Lastly, to compute E[||Ê[g(λa)g(y)] − E[g(λa)g(y)]||2], we use Jensen’s inequality (concave version, due to the square root) and linearity of expectation:
E[|Ê[g(λa)g(y)]− E[g(λa)g(y)]|]
≤
( max(emax, e 2 max)
c2
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) · 3
2 E[||êa,b,c − ea,b,c||22]
) 1 2
.
We use the covariance matrix inequality as described in Tropp (2014), which states that P (||ê− e||2 ≥ γ) ≤ max ( 2e3− nγ σ2C , 2e3− nγ2 σ4C2 ) ,
where σ = maxa eaa and C > 0 is a universal constant.
To get the probability distribution over ||êa,b,c − ea,b,c||22, we just note that P (||êa,b,c − ea,b,c||2 ≥ γ) = P (||ê− e||22 ≥ γ2) to get
P (||êa,b,c − ea,b,c||22 ≥ γ) ≤ 2e3 max ( e− n √ γ σ2C , e− nγ σ4C2 ) .
From this we can integrate to get E[||êa,b,c − ea,b,c||22] = ∫ ∞
0
P (||êa,b,c − ea,b,c||22 ≥ γ)dγ ≤ 2e3 max ( σ4C2
n , 2 σ4C2 n2
) = O( σ4
n ).
Substituting this back in, we get
E[|Ê[g(λa)g(y)]− E[g(λa)g(y)]|]
≤
( max(emax, e 2 max)
(â|min| + a|min|)2
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) ·O ( σ4
n
)) 12
≤
( max(emax, e 2 max)
(â|min| + a|min|)2 ·
( 1
a4|min|â 4 |min|E[Y
2]4 +
2
a4|min|E[Y 2]2
) ·O ( σ4
n
)) 12
≤
( max(emax, e 2 max)
(â|min| + a|min|)2 min(E[Y 2]4, E[Y 2]2) ·
( 1
a4|min|â 4 |min|
+ 2
a4|min|
) ·O ( σ4
n )) 12 with high probability. Finally, we clean up the a|min| and â|min| terms. The terms involving a and â can be rewritten as
1 + 2â4|min|
a6|min|â 4 |min| + 2a 5 |min|â 5 |min| + a 4 |min|â 6 |min|
.
We suppose that â|min|a|min| ∈ [1− , 1 + ] for some > 0 with high probability. Then, this becomes less than
1 + 2â4|min|
(1− )4a10|min| + 2(1− )5a 10 |min| + (1− )6a 10 |min|
≤ 1 + 2â4|min|
4(1− )6a10|min|
= O
( 1
a10|min| +
1
a6|min|
) .
Therefore, with high probability, the sampling error for the accuracy is bounded by
E[||Ê[g(λa)g(y)]− E[g(λa)g(y)]||2] = O ( σ2 ( 1
a10|min| +
1
a6|min|
)√ max(emax, e2max)
n
)
= O
(( 1
a10|min| +
1
a6|min|
)√ max(e5max, e 6 max)
n
) .
Note that if all label functions are conditionally independent, we only need to know the sign of one accuracy to recover the rest. For example, if we know if E[g(λ1)g(y)] is positive or negative, we can use E[g(λ1)g(y)]E[g(λ2)g(y)] = e1,2E[Y 2]2, E[g(λ1)g(y)]E[g(λ3)g(y)] = e1,3E[Y 2]2, . . . , E[g(λ1)g(y)]E[g(λm)g(y)] = e1,mE[Y 2]2 to recover all other signs.

heading: F EXTENDED EXPERIMENTAL DETAILS
text: 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 experiments take from 30 minutes up to a few hours depending on the experiment conditions.
Hyperbolic Space and Geodesic Regression The following is basic background useful for understanding our hyperbolic space models. Hyperbolic space is a 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 metric for the space. Points p in Smooth manifolds M are equipped with a tangent space denoted TpM . The elements (tangent vectors v ∈ TpM ) in this space are used for linear approximations of a function at a point. The shortest paths in a Riemannian manifold are called geodesics. Each tangent vector x ∈ TpM is equivalent to a particular geodesic that takes p to a point q. Specifically, the exponential map is the operation exp : TpM → M that takes p to the point q = expp(v) that the tangent vector v points to. In addition, the length ‖v‖ 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 ∈M , provides the tangent vector v = logp(q). The geodesic regression model is the following. Set some intercept p ∈ M . Scalars xi ∈ R are selected according to some distribution. Without noise, the output points are selected along a geodesic through p parametrized by β: yi = expp(xi × β), where β is the weight vector, a tangent vector in Tp(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 expp(v) as exp(p, v). Then, the noisy y are yi = exp(exp(p, xi×β), εi), where εi ∈ Texp(p,xi)M . This notion generalizes adding zero-mean Gaussian noise to the y’s in conventional linear regression.
The equivalent of least squares estimation is then given by p̂, β̂ = arg minq,α ∑n i=1 d(exp(q, αxi), yi) 2.
Semantic Dependency Parsing We used datasets on Czech and English taken from the Universal Dependencies 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.fictree, cs.pdt, while for English, they were taken from en.gum, en.lines, en.partut, en.ewt. The metric is the standard unlabeled attachment score (UAS) metric used for unlabeled dependency parsing.
Movies dataset processing In order to have access to ample features for learning to rank and regression tasks, we combined IMDb (imd) and TMDb(tmd, 2017) 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 vote average column from TMDb dataset as a target feature. In rankings, we converted the vote average 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 we later included IMDb, Rotten Tomatoes, MovieLens ratings as weak labels in Table 2.
After merging the two datasets, we performed feature engineering as follows.
1. One-hot encoding: color, content rating, original language, genres, status 2. Top (frequency) 0.5% one-hot encoding: plot keywords, keywords, production companies, actors 3. Count: production countries, spoken languages 4. Merge (add) actor 1 facebook likes, actor 2 facebook likes, actor 3 facebook likes into ac-
tor facebook likes 5. Make a binary feature regarding whether the movie’s homepage is missing or not. 6. Transform date into one-hot features such as month, the day of week.
We included the preprocessed dataset in supplementary. By adding features above, we were able to enhance MSE from 0.3626 to 0.2106 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 as the test set. 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.e. 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(Ioffe & Szegedy, 2015) was applied for all hidden layers. We used the SGD optimizer with ListMLE loss (Xia et al., 2008); the learning rate was 0.01.
In the regression experiments, we used gradient boosting regression implemented in sklearn with n estimators=250. Other than n estimators, we used the default hyperparameters of sklearn implementation.
BoardGameGeek data processing In the BoardGameGeek dataset (boa, 2020), we used metadata of board games only. Since this dataset showed enough model performance without additional feature engineering, we used the existing features: yearpublished, minplayers, maxplayers, playingtime, minplaytime, maxplaytime, minage, owned, trading, 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. BoardGameGeek has its own internal equation to determine the ranking of board games. When we used the features above, we obtained a MSE Of 0.2837 in the fully-supervised regression task. 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 λa(i) ∼ 1 Z e −βadτ (π,Yi) with βa. For more realistic heterogeneous LFs, 1/3 (good) LFs βa are sampled from Uniform(0.2, 1), and 2/3 (bad) LFs’ βa are sampled from Uniform(0.001, 0.01). Note that higher value of βa yields less noisy weak labels. In regression, we used the conditional distribution Λ|Y to generate
samples of Λ. Specifically, where Λ|Y ∼ N (µ̄, Σ̄), where µ̄ = ΣΛY Σ−1Y y and Σ̄ = ΣΛ − ΣΛY Σ −1 Y ΣY Λ, from the assumption (Λ, Y ) ∼ N (0,Σ).

heading: G ADDITIONAL SYNTHETIC EXPERIMENTS

heading: G.1 RANKING
text: To check whether our algorithm works well under different conditions, additional experiments were performed with slightly different parameters. Also, we included partial ranking experiment here.
Ranking synthetic data generation First, n true rankings Y are sampled uniformly at random. In the full ranking setup, each LF πi is sampled from the Mallows λa(i) ∼ 1Z e
−βadτ (π,Yi) with parameters βa, Yi and in the partial ranking setup it is sampled from a selective Mallows with parameters βa, Yi, Si where each Si ⊆ [d] is chosen randomly while ensuring that each x ∈ [d] appears in at least p 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 βa ∼ Uniform(0.1, 0.2) and rest have βa ∼ Uniform(2, 5). This was done in order to model LFs of different quality. These LFs are then randomly shuffled so that the order in which they are added is not a factor. For the partial rankings setup we use the same process to get βa and randomly generate Si according to the sparsity parameter p. Keeping the LFs parameters we run the experiments for 5 random trials and observe mean and standard deviations.
Full Ranking Experiments Figure 6 shows synthetic data results without an end model, i.e., just using the inference procedure as an estimate of the label. We report the ‘Unweighted’ Kemeny baseline that ignores differing accuracies. ‘Estimated Weights’ uses our approach, while ‘Optimal Weights’ is based on an oracle with access to the true θa 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 LFs globally improves estimation even when accuracies differ.
Partial Ranking Experiments In the synthetic data partial ranking setup, we vary the value of p (observation probability) from 0.9 (dense) to 0.2 (sparse) and apply our extension of the inference method tp partial rankings. Figure 7 shows the plots 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.

heading: G.2 REGRESSION
text: For regression, we reports a synthetic experiment to show how our algorithm works well by properly estimating parameteres necessary in inference.
Regression synthetic data generation For simplicity, we generated synthetic data with a linear relationship. Denote the data as (X,Y ), where X ∈ Rq and Y ∈ R. The linear relationship is
Y = βTX.
We generate n such samples. Note that we did not add a noise variable ε ∼ N here since we do not directly interact with Y ; the noise exists instead in the labeling functions (i.e., the weak labels).
Parameter estimation in synthetic regression experiments Figure 8 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
as it accesses sufficiently many samples to estimate the label model itself. On the bottom, we observe, as expected, that label estimation significantly improves with access to more labels.

heading: H ADDITIONAL REAL LF EXPERIMENTS AND RESULTS

heading: H.1 RESULT ON REGRESSION
text: In Figure 9, we show the results of end-model performance on the regression setting.

heading: H.2 BOARD GAME GEEK DATASET
text: In the board games dataset, we built labeling functions using simple programs expressing heuristics. For regression, we picked several continuous features and scaled them to the range of 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’].
In this case, we observed that despite not having access to any labels, we can produce performance similar to fully-supervised training on 5-10% of the true labels. We expect that further LF development will produce even better performance, and are working on developing these labeling functions.

heading: H.3 MSLR-WEB10K
text: To illustrate the strength of our approach we were able to run an additional experiment using unsupervised learning methods in information retrieval (such as BM25) as weak supervision sources. The task is information retrieval, the dataset is MSLR-WEB10Kmsl, and the model and training details are identical to our paper’s 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 as covered query term number, covered query term ratio, boolean model, vector space model, LMIR.ABS, LMIR.DIR, LMIR.JM, 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 a better choice than either hand-labeling or using a single source of weak supervision to provide weak labels. Below, for Kendall tau, lower is better.

Review summaries:
This work studies a weakly supervised learning setup of aggregating multiple weak sources of labels into high-quality pseudo labels for learning.   The 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.   Experiments 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.

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.   The 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.