zbMATH — the first resource for mathematics

Error bounds of multi-graph regularized semi-supervised classification. (English) Zbl 1192.68509
Summary: We investigate the generalization performance of the multi-graph regularized semi-supervised classification algorithm associated with the hinge loss. We provide estimates for the excess misclassification error of multi-graph regularized classifiers and show the relations between the generalization performance and the structural invariants of data graphs. Experiments performed on real database demonstrate the effectiveness of our theoretical analysis.

68T05 Learning and adaptive systems in artificial intelligence
68T10 Pattern recognition, speech recognition
Full Text: DOI
[1] Argyriou, A.; Herbster, M.; Pontil, M., Combining graph Laplacians for semi-supervised learning, Nips 18, (2006), MIT Press Cambridge, MA, USA
[2] Aronszajn, N., Theory of reproducing kernels, Transactions of the American mathematical society, 68, 337-404, (1950) · Zbl 0037.20701
[3] Bartlett, P.L.; Mendelson, S., Rademacher and Gaussian complexities: risk bounds and structural results, Journal of machine learning research, 3, 463-482, (2002) · Zbl 1084.68549
[4] Belkin, M.; Matveeva, I.; Niyogi, P., Regularization and semi-supervised learning on large graphs, (), 624-638 · Zbl 1078.68685
[5] Belkin, M.; Niyogi, P., Semi-supervised learning on Riemannian manifolds, Machine learning, 56, 209-239, (2004) · Zbl 1089.68086
[6] Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularizaion: a geometric framework for learning from labeled and unlabeled examples, Journal of machine learning research, 7, 2399-2434, (2006) · Zbl 1222.68144
[7] C.L. Blake, C.J. Merz, UCI repository of machine learning databases, Irvine, CA, University of California, Department of Information and Computer Science, 1998, <http://www.ics.uci.edu/mlearn/MLRepository.html>.
[8] A. Blum, T. Mitchell, Combining labeled and unlabeled data with co-training, in: Proceedings of the Workshop on Computational Learning Theory, 1998.
[9] Chen, D.R.; Wu, Q.; Ying, Y.; Zhou, D.X., Support vector machine soft margin classifiers: error analysis, Journal of machine learning research, 5, 1143-1175, (2004) · Zbl 1222.68167
[10] Chung, F.R.K., Spectral graph theory, Regional conference series in mathematics, vol. 92, (1997), SIAM Philadelphia · Zbl 0872.05052
[11] Cucker, F.; Smale, S., On the mathematical foundations of learning, Bulletin of the American mathematical society, 39, 1-49, (2002) · Zbl 0983.68162
[12] Cucker, F.; Zhou, D.X., Learning theory: an approximation theory viewpoint, (2007), Cambridge University Press Cambridge · Zbl 1274.41001
[13] R. El-Yaniv, D. Pechyony, Stable transductive learning, in: G. Lugosi, H.U. Simon (Eds.), Proceedings of the 19th Annual Conference on Learning Theory, Pittsburgh, PA, USA, 2006, pp. 35-49. · Zbl 1143.68532
[14] Johnson, R.; Zhang, T., On the effectiveness of Laplacian normalization for graph semi-supervised learning, Journal of machine learning research, 8, 1489-1517, (2007) · Zbl 1222.68227
[15] Johnson, R.; Zhang, T., Graph-based semi-supervised learning and spectral kernel design, IEEE transactions on information theory, 54, 275-288, (2008) · Zbl 1304.68147
[16] Koprinska, I.; Poon, J.; Clark, J.; Chan, J., Learning to classify e-mail, Information sciences, 177, 2167-2187, (2007)
[17] Lafferty, J.; Wasserman, L., Challenges in statistical machine learning, Statistica sinica, 16, 307-323, (2006)
[18] Lanckriet, G.; Cristianini, N.; Bartlett, P.L.; Ghaoui, L.; Jordan, M.I., Learning the kernel matrix with semidefinite programming, Journal of machine learning research, 5, 27-72, (2004) · Zbl 1222.68241
[19] Lee, C.-H.; Zaı¨ane, O.R.; Park, H.-H.; Huang, J.; Creiner, R., Clustering high dimensional data: a graph-based relaxed optimization approach, Information sciences, 178, 4501-4511, (2008)
[20] Lingras, P.; Butz, C., Rough set based 1-v-1 and 1-v-r approaches to support vector machine multi-classification, Information sciences, 177, 3782-3798, (2007)
[21] McDiarmid, C., On the method of bounded differences, Surveys in combinatorics 1989, (1989), Cambridge University Press · Zbl 0712.05012
[22] Micchelli, C.A.; Pontil, M., Learning the kernel function via regularization, Journal of machine learning research, 6, 1099-1125, (2005) · Zbl 1222.68265
[23] Vapnik, V., Statistical learning theory, (1998), John Wiley and Sons · Zbl 0935.62007
[24] Wu, Q.; Ying, Y.; Zhou, D.X., Multi-kernel regularized classifiers, Journal of complexity, 23, 108-134, (2007) · Zbl 1171.65043
[25] X. Zhu, Semi-supervised learning literature survey, Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005.
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.