Efficient Greedy Learning of Gaussian Mixture Models
Open accessThe DOI matches its Crossref record; 26 of the 27 references it cites were found in a registry or an index.
Abstract
This article concerns the greedy learning of gaussian mixtures. In the greedy approach, mixture components are inserted into the mixture one aftertheother.We propose a heuristic for searching for the optimal component to insert. In a randomized manner, a set of candidate new components is generated. For each of these candidates, we find the locally optimal new component and insert it into the existing mixture. The resulting algorithm resolves the sensitivity to initialization of state-of-the-art methods, like expectation maximization, and has running time linear in the number of data points and quadratic in the (final) number of mixture components. Due to its greedy nature, the algorithm can be particularly useful when the optimal number of mixture components is unknown. Experimental results comparing the proposed algorithm to other methods on density estimation and texture segmentation are provided.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The text we found for this paper looks like another document, so the self-check wasn’t run.
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 · cited 3×
“The EM algorithm (Dempster et al., 1977) enables us to update the parameters of a given k-component mixture with respect to a data set Xn = {x1, . . . , xn} with all xi ∈ Rd, such that the likelihood of Xn is never smaller under the new mixture.”
MethodResultElements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
McLachlan, G., & Peel, D. (2000) · Wiley Series in Probability and Statistics · doi:10.1002/0471721182 · Cited by 10,991
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,003
The 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 · cited 1×
“We recently applied a similar strategy to the k-means clustering problem (Likas et al., 2002), for which encouraging results were obtained.”
MethodSelf-citationA View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
Neal, R. M., & Hinton, G. E. (1998) · Learning in Graphical Models · doi:10.1007/978-94-011-5014-9_12 · Cited by 2,187 · cited 3×
“energy (Neal and Hinton, 1998), is detailed in Appendix A.”
BackgroundMethodInfluentialUnsupervised learning of finite mixture models
Figueiredo, M. A. T., & Jain, A. K. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.990138 · Cited by 2,125 · cited 4×
“Recently, several novel methods to learn mixtures (of Gaussian densities) were proposed among which we mention (Dasgupta, 1999; Figueiredo and Jain, 2002; Ueda et al., 2000).”
BackgroundInfluentialOn Bayesian Analysis of Mixtures with an Unknown Number of Components (with discussion)
Richardson, S., & Green, P. J. (1997) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/1467-9868.00095 · Cited by 1,898 · cited 2×
“For example, in Richardson and Green (1997), a reversible-jump Markov chain Monte Carlo (MCMC) method is proposed.”
BackgroundOn Bayesian Analysis of Mixtures with an Unknown Number of Components
Richardson, S. T., & Green, P. J. (1997) · Cited by 927
The Geometry of Mixture Likelihoods: A General Theory
Lindsay, B. G. (1983) · The Annals of Statistics · doi:10.1214/aos/1176346059 · Cited by 634 · cited 5×
“Experimental results comparing the proposed algorithm to other methods on density estimation and texture segmentation are provided.”
BackgroundMethodResultInfluentialLearning mixtures of Gaussians
Dasgupta, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814639 · Cited by 588
Sparse Greedy Matrix Approximation for Machine Learning
Smola, A. J., & Schökopf, B. (2000) · doi:10.5555/645529.657980 · Cited by 574
SMEM Algorithm for Mixture Models
Ueda, N., Nakano, R., Ghahramani, Z., & Hinton, G. E. (2000) · Neural Computation · doi:10.1162/089976600300015088 · Cited by 409
A Greedy EM Algorithm for Gaussian Mixture Learning
Vlassis, N., & Likas, A. (2002) · Neural Processing Letters · doi:10.1023/a:1013844811137 · Cited by 300 · cited 4×
“Vlassis and Likas (2002) proposed using n candidate components.”
BackgroundMethodInfluentialSelf-citationLi, J. Q., & Barron, A. R. (1999) · neural information processing systems · Cited by 297
Recursive unsupervised learning of finite mixture models
Zivkovic, Z., & van der Heijden, F. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1273970 · Cited by 266
A kurtosis-based dynamic approach to Gaussian mixture modeling
Vlassis, N. A., & Likas, A. C. (1999) · IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans · doi:10.1109/3468.769758 · Cited by 90 · cited 2×
“For example a kurtosis-based selection criterion, like the one in (Vlassis and Likas, 1999), can be used here.”
Self-citationA review of reliable maximum likelihood algorithms for semiparametric mixture models
Böhning, D. (1995) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(94)00119-g · Cited by 89 · cited 7×
“(iii) One may note similarity to the Vertex Direction Method (VDM) (Böhning, 1995; Lindsay, 1983; Wu, 1978) to learn Gaussian Mixtures.”
BackgroundMethodInfluentialSome Algorithmic Aspects of the Theory of Optimal Designs
Wu, C.-F. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344374 · Cited by 85 · cited 3×
“By partial EM search, we mean that we fix fk and optimize Lk+1 over θ and α only.”
MethodInfluentialLi, Q., & Barron, A. R. (1999) · Cited by 72
Algorithm AS 221: Maximum Likelihood Estimation of a Mixing Distribution
DerSimonian, R. (1986) · Journal of the Royal Statistical Society Series C (Applied Statistics) · doi:10.2307/2348030 · Cited by 30 · cited 12×
“The results of the greedy method and SMEM are roughly comparable, although the greedy approach was much faster.”
MethodInfluentialStochastic Optimal Prediction for the Kuramoto--Sivashinsky Equation
Stinis, P. (2004) · Multiscale Modeling and Simulation · doi:10.1137/030600424 · Cited by 23
Appearance-based concurrent map building and localization using a multi-hypotheses tracker
Porta, J. M., & Kröse, B. (2005) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2004.1389946 · Cited by 19
Self-citationMethod for computing protein binding affinity
Karney, C. F. F., Ferrara, J. E., & Brunner, S. (2004) · Journal of Computational Chemistry · doi:10.1002/jcc.20167 · Cited by 12
Almost autonomous training of mixtures of principal component analyzers
Musa, M. E. M., de Ridder, D., Duin, R. P. W., & Atalay, V. (2004) · Pattern Recognition Letters · doi:10.1016/j.patrec.2004.03.019 · Cited by 7
On model selection and concavity for finite mixture models
Cadez, I. V., & Smyth, P. (2002) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2000.866621 · Cited by 4 · cited 2×
“Recently, a result of “almost” concavity of the log likelihood of a data set under the maximum likelihood k-component mixture, as a function of the number of components k, was presented (Cadez & Smyth, 2000).”
BackgroundMethod
Research works printed but not linked: 1
- DerSimonian R., 1986, J. Roy. Statist. Soc. C, 35, 302
Cited by
A survey on deep learning and its applications
Dong, S., Wang, P., & Abbas, K. (2021) · Computer Science Review · doi:10.1016/j.cosrev.2021.100379 · Cited by 1,800
Pimentel, M. A. F., Clifton, D. A., Clifton, L., & Tarassenko, L. (2014) · Signal Processing · doi:10.1016/j.sigpro.2013.12.026 · Cited by 1,649
“The Greedy EM clustering algorithm [123] is used to identify and initialise clusters corresponding to different operating modes.”
MethodA tutorial on task-parameterized movement learning and retrieval
Calinon, S. (2016) · Intelligent Service Robotics · doi:10.1007/s11370-015-0187-9 · Cited by 422
“Other forms of learning for mixture models are possible, including spectral clustering [68, 84, 52], online learning [67, 82, 27, 99, 34] or selfrefinement [19].”
BackgroundFinite mixture models and model-based clustering
Melnykov, V., & Maitra, R. (2010) · Statistics Surveys · doi:10.1214/09-ss053 · Cited by 314
“Nevertheless, this method has been used in evaluating algorithms by [68, 115, 116].”
MethodGenetic-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
“Index Terms—Unsupervised learning, clustering, Gaussian mixture models, EM algorithm, Genetic algorithm, minimum description length.”
Method
Metadata
- Authors
- Verbeek, J. J., Vlassis, N., & Kröse, B.
- Affiliations
- University of Amsterdam (NL)
- Venue
- Neural Computation
- Publisher
- MIT Press - Journals
- Published
- 2003-02-01
- Volume
- 15
- Issue
- 2
- Pages
- 469-485
- ISSN
- 0899-7667 (ISSN-L)
- 1530-888X
- OpenAlex
- W2140136927
- Semantic Scholar
- 0c20cf7ce72d0df1e7a72ad4a94aed2a37c5a1c3
- Cited by
- 340
- References
- 27
- Citations by year
- 2026: 1 · 2025: 7 · 2024: 10 · 2023: 6 · 2022: 4 · 2021: 13 · 2020: 18 · 2019: 7 · 2018: 12 · 2017: 14 · 2016: 24 · 2015: 14 · 2014: 22 · 2013: 13 · 2012: 9
- FWCI
- 18.46
- Type
- journal article
- Language
- en
- Open access
- green
- orbilu.uni.lu
- Licence
- other-oa
- Locations
- Neural Computation (publishedVersion)
- PubMed (publishedVersion)
- UvA-DARE (University of Amsterdam) (publishedVersion)
- Open Repository and Bibliography (University of Luxembourg) (submittedVersion, other-oa)
- HAL (submittedVersion, other-oa)
- Data Archiving and Networked Services (DANS) (submittedVersion)
- Funders
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- Stichting voor de Technische Wetenschappen
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Methods and Mixture Models
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Keywords
- Gaussian mixture model, greedy learning, component insertion, density estimation, texture segmentation, model selection, expectation-maximization algorithm
- MeSH terms
- Algorithms, Learning, Normal Distribution
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.