Recovery of Empty Nodes in Parse Structures

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 620–629, Prague, June 2007. c⃝2007 Association for Computational Linguistics Recovery of Empty Nodes in Parse Structures Denis Filimonov1 1University of Maryland College Park, MD 20742 den@cs.umd.edu Mary P. Harper1,2 2Purdue University West Lafayette, IN 47907 mharper@casl.umd.edu Abstract In this paper, we describe a new algorithm for recovering WH-trace empty nodes. Our approach combines a set of hand-written patterns together with a probabilistic model. Because the patterns heavily utilize regu- lar expressions, the pertinent tree structures are covered using a limited number of pat- terns. The probabilistic model is essen- tially a probabilistic context-free grammar (PCFG) approach with the patterns acting as the terminals in production rules. We eval- uate the algorithm’s performance on gold trees and parser output using three differ- ent metrics. Our method compares favorably with state-of-the-art algorithms that recover WH-traces. 1 Introduction In this paper, we describe a new algorithm for re- covering WH-trace empty nodes in gold parse trees in the Penn Treebank and, more importantly, in automatically generated parses. This problem has only been investigated by a handful of researchers and yet it is important for a variety of applications, e.g., mapping parse trees to logical representations and structured representations for language mod- eling. For example, SuperARV language models (LMs) (Wang and Harper, 2002; Wang et al., 2003), which tightly integrate lexical features and syntactic constraints, have been found to significantly reduce word error in English speech recognition tasks. In order to generate SuperARV LM training, a state-of- the-art parser is used to parse training material and then a rule-based transformer converts the parses to the SuperARV representation. The transformer is quite accurate when operating on treebank parses; however, trees produced by the parser lack one im- portant type of information – gaps, particularly WH- traces, which are important for more accurate ex- traction of the SuperARVs. Approaches applied to the problem of empty node recovery fall into three categories. Dienes and Dubey (2003) recover empty nodes as a pre- processing step and pass strings with gaps to their parser. Their performance was comparable to (Johnson, 2002); however, they did not evaluate the impact of the gaps on parser performance. Collins (1999) directly incorporated wh-traces into his Model 3 parser, but he did not evaluate gap in- sertion accuracy directly. Most of the research be- longs to the third category, i.e., post-processing of parser output. Johnson (2002) used corpus-induced patterns to insert gaps into both gold standard trees and parser output. Campbell (2004) developed a set of linguistically motivated hand-written rules for gap insertion. Machine learning methods were em- ployed by (Higgins, 2003; Levy and Manning, 2004; Gabbard et al., 2006). In this paper, we develop a probabilistic model that uses a set of patterns and tree matching to guide the insertion of WH-traces. We only insert traces of non-null WH-phrases, as they are most relevant for our goals. Our effort differs from the previous ap- …

Content truncated to 500 words