Quantum algorithm for Help-Training semi-supervised support vector machine
- PDF / 582,790 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 179 Views
Quantum algorithm for Help-Training semi-supervised support vector machine Yanyan Hou1,2,3 · Jian Li1 · Xiubo Chen4 · Hengji Li1 · Chaoyang Li1 · Yuan Tian1 · Leilei Li1 · Zhengwen Cao5 · Na Wang1 Received: 25 February 2020 / Accepted: 16 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Semi-supervised support vector machine (S 3 V M) is a popular strategy for many machine learning tasks due to the expensiveness of getting enough labeled data. In this paper, we propose a quantum Help-Training S 3 V M and design a quantum Parzen window model to select n 1 + n 2 unlabeled data from l labeled and n√unlabeled data √ √ set in each iteration, the time complexity is O(τ nn 1 + τ nn 2 + τ n) for τ iterations, which exhibits a quadratic speed-up over classical algorithm, we adopt quantum linear system to build Lagrangian multipliers with accuracy ε, the time complexity is O(τ κ 3 ε−3 polylog(N (n + l))), where condition number is κ and feature dimension is N , it is exponentially faster than classical S 3 V M algorithm. Our scheme has two significant merits, (i) we provide the first quantum method for semi-supervised learning, which uses multiple unlabeled data with quantum superposition to predict Lagrangian multipliers at the same time, (ii) quantum matrix decomposition method avoids building matrices of different dimensions in one iteration; specially, this work provides inspiration to explore the potential quantum machine learning applications. Keywords Semi-supervised support vector machine (S 3 V M) · Lagrangian multipliers · Quantum Parzen window · Controlled swap test operation
1 Introduction With the development of artificial intelligence in the past decades, machine learning has developed rapidly and influenced many different fields, such as computer
Supported by the National Natural Science Foundation of China (Grant Nos. U1636106, 61472048), the China Postdoctoral Science Foundation under Grant 2019M650020 and the Fund of the Fundamental Research Funds for the Central Universities (Grant No. 2019XD-A02).
B
Jian Li [email protected]
Extended author information available on the last page of the article 0123456789().: V,-vol
123
278
Page 2 of 20
Y. Hou et al.
vision, face recognition, financial risk management, etc, and classical machine learning tasks frequently involve large amounts of high-dimensional data and need to spend extremely large time on manipulation or classification. Quantum algorithm is a remarkable branch of quantum computing, which computes data information in parallel and is suitable for dealing large amount of high-dimensional data. Combination quantum computing with machine learning, quantum machine learning, has attracted extensive attention and research. Despite the fact that quantum machine learning is a recent field, it already encompasses a rich set of quantum techniques and approaches; researchers in quantum machine learning field focus on improving classical machine learning performance by quantum parallelism and entanglement. Narayanan
Data Loading...
