Pointwise manifold regularization for semi-supervised learning

Abstract

Manifold regularization (MR) provides a powerful framework for semi-supervised classification using both the labeled and unlabeled data. It constrains that similar instances over the manifold graph should share similar classification outputs according to the manifold assumption. It is easily noted that MR is built on the pairwise smoothness over the manifold graph, i.e., the smoothness constraint is implemented over all instance pairs and actually considers each instance pair as a single operand. However, the smoothness can be pointwise in nature, that is, the smoothness shall inherently occur “everywhere” to relate the behavior of each point or instance to that of its close neighbors. Thus in this paper, we attempt to develop a pointwise MR (PW_MR for short) for semi-supervised learning through constraining on individual local instances. In this way, the pointwise nature of smoothness is preserved, and moreover, by considering individual instances rather than instance pairs, the importance or contribution of individual instances can be introduced. Such importance can be described by the confidence for correct prediction, or the local density, for example. PW_MR provides a different way for implementing manifold smoothness. Finally, empirical results show the competitiveness of PW_MR compared to pairwise MR.

Keywords

semi-supervised classification / manifold regularization / pairwise smoothness / pointwise smoothness / local density

References

[1] Zhou Z H, Li M. Semi-supervised learning by disagreement. Knowledge and Information Systems, 2010, 24(3): 415–439

[2] Zhu X J, Goldberg A B. Introduction to semi-supervised learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2009, 3(1): 1–130

[3] Zhu X J. Semi-supervised learning literature survey. Technical Report, 2005

[4] Chapelle O, Schölkopf B, Zien A. Semi-supervised Learning. Cambridge, MA: MIT Press, 2006

[5] Mallapragada P K, Jin R, Jain A K, Liu Y. Semiboost: boosting for semisupervised learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 31(11): 2000–2014

[6] Joachims T. Transductive inference for text classification using support vector machines. In: Proceedings of the 16th Annual International Conference on Machine Learning. 1999, 200–209

[7] Fung G, Mangasarian O L. Semi-supervised support vector machines for unlabeled data classification. Optimization Methods and Software, 2001, 15(1): 29–44

[8] Collobert R, Sinz F, Weston J, Bottou L. Large scale transductive SVMs. Journal of Machine Learning Research, 2006, 7(8): 1687–1712

[9] Li Y F, Kwok J T, Zhou Z H. Semi-supervised learning using label mean. In: Proceedings of the 26th Annual International Conference on Machine Learning. 2009, 633–640

[10] Bengio Y, Delalleau O, Roux N L. Label propagation and quadratic criterion. In: Chapelle O, Schölkopf B, Zien A, eds. Semi-supervised Learning. Cambridge, MA: MIT Press, 2006, 193–216

[11] Zhu X J, Ghahramani Z. Learning from labeled and unlabeled data with label propagation. Technical Report, 2002

[12] Blum A, Chawla S. Learning from labeled and unlabeled data using graph mincuts. In: Proceedings of the 18th Annual International Conference on Machine Learning. 2001, 19–26

[13] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 2006, 7(11): 2399–2434

[14] Chen K, Wang S H. Semi-supervised learning via regularized boosting working on multiple semi-supervised assumptions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 33(1): 129–143

[15] He X F. Laplacian regularized D-optimal design for active learning and its application to image retrieval. IEEE Transactions on Image Processing, 2009, 19(1): 254–263

[16] Abernethy J, Chapelle O, Castillo C. Web spam identification through content and hyperlinks. In: Proceedings of the 4th International Workshop on Adversarial Information Retrieval on the Web. 2008, 41–44

[17] Fang Y, Chang K C C, Lauw H W. Graph-based semi-supervised learning: realizing pointwise smoothness probabolistically. In: Proceedings of the 31st Annual International Conference on Machine Learning. 2014, 406–414

[18] Singh A, Nowak R, Zhu J. Unlabeled data: now it helps, now it doesn’t. In: Proceedings of Advances in Neural Information Processing Systems. 2009, 1513–1520

[19] Wasserman L, Lafferty J D. Statistical analysis of semi-supervised regression. In: Proceedings of Advances in Neural Information Processing Systems. 2008, 801–808

[20] Rigollet P. Generlization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 2007, 8(7): 1369–1392

[21] Wang H, Wang S B, Li Y F. Instance selection method for improving graph-based semi-supervised learning. Frontiers of Computer Science, 2018, 12(4): 725–735

[22] Gan H, Li Z, Wu W, Luo Z, Huang R. Safety-aware graph-based semisupervised learning. Expert Systems with Applications, 2018, 107: 243–254

[23] Wang Y, Meng Y, Li Y, Chen S C, Fu Z Y, Xue H. Semi-supervised manifold regularization with adaptive graph construction. Pattern Recognition Letters, 2017, 98: 90–95

[24] Gan H T, Luo Z Z, Sun Y, Xi X G, Sang N, Huang R. Towards designing risk-based safe laplacian regularized least squares. Expert Systems with Applicaions, 2016, 45: 1–7

[25] Quang M H, Bazzani L, Murino V. A unifying framework for vectorvalued manifold regularization and multi-view learning. In: Proceedings of the 30th Annual International Conference on Machine Learning. 2013, 100–108

RIGHTS & PERMISSIONS

Higher Education Press