Enhancing Deep Partial Label Learning via Casting it to a Satisfiability Problem
weak supervised learning;partial label learning
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
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.
The proposed SATisfiability-based (SAT) loss leads to consistently higher classification accuracy over all settings compared with previous state-of-the-art techniques.
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.
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.
Yes
No ethics review needed.
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?
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.
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.
see questions
Yes
No ethics review needed.
See above
The paper is quite easy to follow.
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.
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).
Yes
No ethics review needed.
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).
+ The paper is generally easy to read and follow.
+ The proposed method shows a good performance.
+ They give a classical generalization error analysis.
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.
- **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.
@inproceedings{
anonymous2024enhancing,
title={Enhancing Deep Partial Label Learning via Casting it to a Satisfiability Problem},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=Z25xTjf3Mv},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
weak supervised learning partial label learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/57c7906b87067c8e319531822b4f19dd9390ea4b.pdf
unsupervised, self-supervised, semi-supervised, and supervised representation learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/d48ed59764ab132913d6fad9c8993247127b8d37.zip
Enhancing Deep Partial Label Learning via Casting it to a Satisfiability Problem
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission