PAC Generalization Bounds for Co-training

In this paper, we study bootstrapping algorithms for learning from unlabeled data. The general idea in bootstrapping is to use some initial labeled data to build a (possibly partial) predictive labeling procedure; then use the labeling procedure to label more data; then use the newly labeled data to build a new predictive procedure and so on. This process can be iterated until a fixed point is reached or some other stopping criterion is met. Here we give P AC style bounds on generalization error which can be used to formally justify certain boostrapping algorithms. One well-known form of bootstrapping is the EM algorithm (Dempster, Laird and Rubin, 1977).