PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Consistent Partial-Label Learning

Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, Masashi Sugiyama

arXiv:2007.08929v2cs.LGstat.ML

TL;DR

PLL lacks explicit candidate-label generation models and strong consistency guarantees, leaving unclear when methods work across datasets. This paper introduces a generation model and two provably consistent methods, with experiments validating their effectiveness.

  • Problem

    PLL methods lack explicit candidate-label generation processes and broad consistency guarantees, making their dataset-specific reliability unclear.

  • Method

    The paper formulates a candidate-label generation model and derives risk-consistent and classifier-consistent PLL methods compatible with deep networks and stochastic optimization.

  • Results

    Extensive benchmark and real-world experiments validate the proposed generation model and two PLL methods.

  • Takeaways & Limitations

    Candidate-label entropy can indicate how well datasets match the proposed generation model, with better-matching datasets yielding better method performance.

  • Takeaways & Limitations

    The generation model assumes candidate label sets are independent of instances given the correct label and uniformly sampled conditional on that label.

Abstract

from arXiv · show

Partial-label learning (PLL) is a multi-class classification problem, where each training example is associated with a set of candidate labels. Even though many practical PLL methods have been proposed in the last two decades, there lacks a theoretical understanding of the consistency of those methods-none of the PLL methods hitherto possesses a generation process of candidate label sets, and then it is still unclear why such a method works on a specific dataset and when it may fail given a different dataset. In this paper, we propose the first generation model of candidate label sets, and develop two novel PLL methods that are guaranteed to be provably consistent, i.e., one is risk-consistent and the other is classifier-consistent. Our methods are advantageous, since they are compatible with any deep network or stochastic optimizer. Furthermore, thanks to the generation model, we would be able to answer the two questions above by testing if the generation model matches given candidate label sets. Experiments on benchmark and real-world datasets validate the effectiveness of the proposed generation model and two PLL methods.

1 Introduction

The paper addresses the lack of an explicit candidate-label generation process and consistency guarantees in partial-label learning. It proposes a statistical generation model and two consistent methods, with experiments supporting their effectiveness and applicability.

  • Partial-label learning assigns each instance a candidate-label set containing the correct label, supporting applications such as web mining, bird song classification, and face naming.
  • Existing PLL research studied practical performance and statistical properties, but lacked an explicit data-distribution formulation explaining when methods succeed.
  • The paper introduces the first statistical model for how candidate-label sets are generated and verifies that it preserves inclusion of the correct label.
  • It derives risk-consistent and classifier-consistent PLL methods that are model-independent and optimizer-independent, enabling use with deep networks and advanced optimizers.
  • Each method receives an estimation error bound, while experiments report a tighter bound and better deep-network performance for the risk-consistent method.
  • Higher-entropy candidate-label sets better match the proposed generation model, and the methods perform better on such datasets.

2 Formulations

PLL learns from candidate-label sets in which only one label is correct, but its formulations and consistency guarantees depend on assumptions about the data distribution. The paper motivates an explicit distribution that supports new statistically consistent methods.

  • Ordinary supervised learning models examples with an unknown joint distribution and seeks a classifier minimizing expected classification risk.
  • A method is risk-consistent when its risk estimator is equivalent to the classification risk, whereas classifier consistency concerns infinite-sample convergence to the risk-minimizing classifier.
  • PLL represents each instance with a candidate-label set containing the correct label, and aims to learn a classifier that predicts correctly on test inputs.
  • Prior statistically consistent PLL work required limited ambiguity and strict conditions such as loss convexity and a dominance relation.
  • Complementary labels specify classes an example does not belong to and form a special case of partial labels.
  • Multiple complementary labels may be common in real-world settings, motivating explicit modeling beyond the single-complementary-label case.
  • The paper answers whether an explicit partially labeled-data distribution can yield both classifier-consistent and risk-consistent PLL methods.

3 Data Generation Model

The paper defines an explicit generation model for partially labeled data in which candidate label sets are sampled conditional on the correct label. The model is a valid distribution, always includes the correct label, and arises from a simple label-set screening procedure.

  • Partially Labeled Data Distribution: The proposed model assumes each partially labeled example is independently drawn from a distribution over instances, correct labels, and candidate label sets.It uses p(Y | x, y) = p(Y | y), making the candidate set independent of the instance given the correct label.
  • Partially Labeled Data Distribution: Given the correct label, each candidate label set containing it is uniformly sampled among the possible sets.There are 2^k−1−1 candidate label sets containing a specific label, and the model assigns them equal probability.
  • Validity of the Model: Theorem 1 establishes that the assumed density integrates to one and therefore defines a valid probability distribution.The equality ∫p(x, Y)dx dY = 1 is stated as the theorem’s conclusion.
  • Validity of the Model: Theorem 2 shows that every example sampled from the proposed distribution contains its correct label in the candidate set.This verifies the key PLL requirement for the proposed data-generating process.
  • Motivation: A screening procedure that uniformly samples label sets and retains those containing the correct label produces the proposed distribution.For an unknown uniformly sampled label set, the probability that it contains the correct label is 1/2; conditioning on inclusion yields the model in Eq. (5).

4 Consistent Methods

The paper derives risk-consistent and classifier-consistent PLL methods from the proposed distribution, with convergence guarantees and model-independent optimization. The risk-consistent method has a tighter bound and is expected to perform better with deep networks, while experiments compare performance across neural and linear models.

  • Method Overview: The two proposed methods are model-independent, optimizer-independent, and compatible with stochastic optimization and large-scale datasets.They can therefore be applied to complex models such as deep neural networks without specially designed optimization objectives.
  • Risk-Consistent Method: The risk-consistent method rewrites classification risk using importance reweighting and estimates class confidence with the model output.Non-candidate labels are assigned zero confidence before constructing the empirical estimator.
  • Risk-Consistent Method: The risk-consistent empirical minimizer converges to the true risk minimizer as the sample size tends to infinity.Theorem 4 provides an estimation error bound based on Rademacher complexity.
  • Classifier-Consistent Method: The classifier-consistent method represents candidate sets as virtual labels and relates their probabilities to ordinary-label probabilities through a transition matrix.The matrix has entries 1/(2^k−1−1) when the ordinary label belongs to the candidate set and zero otherwise.
  • Classifier-Consistent Method: When the transition matrix has full rank and the stated loss condition holds, the classifier-consistent minimizer equals the true minimizer.Theorem 5 establishes classifier consistency under these conditions.
  • Classifier-Consistent Method: The classifier-consistent empirical minimizer also converges to the true risk minimizer as the sample size tends to infinity.Theorem 6 supplies the corresponding estimation error bound.
  • Theoretical Comparison: The risk-consistent method has a tighter estimation error bound than the classifier-consistent method and is expected to perform better with deep neural networks.The paper states that experiments demonstrate RC is generally superior to CC with deep neural networks.
  • Experiments: The benchmark tables report neural-network test performance for CIFAR-10 and three other datasets using different network architectures.Table 1 uses ResNet on CIFAR-10 and MLP on the other datasets, while Table 2 uses DenseNet and LeNet respectively.

5 Experiments

The experiments evaluate the proposed PLL methods across benchmark, UCI, and real-world datasets, comparing them with existing PLL and complementary-label methods. Results support strong performance, especially for RC, and show that higher entropy indicates better alignment with the proposed generation model and better method performance.

  • Datasets and setup: Experiments cover benchmark, UCI, and real-world partially labeled datasets using neural-network and linear-model settings.The benchmark collection includes MNIST, Kuzushiji-MNIST, Fashion-MNIST, and CIFAR-10; real-world datasets include Lost, BirdSong, MSRCv2, Soccer Player, and Yahoo! News.
  • Compared methods: The evaluation compares RC and CC with six state-of-the-art PLL methods and complementary-label learning methods.The compared PLL methods include SURE, CLPL, IPAL, PLSVM, PLECOC, and PLKNN.
  • Experimental results: RC always achieves the best benchmark performance and significantly outperforms other methods in most cases.On UCI and real-world datasets, RC and CC generally achieve superior performance against the compared methods.
  • RC versus CC: RC and CC have similar performance with linear models, whereas RC significantly outperforms CC with deep neural networks.This agrees with the reported expectation that RC’s superiority becomes more pronounced with more complex models.
  • Generation-model effectiveness: Higher entropy corresponds to a better match with the proposed generation model and better performance of RC and CC.Entropy is used to assess, before model training, whether candidate label sets match the proposed generation process.

6 Conclusion

The paper formulates an explicit generation process for partially labeled data and derives risk-consistent and classifier-consistent PLL methods. Theoretical error bounds and extensive experiments demonstrate the effectiveness of the generation model and methods.

  • The paper provides the first explicit mathematical formulation of the partially labeled data generation process for PLL.
  • Based on this model, the paper derives a novel risk-consistent method and a novel classifier-consistent method.
  • The authors theoretically derive an estimation error bound for each proposed method.
  • Extensive experimental results demonstrate the effectiveness of the proposed generation model and two PLL methods.

Broader Impact

The proposed PLL methods may support privacy-sensitive data collection by learning from candidate-label sets rather than directly obtained ground-truth labels. However, adversarial use could expose private information, and reduced annotation needs could affect annotation specialists’ employment.

  • PLL can be applied when respondents provide candidate labels containing the true answer instead of directly revealing ground-truth labels.The paper gives extremely private survey questions as an example where removing obviously wrong labels may be easier for respondents.
  • Adversaries could use deliberately collected high-quality partially labeled data to learn from and divulge or leverage private information.
  • If partial-label methods reduce the need for accurately annotated data, data-annotation specialists could face increased unemployment.

A Proofs of Data Generation Process

The proof derives the partially labeled data distribution by conditioning on the correct label and candidate set, using uniform sampling over candidate sets that contain that label. Summing over labels yields the proposed distribution.

  • The resulting expression is used to conclude the proof of Theorem 1 and Lemma 1.
  • The proof rewrites candidate-set inclusion as p(y ∈Y | x, Y ) = 1 −p(y /∈Y | x, Y ).
  • For a fixed correct label i, the joint probability of candidate-set inclusion factors into conditional inclusion and label-prediction probabilities.
  • The derivation expands the candidate-set event by conditioning on a candidate set C and then uses the assumed candidate-set distribution.
  • Uniform sampling gives p(Y = C | x) = p(Y = C) = 1 2k−2, while the number of candidate sets containing a specific label is |Ci| = 2k−1 −1.
  • Summing over possible correct labels and multiplying by p(x) produces the proposed partially labeled distribution ep(x, Y ).

B Proofs of Theorem 4

The proof establishes an estimation-error bound for the risk-consistent method using empirical-process tools, bounded differences, and Rademacher complexity. The argument combines an empirical-to-true risk comparison with complexity bounds under bounded and Lipschitz loss assumptions.

  • Proof strategy: The proof uses Rademacher complexity to establish the estimation-error bound for the risk-consistent method.The proof first introduces the relevant function space and expected Rademacher complexity, then combines several lemmas to prove the theorem.
  • Proof strategy: The empirical risk minimizer’s excess true risk is bounded by deviations between empirical and true risks.The proof decomposes R(bf) − R(f⋆) into two empirical-to-true risk deviations.
  • Concentration bound: McDiarmid’s inequality controls both directions of the empirical-to-true risk deviation when the loss is bounded by M.Replacing one training example changes the relevant supremum by at most M/(2n), enabling concentration bounds.
  • Complexity bound: A ρ-Lipschitz loss permits the expected Rademacher complexity of the risk-consistent function class to be bounded through vector contraction.The bound reduces to the complexities of the coordinate function classes H_y.
  • Conclusion: Combining the empirical-risk comparison, concentration inequality, and complexity estimate proves the risk-consistency estimation bound.The theorem follows by combining Lemmas 3, 4, and 5.

C Proofs of Classifier-Consistency

The classifier-consistency proof shows that minimizing the classifier-consistent risk recovers the true classifier under a full-rank transformation, while its estimation bound follows from Rademacher-complexity arguments. The proof also uses bounded and Lipschitz loss assumptions for concentration and contraction steps.

  • Consistency proof: The proof represents candidate-set probabilities as q⋆(x) = Q⊤g⋆(x), linking observed candidate labels to true classifier outputs.The vectors q⋆ and g⋆ collect candidate-set and class probabilities, respectively.
  • Consistency proof: Classifier consistency follows when the transformation matrix Q has full rank, yielding gcc = g⋆ and fcc = f⋆.Both classifiers induce the same transformed output, and full rank makes the underlying outputs equal.
  • Estimation bound: The classifier-consistent function space is defined over samples whose candidate set is selected from the collection of label sets.The construction uses Y = C_ey and defines the expected Rademacher complexity of the resulting class.
  • Estimation bound: For bounded loss, concentration controls deviations between classifier-consistent empirical and true risks.Replacing one example changes the supremum by at most M/n, after which McDiarmid’s inequality is applied.
  • Estimation bound: A ρ′-Lipschitz loss and vector contraction bound the classifier-consistent complexity by coordinate-wise Rademacher complexities.Combining this complexity estimate with the preceding lemmas yields the estimation theorem.

E.1 Datasets and Models

The experiments evaluate PLL methods on benchmark, UCI, and real-world partially labeled datasets using linear models and neural networks. Across the reported performance analyses, RC and CC consistently outperform competing methods, including with simple linear models.

  • Datasets and models: The controlled evaluation uses four benchmark image datasets and five UCI datasets, with linear models restricted to the regular-scale UCI datasets.The benchmark datasets include MNIST, Kuzushiji-MNIST, Fashion-MNIST, and CIFAR-10; the UCI datasets include Yeast, Texture, Dermatology, Har, and 20Newsgroups.
  • Datasets and models: Five real-world datasets cover automatic face naming, bird song classification, and object classification applications.The datasets are Lost, BirdSong, MSRCv2, Soccer Player, and Yahoo! News.
  • Evaluation protocol: The experiments use validation-based hyperparameter selection and average accuracy over the final ten epochs of each trial.The reported trials use five runs on benchmark datasets and ten runs on UCI datasets.
  • Compared methods: The study compares RC and CC with PLL and complementary-label methods under matched full-batch training settings.The comparison includes methods such as SURE, CLPL, IPAL, PLSVM, PLECOC, PLKNN, PC, Forward, Free, NN, and GA.
  • Results: RC and CC significantly outperform other compared methods in most neural-network transductive-accuracy cases.The reported transductive analyses use neural networks on benchmark datasets, including ResNet, DenseNet, MLP, and LeNet settings.
  • Results: RC and CC consistently outperform competing methods in test-accuracy curves, even with simple linear models.Figure 1 reports mean accuracy over five trials with standard deviations shown separately.

F Experiments on Effectiveness of Generation Model

The paper tests whether candidate-label generation processes match the proposed model by comparing their entropy and resulting method performance. The proposed model has maximum entropy because non-true labels are equally likely candidates given the true label.

  • Evaluation design: Entropy is used to measure how well observed candidate-label sets match the proposed generation model before training.The measure is intended to indicate whether applying the proposed methods to a dataset is appropriate.
  • Generation processes: Six candidate-label generation cases are compared, each assigned an entropy value and visualized as a heatmap.The entropy calculation normalizes the transition matrix before evaluating the resulting distribution.
  • Generation processes: The experiments vary the class transition matrix T while keeping candidate-label sets independent of the instance.T_ij denotes the probability that label j is a candidate given true label i, with T_ii = 1.
  • Generation processes: The proposed generation model achieves maximum entropy, with entropy 2.257, because other labels have equal candidate probabilities given the true label.This model is the reference case for assessing how well alternative candidate-label sets match the proposed process.
Loading 2007.08929v2…