Co-EM support vector learning

ABSTRACT

Multi-view algorithms, such as co-training and co-EM, utilize unlabeled data when the available attributes can be split into independent and compatible subsets. Co-EM outperforms co-training for many problems, but it requires the underlying learner to estimate class probabilities, and to learn from probabilistically labeled data. Therefore, co-EM has so far only been studied with naive Bayesian learners. We cast linear classifiers into a probabilistic framework and develop a co-EM version of the Support Vector Machine. We conduct experiments on text classification problems and compare the family of semi-supervised support vector algorithms under different conditions, including violations of the assumptions underlying multi-view learning. For some problems, such as course web page classification, we observe the most accurate results reported so far.

REFERENCES

• 1: Shumeet Baluja, Probabilistic modeling for face orientation discrimination: learning from labeled and unlabeled data, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.854-860, July 1999
• 2: Kristin P. Bennett, Combining support vector and mathematical programming methods for classification, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 3: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 4: Bradley, A. (1997). The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognition, 30, 1145--1159.
• 5: Brefeld, U., Geibel, P., & Wysotzki, F. (2003). Support vector machines with example dependent costs. Proceedings of the European Conference on Machine Learning.
• 6: Collins, M., & Singer, Y. (1999). Unsupervised models for named entity classification. Proceedings of the Conference on Empirical Methods in Natural Language Processing.
• 7: Cooper, D., & Freeman, J. (1970). On the asymptotic improvement in the outcome of supervised learning provided by additional nonsupervised learning. IEEE Transactions on Computers, C-19, 1055--1063.
• 8: Cozman, F., Cohen, I., & Cirelo, M. (2003). Semi-supervised learning of mixture models. Proceedings of the International Conference on Machine Learning (pp. 99--106).
• 9: Dempster, A., Laird, N., & Rubin, D. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society B, 39.
• 10: Denis, F., Laurent, A., Gilleron, R., & Tommasi, M. (2003). Text classification and co-training from positive and unlabeled examples. ICML Workshop on the Continuum from Labeled to Unlabeled Data.
• 11: Rayid Ghani, Combining Labeled and Unlabeled Data for MultiClass Text Categorization, Proceedings of the Nineteenth International Conference on Machine Learning, p.187-194, July 08-12, 2002
• 12: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 13: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 14: Joachims, T. (2003). Transductive learning via spectral graph partitioning. Proceedings of the International Conference on Machine Learning.
• 15: Kiritchenko, S., & Matwin, S. (2002). Email classification with co-training (Technical Report). University of Ottawa.
• 16: Kockelkorn, M., Lüneburg, A., & Scheffer, T. (2003). Using transduction and multi-view learning to answer emails. Proceedings of the European Conference on Principle and Practice of Knowledge Discovery in Databases.
• 17: Andrew McCallum , Kamal Nigam, Employing EM and Pool-Based Active Learning for Text Classification, Proceedings of the Fifteenth International Conference on Machine Learning, p.350-358, July 24-27, 1998
• 18: Dunja Mladenic, Learning word normalization using word suffix and context from unlabeled data, Proceedings of the Nineteenth International Conference on Machine Learning, p.427-434, July 08-12, 2002
• 19: Ion Muslea , Steven Minton , Craig A. Knoblock, Active + Semi-supervised Learning = Robust Multi-View Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.435-442, July 08-12, 2002
• 20: Ion Muslea , Steven Minton , Craig A. Knoblock, Adaptive View Validation: A First Step Towards Automatic View Detection, Proceedings of the Nineteenth International Conference on Machine Learning, p.443-450, July 08-12, 2002
• 21: Kamal Nigam , Rayid Ghani, Analyzing the effectiveness and applicability of co-training, Proceedings of the ninth international conference on Information and knowledge management, p.86-93, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354805]
• 22: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 23: Foster J. Provost , Tom Fawcett , Ron Kohavi, The Case against Accuracy Estimation for Comparing Induction Algorithms, Proceedings of the Fifteenth International Conference on Machine Learning, p.445-453, July 24-27, 1998
• 24: Seeger, M. (2001). Learning with labeled and unlabeled data. (Technical Report). University of Edinburgh.
• 25: 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, 1087--1095.
• 26: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995