Back

Unsupervised Learning of Finite Mixture Models

Mário A. T. FigueiredoAnil K. Jain

article2002TPAMI2,393 citations

Presents a unified expectation-maximization framework for finite mixture models that automatically estimates the optimal number of components while eliminating sensitivity to initialization and avoiding singular boundary solutions.

Listen

Finite mixture models are essential tools across pattern recognition, machine learning, and computer vision for clustering, density estimation, and feature selection. Standard practice relies heavily on the Expectation-Maximization algorithm to fit these models. However, Expectation-Maximization suffers from several critical operational limitations: it is greedy and highly sensitive to initial conditions, easily trapped in poor local maxima, prone to numerical failure when estimating boundaries collapse, and incapable of determining the true number of mixture components on its own. Addressing model complexity usually forces practitioners into computationally demanding workarounds, such as repeatedly running Expectation-Maximization across many candidate model sizes and scoring each with post-hoc selection criteria.

To overcome these hurdles, the article introduces an integrated unsupervised algorithm designed to simultaneously estimate mixture parameters and automatically select the optimal number of components. The approach eliminates separate candidate generation and testing loops by embedding model selection directly within the parameter estimation process. Rooted in the Minimum Message Length information-theoretic criterion, the method formulates a specialized objective function using a Dirichlet-type prior with negative parameters, which systematically drives unsupported or redundant components to extinction during optimization.

The algorithm operates through a component-wise update procedure that starts with an intentionally oversized initial number of components distributed across the data space. As iterations progress, under-supported components shrink and vanish via an explicit annihilation mechanism, preventing boundary singularities and avoiding poor local traps. The process sequentially eliminates the weakest surviving components and re-optimizes until the overall information criterion is minimized, yielding both the final component count and reliable parameter estimates in a single integrated workflow.

Extensive experimental evaluations across synthetic Gaussian mixtures, benchmark real-world datasets (such as the Iris, acidity, and enzyme benchmarks), and high-dimensional tasks (such as texture classification and noisy spiral manifold extraction) demonstrate strong performance advantages. In comparative experiments against standard Expectation-Maximization paired with traditional criteria like the Bayesian Information Criterion and the Integrated Completed Likelihood, the proposed method achieved equal or superior accuracy while reducing computational requirements by roughly 70% to 80% (requiring four to five times fewer iterations). Crucially, the method exhibited 100% success across 100 random restarts in complex overlap scenarios where standard methods frequently miscalculated cluster counts or converged to degenerate boundaries.

These findings mean that organizations deploying mixture models for unsupervised pattern recognition can dramatically streamline their modeling pipelines. The integrated algorithm lowers computational overhead, accelerates processing timelines, and removes the risk of algorithmic failure caused by fragile initialization and parameter singularities. Practitioners do not need complex, manually tuned cooling schedules or multiple exploratory runs across arbitrary ranges of component counts to achieve robust clustering.

Organizations should consider adopting this integrated framework for tasks involving Gaussian mixtures, mixtures of factor analyzers, and general parametric clustering. The main trade-off occurs in scenarios with extremely unbalanced component weights: if a true component holds very few data points, the strong annihilation dynamic can occasionally extinguish it prematurely. Readers can place high confidence in the method's effectiveness for general and overlapping distributions, though caution is recommended when detecting rare, low-frequency anomalies. Future development should incorporate dedicated outlier-handling components to make the framework fully resilient against extreme noise and severe class imbalance.

Instituto de TelecomunicaçõesInstituto Superior TécnicoMichigan State Universitygaussian mixturesgaussiansgenetic selectionfinite mixture modelsunsupervised learning
abriosi/gmm-mmlFigueiredo et al (2002).pdf
  • Paper: X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Dan Pelleg et al. (2000). Read X-means first to see an earlier BIC-based strategy for choosing mixture component counts, clarifying the model-selection problem this paper instead integrates into estimation.
  • Paper: The Infinite Gaussian Mixture Model, Carl Edward Rasmussen (1999). Rasmussen’s infinite Gaussian mixture provides an earlier probabilistic approach to inferring cluster count, making a useful point of comparison for this paper’s finite, component-annihilation method.
  • Paper: Hierarchical Mixtures of Experts and the EM Algorithm, Michael I. Jordan et al. (1994). Its mixture-of-experts treatment develops EM responsibilities and parameter updates, the EM machinery whose limitations motivate the source’s alternative estimation procedure.

No sufficiently relevant recommendations were found.

Cover for Unsupervised Learning of Finite Mixture Models

Abstract

This paper proposes an unsupervised algorithm for learning a finite mixture model from multivariate data. The adjective “unsupervised” is justified by two properties of the algorithm: 1) it is capable of selecting the number of components and 2) unlike the standard expectation-maximization (EM) algorithm, it does not require careful initialization. The proposed method also avoids another drawback of EM for mixture fitting: the possibility of convergence toward a singular estimate at the boundary of the parameter space. The novelty of our approach is that we do not use a model selection criterion to choose one among a set of preestimated candidate models; instead, we seamlessly integrate estimation and model selection in a single algorithm. Our technique can be applied to any type of parametric mixture model for which it is possible to write an EM algorithm; in this paper, we illustrate it with experiments involving Gaussian mixtures. These experiments testify for the good performance of our approach.

Topics

gaussian mixturesgaussiansgenetic selectionmode selectionsupervised machine learningunsupervised learning methodestimation method

Keywords

finite mixture modelsunsupervised learning

Table of Contents

  • 1 INTRODUCTION
  • 2 LEARNING FINITE MIXTURE MODELS
  • 2.1 Finite Mixture Models
  • 2.2 The EM Algorithm
  • 3 PREVIOUS WORK
  • 3.1 Estimating the Number of Components
  • 3.1.1 Deterministic Methods
  • 3.1.2 Stochastic and Resampling Methods
  • 3.2 The Drawbacks of EM-Based Methods
  • 3.2.1 The Initialization Issue
  • 3.2.2 The Boundary of the Parameter Space
  • 4 THE PROPOSED CRITERION
  • 4.1 The Minimum Message Length Criterion
  • 5 ALGORITHM
  • 5.1 Minimization of the Cost Function via EM
  • 5.1.1 Component Annihilation
  • 5.1.2 Robustness Regarding Initialization
  • 5.1.3 Relation with Supervised Learning
  • 5.1.4 Relation with Minimum-Entropy Priors
  • 5.2 The Component-Wise EM Algorithm
  • 5.3 The Complete Algorithm
  • 6 EXPERIMENTS
  • 6.2 First Examples
  • 6.3 Comparison with EM-Based Methods
  • 6.4 Mixtures as Class-Conditional Densities
  • 6.5 Mixtures of Factor Analyzers
  • 6.6 Failure Conditions
  • 7 DISCUSSION AND OUTLOOK
  • ACKNOWLEDGMENTS
  • APPENDIX
  • DERIVATION OF THE MML CRITERION
  • REFERENCES

Knowls

  1. Knowl 1 — Minimum Message Length Objective Function for Finite Mixture Models

    equation

    For a dataset Y={y(1),…,y(n)}\mathcal{Y} = \{\mathbf{y}^{(1)}, \dots, \mathbf{y}^{(n)}\} consisting of nn independent and identically distributed dd-dimensional continuous observations generated from a kk-component finite mixture model:

    p(y∣θ)=∑m=1kαmp(y∣θm)p(\mathbf{y}|\boldsymbol{\theta}) = \sum_{m=1}^k \alpha_m p(\mathbf{y}|\boldsymbol{\theta}_m)

    where αm≥0\alpha_m \ge 0, ∑m=1kαm=1\sum_{m=1}^k \alpha_m = 1, and each component density p(y∣θm)p(\mathbf{y}|\boldsymbol{\theta}_m) is parameterized by an NN-dimensional vector hetam\boldsymbol{ heta}_m, the total parameter vector is heta={heta1,…,hetak,α1,…,αk}\boldsymbol{ heta} = \{\boldsymbol{ heta}_1, \dots, \boldsymbol{ heta}_k, \alpha_1, \dots, \alpha_k\}. Let knz=∣{m:αm>0}∣k_{nz} = |\{m : \alpha_m > 0\}| denote the number of active components with non-zero probability.

    The Minimum Message Length (MML) cost function to be minimized with respect to heta\boldsymbol{ heta} is:

    L(θ,Y)=N2∑m:αm>0log⁡(nαm12)+knz2log⁡(n12)+knz(N+1)2−log⁡p(Y∣θ)\mathcal{L}(\boldsymbol{\theta}, \mathcal{Y}) = \frac{N}{2} \sum_{m: \alpha_m > 0} \log\left(\frac{n \alpha_m}{12}\right) + \frac{k_{nz}}{2} \log\left(\frac{n}{12}\right) + \frac{k_{nz}(N+1)}{2} - \log p(\mathcal{Y}|\boldsymbol{\theta})

    where log⁡p(Y∣θ)=∑i=1nlog⁡(∑m=1kαmp(y(i)∣θm))\log p(\mathcal{Y}|\boldsymbol{\theta}) = \sum_{i=1}^n \log\left(\sum_{m=1}^k \alpha_m p(\mathbf{y}^{(i)}|\boldsymbol{\theta}_m)\right) is the log-likelihood of the observed data.

    The terms in the cost function correspond to:

    1. −log⁡p(Y∣θ)-\log p(\mathcal{Y}|\boldsymbol{\theta}): the code length required to transmit the data given the parameters heta\boldsymbol{ heta}.

    2. N2log⁡(nαm12)\frac{N}{2} \log\left(\frac{n \alpha_m}{12}\right): the code length required to encode the NN continuous parameters of component mm, where nαmn \alpha_m acts as the effective sample size available for estimating hetam\boldsymbol{ heta}_m.

    3. knz2log⁡(n12)\frac{k_{nz}}{2} \log\left(\frac{n}{12}\right): the code length required to encode the mixing probabilities αm\alpha_m.

    4. knz(N+1)2\frac{k_{nz}(N+1)}{2}: constant quantization overhead under optimal uniform lattice quantization.

  2. Knowl 2 — Component Annihilation Rule in the Expectation-Maximization Step

    equation

    Under the improper Dirichlet prior p(α1,…,αk)∝exp⁡(−N2∑m=1klog⁡αm)=∏m=1kαm−N/2p(\alpha_1, \dots, \alpha_k) \propto \exp\left(-\frac{N}{2} \sum_{m=1}^k \log \alpha_m\right) = \prod_{m=1}^k \alpha_m^{-N/2}, where NN is the number of parameters per component, the M-step update for the mixing probabilities αm\alpha_m at iteration t+1t+1 is given by:

    α^m(t+1)=max⁡{0,(∑i=1nwm(i))−N2}∑j=1kmax⁡{0,(∑i=1nwj(i))−N2},m=1,…,k\hat{\alpha}_m(t+1) = \frac{\max\left\{0, \left(\sum_{i=1}^n w_m^{(i)}\right) - \frac{N}{2}\right\}}{\sum_{j=1}^k \max\left\{0, \left(\sum_{i=1}^n w_j^{(i)}\right) - \frac{N}{2}\right\}}, \quad m = 1, \dots, k

    where wm(i)w_m^{(i)} is the posterior responsibility of component mm for observation y(i)\mathbf{y}^{(i)} computed during the E-step:

    wm(i)=α^m(t)p(y(i)∣θ^m(t))∑j=1kα^j(t)p(y(i)∣θ^j(t))w_m^{(i)} = \frac{\hat{\alpha}_m(t) p(\mathbf{y}^{(i)}|\hat{\boldsymbol{\theta}}_m(t))}{\sum_{j=1}^k \hat{\alpha}_j(t) p(\mathbf{y}^{(i)}|\hat{\boldsymbol{\theta}}_j(t))}

    If the total effective support ∑i=1nwm(i)\sum_{i=1}^n w_m^{(i)} for component mm is less than or equal to N2\frac{N}{2}, the update sets α^m(t+1)=0\hat{\alpha}_m(t+1) = 0, annihilating component mm from the mixture model. This mechanism prevents the parameter estimates from drifting toward singular points on the boundary of the parameter space (where covariance matrices collapse onto single data points) and enables automatic component reduction.

  3. Knowl 3 — Unsupervised Component-Wise EM Algorithm for Finite Mixture Models

    algorithm

    The algorithm estimates mixture parameters while simultaneously determining the number of components kk. Rather than testing separate candidate values of kk across independent runs, it begins with an over-complete initialization of kmaxk_{max} components and utilizes Component-Wise EM (CEM2^2) to update components sequentially. When a component's mixing weight is driven to zero via the annihilation threshold N/2N/2, its probability mass is immediately redistributed to surviving components in the same sweep. Once CEM2^2 converges to a local minimum of L(θ,Y)\mathcal{L}(\boldsymbol{\theta}, \mathcal{Y}), the least probable active component is pruned and CEM2^2 is rerun, repeating until knz<kmink_{nz} < k_{min}.

    Input: Data Y={y(1),…,y(n)}\mathcal{Y} = \{\mathbf{y}^{(1)}, \dots, \mathbf{y}^{(n)}\}, range [kmin,kmax][k_{min}, k_{max}], convergence threshold ϵ=10−5\epsilon = 10^{-5}, initial parameters θ(0)={θ^1,…,θ^kmax,α^1,…,α^kmax}\boldsymbol{\theta}(0) = \{\hat{\boldsymbol{\theta}}_1, \dots, \hat{\boldsymbol{\theta}}_{k_{max}}, \hat{\alpha}_1, \dots, \hat{\alpha}_{k_{max}}\}
    Output: Best mixture model θ^best\hat{\boldsymbol{\theta}}_{best}
    t←0t \leftarrow 0
    knz←kmaxk_{nz} \leftarrow k_{max}
    Lmin←+∞\mathcal{L}_{min} \leftarrow +\infty
    Compute um(i)←p(y(i)∣θ^m)u_m^{(i)} \leftarrow p(\mathbf{y}^{(i)} | \hat{\boldsymbol{\theta}}_m) for m=1,…,kmaxm = 1, \dots, k_{max} and i=1,…,ni = 1, \dots, n
    while knz≥kmink_{nz} \ge k_{min} do
        repeat
            t←t+1t \leftarrow t + 1
            for m=1m = 1 to kmaxk_{max} do
                if α^m>0\hat{\alpha}_m > 0 then
                    for i=1i = 1 to nn do
                        wm(i)←α^mum(i)(∑j=1kmaxα^juj(i))−1w_m^{(i)} \leftarrow \hat{\alpha}_m u_m^{(i)} \left(\sum_{j=1}^{k_{max}} \hat{\alpha}_j u_j^{(i)}\right)^{-1}
                    α^m←max⁡{0,∑i=1nwm(i)−N2}(∑j=1kmaxmax⁡{0,∑i=1nwj(i)−N2})−1\hat{\alpha}_m \leftarrow \max\left\{0, \sum_{i=1}^n w_m^{(i)} - \frac{N}{2}\right\} \left(\sum_{j=1}^{k_{max}} \max\left\{0, \sum_{i=1}^n w_j^{(i)} - \frac{N}{2}\right\}\right)^{-1}
                    {α^1,…,α^kmax}←{α^1,…,α^kmax}(∑j=1kmaxα^j)−1\{\hat{\alpha}_1, \dots, \hat{\alpha}_{k_{max}}\} \leftarrow \{\hat{\alpha}_1, \dots, \hat{\alpha}_{k_{max}}\} \left(\sum_{j=1}^{k_{max}} \hat{\alpha}_j\right)^{-1}
                    if α^m>0\hat{\alpha}_m > 0 then
                        θ^m←arg⁡max⁡θmQ(θ,θ^(t))\hat{\boldsymbol{\theta}}_m \leftarrow \arg\max_{\boldsymbol{\theta}_m} Q(\boldsymbol{\theta}, \hat{\boldsymbol{\theta}}(t))
                        Update um(i)←p(y(i)∣θ^m)u_m^{(i)} \leftarrow p(\mathbf{y}^{(i)} | \hat{\boldsymbol{\theta}}_m) for i=1,…,ni = 1, \dots, n
                    else
                        knz←knz−1k_{nz} \leftarrow k_{nz} - 1
            θ^(t)←{θ^1,…,θ^kmax,α^1,…,α^kmax}\hat{\boldsymbol{\theta}}(t) \leftarrow \{\hat{\boldsymbol{\theta}}_1, \dots, \hat{\boldsymbol{\theta}}_{k_{max}}, \hat{\alpha}_1, \dots, \hat{\alpha}_{k_{max}}\}
            L(θ^(t),Y)←N2∑m:α^m>0log⁡(nα^m12)+knz2log⁡n12+knz(N+1)2−∑i=1nlog⁡∑m=1kmaxα^mum(i)\mathcal{L}(\hat{\boldsymbol{\theta}}(t), \mathcal{Y}) \leftarrow \frac{N}{2} \sum_{m: \hat{\alpha}_m > 0} \log\left(\frac{n \hat{\alpha}_m}{12}\right) + \frac{k_{nz}}{2} \log\frac{n}{12} + \frac{k_{nz}(N+1)}{2} - \sum_{i=1}^n \log\sum_{m=1}^{k_{max}} \hat{\alpha}_m u_m^{(i)}
        until L(θ^(t−1),Y)−L(θ^(t),Y)<ϵ∣L(θ^(t−1),Y)∣\mathcal{L}(\hat{\boldsymbol{\theta}}(t-1), \mathcal{Y}) - \mathcal{L}(\hat{\boldsymbol{\theta}}(t), \mathcal{Y}) < \epsilon |\mathcal{L}(\hat{\boldsymbol{\theta}}(t-1), \mathcal{Y})|
        if L(θ^(t),Y)≤Lmin\mathcal{L}(\hat{\boldsymbol{\theta}}(t), \mathcal{Y}) \le \mathcal{L}_{min} then
            Lmin←L(θ^(t),Y)\mathcal{L}_{min} \leftarrow \mathcal{L}(\hat{\boldsymbol{\theta}}(t), \mathcal{Y})
            θ^best←θ^(t)\hat{\boldsymbol{\theta}}_{best} \leftarrow \hat{\boldsymbol{\theta}}(t)
        m∗←arg⁡min⁡m:α^m>0{α^m}m^* \leftarrow \arg\min_{m: \hat{\alpha}_m > 0} \{\hat{\alpha}_m\}
        α^m∗←0\hat{\alpha}_{m^*} \leftarrow 0
        knz←knz−1k_{nz} \leftarrow k_{nz} - 1

  4. Knowl 4 — Parameter Estimation Updates for Multivariate Gaussian Mixtures

    equation

    For a multivariate Gaussian mixture with unconstrained covariance matrices in Rd\mathbb{R}^d, each component density is:

    p(y∣θm)=(2π)−d/2∣Cm∣exp⁡{−12(y−μm)TCm−1(y−μm)}p(\mathbf{y}|\boldsymbol{\theta}_m) = \frac{(2\pi)^{-d/2}}{\sqrt{|\mathbf{C}_m|}} \exp\left\{-\frac{1}{2}(\mathbf{y} - \boldsymbol{\mu}_m)^T \mathbf{C}_m^{-1} (\mathbf{y} - \boldsymbol{\mu}_m)\right\}

    where θm=(μm,Cm)\boldsymbol{\theta}_m = (\boldsymbol{\mu}_m, \mathbf{C}_m) and the number of parameters per component is N=d+d(d+1)2N = d + \frac{d(d+1)}{2}.

    Given the posterior weights wm(i)w_m^{(i)}, the M-step parameter updates for active components (where α^m(t+1)>0\hat{\alpha}_m(t+1) > 0) are:

    μ^m(t+1)=∑i=1nwm(i)y(i)∑i=1nwm(i)\hat{\boldsymbol{\mu}}_m(t+1) = \frac{\sum_{i=1}^n w_m^{(i)} \mathbf{y}^{(i)}}{\sum_{i=1}^n w_m^{(i)}}

    C^m(t+1)=∑i=1nwm(i)(y(i)−μ^m(t+1))(y(i)−μ^m(t+1))T∑i=1nwm(i)\hat{\mathbf{C}}_m(t+1) = \frac{\sum_{i=1}^n w_m^{(i)} (\mathbf{y}^{(i)} - \hat{\boldsymbol{\mu}}_m(t+1))(\mathbf{y}^{(i)} - \hat{\boldsymbol{\mu}}_m(t+1))^T}{\sum_{i=1}^n w_m^{(i)}}

    When covariance matrices are constrained to be diagonal, Cm=diag(σm,12,…,σm,d2)\mathbf{C}_m = \text{diag}(\sigma_{m,1}^2, \dots, \sigma_{m,d}^2), the parameter count is N=2dN = 2d, and the variance along coordinate j∈{1,…,d}j \in \{1, \dots, d\} is updated as:

    σ^m,j2(t+1)=∑i=1nwm(i)(yj(i)−μ^m,j(t+1))2∑i=1nwm(i)\hat{\sigma}_{m,j}^2(t+1) = \frac{\sum_{i=1}^n w_m^{(i)} (y_j^{(i)} - \hat{\mu}_{m,j}(t+1))^2}{\sum_{i=1}^n w_m^{(i)}}

  5. Knowl 5 — Initialization Rule and Component Bound for Unsupervised Mixture Learning

    model/method

    The algorithm initializes kmaxk_{max} components (where kmaxk_{max} is an over-estimate of the true component count) by distributing them across the data space:

    1. Initial Means: The kmaxk_{max} mean vectors μ^m(0)\hat{\boldsymbol{\mu}}_m(0) are set to randomly chosen data points from the dataset Y={y(1),…,y(n)}\mathcal{Y} = \{\mathbf{y}^{(1)}, \dots, \mathbf{y}^{(n)}\}.

    2. Initial Covariances: Initial covariance matrices are set proportional to the identity matrix:

    C^m(0)=σ2I\hat{\mathbf{C}}_m(0) = \sigma^2 \mathbf{I}

    where σ2=110dtrace(1n∑i=1n(y(i)−m)(y(i)−m)T)\sigma^2 = \frac{1}{10 d} \text{trace}\left(\frac{1}{n} \sum_{i=1}^n (\mathbf{y}^{(i)} - \mathbf{m})(\mathbf{y}^{(i)} - \mathbf{m})^T\right) and m=1n∑i=1ny(i)\mathbf{m} = \frac{1}{n} \sum_{i=1}^n \mathbf{y}^{(i)} is the sample mean of the full dataset.

    1. Component Bound: To guarantee with probability at least 1−ε1 - \varepsilon that every true component with minimum mixing probability αmin=min⁡{α1,…,αk}\alpha_{min} = \min\{\alpha_1, \dots, \alpha_k\} is initialized with at least one data point representing it, the initial component count kk must satisfy:

    k>log⁡εlog⁡(1−αmin)k > \frac{\log \varepsilon}{\log(1 - \alpha_{min})}

    For example, setting αmin=0.1\alpha_{min} = 0.1 and ε=0.05\varepsilon = 0.05 requires kmax>28k_{max} > 28.

  6. Knowl 6 — Performance on Brodatz Texture Feature Classification Benchmark

    data/table

    Classification performance on a 4-class Brodatz texture classification task using 19-dimensional Gabor filter features (4,000 total observations; 800 training and 200 test samples per class, evaluated over 50 random splits):

    Method Mean error rate Error rate standard deviation
    Mixture-based, our method 0.0074 0.0020
    Mixture-based, EM and MDL/BIC 0.0075 0.0019
    Linear discriminant 0.0185 0.0024
    Quadratic discriminant 0.0155 0.0027

    The unsupervised mixture learning algorithm achieves test accuracy comparable to standard EM paired with exhaustive MDL/BIC model selection (0.00740.0074 vs 0.00750.0075) while reducing the computational cost by approximately a factor of 10 (requiring ∼0.1\sim 0.1 of the runtime). Both mixture-based approaches significantly outperform linear and quadratic discriminants. On this benchmark, alternative criteria including Laplace-empirical criterion (LEC) and Integrated Classification Likelihood (ICL) yield substantially worse results.

  7. Knowl 7 — Component Selection Robustness and Separation Sensitivity

    empirical result

    Evaluating model order selection across 50 simulations on equiprobable two-component Gaussian mixtures (μ1=0\boldsymbol{\mu}_1 = \mathbf{0}, μ2=[δ,…,δ]T\boldsymbol{\mu}_2 = [\delta, \dots, \delta]^T, C1=C2=I\mathbf{C}_1 = \mathbf{C}_2 = \mathbf{I}, n=800n = 800) reveals:

    1. Bivariate Case (d=2d=2, distance δ\delta): With free covariance matrices, the proposed unsupervised method matches or outperforms the Laplace-empirical criterion (LEC) across separations δ∈[1.8,2.6]\delta \in [1.8, 2.6], achieving >90%>90\% correct component selection at δ≥2.3\delta \ge 2.3 with 5 to 7 times fewer iterations than standard EM search. MDL/BIC requires δ≥2.5\delta \ge 2.5 to achieve >80%>80\% accuracy, while Integrated Classification Likelihood (ICL) underperforms when components overlap.

    2. 10-Dimensional Case (d=10d=10, distance δ10\delta\sqrt{10}): With unconstrained covariance matrices (N=65N = 65), the method reaches 100%100\% accuracy for δ≥1.35\delta \ge 1.35, whereas LEC completely breaks down by selecting kmaxk_{max} components regardless of separation. With diagonal covariance constraints, the proposed method reaches 100%100\% correct selection at δ≥0.5\delta \ge 0.5, outperforming MDL/BIC, LEC, and ICL.

    3. Real-World Datasets: On the 4-dimensional Iris dataset (n=150n=150), the method selects knz=3k_{nz}=3 in 100% of 100 runs (in 30 to 50 iterations). On the univariate acidity (n=155n=155) and enzyme (n=245n=245) datasets, the method selects knz=3k_{nz}=3 and knz=4k_{nz}=4 respectively, matching the modes of the marginal posterior distribution p(k∣Y)p(k|\mathcal{Y}) obtained by reversible-jump MCMC.

  8. Knowl 8 — Application of Unsupervised Learning to Mixtures of Factor Analyzers

    model/method

    The unsupervised mixture learning algorithm applies directly to Mixtures of Factor Analyzers (MFA) for joint density estimation and local dimensionality reduction. Under an MFA model, the observation y∈Rd\mathbf{y} \in \mathbb{R}^d generated by component mm is modeled as:

    y=μm+Λmv+n\mathbf{y} = \boldsymbol{\mu}_m + \mathbf{\Lambda}_m \mathbf{v} + \mathbf{n}

    where v∼N(0,Iq)\mathbf{v} \sim \mathcal{N}(\mathbf{0}, \mathbf{I}_q) is a qq-dimensional latent factor (q<dq < d), Λm∈Rd×q\mathbf{\Lambda}_m \in \mathbb{R}^{d \times q} is the factor loading matrix, and n∼N(0,Ψm)\mathbf{n} \sim \mathcal{N}(\mathbf{0}, \mathbf{\Psi}_m) is sensor noise with diagonal covariance matrix Ψm=diag(ψm,12,…,ψm,d2)\mathbf{\Psi}_m = \text{diag}(\psi_{m,1}^2, \dots, \psi_{m,d}^2). The marginal covariance of component mm is Cm=ΛmΛmT+Ψm\mathbf{C}_m = \mathbf{\Lambda}_m \mathbf{\Lambda}_m^T + \mathbf{\Psi}_m.

    For 3-dimensional noisy shrinking spiral data (d=3,n=900d=3, n=900) modeled using 1D factor analyzers (q=1q=1, with N=9N = 9 parameters per component: 3 mean, 3 loading, and 3 noise parameters), starting from an initial configuration of kmax=40k_{max} = 40 components reliably prunes superfluous components and converges to knz=13k_{nz} = 13 in 28 out of 30 runs (and knz∈{11,12}k_{nz} \in \{11, 12\} in the remaining two) in 300 to 400 iterations, extracting a piecewise-linear manifold representation without becoming trapped in local minima.

  9. Knowl 9 — Premature Component Annihilation Under Imbalanced Mixing Weights

    limitation

    The algorithm's primary failure mode occurs on mixtures containing components with widely disparate mixing weights. If a genuine component has a very small mixing probability (e.g., αm<0.05\alpha_m < 0.05) and spatial overlap with a heavier component, its effective data support ∑i=1nwm(i)\sum_{i=1}^n w_m^{(i)} can fall below the parameter penalty threshold N2\frac{N}{2} during early iterations.

    When this occurs, the low-weight component is annihilated prematurely before its mean and covariance parameters can adapt to fit its data subset, and its probability mass is absorbed into the overlapping heavier component. This issue stems from the uniform penalty N2\frac{N}{2} applied equally across all components in the modified M-step.

Coverage note — No substantial contributed material was omitted; intermediate MML mathematical derivations in the appendix were excluded in accordance with the extraction rules.

References

  1. 1.J. Banfield and A. Raftery, "Model-Based Gaussian and Non-Gaussian Clustering," Biometrics, vol. 49, pp. 803-821, 1993.
  2. 2.H. Bensmail, G. Celeux, A. Raftery, and C. Robert, "Inference in Model-Based Cluster Analysis," Statistics and Computing, vol. 7, pp. 1-10, 1997.
  3. 3.J. Bernardo and A. Smith, Bayesian Theory. Chichester, UK: J. Wiley & Sons, 1994.
  4. 4.D. Bertsekas, Nonlinear Programming. Belmont, Mass.: Athena Scientific, 1999.
  5. 5.C. Biernacki, G. Celeux, and G. Govaert, "Assessing a Mixture Model for Clustering with the Integrated Classification Likelihood," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 7, pp. 719-725, July 2000.
  6. 6.C. Biernacki, G. Celeux, and G. Govaert, "An Improvement of the NEC Criterion for Assessing the Number of Clusters in a Mixture Model," Pattern Recognition Letters, vol. 20, pp. 267-272, 1999.
  7. 7.C. Biernacki and G. Govaert, "Using the Classification Likelihood to Choose the Number of Clusters," Computing Science and Statistics, vol. 29, pp. 451-457, 1997.
  8. 8.H. Bozdogan, "Choosing the Number of Component Clusters in the Mixture Model Using a New Informational Complexity Criterion of the Inverse-Fisher Information Matrix," Information and Classification, O. Opitz, B. Lausen, and R. Klar, eds., pp. 40-54, Springer Verlag, 1993.
  9. 9.M. Brand, "Structure Learning in Conditional Probability Models Via Entropic Prior and Parameter Extinction," Neural Computation, vol. 11, pp. 1155-1182, 1999.
  10. 10.J. Campbell, C. Fraley, F. Murtagh, and A. Raftery, "Linear Flaw Detection in Woven Textiles Using Model-Based Clustering," Pattern Recognition Letters, vol. 18, pp. 1539-1548, 1997.
  11. 11.G. Celeux, S. Chrétien, F. Forbes, and A. Mkhadri, "A Component-Wise EM Algorithm for Mixtures," Technical report 3746, INRIA Rhône-Alpes, France, 1999. Available at http://www.inria.fr/RRRT/RR-3746.html.
  12. 12.G. Celeux and G. Soromenho, "An Entropy Criterion for Assessing the Number of Clusters in a Mixture Model," J. Classification, vol. 13, pp. 195-212, 1996.
  13. 13.S. Chrétien and A. Hero III, "Kullback Proximal Algorithms for Maximum Likelihood Estimation," IEEE Trans. Information Theory, vol. 46, pp. 1800-1810, 2000.
  14. 14.J. Conway and N. Sloane, Sphere Packings, Lattices, and Groups. New York: Springer Verlag, 1993.
  15. 15.T. Cover and J. Thomas, Elements of Information Theory. New York: John Wiley & Sons, 1991.
  16. 16.S. Dalal and W. Hall, "Approximating Priors by Mixtures of Natural Conjugate Priors," J. Royal Statistical Soc. (B), vol. 45, 1983.
  17. 17.A. Dasgupta and A. Raftery, "Detecting Features in Spatial Point Patterns with Clutter Via Model-Based Clustering," J. Am. Statistical Assoc., vol. 93, pp. 294-302, 1998.
  18. 18.A. Dempster, N. Laird, and D. Rubin, "Maximum Likelihood Estimation from Incomplete Data Via the EM Algorithm," J. Royal Statistical Soc. B, vol. 39, pp. 1-38, 1977.
  19. 19.R. Duda and P. Hart, Pattern Classification and Scene Analysis. New York: John Wiley & Sons, 1973.
  20. 20.M. Figueiredo and A.K. Jain, "Unsupervised Selection and Estimation of Finite Mixture Models," Proc. Int'l Conf. Pattern Recognition—ICPR-2000, pp. 87-90, 2000.
  21. 21.M. Figueiredo, J. Leitão, and A.K. Jain, "On Fitting Mixture Models," Energy Minimization Methods in Computer Vision and Pattern Recognition, E. Hancock and M. Pellilo, eds., pp. 54-69, Springer Verlag, 1999.
  22. 22.C. Fraley and A. Raftery, "How Many Clusters? Which Clustering Method? Answers Via Model-Based Cluster Analysis," Technical Report 329, Dept. Statistics, Univ. Washington, Seattle, WA, 1998.
  23. 23.Z. Ghahramani and M. Beal, "Variational Inference for Bayesian Mixtures of Factor Analyzers," Advances in Neural Information Systems 12, S. Solla, T. Leen, and K.-R. Müller, eds., pp. 449-455, MIT Press, 2000.
  24. 24.Z. Ghahramani and G. Hinton, "The EM Algorithm for Mixtures of Factor Analyzers," Technical Report CRG-TR-96-1, Univ. of Toronto, Canada, 1997.
  25. 25.T. Hastie and R. Tibshirani, "Discriminant Analysis by Gaussian Mixtures," J. Royal Statistical Soc. (B), vol. 58, pp. 155-176, 1996.
  26. 26.G. Hinton, P. Dayan, and M. Revow, "Modeling the Manifolds of Images of Handwritten Digits," IEEE Trans. Neural Networks, vol. 8, pp. 65-74, 1997.
  27. 27.T. Hofmann and J. Buhmann, "Pairwise Data Clustering by Deterministic Annealing," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 1, pp. 1-14, Jan. 1997.
  28. 28.A.K. Jain and R. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
  29. 29.A.K. Jain, R. Duin, and J. Mao, "Statistical Pattern Recognition: A Review," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 1, pp. 4-38, Jan. 2000.
  30. 30.A.K. Jain and F. Farrokhnia, "Unsupervised Texture Segmentation Using Gabor Filters," Pattern Recognition, vol. 24, pp. 1167-1186, 1991.
  31. 31.M. Kloppenburg and P. Tavan, "Deterministic Annealing for Density Estimation by Multivariate Normal Mixtures," Physical Rev. E, vol. 55, pp. R2089-R2092, 1997.
  32. 32.A. Lanterman, "Schwarz, Wallace, and Rissanen: Intertwining Themes in Theories of Model Order Estimation," Int'l Statistical Rev., vol. 69, pp. 185-212, Aug. 2001.
  33. 33.G. McLachlan, "On Bootstrapping the Likelihood Ratio Test Statistic for the Number of Components in a Normal Mixture," J. Royal Statistical Soc. Series (C), vol. 36, pp. 318-324, 1987.
  34. 34.G. McLachlan, Discriminant Analysis and Statistical Pattern Recognition. New York: John Wiley & Sons, 1992.
  35. 35.G. McLachlan and K. Basford, Mixture Models: Inference and Application to Clustering. New York: Marcel Dekker, 1988.
  36. 36.G. McLachlan and T. Krishnan, The EM Algorithm and Extensions. New York: John Wiley & Sons, 1997.
  37. 37.G. McLachlan and D. Peel, Finite Mixture Models. New York: John Wiley & Sons, 2000.
  38. 38.P. Meinicke and H. Ritter, "Resolution-Based Complexity Control for Gaussian Mixture Models," Neural Computation, vol. 13, no. 2, pp. 453-475, 2001.
  39. 39.K. Mengersen and C. Robert, "Testing for Mixtures: A Bayesian Entropic Approach," Proc. Fifth Valencia Int'l Meeting Bayesian Statistics 5, J. Bernardo, J. Berger, A. Dawid, and F. Smith, eds., pp. 255-276, 1996.
  40. 40.R. Neal, "Bayesian Mixture Modeling," Proc. 11th Int'l Workshop Maximum Entropy and Bayesian Methods of Statistical Analysis, pp. 197-211, 1992.
  41. 41.R. Neal and G. Hinton, "A View of the EM Algorithm that Justifies Incremental, Sparse, and Other Variants," Learning in Graphical Models, M.I. Jordan, ed., pp. 355-368, Kluwer Academic Publishers, 1998.
  42. 42.J. Oliver, R. Baxter, and C. Wallace, "Unsupervised Learning Using MML," Proc. 13th Int'l Conf. Machine Learning, pp. 364-372, 1996.
  43. 43.P. Pudil, J. Novovicova, and J. Kittler, "Feature Selection Based on the Approximation of Class Densities by Finite Mixtures of the Special Type," Pattern Recognition, vol. 28, no. 9, pp. 1389-1398, 1995.
  44. 44.A. Rangarajan, "Self Annealing: Unifying Deterministic Annealing and Relaxation Labeling," Energy Minimization Methods in Computer Vision and Pattern Recognition, M. Pellilo and E. Hancock, eds., pp. 229-244, Springer Verlag, 1997.
  45. 45.C. Rasmussen, "The Infinite Gaussian Mixture Model," Advances in Neural Information Processing Systems 12, S. Solla, T. Leen, and K.-R. Müller, eds., pp. 554-560, MIT Press, 2000.
  46. 46.S. Raudys and A.K. Jain, "Small Sample Size Effects in Statistical Pattern Recognition: Recommendations for Practitioners," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, pp. 252-264, 1991.
  47. 47.S. Raudys and V. Pikelis, "On Dimensionality, Sample Size, Classification Error, and Complexity of Classification Algorithms in Pattern Recognition," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 2, pp. 243-252, 1980.
  48. 48.S. Richardson and P. Green, "On Bayesian Analysis of Mixtures with Unknown Number of Components," J. Royal Statistical Soc. B, vol. 59, pp. 731-792, 1997.
  49. 49.J. Rissanen, Stochastic Complexity in Statistical Inquiry. Singapore: World Scientific, 1989.
  50. 50.S. Roberts, D. Husmeier, I. Rezek, and W. Penny, "Bayesian Approaches to Gaussian Mixture Modelling," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 11, pp. 1133-1142, Nov. 1998.
  51. 51.K. Roeder and L. Wasserman, "Practical Bayesian Density Estimation Using Mixtures of Normals," J. Am. Statistical Assoc., vol. 92, pp. 894-902, 1997.
  52. 52.K. Rose, "Deterministic Annealing for Clustering, Compression, Classification, Regression, and Related Optimization Problems," Proc. IEEE, vol. 86, pp. 2210-2239, 1998.
  53. 53.G. Schwarz, "Estimating the Dimension of a Model, Annals of Statistics, vol. 6, pp. 461-464, 1978.
  54. 54.P. Smyth, "Model Selection for Probabilistic Clustering Using Cross-Validated Likelihood," Statistics and Computing, vol. 10, no. 1, pp. 63-72, 2000.
  55. 55.R. Streit and T. Luginbuhl, "Maximum Likelihood Training of Probabilistic Neural Networks," IEEE Trans. Neural Networks, vol. 5, no. 5, pp. 764-783, 1994.
  56. 56.M. Tipping and C. Bishop, "Mixtures of Probabilistic Principal Component Analyzers," Neural Computation, vol. 11, no. 2, pp. 443-482, 1999.
  57. 57.D. Titterington, A. Smith, and U. Makov, Statistical Analysis of Finite Mixture Distributions. Chichester, U.K.: John Wiley & Sons, 1985.
  58. 58.N. Ueda and R. Nakano, "Deterministic Annealing EM Algorithm," Neural Networks, vol. 11, pp. 271-282, 1998.
  59. 59.N. Ueda, R. Nakano, Z. Gharhamani, and G. Hinton, "SMEM Algorithm for Mixture Models," Neural Computation, vol. 12, pp. 2109-2128, 2000.
  60. 60.C. Wallace and D. Dowe, "Minimum Message Length and Kolmogorov Complexity," The Computer J., vol. 42, no. 4, pp. 270-283, 1999.
  61. 61.C. Wallace and P. Freeman, "Estimation and Inference Via Compact Coding," J. Royal Statistical Soc. (B), vol. 49, no. 3, pp. 241-252, 1987.
  62. 62.M. Windham and A. Cutler, "Information Ratios for Validating Mixture Analysis," J. Am. Statistical Assoc., vol. 87, pp. 1188-1192, 1992.
  63. 63.L. Xu and M. Jordan, "On Convergence Properties of the EM Algorithm for Gaussian Mixtures," Neural Computation, vol. 8, pp. 129-151, 1996.
  64. 64.A. Zellner, "Maximal Data Information Prior Distributions," New Developments in the Applications of Bayesian Methods, A. Aykac and C. Brumat, eds., pp. 211-232, Amsterdam: North Holland, 1977.

Citation

MLA
Figueiredo, M. A. T., and A. K. Jain. “Unsupervised Learning of Finite Mixture Models”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 3, 2002, pp. 381–96, https://doi.org/10.1109/34.990138.
APA
Figueiredo, M. A. T., & Jain, A. K. (2002). Unsupervised learning of finite mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(3), 381–396. https://doi.org/10.1109/34.990138
Chicago
Figueiredo, M. A. T., and A. K. Jain. 2002. “Unsupervised Learning of Finite Mixture Models”. IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (3): 381–96. https://doi.org/10.1109/34.990138.
Harvard
Figueiredo, M.A.T. and Jain, A.K. (2002) “Unsupervised learning of finite mixture models”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(3), pp. 381–396. Available at: https://doi.org/10.1109/34.990138.
Vancouver
1. Figueiredo MAT, Jain AK (2002) Unsupervised learning of finite mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence 24:381–396

BibTeX

@article{Figueiredo_2002, title={Unsupervised learning of finite mixture models}, volume={24}, ISSN={2160-9292}, url={http://dx.doi.org/10.1109/34.990138}, DOI={10.1109/34.990138}, number={3}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Figueiredo, M.A.T. and Jain, A.K.}, year={2002}, month=Mar, pages={381–396} }
Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF