Quantum semi-supervised kernel learning
Tóm tắt
Quantum machine learning methods have the potential to facilitate learning using extremely large datasets. While the availability of data for training machine learning models is steadily increasing, oftentimes it is much easier to collect feature vectors to obtain the corresponding labels. One of the approaches for addressing this issue is to use semi-supervised learning, which leverages not only the labeled samples, but also unlabeled feature vectors. Here, we present a quantum machine learning algorithm for training semi-supervised kernel support vector machines. The algorithm uses recent advances in quantum sample-based Hamiltonian simulation to extend the existing quantum LS-SVM algorithm to handle the semi-supervised term in the loss. Through a theoretical study of the algorithm’s computational complexity, we show that it maintains the same speedup as the fully-supervised quantum LS-SVM.
Tài liệu tham khảo
Allcock J, Hsieh CY (2020) A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time. Quantum 4:342
Arodz T, Saeedi S (2019) Quantum sparse support vector machines. arXiv:190201879
Arrazola JM, Delgado A, Bardhan BR, Lloyd S (2019) Quantum-inspired algorithms in practice. arXiv:190510415
Arunachalam S, de Wolf R (2017) A survey of quantum learning theory. ACM SIGACT News 48(2):41–67
Belkin M, Niyogi P, Sindhwani V (2006) Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J Mach Learn Res 7(11)
Berry DW, Ahokas G, Cleve R, Sanders BC (2007) Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270(2):359–371
Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S (2017) Quantum machine learning. Nature 549(7671):195
Chia NH, Gilyén A, Li T, Lin HH, Tang E, Wang C (2020) Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In: Proceedings of the 52nd Annual ACM SIGACT symposium on theory of computing, pp 387–400
Ding C, Bao TY, Huang HL (2019) Quantum-inspired support vector machine. arXiv:190608902
Dunjko V, Briegel HJ (2018) Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Rep Prog Phys 81(7):074001
Eikmeier N, Gleich DF (2017) Revisiting power-law distributions in spectra of real world networks. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp 817–826
Gilyén A, Lloyd S, Tang E (2018) Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:181104909
Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Rev Lett 103(15):150502
Kimmel S, Lin CYY, Low GH, Ozols M, Yoder TJ (2017) Hamiltonian simulation with optimal sample complexity. NPJ Quantum Inf 3(1):13
Li T, Chakrabarti S, Wu X (2019) Sublinear quantum algorithms for training linear and kernel-based classifiers. In: Proceedings of the 36th international conference on machine learning, pp 3815– 3824
Lloyd S, Mohseni M, Rebentrost P (2014) Quantum principal component analysis. Nat Phys 10(9):631
Melacci S, Belkin M (2011) Laplacian support vector machines trained in the primal. J Mach Learn Res 12:1149–1184
Perdomo-Ortiz A, Benedetti M, Realpe-Gómez J, Biswas R (2018) Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers. Quantum Sci Technol 3(3):030502
Rebentrost P, Mohseni M, Lloyd S (2014) Quantum support vector machine for big data classification. Phys Rev Lett 113(13):130503
Schölkopf B, Herbrich R, Smola AJ (2001) A generalized representer theorem. In: International conference on computational learning theory, COLT’01. Springer, pp 416–426
Schuld M, Petruccione F (2018) Supervised learning with quantum computers. Springer Nature, New York
Steinwart I, Hush D, Scovel C (2011) Training svms without offset. J Mach Learn Res 12(1)
Tang E (2018) Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv:181100414
Tang E (2019) A quantum-inspired classical algorithm for recommendation systems. In: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp 217–228
Wathen AJ, Zhu S (2015) On spectral distribution of kernel matrices related to radial basis functions. Numer Algorithm 70(4):709–726
Wiebe N, Braun D, Lloyd S (2012) Quantum algorithm for data fitting. Phys Rev Lett 109(5):050505