Premium
Undirected Dependency Parsing
Author(s) -
GómezRodríguez Carlos,
FernándezGonzález Daniel,
Bilbao Víctor Manuel Darriba
Publication year - 2015
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/coin.12027
Subject(s) - computer science , parsing , parser combinator , treebank , dependency (uml) , top down parsing , lr parser , artificial intelligence , dependency grammar , construct (python library) , parsing expression grammar , syntax , natural language processing , undirected graph , bottom up parsing , theoretical computer science , algorithm , programming language , l attributed grammar , graph , context free grammar
Dependency parsers, which are widely used in natural language processing tasks, employ a representation of syntax in which the structure of sentences is expressed in the form of directed links (dependencies) between their words. In this article, we introduce a new approach to transition‐based dependency parsing in which the parsing algorithm does not directly construct dependencies, but rather undirected links, which are then assigned a direction in a postprocessing step. We show that this alleviates error propagation, because undirected parsers do not need to observe the single‐head constraint, resulting in better accuracy. Undirected parsers can be obtained by transforming existing directed transition‐based parsers as long as they satisfy certain conditions. We apply this approach to obtain undirected variants of three different parsers (the Planar, 2‐Planar, and Covington algorithms) and perform experiments on several data sets from the CoNLL‐X shared tasks and on the Wall Street Journal portion of the Penn Treebank, showing that our approach is successful in reducing error propagation and produces improvements in parsing accuracy in most of the cases and achieving results competitive with state‐of‐the‐art transition‐based parsers.