Immediate-Head Parsing for Language Models

Immediate-Head Parsing for Language Models � Eugene Charniak Brown Laboratory for Linguistic Information Processing Department of Computer Science Brown University, Box 1910, Providence RI ec@cs.brown.edu Abstract We present two language models based upon an “immediate-head” parser — our name for a parser that conditions all events below a constituent c upon the head of c. While all of the most accurate statistical parsers are of the immediate-head variety, no previous grammatical language model uses this technology. The perplexity for both of these models significantly improve upon the trigram model base-line as well as the best previous grammar- based language model. For the better of our two models these improvements are 24% and 14% respectively. We also suggest that improvement of the un- derlying parser should significantly im- prove the model’s perplexity and that even in the near term there is a lot of po- tential for improvement in immediate- head language models. 1 Introduction All of the most accurate statistical parsers [1,3, 6,7,12,14] are lexicalized in that they condition probabilities on the lexical content of the sen- tences being parsed. Furthermore, all of these �This research was supported in part by NSF grant LIS SBR 9720368 and by NSF grant 00100203 IIS0085980. The author would like to thank the members of the Brown Laboratory for Linguistic Information Processing (BLLIP) and particularly Brian Roark who gave very useful tips on conducting this research. Thanks also to Fred Jelinek and Ciprian Chelba for the use of their data and for detailed com- ments on earlier drafts of this paper. parsers are what we will call immediate-head parsers in that all of the properties of the imme- diate descendants of a constituent c are assigned probabilities that are conditioned on the lexical head of c. For example, in Figure 1 the probability that the vp expands into v np pp is conditioned on the head of the vp, “put”, as are the choices of the sub-heads under the vp, i.e., “ball” (the head of the np) and “in” (the head of the pp). It is the ex- perience of the statistical parsing community that immediate-head parsers are the most accurate we can design. It is also worthy of note that many of these parsers [1,3,6,7] are generative — that is, for a sentence s they try to find the parse � defined by Equation 1: arg max �p(� j s) = arg max �p(�, s) (1) This is interesting because insofar as they com- pute p(�, s) these parsers define a language-model in that they can (in principle) assign a probability to all possible sentences in the language by com- puting the sum in Equation 2: p(s) = X � p(�, s) (2) where p(�, s) is zero if the yield of � 6= s. Lan- guage models, of course, are of interest because speech-recognition systems require them. These systems determine the words that were spoken by solving Equation 3: arg maxsp(s j A) = arg maxsp(s)p(A j s) (3) where A denotes …

Content truncated to 500 words