Lifting Weak Supervision To Structured Prediction
Authors: Harit Vishwakarma
Frederic Sala
Venue: NeurIPS 2022 Accept (2022)
Keywords: Weak Supervision
Structured Prediction
Pseudo-Euclidean
Riemannian Manifolds
Learning with Noise

Abstract: Weak supervision (WS) is a rich set of techniques that produce pseudolabels by aggregating easily obtained but potentially noisy label estimates from various sources. WS is theoretically well-understood for binary classification, where simple approaches enable consistent estimation of pseudolabel noise rates. Using this result, it has been shown that downstream models trained on the pseudolabels have generalization guarantees nearly identical to those trained on clean labels. While this is exciting, users often wish to use WS for \emph{structured prediction}, where the output space consists of more than a binary or multi-class label set: e.g. rankings, graphs, manifolds, and more. Do the favorable theoretical properties of WS for binary classification lift to this setting? We answer this question in the affirmative for a wide range of scenarios. For labels taking values in a finite metric space, we introduce techniques new to weak supervision based on pseudo-Euclidean embeddings and tensor decompositions, providing a nearly-consistent noise rate estimator. For labels in constant-curvature Riemannian manifolds, we introduce new invariants that also yield consistent noise rate estimation. In both cases, when using the resulting pseudolabels in concert with a flexible downstream model, we obtain generalization guarantees nearly identical to those for models trained on clean data. Several of our results, which can be viewed as robustness guarantees in structured prediction with noisy labels, may be of independent interest.

Lifting Weak Supervision To Structured Prediction
Harit Vishwakarma hvishvakarm&&wiis... edu
Frederic Sala fredsala@cs wisc.
Department of Computer Sciences,
University of Wisconsin-Madison WI, USA.
Abstract
Weak supervision (WS) is rich of techniques that produce pseudolabels by aggregating easily obtained but potentially noisy label estimates from a variety sources. WS is theoretically well understood for binary classification, where simple approaches enable consistent estimation of pscudolabel noise rates. Using this result, has been shown that downstream models trained on the pseudolabels have generalization guarantees nearly identical to those trained on clean labels. While this is exciting, users often wish use WS for structured prediction, where the output space consists of more than a binary or multi-class label set: e.g. rankings, graphs, manifolds, and more. Do the favorable theoretical properties of WS for binary classification lift to this setting? We answer this question in the affirmative for wide range scenarios. For labels taking values in finite metric space, we introduce techniques new to weak supervision based pseudo- pseudo-Euclidean embeddings and tensor decompositions, providing nearly-consistent noise rate estimator. For labels in constant-curvatur new invariants that also yield consistent noise rate estimation. In both cases, when using the resulting pseudolabels in concert with a flexible downstream model, we obtain generalization guarantees nearly identical to those for models trained on clean data. Several of our results, which can be viewed robustness guarantees in structured prediction with noisy labels, may be of independent interest. Empirical evaluation validates claims and shows the merits of the proposed method"
Riemannian manifolds, we introduce
1 Introduction
Weak supervision (WS) is an array of methods used to construct pseudolabels for training supervised models in label-constrained settings. The standard workflow (RSW+16 RBE+ 18 FCS+ is to assemble set of cheaply-acquired labeling functions-simpe heuristics, small programs, pretrained models, knowledge base lookups- produce multiple noisy estimates of what the true label is for each unlabeled point in training set. These noisy outputs modeled and aggregated into a single higher-quality pseudolabel. Any conventional supervised end model can be trained on these pseudolabels. This pattern has been used to deliver excellent performance in range of domains in both research and industry settings [DRS 20 RNGS20 SLB20) bypassing the need to invest in harge-scale manual labeling. Importantly, these successes are usually found in binary or small-cardinality classification settings.
While exciting, users often wish to use weak supervision in structured prediction (SP) settings, where the output space consists of more than a binary or multiclass label set [BHS+07 KL15). In such cases, there exists meaningful algebraic or geometric structure to exploit. Structured prediction includes, for example, learning rankings used for recommendation systems (KAGI8), regression in metric spaces PM199, learning manifolds [RCMR18), graph-based learning [GS19), and more.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

An important udvantage of WS in the standard setting of binary classification is that it sometimes yields models with nearly the same generalization guarantees their fully-supervised counterparts. Indeed, the penalty for using pseudolabels instead of clean labels is only a multiplicatiie constant. This is highly favorable tradeoff since acquiring more unlabeled data easy. This property leads us to ask the key question for this work: does weak supervision for structured prediction preserve generalization guarantees? We answer this question in the affirmative, justifying the application of WS to settings far from its current use.
Generalization results in WS rely on two steps [RHD*19 FCS I 20] (i) showing that the estimator used to learn the model of the labeling functions is consistent, thus recovering the noise rates for these noisy voters, and (ii) using a noise-aware loss to de-bias end-model training [NDRT13]. Lifting these two results to structured prediction is challenging. The only available weak supervision technique suitable for SP that of [2] It suffers from several limitations. First, it relies on the availability of isometric embeddings of metric spaces into but does not explain how to find these. Second, it does not tackle downstream generalization at all. We resolve these two challenges.
We introduce results for a wide variety of structured prediction problems, requiring only that the labels live in some metric space. We consider both finite and continuous smanifold-valuedd settings. For finite spaces, we apply two tools that are new to weak supervision. The approach we propose combines isometric Greudo-Euclided consistent noise rate estimator. In the continuous case, we introduce a label model suitable for the so-called model spaces-RRiemnaae Riemannian manifolds of constant curvature curvature-along along with extensions to even more general spaces. In both cases, we show generalization results when using the resulting pseudolabels in concert with a flexible end model from [CRR16 RCMR18
embeddings with tensor decompositions resulting resulttnn in nearly-
Contributions:
New techniques for performing weak supervision in finite metric spaces based on isometric pseudo-Euclidean embeddings and tensor decomposition algorithms,
Generalizations to manifold-valued regression in constant-curvature manifolds,
Fimite-sample error bounds for noise rate estimation in each scenario, Generalization error guarantees for training downstream models on pseudolabels. Experiments confirming the theoretical results and showing improvements over (SLV 22
2 Background and Problem Setup
Our goal is to theoretically characterize how well learning with pseudolabels (built with weak supervision techniques) performs in structured prediction. We seek to understand the interplay between the noise in WS sources and the generalization performance of the downstream structured prediction model. We provide brief background and introduce our problem and some useful notation.
2.1 Structured Prediction
Structured prediction (SP) involves predicting labels in spaces with rich structure. Denote the label space by y. Conventionally y is a set, e.g., y= = +1} for binary classification. In the SP setting, ) has some additional algebraic or geometric structure. this work we assume that y is metric space with metric (distance) dy. This covers many types of problems, including
Rankings, where y Sp. the symmetric group on {1, {1....,/l P), i.e., labels permutations, Graphs, where y = Gp. the space of graphs with vertex set V {1.....ph p).
Riemannian manifolds, including y S.. the sphere, or Hig, the hyperboloid.
Learning and Generalization in Structured Prediction In conventional supervised learning we have dataset {(11, ,,),.., (z,, (zny,.)} },)} of i.i.d. samples drawn from distribution p over X' Y As usual, we seek to learn model that generalizes well to points not seen during training. Let F {f X + )) be a family of functions from X' to y. Define the risk R(f) for f E F and f as
R(f) = f JxXy (l v)
f E arg min R(f).
(I)
JeF
2

---

For large class of settings (including all of those we consider in this paper). [CRRI6 RCMR 88 have shown that the estimator is consistent:
F(z, 1 Σ 0s oz(T)
f(x) arg min F(r.y) v) yEy
(2)
where a(x) (K + + Here, K is the kernel matrix for p.d. kernel k X X R. so that K.j = k(,,, xz), (K,)² = k(æ, ky), and y is a regularization parameter. The procedure here is first compute the weights a and then to perform the optimization in (2) to make prediction.
An exciting contribution of [CRRI6 RCMRI8] is the generalization bound
R(f) s R(f*) + ((
that holds with high probability, as long as there is label noise. The key question we tackle is does the use of pseudolabels instead of true labels affect the generalization rate?
2.2 Weak Supervision
In WS, cannot access any of the ground- truth labels yt- Instead observe for each z; the noisy votes A1,i.... Am.i. These are m weak supervision outputs provided by labeling functions (LFs) 8a. where 8a X' - y and Aa, = 8, (an)). two step process is used to construct pseudolabels. First, we learn noise model (also called label model) that determines how reliable each source sa is. That is, we must learn 0 for Pe (A1, ......... .m........ll. -without having access any samples of y. Second, the noise model is used to infer a distribution (or its mode) for each point: Pe Ai........ Am,)).
Am|y)
We adopt the noise model from 2SL which is suitable for our SP setting:
A = y) Z exp
Σ Oa Ba (2a
Σ (a.D)EE
o do)
(3)
are canonical parameters, and E of correlations. The model can be described in terms of the mean parameters Eld? (Xa, y)]- Intuitively, if 0g is large, the typical distance from A to is small and the LF is reliable; if 0, is small, the LF is unreliable. This model is appropriate for several reasons. is an exponential family model with useful theoretical properties. It subsumes popular special cases of noise, including, for regression, zero-mean multivariate Gaussian noise; for permutations, a generalization of the popular Mallows model; for the binary case, it produces close relative of the Ising model.
Z is the normalizing partition function, (0 mm)²
Our goal is to form estimates i in order to construct pseudolabels. One way to build such pseudolabels is to compute i arg mingey 1/m Σm= da (z, Aa). Observe how the estimated parameters A are used to weight the labeling functions, ensuring that more reliable votes receive a larger weight.
We are now a position to state the main research question for this work:
Do there exist estimation approaches yielding Ô that produce pseudolabels ÿ that maintain the same generalization error rate Onni1/4) when used in (2), modified version of (
3 Noise Rate Recovery in Finite Metric Spaces
In the next two sections we handle finite metric spaces. Afterwards we tackle continuous (manifold- valued) spaces. We first discuss learning the noise parameters 9, then the use of pseudolabels.
Roadmap For finite metric spaces with D = r, we apply two tools new to weak supervision. First, embed y into enabling isometric eestance-preserving embeddings for any metric. Using pscudo-Euclidean spaces make our analysis slightly more complex, but gain the isometry property, which is critical.
space [Go185). These spaces generalize Euclidean space,
Second, we form three-way tensors from embeddings of observed labeling functions. Applying tensor product decomposition algorithms [AGH+ 14), we can recover estimates of the mean parameters Eid (Aa. v)] and ultimately 0.. Finally, reweight the model 2 to preserve generalization.

---

Outputs
Pseudo-Euciddenn Embeddinge
Tensor Decompattion
Pacudo-Labed Inforance
Model Training
XXX D RXRR 10 Av in Andlii
10,,
Figure 1: Illustration of our weak supervision pipeline for the finite label space setting.
The intuition behind this approach the following. First, we need technique that can provide consistent or nearly-consisten estimates of the parameters in the noise model. Second, we need to handle any finite metric space. 'eechnquess like the one introduced first-but do not work for generic finite metric spaces, only binary labels and certain sequences. Techniques like the one in [SLV+22 handle any metric space- but only have consistency guarantees in highly restrictive settings (e.g., it requires an isometric embedding, that the distribution over the resulting embeddings is isomorphic to certain distributions, the true label only takes on two values). Iseudo-Euclidens embeddings used with tensor decomposition algorithms meet both requirements
[FCS+20) handle the
3.1 Eseudo-Euclideal Embeddings
Our first task is to embed the metric space into a continuous ppace-enabling easier computation and potential dimensionality reduction. A standard approach is multi--dimensionl scaling (MDS) [KW78), which embeds y into Rd A downside of MDS is that not all metric spaces embed (isometrically) into Euclidean space, as the square distance matrix D must be positive semi-definite.
A simple and elegant way overcome this difficulty is to instead use pveudo-Euclidedd spaces for embeddings. These pseudo-spaces do not require a p.s.d. inner product. As an outcome, any finite metric space can be embedded into gpeudo-Euclidees space with no distortion [Gol85] that distances are exactly preserved. Such spaces have been applied to similarity- learning methods [PPDOT] LRBM06 PHD -6) A vector u in pseudo- Euclidean space Rd*,.f has two parts: ut E Rdd and u E Rdd The dot product and the squared distance between any two vectors u, V are v)o = ( (u y and de (u, v) = I|u - v + - IIlu v 11 These properties enable isometric embeddings: the distance can decomposed into two components that are individually induced from p.s.d. inner products-and can thus be embedded via MDS. Indeed, Seeudo-Fuclidee embeddings effectively run MDS for each component (see Algorithm| [ stees 4-9).
To recover the original distance, we obtain ||u - v+1l and ||u v 112
and subtract.
Example: To see why such embeddings are advantageous, we compare with a one-hot vector representation (whose dimension is [)).. Consider a tree with a root node and three branches, each of which is a path with nodes. Let y be the nodes the tree with the shortest-hops distance as the metric. The pseudo-Euclidean Euclidean embedding dimension is just d = 3; see Appendix for more details. The one-hot embedding dimension is d = | 3t + arbitrarily larger!
Now we are ready to apply these embeddings to our problem. Abusing notation, we write A, and for the sseudo-Euclidenn embeddings of λo y, respectively. We have that (>,, so that there is no loss of information from working with these spaces. In addition, we write the mean as Play = ByAoly] and the covariance as Eg,g- Our goal is to obtain an accurate estimate Pa.y = EB yy], which we will use to estimate the mean parameters (Aa, v)]. If we could observe y, it would be easy to empirically estimate Ma.y Ma.y-but we do not have access to it. Our approach will be to apply tensor decomposition for multi-view mixtures [GG]14.
dz (Aa, y),
3.2 Multi View Mixtures and Tensor Decompositions
In a multi-view mixture model, multiple views { of a latent variable Y are observed. These views are independent when conditioned on Y. We treat the positive and negative components d E Rdt and Do E Rdd of our aseudo-Euclidens embedding as separate multi-view mixtures:
l ~ pt. + ovd+ et
and X ly Ho.y +ovd C Va E [m],
where MT, = E[A yy], MT.y
EAATly and + E are mean zero random vectors with covariances L + respectively. Here 2² is proxy variance whose use is described in Assumption

---

Algorithm Algorithm for Pseudolabel Construction
Input: Labeling function outputs L ((A1,is.... .... Am.i)/=11 Label Space y {.o...... ... 1/--11 Pseudolabels for each data point Z = {
Output:
Step 1:
Compute pseudo-Euclidean Euclidean Embeddings
Construct matrices D R Di, = (3), vú) and M e R M,, 2 (D + Di; D.
2: Compute eigendecomposition of and let M UCUT
3: Set [+ 1 be indices of positive and negative eigenvalues sorted by their magnitude
4: Let d' = |, d = |[|
i.e. the sizes of lists I+ and 1 respectively.
5: Construct permutation matrix perm grx(d +d") by concatenating (+, _ in order
6: C Cl U = UI perm
7: Y UT E R (d++ +d and let this define the mapping g y
Step 2: Parameter Estimation Using Tensor Decomposition 3
8: for 4- 1 to - do
9:
Obtain embeddings Aa,s = g(a,s)) Ao,5 = g(No,)), de, = g(e,.) Vi [x] where a, b,
uncorrelated
10:
Construct tensors T and T- as defined (5) for triplet (a, b,
11:
Payy Plyy P = TensorDeccupositioon
12:
Pay Pbay Pey = TensorDecomposttion((]]
13:
sā. min,,(-1,+1) 6(2 Ma.y''' y*) and similarly si. styy Sa.g So. Sag
14:
Pay = sa. Pag and similarly correct signs م P Peay Hb y Hog
end for
b Step 3: Infer Pscudo-Labels
16: 200 2 MIA (0)
..... Am (8) 0
17: return {
We cannot directly estimate these parameters from observations of X,, due to the fact that y is observed. However, we can observe various moments of the outputs of the LFs such as tensors of outer products of LF triplets. We require that for each a such triplet exists. Then,
T E x
Σ Mylaa 8 phy pty and T DEV.
Σ
A
& 2
X
(5)
Here wy are the mixture probabilities (prior probabilities of Y) and V4 (v wy
0}. We similarly
define T and T-. We then obtain estimates p Pa.y using an algorithm from AAGH 14] with minor modifications to handle pseudo-Euclidee shown in Algorithm We have three key assumptions for our analysis,
rather than Euclidean space. The overall approach
Assumption The support of Py, i.e., = Hy wy > 0H and the label space y is such that min(d ( d
|| 1, 1.I1pTylle
for [m]. V.
Assumption 2. (Bounded angle between and y) Let 6(u, v) denote the angle between any two vectors u, v in a Euclidean space. We assume that df y+) [0, x0, c), Mp y
n0, c) Va [m], and y Ye, for some sufficiently small e E (0, x/4] such that sin(c) > max(eo(dt) ), co )), where co(d) is defined for some nhn samples in (6).
Assumption 3. such that the recovery error with model at least as large as with
These enable providing guarantees recovering the mean vector magnitudes and signs 2 and simplify the analysis 11. (3); all three can be relaxed at the expense of more complex analysis.
Our first theoretical result shows that we have near-consistency in estimating the mean parameters in We use standard notation Ô ignoring logarithmic factors.
3
5

---

Theorem 1. Let Paay Paay be the estimates of Pa Ha.y returned by Algorithm 1 with impur T T constructed using isometric pseudo- pseudo-Euclided Euclidean embeddings (in Bd a ). Suppose Assumptions 1 and 2 are met, a sufficiently large number of samples are drawn from the model in 3.. and k VV.l- Then there exists constant Co > O such that with high probability Vo E [mm] and y E ys.
10a 0al S Co B|d (Au; v) - Bld3 (Aa w)|| S <(( + t(dd),
where
6 (OVA :
+ (
+
o = O
<dd)
(6)
if = +())
We interpret Theorem 1
It is nearly direct application of [AGJ14] There are two noise cases for In the high-noise case, o is independent of dimension d (and thus (2]). Intuitively, this means the average distance balls around each LF begin to overlap the number of points grows-explaine the multiplicative & term. If the noise scales down as we add more embedded points, this problem is removed, as in the low-noise case. In both cases, the second error term comes from using the algorithm of [AGH+14] 14) and is independent of the sampling error. Since = (dd), this term goes down with d. The first error term is due to sampling noise and goes to in the number of samples n. Note the tradeoffs of using the embeddings. If we used one-hot encoding, d = [3%, and in the / /d/n. However, while sampling error is minimized when using a very small d. we pay a cost in the second error term. This leads a tradeoff' in selecting the appropriate embedding dimension.
high-noise case, we would pay very heavy cost for
4 Generalization Error for Structured Prediction in Finite Metric Spaces
We have access to labeling function outputs ... Am,5 for points H; and noise rate estimates 0....., 0m How can we use these to infer unobserved labels y in ? Our approach is based on IDRTTE vRW18 where the underlying loss function is modified deal with noise. Analogously, we modify in such way that the generalization guarantee is nearly preserved.
4.1 Prediction with Pseudolabels
First, construct the posterior distribution Pa = A) We our estimated noise model (A() and the prior P(Y = y). We create pseudo-labels for each data point by drawing random sample from the posterior distribution conditioned on the output of labeling functions:
70 = 2 ~ YI = ( Am = (6) 0. We thus observe (x1, (1), ,.,..... (In, 2n) where & is sampled above. To overcome the effect of noise we create perturbed version of the distance function using the noise rates, generalizing [NDRT13]. This requires us to characterize the noise distribution induced by our inference procedure. In particular we seek the probability that 2 = yj when the true label is yj- This can be expressed as follows. Let ym denote the m-fold Cartesian
product of y and let A,, = (w) ..... (w) denote its th entry. We write
1m
P. Po(ž V = y.) Σ PolY -- AW)) Po(A A vi)-
We define Qu PO(ž y L y1) using Ô. P is the noise distribution induced by the true parameters 0 and Q is an approximation obtained from inference with the estimated parameters
Ô. With this terminology, we can define the perturbed version of the distance function and a corresponding replacement of
dT Ý = vj) = Σ Q (n = = Vys Ey,
(8)
n
F,(x,))
Σ
(n()) 2.)
fo(x) = aarg min Pg (2,
(9)
yEy

---

We similarly define de. Fp. fp using the true noise distribution P. The perturbed distance dp is an unbiased estimator of the true distance. However we do not know the true noise distribution P hence we cannot use it for prediction. Instead we use dg. Note that dg is no longer an unbiased estimator-iit its bias can be expressed as function of the parameter recovery error bound in Theorem |
4.2 Bounding the Generalization Error
What can we say about the excess risk R(f,) )( Note that compared to the prediction based on clean labels, there are additional sources of error. One is the noise in the labels (i.e., even if we know the true P, the quality of the pseudolabels is imperfect). The other is our estimation procedure for the noise distribution. We must address both sources of error.
Our analysis uses the following assumptions on the minimum and maximum singular values F (P) max (P) and the condition number (PP) of true noise matrix P and the function F. Additional detail is provided in the Appendix.
Assumption 4. (Noise model is not arbitrary) The true parameters are such that miin > 0, and the condition number P(P) is sufficiently small.
Assumption 5. (Normalized features) [or(x)] S for all x E E.X.
Assumption 6. (Proxy strong convexity) The function F in (2) satisfies the the following property with
some 3 O. As move away from the minimizer of F, the function increases and the rate of increase is proportional to the distance between the points:
F(z.f(x)) 2 f(x)) + (f)
V.E
(10)
With these assumptions, we provide generalization result for prediction with pseudolabels,
Theorem 2. (Generalization Error ) Let f be the minimizer as defined in Q over the clean labels
and let fg (defined in (9) be the minimizer over the noisy labels obtained from inference Algorithm
Suppose Assumptions 4 6 hold. Then for 62 = 1.5/2 ((c(dt) + c(dd))
(1+
x(P)
and
Tmia (P)
Omin (P) with high probability,
R(A)) R(*)+ 0( 0 -1 ( +
3E2 B
(11)
Implications and Tradeoffs: We interpret each term in the bound. The first term is present even with access the clean labels and hence unavoidable. The second term the additional error we incur if we learn with the knowledge of the true noise distribution. The third term is due to the use of the estimated noise model. dominated by the noise rate recovery result in Theorem third term goes to 0 (perfect recovery) then we obtain the rate On 1/4), the same as in the case of access to clean labels. The third term is introduced by our noise rate recovery algorithm and has two terms: one dominated by 0n22 and the other on ((Vk/d) (see discussion of Theorem 1). Thus we only pay extra additive factor O (VK/dd) in the excess risk when using pseudolabels.
the
Manifold-Valuei Label Spaces: Noise Recovery and Generalization
We introduce simple recovery method for weak supervision in constant-curvature Riemannian manifolds. First we briefly introduce some background notation on these spaces, then provide our estimator and consistency result, then the downstream generalization result. Finally, we discuss extensions to symmetric Riemannian manifolds, an even more general class of spaces.
Background on Riemannian manifolds The following necessarily a very abridged background; more detail can be found in [Le000 Tull]. A smooth manifold M is a space where each point is located in a neighborhood diffeomorphic to Rd Attached to each point p E M is a tangent space TpM;; each such tangent space is d-dimensional vector space enabling the use of calculus.
7

---

A Riemannian manifold equips smooth manifold with Riemannian metric: smoothly-varye inner product :) at each point p. This tool allows us to compute angles, lengths, and ultimately, distances d (p. q) between points on the manifold as shortest-patl distances. These shortest paths are called geodesics and can be parametrized as eurves 7()), where -(0) = p, or by tangent vectors E M, The exponential map operation exp: TpM + -M takes tangent vectors to manifold points. enables switching between these tangent vectors: (xp, = q implies that dP, q) = ||e||. The logarithmic map operation log .M + T,M takes manifold points to tangent vectors. Further, exp,(r) = q is equivalent to log, (q) = v.
Invariant Our first contribution is simple invariant that enables us to recover the error parameters. Note that we cannot rely on the finite metric-space technique, since the manifolds we consider have an infinite number of points. Nor do we need an embedding Instead, we propose a simple idea based on the law of cosines. Essentially, on average, the geodesic triangle formed by the latent variable y E .M and two observed LFs Åas λo, is right triangle. This means it can be characterized by the (Riemannian) version of the Pythagorean theorem:
have continuous representation as-is.
Lemma 1. For y= M, a hyperbolic manifold, y ~ for some distribution on M and labeling functions Àa År drawn from (3). E cosh dy(A,, Ag) = E cosh dy (A6, 2) cosh dy (b. v), while for y = Me a spherical manifold, E cos dy (Xus Ab) = E cos dy()b. y/ cos dy(>b. y).
These invariants enable us to easily learn by forming triplet system. Suppose we construct the equation Lemma for three pairs of labeling functions. The resulting system can be solved to ex- press E[ E[cosh(dy(A) v))] in terms of E cosh cosh(dy(>,, Ag)). E cosh (Na, Ac)), E cosh (As, Ac)). Specifically.
E cosh (A AB cosh dy (Aa, Ac)
Ecosh(dy v))
(E (oosh(d((2) (Ay)A,yAA) A²))
Note that we can estimate È via the empirical versions of terms on the right as these are based on observable quantities. This is generalization of the binary case in (FCS+20) and the Gaussian (Euclidean) case in [SLV+22] to hyperbolic manifolds. A similar estimator can be obtained for spherical manifolds by replacing cosh with cos.
Using this tool, we can obtain a consistent estimator for 0g for each of a = I...., m. Let Co satisfy cosh (Aa, An)) - E cos (Na, As)) 2 Co Ei (Aa, As)) - Edy (A., Ab)1: that is, Co reflects the preservation of concentration when moving from distribution cosh(d) to d². Then,
Theorem 3. Let M be a hyperbolic manifold.
Fix < 8 < 1 and let A65 min, Pr.(vrr (ii, dyy (Na,, do.s) s)) 1 1 Then, there exists constant C1 so that with proba- bility at least 1 - 8, E EE (Aa. v)) - Ed3 (2a, v)1 S C₁ cosh(A(8)) 3/2 //ov
As we hoped, our estimator is consistent. Note that pay a price for tighter bound: ( is large for smaller probability 5. It is possible to estimate the size of A()) (more generally, it is a function the curvature). In addition, it is possible to replace the A66) term by applying version of McDiarmid's inequality for unbounded spaces as in [Kon14].
Next, we adapt the downstream model predictor 2 in the following way. Let 2 = Eid3 (Aa v)]. Let 3 = , 3m0 be such that >n Bo = 1 and / minimizes En S2n2. Then, we set
Σ (x(x)) Σ m yEy n
f(x) arg min
Ld )a.))
We simply replace each of the true labels with a combination of the labeling functions. With this, we can state final result. First, introduce our assumptions.
Let arg min ey ())(()())dd(( (z. y)], where the expectation is taken over the population level distribution and (v) denotes the kernel at y.
Assumption 7. (Bounded Hugging Function c.f. (Str20)) Let g be defined as above. For all a, b E M. the hugging function at q given by kā((a = 1 - (I) log, (a) log,(b)] ly b). We
assume that (a)(a) is lower bounded by kmin-
8

---

N.O.n
20-1
2000 vil 20
-0-
20
1.0
Dut
Ous
3.7
202
600 802
1000
1200
3403
1900
1930
2002
Figure 2: Finite metric space case. Parameter estimation improves with samples n in learning to rank showwng nearly-consistent behavior. Our tensor decomposition estimator outperforms [SLV+22]. In particular, (top left) as number samples increases, our estimates the positive and negative components of T improve. (Top right) the improvements in T recovery with more samples translates to significantly improved performance over [SLV+22), which is close to constant across (Bottom) this improved parameter estimation further translates to improvements in label model accuracy (using only the noisy estimates for prediction, without training an end model) and end model generalization. For the top two plots, use 0 [6, 3, 8]. and in the bottom plot, use [0,0, 0, 1]. In all plots, we report medians along with upper and lower quartiles across trials.
Assumption 8. (Kernel Symmetry) We assume that for all x and all TyM, ((x)(exp,(()) (-v)..
The first condition provides control on how geodesic triangles behave; it relates the curvature, We provide more details on this in the Appendix. The second assumption restricts us to kernels symmetric about the minimizers of the objective Finally, suppose we draw (x, y) and (x', y') independently from Pxy. Set o a(x Edy
Theorem 4. Let M be complete manifold and suppose the assumptions above hold. Then, there exist constants Cz C4 such that,
(lz) Cro + +C4 E + o.)
n kimin )
Note that as n grows, as long as our worst-quality LF has bounded variance, our estimator of the true predictor is consistent. Moreover, we also have favorable dependence the noise rate. This because the only error we incur computing suboptimal 3 coefficients. We comment on this suboptimality in the Appendix.
simple corollary of Theorem 4 provides the generalization guarantees sought,
Corollary 1. Let M be a complete manifold and suppose the assumptions above hold. Then, with high probability, R(f)) < R(f*) + On.
Extensions to Other Manifolds First, we note that all of our approaches almost immediately lift to products of constant-curvatur spaces. For example, we have that Mi x M2 has metric dł (p, q) di,, (pi, 91) drn, (p2, 92), where Pt, qi are the projections of q onto the ith component.

---

107
Aksouue Ereer on
10-1
10-4
Figure 3: Continuous case. Parameter estimation improves with more samples in the hyperbolic regression problem. Our estimator outperforms (SLV+22), Here, we use different randomly sampled values of for each run. We report medians along with upper and lower quartiles across 10 trials.
We can go beyond products of constant-curvatuu spaces as well. To do so, we can build generaliza- tions of the law of cosines (as needed for the invariance in Lemma TT. For example, it is possible to do so for symmetrie Riemannian manifolds using the tools in [AH9]].
Experiments
Finally, we validate our theoretical claims with experimental results demonstrating improved parame- ter recovery and end model generalization using our techniques over that of prior work (SLV (SLV+22) We illustrate both the finite metric space and continuous space cases by targeting rankings (i.e.. permutations) and hyperbolic spaces. In the case of rankings we show that our embeddings with tensor decomposition estimator yields stronger parameter recovery and downstream generalization than [SLV+22). In the case of hyperbolic regression (an example of a Riemannian manifold), we show that our estimator yields improved parameter recovery over [SLY+22]
Finite metric spaces: Learning to rank To experimentally evaluate our tensor decomposition estimator for finite metric spaces, consider the problem of learning rank. We construct synthetic dataset whose ground truth comprises n samples of two distinct rankings among the finite metric space of all length-four permutations. We construct three labeling functions by sampling rankings according to a Mallows model, for which we obtain pseudo-Euclidean embeddings to use with our tensor decomposition estimator.
In Figure (top left), we show that as we increase the number of samples, we can obtain an increasingly accurate estimate of T T-exibittigg the nearly-consistent behavior predicted by theoretical claims. This leads to downstream improvements in parameter estimates, which also become more accurate
increases. In contrast, find that the estimates of the same parameters given by [SLV+22) do not improve substantially as n. increases, and are ultimately worse (see Figure top right), Finally, this leads to improvements in the label model accuracy as compared to that of (2 and translates to improved accuracy of an end model trained using synthetic samples (see Figure bottom).
Hyperbolic regression We similarly evaluate our estimator using syn- thetic labels from a hyperbolic manifold, matching the setting of Section 5 As shown in Figure we find that our estimator consistently outperforms that SLV+22). often by an order of magnitude.
Riemannian manifolds:
7 Conclusion
We studied the theoretical properties of weak supervision applied structured prediction in two general scenarios: label spaces that are finite metric spaces or constant-curvatte manifolds. We introduced ways estimate the noise rates labeling functions, achieving consistency or near- consistency. Using these tools, we established that with suitable modifications downstream structured prediction models maintain generalization guarantees. Future directions include extending these results to more general manifolds and removing some of the assumptions needed in analysis.
10

---

Acknowledgments
We are grateful for the support of the NSF (CCF2106707), the American Family Funding Initiative and the Wisconsin Alumni Research Foundation (WARF). We are thankful to Changho Shin and Harshavardhan Adepu for the discussions and feedback.
References
[AGH* 14] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham Kakade, and Matus Telgarsky, Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15:2773-2832, 2014.
[AGJ14] Animashree Anandkumar, Rong Ge, and Majid Janzamin. Sample complexity analysis for learning overcomplete latent variable models through tensor methods. arXiv preprint 1r0iv:1408.05555 2014.
[AH91] Helmer Aslaksen and Hsueh-Ling Huynh, Laws of trigonometry in symmetric spaces. Geometry from the Pacific Rim, 1991.
[BHS Gükhan H. Bakir, Thomas Hofmann, Bernhard Schölkopf. Alexander J. Smola, Ben Taskar, and S. V. N. Vishwanathan. Predicting Structured Data (Neural Information Processing). The MIT Press, 2007.
[CRR16] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. In Advances in Neural Information Processing Systems 30 (NIPS 2016), volume 30, 2016.
[DRS+20] Jared A. Dunnmon, Alexander J. Ratner, Khaled Saab, Nishith Khandwala, Matthew Markert, Hersh Sagreiya, Roger Goldman, Christopher Lee-Messer, Matthew Lungren, Daniel L. Rubin, and Christopher Ré. Cross-modal data programming enables rapid medical machine learning. Patterns, 1(2), 2020.
[FCS+20) Daniel Y. Fu, Mayee F. Chen, Frederic Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), 2020.
[Gol85] Lev Goldfarb. A new approach to pattern recognition. pages 241-402, 1985.
[GS19] Colin Graber and Alexander Schwing. Graph structured prediction energy networks. In Advances Neural Information Processing Systems 33 (NeurIPS 2019), volume 33, 2019.
[KAGI8] Anna Korba and Florence d' A'Aché-BBuc Alexandre Garcia. structured prediction approach for label ranking. In Advances in Neural Information Processing Systems 32 (NeurIPS 2018), volume 32, 2018.
[KL15] Volodymyr Kuleshov and Percy S Liang. Calibrated structured prediction. In Advances in Neural Information Processing Systems 28 (NIPS 2015), 2015.
[Kon14] Aryeh Kontorovich. Concentration in unbounded metric spaces and algorithmic stability. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Confer- ence on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 28-36, Bejing, China, 22-24 Jun 2014. PMLR.
[KW78] J.B. Kruskal and M. Wish. Multidimensional Scaling. Sage Publications, 1978.
[Lee00] John M. Lee. Introduction to Smooth Manifolds. Springer, 2000.
[LRBM06] Julian Laub, Volker Roth, Joachim M Buhmann, and Klaus-Robed Müller. On the information and representation of non-euclidean pairwise data. Pottern Recognition, 1910011815-1886 2006.

---

[NDRTI3] Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learn- ing with noisy labels. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 1, NIPS' 13, page 1196-1204, 2013.
[PHD+06] Elžbieta Pękalska, Artsiom Harol, Robert P. W. Duin, Barbara Spillmann, and Horst Bunke. Non-euclidean James T. Kwok, Ana Fred, Fabio Roli, and Dick de Ridder, editors, Structural, Syntactic, and Statistical Pattern Recognition, pages 871 871-880, 2006.
mon-metric measures can be informative. In Dit- Yan Yeung,
[PM19] Alexander Petersen and Hans-Georg Müller. Fréchet regression for random objects with euclidean predictors. Annals of Statistics, (7(2):691-719 2019.
[PPD01] Elžbieta Pękalska, Pavel Paclik, and Robert P.W. Duin. A generalized kernel approach to dissimilarity- based classification. Journal of Machine Learning Research, 2:175-21 2001.
[RBE*18] 18] Alexander Ratner, Stephen H. Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christo- pher 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.
(RCMR18) Alessandro Rudi, Carlo Ciliberto, GianMaria Marconi, and Lorenzo Rosasco. Mani- fold structured prediction. In Advances in Neural Information Processing Systems 32 (NeurIPS 2018), volume 32, 2018.
[RHD* 19] A. J. Ratner, B. Hancock, J. Dumnmon, F. 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.
[RNGS20] 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.
[RSW+16] 16] A. Ratner, Christopher M. De Sa, Sen Wu, Daniel Selsam, and C. Ré. Data program- ming: Creating large training sets, quickly. In Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, 2016.
[SLB20] Esteban Safranchik, Shiying Luo, and Stephen Bach. Weakly supervised sequence tag- ging from noisy rules. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 5570-5578, Apr. 2020.
[2] Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Universalizing weak supervision. In International Conference on Learning Representations, 2022.
[Str20] Austin J. Stromme. Wasserstein Barycenters: Statistics and Optimization. MIT, 2020.
[Tul1] Loring W. Tu. An Introduction to Manifolds. Springer, 2011.
[vRW18] Brendan van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18(228): 1-50, 2018.
Checklist
1. Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
2. Did you describe the limitations of your work? [Yes]
3. Did you discuss any potential negative societal impacts of your work? [N/A]
4. Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
5. Did you state the full set of assumptions of all theoretical results? [Yes]
6. Did you include complete proofs of all theoretical results? [Yes] See appendix
12


Reviews:
[{"review_id": "vj0TsTODuD", "reviewer": "Reviewer_tEkM", "summary": "Most prior work on weak supervision with theoretical guarantees has focused on the binary or multi-way classification settings. This paper provides theoretical guarantees for weak supervision in a broader range of label settings like finite metric spaces, for example, rankings (where the label for every data point is an ordering of {1,2,..., k} - if there are k categories, with the Kendall tau metric), and manifold-valued label spaces. In particular, for the case where the labels belong to a finite metric space, they provide an algorithm for pseudo-label construction using pseudo-Euclidean embeddings and tensor decompositions, which they claim are new to weak supervision, and for the case of labels in constant-curvature Riemannian manifolds, they provide an invariant which they then use for noise rate estimation of the labeling functions. Using the pseudo-labels formed by their procedures in down-stream models from prior work [CRR16, RCMR18], they provide generalization error bounds for both these cases.\n\nCRR16 - Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. In Advances in Neural Information Processing Systems 30 (NIPS 2016), volume 30, 2016.\nRCMR18 - Alessandro Rudi, Carlo Ciliberto, GianMaria Marconi, and Lorenzo Rosasco. Manifold structured prediction. In Advances in Neural Information Processing Systems 32 (NeurIPS 2018), volume 32, 2018.", "questions": "The authors claim that tensor decompositions are new to weak-supervision but [SLV+22] mentions “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.” on page 5. I have not read [SLV+22] very carefully but it seems like they were the first to notice that tensor decomposition based approaches can be used for weak supervision.\n", "limitations": "This is primarily a theoretical paper and so the authors have chosen N/A for checklist item 3 [Did you discuss any potential negative societal impacts of your work].", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: I am not an expert in this area so I am not entirely sure about other related work. From what I can read from the paper, it indeed does seem like there is not much prior work on weak supervision for structured prediction, which clearly is an interesting area. The only other paper which they say that has studied WS for structured prediction is a recent ICLR 2022 paper [SLV+22], which seems to lean more on the empirical side.\n\nQuality: The submission is technically sound. All claims are well-supported with proofs.\n\nClarity: The submission is clearly written and well-organized.\n\nSignificance: Yes, the problems being studied are quite significant. Structured prediction settings like rankings are very well studied in the literature and they also seem to have a lot of practical applications so weak-supervision algorithms for them can have a good impact.\n\nSLV+22 - Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Universalizing weak supervision. In International Conference on Learning Representations, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7lG3wa_nhKi", "reviewer": "Reviewer_J1JM", "summary": "This article proposes a weak supervision technique for structured prediction, with labels taking values in finite metric spaces and constant-curvature Riemannian manifolds, and assuming an exponential-family-based probabilistic label model for the weak labels parametrized by the accuracy potentials.\n\nFor finite metric spaces, the authors incorporate structure into the label model by first computing pseudo-Euclidean embeddings of the labels, making use of native distance in the label space.  Similar to [1], a tensor decomposition algorithm is used on the pseudo-embeddings to obtain estimators for the mean parameters of the label model.  Pseudo-labels are created for each data point by sampling from conditional distribution of the latent truth conditional on the output of labeling functions.  The authors then proceed in a similar way to [2], where the label space distance is is a weighted (according to the estimated conditional distribution) aggregation of distances to the weak labels.  The authors derived an upper bound for the parameter recovery error for both high and low noise regimes.  An upper bound for generalization error is also derived and shown to have an extra (compared to the bound in [2]) additive factor which is dependent on the support size of the label space and embedding dimension size.\n\nFor constant-curvature Riemannian manifolds, a generalization of the triplet method (similar to [3,4]) which leverages the law of cosines is proposed, which allows for a closed form estimator for the distance between weak label and latent truth.  This estimator is shown to be consistent. The authors then proceed in a similar to way to [2], where the label space distance is a minimized convex combination of distances to the weak labels.\n\nThe paper focuses on the theoretical aspects of the algorithm, without any experimentation.\n\n[1] Tensor decompositions for learning latent variable models. Anandkumar et al.\n\n[2] A consistent regularization approach for structured prediction. Ciliberto et al.\n\n[3] Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods. Fu, Chen et al.\n\n[4] Evaluating the Crowd with Confidence. Joglekar et al.\n\n", "questions": "1. Why is tensor decomposition ([1]) chosen for parameter estimation? Would other approaches work?  Presumably you would want the method to have guarantees so that you can derive an analog of Theorem 1.\n\n2. Can the authors please comment on/reconcile the differences between the $O(n^{-1/4})$ generalization error proposed to the $O(n^{-1/2})$ in [2]?\n\n3. Can the multi-view mixture model handle correlations between the views?  That might be how the correlation potential can be handled in the probabilistic model.\n\n[1] Tensor decompositions for learning latent variable models. Anandkumar et al.\n\n\n[2] Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods. Fu, Chen et al.\n", "limitations": "Adequately addressed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) Adapting of the guaranteed general approach to structured prediction in [1] to the case of weak supervision is a natural goal.  At a high level, the general approach is simple to understand and does not change very much -- we only need to swap the label space distance term to a weighted combination of the distances to the weak labels. \n2) The design choice of using pseudo-Euclidean embeddings seems to be very appropriate, to accomodate general dissimilarity matrix from general finite metric structured spaces.\n3) Parameter recovery error and generation error bounds seem to be rigorously derived.  The desciption of practical consequences, for example, on Line 186 (\"This leads to tradeoff in selecting the appropriate embedding dimension\") and on Lines 245-246 (\"Thus we see that we only pay an extra additive factor...\"), are highly appreciated.  \n\nWeaknesses:\n\n1) The choice of noise model (Equation 3) seems to exclude correlation potentials, which may limit the scope of practicality.\n2) It is not clear how the bounds presented compare to bounds in prior works for binary/multiclass labels.\n3) It is not clear why tensor decomposition from [4] is chosen for parameter estimation.\n4) Some presentation aspects can be improved:\n- Line 36, it is implied that all WS methods for binary classification yields models with generalization guarantees, but this is not the case. See [2] for other weak supervision methods.\n- Line 106, there should a space in \"small.In\"\n- Line 109, should there be $\\theta_a$ there? The sentence seems awkward.\n- Line 110, \"and $\\theta_a = \\infty$, so that $\\theta_a = y$ seems awkward.\n- Line 143, it may not be clear for readers who are not familiar with pseudo-Euclidean embedding, why the pseudo-Euclidean embedding of the example is 3.  Moreover, I do not think there is enough citation on pseudo-Euclidean embedding and its computation in Algorithm 1.\n- Line 145, it might be clear to write \"embeddings of $\\lambda_{a}, y$ respectively\".\n- In Equation 4, instead of a period, it should be a comma at the end of the line.\n- Line 200, there seems to be something missing after \"where $\\tilde{z}_i$\".\n- Line 243, \"as in the case of access toclean labels\" needs to be fixed.\n- Line 272, \"Note that the finite metric-space case is insufficient: the support is infinite\".  This sentence is hard to understand.\n- Lines 325,326, \"it is possible to do for...\" is ungrammatical.\n- Line 290, I find \"C_0 reflects the pushforward of concentration between the distributions ...\" dubious -- I have never seen \"pushforward\" used for \"concentration\" before.\n- Appendix E, Definition 1. Is this missing \"triangle inequality\" and \"need not be distinguishable\"?\n5. It would have been interesting for weak supervision practitioners to see some experiments to study the empirical performance, perhaps comparing against the approach proposed in [3].   \n\n[1] A consistent regularization approach for structured prediction. Ciliberto et al.\n\n[2] WRENCH: A Comprehensive Benchmark for Weak Supervision. Zhang et al.\n\n[3] Universalizing weak supervision. Shin et al.\n\n[4] Tensor decompositions for learning latent variable models. Anandkumar et al.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3jSEH_2_1gA", "reviewer": "Reviewer_x4kV", "summary": "This paper considers the problem of aggregating noisy labels for learning with structured label set. It proposes methods of first estimate the weights of confidences of each label source, and then learn the hypothesis. Authors provides generalization error bounds for labels sets with different cardinalities. However, no empirical evaluations are presented.", "questions": "- For equation (3), why this model is selected? If it is just adapted from SLV+22, then why this model is selected in SLV+22? How is it favorable than other models, if any?\n- For find the Pseudo-Euclidean embedding space, is it unique? If not, how its selection and how embedding dimension would affect downstream performance? It seems like authors critique on SLV+22 can be applied as it relies on the availablity of pseudo-euclidean embeddings but does not explain how to find these.\n- What are the motivations for introducing multi-view mixtures in Seciton 3.2?\n- In Page 5, Line 160, what are the various moments of the outputs of LFs?\n- What are intuitive reasons for the three assumptions in page 7?\n- Maybe a typo in Algorithm1 Input, should be dots instead of comman in Labeling function outputs?", "limitations": "Authors properly addressed limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The problem setting is an important and general one, and the proposal is original.\n- The writting is overall fine.\n\nWeakness\n- The title is too general. Weak supervision can also mean indirect information about labels. It would be better to emphasis the aggregation aspect of the paper.\n- Motivation is overal not presented clearly. What exactly the proposed method is neccessary for dealing with structured label spaces remains unclear.\n- related work is not enough. Aggregating multiple noisy labels and estimating label source confidence has been explored in fields such as crowdsourcing, at least to an empirical evaluation extent.\n- Without neccessary empirical evaluation results even using synthetic data, it is difficult to judge the overall significance of the proposal.\n- In Page 6, Line 197, Assumption on knowing the prior should be more emphasized. This is a strong assumption as some weakly supversied learning methods heavily depend on it, such as Positive-Unlabeled Learning with Non-Negative Risk Estimator, Kiryo et al., NeurIPS 2017.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept