NP Bracketing by Maximum Entropy Tagging and SVM Reranking

NP Bracketing by Maximum Entropy Tagging and SVM Reranking Hal Daum´e III and Daniel Marcu University of Southern California Information Sciences Institute 4676 Admiralty Way, Suite 1001 Marina del Rey, CA 90292 {hdaume,marcu}@isi.edu Abstract We perform Noun Phrase Bracketing by using a lo- cal, maximum entropy-based tagging model, which produces bracketing hypotheses. These hypothe- ses are subsequently fed into a reranking frame- work based on support vector machines. We solve the problem of hierarchical structure in our tag- ging model by modeling underspecified tags, which are fully determined only at decoding time. The tagging model performs comparably to competing approaches and the subsequent reranking increases our system’s performance from an f-score of 81.7 to 86.1, surpassing the best reported results to date of 83.8. 1 Introduction and Prior Work Noun Phrase Bracketing (NP Bracketing) is the task of identifying any and all noun phrases in a sen- tence. It is a strictly more difficult problem than NP Chunking (Ramshaw and Marcus, 1995), in which only non-recursive (or “base”) noun phrases are identified. It is simultaneously strictly more sim- ple than either full parsing (Collins, 2003; Charniak, 2000) or supertagging (Bangalore and Joshi, 1999). NP Bracketing is both a useful first step toward full parsing and also a meaningful task in its own right; for instance as an initial step toward co-reference resolution and noun-phrase translation. While existing NP Bracketers (including the one described in this paper) tend to achieve worse over- all F-measures than a full statistical parser (eg., (Collins, 2003; Charniak, 2000)), they can be sig- nificantly more computationally efficient. Statisti- cal parsers tend to scale exponentially in sentence length, unless a narrow beam is employed, which leads to globally poorer parses. In contrast, the bracketer described in this paper scales linearly in [[Confidence] in [the pound]] is widely expected to take [another sharp dive] if [[[trade figures] for [September]] , due for [release] [tomorrow] ,] . . . Figure 1: Sample sentence with NPs bracketed. the length of the sentence to find the globally op- timal solution. This trade-off is depicted graphi- cally in Figure 2. This figure shows the amount of time (excluding any startup overhead) spent pars- ing or bracketing using this system (the two lowest lines) versus the parsers of Collins (2003) and Char- niak (2000) run with default settings. NP Bracketing was the shared task of the Com- putational Natural Language Learning workshop in 1999 (CoNLL-99). In this competition, NP Brack- eting systems were trained on sections 15-18 of the Wall Street Journal corpus, while section 20 was used for testing. The bracketing information was extracted directly from the Penn Treebank, essen- tially disregarding all non-NP brackets. An example bracketed sentence is in Figure 1. There have been several successful approaches reported in the literature to solve this task. Tjong Kim Sang (1999) first used repeated chunking to at- tain an f-score of 82.98 during the CoNLL compe- tition and subsequently (Sang, 2002) an f-score of 83.79 using a combination of two different systems. …

Content truncated to 500 words