1. Graph-Based Dependency Parsing Using Dynamic Features in Korean.
- Author
-
LEE, YONG-HUN, JIN, MEIXUN, and LEE, JONG-HYEOK
- Subjects
PARSING (Grammar) ,COMPUTATIONAL linguistics ,KOREAN language ,ALGORITHMS - Abstract
In this paper, we propose a graph-based dependency parsing model using dynamic features. The dynamic features, which are derived from the partial tree during bottom-up chart parsing, play an important role in finding the correct heads. Based on the beneficial aspects of the head-final property of Korean, we suggest a variant of the CYK parsing algorithm with an O(n
3 ) complexity which has the ability to search for the maximum spanning tree (MST) from all projective trees. Compared to Eisner's algorithm, this algorithm is time-efficient in parsing all other head-final languages. We also explain why the graph-based approaches are seldom attempted in parsing morphologically rich languages (MRLs) and suggest a morpheme-level dependency representation as a solution. Finally, we evaluate the proposed method on the KAIST corpus using two discriminative online learning methods (the averaged perceptron algorithm and passive-aggressive algorithm) and show that the trained parser achieves the best reported parsing accuracy. [ABSTRACT FROM AUTHOR]- Published
- 2011
- Full Text
- View/download PDF