Deterministic quantum annealing expectation-maximization algorithm. (English) Zbl 1456.68159
J. Stat. Mech. Theory Exp. 2017, No. 11, Article ID 113404, 22 p. (2017); erratum ibid. 2020, No. 10, Article ID 109901, 3 p. (2020).
Summary: Maximum likelihood estimation (MLE) is one of the most important methods in machine learning, and the expectation-maximization (EM) algorithm is often used to obtain maximum likelihood estimates. However, EM heavily depends on initial configurations and fails to find the global optimum. On the other hand, in the field of physics, quantum annealing (QA) was proposed as a novel optimization approach. Motivated by QA, we propose a quantum annealing extension of EM, which we call the deterministic quantum annealing expectation-maximization (DQAEM) algorithm. We also discuss its advantage in terms of the path integral formulation. Furthermore, by employing numerical simulations, we illustrate how DQAEM works in MLE and show that DQAEM moderate the problem of local optima in EM.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 62F12 | Asymptotic properties of parametric estimators |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 81P15 | Quantum measurement theory, state operations, state preparations |
References:
| [1] | Bishop C 2007 Pattern Recognition and Machine Learning(Information Science and Statistics) 1st edn (2006 corr 2nd printing edn) · Zbl 1107.68072 |
| [2] | Murphy K P 2012 Machine Learning: a Probabilistic Perspective (Cambridge, MA: MIT press) · Zbl 1295.68003 |
| [3] | Dempster A P, Laird N M and Rubin D B 1977 J. R. Stat. Soc. B 39 1-38 · Zbl 0364.62022 · doi:10.1111/j.2517-6161.1977.tb01600.x |
| [4] | Kirkpatrick S, Gelatt C D and Vecchi M P 1983 Science220 671-80 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [5] | Kirkpatrick S 1984 J. Stat. Phys.34 975-86 · doi:10.1007/BF01009452 |
| [6] | Geman S and Geman D 1984 IEEE Trans. Pattern Anal. Mach. Intell.PAMI-6 721-41 · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596 |
| [7] | Rose K, Gurewitz E and Fox G 1990 Pattern Recognit. Lett.11 589-94 · Zbl 0800.68817 · doi:10.1016/0167-8655(90)90010-Y |
| [8] | Rose K, Gurewitz E and Fox G C 1990 Phys. Rev. Lett.65 945-8 · doi:10.1103/PhysRevLett.65.945 |
| [9] | Ueda N and Nakano R 1998 Neural Netw.11 271-82 · doi:10.1016/S0893-6080(97)00133-0 |
| [10] | Apolloni B, Carvalho C and de Falco D 1989 Stoch. Process. Appl.33 233-44 · Zbl 0683.90067 · doi:10.1016/0304-4149(89)90040-9 |
| [11] | Finnila A, Gomez M, Sebenik C, Stenson C and Doll J 1994 Chem. Phys. Lett.219 343-8 · doi:10.1016/0009-2614(94)00117-0 |
| [12] | Kadowaki T and Nishimori H 1998 Phys. Rev. E 58 5355-63 · doi:10.1103/PhysRevE.58.5355 |
| [13] | Santoro G E, Martoňák R, Tosatti E and Car R 2002 Science295 2427-30 · doi:10.1126/science.1068774 |
| [14] | Santoro G E and Tosatti E 2006 J. Phys. A: Math. Gen.39 R393 · Zbl 1130.49037 · doi:10.1088/0305-4470/39/36/R01 |
| [15] | Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A and Preda D 2001 Science292 472-5 · Zbl 1226.81046 · doi:10.1126/science.1057726 |
| [16] | Morita S and Nishimori H 2008 J. Math. Phys.49 125210 · Zbl 1159.81332 · doi:10.1063/1.2995837 |
| [17] | Brooke J, Bitko D, Rosenbaum F T and Aeppli G 1999 Science284 779-81 · doi:10.1126/science.284.5415.779 |
| [18] | de Falco D and Tamascelli D 2009 Phys. Rev. A 79 012315 · doi:10.1103/PhysRevA.79.012315 |
| [19] | de Falco D and Tamascelli D 2011 RAIRO—Theor. Inf. Appl.45 99-116 · Zbl 1219.68105 · doi:10.1051/ita/2011013 |
| [20] | Das A and Chakrabarti B K 2008 Rev. Mod. Phys.80 1061-81 · Zbl 1205.81058 · doi:10.1103/RevModPhys.80.1061 |
| [21] | Martoňák R, Santoro G E and Tosatti E 2002 Phys. Rev. B 66 094203 · doi:10.1103/PhysRevB.66.094203 |
| [22] | Lloyd S, Mohseni M and Rebentrost P 2013 arXiv:1307.0411 |
| [23] | Rebentrost P, Mohseni M and Lloyd S 2014 Phys. Rev. Lett.113 130503 · doi:10.1103/PhysRevLett.113.130503 |
| [24] | Wiebe N, Kapoor A and Svore K M 2014 Quantum Deep Learning (arXiv:1412.3489) |
| [25] | Johnson M et al 2011 Nature473 194-8 · doi:10.1038/nature10012 |
| [26] | Schuld M, Sinayskiy I and Petruccione F 2015 Contemp. Phys.56 172-85 · doi:10.1080/00107514.2014.964942 |
| [27] | Aaronson S 2015 Nat. Phys.11 291-3 · doi:10.1038/nphys3272 |
| [28] | Kullback S and Leibler R A 1951 Ann. Math. Stat.22 79-86 · Zbl 0042.38403 · doi:10.1214/aoms/1177729694 |
| [29] | Kullback S 1997 Information Theory and Statistics (New York: Dover) · Zbl 0897.62003 |
| [30] | Umegaki H 1962 Kodai Math. Semin. Rep.14 59-85 · Zbl 0199.19706 · doi:10.2996/kmj/1138844604 |
| [31] | Al-Mohy A H and Higham N J 2010 SIAM J. Matrix Anal. Appl.31 970-89 · Zbl 1194.15021 · doi:10.1137/09074721X |
| [32] | Baum L E and Petrie T 1966 Ann. Math. Stat.37 1554-63 · Zbl 0144.40902 · doi:10.1214/aoms/1177699147 |
| [33] | Suzuki M 1976 Prog. Theor. Phys.56 1454-69 · Zbl 1097.82507 · doi:10.1143/PTP.56.1454 |
| [34] | Gubernatis J, Kawashima N and Werner P 2016 Quantum Monte Carlo Methods (Cambridge: Cambridge University Press) · Zbl 1366.81003 · doi:10.1017/CBO9780511902581 |
| [35] | Kawashima N and Harada K 2004 J. Phys. Soc. Japan73 1379-414 · Zbl 1113.82304 · doi:10.1143/JPSJ.73.1379 |
| [36] | Berry M V 1985 J. Phys. A: Math. Gen.18 15 · Zbl 0569.70020 · doi:10.1088/0305-4470/18/1/012 |
| [37] | Nagaosa N 2013 Quantum Field Theory in Condensed Matter Physics (Berlin: Springer) |
| [38] | Heim B, Rønnow T F, Isakov S V and Troyer M 2015 Science348 215-7 · Zbl 1355.81182 · doi:10.1126/science.aaa4170 |
| [39] | Miyahara H, Tsumura K and Sughiyama Y 2016 Relaxation of the em algorithm via quantum annealing for gaussian mixture models IEEE 55th Conf. Decision and Control pp 4674-9 |
| [40] | Hofmann T and Buhmann J M 1997 IEEE Trans. Pattern Anal. Mach. Intell.19 1-14 · doi:10.1109/34.566806 |
| [41] | Rose K 1998 Proc. IEEE86 2210-39 · doi:10.1109/5.726788 |
| [42] | Wu C F J 1983 Ann. Stat.11 95-103 · Zbl 0517.62035 · doi:10.1214/aos/1176346060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
