A Crossing-Sensitive Third-Order Factorization for Dependency Parsing
Venue
Transactions of the Association for Computational Linguistics, vol. 2 (2014), pp. 41-54
Publication Year
2014
Authors
BibTeX
Abstract
Parsers that parametrize over wider scopes are generally more accurate than
edge-factored models. For graph-based non-projective parsers, wider factorizations
have so far implied large increases in the computational complexity of the parsing
problem. This paper introduces a “crossing-sensitive” generalization of a
third-order factorization that trades off complexity in the model structure (i.e.,
scoring with features over multiple edges) with complexity in the output structure
(i.e., producing crossing edges). Under this model, the optimal 1-Endpoint-Crossing
tree can be found in O(n^4) time, matching the asymptotic run-time of both the
third-order projective parser and the edge-factored 1-Endpoint-Crossing parser. The
crossing-sensitive third-order parser is significantly more accurate than the
third-order projective parser under many experimental settings and significantly
less accurate on none.
