Unambiguity Regularization for Unsupervised Learning of Probabilistic Grammars

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1324–1334, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Unambiguity Regularization for Unsupervised Learning of Probabilistic Grammars Kewei Tu∗ Departments of Statistics and Computer Science University of California, Los Angeles Los Angeles, CA 90095, USA tukw@ucla.edu Vasant Honavar Department of Computer Science Iowa State University Ames, IA 50011, USA honavar@cs.iastate.edu Abstract We introduce a novel approach named unam- biguity regularization for unsupervised learn- ing of probabilistic natural language gram- mars. The approach is based on the observa- tion that natural language is remarkably unam- biguous in the sense that only a tiny portion of the large number of possible parses of a nat- ural language sentence are syntactically valid. We incorporate an inductive bias into gram- mar learning in favor of grammars that lead to unambiguous parses on natural language sentences. The resulting family of algorithms includes the expectation-maximization algo- rithm (EM) and its variant, Viterbi EM, as well as a so-called softmax-EM algorithm. The softmax-EM algorithm can be implemented with a simple and computationally efficient extension to standard EM. In our experiments of unsupervised dependency grammar learn- ing, we show that unambiguity regularization is beneficial to learning, and in combination with annealing (of the regularization strength) and sparsity priors it leads to improvement over the current state of the art. 1 Introduction Machine learning offers a potentially powerful ap- proach to learning probabilistic grammars from data. Because of the high cost of manual sentence anno- tation, there is substantial interest in unsupervised grammar learning, i.e., the induction of a grammar from a corpus of unannotated sentences. The sim- plest such approaches attempt to maximize the like- ∗Part of the work was done while at Iowa State University. lihood of the grammar given the training data, typi- cally using expectation-maximization (EM) (Baker, 1979; Lari and Young, 1990; Klein and Manning, 2004). More recent approaches incorporate addi- tional prior information of the target grammar into learning. For example, Kurihara and Sato (2004) used Dirichlet priors over rule probabilities to obtain smoothed estimates of the probabilities. Johnson et al. (2007) used Dirichlet priors with hyperparame- ters set to values less than 1 to encourage sparsity of grammar rules. Finkel et al. (2007) and Liang et al. (2007) proposed to use the hierarchical Dirichlet process prior to bias learning towards concise gram- mars without the need to pre-specify the number of nonterminals. Cohen et al. (2008) and Cohen and Smith (2009) employed the logistic normal prior to model the correlations between grammar symbols. Gillenwater et al. (2010) incorporated a sparsity bias on grammar rules into learning by means of poste- rior regularization. More recently, Spitkovsky et al. (2010) and Poon and Domingos (2011) observed that the use of Viterbi EM (also called hard EM) in place of stan- dard EM can lead to significantly improved results in unsupervised learning of probabilistic grammars from natural language and image data respectively, even if …

Content truncated to 500 words