代写COMP4650、代写Python程序设计

日期：2022-10-17 07:35

COMP4650/6490 Document Analysis – Semester 2 / 2022

Assignment 3

Due 17:00 on Wednesday 19 October 2022 AEDT (UTC +11)

Last updated September 27, 2022

Overview

For this assignment, you will implement several common NLP algorithms: probabilistic context free

grammar learning, dependency parsing, and relation extraction in Python.

Throughout this assignment you will make changes to the provided code to improve or complete existing

models.

Submission

• The answers to this assignment (including your code files) have to be submitted online in Wattle.

• You will produce an answers file with your responses to all questions. Your answers file must be a

PDF file named u1234567.pdf where u1234567 should be replaced with your Uni ID.

• Questions 1 and 3 also require you to submit an output file in a format specified by the question.

• You should submit a ZIP file containing all the code files, your answers PDF file, and these requested

output files BUT NO OTHER DATA.

Marking

This assignment will be marked out of 15, and it will contribute 15% of your final course mark.

Your answers to coding questions (or coding parts of each question) will be marked based on the quality

of your code (is it efficient, is it readable, is it extendable, is it correct). The output files requested will be

used as part of the marking for the coding questions.

Your answers to discussion questions (or discussion parts of each question) will be marked based on how

convincing your explanations are (are they sufficiently detailed, are they well-reasoned, are they backed

by appropriate evidence, are they clear).

This is an individual assignment. Group work is not permitted. Assignments will be checked for

similarities.

Question 1: Probabilistic Context Free Grammars (3 marks)

For this question you will be modifying the starter code in syntax parser.py. You have been provided

with a training dataset containing 73,638 English language sentences, which have been parsed into

constituency trees (in parsed sents list.json).

For example, given the sentence: “A large elephant scratching”. The parse tree is:

1

For this structure the parsed sentence in parsed sents list.json is

[“S”, [“NP”, [“DT”, “a”], [“JJ”, “large”], [“NN”, “elephant”]], [“VP”, [“VBG”, “scratching”]]].

Note that parsed sents list.json contains a list of parses, each for a different sentence.

Your task is to estimate a probabilistic context free grammar (PCFG) given this dataset. You should

estimate the conditional probabilities of the rules in this grammar (including all rules that express facts

about the lexicon) using the maximum-likelihood approach given in lectures. Some examples of rules in

this grammar are:

S → NP

VBN → parked

ADVP → INNP

NP → NP, NP

Note that some terminals and non-terminals are punctuation characters. There are many more rules

than those listed here and you will first have to identify all the rules. All terminals are lower case or

punctuation.

When your syntax parser.py code is run, write a list of all the transition rules and their conditional

probabilities to a file called “q1.json”. There is a class called RuleWriter in syntax parser.py which

will write the rules in the correct format for the automated judging system (do not modify this class). The

expected format is (example of format only not actual answers):

[[“NP”, [“PP”, “NP”], 0.8731919455731331], [“NNS”, [“locations”], 0.062349802638746935],

. . . <many more rules> ]

Hint: if you create a test input file containing only

[[“A”, [“B”, [“C”, “blue”]], [“B”, “cat”]]]

Your program should output (note that the order the rules are listed in the output does not matter):

[[“A”, [“B”, “B”], 1.0 ], [“B”, [“C”], 0.5 ], [“B”, [“cat”], 0.5 ], [“C”, [“blue”], 1.0 ]]

What to submit

Make sure to submit “q1.json” for marking. Also make sure to submit your syntax parser.py.

Question 2: Dependency Parsing (6 marks)

Complete both Part A and Part B of this question.

Part A

The file dependency parser.py contains a partial implementation of Nivre’s arc-eager dependency

parsing algorithm. Your first task is to implement the missing left arc method, reduce method,

2

right arc method, and parse function. Your implementation should follow the transitions as given by

the lecture slides (also some additional instructions are provided as comments in dependency parser.py).

Make sure that your class methods and parse function return True if the operation(s) was/were successfully

applied, or else False. The parse function should return True if it generates a dependency forest. Your

implementation must make use of the DepContext class which stores the current state of the parser.

Do not modify the DepContext class or the name and parameters of the methods and functions you

have been asked to implement because Part A of this question will be automatically marked.

The auto-marker will inspect the internal state of DepContext to confirm that operations have been

applied correctly. You should not use any additional imports for this question (except from Python

standard libraries). The judging system will use Python-3.9.13 in a sandboxed Linux environment.

Hint: As mentioned in lectures we need to make sure that words are uniquely represented (in case there

are multiple copies of the same word), to do this we use the position of the word in the sequence, with

the [ROOT] token prepended to the sequence. This is handled by DepContext.

What to submit

In your answers PDF file include the output of dependency parser.py (it runs a small number of test

cases and prints them to the terminal). Make sure to submit your dependency parser.py.

Part B

Your second task is to implement the standard oracle for arc-eager dependency parsing in oracle parser.py

(specifically you should implement the parse gold function). Make use of the parsing class you developed in Part A of this question – do not modify your parsing class from Part A, all code for this second

part should be put in the oracle parser.py.

The parsing class from Part A has been imported. Additional imports are not permitted (except from

Python standard libraries). You may add helper functions in oracle parser.py.

The oracle you need to implement determines which action to be performed in each state to reconstruct the

ground truth dependency parse tree. It returns the list of actions, and the states in which they occur – though

in this case you should return only features of the state (using the provided extract features function

– do not modify the feature extraction code). The details of this algorithm were not covered in lectures,

instead you should implement Algorithm 1 from this paper https://aclanthology.org/C12-1059.pdf

(while this paper covers different oracle methods including a dynamic oracle, you should only implement

Algorithm 1 on page 963). You should implement un-labelled dependency parsing so you will need to

modify this algorithm to work without labels. To implement Algorithm 1 you will need to make use of

the parsing class you developed in Part A of this question.

Once you have implemented the parse gold function, run oracle parser.py and it will determine the

actions that could generate the ground truth dependency parse trees in gold parse.json under the rule

set in rule set.json. It will print the first 3 cases where the oracle could reproduce the ground truth,

the first 3 cases where it could not reproduce the ground truth, and after a short wait the number of total

failure and total success cases.

What to submit

In your answers PDF file include the output of oracle parser.py and explain why it failed in the three

printed cases. Make sure to submit your oracle parser.py.

3

Question 3: Relation Extraction (6 marks)

Your task is to design and implement a relation extraction model along with its training and testing pipeline.

Specifically, your model should extract the relation ‘nationality’ (denoted /people/person/nationality

in our dataset) which holds between a person and a geopolitical entity (GPE). For example,

/people/person/nationality(Yann LeCun, France),

/people/person/nationality(Julie Bishop, Australia).

The training data is provided in sents parsed train.json, the test data is in sents parsed test.json.

A file containing a list of country names (country names.txt) is also provided for you to use. The test

data does not have the ground truth set of relations; your program must extract them. Some starter code

has been provided in rel extract.py which shows you how to read in the data, access its various fields,

and write a valid output file.

It is very important that your relation extraction algorithm work for entities not seen during training.

To clarify, this means that your model should be designed so that it can identify relations such as

/people/person/nationality(Julie Bishop, Australia) even if “Julie Bishop” and “Australia”

entities are not in the training data. None of the (PERSON, GPE) pairs that constitute a nationality relation

occur in both the training dataset and the test dataset. The focus of this question is to develop a good

training/validation pipeline and to explore different lexical, syntactic or semantic features. You should

use the “Feature-based supervised relation classifiers” technique introduced in the Speech and Language

Processing textbook (3rd ed. Jan 12, 2022 draft) Section 17.2.2 and Figure 17.6. You do not have to

implement all the suggested features, but an attempt to implement a variety of them is expected. You

will likely need to do substantial pre-processing of the input data as well as some post processing of

the output list to get a good result. You should use LogisticRegression from scikit-learn as the

classifier. Neural networks and vector features generated by neural networks are not to be used

for this question. You may use spaCy1 to extract additional features from your text; however, several

features are already provided for you (see Description of the data below). It is possible to get full marks

using only the features provided; however, these features will likely need some processing before they can

be used appropriately as part of a classification pipeline. You are permitted to use the Python standard

libraries, numpy, pandas, scikit-learn, nltk, spaCy. You should not use other libraries, datasets, or

ontological resources.

The final goal is to extract all relations of the type nationality that exist in the test data, not to simply

identify if a relation type is in each sentence. Your output should be a list of all the relations in the test

data, in CSV format (you should name it “q3.csv”) – the starter code provides a function to write this

file in the correct format for the automated judging system. The order of lines in this CSV file does not

matter, and duplicate lines will be removed before scoring. An example judging script eval output.py

is provided for you. Since you have not been given the ground truth for the test data you can only run this

script using the training data. To do a sanity check before submitting,

(1) first run your rel extract.py using the training data, and

(2) evaluate your model performance on the training set

python eval_output.py --trainset

(3) to make sure “q3.csv” is the output from the test data, run rel extract.py again using the test data

(this overwrites “q3.csv” with the relations extracted from the test set).

Note that part of the mark for this question will be based on the F1 score of your “q3.csv” file on the

held-out ground truth for the test data (evaluated by the examiner using the automated judging system).

The rest will be based on an examination of your code and answers to the questions below.

1https://spacy.io/

4

What to submit

Answer the following questions in your answers PDF file (please answer in plain English, dot points are

preferred, do not include code snippets or screenshots of code as these will not be marked):

(a) What pre-processing did you do?

(b) How did you split the data into training and validation sets?

(c) How did you choose hyper-parameters?

(d) What features did you choose and why did you choose these features?

(e) What post-processing did you do?

Submit your code. Submit your output file named “q3.csv” (make sure this is the output from the test

data). Submit your answers to the questions.

Description of the data

The data you have been given is described in detail below. Briefly, it is a set of sentences, each of

which contain a relation between two entities. You may use the relations that are not the target relation

/people/person/nationality to generate negative examples on which to train your model.

sents parsed train.json and sents parsed test.json each contain a list of dictionaries. Each dictionary corresponds to a different example. Each example dictionary has the following fields:

• tokens: a tokenised sentence that contains a relation

• entities: a list of the named entities in the sentence

• relation: a description of the relation in the sentence

Each entity is a dictionary with the following fields:

• start: the token index where the entity starts

• end: the token index where the entity ends

• label: the entity type. PERSON = a person, GPE = a geopolitical entity, and several others

Each relation is a dictionary with the following fields (note that the relation field has been removed from

sents parsed test.json):

• a: first entity that is part of the relationship (tokenised into a list)

• b: the second entity that is part of the relationship (tokenised into a list)

• a start: the token index where the first entity starts

• b start: the token index where the second entity starts

• relation: the type of relation, note we are interested in the /people/person/nationality relation

for this assignment.

There are also some additional features that may or may not be helpful (each of the features below is a

list, the array indices match to those of the tokenised sentence):

• lemma: the tokenised text that has been lemmatised.

• pos: part of speech tags for each word

• dep: the dependency relationships

5

• dep head: the head of each dependency relationship (allowing you to reconstruct the full dependency tree)

• shape: shape features for each word. This preserves things such as word length and capitalisation

while removing much of the content of the word.

• isalpha: is each word only alphabetic.

• isstop: is each word in the spaCy stop word dictionary (and thus likely to be common)

All features were extracted using spaCy-2.3.5 en core web md models. The data you have been provided

was constructed automatically by matching ground truth relations to text. For the training data any

sentence that had both the named entities that participated in a ground truth relation was marked as

containing that relation. No manual checks were done to ensure accuracy. You might like to consider

how this will affect the data quality.

6