Research PaperNo Access

Generalization bounds of incremental SVM

Jingjing Zeng

https://orcid.org/0009-0008-9212-2641

School of Mathematics and Physics, Wuhan Institute of Technology, Wuhan 430205, P. R. China

Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan 430062, P. R. China

E-mail Address: zengjingjing82@sina.com

Search for more papers by this author

Bin Zou

https://orcid.org/0000-0002-8649-1538

Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, P. R. China

E-mail Address: zoubin0502@gmail.com

Corresponding author.

Search for more papers by this author

Yimo Qin

https://orcid.org/0000-0002-3382-3877

School of Mathematics and Statistics, Central South University, Changsha 410083, P. R. China

E-mail Address: qinyimo1997@163.com

Corresponding author.

Search for more papers by this author

, and

Jie Xu

https://orcid.org/0000-0001-8238-9344

Faculty of Computer Science and Information Engineering, Hubei University, Wuhan 430062, P. R. China

Hubei Key Laboratory of Big Data Intelligent, Analysis and Application, Hubei University, Wuhan 430062, P. R. China

Engineering Research Center of Hubei, Province in Intelligent Government Affairs, and Application of Artificial Intelligence, Wuhan 430062, P. R. China

E-mail Address: frangipani@hubu.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0219691324500279Cited by:0 (Source: Crossref)

Abstract

Incremental learning is one of the effective methods of learning from the accumulated training samples and the large-scale dataset. The main advantages of incremental learning consist of making full use of historical information, reducing the training scale greatly and saving space and time consumption. Despite extensive research on incremental support vector machine (SVM) learning algorithms, most of them are based on independent and identically distributed samples (i.i.d.). Not only that, there has been no theoretical analysis of incremental SVM learning algorithms. In this paper, we mainly study the generalization bounds of this incremental SVM learning algorithm whose samples are based on uniformly geometric Markov chains, and exponentially strongly mixing sequence. As a special case, we also obtain the generalization bounds of i.i.d. samples.

Keywords:

AMSC: 22E46, 53C35, 57S20

References

1. N. Aronszajn , Theory of reproducing kernels, Trans. Amer. Math. Soc. 68(3) (1950) 337–404. Crossref, Web of Science, Google Scholar
2. P. L. Bartlett, M. I. Jordan and J. D. McAuliffe , Convexity, classification, and risk bounds, J. Amer. Statist. Assoc. 101(473) (2006) 138–156. Crossref, Web of Science, Google Scholar
3. O. Bousquet and A. Elissee , Stability and generalization, J. Mach. Learn. Res. 2 (2002) 499–526. Web of Science, Google Scholar
4. G. Cauwenberghs and T. Poggio , Incremental and decremental support vector machine learning, in Proc. 13th Int. Conf. Neural Information Processing Systems (NIPS’00) (MIT Press, Cambridge, MA, USA, 2000), pp. 388–394. Google Scholar
5. D. R. Chen, Q. Wu, Y. M. Ying and D. X. Zhou , Support vector machine soft margin classifiers: Error analysis, J. Mach. Learn. Res. 5 (2004) 1143–1175. Web of Science, Google Scholar
6. F. Cucker and S. Smale , On the mathematical foundations of learning, Bull. Amer. Math. Soc. 39 (2001) 1–49. Crossref, Web of Science, Google Scholar
7. T. Evgeniou, M. Pontil and T. Poggio , Regularization networks and support vector machines, Adv. Comput. Math. 13(1) (2000) 1–50. Crossref, Web of Science, Google Scholar
8. T. Joachims , A support vector method for multivariate performance measures, in Proc. 22nd Int. Conf. Machine Learning (ICML’05) (Association for Computing Machinery, New York, USA, 2005), pp. 377–384. Crossref, Google Scholar
9. T. Joachims , Training linear SVMs in linear time, in Proc. 12th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD’06) (Association for Computing Machinery, New York, USA, 2006), pp. 217–226. Crossref, Google Scholar
10. C. H. Li, K. W. Liu and H. X. Wang , The incremental learning algorithm with support vector machine based on hyperplane-distance, Appl. Intell. 34(1) (2011) 19–27. Crossref, Web of Science, Google Scholar
11. O. L. Mangasarian and D. R. Musicant , Lagrangian support vector machines, J. Mach. Learn. Res. 1(3) (2001) 161–177. Google Scholar
12. S. Modha and E. Masry , Minimum complexity regression estimation with weakly dependent observations, IEEE Trans. Inform. Theory 42 (1996) 2133–2145. Crossref, Web of Science, Google Scholar
13. Y. Nawal et al., New incremental SVM algorithms for human activity recognition in smart homes, Ambient Intell. Hum. Comput. 14 (2023) 13433–13450. Crossref, Web of Science, Google Scholar
14. M. P. Qian and G. L. Gong , Applied Random Processes (Peking University, Beijing, China, 1998). Google Scholar
15. S. Rüping , Incremental learning with support vector machines, in Proc. 2001 IEEE Int. Conf. Data Mining (IEEE, San Jose, CA, USA, 2001), pp. 641–642. Crossref, Google Scholar
16. M. Rosenblatt , Uniform ergodicity and strong mixing, Z. Wahrscheinlichkeitstheorie verw Gebiete 24 (1972) 79–84. Crossref, Google Scholar
17. S. Smale and D. X. Zhou , Online learning with Markov sampling, Anal. Appl. 7 (2009) 87–113. Link, Web of Science, Google Scholar
18. I. Steinwart and A. Christmann , Support Vector Machines (Springer, New York, 2008). Google Scholar
19. I. Steinwart and A. Christmann , Fast learning from non-i.i.d. observations, Adv. Neural Inf. Process. Syst. 22 (2009) 1768–1776. Google Scholar
20. I. Steinwart , Consistency of support vector machines and other regularized kernel classifiers, IEEE Trans. Inform. Theory 51(1) (2005) 128–142. Crossref, Web of Science, Google Scholar
21. J. A. K. Suykens, L. Lukas and J. Vandwealle , Sparse least squares support vector machines for adaptive communication channel equalization, Internat. J. Appl. Sci. Eng. 11(3) (2005) 51–59. Google Scholar
22. J. A. K. Suykens and J. Vandewalle , Least squares support vector machine classifiers, Neural Process. Lett. 9(3) (1999) 293–300. Crossref, Web of Science, Google Scholar
23. N. A. Syed, H. Liu and K. K. Sung , Incremental learning with support vector machines, in Proc. Workshop on Support Vector Machines at the Int. Joint Conf. Articial Intelligence (Stockholm, Sweden, 1999), pp. 317–321. Google Scholar
24. H. Z. Tong, D. R. Chen and L. Z. Peng , Analysis of support vector machine regression, Found. Comput. Math. 9(2) (2009) 243–257. Crossref, Google Scholar
25. I. Tsochantaridis, T. Joachims, T. Hofmann and Y. Altun , Large margin methods for structured and interdependent output variables, J. Mach. Learn. Res. 6 (2005) 1453–1484. Web of Science, Google Scholar
26. V. Vapnik , Statistical Learning Theory (John Wiley & Sons, New York, 1998). Google Scholar
27. M. Vidyasagar , Learning and Generalization with Applications to Neural Networks, 2nd edn. (Springer, London, U. K., 2003). Crossref, Google Scholar
28. Q. Wu, Y. M. Ying and D. X. Zhou , Learning rates of least-square regularized regression, Found. Comput. Math. 6(2) (2006) 171–192. Crossref, Web of Science, Google Scholar
29. Q. Wu, Y. M. Ying and D. X. Zhou , Learning theory from regression to classification, Stud. Comput. Math. 12 (2006) 257–290. Google Scholar
30. J. Xu, C. Xu, B. Zou, Y. Y. Tang, J. Peng and X. You , New incremental learning algorithm with support vector machines, IEEE Trans. Syst. Man Cybernet. Syst. 49(11) (2019) 2230–2241. Crossref, Web of Science, Google Scholar
31. Y. L. Xu and D. R. Chen , Learning rates of regularized regression for exponentially strongly mixing sequence, J. Statist. Plann. Inference 138(7) (2008) 2180–2189. Crossref, Web of Science, Google Scholar
32. J. Xu, Y. Y. Tang, B. Zou, Z. B. Xu, L. Q. Li and Y. Lu , The generalization ability of online SVM classification based on Markov sampling, IEEE Trans. Neural Netw. Learn. Syst. 26(3) (2015) 628–639. Crossref, Web of Science, Google Scholar
33. J. Xu, Y. Y. Tang, B. Zou, Z. B. Xu, L. Q. Li and Y. Lu , The generalization ability of SVM classification based on Markov sampling, IEEE Trans. Cybernet. 45(6) (2015) 1169–1179. Crossref, Web of Science, Google Scholar
34. J. Xu, Y. Y. Tang, B. Zou, Z. B. Xu, L. Q. Li and Y. Lu , The generalization ability of online SVM classification based on Markov sampling, IEEE Trans. Cybernet. 26(3) (2015) 628–638. Google Scholar
35. Y. Ying and D. X. Zhou , Online regularized classification algorithms, IEEE Trans. Inform. Theory 52(11) (2006) 4775–4788. Crossref, Web of Science, Google Scholar
36. T. Zhang , Statistical behaviour and consistency of classification methods based on convex risk minimization, Ann. Statist. 32(1) (2004) 56–134. Crossref, Web of Science, Google Scholar
37. T. Zhang , Covering number bounds of certain regularized linear function classes, J. Mach. Learn. Res. 2 (2002) 527–550. Web of Science, Google Scholar
38. B. Zou, L. Q. Li and Z. B. Xu , The generalization performance of ERM algorithm with strongly mixing observations, Mach. Learn. 75(3) (2009) 275–295. Crossref, Web of Science, Google Scholar
39. B. Zou and L. Q. Li , The performance bounds of learning machines based on exponentially strongly mixing sequences, Comput. Math. Appl. 53(7) (2007) 1050–1058. Crossref, Web of Science, Google Scholar
40. B. Zou, Y. Y. Tang, Z. B. Xu, L. Q. Li, J. Xu and Y. Lu , The generalization performance of regularized regression algorithms based on Markov sampling, IEEE Trans. Cybernet. 44(9) (2014) 1497–1507. Crossref, Web of Science, Google Scholar
41. B. Zou, Z. B. Xu and X. Y. Chang , Generalization bounds of ERM algorithm with V-geometrically ergodic Markov chains, Adv. Comput. Math. 36 (2012) 99–114. Crossref, Web of Science, Google Scholar
42. B. Zou, Z. M. Pen and Z. B. Xu , The learning performance of support vector machine classification based on Markov sampling, Sci. China Ser.: Inform. Sci. 56(3) (2013) 1–16. Crossref, Google Scholar