Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning

ABSTRACT

Graph-based methods for semi-supervised learning have recently been shown to be promising for combining labeled and unlabeled data in classification problems. However, inference for graph-based methods often does not scale well to very large data sets, since it requires inversion of a large matrix or solution of a large linear program. Moreover, such approaches are inherently transductive, giving predictions for only those points in the unlabeled set, and not for an arbitrary test point. In this paper a new approach is presented that preserves the strengths of graph-based semi-supervised learning while overcoming the limitations of scalability and non-inductive inference, through a combination of generative mixture models and discriminative regularization using the graph Laplacian. Experimental results show that this approach preserves the accuracy of purely graph-based transductive methods when the data has "manifold structure," and at the same time achieves inductive learning with significantly reduced computational cost.

REFERENCES

• 1: Belkin, M., Matveeva, I., & Niyogi, P. (2004a). Regularization and semi-supervised learning on large graphs. COLT.
• 2: Belkin, M., Niyogi, P., & Sindhwani, V. (2004b). Manifold regularization: A geometric framework for learning from examples (Technical Report TR-2004-06). University of Chicago.
• 3: Avrim Blum , Shuchi Chawla, Learning from Labeled and Unlabeled Data using Graph Mincuts, Proceedings of the Eighteenth International Conference on Machine Learning, p.19-26, June 28-July 01, 2001
• 4: Castelli, V., & Cover, T. (1996). The relative value of labeled and unlabeled samples in pattern recognition with an unknown mixing parameter. IEEE Transactions on Information Theory, 42, 2101--2117.
• 5: Cozman, F., Cohen, I., & Cirelo, M. (2003). Semi-supervised learning of mixture models. ICML-03, 20th International Conference on Machine Learning.
• 6: Delalleau, O., Bengio, Y., & Roux, N. L. (2005). Efficient non-parametric function induction in semi-supervised learning. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTAT 2005).
• 7: Charless Fowlkes , Serge Belongie , Fan Chung , Jitendra Malik, Spectral Grouping Using the Nyström Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.214-225, January 2004 [doi>10.1109/TPAMI.2004.1262185]
• 8: Krishnapuram, B., Williams, D., Xue, Y., Hartemink, A., Carin, L., & Figueiredo, M. (2005). On semi-supervised classification. In L. K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in neural information processing systems 17. Cambridge, MA: MIT Press.
• 9: 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]
• 10: Joel Ratsaby , Santosh S. Venkatesh, Learning from a mixture of labeled and unlabeled examples with parametric side information, Proceedings of the eighth annual conference on Computational learning theory, p.412-417, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225348]
• 11: Weinberger, K. Q., Packer, B. D., & Saul, L. K. (2005). Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTAT 2005).
• 12: Kilian Q. Weinberger , Fei Sha , Lawrence K. Saul, Learning a kernel matrix for nonlinear dimensionality reduction, Proceedings of the twenty-first international conference on Machine learning, p.106, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015345]
• 13: Zhou, D., Bousquet, O., Lal, T., Weston, J., & Schlkopf, B. (2004). Learning with local and global consistency. Advances in Neural Information Processing System 16.
• 14: Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. ICML-03, 20th International Conference on Machine Learning.
• 15: Zhu, X., Kandola, J., Ghahramani, Z., & Lafferty, J. (2005). Nonparametric transforms of graph kernels for semi-supervised learning. In L. K. Saul, Y. Weiss and L. Bottou (Eds.), Advances in neural information processing systems 17. Cambridge, MA: MIT Press.