NDLI: Polynomial Learning of Distribution Families

Content Provider	IEEE Xplore Digital Library
Author	Belkin, M. Sinha, K.
Copyright Year	2010
Abstract	The question of polynomial learn ability of probability distributions, particularly Gaussian mixture distributions, has recently received significant attention in theoretical computer science and machine learning. However, despite major progress, the general question of polynomial learn ability of Gaussian mixture distributions still remained open. The current work resolves the question of polynomial learn ability for Gaussian mixtures in high dimension with an arbitrary fixed number of components. Specifically, we show that parameters of a Gaussian mixture distribution with fixed number of components can be learned using a sample whose size is polynomial in dimension and all other parameters. The result on learning Gaussian mixtures relies on an analysis of distributions belonging to what we call “polynomial families” in low dimension. These families are characterized by their moments being polynomial in parameters and include almost all common probability distributions as well as their mixtures and products. Using tools from real algebraic geometry, we show that parameters of any distribution belonging to such a family can be learned in polynomial time and using a polynomial number of sample points. The result on learning polynomial families is quite general and is of independent interest. To estimate parameters of a Gaussian mixture distribution in high dimensions, we provide a deterministic algorithm for dimensionality reduction. This allows us to reduce learning a high-dimensional mixture to a polynomial number of parameter estimations in low dimension. Combining this reduction with the results on polynomial families yields our result on learning arbitrary Gaussian mixtures in high dimensions.
Starting Page	103
Ending Page	112
File Size	513805
Page Count	10
File Format	PDF
ISBN	9781424485253
ISSN	02725428
DOI	10.1109/FOCS.2010.16
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-10-23
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Probability distribution Covariance matrix Computer science Geometry Estimation Moment methods Polynomial Learnability Gaussian mixture learning
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Settling the Polynomial Learnability of Mixtures of Gaussians

EM algorithms of Gaussian mixture model and hidden Markov model

Offline handwritten numeral recognition using orthogonal Gaussian mixture model

Polynomial Learning of Distribution Families

On learning mixtures of heavy-tailed distributions

Learning feature characteristics

Initializing subspace constrained Gaussian mixture models

Generating Multivariate Mixture of Normal Distributions using a Modified Cholesky Decomposition

A comparison of mixture models for density estimation

Polynomial Learning of Distribution Families

Similar Documents

Settling the Polynomial Learnability of Mixtures of Gaussians

EM algorithms of Gaussian mixture model and hidden Markov model

Offline handwritten numeral recognition using orthogonal Gaussian mixture model

Polynomial Learning of Distribution Families

On learning mixtures of heavy-tailed distributions

Learning feature characteristics

Initializing subspace constrained Gaussian mixture models

Generating Multivariate Mixture of Normal Distributions using a Modified Cholesky Decomposition

A comparison of mixture models for density estimation

Polynomial Learning of Distribution Families