Quantum Expectation-Maximization for Gaussian Mixture Models

Abstract

The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that represent unlabelled points originating from $k$ different processes, as samples from $k$ multivariate distributions. In this work we define and use a quantum version of EM to fit a Gaussian Mixture Model. Given quantum access to a dataset of $n$ vectors of dimension $d$, our algorithm has convergence and precision guarantees similar to the classical algorithm, but the runtime is only polylogarithmic in the number of elements in the training set, and is polynomial in other parameters - as the dimension of the feature space, and the number of components in the mixture. We generalize further the algorithm in two directions. First, we show how to fit any mixture model of probability distributions in the exponential family. Then, we show how to use this algorithm to compute the Maximum a Posteriori (MAP) estimate of a mixture model: the Bayesian approach to likelihood estimation problems. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by this algorithm, arguing that on those cases we can give strong guarantees on the runtime.

arXiv commentAs to appear in ICML2020 conference - with improved algorithms and runtimes

References in corpus (19)

• Scikit-learn: Machine Learning in Python
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum algorithms: an overview
• Quantum algorithms for supervised and unsupervised machine learning
• Experimental Realization of Quantum Artificial Intelligence
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum gradient descent for linear systems and least squares
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Quantum-inspired algorithms in practice
• q-means: A quantum algorithm for unsupervised machine learning
• Quantum Algorithms for Deep Convolutional Neural Networks
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• Quantum Wasserstein Generative Adversarial Networks
• Quantum Expectation-Maximization Algorithm
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Parameter Estimation in Gaussian Mixture Models with Malicious Noise, without Balanced Mixing Coefficients

Cited by in corpus (8)

• Quantum computing for finance
• Quantum Capsule Networks
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Quantum algorithms for SVD-based data representation and analysis
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Large-Sample Properties of Blind Estimation of the Linear Discriminant Using Projection Pursuit