Natural Language Processing
Assignment- 6
TYPE OF QUESTION: MCQ
Number of questions: 8 Total mark: 6X 1 + 2*2 = 10
Question 1 : Which of the following is/are False about the criteria of head (H) and
dependants (D) in a construction (C) in a dependency graph?
1. H is obligatory; D is mandatory
2. H selects D and determines whether D is obligatory
3. The form of D depends on H
4. H specifies D
Answer: 1,4
Solution: H is obligatory; D may be optional. D specifies H
Question 2. Which of the following is/are True about formal conditions on Dependency
graph G?
1. G can be cyclic
2. G is projective
3. G is disconnected
4. G obeys the rule: if i→j then not k→j, for any k not equal to i
Answer: 2, 4
Solution: G is connected and acyclic. G is projective and follows single head constraint (option
4)
Question 3: Which of the following is false?
1. Deterministic parsing requires an oracle and an oracle can be approximated by a
classifier
2. Each vertex in the graph greedily selects the incoming edge with the highest weight in
the Chu-Liu-Edmonds Algorithm
3. During the iteration of Chu-Liu-Edmonds Algorithm it never produces cycle
4. A multi-digraph is a digraph where multiple arcs between vertices are possible
Answer: 3
Solution: During the iteration of the Chu-Liu-Edmonds Algorithm it might produce cycle also.
Refer lecture 30
Question 4: Suppose you write down the sequence of actions that generate the parse
tree of the sentence “I love AI course" using Arc-Eager Parsing. The number of times you
have to use Right Arc, Left Arc, Reduce, Shift is:
Format of the answer is [a, b, c, d] corresponding to the 4 values in the order
specified in the query.
1. [3, 0, 2, 1]
2. [1, 2, 1, 3]
3. [1, 2, 0, 2]
4. [1, 2, 0, 3]
Answer: 4
Solution: Please refer lecture
Question 5: Correct sequence of actions that generates the parse tree of the sentence “I
love AI course” using Arc-Eager Parsing is:
Note: Right Arc (RA), Left Arc(LA), Reduce(RE), Shift(SH)
1. SH->LA->SH->RE->LA->RA
2. SH->LA->SH->SH->LA->RA
3. SH->LA->SH->RE->LA->RA
4. SH->LA->SH->SH->RA->LA
Answer: 2
Solution: Solve by arc-eager parsing, Refer lecture 29
Question 6: Consider the following graph with a root node and 3 other vertices. I had
drawn and put initial edge weights between all the pair of modes at night as shown below.
In the morning, my little brother added one (1) to each of the edge weight and said now the
edge weight looks good. Suppose you use Chu-Liu-Edmonds algorithm to find the MST
for the modified edge weighted graph by my brother. Which pair of nodes will have to be
contracted in the modified edge weighted graph to form a single vertex during the
algorithm in the 1st iteration?
1. (V1, V2)
2. (V2, V3)
3. (V1, V3)
4. (ROOT, V1)
Answer: 1
Solution: Solve by applying Chu-Liu-Edmonds Algorithm
Question 7: Suppose you are training MST Parser for dependency and the sentence, “I
like offline exam” occurs in the training set. The POS tags for these words are Pronoun,
Verb, PropNoun and Noun, respectively. Also, for simplicity, assume that there is only
one dependency relation, “rel”. Thus, for every arc from word wi to wj, your features may
be simplified to depend only on words wi and wj and not on the relation label.
Below is the set of features
f1: pos(wi) = Verb and pos(wj) = Noun|Pronoun
f2: wi = Root | wi occurs before wj in the sentence
f3: wi = Root and pos(wj) = Verb
f4: wj occurs before wi in the sentence
The feature weights before the start of the iteration are: [6,19,15,12]
Suppose you are also given that after applying the Chu-Liu Edmonds, you get the
following parse tree {Root → like, like → I, I → offline, offline → exam}
What would be the weights after this iteration?
1. [7, 19, 14, 13]
2. [7, 18, 15, 13]
3. [6, 19, 13, 13]
4. [6, 19, 15, 12]
Answer: 2
Solution: Please refer lecture 30
Question 8: Assume that you are learning a classifier for the data-driven deterministic
parsing and the sentence ‘I love ML course’ is a gold-standard parse in your training
data. You are also given that ML and ‘course’ are ‘Nouns’, ‘I’ is a ‘Pronoun’ while the POS
tag of ‘love’ is ‘Verb’. Find the dependency graph for this sentence below. Assume that
your features correspond to the following conditions:
1. The stack is empty.
2. Top of stack is Noun and Top of buffer is Verb.
3. Top of stack is Pronoun and Top of buffer is Verb.
4. The word at the top of stack occurs before word at the top of the buffer in the
sentence
The initial weights of your features are
[2,2,2,2 | 3,3,3,2| 2,2,2,2 | 2,2,2,2] where the first four features correspond to LA, and then
to RA, SH and RE, respectively
Use this gold standard parse during online learning. What will be the weights after
completing two iteration of Arc-Eager parsing over this sentence:
1. [2,2,2,2 | 3,3,3,2| 2,2,2,2 | 2,2,2,2]
2. [2,2,3,2 | 2,3,2,1| 3,2,2,2 | 2,2,2,2]
3. [2,2,3,3 | 3,3,2,1| 3,2,2,2 | 2,2,2,2]
4. [2,2,3,3 | 2,3,2,1| 3,2,2,2 | 2,2,2,2]
Answer: 4
Solution: Refer lecture 29 of week 6
