A comparison of new and old algorithms for a mixture estimation problem

David P. Helmbold, Yoram Singer, Robert E. Schapire, Manfred K. Warmuth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised learning and give simple derivations for many of the standard iterative algorithms like gradient projection and EM. In this framework, the distance between the new and old proportion vectors is used as a penalty term. The square distance leads to the gradient projection update, and the relative entropy to a new update which we call the exponentiated gradient update (EG,). Curiously, when a second order Taylor expansion of the relative entropy is used, we arrive at an update EMη which, for η = 1, gives the usual EM update. Experimentally, both the EMη-update and the EGη-update for η > 1 outperform the EM algorithm and its variants. We also prove a worst-case polynomial bound on the global rate of convergence of the EGη algorithm.

Original languageEnglish (US)
Title of host publicationProceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
PublisherAssociation for Computing Machinery, Inc
Pages69-78
Number of pages10
ISBN (Electronic)0897917235, 9780897917230
DOIs
StatePublished - Jul 5 1995
Event8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States
Duration: Jul 5 1995Jul 8 1995

Publication series

NameProceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Volume1995-January

Other

Other8th Annual Conference on Computational Learning Theory, COLT 1995
CountryUnited States
CitySanta Cruz
Period7/5/957/8/95

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Artificial Intelligence
  • Software

Fingerprint Dive into the research topics of 'A comparison of new and old algorithms for a mixture estimation problem'. Together they form a unique fingerprint.

  • Cite this

    Helmbold, D. P., Singer, Y., Schapire, R. E., & Warmuth, M. K. (1995). A comparison of new and old algorithms for a mixture estimation problem. In Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 (pp. 69-78). (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January). Association for Computing Machinery, Inc. https://doi.org/10.1145/225298.225306