Paper: Generalized Higher-Order Dependency Parsing with Cube Pruning

ACL ID D12-1030
Title Generalized Higher-Order Dependency Parsing with Cube Pruning
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2012

State-of-the-art graph-based parsers use fea- tures over higher-order dependencies that rely on decoding algorithms that are slow and difficult to generalize. On the other hand, transition-based dependency parsers can eas- ily utilize such features without increasing the linear complexity of the shift-reduce system beyond a constant. In this paper, we attempt to address this imbalance for graph-based pars- ing by generalizing the Eisner (1996) algo- rithm to handle arbitrary features over higher- order dependencies. The generalization is at the cost of asymptotic efficiency. To account for this, cube pruning for decoding is utilized (Chiang, 2007). For the first time, label tuple and structural features such as valencies can be scored efficiently with third-order features in a graph-based ...