Exploiting Diversity in Natural Language Processing: Combining Parsers

Exploiting Diversity in Natural Language Processing: Combining Parsers John C. Henderson and Eric Brill Department of Computer Science Johns Hopkins University Baltimore, MD 21218 {jhndrsn,brill}@cs.jhu.edu Abstract Three state-of-the-art statistical parsers are com- bined to produce more accurate parses, as well as new bounds on achievable Treebank parsing accu- racy. Two general approaches are presented and two combination techniques are described for each ap- proach. Both parametric and non-parametric mod- els are explored, i The resulting parsers surpass the best previously published performance results for the Penn Treebank. 1 Introduction The natural language processing community is in the strong position of having many available approaches to solving some of its most fundamental problems. The machine learning community has been in a simi- lar situation and has studied the combination of mul- tiple classifiers (Wolpert, 1992; Heath et al., 1996). Their theoretical I finding is simply stated: classifica- tion error rate decreases toward the noise rate ex- ponentially in the number of independent, accurate classifiers. The theory has also been validated em- pirically. Recently, combination techniques have been in- vestigated for part of speech tagging with positive results (van Halteren et al., 1998; Brill and Wu, 1998). In both cases the investigators were able to achieve significant improvements over the previous best tagging results. Similar advances have been made in machine translation (Frederking and Niren- burg, 1994), speech recognition (Fiscus, 1997) and named entity recognition (Borthwick et al., 1998). The corpus-based statistical parsing community has many fast and accurate automated parsing sys- tems, including systems produced by Collins (1997), Charniak (1997) and Ratnaparkhi (1997). These three parsers have given the best reported parsing results on the Penn Treebank Wall Street Journal corpus (Marcus et al., 1993). We used these three parsers to explore parser combination techniques. 2 Techniques for Combining Parsers 2.1 Parse Hybridization We are interested in combining the substructures of the input parses to produce a better parse. We call this approach parse hybridization. The sub- structures that are unanimously hypothesized by the parsers should be preserved after combination, and the combination technique should not foolishly cre- ate substructures for which there is no supporting evidence. These two principles guide experimenta- tion in this framework, and together with the evalu- ation measures help us decide which specific type of substructure to combine. The precision and recall measures (described in more detail in Section 3) used in evaluating Tree- bank parsing treat each constituent as a separate entity, a minimal unit of correctness. Since our goal is to perform well under these measures we will simi- larly treat constituents as the minimal substructures for combination. 2.1.1 Constituent Voting One hybridization strategy is to let the parsers vote on constituents' membership in the hypothesized set. If enough parsers suggest that a particular con- stituent belongs in the parse, we include it. We call this technique constituent voting. We include a con- stituent in our hypothesized parse if it appears in the output of a majority of the parsers. In our particular case …

Content truncated to 500 words