Quantum algorithm for soft margin support vector machine withhinge loss function |
| |
Authors: | Liu Hailing Zhang Jie Qin Sujuan Gao Fei |
| |
Affiliation: | 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
|
| |
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 SVMwith hinge loss function generally entails the sub-gradient projection algorithm, which is very time-consuming whenprocessing big training data set. To achieve it, an efficient quantum algorithm is proposed. Specifically, thisalgorithm implements the key task of the sub-gradient projection algorithm to obtain the classical sub-gradients ineach iteration, which is mainly based on quantum amplitude estimation and amplification algorithm and thecontrolled rotation operator. Compared with its classical counterpart, this algorithm has a quadratic speedup on thenumber of training data points. It is worth emphasizing that the optimal model parameters obtained by this algorithmare in the classical form rather than in the quantum state form. This enables the algorithm to classify new data atlittle cost when the optimal model parameters are determined. |
| |
Keywords: | |
|
| 点击此处可从《中国邮电高校学报(英文版)》浏览原始摘要信息 |
|
点击此处可从《中国邮电高校学报(英文版)》下载全文 |
|