Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1502–1511, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization Shay B. Cohen and Noah A. Smith School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA {scohen,nasmith}@cs.cmu.edu Abstract We consider the search for a maximum likelihood assignment of hidden deriva- tions and grammar weights for a proba- bilistic context-free grammar, the problem approximately solved by “Viterbi train- ing.” We show that solving and even ap- proximating Viterbi training for PCFGs is NP-hard. We motivate the use of uniform- at-random initialization for Viterbi EM as an optimal initializer in absence of further information about the correct model pa- rameters, providing an approximate bound on the log-likelihood. 1 Introduction Probabilistic context-free grammars are an essen- tial ingredient in many natural language process- ing models (Charniak, 1997; Collins, 2003; John- son et al., 2006; Cohen and Smith, 2009, inter alia). Various algorithms for training such models have been proposed, including unsupervised meth- ods. Many of these are based on the expectation- maximization (EM) algorithm. There are alternatives to EM, and one such al- ternative is Viterbi EM, also called “hard” EM or “sparse” EM (Neal and Hinton, 1998). Instead of using the parameters (which are maintained in the algorithm’s current state) to find the true pos- terior over the derivations, Viterbi EM algorithm uses a posterior focused on the Viterbi parse of those parameters. Viterbi EM and variants have been used in various settings in natural language processing (Yejin and Cardie, 2007; Wang et al., 2007; Goldwater and Johnson, 2005; DeNero and Klein, 2008; Spitkovsky et al., 2010). Viterbi EM can be understood as a coordinate ascent procedure that locally optimizes a function; we call this optimization goal “Viterbi training.” In this paper, we explore Viterbi training for probabilistic context-free grammars. We first show that under the assumption that P ̸= NP, solv- ing and even approximating the Viterbi training problem is hard. This result holds even for hid- den Markov models. We extend the main hardness result to the EM algorithm (giving an alternative proof to this known result), as well as the problem of conditional Viterbi training. We then describe a “competitiveness” result for uniform initializa- tion of Viterbi EM: we show that initialization of the trees in an E-step which uses uniform distri- butions over the trees is optimal with respect to a certain approximate bound. The rest of this paper is organized as follows. §2 gives background on PCFGs and introduces some notation. §3 explains Viterbi training, the declar- ative form of Viterbi EM. §4 describes a hardness result for Viterbi training. §5 extends this result to a hardness result of approximation and §6 further extends these results for other cases. §7 describes the advantages in using uniform-at-random initial- ization for Viterbi training. We relate these results to work on the k-means problem in §8. 2 Background and Notation We assume familiarity …

Content truncated to 500 words