Probabilistic CFG with Latent Annotations

Proceedings of the 43rd Annual Meeting of the ACL, pages 75–82, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Probabilistic CFG with latent annotations Takuya Matsuzaki � Yusuke Miyao � Jun’ichi Tsujii �� � Graduate School of Information Science and Technology, University of Tokyo Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033 � CREST, JST(Japan Science and Technology Agency) Honcho 4-1-8, Kawaguchi-shi, Saitama 332-0012 � matuzaki, yusuke, tsujii � @is.s.u-tokyo.ac.jp Abstract This paper defines a generative probabilis- tic model of parse trees, which we call PCFG-LA. This model is an extension of PCFG in which non-terminal symbols are augmented with latent variables. Fine- grained CFG rules are automatically in- duced from a parsed corpus by training a PCFG-LA model using an EM-algorithm. Because exact parsing with a PCFG-LA is NP-hard, several approximations are de- scribed and empirically compared. In ex- periments using the Penn WSJ corpus, our automatically trained model gave a per- formance of 86.6% (F � , sentences � 40 words), which is comparable to that of an unlexicalized PCFG parser created using extensive manual feature selection. 1 Introduction Variants of PCFGs form the basis of several broad- coverage and high-precision parsers (Collins, 1999; Charniak, 1999; Klein and Manning, 2003). In those parsers, the strong conditional independence as- sumption made in vanilla treebank PCFGs is weak- ened by annotating non-terminal symbols with many ‘features’ (Goodman, 1997; Johnson, 1998). Exam- ples of such features are head words of constituents, labels of ancestor and sibling nodes, and subcatego- rization frames of lexical heads. Effective features and their good combinations are normally explored using trial-and-error. This paper defines a generative model of parse trees that we call PCFG with latent annotations (PCFG-LA). This model is an extension of PCFG models in which non-terminal symbols are anno- tated with latent variables. The latent variables work just like the features attached to non-terminal sym- bols. A fine-grained PCFG is automatically induced from parsed corpora by training a PCFG-LA model using an EM-algorithm, which replaces the manual feature selection used in previous research. The main focus of this paper is to examine the effectiveness of the automatically trained models in parsing. Because exact inference with a PCFG-LA, i.e., selection of the most probable parse, is NP-hard, we are forced to use some approximation of it. We empirically compared three different approximation methods. One of the three methods gives a perfor- mance of 86.6% (F � , sentences � 40 words) on the standard test set of the Penn WSJ corpus. Utsuro et al. (1996) proposed a method that auto- matically selects a proper level of generalization of non-terminal symbols of a PCFG, but they did not report the results of parsing with the obtained PCFG. Henderson’s parsing model (Henderson, 2003) has a similar motivation as ours in that a derivation history of a parse tree is compactly represented by induced hidden variables (hidden layer activation of a neu- ral network), although the details of his approach is quite different from ours. 2 Probabilistic model PCFG-LA is …

Content truncated to 500 words