Unified Expectation Maximization

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 688–698, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Unified Expectation Maximization Rajhans Samdani University of Illinois rsamdan2@illinois.edu Ming-Wei Chang Microsoft Research minchang@microsoft.com Dan Roth University of Illinois danr@illinois.edu Abstract We present a general framework containing a graded spectrum of Expectation Maximization (EM) algorithms called Unified Expectation Maximization (UEM.) UEM is parameterized by a single parameter and covers existing al- gorithms like standard EM and hard EM, con- strained versions of EM such as Constraint- Driven Learning (Chang et al., 2007) and Pos- terior Regularization (Ganchev et al., 2010), along with a range of new EM algorithms. For the constrained inference step in UEM we present an efficient dual projected gradient as- cent algorithm which generalizes several dual decomposition and Lagrange relaxation algo- rithms popularized recently in the NLP litera- ture (Ganchev et al., 2008; Koo et al., 2010; Rush and Collins, 2011). UEM is as efficient and easy to implement as standard EM. Fur- thermore, experiments on POS tagging, infor- mation extraction, and word-alignment show that often the best performing algorithm in the UEM family is a new algorithm that wasn’t available earlier, exhibiting the benefits of the UEM framework. 1 Introduction Expectation Maximization (EM) (Dempster et al., 1977) is inarguably the most widely used algo- rithm for unsupervised and semi-supervised learn- ing. Many successful applications of unsupervised and semi-supervised learning in NLP use EM in- cluding text classification (McCallum et al., 1998; Nigam et al., 2000), machine translation (Brown et al., 1993), and parsing (Klein and Manning, 2004). Recently, EM algorithms which incorporate con- straints on structured output spaces have been pro- posed (Chang et al., 2007; Ganchev et al., 2010). Several variations of EM (e.g. hard EM) exist in the literature and choosing a suitable variation is of- ten very task-specific. Some works have shown that for certain tasks, hard EM is more suitable than reg- ular EM (Spitkovsky et al., 2010). The same issue continues in the presence of constraints where Poste- rior Regularization (PR) (Ganchev et al., 2010) cor- responds to EM while Constraint-Driven Learning (CoDL)1 (Chang et al., 2007) corresponds to hard EM. The problem of choosing between EM and hard EM (or between PR and CoDL) remains elusive, along with the possibility of simple and better alter- natives, to practitioners. Unfortunately, little study has been done to understand the relationships be- tween these variations in the NLP community. In this paper, we approach various EM-based techniques from a novel perspective. We believe that “EM or Hard-EM?” and “PR or CoDL?” are not the right questions to ask. Instead, we present a unified framework for EM, Unified EM (UEM), that covers many EM variations including the constrained cases along with a continuum of new ones. UEM allows us to compare and investigate the properties of EM in a systematic way and helps find better alternatives. The contributions of this paper are as follows: 1. We …

Content truncated to 500 words