Enhancing Deep Partial Label Learning via Casting it to a Satisfiability Problem

Authors: Liwei Che, Efthymia Tsamoura, Vladimir Pavlovic
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: weak supervised learning, partial label learning

Abstract:
Partial label learning (PLL) is a challenging real-world problem in the field of weakly supervised learning, in which each data instance contains a set of candidate labels with multiple ambiguous labels and one gold label. Although recent progress in PLL using deep representation learning has led to significant advances, the methods continue to experience significant performance drops on data with high label ambiguity and fine-grained categories. By casting PLL into a satisfiability problem and incorporating a loss based on this reduction,  we show that the accuracy of those techniques can be further improved. We establish several key theoretical properties of the proposed SATisfiability-based (SAT) loss and its learning error bound. Our extensive empirical comparison reveals that the proposed loss improves over existing PLL techniques by up to 25.12% on multi-class benchmarks and 12.50% on fine-grained categorized benchmarks.

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

Reviews and discussion:
<thread>
creation date:
1729083508334

thread_type:
official_review

<thread_object>
creator: reviewer_ej8p

<content>
summary:
This work discussed the partial label learning(PLL) problem, which means that the supervision information is a set of possible labels.

Specifically, this paper proposed a satisfiability-based(SAT) loss function to handle the PLL problem.

To do this, they first transform the partial label information into the propositional logic formula, e.g., $\displaystyle\phi = (\land_{i\in s} X_i)\land \neg(\text{more than one label is correct})$. 
Then they optimize this loss function as any other loss function, by maximizing the semantic loss form.

The authors also established a generalization error bound under the low-ambiguity assumption.

strengths:
+ The paper is generally easy to read and follow.
+ The proposed method shows a good performance.
+ They give a classical generalization error analysis.

weaknesses:
- **Motivation is UNCLEAR.** The introduction failed to explain why this paper should introduce the SAT loss. As the authors claim that the previous works are not good enough, they say the previous methods have *undesired behavior*, which is very fun, because no method can guarantee error-free, especially in such a weakly-supervised learning scenario.
  - For example, the motivation example and analysis of the introduction part (see lines 27 to 100) can be used to introduce the motivation of any algorithm of partial label learning. 
  - The necessity of transforming a partial label constraint to a propositional logic formula is unclear, why? 

- **Claims are UNSUPPORTED or TRIVIAL.** There are two claims of the proposed method.
  - *Robustness*. The authors claim that the proposed SAT loss is robust to high label ambiguity. They explained that 
> the SAT loss holds the property that its risk is non-increasing as the small ambiguity degree increases.

    This is not a good explanation, because *any* loss function with $\prod_{i \in s} \ell(f(x_i))$ form will satisfy this property.

  - *Disambiguation*. The authors say that the proposed SAT loss can perform better by *low entropy preference*. However, it is a small trick to regularize the model's output to have low entropy in the field of weakly-supervised learning. It is *not a rare property, many loss functions can induce such a property*, and it can not explain why this method is better since there is no more information used.

- **Theoretical analysis is EMPTY**. The given bound is not rigorous, first, the given bound can only hold when the classification task is binary, that is to say, this bound is not consistent with the notations introduced in the paper. Although this problem can be fixed easily to extend to a multiclass case. The established bound is no better than the earlier proposed PLL bound [1,2]. Especially, we can see that the Rademacher complexity is increased if we choose the SAT loss. Also, the established process of this error bound is very common in this field, thus can not bring any new insight or perspective to us.

- **Experiment results are Weried**. The reported performance of SAT loss is surprisingly high, for example, the reported performance of CIFAR-100 (see Table 1) is even better than the supervised case (purely use cross entropy). It is convinced that the experiments are done in unfair settings, i.e., using bags of tricks. Thus it is difficult to say the SAT loss is better. Besides, I *checked the code*, and the running code is different compared with what the authors said in their paper. For example, they use more than SAT loss, but also EMA trick, warmup learning rate decay, and mixup loss, and even more I have not carefully checked.  It is easy to do such a good performance if you can do many bags of tricks. 


Refs:

---
[1] Timothee Cour, Ben Sapp, and Ben Taskar. 2011. Learning from Partial Labels. J. Mach. Learn. Res. vol.12, pp. 1501–1536.

[2] Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. 2020. Provably consistent partial-label learning.  In Advances in Neural Information Processing. Systems 33, pp. 10948–10960, Virtual, 2020.

questions:
Q1: Can you explain your motivation clearly?

Q2: Can you support your claims? 

Q3: Can you explain the superiority of your error bound compared with other papers (for example, the listed two)? 

Q4: It is well-known that the semantic loss minimizes the inconsistency of the model and the logic constraint, the proposed loss can be seen as a special case of semantic loss. But the computational complexity of the semantic loss is very high, in fact, the computation of SL is #P, which is usually harder than NP. Can you compare the efficiency of the algorithm with other methods? Especially on a large scale (concerning the label space size).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730285689289

thread_type:
official_review

<thread_object>
creator: reviewer_a6aw

<content>
summary:
The paper proposes a novel loss function applicable to partial label learning, a problem in which each datapoint is annotated with a set of candidate labels, of which only one is the correct (or gold) one. They also provide the learning error bounds of this new loss and an extensive experimental analysis.

strengths:
The paper is quite easy to follow.

weaknesses:
The paper presents a series of dubious claims:

1. The authors first try to cast PLL as a satisfiability problem. This entails encoding the candidate set into a boolean formula which can be intuitively divided into two subformulas: one that states that at least one label in the candidate set should be the predicted and the other that states that only one should be predicted. Now, the authors can discard the second formula (which also happens to be very large) because they assume that they only work with models with softmax non-linearity in their last layer. This is fine, but then essentially their loss function is simply trying to maximise the probability that one of the labels in the candidate set should be predicted. There are many functions in the PLL community that try to do this (e.g., the methods based on the EM algorithm [1]). How is your loss different and better than these methods?

2. The authors call their loss the Saitifiability-based loss which from Remark 3.3 seems to simply coincide with the Product t-norm in the fuzzy logic literature. This is a failure to recognise the fact that the authors are *not* proposing a new loss, but they are applying a known loss function (which has been heavily studied in the Near-symbolic AI literature) in the PLL field. 

3. The authors give a definition of the *small ambiguity degree*, however, that definition coincides with Cour's definition of ambiguity degree. If that is the small one, how would be large ambiguity degree be defined? 


Smaller problems/typos: 

- In Figure 2 what is PC, MC, PI and MI? 
- Page 3 line 155 it should be the marginal of $P(X,S,Y)$
- Equation (2) it should be $X_{j'}$
- Corollary 4.2, of what exactly is a Corollary? 

References:

[1] Jin, R., & Ghahramani, Z. (2002). Learning with multiple labels. In NeurIPS, Vol. 15 (pp. 897–904).

questions:
See above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730881059191

thread_type:
official_review

<thread_object>
creator: reviewer_6scy

<content>
summary:
A SAT-based formulation of the partial label learning problem is proposed. The authors encode each training instance (data / candidate-label pairs) into formulas in propositional logic. The proposed method then exploits a SAT-based loss to do training over these formulas. Theoretical justification is provided. The authors demonstrate (1.) robustness to label ambiguity- i.e. the risk a classifier suffers wrt the SAT loss is non-increasing with the partial label ambiguity. (2.) the SAT loss is proportional to the entropy of the network logits i.e., minimization of the SAT loss induces low-entropy confident predictions. The authors also provide a detailed analysis of the generalization of classifiers trained with the SAT loss. 

Empirically, a significant improvement is demonstrated on a variety of datasets, including CIFAR100 and tiny-imagenet. Improved clustering of the latent space embeddings is demonstrated by applying T-SNE to model embeddings.

strengths:
I find this paper to be very well-written and interesting- I appreciate the examples. The core concept is novel and I believe bridging neural methods and logical reasoning is an important topic of study. The inclusion of a detailed, but concise, theoretical analysis is beneficial in providing justification for their method. The empirical results are encouraging as well and I am happy to see that the authors have provided code. I am inclined to accept this paper.

weaknesses:
see questions

questions:
I assume there would be other methods that can be used to penalize the entropy of predictions. How does the proposed SAT loss compare to those methods?

If a subset of the partial labels are noisy how would SAT loss perform?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730883291959

thread_type:
official_review

<thread_object>
creator: reviewer_k18q

<content>
summary:
In this paper, the authors casted PLL into a satisfiability problem and incorporated a SATisfiability-based (SAT) loss based on this reduction. Besides, the authors proved several natural properties of satisfiability-based PLL: that the loss is non-increasing the larger candidate label sets become and that it favors low entropy classifiers. Experiments show that satisfiability-based training leads to consistently higher classification accuracy over all settings compared with previous state-of-the-art techniques.

strengths:
The proposed SATisfiability-based (SAT) loss leads to consistently higher classification accuracy over all settings compared with previous state-of-the-art techniques.

weaknesses:
1. **Lack of Intuitive Explanation for the Proposed Method's Effectiveness**: While the paper introduces the idea of "casting PLL into a satisfiability problem" to address performance drops in data with high label ambiguity and fine-grained categories, the intuition behind how this formulation resolves these issues is not sufficiently explained.

2. **Unclear Distinction Between PLL and Complementary-Label Learning**: The relationship between the proposed PLL method and Complementary-Label Learning (CLL) is not well articulated. 

3. **Absence of Ablation Studies**: The paper lacks ablation studies that could provide more detailed insights into the contributions of each component of the proposed method. Additionally, while theoretical justifications for the SAT loss are provided, their direct relevance and contribution to the method’s practical effectiveness are not sufficiently explored.

questions:
1. The approach of "casting PLL into a satisfiability problem" proposed in the paper is suggested to help address the issue of "significant performance drop on data with high label ambiguity and fine-grained categories." Could the authors provide some intuitive insights or explanations on how this formulation helps in this context? It appears that this approach could also address the issue of "low label ambiguity."

2. In the methodology section, the form of Eq. (3) appears similar to that used in Complementary-Label Learning. Based on this, it seems that the goal of minimizing the probability of labels not in the candidate label set is conceptually similar to the objectives in Complementary-Label Learning[1][2]. When the number of labels in the candidate label set increases, PLL seems to approach the problem of Complementary-Label Learning in some respects. Could the authors elaborate on the relationship between these two approaches?

3. In Section 4, the SAT loss is provided with theoretical justification. I would like to know whether these theoretical justifications offer any insights or guidance for the methodology and the underlying problem it addresses. For example, does Theorem 4.4 provide any valuable insights into the design of the proposed method?

4. The experiments lack corresponding ablation studies. Could the authors provide some potential ablation experiments or suggestions on which experiments could be conducted to further validate the proposed method?


[1] "Discriminative complementary-label learning with weighted loss." ICML 2021.

[2] "Learning with multiple complementary labels." ICML 2020.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731071514783

thread_type:
official_review

<thread_object>
creator: reviewer_58dh

<content>
summary:
This paper proposes a new method for Partial Label Learning (PLL) by formulating the task as a satisfiability (SAT) problem and introducing a SAT-based loss function. Partial label learning involves scenarios where each data instance has multiple candidate labels, but only one is correct. The authors argue that current PLL methods struggle in cases of high label ambiguity and fine-grained categorization. By encoding PLL constraints as logical formulas and designing a SAT loss that penalizes unsatisfied formulas, this method encourages disambiguation toward the true label without relying on pseudo-labels. The approach is validated on various benchmarks, showing up to 25% improvement over existing PLL techniques, such as PICO and PAPI, in certain settings.

strengths:
Novel Problem Framing: Casting PLL as a SAT problem is innovative, providing a new angle to address label ambiguity. The SAT loss introduces a logic-driven constraint, which could contribute positively to PLL tasks by enforcing logical consistency.
Solid Theoretical Foundation: The paper includes theoretical analysis, demonstrating the robustness of SAT loss in high-ambiguity scenarios and fine-grained categorization tasks, supported by proofs of error bounds and properties like low-entropy preference.
Significant Experimental Improvements: Empirical results are extensive, covering diverse datasets and demonstrating significant performance gains. The experiments suggest that the SAT loss is effective in improving classification accuracy and resilience in challenging PLL scenarios.

weaknesses:
Limited Innovation Scope in PLL: While the SAT-based formulation is novel, it may be perceived as incremental in its application, as it leverages established ideas from satisfiability and logical constraints. Whether this alone constitutes a breakthrough in PLL could be debatable, especially given the broader ICLR scope.
Dependency on Existing Models: The proposed SAT loss is integrated with existing PLL methods like PICO and PAPI rather than functioning independently as a standalone model. This limits the novelty of the overall algorithm, as the SAT loss relies heavily on baseline techniques for its effectiveness.
Complexity and Scalability Concerns: Implementing SAT loss with logic-based constraints may increase computational requirements. The scalability of the approach to large-scale, real-world datasets or cases with more complex dependencies among labels could be challenging and is not addressed in depth.

questions:
Generalization to Real-World Data: Does the model maintain its efficacy when applied to real-world, noisy datasets where label ambiguity might not align as neatly with the SAT loss assumptions?

Computational Overheads: The SAT loss, while theoretically sound, could introduce computational complexity. How does this approach compare in terms of training efficiency with more traditional PLL methods?

Potential for Broader Application: Could the SAT-based formulation be generalized to other types of weakly supervised learning beyond PLL, such as multi-label learning?

Please clarify the significance of this partial label learning setting. Is it truly valuable to have numerous papers on this problem, given that each often presents only marginal improvements?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732049930934

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Author Rebuttal

comment:
Dear AC and reviewers,

We genuinely appreciate the valuable feedback from the reviewers on our work. We are encouraged by the reviewers' recognition that our work is well-written (Reviewer 6sCy, A6aW, Ej8p), with innovative motivations, interesting and promising
methods (Reviewer 58DH, 6sCy), a good combination of theoretical justification and superior experimental
performance (Reviewer 58DH, k18q, 6sCy, Ej8p).

We have responded to the concerns raised by reviewers in the individual replies. We hope these responses will offer additional clarity on the contributions and the novel approach taken in our work. 


We appreciate your time and efforts in the review of our work. We are happy to discuss any further questions. It would be greatly appreciated if you could reconsider and raise the score!

We will use the below reference list in our replies:

[1] Suciu, D., Olteanu, D., Ré, C., & Koch, C. (2022). Probabilistic databases. Springer Nature.

[2] Jin, R., & Ghahramani, Z. (2002). Learning with multiple labels. Advances in neural information processing systems, 15.

[3] Cabannnes, V., Rudi, A., & Bach, F. (2020, November). Structured prediction with partial labeling through the infimum
loss. In International Conference on Machine Learning (pp. 1230-1239). PMLR.

[4] Wu, D. D., Wang, D. B., & Zhang, M. L. (2022, June). Revisiting consistency regularization for deep partial label learning.
In International conference on machine learning (pp. 24212-24225). PMLR.

[5] Wang, H., Xiao, R., Li, Y., Feng, L., Niu, G., Chen, G., & Zhao, J. (2022). Pico: Contrastive label disambiguation for partial
label learning. In International conference on learning representations.

[6] Wang, H., Xiao, R., Li, Y., Feng, L., Niu, G., Chen, G., & Zhao, J. (2023). Pico+: Contrastive label disambiguation for robust
partial label learning. IEEE Transactions on Pattern Analysis and Machine Intelligence.

[7] Xia, S., Lv, J., Xu, N., Niu, G., & Geng, X. (2023). Towards effective visual representations for partial-label learning. In
Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 15589-15598).

[8] Cour, T., Sapp, B., & Taskar, B. (2011). Learning from partial labels. The Journal of Machine Learning Research, 12, 1501-
1536.

[9] Lv, J., Xu, M., Feng, L., Niu, G., Geng, X., & Sugiyama, M. (2020, November). Progressive identification of true labels for partial-label learning. In international conference on machine learning (pp. 6500-6510). PMLR. 

[10] Liu, L., & Dietterich, T. (2014, June). Learnability of the superset label learning problem. In International conference on machine learning (pp. 1629-1637). PMLR.

[11] Wen, H., Cui, J., Hang, H., Liu, J., Wang, Y., & Lin, Z. (2021, July). Leveraged weighted loss for partial label learning. In
International conference on machine learning (pp. 11091-11100). PMLR.

[12] Feng, L., Lv, J., Han, B., Xu, M., Niu, G., Geng, X., ... & Sugiyama, M. (2020). Provably consistent partial-label learning.
Advances in neural information processing systems, 33, 10948-10960.

[13] Feng, L., Kaneko, T., Han, B., Niu, G., An, B., & Sugiyama, M. (2020, November). Learning with multiple complementary
labels. In International conference on machine learning (pp. 3072-3081). PMLR.

[14] Mohri, M. (2018). Foundations of machine learning.


[15] Ishida, T., Niu, G., Hu, W., & Sugiyama, M. (2017). Learning from complementary labels. Advances in neural information processing systems, 30.

[16] Fink, R., Huang, J., & Olteanu, D. (2013). Anytime approximation in probabilistic databases. The VLDB journal, 22, 823-848.

[17] Everingham, M. (2009). The PASCAL visual object classes challenge 2007. In http://www. pascal-network. org/challenges/VOC/voc2007/workshop/index. HTML.

[18] Diligenti, M., Gori, M., & Sacca, C. (2017). Semantic-based regularization for learning and inference. Artificial Intelligence, 244, 143-165.

[19] Thomson, B. S., Bruckner, J. B., & Bruckner, A. M. (2008). Elementary real analysis (Vol. 1). ClassicalRealAnalysis. com.

[20] O'Searcoid, M. (2006). Metric spaces. Springer Science & Business Media.

[21] Kakade, S. M., Sridharan, K., & Tewari, A. (2008). On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in neural information processing systems, 21.

[22] Paulus, A., Rolínek, M., Musil, V., Amos, B., & Martius, G. (2021, July). Comboptnet: Fit the right np-hard problem by learning integer programming constraints. In International Conference on Machine Learning (pp. 8443-8453). PMLR.

[23] Pogančić, M. V., Paulus, A., Musil, V., Martius, G., & Rolinek, M. (2020). Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732252876827

thread_type:
official_comment

<thread_object>
creator: area_chair_ksdr

<content>
title:
calm down

comment:
Please calm down and stop your discussion, because you cannot get the points of each other effectively. You are just repeating your original statements to the air and this would not change anything in the end.
</content>
</thread_object>

</thread>


Metareview: