Transductive Rademacher Complexity and its Applications
Abstract
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.
- Publication:
-
arXiv e-prints
- Pub Date:
- January 2014
- DOI:
- arXiv:
- arXiv:1401.3441
- Bibcode:
- 2014arXiv1401.3441E
- Keywords:
-
- Computer Science - Machine Learning;
- Computer Science - Artificial Intelligence;
- Statistics - Machine Learning
- E-Print:
- Journal Of Artificial Intelligence Research, Volume 35, pages 193-234, 2009