1
• •
•
ANLP exam study guide and sample questions
Sharon Goldwater November 20, 2020
Content and format
The final exam will primarily cover content from Weeks 5-10, but may include ques-
tions that require synthesising material from the whole course. Questions will be worth 50 marks in total.
– The first 20 marks will be from several smaller questions, most of which are more straightforward.
– The final 30 marks will consist of three 10-mark questions that may have some more open-ended parts.
As in the midterm,
– Each question will indicate the number of marks it is worth.
– Partial credit may be awarded.
– The format is open book and question types may include multiple choice, numerical answers, or free response.
– The exam will be presented online using the Gradescope system, and your answers will be saved as you go.
Unlike the midterm,
– You will be logging into Gradescope via Learn, because the integration of the two systems has recently finished. We will provide more information about this in due course.
– The exam is written to take 2 hours (as in previous years), and you will have one additional hour to account for any minor issues with uploading images, internet problems, etc. So you will have 3 hours altogether.
1
•
2
• •
•
•
– The exam is at a fixed time (1300 GMT) and you will need to log in to do the exam at that time in order to have the full 3 hours to finish. Unfortunately we are not able to change this, as it is due to University exam regulations.
Revision tips
Don’t wait until the last minute. Study early and often. Research shows that
spaced repetition is the most effective way to remember material.
Don’t rely on the open book. Pretend the exam is closed-book, or that you have at most a single sheet of paper to write down all the information you need to look up. It’s a mistake to think you don’t need to remember anything: you will not have time to look up lots of information during the exam. Creating a single page containing key information you think you might need will force you to consider what is most important in the course, what parts you can remember, and what parts you need to write down.
Study actively. Simply reading information is not a good way to remember or under- stand it. Work through examples, making sure you get the same answer that’s in in the text or notes, and think about what questions we might ask related to that material (see above about types of questions). Also ask yourself how different parts of the course connect to each other. What are the different themes? What are different ways to approach some of the tasks?
Consider the types of questions we might ask, and how they would apply to different parts of the course. Types of questions include:
– Applying a method, model or linguistic concept to a particular situation. (For example, parsing a sentence, either by hand or using an algorithm; computing the probability of a construction under a particular probabilistic model.)
– Analysing or evaluating one or more methods. (For example, discussing or providing examples of the pros and cons of a particular method for some task; explaining the similarities and differences between two methods; explaining or pro- viding examples of why a particular phenomenon is challenging for NLP; analysing the execution of an algorithm or the properties of a model that you have learned about.)
– Synthesising knowledge to address a new situation. (For example, given a new task related to one we’ve discussed, discuss how you could apply or extend methods we have seen to address it, and the problems you might expect.)
Practice the way you will be tested. You will need to type your answers (or in a few cases draw them by hand) in a limited amount of time. So practice doing that, using the sample questions below or other exercises from tutorials, etc.
2
•
• Use a held-out dataset (2019-20 exam). This year’s exam is different because it mainly focuses on the second part of the course and is open book, but it is most similar to the 2019-20 exam, which also had 20 points of more straightforward questions followed by three 10-point more challenging questions. So we suggest leaving that one aside until you have done most of your revision, and then going through it in a single 2-hour sitting (it was a 2h exam). You may discover timing issues or gaps in your knowledge. To help you do this, we have excluded questions from the 2019-20 exam in the samples below. You can find the full 2019-20 exam here: https://exampapers.ed.ac.uk/. (Don’t bother looking at other past papers, we’ve included the relevant questions from them in the midterm study guide and below.)
3 Sample questions
The sample questions below are questions from previous exams that would be appropriate as open-book questions covering content from this year’s course. (Questions that are only about Weeks 1-4 are not included here since we already provided those before the midterm.) Each question is shown with the number of marks that it was worth on a two-hour final exam worth 50 marks in total.
We do not provide model answers. It is easy to convince yourself you know the answer by looking at the answer too soon. Even if you don’t do that, many questions have different ways to answer well, so model answers can be misleading. You may also know from the midterm that even if you are on the right track, marks depend on the clarity of your response.
Instead, we encourage you to post your own answers to these questions on Piazza. If lots of students take us up on this, we can’t promise to give feedback on every proposed solution, but we will try to do so for at least a reasonable selection.
3.1 Questions you’ve seen before
These questions are repeated from the midterm guide, either because parts of the question were not included then (because they require knowledge from later in the course), or because your answer might be different now, since you have more to draw on.
1. In social media such as Twitter, users sometimes emphasize words by repeating let- ters. For example, a user might write I lloooovveee it! to emphasize the word love. However, this non-standard spelling can present problems for NLP systems. This question considers some ways to deal with the problems.
(a) The diagram below shows a finite-state automaton that recognizes the word love. Convert this to a finite-state transducer that corrects non-standard to standard spelling for the word love. Assume that the non-standard spelling contains the
3
characters l, o, v, e in that order, but might have more than one of each character. Your FST need not be deterministic.
ion
love
START
(b) Suppose you designed similar transducers for all English words in order to convert emphasized (repeated letter) versions of words into standard spelling. What prob- lem(s) might you have with the results? Outline how you might try to solve these problem(s) using other methods from the course, assuming you have access to the full text where the words are used. Include specific examples in your answer where possible, and discuss whether your solution requires other resources beyond those already mentioned, and any other pros/cons of your solution.
2. This question is about handling unseen words in sequence models. As in the previous question,we want to tag named entities using the PER, ORG, and OTH tags.
The following sentences occur in our test set, and the words Xfinity, GBX, Altoona, Slovensky, and semiconscious have not been seen in training:
Xfinity is going further .
GBX acquired Altoona Corporation for $100 million .
Mr Slovensky looked at the semiconscious attendees .
(a) Consider the following method for handling unseen words using an HMM. In the training corpus, use the new token UNK to replace all words that occur exactly once, and then estimate probabilities as usual. To tag the test sentences, temporarily replace any unseen word with UNK, and then run the Viterbi algorithm. In the output, change each UNK back to its original word.
Using this method, which of the unseen words in the example sentences seem most likely to be tagged correctly, and why? (That is, what information might lead the HMM to predict the correct tag?)
(b) Now consider using a discriminative sequence model instead, so we can include arbitrary features. Describe two features you think could improve the model’s performance, and explain why you think so, with reference to the examples above and your knowledge of English.
3. Suppose you want to build a sentiment analysis system for movie reviews. That is, given the text of a movie review, your system should classify the review as either positive or negative.
4
[3 marks]
[6 marks]
[3 marks]
[3 marks]
3.2
1.
Describe how you would build such a system. Your description should include the following aspects:
• What data or other resources would you need, how you might get them, and how you would use them.
• What model or algorithm you would use, and how you would apply it in this situation. Your description should be high-level and does not need to include equations.
• How you would evaluate the results of the system.
• What, if any, ethical issues might arise in developing the system.
In some cases there might be multiple options for each choice. If so, mention briefly the strengths and weaknesses of each approach, or say what additional information you might need in order to decide which approach is best.
Questions you haven’t seen before
Cocke-Kasami-Younger (CKY) parsing
The figure below shows an intermediate state of a CKY parse of the ambiguous string “time flies”.
(a) What are the rules that must be in the grammar used in this parse so far, and to get it to a successful conclusion with two analyses of the whole string as S, one with a structure which would also be appropriate for “open the door!” and the other appropriate for “water evaporates”?
(b) What happens next? That is, what gets inserted into the upper-right-hand corner? Why? That is, explain in each case how the CKY algorithm determines what gets added.
Note that you are not required to stick to Chomsky Normal Form for your rules. That is, you may use any symbols on the right-hand side of rules, as long as there are only one or two of them.
5
[8 marks]
[3 marks]
[3 marks]
1. 2. 3. 4. 5.
Rule
Det →a
N →green Adj →green N →flower V →flower
Sem. attachment
λP.λQ.∃x.P (x) ∧ Q(x) 6. λx.green(x) 7.
Sem. attachment
N.sem Adj.sem(Nom.sem) Det.sem(Nom.sem) V.sem V.sem(NP.sem)
2. Suppose we have the following grammar fragment with semantic attachments. Grammar
rules are numbered so you can refer to them
easily.
Rule
Nom →N
Nom →Adj Nom NP →Det Nom VP →V VP→VNP
3. (a)
Suppose you are building a question-answering system. Using an example, explain why it is important for your system to be able to identify the kind of lexical semantic relationship that exists between the word car and the word vehicle.
4. (a)
The following table shows which of five different 50-word documents contain each of two words, x and y. For example, the under document 1 for word x means that x occurred (at least once) in document 1.
doc: 1 2 3 4 5 x:
y:
Based on this data, what is the pointwise mutual information (PMI) between the events “x occurs in a document” and “y occurs in a document”, assuming maximum-likelihood estimation of probabilities? You should write down the gen- eral expression for PMI and plug in the appropriate numbers, as well as giving the final numerical value.
λP.λx.green(x) ∧ P (x) λx.f lower(x)
λx.λy.f lower(x, y)
8.
9. 10.
(a) Is the meaning representation language in this grammar compositional? Explain why or why not.
(b) Which rules are needed to parse the phrase a green flower?
(c) Show how the meaning representation for a green flower is obtained. You can explain each step, show a parse tree, or use some combination of those to illustrate the method.
[2 marks ] [1 mark ]
[4 marks ]
[2 marks ] [2 marks ]
(b) What resource could you use to help identify this kind of relationship?
(b) In our lab on sentiment analysis in Twitter, we tried to determine if certain “target” words (e.g., Bieber) are generally viewed positively or negatively. We did so by computing PMI between the target words and words that are known to convey positive or negative sentiment (e.g., love or hate). Discuss how negation words (no, not, don’t, etc.) might affect the results of such an analysis, and whether there are ways you could try to address any problems these words might cause.
6
[3 marks ]
[4 marks ]
5.
(a)
Consider the following joke by Groucho Marx:
One morning I shot an elephant in my pajamas. How he got into my pajamas I don’t know.
Sketch two alternative trees and accompanying grammar rules for the sentence “I shot an elephant in my pajamas” which might be used to explain the joke quoted above.
You can assume the following rules to start with, but will need to add more of your own:
N −→ elephant | pajamas D −→ an | my
P −→ in
NP −→ D N
PP −→ P NP S −→ NP VP
You do not need to use Chomsky Normal Form for your rules. Also, this is not a question about statistical grammars, or about processing or ranking alternative analyses. Nor should you make any attempt at attaching explicit semantics to your trees.
(b)
6. Fill in the blanks: (Write the answers in your script book, not on this paper!)
Briefly explain the aspects of grammar discussed in the course that are illustrated by the first sentence in the above joke and your trees.
[2 marks ]
[1 mark ] [1 mark ]
[7 marks]
(a) In terms of lexical semantic relationships, “fruit” is a of “apple”.
(b) In WordNet, “buy” and “purchase” belong to the same because in many
contexts, they are .
7. Answer the following questions about this ambiguous sentence:
I ate the fish in the freezer
(a) Give unambiguous paraphrases of each of the two meanings and say which of them is the more likely meaning.
(b) Look at the three syntax trees shown in Figure 1 on the following page. Which of them (A, B, or C) best corresponds to the likely meaning of the sentence? (Write the correct letter in your exam book.)
(c) Is the ambiguity in this sentence also reflected in its dependency structure? If so, give the two alternative labelled dependency parses and say which corresponds to the likely meaning. If not, explain why not.
7
[3 marks ]
A. S
H H
H H H
NP VP
H
H H H H H
Pro
IV NP PP
H
ate Det N the fish
B. S
H H
H H H
H
P NP
H H
in Det N the freezer
H H
NP Pro I
VP
H H H H
VP PP
H H HH
V NP P NP
H HH
ate Det N the fish
in Det N the freezer
H
C. S
H H H
NP Pro I
ate
VP
H H
HH
V NP
H H H
NP PP
H H
H
Det N the fish
H
P NP
H H
in Det N the freezer
Figure 1: The trees used for question 7b and question 8.
8
8. Look again at the parse trees in Figure 1. Assume we have a grammar with all the rules needed to generate these trees. Which rule(s) used in these trees could cause non-termination if we tried to parse with a recursive descent parser?
9. Answer the following questions about the same sentence used in Question 7:
I ate the fish in the freezer
(a) Give an example of a contrasting sentence that illustrates the fundamental weak- ness of vanilla PCFGs for attachment disambiguation, and explain what that weakness is, with reference to your contrast pair. You can refer to the tree struc- tures in Figure 1 by letter (A, B, C) if you wish.
(b) What extension to the vanilla PCFG model could potentially disambiguate both sentences correctly? Justify your answer using syntactic trees and/or rules as appropriate.
10. Suppose I want to classify restaurant reviews into those that complain about the restau- rant’s service and those that do not. I evaluate two different text classification systems on the same dataset of reviews. Compared to the gold standard, system A gets a preci- sion of 92% and system B gets a precision of 94%. I then claim that system B is better than system A for my task.
Give two reasons why you shouldn’t believe my claim (unless I provide further evidence or explanation).
11. Give a semantic representation for the sentence Alex watched Hamlet yesterday using first-order logic with event variables. Using this example, explain the advantage of using event variables with respect to identifying entailment relationships.
12. You are developing a question answering system that users will run on their mobile devices. The system requires parsing each query in real time. Would you choose a dependency parser or a constituency parser in this situation, and why? Also give one potential disadvantage of the system you chose.
13. Compare the following two parses. On the left is the gold standard parse, and on the right is the output of a parser.
9
[2 marks ]
[7 marks]
[3 marks ]
[3 marks ]
[3 marks ]
SS
H H H H H H
Pro VP
HH He
Pro
VP
H
V NP
HH
HH
He
V NP
saw
H H
HH H
Det Nom
saw Det
H H
HH
Nom
H
HH aHH
a AP N H Adj Adj N
H H
H
H frog
Adj Adj yellow spotted frog yellow spotted
What are the parser’s labelled precision and recall scores on this example?
14. Statement S1 below entails statement S2:
(S1) Alec scratched his chin thoughtfully. (S2) Alec scratched his chin.
Answer the following questions about these statements.
(a) Give logical meaning representations for these two sentences using reified events.
(b) Explain why using reified events makes it easier to model the entailment relation- ship, compared to a meaning representation without reified events.
(c) Give another statement that is entailed by S1, but where the entailment does not follow naturally from the logical meaning representations. How does your example illustrate a weakness of logical meaning representations?
15. Consider the sentence The boy in the shop likes reading, and answer the following questions about it.
(a) This sentence contains an agreement relationship that a trigram model cannot capture. What is it?
(b) Using examples that build on the given sentence, explain why no N-gram model (for any fixed N) is sufficient to model this type of relationship in English.
(c) Name two different models of syntax discussed in class that can capture this type of relationship. Then pick one of these, give a parse of the sentence using this type of model, and use it to explain how the agreement relationship is captured.
10
[2 marks]
[6 marks]
[7 marks]
16. Use the following sentence to answer this question.
The president arrived in Hawaii after a long trip
(a) Give the lemma for any word(s) in the sentence where the lemma is different from the word itself.
(b) Draw the dependency parse above the sentence and label each arc using Uni- versal Dependency style labels.
Then, underneath each word in the sentence, write its part of speech, using Penn Treebank style tags.
17. Use the following three very short documents to answer this question.
[5 marks]
Doc1: Doc2: Doc3:
The president arrived in Hawaii after a long trip. He rested
in a local hotel.
Hawaii is beautiful, and you should take a trip there. I can
tell you what my favorite hotel in Hawaii is.
The president announced another trip yesterday.
(a) Find two (distinct) examples in these documents that illustrate different kinds of linguistic agreement. What are the two kinds of agreement your examples illustrate and which words agree in each case?
(b) Consider the two events:
X = “Hawaii occurs in a document”
Y = “president occurs in a document”
Using MLE on the documents above, find the estimated probabilities P(X) and P (Y ) and determine whether X and Y are independent in this data. What does the answer tell us about the value of PMI(X,Y )?
(Hint: you don’t need to compute PMI(X, Y ) to answer this question.)
11
[5 marks]
18. NLP tools for historical documents. (19 marks total)
Historians and social scientists have begun to use computer-based methods to study historical documents. However, NLP tools developed on modern text have difficulty these documents because historical words may have inconsistent spellings, or spellings that differ from their modern forms. One way to address this problem is to normalize the text before doing further processing.
Here is an excerpt of a historical text (1a) and a normalized version of it (1b):
(1a) Myn adversarie is become bysshop of Cork in Irland, and ther arn ii other persones provided to the same bysshopriche yet lyvyng,
beforn my seyd adversarie; (William Paston, 1426)
(1b) My adversary has become bishop of Cork in Ireland, and there are two other persons provided to the same bishopric yet living,
before my said adversary;
And here is a simple method to normalize historical text:
Dictionary method:
1 2 3a
(a)
(b)
Look up each historical word token h in a modern dictionary.
If h appears in the dictionary, leave it as is.
Else find the dictionary word d that has the most similar spelling to h, and replace h with d.
If you implement the dictionary method above, what well-known algorithm could you use to determine how similar the spellings of each word pair are? (You do not need to explain how the algorithm works, just give its name.)
Sometimes, d will not be the right normalization for h, so the dictionary method will produce an error. A possible improvement might be:
N-best method: Follow steps 1 and 2 as above, but replace 3a with:
3b Else generate a list of the N dictionary words that are spelled most sim- ilarly to h. For each of the N words, use a logistic regression model to compute the probability that this word is the correct normalization,
and pick the most probable one.
i. Give two different types of features that would be important to include in the model, and say why.
ii. What sort of training data would you need to train your model? 12
[2 marks]
[4 marks] [2 marks]
iii. Would you also need a development set? If so, explain what you would use it for in this particular context. If not, explain why not.
(c) Describe two other types of errors that can occur with the dictionary method, which can not be solved by the N-best method. Use examples from the provided text to illustrate each type. Pick one of these error types and propose a way you could try to solve it. Discuss any new difficulties or weaknesses your method might introduce.
[2 marks]
[5 marks] Like historical text, Twitter data often contains non-standard spellings, and some researchers
have suggested normalization as a way to improve performance of downstream NLP systems.
(d) Consider the following two tweets, and imagine you are trying to get annotators to produce “normalized” versions of them.
(1) @SwizzOnaRampage lol no comment bro… can’t say if I disagree or agree. lol
(2) Really wish 1 of the #sixxtards won. Haha mayb a book? Wld b my 3rd copy. My 1st copy got worn out had to buy a new1
Give two examples of difficult annotation decisions from this data: that is, tokens where annotators might disagree about the correct normalized form unless very specific guidelines are given. For each example explain briefly why it is difficult (i.e. provide two or more alternative normalizations and say why each might be reasonable).
[4 marks]
13
19. Semantic parsing. (12 marks total) Below is a grammar that covers a tiny fragment of English. It generates sentences such as “the kids take the toys and books” and “the big kids take the toys”.
Freq Rule
8 Conj→and 12 N→kids
5 N→toys
10 N→books
Freq Rule
2 V→books
6 V→take 11 V→takes 31 Det→the
Freq Rule
16 S→NPVP
3 S→VP
7 VP→V
9 VP→VNP
3 VP→VNPNP
Freq Rule
31 NP→DetNom
4 Nom→AdjNom
8 Nom→NomConjNom
4 Adj→big
(a) Assume that the frequencies (Freq) shown next to the rules are counts from a
treebank, and answer the following questions.
i. Suppose the rules/counts provided are the complete set of rules/counts col- lected from the corpus. What are the maximum-likelihood estimated prob- abilities of the two rules VP →V NP and N →books, and what conditional probabilities do these correspond to? That is, for each rule give an expression of the form PMLE(·|·) = · where you replace the dots with the correct answers.
ii. Now suppose the grammar also contains other rules (not shown above) that may not have been observed in the treebank, and you want to apply add-alpha smoothing. Give the formula you would need to use to estimate the smoothed probability of the VP →V NP rule and say what the terms mean in this context.
(b) The provided grammar overgenerates. Give an example demonstrating this, and explain using your example how subcategorization could help to address the prob- lem. What new problem is introduced by subcategorization?
(c) Consider the following sentence, which is ambiguous under this grammar:
take the big toys and books
Suppose we are parsing this sentence using an algorithm like CKY (you can assume that the algorithm extends CKY to handle ternary rules, but is otherwise the same as CKY). Answer the following questions.
i. Draw the alternative parse trees for the sentence and put a box around the node in each parse that is at the root of the ambiguous subtree. Which location in the chart will store this node?
ii. How does the algorithm represent ambiguity in the chart while also being efficient? You should describe the information that is stored in the chart location you identified in part (i), and explain how this information is used when building higher nodes in the tree. Full details of the computation are not needed but your answer must indicate how the efficiency is achieved.
14
[3 marks]
27 Nom→N
[3 marks]
[6 marks]
20. Gmail autocomplete. (14 marks total)
Google’s Gmail service recently added a new feature. In some cases, when a user receives an email, three possible short responses are suggested. If the user clicks on one of the responses, it is copied into the reply window. (The user can then choose to add more text before sending.) This feature allows the user to avoid typing common responses.
Some example emails and suggested responses produced by the real system are shown in Figure 2 (next page). Note that suggested responses are not always provided, but if they are, there are always three options.
Imagine that it is 2016 and you are one of the employees helping to develop this system. Your boss suggests that you build a supervised text classifier to produce the desired results.
(a) Describe the following aspects of building the system.
(Note: this question is not asking for mathematical definitions or technical details of the classifier, nor is it asking you to choose a particular classifier. But you may need to say something about what kind of information the classifier must provide.)
i. How would you define the classes (labels) that this classifier needs to predict?
ii. What data is needed to train the supervised classifier and how would you obtain it?
iii. Once you have built and trained the classifier, how can you use it to produce the desired behaviour?
(b) You will need to evaluate different versions of your system during development, and eventually convince your boss that your system is worth deploying. What evaluation method(s) and approach(es) would you use to accomplish these goals, and why? Briefly discuss any weaknesses of your approach.
(c) Identify two ethical issues that should be considered when developing this system. That is, identify two aspects of developing or deploying the system that could have unintended negative consequences for individuals, groups, or society as a whole. What are the possible negative consequences and for whom?
[6 marks]
15
[5 marks]
[3 marks]
(a) Hi ***,
I just realised that I won’t be here on the 19th of Nov. So please make it the 12th of November
(b) Argh sorry, forgot the attachment – here it is!
(c) Hi ***,
You can hand it into the ITO if there’s not a servitor around. Kind regards,
***
(d) Happy New Year to you too! It was great to see you over the summer and [… long text with personal updates …]
Let us know if you will be in *** at all–it was great to re-connect in May.
Love to everyone,
***
Figure 2: Several example emails, for Question 20. In examples (a)-(c), the system’s suggested responses are shown in boxes and the user can click on one (if desired). In example (d), the system does not provide any suggested responses. Identifying details in all examples are replaced here by ***.
16
Ok, no problem.
Ok, thanks for letting me know.
Will do.
Got it, thanks!
Thank you!
Looks great!
Yes, I have one.
Sorry, I don’t have it.
I don’t, sorry.