Towards EM-style Algorithms for a posteriori Optimization of Normal Mixtures

Abstract: Expectation maximization (EM) provides a simple and elegant approach to the problem of optimizing the parameters of a normal mixture on an unlabeled dataset. To accomplish this, EM iteratively reweights the elements of the dataset until a locally optimal normal mixture is obtained. This paper explores the intriguing question of whether such an EM-style algorithm exists for the related and apparently more difficult problem of finding a normal mixture that maximizes the a posteriori class probabilities of a labeled dataset.

We expose a fundamental degeneracy in the relationship between a normal mixture and the a posteriori class probability functions that it induces, and use this degeneracy to prove that reweighting a dataset can almost always give rise to a normal mixture that exhibits any desired class function behavior. This establishes that EM-style approaches are sufficiently expressive for a posteriori optimization problems and opens the way to the design of new algorithms for them.

Keywords: Expectation Maximization (EM), Normal Mixtures, Gaussian Mixtures, Supervised Learning, Maximize mutual information (MMI).

• View the complete paper (converted to HTML)

• The complete paper (PDF)

• The complete paper (PostScript)

• The 1-page symposium version (PDF)

• The 1-page symposium version (PostScript)

• BibTex entry

• My homepage ( Peter N. Yianilos )

• See also:
  • A General Decomposition Theorem that Extends Baum-Welch and the Expectation-Maximization Paradigm to Rational Forms
  • Learning String Edit Distance
  • A Surficial Pronounciation Model
  • Topics in Computational Hidden State Modeling
  • Finite Growth Models

• Coauthors:
  • Eric Sven Ristad