From Batch to Transductive Online Learning
- Sham Kakade ,
- Adam Tauman Kalai
Advances in Neural Information Processing Systems 18, 2006 (NIPS 05) |
We consider the online transductive learning (Ben-David, Kushilevitz and Mansour, 1995) model where an arbitrary sequence of examples are presented to a learner, one at a time. The learner must predict each label, online, given only the labels of the previous examples and the future unlabeled examples. In contrast, more standard i.i.d. models of learning assume that examples are drawn independently and identically distributed from a fixed distribution. We give an algorithm that employs unlabeled data to convert any efficient learning algorithm in an i.i.d. setting to an efficient learning algorithm in the more difficult online transductive model.