Co-Training and the Notion of Weak Learnability

Philip Zigoris

Professor Lillian Lee

Here we investigate Co-Training and its relation to PAC-Style notions of weak and strong learning. Co-Training is a meta-learning algorithm proposed by Blum,Mitchell which leverages information between independent views of the instance space in order to utilize unlabeled data.  Subsequent work by Dasgupta et al and Steven Abney showed the error of a classifier based on one of these views is upper-bounded by the disagreement rate between that classifier and one based on the second view.

Our work was originally motivated by apparent flaws and cryptic assumptions that appeared throughout Abney's work.  Abney's theorem fails (and is ill-defined) for anything but binary classification.  We prove a stronger lemma, analogous but stronger than one that appears in Abney's paper, and give a clearer set of assumptions.  As it turns out, Dasgupta et al's work has a very similar set of assumptions, only they take much more care in correcting for sample error.

Worried that our set of assumptions was too strong, we decided to investigate its relationship to weak learning.  Suprisingly, there was no well referenced formal definition of weak learnability for a non-binary concept classes.  But following the intuition that a weak learner should do at least slightly better than random guessing, we developed what seemed to be a natural definition for k-label weak learnability.  Some time was spent investigating the validity of this definition.  At this point, it seems as though the assumptions of Dasgupta et al's and our work are stronger than simply assuming weak learnability.  Although less useful an implication, one can show that if the assumption's are satisfied, then the classifier is in fact a weak learner.

References

Steven Abney. Bootstrapping. 40th Annual Meeting of the Association for Computational Linguistics: Proceedings of the Conference. 2002.

Blum, A., & Mitchell, T. (1998). Combining labeled and unlabeled data with co-training. Proceedings of the Workshop on Computational Learning Theory. 1998.

Sanjoy Dasgupta, Michael Littman, and David McAllester. PAC Generalization Bounds for Co-Training.  NIPS 2001