TL;DR
This paper investigates the computational complexity of learning from label proportions, a setting where only the proportion of labels in a dataset is known, not individual labels. They demonstrate that learning from label proportions is strictly harder than standard PAC learning, establishing NP-hardness for certain hypothesis classes and identifying a strict subset of PAC-learnable classes that are learnable in this setting.
What Problem Does This Paper Address?
In traditional machine learning, particularly PAC (Probably Approximately Correct) learning, algorithms are trained on datasets where each data point has an explicit label. This allows the learner to directly infer the relationship between features and labels. However, in many real-world scenarios, obtaining individual labels is difficult or impossible. For instance, political polls report the percentage of voters favoring a candidate, not the voting preference of each individual surveyed. This paper addresses the problem of "learning from label proportions," where the training data consists of unlabeled instances along with the proportion of instances belonging to each class. The goal is to learn a hypothesis that accurately predicts these proportions for a hidden distribution, rather than predicting individual labels. This setting is crucial for applications where aggregate statistics are more readily available than granular data.
Methods
The authors formalize a PAC-like learning model for label proportions. A key aspect of their approach is to analyze the computational complexity by comparing it to classical PAC learning. They leverage the concept of VC dimension to characterize learnability. Their methodology involves:
- Formalizing the Model: Defining "PAC learning from label proportions" and distinguishing it from improper learning (which is shown to be trivial).
- Establishing Hardness Results: Using reductions from known NP-hard problems like SUBSET SUM and k-SUM to prove that learning certain hypothesis classes (specifically, those with high VC dimension) is NP-hard in this setting. They also show hardness for specific classes like parity functions under certain distributions.
- Characterizing Learnability: Demonstrating that the set of hypothesis classes efficiently learnable from label proportions is a strict subset of those learnable in the standard PAC setting.
- Identifying Learnable Classes: Providing positive results by showing that some classes, like half-spaces under the uniform distribution, are efficiently learnable from label proportions, highlighting the importance of well-behaved distributions.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic distributions for hardness proofs and learnability demonstrations.
Key Insights and Ideas
- Learning from Proportions is Strictly Harder: Perhaps the most surprising finding is that learning from label proportions is computationally harder than standard PAC learning. This challenges the intuition that less information (no individual labels) would necessarily make learning easier.
- VC Dimension as a Barrier: Similar to PAC learning, high VC dimension is a significant barrier to efficient learning from label proportions. However, the paper shows that even classes with moderate VC dimensions can be hard to learn in this setting.
- The Importance of Distribution: The paper highlights that while learning can be hard under arbitrary distributions, it can become significantly easier under specific, well-behaved distributions (e.g., the uniform distribution for half-spaces).
- Strict Subset Relationship: The set of hypothesis classes that can be efficiently learned from label proportions is a strict subset of those learnable via standard PAC learning. This means there are problems learnable in PAC that are intractable with only label proportions.
Key Results
- NP-Hardness: Learning from label proportions is NP-hard for hypothesis classes with VC dimension $\ge n^\gamma$ for some constant $\gamma > 0$.
- Hardness for Parity Functions: PAC learning parity functions from label proportions is at least as hard as learning noisy parities, implying hardness for classes with VC dimension $\omega(\log^2 n)$ under a parity hardness assumption.
- Hardness for k-SUM related classes: Hypothesis classes where hypotheses label exactly $k$ points positively are at least as hard as k-SUM.
- Strict Subset: If NP = RP, then any hypothesis class efficiently learnable from label proportions is also efficiently PAC learnable. This implies that the converse is not true, establishing a strict subset relationship.
- Learnability of Half-Spaces: The class of half-spaces in $n$ dimensions is learnable from label proportions under the uniform distribution.
- Learnability of Parities with Noise: Parities are learnable from label proportions under the uniform distribution even with unknown $\eta$ white-label noise.
Limitations and Future Work
- Binary Labels: The current work focuses exclusively on binary classification. Extending the analysis to multi-class settings is a natural next step.
- Single Bag Assumption: The paper considers the "one-bag case," where all unlabeled instances and their aggregate proportion form a single training set. Future work should analyze scenarios with multiple bags of instances, each with its own label proportion.
- Distributional Assumptions: While the paper shows hardness under arbitrary distributions, further exploration of learnability under various specific distributions could be valuable.
- Agnostic and Improper Learning: The paper primarily focuses on proper PAC learning. Investigating agnostic or improper learning from label proportions could reveal different complexity landscapes.
Summary updated