On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning

Authors: Kaifu Wang, Efthymia Tsamoura, Dan Roth
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: muliti-instance partial label learning, weakly-supervised learning, neurosymbolic learning, learning theory, long-tailed learning, learning imbalances, class-specific error bounds

Abstract:
\textit{Multi-Instance Partial Label Learning} (MI-PLL) is a weakly-supervised learning setting encompassing \textit{partial label learning}, \textit{latent structural learning}, and \textit{neurosymbolic learning}. Unlike supervised learning, in MI-PLL, the inputs to the classifiers at training-time are tuples of instances $\mathbf{x}$. At the same time, the supervision signal is generated by a function $\sigma$ over the (hidden) gold labels of $\mathbf{x}$. In this work, we make multiple contributions towards addressing a problem that hasn’t been studied so far in the context of MI-PLL: that of characterizing and mitigating \textit{learning imbalances}, i.e., major differences in the errors occurring when classifying instances of different classes (aka \emph{class-specific risks}). In terms of theory, we derive class-specific risk bounds for MI-PLL, while making minimal assumptions. Our theory reveals a unique phenomenon: that $\sigma$ can greatly impact learning imbalances. This result is in sharp contrast with previous research on supervised and weakly-supervised learning, which only studies learning imbalances under the prism of data imbalances. On the practical side, we introduce a technique for estimating the marginal of the hidden labels using only MI-PLL data. Then, we introduce algorithms that mitigate imbalances at training- and testing-time, by treating the marginal of the hidden labels as a constraint. We demonstrate the effectiveness of our techniques using strong baselines from neurosymbolic and long-tail learning, suggesting performance improvements of up to 14\%.

Decision: reject
Reviewer scores: 6, 5, 3, 6

Reviews and discussion:
<thread>
creation date:
1730176209289

thread_type:
official_review

<thread_object>
creator: reviewer_qvdr

<content>
summary:
This paper explores a weakly-supervised learning framework that integrates aspects of partial label learning and partial label learning. It presents theoretical contributions by establishing class-specific risk bounds under minimal assumptions and demonstrating the significant impact of transition functions on learning imbalances. Additionally, the paper introduces practical algorithms for estimating hidden label distributions and mitigating learning imbalances at both training and testing phases, achieving performance improvements of up to 14% over strong baselines.

strengths:
1. This is an theoritically-solid paper - the proofs and theorems appears to be correct and sound.

2. This paper have proposes several notable and interesting theoritical properties, which could be benefical for the future development of MI-PLL.

3. This paper introduces two new algorithms to mitigate imbalances at training and inference time.

4. The proposed method obtained competitive performances comparing with its closest counterparts.

weaknesses:
1. This paper becomes challenging to comprehend as the authors have not provided clear definitions of a partial label. Specifically, by examining Example 1.1 alone, the authors' characterization of partial labeling seems to differ from existing work [1].

2. It appears that the authors' proposed method is somewhat orthogonal to their theoretical results, suggesting a divergence between practice and theory.

3. While it is reasonable to assume that imbalances in Multi-Instance Partial Label Learning (MI-PLL) arise not only from label distribution but also from the partial labeling process, the theoretical results of this paper seem to only consider the imbalances caused by partial labeling. This limitation potentially restricts the flexibility and applicability of the theoretical findings.

[1] Learning from Partial Labels, JMLR 2011.

questions:
1. Is Equation 1 introduced by the authors or derived from previous works? I find the mathematical connections a bit challenging to grasp, particularly as it doesn’t seem to directly correspond to the definition of partial risk outlined by Cour et al. If this is an original contribution from your team, shouldn’t Equation 1 be presented as a lemma with accompanying proofs to substantiate its validity?

2. I'm not completely certain, but it appears that Proposition 3.3 suggests the dependency of the empirical partial risk on the imbalance of partial labels, while your measure of complexity (e.g., the Natarajan dimension) remains unaffected by the level of imbalance. If this interpretation is accurate, does this imply that minimizing the partial risk is invariably advantageous in imbalanced MI-PLL scenarios, regardless of the extent of imbalance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730293257039

thread_type:
official_review

<thread_object>
creator: reviewer_98rq

<content>
summary:
This paper addresses the problem of learning imbalances in Multi-Instance Partial Label Learning (MI-PLL), where the true labels are hidden and supervision is provided via a transition function. The authors derive theoretical bounds for class-specific risks, and propose methods to estimate hidden label distributions and introduce algorithms to mitigate these imbalances during both training and testing.

strengths:
1. The paper provides a theoretical contribution by analyzing learning imbalances in MI-PLL, offering a deeper understanding of the problem.

2. The authors introduce novel algorithms for both training and testing phases, with empirical evidence.

weaknesses:
1. The notation used in this paper is quite convoluted and makes it really hard to follow. I spent a lot of time carefully reading Section 2, but I still don’t have a clear understanding of what exactly the MI-PLL setting is or how it’s supposed to be used in practice.I would recommend reconsidering whether certain notations, e.g., $r_y = r_{l_j} = r_j$ , are essential in the manuscript. Additionally, including a notation table may be helpful for readers to quickly reference symbols, which would enhance the overall clarity and accessibility of the paper.

2. I understand that the setup in this paper seems different from previous work called MI-PLL, but the motivation of this pape is that earlier "MI-PLL" (which has a different meaning than this paper) methods cannot handling the long-tail issue well. What’s puzzling is that it doesn’t actually compare the proposed approaches to those prior MI-PLL methods in the experiments, which feels really inconsistent.

3. From the algorithmic side, I’m left wondering why the proposed methods should work for long-tail distributions. The explanation for how they handle rare classes is pretty vague, and it’s not easy to see how the approach directly addresses the long-tail problem. And the assumption that transition function is known to the learner is too strong. As far as I know, in weakly supervised learning people generally don't make such strong assumption, but it is crucial to learn the function。

questions:
Please see above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730584032904

thread_type:
official_review

<thread_object>
creator: reviewer_khyb

<content>
summary:
In the multi-Instance partial label learning problem, the authors provide class-specific error bounds and show that the transition function $\simga$ can significantly impact learning imbalances. On the practical side, we first propose a statistically consistent technique for estimating the marginal of the hidden labels given partial labels. They propose two algorithms that mitigate imbalances at training- and testing-time. The first algorithm assigns pseudo-labels to training data based on a novel linear programming formulation of MI-PLL. The second algorithm uses the hidden label marginals to constrain the model’s prediction on testing data

strengths:
1. They derive class-specific error bounds that depend on the MI-PLL risk under minimal assumptions.
2. They introduce an algorithm to estimate the marginal of the hidden labels.
3. They mitigate learning imbalances at testing-time by modifying the model’s scores to adhere to the estimated ratios.

weaknesses:
1. The presentation about the algorithm in Section 4.2 becomes confusing from line 300. I will list my doubts in the questions below.
2. Can you explain why you enforce the first three constraints in Equ. (6)?
3. In experiments, for $\rho = 0$, i.e., the hidden label distribution is unmodified and balanced, the performance of CAROT is even worse than LA under $M=5$.
4. Figure 1 seems to indicate that within 100 epochs, almost all classes are not well classified. Does the model converge in 100 epochs? If not, can you provide the curve after 100 epochs until the network converges?

questions:
a).	In line 301, why is each training sample uniquely associated with a Boolean formula of $R_{\ell}$ disjuncts of the form $\Phi_{\ell} := \psi_{\ell, 1} \vee \ldots \vee \psi_{\ell, R_n}$? Is each $\psi_{i, t}$ a bool variable or a function? How to determine $R_{\ell}$. 

b).	In line 302, why it is that “Formula $\Phi_{\ell}$ encodes the valid label assignments for the $\ell$-th partial training sample subject to $\sigma$ and $s_{\ell}$?

c).	Can you show that “Each disjunct in $\Phi_{\ell}$ is a conjunction of Boolean variables from $\\{ q\_{\ell,i,j} \\}\_{i,j}$, where $q_{\ell,i,j}$ is true if and only if $x_{\ell, i}$ is assigned to the $j$-th label in $\mathcal{Y}$”.

d)    The introduction of $\alpha_{\ell, t}$ is also not easy-to-follow.

e)   Exact definition of $\Phi_{\sigma}$ in Section 4.1 is missing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730683018921

thread_type:
official_review

<thread_object>
creator: reviewer_9ewx

<content>
summary:
This paper addresses Multi-Instance Partial Label Learning (MI-PLL). The primary contributions are :  1. a theoretical characterization of class-specific learning imbalances in MI-PLL; 2. practical algorithms for mitigating these imbalances at training and testing stages.

strengths:
The exploration of class-specific risk in MI-PLL settings is a novel angel. The theory is sound and robust. The proposed algorithms lead to empirical improvements.

weaknesses:
I'm a bit concerned on the assumption that the transition $\sigma$ is instance-independent. I'm not sure how consistent it is with the real-world datasets. I think recent literatures on learning with noise and domain changes assume instance-dependent transitions (e.g. https://www.arxiv.org/pdf/2408.16189).

questions:
How hard is it to generalize the theory to allow transition $\sigma$ to be instance-dependent and how will that change the analysis? I think the proofs in Patrini et al., 2017 can be naturally adapted to instance-dependent noise by letting noise transitions $T$ depend on $x$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732210303751

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to sincerely thank the reviewers for their constructive feedback and valuable suggestions, which have helped us improve the quality of our manuscript.

In our responses below, we have carefully answered all the questions and weaknesses that are raised by the reviewers. To better address those concerns, we have also uploaded a **revised version of our manuscript** accordingly, with all changes clearly marked in ${\color{red} \textbf{red color}}$ for ease of reference.

The changes in the revised version include:
- Simplified notations, with a comprehensive notation table in Table 7&8.
- Additional explanation to the construction of Equation (1)
- Additional explanation to CAROT and the function $\Psi_\sigma$ (Section 4.1)
- Additional explanation to the training-time imbalance mitigation algorithm (Section 4.2) and the derivation of the linear programs with examples (in Appendix D.2)
- Explanation of why we consider semantic loss and Scallop, in Appendix F
- Additional plots of experiment results to demonstrate the benefits of considering the label priors, in Figure 8

Thank you for your time and consideration!
</content>
</thread_object>

</thread>
<thread>
creation date:
1733288803231

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Reviewer's Questions and Our Responses (as of 12/03)

comment:
Dear Reviewers and ACs,
 
We want to summarize our responses to the reviewers’ main comments, along with the updates we have incorporated into our revised submission:
 
-    **Regarding extending MI-PLL and our theoretical analysis to instance-dependent transitions (Reviewer 9Ewx)**, we showed that is possible, providing also a concrete example to ground the discussion.
 
-    **About comparing against other neurosymbolic baselines (Reviewer 98Rq)**, we considered the Scallop engine by (Huang et al., 2021), as it is the only one that can scale to our scenarios in Section 5 and Appendix F. Previous work already demonstrated that other neurosymbolic engines scale poorly to large scenarios as ours (Tsamoura et al., 2021; Wang et al., 2023b). We included this discussion in Appendix F in our revised manuscript.  
 
-   **Regarding why our techniques handle long-tail distributions (Reviewers 98Rq and QVdr)**, lines 243—246 in our original submission describe the intuition: enforcing the class priors gives more importance to the minority classes at training time (as ILP does in Section 4.2) and encourages $f$ to predict minority classes at testing time (as CAROT does in Section 4.3). Furthermore, our experiments in Section 5 show that our imbalance mitigation techniques improve over the baselines by up to 14\%. Finally, Figure 8 clearly shows the effects of our imbalance mitigation techniques over the baselines in our experimental scenarios.
 
-  **About the comment that our assumption that the transition function is known is too strong (Reviewer 98Rq)**, this assumption is common in the literature of weakly supervised learning and partial label learning (Raghunathan et al., 2016) and (van Rooyen and Williamson et al., 2018). Furthermore, this assumption is also made in neurosymbolic learning (Manhaeve et al., 2018; Wang et al., 2019b; Dai et al., 2019; Tsamoura et al., 2021; Huang et al., 2021; Li et al., 2023a).
 
-   **Regarding applications of MI-PLL (Reviewer QVdr)**, our introduction provides multiple references and application scenarios, e.g., visual question answering and fine-tuning language models. Further, MI-PLL encompasses partial label learning (Cour et al., 2011; Cabannes et al., 2020) and latent structural learning (Steinhardt \& Liang, 2015; Raghunathan et al., 2016).
 
-   **Regarding the utility of our theoretical results (Reviewer QVdr)**, our results suggest a phenomenon nobody else has observed in the relevant literature -- that learning in MI-PLL is inherently imbalanced -- and motivated us to develop new techniques for imbalance-aware learning. Our error bounds also extend previous relevant results (Cour et al., 2011; Wang et al., 2023b).
 
-   **About the comment that existing techniques for addressing long-tailed learning could be applicable in MI-PLL (Reviewer QVdr)**, we discuss in lines 076—083, lines 287—294, Appendix D, and Appendix E of our original submission why it is not straightforward to apply existing long-tail learning techniques to MI-PLL. For example, about mitigating imbalances at training time, differently for existing techniques in supervised and semi-supervised learning, in MI-PLL (1) training samples are $M$-ary tuples of instances of the form ${(x_1,\dots,x_M)}$ and (2) the predictions must abide by the constraints coming from $\sigma$. In addition, there was no previous technique for estimating the marginal of the hidden labels $\mathbf{r}$ from MI-PLL training samples (we are the first to provide such a theoretically grounded technique in Section 4.1). Lastly, **our experiments in Section 5 and Appendix F show that a straightforward application of state-of-the-art techniques to MI-PLL may harm the accuracy of the baseline model.**  
 
-   **Regarding our linear program formulation in Section 4.2 and our notation in Section 4.1 (Reviewer KhYb)**, we rewrote Sections 4.1, 4.2, and Appendix D to address these questions, giving in Appendix D an example of our linear program formulation.
 
-   **About providing a notation table and simplifying our notation (Reviewers 98Rq and KhYb)**, we addressed both comments in our revised paper and added detailed notation tables (Tables 7 and 8) for clarity.
 
-   **Regarding the accuracies reported in our experimental results (Reviewer KhYb)**, Tables 1--6 show balanced accuracies, i.e., the reported numbers are the weighted sums of the class-specific accuracies, where each class-specific accuracy is weighted by the frequency of occurrence of the corresponding class in the testing data.  
 
**Given that (i) we addressed all of the comments raised by reviewers and (ii) the only comments posted by Reviewer KhYb after our rebuttal had already been addressed in our original rebuttal, it is unclear to us why Reviewers KhYb and 98Rq maintained their original negative scores. Especially Reviewer 98Rq made no comment to our rebuttal.** 
 
Kind regards,
The authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary

The paper tackles multi-instance partial label learning within neuro-symbolic learning, redefining imbalance as class-specific error differences rather than instance counts. It offers theoretical insights on how the instance-to-bag label transition function influences this imbalance, alongside a practical method for estimating hidden label marginals. 

Strengths

The paper's strengths lie in its novel perspective on class-specific risk, shifting the focus from instance count imbalance to error differences. It provides strong theoretical contributions through class-specific error bounds. Additionally, the proposed algorithm for estimating marginal probabilities of hidden labels introduces practical innovation. Finally, extensive experiments, particularly in neuro-symbolic learning scenarios, showcase the approach's effectiveness. 

Weaknesses

The paper has several weaknesses. The assumption that the transition function is known is overly strong; while the authors argue this is common in weakly supervised learning literature, it is more typical to estimate it from clean data rather than assume it is given. Clarity in presentation was initially an issue. Though the authors claim this notation and mathematics issues been addressed in a revised version, the non-traditional multi-instance partial label problem and the non-traditional imbalance problem are not clarified sufficiently in introduction - these terminologies used are against its widely accepted definition and are misleading. Empirical performance improvement appears marginal, with results like an increase from 59.88 (±5.58) to 60.26 suggesting randomness rather than meaningful progress. The scope of the work is narrow, as it does not address classical partial label problems and instead focuses on a specific imbalance definition tied to model performance rather than inherent data characteristics, necessitating stronger arguments for its broader relevance.

Recommendation

The paper is recommended to be rejected due to its overly strong assumption that the transition function is known, marginal empirical, and a narrow scope focused on model performance rather than inherent data issues. These limitations outweigh its theoretical and algorithmic contributions, making its broader relevance and practical impact unclear.