Quantum algorithms for structured prediction
Tóm tắt
We introduce two quantum algorithms for solving structured prediction problems. We first show that a stochastic gradient descent that uses the quantum minimum finding algorithm and takes its probabilistic failure into account solves the structured prediction problem with a runtime that scales with the square root of the size of the label space, and in
$$\tilde{O}\left (1/\epsilon \right )$$
with respect to the precision, 𝜖, of the solution. Motivated by robust inference techniques in machine learning, we then introduce another quantum algorithm that solves a smooth approximation of the structured prediction problem with a similar quantum speedup in the size of the label space and a similar scaling in the precision parameter. In doing so, we analyze a variant of stochastic gradient descent for convex optimization in the presence of an additive error in the calculation of the gradients, and show that its convergence rate does not deteriorate if the additive errors are of the order
$$O(\sqrt{\epsilon})$$
. This algorithm uses quantum Gibbs sampling at temperature Ω(𝜖) as a subroutine. Based on these theoretical observations, we propose a method for using quantum Gibbs samplers to combine feedforward neural networks with probabilistic graphical models for quantum machine learning. Our numerical results using Monte Carlo simulations on an image tagging task demonstrate the benefit of the approach.
Từ khóa
Tài liệu tham khảo
Albash T, Boixo S, Lidar DA, Zanardi P (2012) Quantum adiabatic markovian master equations. New J Phys 14(12):123016
Avron JE, Fraas M, Graf GM, Grech P (2012) Adiabatic theorems for generators of contracting evolutions. Commun Math Phys 314(1):163–191
Bachmann S, De Roeck W, Fraas M (2016) The adiabatic theorem for many-body quantum systems. Preprint
Bi W, Kwok J (2013) Efficient multi-label classification with many labels. In: International conference on machine learning, pp 405–413
Brandão FGSL, Kalev A, Li T, Yen-Yu Lin C, Svore KM, Wu X (2017) Quantum sdp solvers: Large speed-ups, optimality, and applications to quantum learning. arXiv:1710.02581
Brandao FGSL, Svore KM (2017) Quantum speed-ups for solving semidefinite programs. In: Foundations of computer science (FOCS), 2017 IEEE 58th annual symposium on. IEEE, pp 415–426
Beck A, Teboulle M (2012) Smoothing and first-order methods: A unified framework. SIAM J Optim 22(2):557–580
Crawford D, Levit A, Ghadermarzy N, Oberoi JS, Ronagh P (2016) Reinforcement learning using quantum boltzmann machines. arXiv:1612.05695
Chowdhury AN, Somma RD (2016) Quantum algorithms for gibbs sampling and hitting-time estimation. arXiv:1603.02940
Chen L-C, Schwing A, Yuille A, Urtasun R (2015) Learning deep structured models. In: International conference on machine learning, pp 1785–1794
Defazio A, Bach F, Lacoste-Julien S (2014) Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In: Advances in neural information processing systems, pp 1646–1654
Durr C, Hoyer P (1996) A quantum algorithm for finding the minimum. arXiv:9607014
Daume HC, Marcu D (2006) Practical structured learning techniques for natural language processing. Citeseer
Giovannetti V, Lloyd S, Maccone L (2008) Quantum random access memory. Phys. Rev. Lett. 100(16):160501
Gao B, Pavel L (2017) On the properties of the softmax function with application in game theory and reinforcement learning. arXiv:1704.00805
Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing, pp 212–219
Gimpel K, Smith NA (2010) Softmax-margin training for structured log-linear models
Huiskes MJ, Lew MS (2008) The MIR Flickr retrieval evaluation. In: Proceedings of the 1st ACM international conference on multimedia information retrieval. ACM, pp 39–43
Harvey NJA, Liaw C, Plan Y, Randhawa S (2018) Tight analyses for nonsmooth stochastic gradient descent. arXiv:1812.05217
Jiang Z (2020) Spatial structured prediction models: Applications, challenges, and techniques. IEEE Access 8:38714–38727
Jerrum MR, Valiant LG, Vazirani VV (1986) Random generation of combinatorial structures from a uniform distribution. Theor Comput Sci 43:169–188
Kingma DP, Ba J (2014) Adam: A method for stochastic optimization. arXiv:1412.6980
Kastoryano MJ, Brandao FGSL (2016) Quantum gibbs samplers: the commuting case. Commun Math Phys 344(3):915–957
Koller D, Friedman N (2009) Probabilistic graphical models: principles and techniques. MIT Press
Kim S, Nowozin S, Kohli P, Yoo CD (2011) Higher-order correlation clustering for image segmentation. In: Advances in neural information processing systems, pp 1530–1538
Karimi S, Ronagh P (2017) A subgradient approach for constrained binary optimization via quantum adiabatic evolution. Quantum Inf Process 16(8):185
Krizhevsky A, Sutskever I, Hinton GE (2012) Imagenet classification with deep convolutional neural networks. In: Advances in neural information processing systems, pp 1097–1105
Levit A, Crawford D, Ghadermarzy N, Oberoi JS, Zahedinejad E, Ronagh P (2017) Free energy-based reinforcement learning using a quantum processor. arXiv:1706.00074
Lacoste-Julien S, Schmidt M, Bach F (2012) A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method. arXiv:1212.2002
Lee Y-J, Mangasarian OL (2001) Ssvm: A smooth support vector machine for classification. Comput optim Appl 20(1):5–22
Matsubara S, Tamura H, Takatsu M, Yoo D, Vatankhahghadim B, Yamasaki H, Miyazawa T, Tsukamoto S, Watanabe Y, Takemoto K et al (2017) Ising-model optimizer with parallel-trial bit-sieve engine. In: Conference on complex, intelligent, and software intensive systems. Springer, pp 432–438
Nesterov Y (2005) Smooth minimization of nonsmooth functions. Mathematical programming 103(1):127–152
Nesterov Y (2013) Introductory lectures on convex optimization: A basic course, vol 87. Springer Science & Business Media, Berlin
Ng A (2010) Support vector machines (part v of cs229 machine learning course materials)
Sebastian N, Gehler PV, Jancsary J, Lampert CH (2014) Advanced structured prediction. MIT Press
Nielsen F, Ke S (2016) Guaranteed bounds on information-theoretic measures of univariate mixtures using piecewise log-sum-exp inequalities. Entropy 18(12):442
Okuyama T, Hayashi M, Yamaoka M (2017) An ising computer based on simulated quantum annealing by path integral monte carlo method. In: Rebooting computing (ICRC), 2017 IEEE international conference on. IEEE, pp 1–6
Paszke A, Gross S, Chintala S, Chanan G, Yang E, Devito Z, Lin Z, Desmaison A, Antiga L, Lerer A (2017) Automatic differentiation in pytorch
Poulin D, Wocjan P (2009) Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer. Phys Rev Lett 103(22):220502
Robbins H, Monro S (1985) A stochastic approximation method. In: Herbert robbins selected papers. Springer, pp 102–109
Rakhlin A, Shamir O, Sridharan K et al (2012) Making gradient descent optimal for strongly convex stochastic optimization. In: ICML, vol 12. Citeseer, pp 1571–1578
Ronagh P, Woods B, Iranmanesh E (2016) Solving constrained quadratic binary problems via quantum adiabatic evolution. Quantum Information & Computation 16(11-12):1029–1047
Sarandy MS, Lidar DA (2005) Adiabatic approximation in open quantum systems. Phys Rev A 71(1):012331
Schmidt M, Roux NL, Bach F (2017) Minimizing finite sums with the stochastic average gradient. Math Program 162(1-2):83–112
Sohn K, Lee H, Yan X (2015) Learning structured output representation using deep conditional generative models. Adv Neural Inf Process Syst 28:3483–3491
Shamir O, Zhang T (2013) Stochastic gradient descent for nonsmooth optimization Convergence results and optimal averaging schemes. In: International conference on machine learning, pp 71–79
Terhal BM, DiVincenzo DP (2000) Problem of equilibration and the computation of correlation functions on a quantum computer. Phys Rev A 61(2):022301
Temme K, Osborne TJ, Vollbrecht KG, Poulin D, Verstraete F (2011) Quantum metropolis sampling. Nature 471(7336):87
Takeda Y, Tamate S, Yamamoto Y, Takesue H, Inagaki T, Utsunomiya S (2017) Boltzmann sampling for an xy model using a non-degenerate optical parametric oscillator network. Quantum Science and Technology 3(1):014004
van Apeldoorn J, Gilyén A (2018) Improvements in quantum sdp-solving with applications. arXiv:1804.05058
van Apeldoorn J, Gilyén A (2019) Quantum algorithms for zero-sum games. arXiv:1904.03180
van Apeldoorn J, Gilyén A, Gribling S, De Wolf R (2017) Sdp-solvers: Quantum Better upper and lower bounds. In: Foundations of computer science (FOCS), 2017 IEEE 58th annual symposium on. IEEE, pp 403–414
Venuti LC, Albash T, Lidar DA, Zanardi P (2016) Adiabaticity in open quantum systems. Phys Rev A 93(3):032118
Wainwright MJ, Jordan MI et al (2008) Graphical models, exponential families, and variational inference. Foundations and Trends®; in Machine Learning 1(1–2):1–305
Wiebe N, Kapoor A, Svore KM (2014) Quantum deep learning. arXiv:1412.3489
Yu C-NJ, Joachims T (2009) Learning structural svms with latent variables. In: Proceedings of the 26th annual international conference on machine learning. ACM, pp 1169–1176
Yu CN (2011) Improved learning of structural support vector machines: training with latent variables and nonlinear kernels