A Simple Pattern-matching Algorithm for Recovering Empty Nodes and their Antecedents

A simple pattern-matching algorithm for recovering empty nodes and their antecedents∗ Mark Johnson Brown Laboratory for Linguistic Information Processing Brown University Mark Johnson@Brown.edu Abstract This paper describes a simple pattern- matching algorithm for recovering empty nodes and identifying their co-indexed an- tecedents in phrase structure trees that do not contain this information. The pat- terns are minimal connected tree frag- ments containing an empty node and all other nodes co-indexed with it. This pa- per also proposes an evaluation proce- dure for empty node recovery procedures which is independent of most of the de- tails of phrase structure, which makes it possible to compare the performance of empty node recovery on parser output with the empty node annotations in a gold- standard corpus. Evaluating the algorithm on the output of Charniak’s parser (Char- niak, 2000) and the Penn treebank (Mar- cus et al., 1993) shows that the pattern- matching algorithm does surprisingly well on the most frequently occuring types of empty nodes given its simplicity. 1 Introduction One of the main motivations for research on pars- ing is that syntactic structure provides important in- formation for semantic interpretation; hence syntac- tic parsing is an important first step in a variety of ∗ I would like to thank my colleages in the Brown Labora- tory for Linguistic Information Processing (BLLIP) as well as Michael Collins for their advice. This research was supported by NSF awards DMS 0074276 and ITR IIS 0085940. useful tasks. Broad coverage syntactic parsers with good performance have recently become available (Charniak, 2000; Collins, 2000), but these typically produce as output a parse tree that only encodes lo- cal syntactic information, i.e., a tree that does not include any “empty nodes”. (Collins (1997) dis- cusses the recovery of one kind of empty node, viz., WH-traces). This paper describes a simple pattern- matching algorithm for post-processing the output of such parsers to add a wide variety of empty nodes to its parse trees. Empty nodes encode additional information about non-local dependencies between words and phrases which is important for the interpretation of construc- tions such as WH-questions, relative clauses, etc.1 For example, in the noun phrase the man Sam likes the fact the man is interpreted as the direct object of the verb likes is indicated in Penn treebank notation by empty nodes and coindexation as shown in Fig- ure 1 (see the next section for an explanation of why likes is tagged VBZ t rather than the standard VBZ). The broad-coverage statistical parsers just men- tioned produce a simpler tree structure for such a rel- ative clause that contains neither of the empty nodes just indicated. Rather, they produce trees of the kind shown in Figure 2. Unlike the tree depicted in Fig- ure 1, this type of tree does not explicitly represent the relationship between likes and the man. This paper presents an algorithm that takes as its input a tree without empty nodes of the kind shown 1There are other ways to represent this information that …

Content truncated to 500 words