CS584: Natural Language Processing - Assignment 5: Dependency Parsing
CS584: Natural Language Processing Name
Assignment 5: Dependency Parsing
Homework assignments will be done individually: each student must hand in their own answers. Use of partial or entire solutions obtained from others or online is strictly prohibited. Electronic submission on Canvas is mandatory.
1. Transition Mechanisms (60 points)
(a) (10 pts) Given a sentence “I parsed this sentence correctly” with the transitions, complete the following table. The first three steps are provided in the table, showing the configuration of the stack and buffer, as well as the transition and the new dependency (if has) for the following steps.
Stack Buffer New dependency Transition
[ROOT] [I, parsed, this, sentence, correctly] Initial Configuration
[ROOT, I] [parsed, this, sentence, correctly] SHIFT
[ROOT, I, parsed] [this, sentence, correctly] SHIFT
[ROOT, parsed] [this, sentence, correctly] parsed → I LEFT-ARC
(b) (10 pts) A sentence containing n words will be parsed in how many steps (in terms of n)? Briefly
explain in 1-2 sentences why.
(c) (20 pts) Implement the transition mechanisms, SHIFT, LEFT-ARC, and RIGHT-ARC. (Please
check the notebook for the details.)
(d) (20 pts) Implement Minibatch Dependency Parsing based on the follwoing algorithm.
Algorithm Minibatch Dependency Parsing
Input: sentences, a list of sentences to be parsed and model, our model that makes parse decisions
Initialize partial parses as a list of PartialParses, one for each sentence in sentences
Initialize unfinished parses as a shallow copy of partial parses
while unfinished parses is not empty do
Take the first batch size parses in unfinished parses as a minibatch
Use the model to predict the next transition for each partial parse in the minibatch
Perform a parse step on each partial parse in the minibatch with its predicted transition
Remove the completed (empty buffer and stack of size 1) parses from unfinished parses
end while
Return: The dependencies for each (now completed) parse in partial parses.
2. Neural Networks for Parsing (40 points)
(a) (20 pts) Build your neural network. (Follow the instruction in the notebook. Please NOTE that DO NOT use tf.keras.layers.Dense or tf.keras.layers.Embedding module in your code for this assignment, otherwise you will receive deductions for this problem.)
(b) (20 pts) Train the network and report the Unlabeled Attachment Score (UAS).
Submission Instructions You shall submit a zip file named Assignment5 LastName FirstName.zip which contains: (Those who do not follow this naming policy will receive penalty points)
• The Jupyter notebook which includes all your code and the output of each cell.
• A pdf file contains all your solutions for 1.(a) and 1.(b).
