Abstract
Comparing natural language parsers across different linguistic frameworks requires a common evaluation format. While converting Penn Treebank (PTB) phrase structures to Combinatory Categorial Grammar (CCG) is well-established, the inverse mapping is complex due to structural discrepancies and non-lexical "dummy" nodes in CCG. This paper introduces a two-stage machine learning approach using Maximum Entropy (MaxEnt) classifiers to automate this conversion. By replacing labor-intensive manual rules with statistical modeling, the system achieves a state-of-the-art F-measure of 95.71% on the CCGbank, facilitating more robust cross-framework parser comparisons.
The Challenge of Grammar Conversion
In Natural Language Processing, the Penn Treebank (PTB) and Combinatory Categorial Grammar (CCG) represent two dominant but structurally distinct formalisms. PTB relies on traditional phrase-structure trees (e.g., Noun Phrases and Verb Phrases), whereas CCG is a lexicalized formalism where words carry complex categories that dictate how they combine.
To evaluate a CCG-based parser against a PTB-based gold standard, CCG derivations must be converted back to PTB format. This task is difficult because CCG derivations often introduce intermediate nodes and structural binarizations that do not exist in the original PTB trees. Previous attempts relied on hundreds of manually crafted rules, which are time-consuming to maintain and often fail to capture the full complexity of the mapping.
A Two-Stage Machine Learning Approach
The authors propose a method that leverages Maximum Entropy (MaxEnt) classifiers to handle the structural mapping. The process begins with a preprocessing step where internal nodes with single children are collapsed, and their labels are concatenated (e.g., NP#N).
The core conversion consists of two specialized classifiers:
- Structural Mapper: This classifier examines each node in the CCG derivation and determines whether it corresponds to a specific PTB label or is a "dummy" node. Dummy nodes, often created during CCG binarization, are deleted, and their children are re-attached to the parent node to restore the original phrase structure.
- Unary Refiner: This second stage addresses "unary" structures—cases where a parent node has only one leaf child. The refiner determines if additional phrase-level nodes (like an
ADVPabove anRB) need to be inserted to match the PTB standard.
Structural Reversibility and Categories
The researchers identified that the vast majority of conversion cases (over 90%) follow a predictable pattern of "dummy" node insertion, labeled as Category A. The remaining cases, Category B, involve more complex structural transformations where the CCG derivation significantly departs from the PTB's hierarchical logic.
As shown in the figure above, Category A cases (top) can often be resolved by identifying the correct mapping for binarized nodes. Category B cases (bottom) present a greater challenge as they require more sophisticated structural "undoing" of the CCG derivation process.
Results and Key Insights
The MaxEnt approach was evaluated on Section 23 of the CCGbank. Using gold-standard Part-of-Speech (POS) tags, the system achieved an F-measure of 95.71%, surpassing previous rule-based methods by approximately 1.3 percentage points. Feature analysis highlighted that sibling-related features—the labels and words of adjacent nodes—were critical for accurate classification, as they provide the necessary grammatical context.
The success of this statistical approach suggests that the complexities of grammar conversion follow learnable patterns that are more effectively captured by machine learning than by manually crafted rule sets, which can exceed 800 rules and still fail to cover all edge cases.
Conclusion and Future Directions
While the current model provides a highly accurate conversion for the majority of phrase types, challenges remain. Performance on Quantifier Phrases (QP) was notably lower (44.8% F-measure), indicating a need for more specialized features. Future work will focus on improving the handling of Category B structures and refining the model's sensitivity to specific rare phrase types to further close the gap in cross-formalism evaluation.
Summary updated