Quantum algorithm for soft margin support vector machine with hinge loss function

doi:10.19682/j.cnki.1005-8885.2022.2017

中国邮电高校学报(英文) ›› 2022, Vol. 29 ›› Issue (4): 32-41.doi: 10.19682/j.cnki.1005-8885.2022.2017

Quantum algorithm for soft margin support vector machine with hinge loss function

Liu Hailing, Zhang Jie, Qin Sujuan, Gao Fei

1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2. State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China

收稿日期:2022-05-02 修回日期:2022-05-23 接受日期:2022-06-10 出版日期:2022-08-31 发布日期:2022-08-31
通讯作者: Qin Sujuan, E-mail: qsujuan@bupt.edu.cn E-mail:qsujuan@bupt.edu.cn
基金资助:
This work was supported by the Beijing Natural Science Foundation (4222031), the National Natural Science Foundation of China (61976024, 61972048), Beijing University of Posts and Telecommunications (BUPT) Innovation and Entrepreneurship Support Program (2021-YC-A206).

Quantum algorithm for soft margin support vector machine with hinge loss function

Liu Hailing, Zhang Jie, Qin Sujuan, Gao Fei

1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2. State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China

Received:2022-05-02 Revised:2022-05-23 Accepted:2022-06-10 Online:2022-08-31 Published:2022-08-31
Contact: Qin Sujuan, E-mail: qsujuan@bupt.edu.cn E-mail:qsujuan@bupt.edu.cn
Supported by:
This work was supported by the Beijing Natural Science Foundation (4222031), the National Natural Science Foundation of China (61976024, 61972048), Beijing University of Posts and Telecommunications (BUPT) Innovation and Entrepreneurship Support Program (2021-YC-A206).

摘要/Abstract

摘要： Soft margin support vector machine (SVM) with hinge loss function is an important classification algorithm, which has been widely used in image recognition, text classification and so on. However, solving soft margin SVM with hinge loss function generally entails the sub-gradient projection algorithm, which is very time-consuming when processing big training data set. To achieve it, an efficient quantum algorithm is proposed. Specifically, this algorithm implements the key task of the sub-gradient projection algorithm to obtain the classical sub-gradients in each iteration, which is mainly based on quantum amplitude estimation and amplification algorithm and the controlled rotation operator. Compared with its classical counterpart, this algorithm has a quadratic speedup on the number of training data points. It is worth emphasizing that the optimal model parameters obtained by this algorithm are in the classical form rather than in the quantum state form. This enables the algorithm to classify new data at little cost when the optimal model parameters are determined.

关键词: soft margin support vector machine, hinge loss function, the sub-gradient projection algorithm, quantum algorithm, quadratic speedup

Abstract: Soft margin support vector machine (SVM) with hinge loss function is an important classification algorithm, which has been widely used in image recognition, text classification and so on. However, solving soft margin SVM with hinge loss function generally entails the sub-gradient projection algorithm, which is very time-consuming when processing big training data set. To achieve it, an efficient quantum algorithm is proposed. Specifically, this algorithm implements the key task of the sub-gradient projection algorithm to obtain the classical sub-gradients in each iteration, which is mainly based on quantum amplitude estimation and amplification algorithm and the controlled rotation operator. Compared with its classical counterpart, this algorithm has a quadratic speedup on the number of training data points. It is worth emphasizing that the optimal model parameters obtained by this algorithm are in the classical form rather than in the quantum state form. This enables the algorithm to classify new data at little cost when the optimal model parameters are determined.

Key words: soft margin support vector machine, hinge loss function, the sub-gradient projection algorithm, quantum algorithm, quadratic speedup

中图分类号:

TP391

Liu Hailing, Zhang Jie, Qin Sujuan, Gao Fei. Quantum algorithm for soft margin support vector machine with hinge loss function[J]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(4): 32-41.

参考文献

References
[1] SHOR P W. Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual
Symposium on Foundations of Computer Science, 1994, Nov 20 -22, Santa Fe, NM, USA. Piscataway, NJ, USA: IEEE, 1994: 124 -134.
[2] GROVER L K. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 1997, 79 (2): 325 -328.
[3] HARROW A W, HASSIDIM A, LLOYD S. Quantum algorithm for linear systems of equations. Physical Review Letters, 2009, 103(15): Article 150502.
[4] WAN L C, YU C H, PAN S J, et al. Asymptotic quantum algorithm for the Toeplitz systems. Physical Review A, 2018,
97(6): Article 062322.
[5] LIU H L, WU Y S, WAN L C, et al. Variational quantum algorithm for the Poisson equation. Physical Review A, 2021,
104(2): Article 022418.
[6] LIU H L, QIN S J, WAN L C, et al. A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected graph. arxiv Preprint, arxiv: 2203. 14451, 2022.
[7] BIAMONTE J, WITTEK P, PANCOTTI N, et al. Quantum machine learning. Nature, 2017, 549(7671): 195 -202.
[8] WIEBE N, BRAUN D, LLOYD S. Quantum algorithm for data fitting. Physical Review Letters, 2012, 109(5): Article 050505.
[9] YU C H, GAO F, WEN Q Y. An improved quantum algorithm for ridge regression. IEEE Transactions on Knowledge and Data Engineering, 2019, 33(3): 858 -866.
[10] REBENTROST P, MOHSENI M, LLOYD S. Quantum support vector machine for big data classification. Physical Review Letters, 2014, 113(13): Article 130503.

[11] DUAN B J, YUAN J B, LIU Y, et al. Quantum algorithm for support matrix machines. Physical Review A, 2017, 96 (3): Article 032301.
[12] LLOYD S, MOHSENI M, REBENTROST P. Quantum algorithms for supervised and unsupervised machine learning.
arxiv Preprint, arxiv: 1307. 0411, 2003.
[13] LLOYD S, MOHSENI M, REBENTROST P. Quantum principal component analysis. Nature Physics, 2014, 10(9): 631 -633.
[14] CONG I, DUAN L M. Quantum discriminant analysis for dimensionality reduction and classification. New Journal of
Physics, 2016, 18(7): Article 073011.
[15] PAN S J, WAN L C, LIU H L, et al. Quantum algorithm for neighborhood preserving embedding. Chinese Physics B, 2022, 31: Article 060304.
[16] ABBAS A, SUTTER D, ZOUFAL C, et al. The power of quantum neural networks. Nature Computational Science, 2021, 1(6): 403 -409.
[17] DUNJKO V, BRIEGEL H J. Machine learning and artificial intelligence in the quantum domain: A review of recent progress. Reports on Progress in Physcis, 2018, 81(7): Article 074001.
[18] VAPNIK V N. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 1999, 10(5): 988 -999.
[19] TRAFALIS T B, INCE H. Support vector machine for regression and applications to financial forecasting. Proceedings of the 2000 IEEE-INNS-ENNS International Joint Conference on Neural Networks (IJCNN'00), 2000, Jul 24 - 27, Como, Italy. Piscataway, NJ, USA: IEEE, 2000: 348 -353.
[20] GOH K S, CHANG E Y, LI B T. Using one-class and two-class SVMs for multiclass image annotation. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(10): 1333 -1346.
[21] ISA D, LEE L H, KALLIMANI V P, et al. Text document preprocessing with the Bayes formula for classification using the support vector machine. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(9): 1264 -1272.
[22] SUYKENS J A K, VANDEWALLE J. Least squares support vector machine classifiers. Neural Processing Letters, 1999, 9(3): 293 -300.
[23] BI J B, ZHANG T. Support vector classification with input data uncertainty. Advances in Neural Information Processing Systems 17: Proceedings of the 17th International Conference on Neural Information Processing Systems (NIPS'04), 2004, Dec 13 -18, Vancouver, Canada. Cambridge, MA, USA: MIT Press, 2004: 161 -168.
[24] ROSASCO L, DE VITO E, CAPONNETTO A, et al. Are loss functions all the same? Neural Computation, 2004, 16(5): 1063 -1076.
[25] SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos: Primal estimated sub-gradient solver for SVM.
Mathematical Programming, 2011, 127(1): 3 -30.
[26] BISHWAS A K, MANI A, PALADE V. Big data classification with quantum multiclass SVM and quantum one-against-all approach. Proceedings of the 2nd International Conference on Contemporary Computing and Informatics (IC3I'16), 2016, Dec 14 -17, Greater Noida, India. Piscataway, NJ, USA: IEEE, 2016: 875 -880.
[27] BISHWAS A K, MANI A, PALADE V. An all-pair quantum SVM approach for big data multiclass classification. Quantum Information Processing, 2018, 17(10): Article 282.
[28] LIN J, ZHANG D B, ZHANG S, et al. Quantum-enhanced least-square support vector machine: Simplified quantum
algorithm and sparse solutions. Physics Letters A, 2020, 384(25): Article 126590.
[29] HAVLICEK V, CORCOLES A D, TEMME K, et al. Supervised learning with quantum-enhanced feature spaces. Nature, 2019, 567(7747): 209 -212.
[30] KERENIDIS I, PRAKASH A, SZILAGYI D. Quantum algorithms for second-order cone programming and support vector machines. Quantum, 2021, 5: Article 427.
[31] LI H, JIANG N, ZHANG R, et al. Quantum support vector machine based on gradient descent. International Journal of Theoretical Physics, 2022, 61(3): Article 92.
[32] ZHANG R, WANG J, JIANG N, et al. Quantum support vector machine based on regularized Newton method. Neural Networks, 2022, 151: 376 -384.
[33] REBENTROST P, SCHULD M, WOSSNIG L, et al. Quantum gradient descent and Newton's method for constrained polynomial optimization. New Journal of Physics, 2019, 21(7): Article 073023.
[34] GAO P, LI K R, WEI S J, et al. Quantum gradient algorithm for general polynomials. Physical Review A, 2021, 103(4): Article 042403.
[35] BRASSARD G, HOYER P, MOSCA M, et al. Quantum amplitude amplification and estimation. LOMONACO S J,
BRANDT H E (eds). Quantum Computation and Information. Contemporary Mathematics 305. Providence, RI, USA:
American Mathematical Society, 2002: 53 -74.
[36] DUAN B J, YUAN J B, LIU Y, et al. Efficient quantum circuit for singular-value thresholding. Physical Review A, 2018, 98(1): Article 012308.
[37] MITARAI K, KITAGAWA M, FUJII K. Quantum analog-digital conversion. Physical Review A, 2019, 99(1): Article 012301.
[38] WOSSNIG L, ZHAO Z K, PRAKASH A. Quantum linear system algorithm for dense matrices. Physical Review Letters, 2018, 120(5): Article 050502.
[39] KERENIDIS I, PRAKASH A. Quantum recommendation system. Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS'17), 2017, Jan 9 -11, Berkeley, CA, USA. Berlin, Germany: Schloss Dagstuhl-Leibniz Center for Information, 2017: 49.1 -49.21.
[40] KERENIDIS I, LANDMAN J, LUONGO A, et al. Q-means: A quantum algorithm for unsupervised machine learning. Advances in Neural Information Processing Systems 32: Proceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS'19), 2019, Dec 8 -14, Vancouver, Canada. Cambridge, MA, USA: MIT Press, 2019: Article 2295.
[41] ZHOU S S, LOKE T, IZAAC J A, et al. Quantum Fourier transform in computational basis. Quantum Information
Processing, 2017, 16(3): Article 82.
[42] LI H. Statistical learning method. Beijing, China: Tsinghua University Press, 2012 (in Chinese).
[43] ALLCOCK J, HSIEH C Y. A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time. Quantum, 2020(4): Article 342.

Quantum algorithm for soft margin support vector machine with hinge loss function

Quantum algorithm for soft margin support vector machine with hinge loss function

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	Guo Xiangbo, Wang Jian, Huang Mengjie, Wang Minghui, Yang Jian, Yu Yongtao. Deep knowledge tracking algorithm based on forgetting law[J]. 中国邮电高校学报(英文版), 2023, 30(1): 17-27.
[2]	Wang Xianlun, Wang Guangyu, Cui Yuxia. Facial expression recognition based on improved ResNet[J]. 中国邮电高校学报(英文版), 2023, 30(1): 28-38.
[3]	Wu Hongxin, Lin Zhijian, Chen Pingping, Chen Feng. Joint partial computation offloading and resource allocation in MEC-enable networks[J]. 中国邮电高校学报(英文版), 2023, 30(1): 80-86.
[4]	Kong Chao, Ou Weihua, Gong Xiaofeng, Li Weian, Han Jie, Yao Yi, Xiong Jiahao. Face anti-spoofing based on multi-modal and multi-scale features fusion [J]. 中国邮电高校学报(英文), 2022, 29(6): 73-82.
[5]	张函井音吉赵永利. FS-LSTM: sales forecasting in e-commerce on feature selection [J]. 中国邮电高校学报(英文版), 2022, 29(5): 92-98.
[6]	Shi Jinjing, Wang Wenxuan, Xiao Zimeng, Mu Shuai, Li Qin. Quantum classifier with parameterized quantum circuit based on the isolated quantum system[J]. 中国邮电高校学报(英文), 2022, 29(4): 21-31.
[7]	Wang Jian, Qiao Kuoyuan, Yuan Yanlei, Liu Xiaole, Yang Jian. Adaptive learning path recommendation model for examination-oriented education[J]. 中国邮电高校学报(英文), 2022, 29(4): 77-88.
[8]	Meng Wei, Wang Liting, Lu Meng. Summary of research on recommendation system based on serendipity[J]. 中国邮电高校学报(英文), 2022, 29(4): 89-105.
[9]	Jia Wei, Gong Chao. Precise and efficient Chinese license plate recognition in the real monitoring scene of intelligent transportation system[J]. 中国邮电高校学报(英文), 2022, 29(3): 1-14.
[10]	Song Yue, Wu Chengmao, Tian Xiaoping, Song Qiuyu. Enhanced kernel-based fuzzy local information clustering integrating neighborhood membership [J]. 中国邮电高校学报(英文版), 2021, 28(6): 65-81.
[11]	Xue Chenzi, Wei Yifei, Zhang Yong. Performance optimization for smart grid blockchain integrated with fog computing using DDQN[J]. 中国邮电高校学报(英文版), 2021, 28(2): 68-78.
[12]	Guo Hairu, Meng Xueyao, Liu Yongli, Liu Shen. Improved HHO algorithm based on good point set and nonlinear convergence formula[J]. 中国邮电高校学报(英文版), 2021, 28(2): 48-67.
[13]	吴成茂曹卓. Entropy-like distance driven fuzzy clustering with local information constraints for image segmentation [J]. 中国邮电高校学报(英文版), 2021, 28(1): 24-40.
[14]	山蕊蒋林邓军勇崔朋飞张玉婷吴皓月谢晓燕. Parallel design of convolutional neural networks for remote sensing images object recognition based on data-driven array processor [J]. 中国邮电高校学报(英文版), 2020, 27(6): 87-100.
[15]	汪昭颖, 周军华, 廖中华, 翟翔, 张连平. Semantic segmentation of track image based on deep neural network[J]. 中国邮电高校学报(英文版), 2020, 27(5): 23-33.