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

doi:10.19682/j.cnki.1005-8885.2022.2017

The Journal of China Universities of Posts and Telecommunications ›› 2022, Vol. 29 ›› Issue (4): 32-41.doi: 10.19682/j.cnki.1005-8885.2022.2017

• Special Topic: Quantum Science and Technology • Previous Articles Next Articles

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

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

CLC Number:

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

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.

Metrics

Comments

Copyright © 2020 The Journal of China Universities of Posts and Telecommunications
　 Adress: P.O. Box 231,Beijing University of Posts and Telecommunications,10 Xi Tucheng Road,Beijing 100876,P.R.China　Post Code: 100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
Support by: Beijing Magtech Co.Ltd

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Guo Xiangbo, Wang Jian, Huang Mengjie, Wang Minghui, Yang Jian, Yu Yongtao. Deep knowledge tracking algorithm based on forgetting law [J]. The Journal of China Universities of Posts and Telecommunications, 2023, 30(1): 17-27.
[2]	Wang Xianlun, Wang Guangyu, Cui Yuxia. Facial expression recognition based on improved ResNet [J]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(6): 73-82.
[5]	Zhang Han Jing Yinji Zhao Yongli. FS-LSTM: sales forecasting in e-commerce on feature selection [J]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(4): 77-88.
[8]	Meng Wei, Wang Liting, Lu Meng. Summary of research on recommendation system based on serendipity [J]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 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]. The Journal of China Universities of Posts and Telecommunications, 2021, 28(2): 48-67.
[13]	Wu Chengmao, Cao Zhuo. Entropy-like distance driven fuzzy clustering with local information constraints for image segmentation [J]. The Journal of China Universities of Posts and Telecommunications, 2021, 28(1): 24-40.
[14]	Shan Rui, Jiang Lin, Deng Junyong, Cui Pengfei, Zhang Yuting, Wu Haoyue, Xie Xiaoyan. Parallel design of convolutional neural networks for remote sensing images object recognition based on data-driven array processor [J]. The Journal of China Universities of Posts and Telecommunications, 2020, 27(6): 87-100.
[15]	Wang Zhaoying, Zhou Junhua, Liao Zhonghua, Zhai Xiang, Zhang Lianping. Semantic segmentation of track image based on deep neural network [J]. The Journal of China Universities of Posts and Telecommunications, 2020, 27(5): 23-33.