Learning mixtures of Gaussians with maximum-a-posteriori oracle

Satyaki Mahalanabis
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:489-497, 2011.

Abstract

We consider the problem of estimating the parameters of a mixture of distributions, where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a “maximum-a-posteriori” oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of $k$ spherical Gaussians in $\mathbb{R}^d$ assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in $d, k$) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02].

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-mahalanabis11a, title = {Learning mixtures of Gaussians with maximum-a-posteriori oracle}, author = {Mahalanabis, Satyaki}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {489--497}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/mahalanabis11a/mahalanabis11a.pdf}, url = {https://proceedings.mlr.press/v15/mahalanabis11a.html}, abstract = {We consider the problem of estimating the parameters of a mixture of distributions, where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a “maximum-a-posteriori” oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of $k$ spherical Gaussians in $\mathbb{R}^d$ assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in $d, k$) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02].} }
Endnote
%0 Conference Paper %T Learning mixtures of Gaussians with maximum-a-posteriori oracle %A Satyaki Mahalanabis %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-mahalanabis11a %I PMLR %P 489--497 %U https://proceedings.mlr.press/v15/mahalanabis11a.html %V 15 %X We consider the problem of estimating the parameters of a mixture of distributions, where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a “maximum-a-posteriori” oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of $k$ spherical Gaussians in $\mathbb{R}^d$ assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in $d, k$) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02].
RIS
TY - CPAPER TI - Learning mixtures of Gaussians with maximum-a-posteriori oracle AU - Satyaki Mahalanabis BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-mahalanabis11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 489 EP - 497 L1 - http://proceedings.mlr.press/v15/mahalanabis11a/mahalanabis11a.pdf UR - https://proceedings.mlr.press/v15/mahalanabis11a.html AB - We consider the problem of estimating the parameters of a mixture of distributions, where each component distribution is from a given parametric family e.g. exponential, Gaussian etc. We define a learning model in which the learner has access to a “maximum-a-posteriori” oracle which given any sample from a mixture of distributions, tells the learner which component distribution was the most likely to have generated it. We describe a learning algorithm in this setting which accurately estimates the parameters of a mixture of $k$ spherical Gaussians in $\mathbb{R}^d$ assuming the component Gaussians satisfy a mild separation condition. Our algorithm uses only polynomially many (in $d, k$) samples and oracle calls, and our separation condition is much weaker than those required by unsupervised learning algorithms like [Arora 01, Vempala 02]. ER -
APA
Mahalanabis, S.. (2011). Learning mixtures of Gaussians with maximum-a-posteriori oracle. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:489-497 Available from https://proceedings.mlr.press/v15/mahalanabis11a.html.

Related Material