TL;DR
This paper introduces a novel boosting-based method for efficiently selecting the best feature templates for syntactic parsing, particularly for morphologically rich languages. By avoiding manual constraints and leveraging a more efficient selection process, their approach achieves state-of-the-art parsing performance with significantly reduced selection time and more compact models.
What Problem Does This Paper Address?
Syntactic parsing, the process of analyzing the grammatical structure of sentences, relies heavily on selecting the right features to represent linguistic information. For morphologically rich languages (like French, which has complex word forms and inflections), the number of potential features explodes, creating a massive search space for model selection. Traditional methods for finding optimal feature sets are computationally intensive, often taking weeks to train and requiring manual, heuristic constraints that might limit the search. This paper tackles the challenge of efficiently exploring this high-dimensional feature space to find compact, high-performing parsing models without relying on such restrictive manual interventions.
Methods
The core of this paper is a novel application of multi-class boosting (specifically, the SAMME algorithm) for template selection in transition-based constituency parsing. Instead of selecting individual features, they focus on selecting feature templates, which are abstract representations of feature functions.
Here's a breakdown of their approach:
- Transition-Based Parser: They use an existing, efficient transition-based lexicalized constituency parser.
- Boosting for Selection: They adapt the SAMME algorithm, which iteratively selects "weak learners" (in this case, weak parsers trained on small sets of templates) and combines them into a strong learner. This process is used to select the most informative templates.
- Local Training: To manage computational cost, weak parsers are trained locally during the selection phase, rather than globally optimizing the entire model at each step.
- Template Grouping: Instead of treating each template individually, they group templates that share similar conditions. This creates "weak parsers" that are more robust and helps accelerate selection.
- Pre-ranking: To guide the boosting process and limit the pool of weak parsers considered at each iteration, they introduce a pre-ranking step. This involves globally training potential weak parsers and ranking them by accuracy.
- Stopping Criterion: They propose a practical stopping criterion based on a user-defined maximum model size, ensuring that the selected model doesn't become excessively large and slow.
What's new is the adaptation of boosting for template selection in parsing, the specific strategies for template grouping and pre-ranking, and the focus on efficiency without manual constraints.
Datasets
The experiments were conducted using the French TreeBank (FTB). They utilized different variants of the FTB for various purposes:
- FTB-20-train, FTB-50-train, FTB-all-train: Used for pre-ranking weak parsers. These variants differ in the maximum sentence length they contain, allowing them to study the effect of pre-ranking data size on selection time and performance.
- FTB-all-dev: Used for tuning and comparing parameter values during selection.
- FTB-all-test: Used for final evaluation of the selected models.
They also mention using automatically predicted morphological tags from MarMoT, which is relevant for handling morphologically rich data.
Key Insights and Ideas
- Boosting as an Efficient Selector: The core insight is that boosting, typically used for classification, can be effectively repurposed for model selection in parsing. It offers a way to explore a large feature space efficiently by iteratively adding informative components.
- Local Training is Sufficient for Selection: The paper demonstrates that training weak parsers locally during selection provides a good approximation for globally trained models, significantly reducing computational burden without sacrificing the quality of the selected template set.
- Template Grouping Improves Robustness: Grouping templates leads to stronger weak parsers and more stable boosted accuracy, preventing premature termination of the selection process and resulting in better final models compared to individual template selection.
- Pre-ranking Guides the Search: While pre-ranking is time-consuming, it effectively guides the boosting process, allowing for faster selection and better performance, especially when using smaller datasets for pre-ranking.
- Compactness and Performance are Achievable: The method successfully produces models that are both compact (fewer templates) and achieve state-of-the-art or near state-of-the-art performance, outperforming manually defined models.
Key Results
- Efficiency: The boosting method significantly reduces selection time. For example, a boosted model with pre-ranking on FTB-20-train and a pool size of 100 took approximately 66 hours for selection (including pre-ranking), compared to 1,163 hours for a naive forward wrapper (FWRAP).
- Performance: The selected models achieve competitive F-scores. The best boosted model (FTB-20-train pre-ranking, k=100) achieved an F-score of 80.34 (test, NoP) for a 36-template model and 80.98 (test, NoP) for a 120-template model. These scores are comparable to or better than existing state-of-the-art parsers.
- Compactness: The boosted models are significantly more compact. For instance, a 120-template boosted model achieved an F-score of 80.98, outperforming the manually chosen model (Crabbé, 2014) which had 68 templates and an F-score of 81.43.
- Robustness: The approach shows robustness across different pre-ranking data sizes and pool sizes.
Limitations and Future Work
- Pre-ranking Time: While boosting is faster than naive wrappers, the pre-ranking step itself can still be time-consuming, especially when using large datasets.
- Large Models: For very large models (e.g., 120 templates), the advantage of boosting diminishes, with "pre-rank only" methods showing comparable performance.
- Future Work:
- Extend the approach to other languages, particularly morphologically rich ones like Arabic, Hungarian, or Korean.
- Incorporate a wider range of feature templates.
- Investigate combining the boosting approach with constraining heuristics, though this might require language-specific rules.
Summary updated