Abstract: We propose a PAC-Bayesian analysis of the transductive learning setting, introduced by Vapnik [2008], by proposing a family of new bounds on the generalization error. These bounds are derived from a general theorem that allows for various convex "divergence" functions. We introduce a specific bound that remains stable even as the number of unlabeled examples grows to infinity—fixing a major flaw in previous transductive bounds.
Introduction
Most machine learning theory operates in the inductive setting, assuming training and test data are drawn independently and identically distributed (i.i.d.) from an unknown distribution. However, in many real-world scenarios, the "test" examples (without labels) are available at training time. This is known as transductive learning.
The challenge in transduction is that training labels are sampled without replacement from a fixed finite pool, breaking the i.i.d. assumption. This requires mathematical tools based on hypergeometric distributions rather than binomial ones. Previous PAC-Bayesian bounds for this setting, notably by Derbeko et al. (2004), often diverged as the number of unlabeled examples increased. This paper introduces a new framework to provide tighter, more stable generalization guarantees.
Methodology: The General Transductive PAC-Bayesian Theorem
The authors derive a General Transductive PAC-Bayesian Theorem (Theorem 5) that utilizes a general convex function $D$ to measure the distance between empirical risk and full-sample risk. This framework allows for a "plug and play" approach with different divergence measures.
A significant contribution is the introduction of a tailored divergence function, $D^*_\beta$, designed to incorporate the ratio of labeled to unlabeled data ($m/N$). As illustrated in Figure 1, the choice of divergence function is critical; while KL-divergence is often preferred in inductive learning, other functions like variation distance or the custom $D^*_\beta$ can yield tighter bounds depending on the data ratio.
Furthermore, the authors adapt the "C-bound" to the transductive setting, allowing them to bound the risk of majority vote classifiers by using unlabeled data to measure expected disagreement between hypotheses. This leverages the unlabeled data as a resource to significantly tighten risk guarantees.
Empirical Evaluation and Results
The proposed bounds were tested on binary classification tasks from the UCI Machine Learning Repository, using AdaBoost with decision stumps to generate posterior distributions. The datasets included car, mushroom, nursery, and others, evaluated at different training/test ratios.
The experimental results, summarized in the table above, highlight several key findings:
- Superiority over Existing Bounds: The new bounds (Thm 5-KL and Thm 5-$D^*$) are consistently tighter than the previous state-of-the-art by Derbeko et al.
- Stability: Unlike previous work, these bounds remain stable and converge toward inductive counterparts as the total sample size $N$ grows.
- Practical Tightness: On datasets such as nursery and mushroom, the transductive bounds for majority votes were remarkably close to the actual observed risks, providing meaningful guarantees rather than just theoretical upper limits.
Conclusion
This work demonstrates that the transductive setting allows for tighter generalization bounds by treating unlabeled data as a resource rather than just a target. By leveraging the known features of the test set, researchers can significantly improve the reliability of risk estimates. Future work includes extending this theory to multi-class and regression settings, as well as developing learning algorithms that explicitly minimize these transductive PAC-Bayesian bounds during training.
Summary updated