Global Optimization of Gaussian Mixture Models

The Expectation-Maximization algorithm is a well known and easy method for the estimation of Gaussian mixture models as well as its natural extension, model-based clustering. Nevertheless, even though the algorithm is easy to apply and numerically very stable, it only provides solutions which are locally optimal. Thus, Expectation-Maximization probably won’t obtain the globally optimal solution in Gaussian mixture analysis problems. This project report features a number of new algorithms meant to produce globally optimal solutions for Gaussian mixture models. The basis of these algorithms are techniques from the operations research literature, specifically the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). The new algorithms suggested in this project must efficiently simulate positive definite covariance matrices of the Gaussian mixture components. We have offered many new approaches to this problem. One option is to blend the updating procedure …

Watch a video on Expectation-Maximization (EM) for the Gaussian mixture model


1 Introduction
1.1 Background
1.2 Contributions of this Dissertation
2 Mathematical Background
2.1 Choosing the Optimal Number of Mixture Components
2.2 Finite Mixture Models
2.3 Model-Based Clustering
2.4 The Expectation-Maximization Algorithm
3 New Global Optimization Algorithms for Model-Based Clustering
3.1 Motivation
3.2 Global Optimization Methods
3.2.1 The Cross-Entropy Method Original CE Mixture Model Algorithm
3.2.2 Challenges of the CE Mixture Model Algorithm
3.2.3 Two New CE Mixture Model Algorithms CE-EM algorithm CE-CD Algorithm
3.2.4 Model Reference Adaptive Search
3.2.5 Two New MRAS mixture model algorithms MRAS-EM Algorithm MRAS-CD Algorithm
3.3 Numerical Experiments
3.3.1 Preventing Degenerate Clusters
3.3.2 Initial Parameters
3.3.3 Numerical Experiment 1
3.3.4 Numerical Experiment 2
3.3.5 Clustering of Survey Responses
3.3.6 A Fair Comparison
3.3.7 Does the Global Optimum “Matter”?
3.4 Discussion
4 Global Convergence of Gaussian Mixture Models with MRAS
4.1 Motivation
4.2 Model Reference Adaptive Search
4.2.1 Global Convergence of MRAS
4.3 MRAS algorithm for Gaussian Mixture Models
4.3.1 Preventing Degenerate Solutions
4.3.2 Proving Global Convergence of the MRAS Mixture Model Algorithm
4.4 Discussion
5 Landscape Analysis of Finite Mixture Models
5.1 Motivation
5.2 Measuring the Difficulty of Optimization Problems
5.2.1 A Fourth and New Attribute for Characterizing Optimization Problems
5.3 Calculating the Global Landscape Metrics
5.3.1 Applying Global Landscape Metrics to Known Examples Shekel’s Foxholes Goldstein-Price Function
5.3.2 Applying Global Landscape Metrics to Gaussian Mixtures
5.3.3 What to do with Degenerate Solutions?
5.4 Numerical Examples
5.4.1 3-component Bivariate Gaussian Mixture
5.4.2 6-component Bivariate Gaussian Mixture….

Source: UMD

Leave a Comment