The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Learning mixtures of Gaussians
Abstract
Mixtures of Gaussians are among the most fundamental and widely used statistical models. Current techniques for learning such mixtures from data are local search heuristics with weak performance guarantees. We present the first provably correct algorithm for learning a mixture of Gaussians. This algorithm is very simple and returns the true centers of the Gaussians to within the precision specified by the user with high probability. It runs in time only linear in the dimension of the data and polynomial in the number of Gaussians.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
Maximum Likelihood from Incomplete Data via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1976) · Cited by 4,517
Pattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495
Lauritzen, S. L. (1996) · doi:10.1093/oso/9780198522195.001.0001 · Cited by 2,976
Statistical Analysis of Finite Mixture Distributions.
Lindsay, B. G., Titterington, D. M., Smith, A. F. M., & Makov, U. E. (1987) · Journal of the American Statistical Association · doi:10.2307/2289504 · Cited by 2,905
Mixture Densities, Maximum Likelihood and the EM Algorithm
Redner, R. A., & Walker, H. F. (1984) · SIAM Review · doi:10.1137/1026034 · Cited by 2,693
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
Cited by
An efficient k-means clustering algorithm: analysis and implementation
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1017616 · Cited by 5,660
“This sort of approach has been applied recently by Dasgupta [13] and Dasgupta and Shulman [14] in the context of clustering data sets that are generated by mixtures of Gaussians.”
MethodThe global k-means clustering algorithm
Likas, A., Vlassis, N., & J. Verbeek, J. (2003) · Pattern Recognition · doi:10.1016/s0031-3203(02)00060-2 · Cited by 3,733
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
Random projection in dimensionality reduction: applications to image and text data
Bingham, E., & Mannila, H. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502546 · Cited by 1,274
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10073 · Cited by 932
Self-citationMulti-view clustering via canonical correlation analysis
Chaudhuri, K., Kakade, S. M., Livescu, K., & Sridharan, K. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553391 · Cited by 786
Tensor decompositions for learning latent variable models
(2012) · arXiv (Cornell University) · doi:10.5555/2627435.2697055 · Cited by 779
“oretical computer science and machine learning have addressed computational and sample complexity issues related to estimating certain latent variable models such as Gaussian mixture models and HMMs (Dasgupta, 1999; Arora and Kannan, 2005; Dasgupta and Schulman, 2007; Vempala and Wang, 2004; Kannan et al., 2008;Achlio…”
BackgroundClustering on the Unit Hypersphere using von Mises-Fisher Distributions
Banerjee, A., Dhillon, I. S., Ghosh, J., & Sra, S. (2005) · MPG.PuRe (Max Planck Society) · doi:10.5555/1046920.1088718 · Cited by 766
Database-friendly random projections
Achlioptas, D. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375608 · Cited by 699
Exploratory Data Mining and Data Cleaning
Dasu, T., & Johnson, T. (2003) · Wiley Series in Probability and Statistics · doi:10.1002/0471448354 · Cited by 618
Consistent mesh partitioning and skeletonisation using the shape diameter function
Shapira, L., Shamir, A., & Cohen-Or, D. (2008) · The Visual Computer · doi:10.1007/s00371-007-0197-5 · Cited by 542
Efficient Greedy Learning of Gaussian Mixture Models
Verbeek, J. J., Vlassis, N., & Kröse, B. (2003) · Neural Computation · doi:10.1162/089976603762553004 · Cited by 340
Finite mixture models and model-based clustering
Melnykov, V., & Maitra, R. (2010) · Statistics Surveys · doi:10.1214/09-ss053 · Cited by 314
Experiments with Random Projection
Dasgupta, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.3849 · Cited by 306
Self-citationA Greedy EM Algorithm for Gaussian Mixture Learning
Vlassis, N., & Likas, A. (2002) · Neural Processing Letters · doi:10.1023/a:1013844811137 · Cited by 300
A spectral algorithm for learning Hidden Markov Models
Hsu, D., Kakade, S. M., & Zhang, T. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2011.12.025 · Cited by 278
To cluster, or not to cluster: An analysis of clusterability methods
Adolfsson, A., Ackerman, M., & Brownstein, N. C. (2019) · Pattern Recognition · doi:10.1016/j.patcog.2018.10.026 · Cited by 270
Genetic-based EM algorithm for learning Gaussian mixture models
Pernkopf, F., & Bouchaffra, D. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.162 · Cited by 265
Toward Privacy in Public Databases
Chawla, S., Dwork, C., McSherry, F., Smith, A., & Wee, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_20 · Cited by 264
Algorithmic applications of low-distortion geometric embeddings
Indyk, P. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959878 · Cited by 253
Settling the Polynomial Learnability of Mixtures of Gaussians
Moitra, A., & Valiant, G. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.15 · Cited by 252
Automatic cognitive load detection from speech features
Yin, B., Ruiz, N., Chen, F., & Khawaja, M. A. (2007) · Proceedings of the 19th Australasian conference on Computer-Human Interaction: Entertaining User Interfaces · doi:10.1145/1324892.1324946 · Cited by 55
“5 GMM Modeling The Gaussian Mixture Model (GMM) maps the feature distributions to a mixture of Gaussian distribution s [6].”
BackgroundMethod
Metadata
- Authors
- Dasgupta, S.
- Venue
- 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
- Publisher
- IEEE Comput. Soc
- Published
- 2003-01-20
- Pages
- 634-644
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W1956647075
- Cited by
- 588
- References
- 17
- FWCI
- 16.20
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.