A Comparison of PCFG Models

In: Proceedings of CoNLL-2000 and LLL-2000, pages 123-125, Lisbon, Portugal, 2000. A Comparison of PCFG Models* Jose Luis Verdd-Mas and Jorge Calera-Rubio and Rafael C. Carrasco Departament de Llenguatges i Sistemes Inform£tics Universitat d'Alacant, E-03071 Alacant (Spain) (verdu, calera, carrasco)@dlsi.ua.es Abstract In this paper, we compare three different ap- proaches to build a probabilistic context-free grammar for natural language parsing from a tree bank corpus: 1) a model that simply ex- tracts the rules contained in the corpus and counts the number of occurrences of each rule 2) a model that also stores information about the parent node's category and, 3) a model that estimates the probabilities according to a gen- eralized k-gram scheme with k -- 3. The last one allows for a faster parsing and decreases the perplexity of test samples. 1 Introduction Recent work (Johnson, 1998) has explored the performance of parsers based on a probabilistic context-free grammar (PCFG) extracted from a training corpus. The results show that the type of tree representation used in the corpus can have a substantial effect in the estimated like- lihood of each sentence or parse tree. Accord- ing to (Johnson, 1998), weaker independence as- sumptions --such as decreasing the number of nodes or increasing the number of node labels-- improve the efficiency of the parser. The best results were obtained with parent-annotated la- bels where each node stores contextual informa- tion in the form of the category of the node's parent. This fact is in agreement with the observation put forward by Charniak (Char- niak, 1996) that simple PCFGs, directly ob- tained from a corpus, largely overgeneralize. This property suggests that, in these models, a large probability mass is assigned to incorrect * Work partially supported by the Spanish CICYT un- der grant TIC97-0941. parses and, therefore, any procedure that con- centrates the probability on the correct parses will increase the likelihood of the samples. In this spirit, we introduce a generalization of the classic k-gram models, widely used for string processing (Brown et al., 1992; Ney et al., 1995), to the case of trees. The PCFG obtained in this way consists of rules that include information about the context where the rule is applied. The experiments were performed using the Wall Street Journal (WSJ) corpus of the Uni- versity of Pennsylvania (Marcus et al., 1993) modified as described in (Charniak, 1996) and (Johnson, 1998). 2 A generalized k-gram model Recall that k-gram models are stochastic mod- els for the generation of sequences sl,s2,... based on conditional probabilities, that is: 1. the probability P(sls2... stlM) of a se- quence in the model M is computed as a product pM( Sl )pM( S2[Sl ) " " " pM( St[Sl S2 . . . St-l), and 2. the dependence of the probabilities PM on previous history is assumed to be re- stricted to the immediate preceding con- text, in particular, the last k - 1 words: PM(St[Sl . . . St-1) ---- pM(St[St-k+l . . . St-1). Note that in this kind …

Content truncated to 500 words