---
title: "Combining Labeled and Unlabeled Data with — Blum 1998"
description: "The paper asks how a large pool of cheap unlabeled examples can improve a classifier when only a few labeled examples exist."
authors: ["Avrim Blum", "Tom Mitchell"]
year: 1998
venue: "COLT 1998"
source: "https://dl.acm.org/doi/10.1145/279943.279962"
doi: "10.1145/279943.279962"
licence: "author copy (cs.cmu.edu) — read only"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/blum-1998-combining-labeled-unlabeled-data-co-training/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/blum-1998-combining-labeled-unlabeled-data-co-training/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1998](https://md.research.elamur.ai/free/en/papers/1998/) / Combining Labeled and Unlabeled Data with Co-Training

# Combining Labeled and Unlabeled Data with Co-Training

**Authors:** Avrim Blum, [Tom Mitchell](https://md.research.elamur.ai/free/en/authors/tom-mitchell/) · **Year:** 1998 · **Venue:** COLT 1998 · **Licence:** author copy (cs.cmu.edu) — read only

**Links:** [Publisher's page](https://doi.org/10.1145/279943.279962) · [PDF](https://www.cs.cmu.edu/~avrim/Papers/cotrain.pdf) · [DOI 10.1145/279943.279962](https://doi.org/10.1145/279943.279962) · [OpenAlex](https://openalex.org/W2048679005)

**Citations:** 5495 citations (openalex-snapshot · 2026-10-14) · [333](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## 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](https://md.research.elamur.ai/free/en/shelves/computing/)

## Cited by

Cited by

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

- [Extending a Parser to Distant Domains Using a Few Dozen Partially Annotated Examples](https://md.research.elamur.ai/free/en/papers/acl-2018-joshi-extending-parser-distant-domains-few/)
- [Effective Self-Training for Parsing](https://md.research.elamur.ai/free/en/papers/aclbulk-2006-mcclosky-effective-self-training-parsing/)
- [A Survey of Paraphrasing and Textual Entailment Methods](https://md.research.elamur.ai/free/en/papers/androutsopoulos-2009-survey-paraphrasing-textual-entailment-methods/)
- [Domain Adaptation with Structural Correspondence Learning](https://md.research.elamur.ai/free/en/papers/blitzer-2006-domain-adaptation-structural-correspondence-learning/)
- [An Empirical Survey of Data Augmentation for Limited Data Learning in NLP](https://md.research.elamur.ai/free/en/papers/chen-2023-empirical-survey-data-augmentation-limited/)
- [Semi-Supervised Sequence Modeling with Cross-View Training](https://md.research.elamur.ai/free/en/papers/clark-2018-semi-supervised-sequence-modeling-cross/)
- [Unsupervised Models for Named Entity Classification](https://md.research.elamur.ai/free/en/papers/collins-1999-unsupervised-models-named-entity-classification/)
- [Iterative Back-Translation for Neural Machine Translation](https://md.research.elamur.ai/free/en/papers/hoang-2018-iterative-back-translation-neural-machine/)
- [Alignment by Agreement](https://md.research.elamur.ai/free/en/papers/liang-2006-alignment-agreement/)
- [Name Tagging with Word Clusters and Discriminative Training](https://md.research.elamur.ai/free/en/papers/miller-2004-name-tagging-word-clusters-discriminative/)
- [Bootstrapping Coreference Classifiers with Multiple Machine Learning Algorithms](https://md.research.elamur.ai/free/en/papers/ng-2003-bootstrapping-coreference-classifiers-multiple-machine/)
- [Unsupervised Models for Coreference Resolution](https://md.research.elamur.ai/free/en/papers/ng-2008-unsupervised-models-coreference-resolution/)
- [SynthLLM: An LLM-based Scalable Synthetic Data Generation Pipeline for Low-Resource Languages](https://md.research.elamur.ai/free/en/papers/panahi-2026-synthllm-llm-based-scalable-synthetic/)
- [Semi-supervised sequence tagging with bidirectional language models](https://md.research.elamur.ai/free/en/papers/peters-2017-semi-supervised-sequence-tagging-bidirectional/)
- [Neural Unsupervised Domain Adaptation in NLP–-A Survey](https://md.research.elamur.ai/free/en/papers/ramponi-2020-neural-unsupervised-domain-adaptation-nlp/)
- [The Web as a Parallel Corpus](https://md.research.elamur.ai/free/en/papers/resnik-2003-web-as-parallel-corpus/)
- [FLSA: Extending Latent Semantic Analysis with Features for Dialogue Act Classification](https://md.research.elamur.ai/free/en/papers/serafin-2004-flsa-extending-latent-semantic-analysis/)
- [Active Learning Literature Survey](https://md.research.elamur.ai/free/en/papers/settles-2009-active-learning-literature-survey/)
- [Augmented SBERT: Data Augmentation Method for Improving Bi-Encoders for Pairwise Sentence Scoring Tasks](https://md.research.elamur.ai/free/en/papers/thakur-2021-augmented-sbert-data-augmentation-method/)

## Cite

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

```bibtex
@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}
}
```

- [← previous Automatic Word Sense Discrimination](https://md.research.elamur.ai/free/en/papers/schutze-1998-automatic-word-sense-discrimination/)
- [next → Description of the UPENN CAMP System as Used for Coreference](https://md.research.elamur.ai/free/en/papers/baldwin-1998-description-upenn-camp-system-as/)
- [↑ back to papers of 1998](https://md.research.elamur.ai/free/en/papers/1998/)

## 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](https://scholar.google.com/scholar?q=V%2E+Castelli+and+T%2EM%2E+Cover%2E+On+the+exponential+value+of+labeled+samples%2E+Pattern+Recognition+Letters+%2C+16%3A105%7B111%2C+January+1995%2E)
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](https://scholar.google.com/scholar?q=V%2E+Castelli+and+T%2EM%2E+Cover%2E+The+relative+value+of+labeled+and+unlabeled+samples+in+pattern%2Drecognition+with+an+unknown+mixing+parameter%2E+IEEE+Transactions+on+Information+Theory+%2C+42%286%29%3A2102%7B2117%2C+Nove)
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](https://scholar.google.com/scholar?q=M%2E+Craven%2C+D%2E+Freitag%2C+A%2E+McCallum%2C+T%2E+Mitchell%2C+K%2E+Nigam%2C+and+C%2EY%2E+Quek%2E+Learning+to+extract+symbolic+knowledge+from+the+world+wide+web%2E+Technical+report%2C+Carnegie+Mellon+University%2C+January+1997%2E)
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](https://scholar.google.com/scholar?q=S%2E+E%2E+Decatur%2E+PAC+learning+with+constant%2Dpartition+classi+cation+noise+and+applications+to+decision+tree+induction%2E+In+Proceedings+of+the+Fourteenth+International+Conference+on+Machine+Learning+%2C+pag)
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](https://scholar.google.com/scholar?q=A%2EP%2E+Dempster%2C+N%2EM%2E+Laird%2C+and+D%2EB%2E+Rubin%2E+Maximum+likelihood+from+incomplete+data+via+the+EM+algorithm%2E+Journal+of+the+Royal+Statistical+Society+B+%2C+39%3A1%7B38%2C+1977%2E)
6. Richard O. Duda and Peter E. Hart. Pattern Classi cation and Scene Analysis . Wiley, 1973. [find](https://scholar.google.com/scholar?q=Richard+O%2E+Duda+and+Peter+E%2E+Hart%2E+Pattern+Classi+cation+and+Scene+Analysis+%2E+Wiley%2C+1973%2E)
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](https://scholar.google.com/scholar?q=Z%2E+Ghahramani+and+M%2E+I%2E+Jordan%2E+Supervised+learning+from+incomplete+data+via+an+EM+approach%2E+In+Advances+in+Neural+Information+Processing+Systems+%28NIPS+6%29+%2E+Morgan+Kau+man%2C+1994%2E)
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](https://scholar.google.com/scholar?q=S%2E+A%2E+Goldman+and+M%2E+J%2E+Kearns%2E+On+the+complexity+of+teaching%2E+Journal+of+Computer+and+System+Sciences+%2C+50%281%29%3A20%7B31%2C+February+1995%2E)
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](https://scholar.google.com/scholar?q=A%2EG%2E+Hauptmann+and+M%2EJ%2E+Witbrock%2E+Informedia%3A+News%2Don%2Ddemand+%2D+multimedia+information+acquisition+and+retrieval%2E+In+M%2E+Maybury%2C+editor%2C+Intelligent+Multimedia+Information+Retrieval+%2C+1997%2E)
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](https://scholar.google.com/scholar?q=J%2E+Jackson+and+A%2E+Tomkins%2E+A+computational+model+of+teaching%2E+In+Proceedings+of+the+Fifth+Annual+Workshop+on+Computational+Learning+Theory+%2C+pages+319%7B326%2E+Morgan+Kaufmann%2C+1992%2E)
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](https://scholar.google.com/scholar?q=D%2E+R%2E+Karger%2E+Random+sampling+in+cut%2C+ow%2C+and+network+design+problems%2E+In+Proceedings+of+the+Twenty%2DSixth+Annual+ACM+Symposium+on+the+Theory+of+Computing+%2C+pages+648%7B657%2C+May+1994%2E)
12. D. R. Karger. Random sampling in cut, ow, and network design problems. Journal version draft, 1997. [find](https://scholar.google.com/scholar?q=D%2E+R%2E+Karger%2E+Random+sampling+in+cut%2C+ow%2C+and+network+design+problems%2E+Journal+version+draft%2C+1997%2E)
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](https://scholar.google.com/scholar?q=M%2E+Kearns%2E+E%0Ecient+noise%2Dtolerant+learning+from+statistical+queries%2E+In+Proceedings+of+the+Twenty%2DFifth+Annual+ACM+Symposium+on+Theory+of+Computing+%2C+pages+392%7B401%2C+1993%2E)
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](https://scholar.google.com/scholar?q=D%2E+D%2E+Lewis+and+M%2E+Ringuette%2E+A+comparison+of+two+learning+algorithms+for+text+categorization%2E+In+Third+Annual+Symposium+on+Document+Analysis+and+Information+Retrieval+%2C+pages+81%7B93%2C+1994%2E)
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](https://scholar.google.com/scholar?q=Joel+Ratsaby+and+Santosh+S%2E+Venkatesh%2E+Learning+from+a+mixture+of+labeled+and+unlabeled+examples+with+parametric+side+information%2E+In+Proceedings+of+the+8th+Annual+Conference+on+Computational+Learning)
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](https://scholar.google.com/scholar?q=M%2EJ%2E+Witbrock+and+A%2EG%2E+Hauptmann%2E+Improving+acoustic+models+by+watching+television%2E+Technical+Report+CMU%2DCS%2D98%2D110%2C+Carnegie+Mellon+University%2C+March+19+1998%2E)
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](https://scholar.google.com/scholar?q=D%2E+Yarowsky%2E+Unsupervised+word+sense+disambiguation+rivaling+supervised+methods%2E+In+Proceedings+of+the+33rd+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%2C+pages+189%7B196%2C+1995%2E) [our card](https://md.research.elamur.ai/free/en/papers/yarowsky-1995-unsupervised-word-sense-disambiguation-rivaling/)