PAC-Bayesian Theory for Transductive Learning

Luc Bégin, Pascal Germain, François Laviolette, Jean-Francis RoyAISTATS 2014 · OpenReview

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.

Comparison of various divergence functions ($D$-functions) across different ratios of labeled to total data ($m/N$).

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.

Empirical results comparing observed risks with the proposed PAC-Bayesian bounds across multiple UCI datasets.

The experimental results, summarized in the table above, highlight several key findings:

  1. 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.
  2. Stability: Unlike previous work, these bounds remain stable and converge toward inductive counterparts as the total sample size $N$ grows.
  3. 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

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. Some of them are derived from ...
BibTeX
@inproceedings{begin2014pac,
  author = {Luc Bégin and Pascal Germain and François Laviolette and Jean-Francis Roy},
  title = {{PAC-Bayesian Theory for Transductive Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=2sf6gpHt0vx},
}
Figure