research-article

Public Access

New Incremental Learning Algorithm for Semi-Supervised Support Vector Machine

Authors:

Xiao-Tong Yuan,

Heng HuangAuthors Info & Claims

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 1475 - 1484

https://doi.org/10.1145/3219819.3220092

Published: 19 July 2018 Publication History

Abstract

Semi-supervised learning is especially important in data mining applications because it can make use of plentiful unlabeled data to train the high-quality learning models. Semi-Supervised Support Vector Machine (S3VM) is a powerful semi-supervised learning model. However, the high computational cost and non-convexity severely impede the S3VM method in large-scale applications. Although several learning algorithms were proposed for S3VM, scaling up S3VM is still an open problem. To address this challenging problem, in this paper, we propose a new incremental learning algorithm to scale up S3VM (IL-S3VM) based on the path following technique in the framework of Difference of Convex (DC) programming. The traditional DC programming based algorithms need multiple outer loops and are not suitable for incremental learning, and traditional path following algorithms are limited to convex problems. Our new IL-S3VM algorithm based on the path-following technique can directly update the solution of S3VM to converge to a local minimum within one outer loop so that the efficient incremental learning can be achieved. More importantly, we provide the finite convergence analysis for our new algorithm. To the best of our knowledge, our new IL-S3VM algorithm is the first efficient path following algorithm for a non-convex problem (i.e., S3VM) with local minimum convergence guarantee. Experimental results on a variety of benchmark datasets not only confirm the finite convergence of IL-S3VM, but also show a huge reduction of computational time compared with existing batch and incremental learning algorithms, while retaining the similar generalization performance.

References

[1]

Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.

Digital Library

[2]

Feng Cai and Vladimir Cherkassky. 2012. Generalized SMO algorithm for SVMbased multitask learning. IEEE transactions on neural networks and learning systems 23, 6 (2012), 997--1003.

[3]

Olivier Chapelle. 2007. Training a support vector machine in the primal. Neural computation 19, 5 (2007), 1155--1178.

Digital Library

[4]

Olivier Chapelle, Mingmin Chi, and Alexander Zien. 2006. A continuation method for semi-supervised SVMs. In Proceedings of the 23rd international conference on Machine learning. ACM, 185--192.

Digital Library

[5]

Olivier Chapelle, Vikas Sindhwani, and S Sathiya Keerthi. 2007. Branch and bound for semi-supervised support vector machines. In Advances in neural information processing systems. 217--224.

Digital Library

[6]

Olivier Chapelle, Vikas Sindhwani, and Sathiya S Keerthi. 2008. Optimization techniques for semi-supervised support vector machines. Journal of Machine Learning Research 9, Feb (2008), 203--233.

Digital Library

[7]

Olivier Chapelle and Alexander Zien. 2005. Semi-Supervised Classification by Low Density Separation. In AISTATS. 57--64.

[8]

Ronan Collobert, Fabian Sinz, Jason Weston, and Léon Bottou. 2006. Large scale transductive SVMs. Journal of Machine Learning Research 7, Aug (2006), 1687--1712.

Digital Library

[9]

Atam P Dhawan. 2011. Medical image analysis. Vol. 31. John Wiley &Sons.

[10]

Wael Emara, Mehmed Kantardzic Marcel Karnstedt, Kai-Uwe Sattler, Dirk Habich, and Wolfgang Lehner. 2007. An approach for incremental semi-supervised svm. In Data MiningWorkshops, 2007. ICDMWorkshops 2007. Seventh IEEE International Conference on. IEEE, 539--544.

Digital Library

[11]

Seyda Ertekin, Leon Bottou, and C. Lee Giles. 2011. Nonconvex Online Support Vector Machines. IEEE Trans. Pattern Anal. Mach. Intell. 33, 2 (Feb. 2011), 368--381.

Digital Library

[12]

Glenn Fung and Olvi L Mangasarian. 2001. Semi-superyised support vector machines for unlabeled data classification. Optimization methods and software 15, 1 (2001), 29--44.

[13]

Gene H Golub and Charles F Van Loan. 2012. Matrix computations. Vol. 3. JHU Press.

[14]

Bin Gu and Victor S Sheng. 2013. Feasibility and finite convergence analysis for accurate on-line-support vector machine. IEEE Transactions on Neural Networks and Learning Systems 24, 8 (2013), 1304--1315.

[15]

B. Gu and V. S. Sheng. 2016. A Robust Regularization Path Algorithm for - Support Vector Classification. IEEE Transactions on Neural Networks and Learning Systems PP, 99 (2016), 1--8.

[16]

Bin Gu, Victor S Sheng, Keng Yeow Tay, Walter Romano, and Shuo Li. 2015. Incremental support vector learning for ordinal regression. IEEE Transactions on Neural networks and learning systems 26, 7 (2015), 1403--1416.

[17]

Trevor Hastie, Saharon Rosset, Robert Tibshirani, and Ji Zhu. 2004. The entire regularization path for the support vector machine. Journal of Machine Learning Research 5, Oct (2004), 1391--1415.

Digital Library

[18]

William Karush. 1939. Minima of functions of several variables with inequalities as side constraints. Ph.D. Dissertation. Master¡s thesis, Dept. of Mathematics, Univ. of Chicago.

[19]

Gert R Lanckriet and Bharath K Sriperumbudur. 2009. On the convergence of the concave-convex procedure. In Advances in neural information processing systems. 1759--1767.

Digital Library

[20]

John Langford, Lihong Li, and Tong Zhang. 2009. Sparse online learning via truncated gradient. Journal of Machine Learning Research 10, Mar (2009), 777--801.

Digital Library

[21]

Mario Martin. 2002. On-line support vector machine regression. In European Conference on Machine Learning. Springer, 282--294.

Digital Library

[22]

Chong-Jin Ong, Shiyun Shao, and Jianbo Yang. 2010. An improved algorithm for the solution of the regularization path of support vector machine. IEEE Transactions on Neural Networks 21, 3 (2010), 451--462.

Digital Library

[23]

T Poggio and G Cauwenberghs. 2001. Incremental and decremental support vector machine learning. Advances in neural information processing systems 13 (2001), 409.

[24]

David Poole. 2014. Linear algebra: A modern introduction. Cengage Learning.

[25]

Fabian Sinz and Matteo Roffilli. 2012. UniverSVM. (2012). http://mloss.org/ software/view/19/.

[26]

Gang Wang, Dit-Yan Yeung, and Frederick H Lochovsky. 2008. A new solution path algorithm in support vector regression. IEEE Transactions on Neural Networks 19, 10 (2008), 1753--1767.

Digital Library

[27]

JunhuiWang, Xiaotong Shen, andWei Pan. 2007. On transductive support vector machines. Contemp. Math. 443 (2007), 7--20.

[28]

Alan L Yuille and Anand Rangarajan. 2003. The concave-convex procedure. Neural computation 15, 4 (2003), 915--936.

Digital Library

Cited By

Zhai ZGu BDeng CHuang H(2025)Global Model Selection via Solution Paths for Robust Support Vector MachineIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.334676547:3(1331-1347)Online publication date: Mar-2025
https://doi.org/10.1109/TPAMI.2023.3346765
Fan YYu SGu BXiong ZZhai ZHuang HChang Y(2025)Global Model Selection for Semi-Supervised Support Vector Machine via Solution PathsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2024.335497836:2(2154-2168)Online publication date: Feb-2025
https://doi.org/10.1109/TNNLS.2024.3354978
Chen LZhang TShi XJin HElkind E(2023)Incremental and decremental optimal margin distribution learningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/392(3523-3531)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/392
Show More Cited By

Index Terms

New Incremental Learning Algorithm for Semi-Supervised Support Vector Machine
1. Computing methodologies
  1. Machine learning
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Semi-supervised learning

Recommendations

Tackle Balancing Constraint for Incremental Semi-Supervised Support Vector Learning
KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Semi-Supervised Support Vector Machine (S3VM) is one of the most popular methods for semi-supervised learning. To avoid the trivial solution of classifying all the unlabeled examples to a same class, balancing constraint is often used with S3VM (denoted ...
An overview on semi-supervised support vector machine

Support vector machine (SVM) is a machine learning method based on statistical learning theory. It has a lot of advantages, such as solid theoretical foundation, global optimization, the sparsity of the solution, nonlinear and generalization. The ...
Incremental learning for transductive support vector machine
Highlights
- We study the fast training method of TSVM under large-scale data.
- We propose an incremental learning algorithm for TSVM (ILTSVM) based on the path following technique under the framework of infinitesimal annealing.
- We also analyze ...
Abstract
Semi-supervised learning is ubiquitous in real-world machine learning applications due to its good performance for handling the data where only a few number of samples are labeled while most of then are unlabeled. Transductive support vector ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2018

2925 pages

ISBN:9781450355520

DOI:10.1145/3219819

General Chairs:
Yike Guo
Imperial College London
,
Faisal Farooq
IBM

Copyright © 2018 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

KDD '18

Sponsor:

KDD '18: The 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 19 - 23, 2018

London, United Kingdom

Acceptance Rates

KDD '18 Paper Acceptance Rate 107 of 983 submissions, 11%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
1,295
Total Downloads

Downloads (Last 12 months)125
Downloads (Last 6 weeks)17

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhai ZGu BDeng CHuang H(2025)Global Model Selection via Solution Paths for Robust Support Vector MachineIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.334676547:3(1331-1347)Online publication date: Mar-2025
https://doi.org/10.1109/TPAMI.2023.3346765
Fan YYu SGu BXiong ZZhai ZHuang HChang Y(2025)Global Model Selection for Semi-Supervised Support Vector Machine via Solution PathsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2024.335497836:2(2154-2168)Online publication date: Feb-2025
https://doi.org/10.1109/TNNLS.2024.3354978
Chen LZhang TShi XJin HElkind E(2023)Incremental and decremental optimal margin distribution learningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/392(3523-3531)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/392
Wang Y(2023)Artificial Immune-Based Semi-supervised Learning for Classification2023 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC)10.1109/CyberC58899.2023.00018(44-50)Online publication date: 2-Nov-2023
https://doi.org/10.1109/CyberC58899.2023.00018
Taha K(2023)Semi-supervised and un-supervised clusteringInformation Systems10.1016/j.is.2023.102178114:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.is.2023.102178
Qu XLi DZhao XGu BKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)GAGAProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602591(32025-32038)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602591
Gao ZWu HTakáč MGu BAl Hasan MXiong L(2022)Towards Practical Large Scale Non-Linear Semi-Supervised Learning with Balancing ConstraintsProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557150(3072-3081)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557150
Gu BZhai ZLi XHuang HAl Hasan MXiong L(2022)Towards Fairer Classifier via True Fairness Score PathProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557109(3113-3121)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557109
Chen HYu YJia YZhang L(2022)Safe transductive support vector machineConnection Science10.1080/09540091.2021.202451134:1(942-959)Online publication date: 7-Feb-2022
https://doi.org/10.1080/09540091.2021.2024511
Gu BZhai ZDeng CHuang H(2021)Efficient Active Learning by Querying Discriminative and Representative Samples and Fully Exploiting Unlabeled DataIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2020.301692832:9(4111-4122)Online publication date: Sep-2021
https://doi.org/10.1109/TNNLS.2020.3016928
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten