Elamur Research
☰
home / papers / 1998 / Combining Labeled and Unlabeled Data with Co-Training

Combining Labeled and Unlabeled Data with Co-Training

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "author copy (cs.cmu.edu) — read only" does not allow redistributing the text itself. Original — cs.cmu.edu~avrim/Papers/cotrain.pdf

Summary

The paper asks how a large pool of cheap unlabeled examples can improve a classifier when only a few labeled examples exist. It focuses on data where each instance has two separate feature sets ("views"), and either view alone would be enough to classify correctly given enough labels. Web pages are the motivating case: one view is the words on the page, the other is the anchor text of hyperlinks pointing to it. The authors propose co-training. A separate learner is trained on each view, and each learner's most confident predictions on unlabeled data become new training examples for the other learner. They give a PAC-style framework built on a notion of "compatibility" between the target concept and the data distribution, which unlabeled data can use to rule out implausible hypotheses. They also prove that, under conditional independence of the views, a weak initial predictor can be boosted using unlabeled data alone. Experiments with naive Bayes on university web pages roughly halve the error rate. The work is foundational for semi-supervised and multi-view learning.

Key points

  • Formal setting: The instance space is X = X1 × X2, and the target must agree on both views (f1(x1) = f2(x2)). The distribution can be drawn as a bipartite graph in which examples in the same connected component must share a label.
  • Theory: If the views are conditionally independent given the class and the concept class is learnable with random classification noise, then unlabeled data alone suffices to strengthen any weak hypothesis into a strong one. As a by-product, the paper gives new results on learning with lopsided misclassification noise.
  • Data and protocol: The task was to identify course home pages among 1051 university web pages. In each split, 263 pages (25%) were held out for testing, and the labeled set had only 12 pages (3 positive, 9 negative). Results were averaged over five splits with parameters p=1, n=3, k=30, u=75.
  • Results (error %, supervised → co-training):
    • Page-based classifier: 12.9 → 6.2
    • Hyperlink-based classifier: 12.4 → 11.6
    • Combined classifier: 11.1 → 5.0
    • For comparison, always predicting "negative" gives 22% error.
  • Limitations and outlook: The hyperlink view gains least, probably because anchor texts are short. The authors note that the theory's assumptions are idealized and that only one dataset was tested. They suggest other multi-sensor applications, such as video plus audio in TV broadcasts, or vision, sonar and laser sensors on a robot.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

333 papers of our library cite it (of the 140673 whose bibliographies we read); 7 of them have a page here, 326 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/279943.279962

@inproceedings{blum1998combining,
  title = {{Combining Labeled and Unlabeled Data with Co-Training}},
  author = {Blum, Avrim and Mitchell, Tom},
  booktitle = {COLT 1998},
  year = {1998},
  doi = {10.1145/279943.279962},
  url = {https://doi.org/10.1145/279943.279962}
}

References

17 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. V. Castelli and T.M. Cover. On the exponential value of labeled samples. Pattern Recognition Letters , 16:105{111, January 1995. find
  2. V. Castelli and T.M. Cover. The relative value of labeled and unlabeled samples in pattern-recognition with an unknown mixing parameter. IEEE Transactions on Information Theory , 42(6):2102{2117, November 1996. find
  3. M. Craven, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, and C.Y. Quek. Learning to extract symbolic knowledge from the world wide web. Technical report, Carnegie Mellon University, January 1997. find
  4. S. E. Decatur. PAC learning with constant-partition classi cation noise and applications to decision tree induction. In Proceedings of the Fourteenth International Conference on Machine Learning , pages 83{91, July 1997. find
  5. A.P. Dempster, N.M. Laird, and D.B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society B , 39:1{38, 1977. find
  6. Richard O. Duda and Peter E. Hart. Pattern Classi cation and Scene Analysis . Wiley, 1973. find
  7. Z. Ghahramani and M. I. Jordan. Supervised learning from incomplete data via an EM approach. In Advances in Neural Information Processing Systems (NIPS 6) . Morgan Kau man, 1994. find
  8. S. A. Goldman and M. J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences , 50(1):20{31, February 1995. find
  9. A.G. Hauptmann and M.J. Witbrock. Informedia: News-on-demand - multimedia information acquisition and retrieval. In M. Maybury, editor, Intelligent Multimedia Information Retrieval , 1997. find
  10. J. Jackson and A. Tomkins. A computational model of teaching. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory , pages 319{326. Morgan Kaufmann, 1992. find
  11. D. R. Karger. Random sampling in cut, ow, and network design problems. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing , pages 648{657, May 1994. find
  12. D. R. Karger. Random sampling in cut, ow, and network design problems. Journal version draft, 1997. find
  13. M. Kearns. Ecient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing , pages 392{401, 1993. find
  14. D. D. Lewis and M. Ringuette. A comparison of two learning algorithms for text categorization. In Third Annual Symposium on Document Analysis and Information Retrieval , pages 81{93, 1994. find
  15. Joel Ratsaby and Santosh S. Venkatesh. Learning from a mixture of labeled and unlabeled examples with parametric side information. In Proceedings of the 8th Annual Conference on Computational Learning Theory , pages 412{417. ACM Press, New York, NY, 1995. find
  16. M.J. Witbrock and A.G. Hauptmann. Improving acoustic models by watching television. Technical Report CMU-CS-98-110, Carnegie Mellon University, March 19 1998. find
  17. D. Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics , pages 189{196, 1995. find our card