NP Bracketing by Maximum Entropy Tagging and SVM Reranking

Hal Daumé Iii, Daniel MarcuEMNLP 2004 · OpenReview

Introduction

Noun Phrase (NP) bracketing is a fundamental task in Natural Language Processing, serving as a middle ground between simple NP chunking and full syntactic parsing. While chunking identifies non-recursive "base" noun phrases, full parsing identifies all sentence structures but at a high computational cost. NP bracketing aims to identify all nested noun phrases (e.g., [[Confidence] in [the pound]]) without the overhead of a complete parse.

This paper introduces a high-performance, two-stage approach to NP bracketing that combines the speed of local tagging with the accuracy of global reranking. By using a Maximum Entropy tagger to generate hypotheses and a Support Vector Machine (SVM) to select the optimal candidate, the authors achieved a then-state-of-the-art F-score of 86.1 while maintaining linear scaling relative to sentence length.

The Hybrid Architecture

The proposed system utilizes a hybrid architecture designed to balance local efficiency with global structural awareness.

1. Maximum Entropy Tagger

The first stage treats bracketing as a sequence labeling problem using five "underspecified" tags: open, close, in, out, and sing (singleton). These tags do not explicitly track nesting depth. Instead, the authors employ a Viterbi-like dynamic programming decoder that enforces well-formedness constraints, such as ensuring every close tag follows an open tag. This approach allows the model to remain agnostic to depth during tagging while ensuring the final output is a valid tree structure.

2. SVM Reranking

Local taggers often make categorical mistakes because they only consider a small window of context. To mitigate this, the tagger produces an $n$-best list of the most likely bracketings. These hypotheses are then passed to an SVM-based reranker. The reranker utilizes rich, global features that are too computationally expensive for the initial tagger, such as Context-Free Grammar (CFG) rules, lexical heads, and child counts.

Evaluation and Results

The system was evaluated using the standard CoNLL-99 shared task dataset, derived from the Wall Street Journal (WSJ) corpus of the Penn Treebank.

Accuracy and Benchmarking

The best version of the system (RR2) achieved an F-score of 86.1, significantly surpassing the previous best-reported result of 83.8. Even without the reranking step, the base MaxEnt tagger (TAG) achieved an 83.4 F-score, which was nearly competitive with the best existing systems on its own.

Performance comparison of NP bracketing systems on the CoNLL-99 dataset.

Computational Efficiency

A major contribution of this work is the system's efficiency. While full statistical parsers (such as those by Collins or Charniak) exhibit processing times that explode as sentences get longer, this system scales linearly.

Parsing time vs. sentence length, showing the linear scaling of the proposed bracketer compared to full parsers.

As shown in the figure above, the time required per sentence remains nearly flat for the bracketer as sentence length increases, whereas the processing time for full parsers increases sharply. This makes the system a viable "middle ground" for real-time applications like translation or co-reference resolution.

Conclusion

The success of this model demonstrates that local decisions are often "mostly right," and a global model can effectively nudge the system toward the most linguistically plausible structure. By specializing in NP structures rather than attempting to solve the entire grammar at once, the system provides a high-performance, scalable solution for identifying complex noun phrases in large-scale NLP applications.

Summary updated

BibTeX
@inproceedings{iii2004np,
  author = {Hal Daumé III and Daniel Marcu},
  title = {{NP Bracketing by Maximum Entropy Tagging and SVM Reranking}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2004},
  url = {https://openreview.net/forum?id=r1NDVfzO-S},
}
Figure