Fourth-Order Dependency Parsing
Xuezhe Ma, Hai Zhao · International Conference on Computational Linguistics · 2012
We present and implement a fourth-order projective dependency parsing algorithm that effectively utilizes both “grand-sibling” style and “tri-sibling” style interactions of third-order and “grand-tri-sibling” style interactions of forth-order factored parts for performance enhancement. This algorithm requires O(n5) time and O(n4) space. We implement and evaluate the parser on two languages—English and Chinese, both achieving state-of-the-art accuracy. This results show that a higher-order (≥4) dependency parser gives performance improvement over all previous lower-order parsers.