×

zbMATH — the first resource for mathematics

Laplacian-optimized diffusion for semi-supervised learning. (English) Zbl 07200776
Summary: Semi-supervised learning (SSL) is fundamentally a geometric task: in order to classify high-dimensional point sets when only a small fraction of data points are labeled, the geometry of the unlabeled data points is exploited to gain better classifying accuracy. A number of state-of-the-art SSL techniques rely on label propagation through graph-based diffusion, with edge weights that are evaluated either analytically from the data or through compute-intensive training based on nonlinear and nonconvex optimization. In this paper, we bring discrete differential geometry to bear on this problem by introducing a graph-based SSL approach where label diffusion uses a Laplacian operator learned from the geometry of the input data. From a data-dependent graph of the input, we formulate a biconvex loss function in terms of graph edge weights and inferred labels. Its minimization is achieved through alternating rounds of optimization of the Laplacian and diffusion-based inference of labels. The resulting optimized Laplacian diffusion directionally adapts to the intrinsic geometric structure of the data which often concentrates in clusters or around low-dimensional manifolds within the high-dimensional representation space. We show on a range of classical datasets that our variational classification is more accurate than current graph-based SSL techniques. The algorithmic simplicity and efficiency of our discrete differential geometric approach (limited to basic linear algebra operations) also make it attractive, despite the seemingly complex task of optimizing all the edge weights of a graph.
MSC:
65D Numerical approximation and computational geometry (primarily algorithms)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abadi, M.; Agarwal, A.; Barham, P.; Brevdo, E.; Chen, Z.; Citro, C.; Corrado, G. S.; Davis, A.; Dean, J.; Devin, M.; Ghemawat, S.; Goodfellow, I.; Harp, A.; Irving, G.; Isard, M.; Jia, Y.; Jozefowicz, R.; Kaiser, L.; Kudlur, M.; Levenberg, J.; Mané, D.; Monga, R.; Moore, S.; Murray, D.; Olah, C.; Schuster, M.; Shlens, J.; Steiner, B.; Sutskever, I.; Talwar, K.; Tucker, P.; Vanhoucke, V.; Vasudevan, V.; Viégas, F.; Vinyals, O.; Warden, P.; Wattenberg, M.; Wicke, M.; Yu, Y.; Zheng, X., TensorFlow: large-scale machine learning on heterogeneous systems (2015)
[2] Abraham, R.; Marsden, J.; Ratiu, T., Manifolds, Tensor Analysis, and Applications, Applied Mathematical Sciences, vol. 75 (1988), Springer-Verlag · Zbl 0875.58002
[3] Beck, A.; Teboulle, M., Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett., 31, 167-175 (2003) · Zbl 1046.90057
[4] Belkin, M.; Niyogi, P., Semi-supervised learning on Riemannian manifolds, Mach. Learn., 56, 209-239 (2004) · Zbl 1089.68086
[5] Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularization: a geometric framework for learning from labeled and unlabeled examples, J. Mach. Learn. Res., 7, 2399-2434 (2006) · Zbl 1222.68144
[6] Blum, A.; Chawla, S., Learning from labeled and unlabeled data using graph mincuts, (ICML (2001)), 19-26
[7] Bossavit, A., Computational Electromagnetism (1998), Academic Press · Zbl 0945.78001
[8] Budninskiy, M.; Liu, B.; Tong, Y.; Desbrun, M., Spectral affine-kernel embeddings, Comput. Graph. Forum, 36, 117-129 (2017)
[9] Budninskiy, M.; Yin, G.; Feng, L.; Tong, Y.; Desbrun, M., Parallel transport unfolding: a connection-based manifold learning approach, SIAM J. Appl. Algebra Geom., 3, 266-291 (2019) · Zbl 1425.53019
[10] Chapelle, O.; Schlkopf, B.; Zien, A., Semi-Supervised Learning (2010), MIT Press
[11] Crane, K.; de Goes, F.; Desbrun, M.; Schröder, P., Digital geometry processing with discrete exterior calculus, (ACM SIGGRAPH 2013 Course Notes (2013))
[12] Csiszár, I.; Tusnády, G., Information geometry and alternating minimization procedures, Stat. Decis., 1, Supplement Issue, 205-237 (1984) · Zbl 0547.60004
[13] Dempster, A. P.; Laird, N. M.; Rubin, D. B., Maximum likelihood from incomplete data via the em algorithm, J. R. Stat. Soc., Ser. B, Methodol., 39, 1-38 (1977) · Zbl 0364.62022
[14] Desbrun, M.; Kanso, E.; Tong, Y., Discrete differential forms for computational modeling, (Bobenko; etal., Discrete Differential Geometry (2008), Birkhäuser: Birkhäuser Basel), 287-324 · Zbl 1152.58001
[15] Desbrun, M.; Meyer, M.; Schröder, P.; Barr, A., Implicit fairing of irregular meshes using diffusion and curvature flow, (ACM SIGGRAPH (1999)), 317-324
[16] Dheeru, D.; Taniskidou, E. K., UCI Machine Learning Repository (2017), U. of California: U. of California Irvine
[17] Georghiades, A. S.; Belhumeur, P. N.; Kriegman, D. J., From few to many, IEEE Trans. Pattern Anal. Mach. Intell., 23, 643-660 (2001)
[18] Grant, M.; Boyd, S., CVX: Matlab software for disciplined convex programming, version 2.1 (2014)
[19] Karasuyama, M.; Mamitsuka, H., Adaptive edge weighting for graph-based learning algorithms, Mach. Learn., 106, 307-335 (2017) · Zbl 06737823
[20] Kipf, T.; Welling, M., Semi-supervised classification with graph convolutional networks, (International Conference on Learning Representations (2017)), 1-14
[21] Nene, S. A.; Nayar, S. K.; Murase, H., Columbia Object Image Library (COIL-20) (1996), Columbia University, Technical Report CUCS-005-96
[22] Olah, C., Neural networks, manifolds, and topology from Colah’s blog (2014)
[23] Playground, T., Playground (2018)
[24] Rasmus, A.; Valpola, H.; Honkala, M.; Berglund, M.; Raiko, T., Semi-supervised learning with ladder networks, (NIPS (2015)), 3546-3554
[25] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326 (2000)
[26] Rustamov, R. M.; Klosowski, J. T., Interpretable graph-based semi-supervised learning via flows, (AAAI Conference on Artificial Intelligence (2018)), 3976-3983
[27] Shah, S. A.; Koltun, V., Robust continuous clustering, Proc. Natl. Acad. Sci., 114, 9814-9819 (2017)
[28] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22, 888-905 (2000)
[29] Sindhwani, V.; Belkin, M.; Niyogi, P., Semi-supervised Learning, 35-54 (2010), Chapter: The geometric basis of SSL. In: Chapelle et al. (2010)
[30] Solomon, J.; Rustamov, R. M.; Guibas, L.; Butscher, A., Wasserstein propagation for semi-supervised learning, (ICML (2014)), 306-314
[31] de Sousa, C. A.R., An overview on the Gaussian fields and harmonic functions method for semi-supervised learning, (Int. Joint Conf. on Neural Networks (2015)), 1-8
[32] Stellato, B.; Banjac, G.; Goulart, P.; Bemporad, A.; Boyd, S., OSQP: an operator splitting solver for quadratic programs (2017), ArXiv e-prints
[33] Subramanya, A.; Bilmes, J., Semi-supervised learning with measure propagation, J. Mach. Learn. Res., 12, 3311-3370 (2011) · Zbl 1280.68200
[34] Vesely, K.; Hannemann, M.; Burget, L., Semi-supervised training of deep neural networks, (IEEE Workshop on Automatic Speech Recognition and Understanding (2013)), 267-272
[35] Wang, F.; Wang, J.; Zhang, C.; Shen, H. C., Semi-supervised classification using linear neighborhood propagation, (CVPR (2006)), 160-167
[36] Wang, F.; Zhang, C., Label propagation through linear neighborhoods, IEEE Trans. Knowl. Data Eng., 20, 55-67 (2008)
[37] Wang, Y.; Jiang, Y.; Wu, Y.; Zhou, Z. H., Spectral clustering on multiple manifolds, IEEE Trans. Neural Netw., 22, 1149-1161 (2011)
[38] Zelnik-Manor, L.; Perona, P., Self-tuning spectral clustering, (NIPS (2004)), 1601-1608
[39] Zhou, D.; Bousquet, O.; Lal, T. N.; Weston, J.; Schölkopf, B., Learning with local and global consistency, (NIPS (2003)), 321-328
[40] Zhou, X.; Belkin, M., Semi-supervised learning by higher order regularization, (International Conference on Artificial Intelligence and Statistics, vol. 15 (2011)), 892-900
[41] Zhu, X., Semi-Supervised Learning Literature Survey (2007), Computer Sciences, U. of Wisconsin-Madison, Technical Report 1530
[42] Zhu, X.; Ghahramani, Z.; Lafferty, J., Semi-supervised learning using Gaussian fields and harmonic functions, (ICML (2003)), 912-919
[43] Zhu, X.; Goldberg, A. B., Introduction to semi-supervised learning, Synth. Lect. Artif. Intell. Mach. Learn., 3, 1-130 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.