On Learning Latent Models with Multi-Instance Weak Supervision

Summary

The authors define and study the problem of multi-instance partial label learning (PLL), where weak supervision is given in the form of a (potentially) unknown transition function $\sigma$, which maps the ground truth labels onto some label set $S$. Under this problem setting, the paper goes on to show multiple theoretical contributions * 1) Under a known transition function (i.e. SUM2 in the MNIST task), a sufficient and necessary condition for learnability is M-ambiguity. To get faster rates (removing the exponential term of 1/M), they show a stronger condition of 1-ambiguity (or that the output of the transition function given one label perturbation will also be changed). They generalize this to consider a top-k loss that is a more efficient surrogate * 2) They study the setting of learning multiple classifiers with shared label spaces, and provide similar learnability results under analogies of M-ambiguity for multiple classifiers, with an additional assumption on the boundedness of the risk function. * 3) Finally, they provide a similar result for learning a single classifier under an unknown transition function, which requires a new assumption about the transition space being unambiguous and the boundedness of the risk function. The paper also provides experiments to evaluate the quality of existing weakly supervised/neuro-symbolic architectures, which support their theoretical findings and takeaways.

Strengths

The paper provides comprehensive theoretical results for the PLL setting. They provide results for multiple different problem setups, considering known/unknown transition functions and learning a single/multiple classifiers. They provide rigorous theoretical analysis, which requires (in my opinion) rather intuitive assumptions. Relevent experiments are nicely descriptive and verify their theoretical analysis.

Weaknesses

As mentioned in the paper, scalability seems to be an issue with the experimental setting. On what seems to be a not overly complex task (a weighted sum of 4 MNIST digits), performance indeed significantly drops, which calls into question the widespread potential of the PLL setting (and not this paper in particular). While the examples are given that illustrate when the various ambiguity assumptions are violated or not violated, a more in depth discussion in the case of Definition 5 would be appreciated, as this is the most interesting setting of an unknown transition function.

Questions

Are the scalability issues as observed in Table 2 primarily due to the chosen neuro-symbolic methods, the PLL setting, or a combination of both factors?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations are sufficiently addressed.

Summary

This paper studies the questions of learnability and generalization under an interesting form of supervision feedback: namely, when the true label of interest is not observed, but the learner instead has access to the output of a "transition function" $\sigma(y_1, \ldots, y_M)$ computed on the labels of an $M$-tuple of examples. The paper gives necessary and sufficient conditions on the transition function for learnability from two "partial" (evaluated on the aggregate/partial labels) loss functions: partial 0/1 loss and a surrogate for the "semantic loss" studied in other related literature. These results are extended in multiple directions and various details such as convergence rates are also derived.

Strengths

- The results are well presented and the key condition (M-unambiguity) is shown in Appendix E.3 to be a natural extention of the "small ambiguity degree" assumption from Partial Label Learning (PLL) literature. - The authors connect the convergence rate (in terms of sample complexity) of learning to the degree of unambiguity of the transition function. - The results provide a theoretical basis for learning with the top-$k$ approximate _semantic loss_, which was introduced by other work. - The core results are extended in multiple directions, including to the case where there are multiple different classifiers and to the case where the transition function is unknown (under additional assumptions). - Studies and provides a nice set of learnability results for an interesting case of weak supervision that could be practically relevant.

Weaknesses

- Core technical contributions / difficulties are not explained enough (e.g., Lemma 1 seems like key result for Thm 1, and the rest follows from standard tools?) What was the key technical challenge to proving the generalization results, and why is it novel / original? - It's not clear what practical insights are gained from the results. The experiments section seems like a proof of concept---no new method other than the "baselines" is proposed or evaluated based on the theory. The main insight seems to be the qualitative relationship between $M$ and the bound, but $M$ is not really a controllable parameter in practice. - Related to the previous point about the experiments, this setup is missing a compelling application. What's a more realistic practical scenario where learning from this type of supervision is relevant? I.e., where observing $s$ for an $M$-tuple of examples is much more practical than observing $y$ for each example?

Questions

In the Remark starting at L172 the authors suggest a possible connection between the perturbation stability of the transition function and learnability / convergence rate. Could this be connected in any way to the algorithmic stability results (e.g., Bousquet and Ellisseef)? Such a connection might lead to better convergence rates? - Am I correct that the PAC failiure probabilities $\delta$ are w.r.t. the sampling of $\mathcal{D}_P$ (not $\mathcal{D}$)? It might be good to clarify this. A few questions I had while reading the intro/setup, some of which were cleared up later by the main text, but suggest that clarity/flow could be improved: L117 Learnability. What is a "partial learning algorithm"? L138 should be $\sigma_(y,\ldots,y) \ne \sigma(y',\ldots,y')$ ? L182 why do we need to "populate $\sigma$" to compute the zero-one loss? I don't fully follow. In the sum-M case, can't we just sum the outputs predicted by $f(x_i)$ and then compare to $s$? Or is the point that this is problematic if we wanted to use a *surrogate loss* such as cross entropy, so we'd need to form a distribution over the image of $\sigma$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors describe one of the main limitations of their work (the somewhat strict assumptions required on the transition function $\sigma$ due to the worst-case distributions they consider). However, the discussion could be expanded to mention broader limitations, such as the current lack of practical insights to glean from the theoretical results.

Summary

This paper studies a weakly supervised learning scenario where supervision signals are given to sets of instances (instead of individual instances), while the goal is still to predict labels of unseen individuals. For example, the learner is provided with a dataset in which each training example comprises a set of instances $(x_1, x_2)$ (for which the gold labels $y_1 = 1$ and $y_2 = 2$ are unobservable) and an aggregate signal $s=3$ (which is calculated by a known function $s=\sigma(y_1,y_2)=y_1 + y_2$). The authors present learnability results for this scenario under certain assumptions. One main result is that if the function $\sigma$ has *M-unambiguity*, a perfect classifier can be learned as the number of training data approaches infinity. The authors further extend the results to situations where the function $\sigma$ is unknown.

Strengths

- This paper concerns an important problem setting called *multi-instance Partial Label Learning* (multi-instance PLL), which is an extension of the standard Partial Label Learning (PLL) problem. - The authors introduce the notion of "M-unambiguity" and show its utility in proving the learnability of the considered problem scenario under specific assumptions. - The authors further propose the notions of "multi-unambiguity" and "unambiguous transition space" to tackle the scenarios of learning multiple classifiers and unknown transition functions.

Weaknesses

- The theoretical results presented in this submission have limited significance. Generally, learnability means that a hypothesis class is learnable under any data distribution. However, the authors state that they prove learnability under distributions that concentrate mass on a single instance or label. This assumption can be invalidated in the real world. This submission primarily considers a “toughest" distribution that concentrates mass on a single instance, implying all the instances in the training data are the same. Such a distribution is unrealistic in real-world applications. Consequently, positive results under this assumption are not so meaningful. The authors may need to explore more realistic data distributions. - Theoretical aspects of the problem setting, which is called multi-instance Partial Label Learning in this submission, have previously been examined in the literature of weakly supervised learning, as seen in [1]. This setting is known as *learning from aggregate observations*. In [1], the consistency of learners is investigated, and the expected log-likelihood in [1] is close to the semantic loss studied in this submission. To avoid confusion and potential overlap, it is essential for the authors to discuss and elucidate the distinctions between these studies. - The terminology "Multi-Instance Partial-Label Learning" has been used in prior research, such as in [2]. Although [2] examines a different problem setting than this paper, to avoid confusion, it would be beneficial for the authors to adopt a distinct term when referring to the problem setting considered in this submission. - The proof of Lemma 1 appears to be convoluted. Specifically, the first inequality in Equation (26) warrants further clarification. It is not immediately evident why the assertion $R_{P}^{01}(f;\sigma) \ge \sum_{l_i\neq l_j} E_{l_i,l_j}(f)^M$ holds true. In a similar vein, could you explain the first inequality of Eq. (32) in the proof of Lemma 4? Do these Lemma rely only on the M-unambiguous condition? [1] Zhang, Y., Charoenphakdee, N., Wu, Z., & Sugiyama, M. (2020). Learning from aggregate observations. Advances in Neural Information Processing Systems, 33, 7993-8005. [2] Tang, W., Zhang, W., & Zhang, M. L. (2022). Multi-instance partial-label learning: Towards exploiting dual inexact supervision. arXiv preprint arXiv:2212.08997.

Questions

- Is the expected log-likelihood discussed in [1] equivalent to the semantic loss (or the top-k surrogate loss) examined in this submission? - Could you provide a clearer explanation for the proof of Lemma 1, particularly regarding the first inequality in Equation (26)? Could you also elaborate on the first inequality in Equation (32) in the proof of Lemma 4? Is it correct to state that the proofs of these lemmas solely rely on the M-unambiguous condition?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

The limitation of the submission is that it relies on assumptions and conditions, such as a concentration of mass on a single instance or label, which may not align with realistic data distributions and weaken the applicability and persuasiveness of the results.

Summary

The paper connects latent structural learning and neuro-symbolic integration and provides the first theoretical study of multi-instance PLL with possibly an unknown transition. Under such weakly supervision scenario where the transition is deterministic, it defines the necessary and sufficient condition, the minimal distribution assumptions, for the ERM-learnability of the problem. They also derive the Rademacher-style error bounds using the top-k semantics loss. The empirical results support their theory.

Strengths

1. The study provides the first theoretical analysis of multi-instance PLL with possibly an unknown transition, which is a significant contribution to the learning theory community. 2. The theory holds for both known and unknown transition cases, and the assumptions are necessary and sufficient. The experiment results also support the learnability of classifiers and the conclusion that when $M$ gets larger, the learning process gets harder.

Weaknesses

1. The author better move some discussion of the necessity to let the transition function be deterministic to the introduction part to prevent confusion since it seems too strict compared with the commonly used assumption. 2. The empirical results are monotone for the weighted sum transition function, and the authors should add some other empirical results for more known transition function cases.

Questions

1. The scalability in this scenario is poor as Table 2, and it seems to be worse than the error bound given by the theory. Will this happen for the known transition function case? What may be the possible reasons?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The author mentions that scalability may be an important issue. No further negative societal impact raises.

Reviewer response

Thanks for your detailed response! I appreciate the additional discussion on scalability and the importance of the problem setting; I'll keep my score the same and wait to hear responses from other reviewers.