Article

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

Authors:

John LaffertyAuthors Info & Claims

ICML '05: Proceedings of the 22nd international conference on Machine learning

Pages 1052 - 1059

https://doi.org/10.1145/1102351.1102484

Published: 07 August 2005 Publication History

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]

Blum, A., & Chawla, S. (2001). Learning from labeled and unlabeled data using graph mincuts. Proc. 18th International Conf. on Machine Learning.

Digital Library

[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]

Fowlkes, C., Belongie, S., Chung, F., & Malik, J. (2004). Spectral grouping using the Nyströöm method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26, 214--225.

Digital Library

[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]

Nigam, K., McCallum, A. K., Thrun, S., & Mitchell, T. (2000). Text classification from labeled and unlabeled documents using EM. Machine Learning, 39, 103--134.

Digital Library

[10]

Ratsaby, J., & Venkatesh, S. (1995). Learning from a mixture of labeled and unlabeled examples with parametric side information. Proceedings of the Eighth Annual Conference on Computational Learning Theory, 412--417.

Digital Library

[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]

Weinberger, K. Q., Sha, F., & Saul, L. K. (2004). Learning a kernel matrix for nonlinear dimensionality reduction. Proceedings of ICML-04 (pp. 839--846).

Digital Library

[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.

Cited By

Peng ZZheng GHuang W(2024)Semi-Supervised Learning with Close-Form Label Propagation Using a Bipartite GraphSymmetry10.3390/sym1610131216:10(1312)Online publication date: 4-Oct-2024
https://doi.org/10.3390/sym16101312
Dornaika FIbrahim ZBosaghzadeh A(2024)Scalable and Inductive Semi-supervised Classifier with Sample Weighting Based on Graph TopologyACM Transactions on Knowledge Discovery from Data10.1145/364364518:5(1-18)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3643645
Gaw NLi JYoon H(2024)A Novel Semi-Supervised Learning Model for Smartphone-Based Health TelemonitoringIEEE Transactions on Automation Science and Engineering10.1109/TASE.2022.321813221:1(428-441)Online publication date: Jan-2024
https://doi.org/10.1109/TASE.2022.3218132
Show More Cited By

Recommendations

Soft constraint harmonic energy minimization for transductive learning and its two interpretations

Using the labeled and unlabeled data to enhance the performance of classification is the core idea of transductive learning, It has recently attracted much interest of researchers on this topic. In this paper, we extend the harmonic energy minimization ...
Semi-supervised dimensionality reduction via harmonic functions
MDAI'11: Proceedings of the 8th international conference on Modeling decisions for artificial intelligence

Traditional unsupervised dimensionality reduction techniques are widely used in many learning tasks, such as text classification and face recognition. However, in many applications, a few labeled examples are readily available. Thus, semi-supervised ...
Conditional bernoulli mixtures for multi-label classification
ICML'16: Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48

Multi-label classification is an important machine learning task wherein one assigns a subset of candidate labels to an object. In this paper, we propose a new multi-label classification method based on Conditional Bernoulli Mixtures. Our proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '05: Proceedings of the 22nd international conference on Machine learning

August 2005

1113 pages

ISBN:1595931805

DOI:10.1145/1102351

General Chair:
Saso Dzeroski
Jozef Stefan Institute, Slovenia
,
Program Chairs:
Luc De Raedt,
Stefan Wrobel

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

98
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peng ZZheng GHuang W(2024)Semi-Supervised Learning with Close-Form Label Propagation Using a Bipartite GraphSymmetry10.3390/sym1610131216:10(1312)Online publication date: 4-Oct-2024
https://doi.org/10.3390/sym16101312
Dornaika FIbrahim ZBosaghzadeh A(2024)Scalable and Inductive Semi-supervised Classifier with Sample Weighting Based on Graph TopologyACM Transactions on Knowledge Discovery from Data10.1145/364364518:5(1-18)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3643645
Gaw NLi JYoon H(2024)A Novel Semi-Supervised Learning Model for Smartphone-Based Health TelemonitoringIEEE Transactions on Automation Science and Engineering10.1109/TASE.2022.321813221:1(428-441)Online publication date: Jan-2024
https://doi.org/10.1109/TASE.2022.3218132
Zhang YJi SZou CZhao XYing SGao Y(2023)Graph Learning on Millions of Data in Seconds: Label Propagation Acceleration on Graph Using Data DistributionIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.316689445:2(1835-1847)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TPAMI.2022.3166894
Zhang WWu QYang Y(2023)Semisupervised Manifold Regularization via a Subnetwork-Based Representation Learning ModelIEEE Transactions on Cybernetics10.1109/TCYB.2022.317757353:11(6923-6936)Online publication date: Nov-2023
https://doi.org/10.1109/TCYB.2022.3177573
Xiao YBo YZheng Z(2023)Speech Emotion Recognition based on Semi-Supervised Adversarial Variational Autoencoder2023 IEEE 10th International Conference on Cyber Security and Cloud Computing (CSCloud)/2023 IEEE 9th International Conference on Edge Computing and Scalable Cloud (EdgeCom)10.1109/CSCloud-EdgeCom58631.2023.00054(275-280)Online publication date: Jul-2023
https://doi.org/10.1109/CSCloud-EdgeCom58631.2023.00054
Jhee JKim MPark MYeon JKwak YShin H(2023)Fast Prediction for Suspect Candidates from Criminal Networks2023 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BigComp57234.2023.00080(353-355)Online publication date: Feb-2023
https://doi.org/10.1109/BigComp57234.2023.00080
Ibrahim ZBosaghzadeh ADornaika F(2023)Joint graph and reduced flexible manifold embedding for scalable semi-supervised learningArtificial Intelligence Review10.1007/s10462-023-10397-456:9(9471-9495)Online publication date: 2-Feb-2023
https://doi.org/10.1007/s10462-023-10397-4
Huang GDu C(2022)The High Separation Probability Assumption for Semi-Supervised LearningIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2022.316106752:12(7561-7573)Online publication date: Dec-2022
https://doi.org/10.1109/TSMC.2022.3161067
Liu CNie FWang RLi X(2022)Scalable Fuzzy Clustering With Anchor GraphIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3200685(1-11)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3200685
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents