Elamur Research⌕
☰
home / papers / 2000 / Text Classification from Labeled and Unlabeled Documents using EM

Text Classification from Labeled and Unlabeled Documents using EM

Paper · 2000 · Kamal Nigam, Andrew McCallum, Sebastian Thrun et al.

Summary

Labels for text classification are costly to produce, but unlabeled documents are usually cheap and plentiful. This paper asks whether a large unlabeled pool can make up for having only a few labeled examples. The authors pair a multinomial naive Bayes classifier with Expectation-Maximization (EM). A first model is trained on the labeled set and then gives soft class labels to the unlabeled documents. The model is retrained on everything, and the two steps repeat until convergence. Basic EM helps when the data really follow the model's mixture assumptions, but real text often does not, and EM can then reduce accuracy. Two extensions address this: a weight λ that controls how much unlabeled data counts (EM-λ), and several mixture components per class. Experiments used three domains: UseNet newsgroups, web pages and Reuters newswire. Adding unlabeled data reduced classification error by up to 30%. This matters wherever collecting text is easy but annotation is the bottleneck.

Key points

  • On the newsgroup task, a supervised learner needs 2000 labeled articles to reach 70% accuracy. With 10,000 unlabeled articles added, the same accuracy needs only about 600 labeled ones, more than three times fewer.
  • With just 40 labeled newsgroup documents (two per class), unlabeled data raised accuracy from 27% to 43%.
  • Newsgroups and web pages are multi-class problems with reasonably frequent classes. Reuters is handled as binary tasks, with the positive class making up between 1% and 30% of documents.
  • The theoretical motivation is a mixture of Gaussians. Unlabeled data alone can, in principle, recover the components, and labeled data then only needs to assign each component to a class. That second step converges exponentially fast (Castelli & Cover).
  • Significance testing depends on the setting. Small-label settings use several trials with paired t-tests, and large-label settings use a single trial with a McNemar test.

Interesting ideas

  • I1. Down-weighting unlabeled data (λ): Scaling how much pseudo-labeled examples contribute to the parameter estimates keeps a mismatched model from being dragged off course. This works as a cheap safety knob for any self-training or pseudo-labeling pipeline, for example on low-resource Ukrainian corpora.
  • I2. Several components per class: Letting one class be a mixture of sub-topics relaxes the assumption that one class equals one cluster. This is useful for broad, heterogeneous categories such as "trade news" that are really several distinct themes.
  • I3. Soft labels instead of hard ones: Unlabeled documents enter training with probabilistic class memberships rather than committed guesses. This limits how much early mistakes reinforce themselves across iterations.
  • I4. Ranking words by weighted log likelihood ratio: This score is each word's contribution to the KL divergence between a class and its complement. It is a principled way to inspect which words a model (or EM) has learned to associate with a class.
  • I5. Evaluating at different label budgets: Measuring gains across a range of labeled-set sizes shows where unlabeled data helps most, which is usually the very-few-labels regime. That tells you how much annotation is worth paying for.

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

 Institutions

🎓Carnegie Mellon UniversityPittsburgh · United States539 works · 179,533 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

💡 Concepts 1Key ideas and methods explained on our concept pages.Text classification · 50 works

Cite

Cite as Kamal Nigam, Andrew McCallum, Sebastian Thrun and Tom Mitchell. 2000. Text Classification from Labeled and Unlabeled Documents using EM. Machine Learning 39.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1023/a:1007692713085

@inproceedings{nigam2000text,
  title = {{Text Classification from Labeled and Unlabeled Documents using EM}},
  author = {Kamal Nigam, Andrew McCallum, Sebastian Thrun and Tom Mitchell},
  booktitle = {Machine Learning 39},
  year = {2000},
  doi = {10.1023/a:1007692713085},
  url = {https://doi.org/10.1023/a:1007692713085}
}

References

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

  1. Blum, A., & Mitchell, T. (1998). Combining labeled and unlabeled data with co-training. In Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT ’98), pp. 92–100.
  2. Castelli, V., & Cover, T. M. (1995). On the exponential value of labeled samples. Pattern Recognition Letters, 16 (1), 105–111. find
  3. Cheeseman, P., & Stutz, J. (1996). Bayesian classification (AutoClass): Theory and results. In Fayyad, U., Piatetsky-Shapiro, G., Smyth, P., & Uthurusamy, R. (Eds.), Advances in Knowledge Discovery and Data Mining. MIT Press. find
  4. Cohen, W. W., & Singer, Y. (1996). Context-sensitive learning methods for text categorization. In SIGIR ’96: Proceedings of the Nineteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 307– 315. find
  5. Cover, T. M., & Thomas, J. A. (1991). Elements of Information Theory. John Wiley and Sons, New York. find
  6. Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K., & Slattery, S. (1998). Learning to extract symbolic knowledge from the World Wide Web. In Proceedings of the Fifteenth National Conference on Artificial Intellligence (AAAI-98), pp. 509–516. find
  7. Dagan, I., & Engelson, S. P. (1995). Committee-based sampling for training probabilistic classifiers. In Machine Learning: Proceedings of the Twelfth International Conference (ICML ’95), pp. 150–157. find
  8. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39 (1), 1–38. find
  9. Dietterich, T. G. (1998). Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10 (7). find
  10. Domingos, P., & Pazzani, M. (1997). On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning, 29, 103–130. find
  11. Friedman, J. H. (1997). On bias, variance, 0/1-loss, and the curse-of-dimensionality. Data Mining and Knowledge Discovery, 1 (1), 55–77. find
  12. Ghahramani, Z., & Jordan, M. I. (1994). Supervised learning from incomplete data via an EM approach. In Advances in Neural Information Processing Systems 6, pp. 120–127. find
  13. Jaakkola, T. S., & Jordan, M. I. (1998). Improving the mean field approximation via the use of mixture distributions. In Jordan, M. I. (Ed.), Learning in Graphical Models. Kluwer Academic Publishers. find
  14. Joachims, T. (1997). A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization. In Machine Learning: Proceedings of the Fourteenth International Conference (ICML ’97), pp. 143–151. find
  15. Joachims, T. (1998). Text categorization with Support Vector Machines: Learning with many relevant features. In Machine Learning: ECML-98, Tenth European Conference on Machine Learning, pp. 137–142.
  16. Koller, D., & Sahami, M. (1997). Hierarchically classifying documents using very few words. In Machine Learning: Proceedings of the Fourteenth International Conference (ICML ’97), pp. 170–178. find
  17. Lang, K. (1995). Newsweeder: Learning to filter netnews. In Machine Learning: Proceedings of the Twelfth International Conference (ICML ’95), pp. 331–339. find
  18. Larkey, L. S., & Croft, W. B. (1996). Combining classifiers in text categorization. In SIGIR ’96: Proceedings of the Nineteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 289–297. find
  19. Lewis, D. D. (1992). An evaluation of phrasal and clustered representations on a text categorization task. In SIGIR ’92: Proceedings of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 37–50. find
  20. Lewis, D. D. (1995). A sequential algorithm for training text classifiers: Corrigendum and additional data. SIGIR Forum, 29 (2), 13–19. find
  21. Lewis, D. D. (1998). Naive (Bayes) at forty: The independence assumption in information retrieval. In Machine Learning: ECML-98, Tenth European Conference on Machine Learning, pp. 4–15. find
  22. Lewis, D. D., & Gale, W. A. (1994). A sequential algorithm for training text classifiers. In SIGIR ’94: Proceedings of the Seventeenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 3–12. find
  23. Lewis, D. D., & Knowles, K. A. (1997). Threading electronic mail: A preliminary study. Information Processing and Management, 33 (2), 209–217. find
  24. Lewis, D. D., & Ringuette, M. (1994). A comparison of two learning algorithms for text categorization. In Third Annual Symposium on Document Analysis and Information Retrieval, pp. 81–93. find
  25. Li, H., & Yamanishi, K. (1997). Document classification using a finite mixture model. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics, pp. 39–47. find
  26. Liere, R., & Tadepalli, P. (1997). Active learning with committees for text categorization. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), pp. 591–596. find
  27. McCallum, A., & Nigam, K. (1998). A comparison of event models for naive Bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization. Tech. rep. WS-98-05, AAAI Press. http://www.cs.cmu.edu/∼mccallum. ↗
  28. NIGAM, MCCALLUM, THRUN AND MITCHELL TEXT CLASSIFICATION FROM LABELED AND UNLABELED DOCUMENTS USING EM 33 find
  29. McCallum, A., Rosenfeld, R., Mitchell, T., & Ng, A. (1998). Improving text clasification by shrinkage in a hierarchy of classes. In Machine Learning: Proceedings of the Fifteenth International Conference (ICML ’98), pp. 359–367. find
  30. McCallum, A. K., & Nigam, K. (1998). Employing EM in pool-based active learning for text classification. In Machine Learning: Proceedings of the Fifteenth International Conference (ICML ’98), pp. 350–358. find
  31. McLachlan, G. J., & Krishnan, T. (1997). The EM Algorithm and Extensions. John Wiley and Sons, New York. find
  32. McLachlan, G., & Basford, K. (1988). Mixture Models. Marcel Dekker, New York. find
  33. Miller, D. J., & Uyar, H. S. (1997). A mixture of experts classifier with learning based on both labelled and unlabelled data. In Advances in Neural Information Processing Systems 9, pp. 571–577. find
  34. Mitchell, T. M. (1997). Machine Learning. McGraw-Hill, New York. find
  35. Ng, A. Y. (1997). Preventing “overfitting” of cross-validation data. In Machine Learning: Proceedings of the Fourteenth International Conference (ICML ’97), pp. 245–253. find
  36. Pazzani, M. J., Muramatsu, J., & Billsus, D. (1996). Syskill & Webert: Identifying interesting Web sites. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), pp. 54–59. find
  37. Rissanen, J. (1983). A universal prior for integers and estimation by minimum description length. Annals of Statistics, 11 (2), 416–431. find
  38. Robertson, S. E., & Sparck-Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27 (3), 129–146. find
  39. Rocchio, J. (1971). Relevance feedback in information retrieval. In Salton, G. (Ed.), The SMART Retrieval System:Experiments in Automatic Document Processing. Prentice Hall, Englewood Cliffs, NJ. find
  40. Sahami, M., Dumais, S., Heckerman, D., & Horvitz, E. (1998). A Baysian approach to filtering junk e-mail. In AAAI-98 Workshop on Learning for Text Categorization. Tech. rep. WS-98-05, AAAI Press. http://robotics.stanford.edu/users/sahami/papers.html. ↗
  41. Salton, G. (1991). Developments in automatic text retrieval. Science, 253 (5023), 974–980. find
  42. Schuurmans, D. (1997). A new metric-based approach to model selection. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), pp. 552–558. find
  43. Shahshahani, B., & Landgrebe, D. (1994). The effect of unlabeled samples in reducing the small sample size problem and mitigating the Hughes phenomenon. IEEE Transactions on Geoscience and Remote Sensing, 32 (5), 1087–1095. find
  44. Shavlik, J., & Eliassi-Rad, T. (1998). Intelligent agents for web-based tasks: An advice-taking approach. In AAAI-98 Workshop on Learning for Text Categorization. Tech. rep. WS-98-05, AAAI Press. http://www.cs.wisc.edu/∼shavlik/mlrg/publications.html. ↗
  45. Stolcke, A., & Omohundro, S. M. (1994). Best-first model merging for hidden Markov model induction. Tech. rep. TR-94-003, ICSI, University of California, Berkeley. http://www.icsi.berkeley.edu/techreports/1994.html. ↗
  46. Yang, Y. (1994). Expert network: Effective and efficient learning from human decisions in text categorization and retrieval.. In SIGIR ’94: Proceedings of the Seventeenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 13–22. find
  47. Yang, Y. (1999). An evaluation of statistical approaches to text categorization. Journal of Information Retrieval. To appear. find
  48. Yang, Y., & Pederson, J. O. (1997). Feature selection in statistical learning of text categorization. In Machine Learning: Proceedings of the Fourteenth International Conference (ICML ’97), pp. 412–420. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nigam-2000-text-classification-labeled-unlabeled-em/