A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars

The paper gives a brief review of the expectation-maximization algorithm (Dempster 1977) in the comprehensible framework of discrete mathematics. In Section 2, two prominent estimation methods, the relative-frequency estimation and the maximum-likelihood estimation are presented. Section 3 is dedicated to the expectation-maximization algorithm and a simpler variant, the generalized expectation-maximization algorithm. In Section 4, two loaded dice are rolled. A more interesting example is presented in Section 5: The estimation of probabilistic context-free grammars.

• Publication year

  2004

• Venue

  arXiv.org

• Publication date

  2004-12-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv cs/0412015
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elements of Information Theory

  2005influential reference
• Inside-Outside Estimation Meets Dynamic EM

  2004cited by this paper
• The estimation of stochastic context-free grammars using the Inside-Outside algorithm

  2003cited by this paper
• Accurate Unlexicalized Parsing

  2003cited by this paper
• Probabilistic Parsing as Intersection

  2003influential reference
• EM-basierte maschinelle Lernverfahren für natürliche Sprachen: Klassifizierung mehrdimensionaler linguistischer Daten und Modellierung lexikalisierter Grammatiken

  2002cited by this paper
• Estimation of Probabilistic Context-Free Grammars

  2002cited by this paper
• Pattern Classification (2nd ed.)

  1999cited by this paper
• Statistical Properties of Probabilistic Context-Free Grammars

  1999cited by this paper
• PCFG Models of Linguistic Tree Representations

  1998cited by this paper
• Consistency of Stochastic Context-Free Grammars From Probabilistic Estimation Based on Growth Transformations

  1997cited by this paper
• A Simple Introduction to Maximum Entropy Models for Natural Language Processing

  1997cited by this paper
• Tree-Bank Grammars

  1996cited by this paper
• The EM algorithm and extensions

  1996cited by this paper
• Inside-Outside Reestimation From Partially Bracketed Corpora

  1992cited by this paper
• Applications of stochastic context-free grammars using the Inside-Outside algorithm

  1990cited by this paper
• ON THE CONVERGENCE PROPERTIES OF THE EM ALGORITHM

  1983cited by this paper
• Introduction to Automata Theory, Languages and Computation

  1979cited by this paper
• Trainable grammars for speech recognition

  1979influential reference
• Maximum likelihood from incomplete data via the EM - algorithm plus discussions on the paper

  1977influential reference
• Applying Probability Measures to Abstract Languages

  1973cited by this paper
• An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process

  1972cited by this paper
• Probability and Statistics

  1959influential reference
• The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference

  1959cited by this paper
• Information Theory and Statistical Mechanics

  1957cited by this paper
• Three models for the description of language

  1956cited by this paper

• Adapting to Shifting Correlations with Unlabeled Data Calibration

  2024cites this paper
• New Technologies in Password Cracking Techniques

  2018cites this paper
• Count-based State Merging for Probabilistic Regular Tree Grammars

  2015cites this paper
• Probabilistic context-free grammar based password cracking: Attack, defense and applications

  2015cites this paper
• Syntax and Parsing of Semitic Languages

  2014cites this paper
• Position-and-Length-Dependent Context-Free Grammars - A New Type of Restricted Rewriting

  2014cites this paper
• Dynamic EM in Neologism Evolution

  2013cites this paper
• Decomposing and regenerating syntactic trees

  2012cites this paper
• Learning the latent structure of translation

  2012cites this paper
• State-Split for Hypergraphs with an Application to Tree Adjoining Grammars

  2012cites this paper
• Text-independent speaker identification system based on the histogram of DCT-cepstrum coefficients

  2012cites this paper
• Optimizing information using the EM algorithm in item response theory

  2012cites this paper
• Global Convergence of the EM Algorithm for Unconstrained Latent Variable Models with Categorical Indicators

  2012cites this paper
• Prioritization and pruning : effic ient inference with weighted context-free grammars : a dissertaion

  2012cites this paper
• Sampling and Approximation in the Context of RNA Secondary Structure Prediction - Algorithms and Studies Based on Stochastic Context-Free Modeling

  2012cites this paper
• Consistency of Probabilistic Context-Free Grammars

  2012influential citation
• Mobile Intention Recognition

  2011cites this paper
• Applying Length-Dependent Stochastic Context-Free Grammars to RNA Secondary Structure Prediction

  2011cites this paper
• Extending Stochastic Context-Free Grammars for an Application in Bioinformatics

  2010cites this paper
• Non Uniform Generation of Combinatorial Objects

  2010cites this paper
• Aplicação de modelos de Markov ocultos na obtenção de taxas de mortalidade das larvas do mosquito da Dengue

  2010cites this paper
• Inducing Lexicalised PCFGs with Latent Heads

  2010cites this paper
• Automatic feature learning and parameter estimation for Hidden Markov models using MCE and Gibbs sampling

  2009cites this paper
• Automatic Syntactic Parsing of the Hungarian Language Appliyng Rule-based Machine Learning Methods

  2008cites this paper
• Re-estimation of Lexical Parameters for Treebank PCFGs

  2008cites this paper
• Probabilistic Context-Free Grammars Estimated from Infinite Distributions

  2007cites this paper
• TOWARDS SIMPLER TREE SUBSTITUTION GRAMMARS

  2007cites this paper
• Corpus Induction of Lexicons for Treebank PCFGs by Inside-Outside Estimation and Frequency Transformations

  2006cites this paper
• Rich Lexicons and Restrictive Grammars: Maximum Likelihood Learning in Optimality Theory

  2006cites this paper
• SENTIMENT CLASSIFICATION OF MOVIE REVIEWS USING LINGUISTIC PARSING

  2006cites this paper
• Head-Driven PCFGs with Latent-Head Statistics

  2005cites this paper
• PROBABILISTIC CONTEXT-FREE GRAMMARS IN NATURAL LANGUAGE PROCESSING

  2005influential citation
• A Dual-Iterative Method for Concept-Word Acquisition from Large-Scale Chinese Corpora

  2005cites this paper
• Hierarchical iterative and self-supervised method for concept-word acquisition from large-scale Chinese corpora

  2005cites this paper
• Rank Consistent Estimation: The DOP Case

  2004cites this paper
• Towards Simpler Tree Substitution Grammars Msc in Logic

  year unknowncites this paper
• A Consistent and Efficient Estimator for the Data-oriented Parsing Model

  year unknowncites this paper