中国邮电高校学报(英文版) ›› 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. 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. 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).

摘要: 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

中图分类号: