Parse Forest Computation of Expected Governors

Parse Forest Computation of Expected Governors Helmut Schmid Institute for Computational Linguistics University of Stuttgart Azenbergstr. 12 70174 Stuttgart, Germany schmid@ims.uni-stuttgart.de Mats Rooth Department of Linguistics Cornell University Morrill Hall Ithaca, NY 14853, USA mats@cs.cornell.edu Abstract In a headed tree, each terminal word can be uniquely labeled with a gov- erning word and grammatical relation. This labeling is a summary of a syn- tactic analysis which eliminates detail, reflects aspects of semantics, and for some grammatical relations (such as subject of finite verb) is nearly un- controversial. We define a notion of expected governor markup, which sums vectors indexed by governors and scaled by probabilistic tree weights. The quantity is computed in a parse for- est representation of the set of tree anal- yses for a given sentence, using vector sums and scaling by inside probability and flow. 1 Introduction A labeled headed tree is one in which each non- terminal vertex has a distinguished head child, and in the usual way non-terminal nodes are la- beled with non-terminal symbols (syntactic cat- egories such as NP) and terminal vertices are labeled with terminal symbols (words such as The governor algorithm was designed and implemented in the Reading Comprehension research group in the 2000 Workshop on Language Engineering at Johns Hopkins Uni- versity. Thanks to Marc Light, Ellen Riloff, Pranav Anand, Brianne Brown, Eric Breck, Gideon Mann, and Mike Thelen for discussion and assistance. Oral presentations were made at that workshop in August 2000, and at the University of Sussex in January 2001. Thanks to Fred Jelinek, John Car- roll, and other members of the audiences for their comments. S ���� NP � �� � � Peter VP ���� V � ��� reads NP � �� NP � � � D � ��  every N � �� paper PP:on  ��� P:on � on NP  ��� N  ��� markup Figure 1: A tree with percolated lexical heads. reads).1 We work with syntactic trees in which terminals are in addition labeled with uninflected word forms (lemmas) derived from the lexicon. By percolating lemmas up the chains of heads, each node in a headed tree may be labeled with a lexical head. Figure 1 is an example, where lex- ical heads are written as subscripts. We use the notation   for the lexical head of a vertex  , and   for the ordinary category or word label of  . The governor label for a terminal vertex  such a labeled tree is a triple which representsin the syntactic and lexical environment at the top of the chain of vertices headed by  . Where is the maximal vertex of which  is a head vertex, and is the parent of , the governor label for  1Headed trees may be constructed as tree domains, which are sets of addresses of vertices. 0 is used as the relative ad- dress of the head vertex, negative integers are used as relative addresses of child vertices before the head, …

Content truncated to 500 words