Learning from weak labelers as constraints

We thank the reviewer for their comments on the paper. Below we would like to address some concerns raised by them.

1. The problem addressed in this paper is certainly interesting, but as the authors themselves mention, it has strong connections to areas like crowdsourcing, noisy label learning, semi-supervised learning, and ensemble learning. Each of these fields already has well-established techniques that could be adapted, with only minor modifications, to solve the problem presented here. However, the paper dismisses these connections too quickly, with phrases like "not directly applicable to our setting" and "relies on the implicit inductive bias." I find this explanation insufficient, as it limits the paper's significance and impact. A deeper exploration of these connections, along with additional comparative experiments, would have been much more convincing.

We did not find these related works to be readily applicable to our setting for various reasons.

In noisy label learning, prior works usually make stringent assumptions about noise. For instance, [1] consider a single noisy label source where noise at any input is assumed to be independent, in particular each label is assumed to be passed through a noisy channel. In our case weak labelers are often in the form of deterministic rules/ classifiers, we cannot make such assumptions about the noise model. Specifically, we cannot assume that the errors of a weak labeler on different data points are independent. In fact the independence assumption is almost always violated, a rule/ classifier is usually smooth over the input space implying that error that is disagreement of weak labeler from target classifier will be highly spatially correlated.

In crowdsourcing, we are usually given multiple weak labels for each input. However, in our setting, we may only have one or very few weak labels for any input, rendering techniques that rely on multiple weak labels from crowdsourcing not applicable.

[1] Natarajan, N., Dhillon, I. S., Ravikumar, P. K., & Tewari, A. (2013). Learning with noisy labels. Advances in neural information processing systems, 26.

2. The authors propose two objectives and frame the problem as a constrained optimization task, introducing corresponding optimization methods. While the paper's main contribution is centered on optimization through projection, I have to admit that I'm not an expert in optimization, this approach feels somewhat intuitive. It doesn't strike me as a particularly novel or non-intuitive solution.

In both of the settings - constraints on classifier and constraints on distribution, we required multiple non trivial steps to reduce the problem into a tractable algorithm. The first step of introducing a lifted variable $q$ and using an alternating minimization procedure of alternating between gradient descent and projection onto constraint sets may look similar to an expectation maximization (EM) style algorithm, but without an efficient projection step such an alternating minimization remains infeasible.

For instance in the case of constraints on classifiers (Section 3.1), the optimizing variable $q$ is continuous whereas the constraints are discrete involving argmax over $y$ of $q(x)_y$ for each $x$. This is not a standard form, and requires a non-trivial observation of reducing it to an optimization on a discrete variable $\text{clf}(q)$ (Proposition 3.5) which then results in a standard ILP. Given $\text{clf}(q)$, then estimating the continuous $q$ (as described in Appendix D.2) in an efficient manner was also not trivial. For the case of constraints on distribution (Section 3.2), the proposition 3.7 and subsequent development of an efficient and scalable algorithm also requires multiple non trivial steps.

3. Additionally, regarding the problem setup and experiments, I would like to see more details about the coverage rate and noisy rate of each weak labeler and the collective coverage of all labelers. This seems crucial to the model’s performance and yet isn’t discussed in enough detail.

We have provided the number of classes, number of weak labelers and their average error and coverage in Table 2 in Appendix G in the revised version.

We thank the reviewer for providing critical feedback on the paper. We addresses the weaknesses and questions asked by the reviewer as follows:

1. The model relies on accurate estimates of weak labelers’ error bounds to define constraints. However, obtaining these estimates is challenging, and inaccurate bounds could lead to suboptimal model performance. In the experiments these are estimated using validation data, which could also be hard to obtain. In contrast several baselines in weak supervision (those based on generative modeling) estimate 'labelers quality' using only the unlabeled samples.

Our method is quite robust and works even when the provided error bounds are noisy. This is evident in Figure 2, where we added uniform random noise to the true error rates of each weak labeler to create error bounds, and observed that its performance only decreases slowly as the noise level is increased. The validation set we used to estimate the error bounds in our main experiments was also quite small (only 100 data points), which is not not sufficient to train a good model, as demonstrated in the Sup(V) baseline. In addition, the estimated error are quite noisy compared to the true errors. On the other hand, other baselines also require this validation data for hyperparameter selection and for early stopping to avoid overfitting.

2. Assumptions made on the weak labelers are not clear. In particular, what are the assumptions that the labelers have to satisfy to ensure the method will work as expected and the theoretical results will hold. Naively putting an upper bound of ηj on each labeler could lead to several scenarios e.g. all could have ηj error in different parts of the input space (independence) or highly overlapping parts (highly correlated). Could you explain how the method and results will turn out in these two extremes?

Contrary to prior work, we do not assume any assumptions on the weak labelers, they can be completely arbitrary and unrelated to each other. Our theoretical results hold as long as the error bound is an upper bound of the true error of each weak labeler since this ensures that the target function satisfies our constraints. Our method however involves relaxing the constrained estimator with an unconstrained one (equation 8) that trades off satisfying constraints and minimizing regularization term. Thus, even if the given error bounds are inaccurate and noisy or less than the true error rates, our algorithm can still work reasonably well as shown in Figure 2.

In the below tables, we show results for the two extremes 1) where we used a subset of weak labelers that are disjoint from each other to simulate error in different parts of input space (independence), 2) we duplicated a weak labeler to simulate the case of labelers being highly correlated.

Scenario 1 : 50% weak labelers are chosen that are as disjoint as possible from each other (determined by a heuristic algorithm.) The following table shows the mean and max IOU (intersection over union) between the coverage sets of pairs of weak labelers in in percentage for the original weak labelers (normal) and the filtered set (disjoint).

Below table shows the results for this case.

Scenario 2: For each dataset, the highest coverage weak labeler with accuracy less than the median accuracy is duplicated 2 * m times where m is the number of weak labelers.

Our method continues to perform better for most datasets in both of these scenarios.

3. Theoretical results do not explain how learning in the proposed setup leads to a classifier with good generalization error. It naively depends on the summation of errors of individual labelers. On the other hand several of the baselines provide results showing how the labelers cancel their noises and eventually lead to a classifier with comparable generalization error to a model trained on clean labels. They do make certain assumptions on labelers to get there. What can be said more specifically in this setup with similar assumptions? Even a naive majority vote with labelers with random noise of ηj could be shown to give good generalization error going down with the number of samples and the number of weak labelers.

We believe our theoretical results do provide insights into how our proposed setup can lead to a classifier with good generalization error beyond naive summation of errors of individual labelers. We presented an argument based on the agreement region (Figure 1); where one can intuitively understand how multiple weak labeler constraints can provide a denoising effect. Further we also provided a bound based on conflict between different weak labelers (Theorem 4.5). The theorem provides a bound which is smaller than simply summing the weak labeler errors by considering the effect of conflicting regions. We also show that a classifier with low error on the coverage set also has low error across the entire space, assuming that the underlying probability distribution is smooth (Theorem 4.6). To this end, our first two results suggest that weak labeler constraints have a denoising effect leading to a low error in the coverage set and the final result suggest that we would have a low error on the whole space as well.

While noise assumption can lead to a better generalization in alternative approaches (e.g. majority vote), this has no impact on our error bound since our proposed method does nott rely on any additional assumption on the weak labeler noise rather than the bound on the error of each weak labelers. We see this a strength rather than a weakness since this implies that our method is more general and more robust to the setting when the noise assumption does not hold.

4. I do not find the empirical results convincing. Ours(C) and Ours(V) rely on either hand tuning ηj or estimating from validation data. Did you estimate source quality in other WS setups using the same validation data?

In Ours(C), we set $\eta_j$ to be a constant value $\eta$ for all weak labelers then we pick the $\eta$ that has the best validation accuracy. In Ours(V), we estimate $eta_j$ using the label from the validation set. Other WS baselines do not have a mechanism to use validation sets to estimate the source accuracy, for instance the method used by Snorkel and Majority vote are based on aggregating weak labels from different weak labelers. However these methods still use validation set for hyperparameter selection and for early stopping when training on the soft-labels. Therefore we think that the comparison is still fair.

5. Can you provide some simulations with different ηj and labeling sources outputs, clearly showing how the method works in different scenarios?

In Figure 2, we provided an ablation where we added a uniform random noise to ηj. It shows that our method is quite robust to misspecified ηj. In response to the point 2 above, we provided results for the two more scenarios, 1) where we used a subset of weak labelers that are disjoint from each other 2) we duplicated a weak labeler many times. In both of these scenarios it can be seen that our method performs better than the baselines.

C1: There are several other weak supervision baselines better than Snorkel

We want to highlight that the main contribution of our paper is to provide a novel, simple and principled method of learning from weak labelers by incorporating information about their average errors and avoiding making modeling assumptions about them. Our method is thus qualitatively different from any prior work in this area.

The purpose of experiments was to validate our approach and provide a sanity-check that it performs at least competitively compared to prior approaches. The choice of our baselines covers two broad approaches - one that first infer pseudo labels using weak labels and then subsequently train a downstream model (Snorkel, Majority vote), and another - that trains an end to end model (LoL). There are several other methods in the prior work but many of them require many hyperparameters, or are limited to binary classification settings, or require auxiliary sources of information, such as dependency graphs between weak labelers. For instance, the popular triplet method [1] was only proposed for binary classification. Here, we provide an additional comparison of [1] vs ours on datasets with 2 classes

[1] Daniel Y. Fu, Mayee F. Chen, Frederic Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré. 2020. Fast and three-rious: speeding up weak supervision with triplet methods. In Proceedings of the 37th International Conference on Machine Learning (ICML'20), Vol. 119. JMLR.org, Article 307, 3280–3291.

C2: I am still not convinced of the value of the theoretical results either.

We believe our proposed method and the corresponding theoretical analysis offer meaningful contributions, as they address a novel setting for learning from weak labelers—a perspective highlighted as valuable by reviewers (jPxa, NPc4, X6nV). We are more than willing to provide additional clarification or further elaboration on our theoretical contributions if that would be helpful.

C5: What's the trade-off between coverage, noise levels, and number of labelers?

We would like to point out that in our framework, there is no trade-off between the coverage, the noise levels (average errors) and the number of weak labelers since we treat each weak labeler as an individual constraint. On the impact of these factors to the final error bound, our theoretical results suggested that

1. As the noise level (average error) is small, we would have a better error bound (Theorem 4.5).
2. As there are more weak labelers, denoising effect among them can also lead to a better error bound (Lemma 4.3, Theorem 4.5).
3. As the weak labeler has more coverage, the full instance space must be closer to the coverage set and this also leads to a better error bound (Theorem 4.6).

On the empirical side, we have provided 3 additional experiments to investigate what happen when 1) weak labelers have disjoint coverages, 2) duplicated weak labelers, 3) additional experiments when we add a fixed noise to the true error rates. We hope that these additional results help clarify your concerns.

By noise levels if they mean noise in the error bounds, as we showed in Figure 2 and the additional experiment, our method is robust to a certain level of noise especially if the provided error is an underestimate, but at some point the performance will start to break down if the error bounds are too relaxed.

C3: The details of the experimental protocol are not given

For our main results in Table 1, we provided details in our main text in section “Experiment Details”. To repeat, for all methods, we used a two-layer neural network of hidden size 16 on pre-trained BERT embeddings and trained it on full batch gradient descent for 500 epochs using Adam optimizer. We used a validation set of size 100 for hyperparameter tuning. Two hyperparameters were used: learning rate in [0.01, 0.003, 0.001] and weight decay (L2 regularization) in [0.01, 0.003, 0.001].

For experiments on noisy bounds (Figure 2), we used the exact same setup, except we add random noise on the true bounds sampled from a uniform distribution.

For the additional experiments on simulating different scenarios for weak labelers as requested by the reviewer, we used the exact same setup for training except we filtered or duplicated the weak labelers as described in our earlier response.

C4: It is not clear why in Figure 2 there is no effect due to noise, at some point (level of noise) things will start to break down.

We want to clarify a misunderstanding here. In Figure 2, we can see that as the noise level increases, the accuracies do decrease across all datasets. Although for some datasets the reduction is minor. Since we added noise sampled uniformly between $[-a, a]$ where $a$ ranged till $0.5$, the error bounds on average are still informative, and so it is possible that performance is not reduced much for some datasets. We see this as a strength as it speaks to the robustness of our method. Here we provide another experiment by adding a fixed noise to the true $\eta$ for every weak labeler. One can clearly see a clear trend that performance decreases as noise is increased. When noise is positive there is a clear trend of performance being reduced as the corresponding constraints are relaxed. When the noise is negative, sometimes the performance is unaffected (CDR, Chemprot, IMDB, Youtube) because the constraints are tightened and since our loss trades off between satisfying the constraints and minimizing the L2 regularization, it may still find a good classifier.

The numbers show mean +- standard deviation across 5 random train - val splits of the data. We trained using Adam optimizer for $500$ epochs using a fixed learning rate of $0.01$ and tuned L2 weight decay in $[0.001, 0.003, 0.01]$.

We thank the reviewer for the their positive comments on the paper. We addressed the missing references ?? in the appendix in the revised version of the paper. We also incorporated suggestions on the plot.

As asked by the reviewer we did another experiment with L1 regularization and provide the results below.

In both columns we use either L1 regularization or L2 regularization weight in [0.001, 0.003, 0.01] as a hyperarameter and use the one that achieves the best validation accuracy. L2 regularization performs a few points better than L1 regularization for most datasets.

We thank the reviewer for their positive comment on the paper. We address the mentioned weaknesses:

1. The paper misses a conclusion and future extensions paragraph

Thank you for pointing it out, we added a conclusion and future extension paragraph in the uploaded revised version.

2. On some datasets, the margin of the proposed methods and competing methods are small. Would it be helpful to run some statistical tests to compare their performances?

We agree that statistical tests would provide a more rigorous basis for comparison. Nevertheless, we remark that with our current result, the proposed method doesn’t significantly underperform any baseline, while performing significantly better than all on some datasets. In our results table, we also bolded methods that are within a standard error of the best-performing method.