by Kerenidis, Iordanis, Luongo, Alessandro and Prakash, Anupam
Abstract:
We define a quantum version of Expectation-Maximization (QEM), a fundamental tool in unsupervised machine learning, often used to solve Maximum Likelihood (ML) and Maximum A Posteriori (MAP) estimation problems. We use QEM to fit a Gaussian Mixture Model, and show how to generalize it to fit mixture models with base distributions in the exponential family. Given quantum access to a dataset, our algorithm has convergence and precision guarantees similar to the classical algorithm, while the runtime is polylogarithmic in the number of elements in the training set and polynomial in other parameters, such as the dimension of the feature space and the number of components in the mixture. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by classical EM and provide guarantees for its runtime.
Reference:
Quantum Expectation-Maximization for Gaussian mixture models (Kerenidis, Iordanis, Luongo, Alessandro and Prakash, Anupam), In Proceedings of the 37th International Conference on Machine Learning (Hal Daumé III, Aarti Singh, eds.), PMLR, volume 119, 2020.
Bibtex Entry:
@inproceedings{pmlr-v119-kerenidis20a,
abstract = {We define a quantum version of Expectation-Maximization (QEM), a fundamental tool in unsupervised machine learning, often used to solve Maximum Likelihood (ML) and Maximum A Posteriori (MAP) estimation problems. We use QEM to fit a Gaussian Mixture Model, and show how to generalize it to fit mixture models with base distributions in the exponential family. Given quantum access to a dataset, our algorithm has convergence and precision guarantees similar to the classical algorithm, while the runtime is polylogarithmic in the number of elements in the training set and polynomial in other parameters, such as the dimension of the feature space and the number of components in the mixture. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by classical EM and provide guarantees for its runtime.},
author = {Kerenidis, Iordanis and Luongo, Alessandro and Prakash, Anupam},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
date-added = {2021-03-09 21:08:36 +0100},
date-modified = {2021-03-09 21:08:36 +0100},
editor = {Hal Daumé III and Aarti Singh},
month = {13--18 Jul},
pages = {5187--5197},
pdf = {http://proceedings.mlr.press/v119/kerenidis20a/kerenidis20a.pdf},
publisher = {PMLR},
series = {Proceedings of Machine Learning Research},
title = {Quantum Expectation-Maximization for {G}aussian mixture models},
url = {http://proceedings.mlr.press/v119/kerenidis20a.html},
volume = {119},
year = {2020},
bdsk-url-1 = {http://proceedings.mlr.press/v119/kerenidis20a.html}}