---
abstract: 'Conventional graph-based dependency parsers guarantee a tree structure both during training and inference. Instead, we formalize dependency parsing as the problem of independently selecting the head of each word in a sentence. Our model which we call <span style="font-variant:small-caps;">DeNSe</span> (as shorthand for [**De**]{}pendency [**N**]{}eural [ **Se**]{}lection) produces a distribution over possible heads for each word using features obtained from a bidirectional recurrent neural network. Without enforcing structural constraints during training, <span style="font-variant:small-caps;">DeNSe</span> generates (at inference time) trees for the overwhelming majority of sentences, while non-tree outputs can be adjusted with a maximum spanning tree algorithm. We evaluate <span style="font-variant:small-caps;">DeNSe</span> on four languages (English, Chinese, Czech, and German) with varying degrees of non-projectivity. Despite the simplicity of the approach, our parsers are on par with the state of the art.[^1]'
author:
- 'Xingxing Zhang, Jianpeng Cheng'
- |
    Mirella Lapata\
    Institute for Language, Cognition and Computation\
    School of Informatics, University of Edinburgh\
    10 Crichton Street, Edinburgh EH8 9AB\
    [{x.zhang,jianpeng.cheng}@ed.ac.uk, mlap@inf.ed.ac.uk]{}
bibliography:
- 'eacl2017.bib'
title: Dependency Parsing as Head Selection
---

Introduction
============

Dependency parsing plays an important role in many natural language applications, such as relation extraction [@fundel2007relex], machine translation [@carreras2009non], language modeling [@chelba1997structure; @zhang-etal:2016] and ontology construction [@snow2004learning]. Dependency parsers represent syntactic information as a set of head-dependent relational arcs, typically constrained to form a tree. Practically all models proposed for dependency parsing in recent years can be described as graph-based [@mcdonald2005online] or transition-based [@yamada2003statistical; @nivre2006labeled]. Graph-based dependency parsers are typically arc-factored, where the score of a tree is defined as the sum of the scores of all its arcs. An arc is scored with a set of local features and a linear model, the parameters of which can be effectively learned with online algorithms [@crammer2001algorithmic; @crammer2003ultraconservative; @freund1999large; @collins2002discriminative]. In order to efficiently find the best scoring tree during training *and* decoding, various maximization algorithms have been developed [@eisner1996three; @eisner2000bilexical; @mcdonald2005non]. In general, graph-based methods are optimized globally, using features of single arcs in order to make the learning and inference tractable. Transition-based algorithms factorize a tree into a set of parsing actions. At each transition state, the parser scores a candidate action conditioned on the state of the transition system and the parsing history, and greedily selects the highest-scoring action to execute. This score is typically obtained with a classifier based on non-local features defined over a rich history of parsing decisions [@yamada2003statistical; @zhang2011transition].

Regardless of the algorithm used, most well-known dependency parsers, such as the [@mcdonald2005non] and the MaltPaser [@nivre2006maltparser], rely on extensive feature engineering. Feature templates are typically manually designed and aim at capturing head-dependent relationships which are notoriously sparse and difficult to estimate. More recently, a few approaches [@chen2014fast; @pei2015effective; @DBLP:journals/corr/KiperwasserG16a] apply neural networks for learning dense feature representations. The learned features are subsequently used in a conventional graph- or transition-based parser, or better designed variants [@dyer2015transition].

In this work, we propose a simple neural network-based model which learns to select the head for each word in a sentence without enforcing tree structured output. Our model which we call [DeNSe]{} (as shorthand for [**De**]{}pendency [**N**]{}eural [**Se**]{}lection) employs bidirectional recurrent neural networks to learn feature representations for words in a sentence. These features are subsequently used to predict the head of each word. Although there is nothing inherent in the model to enforce tree-structured output, when tested on an English dataset, it is able to generate trees for 95% of the sentences, 87% of which are projective. The remaining non-tree (or non-projective) outputs are post-processed with the Chu-Liu-Edmond (or Eisner) algorithm. [ DeNSe]{} uses the head selection procedure to estimate arc weights during training. During testing, it essentially reduces to a standard graph-based parser when it fails to produce tree (or projective) output.

We evaluate our model on benchmark dependency parsing corpora, representing four languages (English, Chinese, Czech, and German) with varying degrees of non-projectivity. Despite the simplicity of our approach, experiments show that the resulting parsers are on par with the state of the art.

Related Work
============

#### Graph-based Parsing

Graph-based dependency parsers employ a model for scoring possible dependency graphs for a given sentence. The graphs are typically factored into their component arcs and the score of a tree is defined as the sum of its arcs. This factorization enables tractable search for the highest scoring graph structure which is commonly formulated as the search for the maximum spanning tree (MST). The Chu-Liu-Edmonds algorithm [@chu1965shortest; @edmonds1967optimum; @mcdonald2005non] is often used to extract the MST in the case of non-projective trees, and the Eisner algorithm [@eisner1996three; @eisner2000bilexical] in the case of projective trees. During training, weight parameters of the scoring function can be learned with margin-based algorithms [@crammer2001algorithmic; @crammer2003ultraconservative] or the structured perceptron [@freund1999large; @collins2002discriminative]. Beyond basic first-order models, the literature offers a few examples of higher-order models involving sibling and grand parent relations [@carreras2007experiments; @koo2010dual; @zhang2012generalized]. Although more expressive, such models render both training and inference more challenging.

#### Transition-based Parsing

As the term implies, transition-based parsers conceptualize the process of transforming a sentence into a dependency tree as a sequence of transitions. A transition system typically includes a stack for storing partially processed tokens, a buffer containing the remaining input, and a set of arcs containing all dependencies between tokens that have been added so far [@nivre2003efficient; @nivre2006labeled]. A dependency tree is constructed by manipulating the stack and buffer, and appending arcs with predetermined operations. Most popular parsers employ an *arc-standard* [@yamada2003statistical; @nivre2004incrementality] or *arc-eager* transition system [@nivre2008algorithms]. Extensions of the latter include the use of non-local training methods to avoid greedy error propagation [@zhang2008tale; @huang2010dynamic; @zhang2011transition; @goldberg2012dynamic].

In an *arc-standard* system [@yamada2003statistical; @nivre2004incrementality], the transitions include a <span style="font-variant:small-caps;">Shift</span> operation which removes the first word in the buffer and pushes it onto the stack; a <span style="font-variant:small-caps;">Left-Arc</span> operation adds an arc from the word in the beginning of the buffer to the word on top of the stack; and a <span style="font-variant:small-caps;">Right-Arc</span> operation adds an arc from the word on top of the stack to the word in the beginning of the buffer. During parsing, the transition from one configuration to the next is greedily scored with a linear classifier whose features are defined according to the stack and buffer. The above arc-standard system builds a projective dependency tree bottom up, with the assumption that an arc is only added when the dependent node has already found all its dependents. Extensions include the *arc-eager* system [@nivre2008algorithms] which always adds an arc at the earliest possible stage, a more elaborate (reduce) action space to handle non-projective parsing [@attardi2006experiments], and the use of non-local training methods to avoid greedy error propagation [@zhang2008tale; @huang2010dynamic; @zhang2011transition; @goldberg2012dynamic].

#### Neural Network-based Features

Neural network representations have a long history in syntactic parsing [@Mayberry:Miikkulainen:1999; @henderson:2004:ACL; @titov-henderson:2007:ACLMain]. Recent work uses neural networks in lieu of the linear classifiers typically employed in conventional transition- or graph-based dependency parsers. For example, use a feed forward neural network to learn features for a transition-based parser, whereas do the same for a graph-based parser. apply tensor decomposition to obtain word embeddings in their syntactic roles, which they subsequently use in a graph-based parser. redesign components of a transition-based system where the buffer, stack, and action sequences are modeled separately with stack long short-term memory networks. The hidden states of these LSTMs are concatenated and used as features to a final transition classifier. use bidirectional LSTMs to extract features for a transition- and graph-based parser, whereas build a greedy arc-standard parser using similar features.

In our work, we formalize dependency parsing as the task of finding for each word in a sentence its most probable head. Both head selection and the features it is based on are learned using neural networks. The idea of modeling child-parent relations independently dates back to who use an edge-factored model to generate $k$-best parse trees which are subsequently reranked using a model based on rich global features. Later show that a head selection variant of their loopy belief propagation parser performs worse than a model which incorporates tree structure constraints. Our parser is conceptually simpler: we rely on head selection to do most of the work and decode the best tree *directly* without using a reranker. In common with recent neural network-based dependency parsers, we aim to alleviate the need for hand-crafting feature combinations. Beyond feature learning, we further show that it is possible to simplify the training of a graph-based dependency parser in the context of bidirectional recurrent neural networks.

Dependency Parsing as Head Selection
====================================

In this section we present our parsing model, [DeNSe]{}, which tries to predict the head of each word in a sentence. Specifically, the model takes as input a sentence of length $N$ and outputs $N$ $\langle$head, dependent$\rangle$ arcs. We describe the model focusing on unlabeled dependencies and then discuss how it can be straightforwardly extended to the labeled setting. We begin by explaining how words are represented in our model and then give details on how [DeNSe]{} makes predictions based on these learned representations. Since there is no guarantee that the outputs of [ DeNSe]{} are trees (although they mostly are), we also discuss how to extend [DeNSe]{} in order to enforce projective and non-projective tree outputs. Throughout this paper, lowercase boldface letters denote vectors (e.g., $\mathbf{v}$ or $\mathbf{v}_i$), uppercase boldface letters denote matrices (e.g., $\mathbf{M}$ or $\mathbf{M}_b$), and lowercase letters denote scalars (e.g., $w$ or $w_i$).

Word Representation {#sec:wordrepr}
-------------------

Let $S=(w_0, w_1, \dots, w_N)$ denote a sentence of length $N$; following common practice in the dependency parsing literature [@Kubler:etal:2009], we add an artificial [root]{} token represented by $w_0$. Analogously, let denote the representation of sentence $S$, with $\mathbf{a}_i$ representing word $w_i \quad (0 \le
i \le N)$. Besides encoding information about each $w_i$ in isolation (e.g., its lexical meaning or POS tag), $\mathbf{a}_i$ must also encode $w_i$’s positional information within the sentence. Such information has been shown to be important in dependency parsing [@mcdonald2005online]. For example, in the following sentence:

[root]{} & a & dog & is & chasing & a & cat\

the head of the first *a* is *dog*, whereas the head of the second *a* is *cat*. Without considering positional information, a model cannot easily decide which *a* (nearer or farther) to assign to *dog*.

Long short-term memory networks (Hochreiter and Schmidhuber, 1997; LSTMs), a type of recurrent neural network with a more complex computational unit, have proven effective at capturing long-term dependencies. In our case LSTMs allow to represent each word on its own and within a sequence leveraging long-range contextual information. As shown in Figure \[fig:dense\], we first use a forward LSTM ($\text{LSTM}^F$) to read the sentence from left to right and then a backward LSTM ($\text{LSTM}^B$) to read the sentence from right to left, so that the entire sentence serves as context for each word:[^2] $$\label{eq:forward}
    \mathbf{h}_i^F,  \mathbf{c}_i^F = \text{LSTM}^F(\mathbf{x}_i, \mathbf{h}_{i-1}^F, \mathbf{c}_{i-1}^F)$$ $$\label{eq:backward}
    \mathbf{h}_i^B,  \mathbf{c}_i^B = \text{LSTM}^B(\mathbf{x}_i, \mathbf{h}_{i+1}^B, \mathbf{c}_{i+1}^B)$$ where $\mathbf{x}_i$ is the feature vector of word $w_i$, $\mathbf{h}_i^F \in \mathbb{R}^{d}$ and $\mathbf{c}_i^F \in \mathbb{R}^{d}$ are the hidden states and memory cells for the $i$th word $w_i$ in $ \text{LSTM}^F$ and $d$ is the hidden unit size. $\mathbf{h}_i^F$ is also the representation for $w_{0:i}$ ($w_i$ and its left neighboring words) and $\mathbf{c}_i^F$ is an internal state maintained by $ \text{LSTM}^F$. $\mathbf{h}_i^B \in \mathbb{R}^d$ and $\mathbf{c}_i^B \in \mathbb{R}^d$ are the hidden states and memory cells for the backward $\text{LSTM}^B$. Each token $w_i$ is represented by $\mathbf{x}_i$, the concatenation of two vectors corresponding to $w_i$’s lexical and POS tag embeddings: $$\label{eq:fearep}
    \mathbf{x}_i = [ \mathbf{W}_e \cdot e(w_i); \mathbf{W}_t \cdot e(t_i) ]$$ where $e(w_i)$ and $e(t_i)$ are one-hot vector representations of token $w_i$ and its POS tag $t_i$; $\mathbf{W}_e \in \mathbb{R}^{s \times |V|}$ and $\mathbf{W}_t \in \mathbb{R}^{q \times |T|}$ are the word and POS tag embedding matrices, where $|V|$ is the vocabulary size, $s$ is the word embedding size, $|T|$ is the POS tag set size, and $q$ the tag embedding size. The hidden states of the forward and backward LSTMs are concatenated to obtain$~\mathbf{a}_i$, the final representation of $w_i$: $$\label{eq:ann}
    \mathbf{a}_i = [ \mathbf{h}_i^F; \mathbf{h}_i^B ] \quad i \in [0, N]$$

Note that bidirectional LSTMs are one of many possible ways of representing word $w_i$. Alternative representations include embeddings obtained from feed-forward neural networks [@chen2014fast; @pei2015effective], character-based embeddings [@ballesteros-dyer-smith:2015:EMNLP], and more conventional features such as those introduced in .

Head Selection
--------------

We now move on to discuss our formalization of dependency parsing as head selection. We begin with unlabeled dependencies and then explain how the model can be extended to predict labeled ones.

In a dependency tree, a head can have multiple dependents, whereas a dependent can have only one head. Based on this fact, dependency parsing can be formalized as follows. Given a sentence $S=(w_0, w_1, \dots, w_N)$, we aim to find for each word $w_i
\in \{w_1, w_2, \dots, w_n\}$ the most probable head $w_j \in \{w_0,
w_1, \dots, w_N\}$. For example, in Figure \[fig:dense\], to find the head for the token *love*, we calculate probabilities $P_{head}(\text{\sc root}|\text{love}, S)$, $P_{head}(\text{kids}|\text{love}, S)$, and $P_{head}(\text{candy}|\text{love}, S)$, and select the highest. More formally, we estimate the probability of token $w_j$ being the head of token $w_i$ in sentence $S$ as: $$\label{eq:softmax}
    P_{head}(w_j|w_i, S) = \frac{\exp(g(\mathbf{a}_j, \mathbf{a}_i))}{ \sum_{k=0}^{N} \exp( g(\mathbf{a}_k, \mathbf{a}_i) ) }$$ where $\mathbf{a}_i$ and $\mathbf{a}_j$ are vector-based representations of $w_i$ and $w_j$, respectively (described in Section \[sec:wordrepr\]); $g(\mathbf{a}_j, \mathbf{a}_i)$ is a neural network with a single hidden layer that computes the associative score between representations $\mathbf{a}_i$ and $\mathbf{a}_j$: $$\label{eq:tanh}
    g(\mathbf{a}_j, \mathbf{a}_i) = \mathbf{v}_a^\top \cdot \tanh( \mathbf{U}_a \cdot \mathbf{a}_j + \mathbf{W}_a \cdot \mathbf{a}_i )$$ where $\mathbf{v}_a \in \mathbb{R}^{2d}$, $\mathbf{U}_a \in
\mathbb{R}^{2d \times 2d}$, and $\mathbf{W}_a \in \mathbb{R}^{2d \times
    2d}$ are weight matrices of $g$. Note that the candidate head $w_j$ can be the [root]{}, while the dependent $w_i$ cannot. Equations  and  compute the probability of adding an arc between two words, in a fashion similar to the neural attention mechanism in sequence-to-sequence models [@bahdanau:2014]. We train our model by minimizing the negative log likelihood of the gold standard $\langle$head, dependent$\rangle$ arcs in all training sentences: $$\hspace*{-2ex}J(\theta) = - \frac{ 1 }{  |\mathcal{T}| } \sum_{S \in \mathcal{T}} \sum_{i=1}^{N_S} \log P_{head}(h(w_i) | w_i, S )$$ where $\mathcal{T}$ is the training set, $h(w_i)$ is $w_i$’s gold standard head[^3] within sentence $S$, and $N_S$ the number of words in $S$ (excluding [ root]{}). During inference, for each word $w_i~(i \in [1, N_S])$ in $S$, we greedily choose the most likely head $w_j~(j \in [0, N_S])$: $$\label{eq:inference}
    w_j = \operatorname*{arg\,max}_{w_j: j \in [0, N_S]} P_{head}(w_j|w_i, S)$$ Note that the prediction for each word $w_i$ is made independently of the other words in the sentence.

Given our greedy inference method, there is no guarantee that predicted $\langle$head, dependent$\rangle$ arcs form a tree (maybe there are cycles). However, we empirically observed that most outputs during inference are indeed trees. For instance, on an English dataset, 95% of the arcs predicted on the development set are trees, and 87% of them are projective, whereas on a Chinese dataset, 87% of the arcs form trees, 73% of which are projective. This indicates that although the model does not explicitly model tree structure during training, it is able to figure out from the data (which consists of trees) that it should predict them.

So far we have focused on unlabeled dependencies, however it is relatively straightforward to extend <span style="font-variant:small-caps;">DeNSe</span> to produce labeled dependencies. We basically train an additional classifier to predict labels for the arcs which have been already identified. The classifier takes as input features $[\mathbf{a}_i; \mathbf{a}_j; \mathbf{x}_i; \mathbf{x}_j]$ representing properties of the arc $\langle w_j, w_i \rangle$. These consist of $\mathbf{a}_i$ and $\mathbf{a}_j$, the LSTM-based representations for $w_i$ and $w_j$ (see Equation ), and their word and part-of-speech embeddings, $\mathbf{x}_i$ and $\mathbf{x}_j$ (see Equation ). Specifically, we use a trained [DeNSe]{} model to go through the training corpus and generate features and corresponding dependency labels as training data. We employ a two-layer rectifier network [@glorot:2011] for the classification task.

Maximum Spanning Tree Algorithms {#sec:maxim-spann-tree}
--------------------------------

As mentioned earlier, greedy inference may not produce well-formed trees. In this case, the output of <span style="font-variant:small-caps;">DeNSe</span> can be adjusted with a maximum spanning tree algorithm. We use the Chu-Liu-Edmonds algorithm [@chu1965shortest; @edmonds1967optimum] for building non-projective trees and the Eisner algorithm for projective ones.

Following , we view a sentence $S=(w_0=\text{\sc root}, w_1, \dots, w_N)$ as a graph $G_S=\langle V_S, E_S \rangle$ with the sentence words and the dummy root symbol as vertices and a directed edge between every pair of distinct words and from the root symbol to every word. The directed graph $G_S$ is defined as:

$$\begin{aligned}
        V_S &= \{w_0 = \text{\sc root}, w_1, \dots ,w_N\} \\
        E_S &= \{ \langle i, j \rangle: i \ne j, \langle i, j \rangle \in [0, N] \times [1, N] \} \\
        s(i, j) &= P_{head}(w_i | w_j, S) \quad \langle i, j \rangle \in E_S
    \end{aligned}$$

where $s(i, j)$ is the weight of edge $\langle i, j \rangle$ and $P_{head}(w_i | w_j, S)$ is known. The problem of dependency parsing now boils down to finding the tree with the highest score which is equivalent to finding a MST in $G_S$ [@mcdonald2005non].

#### Non-projective Parsing

To build a non-projective parser, we solve the MST problem with the Chu-Liu-Edmonds algorithm [@chu1965shortest; @edmonds1967optimum]. The algorithm selects for each vertex (excluding [root]{}) the in-coming edge with the highest weight. If a tree results, it must be the maximum spanning tree and the algorithm terminates. Otherwise, there must be a cycle which the algorithm identifies, contracts into a single vertex and recalculates edge weights going into and out of the cycle. The greedy inference strategy described in Equation ) is essentially a sub-procedure in the Chu-Liu-Edmonds algorithm with the algorithm terminating after the first iteration. In implementation, we only run the Chu-Liu-Edmonds algorithm through graphs with cycles, i.e., non-tree outputs.

#### Projective Parsing

For projective parsing, we solve the MST problem with the Eisner algorithm. The time complexity of the Eisner algorithm is $O(N^3)$, while checking if a tree is projective can be done reasonably faster, with a $O(N\log N)$ algorithm. Therefore, we only apply the Eisner algorithm to the non-projective output of our greedy inference strategy. Finally, it should be noted that the *training* of our model does not rely on the Chu-Liu-Edmonds or Eisner algorithm, or any other graph-based algorithm. MST algorithms are only used at *test* time to correct non-tree outputs which are a minority; [DeNSe]{} acquires underlying tree structure constraints from the data without an explicit learning algorithm.

Experiments {#sec:experiments}
===========

We evaluated our parser in a projective and non-projective setting. In the following, we describe the datasets we used and provide training details for our models. We also present comparisons against multiple previous systems and analyze the parser’s output.

Datasets
--------

In the projective setting, we assessed the performance of our parser on the English Penn Treebank (PTB) and the Chinese Treebank 5.1 (CTB). Our experimental setup closely follows and .

For English, we adopted the Stanford basic dependencies (SD) representation [@demarneffe:2006].[^4] We follow the standard splits of PTB, sections 2–21 were used for training, section 22 for development, and section 23 for testing. POS tags were assigned using the Stanford tagger [@toutanova:2003] with an accuracy of 97.3%. For Chinese, we follow the same split of [ CTB5]{} introduced in . In particular, we used sections , for training, sections , for development, and sections , for testing. The original constituency trees in CTB were converted to dependency trees with the Penn2Malt tool.[^5] We used gold segmentation and gold POS tags as in and .

In the non-projective setting, we assessed the performance of our parser on Czech and German, the largest non-projective datasets released as part of the CoNLL 2006 multilingual dependency parsing shared task. Since there is no official development set in either dataset, we used the last 374/367 sentences in the Czech/German training set as development data.[^6] Projective statistics of the four datasets are summarized in Table \[tab:proj\].

  [Dataset]{}    \# Sentences   (%) Projective
  ------------- -------------- ----------------
  English           39,832           99.9
  Chinese           16,091          100.0
  Czech             72,319           76.9
  German            38,845           72.2

  : Projective statistics on four datasets. Number of sentences and percentage of projective trees are calculated on the training set.[]{data-label="tab:proj"}

Training Details
----------------

We trained our models on an Nvidia GPU card; training takes one to two hours. Model parameters were uniformly initialized to $[-0.1, 0.1]$. We used Adam [@kingma:2014] to optimize our models with hyper-parameters recommended by the authors (i.e., learning rate 0.001, first momentum coefficient 0.9, and second momentum coefficient 0.999). To alleviate the gradient exploding problem, we rescaled the gradient when its norm exceeded 5 [@pascanu:2013]. Dropout [@srivastava:2014] was applied to our model with the strategy recommended in the literature [@zaremba:2014; @semeniuta-etal-2016:COLING]. On all datasets, we used two-layer LSTMs and set $d=s=300$, where $d$ is the hidden unit size and $s$ is the word embedding size.

As in previous neural dependency parsing work [@chen2014fast; @dyer2015transition], we used pre-trained word vectors to initialize our word embedding matrix $\mathbf{W}_e$. For the PTB experiments, we used 300 dimensional pre-trained GloVe[^7] vectors [@pennington:2014]. For the CTB experiments, we trained 300 dimensional GloVe vectors on the Chinese Gigaword corpus which we segmented with the Stanford Chinese Segmenter [@tseng:2005]. For Czech and German, we did not use pre-trained word vectors. The POS tag embedding size was set to $q=30$ in the English experiments, $q=50$ in the Chinese experiments and $q=40$ in both Czech and German experiments.

Results {#sec:projr}
-------

For both English and Chinese experiments, we report unlabeled (UAS) and labeled attachment scores (LAS) on the development and test sets; following punctuation is excluded from the evaluation.

Experimental results on PTB are shown in Table \[tab:en\_depparse\]. We compared our model with several recent papers following the same evaluation protocol and experimental settings. The first block in the table contains mostly graph-based parsers which do not use neural networks: Bohnet10 [@bohnet:2010], Martins13 [@martins:2013], and Z&M14 [@zhang:2014:acl]. Z&N11 [@zhang2011transition] is a transition-based parser with non-local features. Accuracy results for all four parsers are reported in .

  ------------------- --------------- --------------- --------------- ---------------
                                                                      
                            UAS             LAS             UAS             LAS
  Bohnet10                   —               —             92.88           90.71
  Martins13                  —               —             92.89           90.55
  Z&M14                      —               —             93.22           91.02
  Z&N11                      —               —             93.00           90.95
  C&M14                    92.00           89.70           91.80           89.60
  Dyer15                   93.20           90.90           93.10           90.90
  Weiss15                    —               —             93.99         [92.05]{}
  Andor16                    —               —         [**94.61**]{}   [**92.79**]{}
  K&G16 [*graph*]{}          —               —             93.10           91.00
  K&G16 [*trans*]{}          —               —             93.90           91.90
  [DeNSe]{}-Pei            90.77           88.35           90.39           88.05
  [DeNSe]{}-Pei+E          91.39           88.94           91.00           88.61
  [DeNSe]{}                94.17           91.82           94.02           91.84
  [DeNSe]{}+E          [**94.30**]{}   [**91.95**]{}     [94.10]{}         91.90
  ------------------- --------------- --------------- --------------- ---------------

  : Results on English dataset (PTB with Stanford Dependencies). +E: we post-process non-projective output with the Eisner algorithm.[]{data-label="tab:en_depparse"}

The second block in Table \[tab:en\_depparse\] presents results obtained from neural network-based parsers. C&M14 [@chen2014fast] is a transition-based parser using features learned with a feed forward neural network. Although very fast, its performance is inferior compared to graph-based parsers or strong non-neural transition based parsers (e.g., Z&N11). Dyer15 [@dyer2015transition] uses (stack) LSTMs to model the states of the buffer, the stack, and the action sequence of a transition system. Weiss15 [@weiss:2015] is another transition-based parser, with a more elaborate training procedure. Features are learned with a neural network model similar to C&M14, but much larger with two layers. The hidden states of the neural network are then used to train a structured perceptron for better beam search decoding. Andor16 [@andor-EtAl:2016] is similar to Weiss15, but uses a globally normalized training algorithm instead.

  ------------------- --------------- --------------- --------------- ---------------
                                                                      
                            UAS             LAS             UAS             LAS
  Z&N11                      —               —             86.00           84.40
  Z&M14                      —               —         [**87.96**]{}   [**86.34**]{}
  C&M14                    84.00           82.40           83.90           82.40
  Dyer15                   87.20       [**85.90**]{}       87.20           85.70
  K&G16 [*graph*]{}          —               —             86.60           85.10
  K&G16 [*trans*]{}          —               —             87.60           86.10
  [DeNSe]{}-Pei          [82.50]{}         80.74         [82.38]{}       [80.55]{}
  [DeNSe]{}-Pei+E        [83.40]{}         81.63         [83.46]{}       [81.65]{}
  [DeNSe]{}              [87.27]{}         85.73         [87.63]{}       [85.94]{}
  [DeNSe]{}+E          [**87.35**]{}       85.85         [87.84]{}       [86.15]{}
  ------------------- --------------- --------------- --------------- ---------------

  : Results on Chinese dataset (CTB). +E: we post-process non-projective outputs with the Eisner algorithm.[]{data-label="tab:ch_depparse"}

  ------------- --------------- --------------- --------------- ---------------
                                                                
  Parser              Dev            Test             Dev            Test
  C&M14              43.35           40.93           32.75           32.20
  Dyer15             51.94           50.70       [**39.72**]{}   [**37.23**]{}
  [DeNSe]{}          51.24           49.34           34.74           33.66
  [DeNSe]{}+E    [**52.47**]{}   [**50.79**]{}       36.49           35.13
  ------------- --------------- --------------- --------------- ---------------

  : UEM results on PTB and CTB.[]{data-label="tab:uem"}

Unlike all models above, [DeNSe]{} does not use any kind of transition- or graph-based algorithm during training and inference. Nonetheless, it obtains a UAS of 94.02%. Around 95% of the model’s outputs after inference are trees, 87% of which are projective. When we post-process the remaining 13% of non-projective outputs with the Eisner algorithm ([DeNSe+E]{}), we obtain a slight improvement on UAS (94.10%).

extract features from bidirectional LSTMs and feed them to a graph- (K&G16 [*graph*]{}) and transition-based parser (K&G16 [*trans*]{}). Their LSTMs are jointly trained with the parser objective. [DeNSe]{} yields very similar performance to their transition-based parser while it outperforms K&G16 [*graph*]{}. A key difference between [DeNSe]{} and K&G16 lies in the training objective. The objective of [DeNSe]{} is log-likelihood based *without* tree structure constraints (the model is trained to produce a distribution over possible heads for each word, where each head selection is independent), while K&G16 employ a max-margin objective *with* tree structure constraints. Although our probabilistic objective is non-structured, it is perhaps easier to train compared to a margin-based one. We also assessed the importance of the bidirectional LSTM on its own by replacing our LSTM-based features with those obtained from a feed-forward network. Specifically, we used the 1-order-atomic features introduced in which represent POS-tags, modifiers, heads, and their relative positions. As can be seen in Table \[tab:en\_depparse\] ([DeNSe]{}-Pei), these features are less effective compared to LSTM-based ones and the contribution of the MST algorithm (Eisner) during decoding is more pronounced ([ DeNSe]{}-Pei+E). We observe similar trends in the Chinese, German, and Czech datasets (see Tables \[tab:ch\_depparse\] and \[tab:ger\_depparse\]).

  ------------------------------------------- -------------------------------------------
  a.                                          b.
  ![image](ptb-crop.pdf){width="49.00000%"}   ![image](ctb-crop.pdf){width="49.00000%"}
  ------------------------------------------- -------------------------------------------

  ------------------- --------------- ------- --------------- -------
                                                              
                            UAS         LAS         UAS         LAS
  MST-1st                  86.18         —         89.54         —
  MST-2nd                  87.30         —         90.14         —
  Turbo-1st                87.66         —         90.52         —
  Turbo-3rd                90.32         —     [**92.41**]{}     —
  RBG-1st                  87.90         —         90.24         —
  RBG-3rd              [**90.50**]{}     —         91.97         —
  [DeNSe]{}-Pei            86.00       77.92       89.42       86.48
  [DeNSe]{}-Pei+CLE        86.52       78.42       89.52       86.58
  [DeNSe]{}                89.60       81.70       92.15       89.58
  [DeNSe]{}+CLE            89.68       81.72       92.19       89.60
  ------------------- --------------- ------- --------------- -------

  : Non-projective results on the CoNLL 2006 dataset. +CLE: we post-process non-tree outputs with the Chu-Liu-Edmonds algorithm.[]{data-label="tab:ger_depparse"}

Results on CTB follow a similar pattern. As shown in Table \[tab:ch\_depparse\], <span style="font-variant:small-caps;">DeNSe</span> outperforms all previous neural models (see the test set columns) on UAS and LAS. <span style="font-variant:small-caps;">DeNSe</span> performs competitively with Z&M14, a non-neural model with a complex high order decoding algorithm involving cube pruning and strategies for encouraging diversity. Post-processing the output of the parser with the Eisner algorithm generally improves performance (by 0.21%; see last row in Table \[tab:ch\_depparse\]). Again we observe that 1-order-atomic features [@pei2015effective] are inferior compared to the LSTM. Table \[tab:uem\] reports unlabeled sentence level exact match (UEM) in Table \[tab:uem\] for English and Chinese. Interestingly, even when using the greedy inference strategy, [DeNSe]{} yields a UEM comparable to Dyer15 on PTB. Finally, in Figure \[fig:uaslen\] we analyze the performance of our parser on sentences of different length. On both PTB and CTB, <span style="font-variant:small-caps;">DeNSe</span> has an advantage on long sentences compared to C&M14 and Dyer15.

For Czech and German, we closely follow the evaluation setup of CoNLL 2006. We report both UAS and LAS, although most previous work has focused on UAS. Our results are summarized in Table \[tab:ger\_depparse\]. We compare [DeNSe]{} against three non-projective graph-based dependency parsers: the MST parser [@mcdonald2005non], the Turbo parser [@martins:2013], and the RBG parser [@lei2014low]. We show the performance of these parsers in the first order setting (e.g., ) and in higher order settings (e.g., ). The results of , MST-2nd, RBG-1st and RBG-3rd are reported in and the results of Turbo-1st and Turbo-3rd are reported in . We show results for our parser with greedy inference (see <span style="font-variant:small-caps;">DeNSe</span> in the table) and when we use the Chu-Liu-Edmonds algorithm to post-process non-tree outputs ([ DeNSe]{}+CLE).

As can been seen, <span style="font-variant:small-caps;">DeNSe</span> outperforms all other first (and second) order parsers on both German and Czech. As in the projective experiments, we observe slight a improvement (on both UAS and LAS) when using a MST algorithm. On German, [DeNSe]{} is comparable with the best third-order parser (), while on Czech it lags behind Turbo-3rd and RBG-3rd. This is not surprising considering that <span style="font-variant:small-caps;">DeNSe</span> is a first-order parser and only uses words and POS tags as features. Comparison systems use a plethora of hand-crafted features and more sophisticated high-order decoding algorithms. Finally, note that a version of <span style="font-variant:small-caps;">DeNSe</span> with features in [@pei2015effective] is consistently worse (see the second block in Table \[tab:ger\_depparse\]).

  -------- ------- ------ ------ ------- -------
                                         
                    Tree   Proj   Tree    Proj
  PTB        1,700  95.1   86.6   100.0   100.0
  CTB          803  87.0   73.1   100.0   100.0
  Czech        374  87.7   65.5   100.0   72.7
  German       367  96.7   67.3   100.0   68.1
  -------- ------- ------ ------ ------- -------

  : Percentage of trees and projective trees on the development set before and after [DeNSe]{} uses a MST algorithm. On PTB and CTB, we use the Eisner algorithm and on Czech and German, we use the Chu-Liu-Edmonds algorithm.[]{data-label="tab:treerate"}

Our experimental results demonstrate that using a MST algorithm during inference can slightly improve the model’s performance. We further examined the extent to which the MST algorithm is necessary for producing dependency trees. Table \[tab:treerate\] shows the percentage of trees before and after the application of the MST algorithm across the four languages. In the majority of cases [ DeNSe]{} outputs trees (ranging from 87.0% to 96.7%) and a significant proportion of them are projective (ranging from 65.5% to 86.6%). Therefore, only a small proportion of outputs (14.0% on average) need to be post-processed with the Eisner or Chu-Liu-Edmonds algorithm.

Conclusions {#sec:conclusions}
===========

In this work we presented [DeNSe]{}, a neural dependency parser which we train without a transition system or graph-based algorithm. Experimental results show that [DeNSe]{} achieves competitive performance across four different languages and can seamlessly transfer from a projective to a non-projective parser simply by changing the post-processing MST algorithm during inference. In the future, we plan to increase the coverage of our parser by using tri-training techniques [@li2014ambiguity] and multi-task learning [@luong:2015].

#### Acknowledgments

We would like to thank Adam Lopez and Frank Keller for their valuable feedback. We acknowledge the financial support of the European Research Council (ERC; award number 681760).

[^1]: Our code is available at <http://github.com/XingxingZhang/dense_parser>.

[^2]: For more detail on LSTM networks, see e.g., or .

[^3]: Note that $h(w_i)$ can be [root]{}.

[^4]: We obtained SD representations using the Stanford parser v.3.3.0.

[^5]: <http://stp.lingfil.uu.se/~nivre/research/Penn2Malt.html>

[^6]: We make the number of sentences in the development and test sets comparable.

[^7]: <http://nlp.stanford.edu/projects/glove/>
