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.
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.
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