Implementing an Arc-Standard Dependency Parser using Neural Networks (Chen and Manning, 2014)

Sanyam Asthana, 24th June 2026

What's this?

In 2014, Danqi Chen and Christopher D. Manning (Stanford) published "A Fast and Accurate Dependency Parser using Neural Networks".

This paper used neural networks to train a dependency parser, based on the arc-standard structure. The original paper can be found here.

I tried to implement this in Python, and the following is about how it went.

Authors' Spec

  1. The original authors used the Penn English Treebank (PTB) to train the model
  2. They used pre-trained word2vec skip-gram embeddings, trained on massive Google News dataset, containing about 100 billion words.
  3. They got a UAS (Unlabeled Attachment Score) of 91.8% on English.

My Spec

  1. I didn't have access to the proprietary Penn English Treebank for free, so I used Universal Dependency (UD) English Treebank instead, which is significantly shorter and more chaotic than PTB.
  2. In the beginning, I used untrained embeddings and trained them along with the model, but later I pivoted to GloVe embeddings.
  3. I got a UAS of.. keep reading :)

What really is dependency parsing?

In NLP tasks, dependency parsing refers to connecting each word of a body of text to words which depend on it.

For example, in the phrase "big slippery whack-a-mole" (completely made-up phrase btw), "big" and "slippery" depend on "whack-a-mole", and they serve as noun modifiers i.e., they modify the noun ("whack-a-mole") since they are adjectives.

There exist many more such relations, and a dependency parser does the painstaking work of labeling and assigning head nodes. Dependency parsing outputs a dependency graph of a sentence, which is highly beneficial in communicating the semantics of the sentence, much more than constituency graphs, especially for languages with free word order, such as Hindi (English does not have a free word order, as most sentences are Subject-Verb-Object, and swapping them changes the meaning of the sentence).

The Data Structure

The core of the implementation is the Arc-Standard data structure. It is a combination of three other structures:

Along with these structures, the Arc-Standard data structure has the following operations:

For the implementation specifically, the arc operations also assign the relations along with their corresponding dependency labels, such as "NMOD".

Then comes some special operations, which are required specifically for the implementation:

All in all, as soon as a word gets assigned its head, it is removed from the stack. The iteration ends when the buffer is empty and the stack only contains the ROOT node (since ROOT node is the only head without a head in a dependency graph).

The paper requires N (in the first two operations above) to be 3, but I build a general method instead.

To train the model on data, we use something the paper calls the Oracle. The Oracle analyses the training data sentences and produces a sequence of operations which will produce the correct dependency tree for the sentence, by looking at the input dependency tree. In other words, it reverse-engineers the correct sequence of operations which produce the input dependency tree from the input sentence. The training loss is calculated against this correct sequence.

This algorithm is a greedy algorithm, and it cannot represent non-projective trees i.e., dependency graphs with crossing edges, and I had to remove such sentences from my training dataset

The Neural Network

Let's now come to the most fun part (subectively)! The paper uses a feedforward neural network to train the dependency parser. The neural network has the following features:

  1. The input layer has 2400 input neurons (as of the paper).
  2. The hidden layer has 200 neurons (as of the paper).
  3. The number of outputs is 2Nl + 1, where Nl is the number of labels in the label vocabulary. More on this later.
  4. The activation function chosen by the authors is f(x) = x3, which is an uncommon function for activation. More on this later.

When processing, we have access to 3 types of data: words, tags and labels. Words are well, words of the sentence. Tags are the POS (Part-of-Speech) tags associated with the word. Labels are the dependency labels associated with the word. Nw, Nt and Nl are the total number of words, tags and labels in the vocabulary, respectively.

For each training sample, we assemble three sets of data: Sw, St and Sl. Here is what they contain:

The input for one sentence to the neural network is a concatenation of Sw, St and Sl. This makes the input vector have 18 + 18 + 12 = 48 elements.

According to the original paper, the words, tags and labels are represented by 50-dimensional embeddings each. Hence, each word/tag/label has 50 elements associated with it. The input vector has 48 such elements. This makes the total elements in the input vector to be 48 x 50 = 2400. Hence the reason we have 2400 input neurons.

According to the original paper, the tag and label embeddings are randomly initialized before training, and the embeddings are trained during the training process. On the contrary, the paper uses pre-trained word2vec skip-grams embeddings for the words, trained on massive Google News dataset.

There are 2Nl + 1 outputs of the neural network. Each of the outputs correspond to an operation on the arc-standard dependency parser. There are Nl output logits corresponding to the probability of the operation being a LEFT-ARC operation, with each of the Nl labels as the arc label. The next Nl logits correspond to the probability of the operation being a RIGHT-ARC operation. The last logits corresponds to the probability of the operation being a SHIFT operation.

At the end, the model calculates a softmax over the output logits to calculate the probability of each of the operations.

Before applying softmax, we also mask out the illegal operations. We then calculate the loss using Cross Entropy, with the target as the decided operation by the Oracle for that iteration.

Something I did not go over yet is the choice of activation function i.e. f(x) = x3. The authors mention that since the function includes the term of xwxtxl, it does a good job of merging the information from each of the three sets, which benefits in the task of dependency parsing.

My implementation

Now that I have explained how the model works on a higher level (there are much more nuances mentioned in the original paper), I'd like to go over how I implemented the model.

Data

I did not have access to the proprietary Penn English Treebank (PTB) data, so I had to use UD English Treebank instead, which is significantly smaller and more chaotic than the Penn English Treebank.

For tags and labels, I used the data which came along with the UD Treebank's CoNLLU-formatted data.

Arc-Standard data structure

The first thing I implemented is the Arc-Standard data structure. I implemented all the structures using Python lists. Instead of removing elements from the buffer, I used a pointer which points at the current "top" element of the buffer, which increments with each SHIFT operation. This is done to avoid expensive O(n) remove operations.

The graph is implemented using two dictionaries, left_children and right_children, with keys as the node IDs and values as lists of their children.

Neural Network

The neural network is implemented using PyTorch's nn.Module. Nothing interesting here, just how it is done usually.

What is interesting though is that in the beginning, I kept the word embeddings as untrained, and trained them along with the model training process.

Iterations

Initially, I set the number of epochs to 5 and the learning rate to 0.001, and I used the Adam optimizer.

When I trained and evaluated the model the first time, I got a UAS of 75.12%. This was good, but I wanted to see how far can I go near the paper's result of 91.8%. I knew this was going to be hard since I had a disadvantage of a much smaller dataset.

I changed the dimensions of each of the embeddings to 100, instead of 50, which gave me a lower UAS of 74.38%. The thing is that doubling the dimensions of the embeddings made the input layer have 100 x 48 = 4800 neurons, while the hidden layer stayed at 200. 4800 inputs couldn't efficiently "squeeze" into 200 hidden neurons, resulting in a worse result.

I increased the number of hidden neurons to 500 and the UAS immediately came out to be 76.92%, which is an improvement over the initial result.

After some more iterations, I arrived at the configuration with 120 embedding dimensions and 720 neurons in the hidden layer, which gave me a UAS of 81.47%.

At this point, I was quite happy, but also wanted to see how far I could take this.

I set the learning rate to 0.0001, applied gradient clipping so the loss could not suddenly explode, and set the number of epochs to 15. Keeping the embedding dimensions at 120 and the hidden neurons at 720, this gave me a UAS of 83.27%.

However, I noticed that during my epochs, the loss sometimes increased in subsequent epochs, instead of decreasing. To battle this, I used a self-stopping training loop, which stops whenever a subsequent epoch has loss greater than the previous loss, and set the maximum number of epochs to 50. I also set the number of embedding dimensions to 125 and the number of hidden neurons to 725. This increased my UAS further to 83.71%.

I then thought that stopping immediately upon noticing an increasing loss is way too harsh, so I used patience-based self-stopping training loop. The loss could exceed a maximum of 3 times before the training would stop. This further improved the UAS to 83.78%.

At this point, there was not a lot of hyperparameter tuning I could do, so I decided to swap out my untrained word embedding matrix for GloVe's pre-trained embeddings. I used 100-dimensional GloVe embeddings, and rolled over the other embedding dimensions to 120 and the number of hidden neurons to 720, and incresed the patience level of the training loop from 3 to 5. This gave me a UAS of 84.43%.

I then swapped the 100-dimensional GloVe embeddings for 300-dimensional GloVe embeddings, but after a lot of tuning, I couldn't get it to surpass the previous UAS of 84.43%, set by the 100-dimensional GloVe embeddings.

It is at this point I realised that my network was probably overfitting on the training dataset because of 300 embedding dimensions and the large number of hidden neurons, and hence it wasn't able to produce better results with the evaluation dataset. I swapped out the 300-dimensional GloVe embeddings with small, 50-dimensional GloVe embeddings and dropped down the dimensions of the tag and label embeddings to 50. I also dropped down the number of neurons in the hidden layer to 500. I also applied a dropout of 0.5 in the network to prevent any overfitting. All of this combined resulted in a UAS of 84.79%.

Finally, I felt like a dropout of 0.5 was too harsh, so I reduced the dropout to 0.2, and increased the max number of epochs from 50 to 60, to get a final best UAS of 85.57%.

Conclusion

So that is it! An 85.57% UAS score on a dependency parser. This was a really fun paper to implement and implementing it taught me a lot of things which merely reading the paper never could have. The code of the model, along with the exported weights can be found in this GitHub repository. Farewell!