Natural Language Processing

Assignment- 1
TYPE OF QUESTION: MCQ
Number of questions: 10 Total mark: 10 X 1 = 10

____________________________________________________________________________

Question 1:

In a corpus, you found that the word with rank 4th has a frequency of 250. What can
be the best guess for the rank of a word with frequency 125?

1. 2
2. 4
3. 8
4. 6

Answer: 3

Solution:
frequency * rank =k [by Zipfs law]
250*4 = 125*r
r=8

____________________________________________________________________________

Question 2:

In the sentence, “In Delhi I took my hat off. But I can’t put it back on.”, total number of
word tokens and word types are:
1. 14, 13
2. 13, 14
3. 15, 14
4. 14, 15
Answer: a) 14, 13.
Solution: Here, the word “I” is repeated two times so type count is
one less than token count.

____________________________________________________________________________
Question 3:

Let the rank of two words, w1 and w2, in a corpus be 1600 and 100,
respectively. Let m1 and m2 represent the number of meanings of w1 and w2
respectively. The ratio m1 : m2 would tentatively be
1. 1:4
2. 4:1
3. 1:2
4. 2:1
Answer: 1

Solution:
m1/m2 = sqrt(rank2)/sqrt(rank1) = sqrt(100)/sqrt(1600) = 1:4

____________________________________________________________________________

Question 4:

What is the valid range of type-token ratio of any text corpus?

1. TTR∈(0,1] (excluding zero)

2. TTR∈[0,1]
3. TTR∈[−1,1]
4. TTR∈[0,+∞] (any non-negative number)

Answer: 1.
Solution: Number of unique words or type ≤ Total number of tokens in text, and both are greater
than 1

____________________________________________________________________________
Question 5:

If first corpus has 𝑇𝑇𝑅1 = 0.06 and second corpus has 𝑇𝑇𝑅2 = 0.105, where 𝑇𝑇𝑅1 and 𝑇𝑇𝑅2
represents type/token ratio in first and second corpus respectively, then

1. First corpus has more tendency to use different words.

2. Second corpus has more tendency to use different words.
3. Both a and b
4. None of these

Answer: b
Solution: Second corpus has more tendency to use different words. If TTR scores are higher
then there is more tendency to use different words.
____________________________________________________________________________

Question 6:

Which of the following is/are true for the English Language?

1. Lemmatization works only on inflectional morphemes and Stemming works only on

derivational morphemes.
2. The outputs of lemmatization and stemming for the same word might differ.
3. Output of lemmatization are always real words
4. Output of stemming are always real words

Answer: 2, 3
Solution: Stemming usually refers to a crude heuristic process that chops off the ends of words
in the hope of achieving this goal correctly most of the time, and often includes the removal of
derivational affixes. Lemmatization usually refers to doing things properly with the use of a
vocabulary and morphological analysis of words, normally aiming to remove inflectional endings
only and to return the base or dictionary form of a word, which is known as the lemma .

Question 7:

An advantage of Porter stemmer over a full morphological parser?

1. The stemmer is better justified from a theoretical point of view
2. The output of a stemmer is always a valid word
3. The stemmer does not require a detailed lexicon to implement
4. None of the above

Answer: 3
Solution: The Porter stemming algorithm is a process for removing suffixes from words in
English. The Porter stemming algorithm was made on the assumption that we don’t have a stem
dictionary (lexicon) and that the purpose of the task is to improve Information Retrieval
performance. Stemming algorithms are typically rule-based. You can view them as a heuristic
process that sort-of lops off the ends of words.

____________________________________________________________________________

Question 8:

Which of the following are not instances of stemming? (as per Porter Stemmer)

1. are -> be
2. plays -> play
3. saw -> s
4. university -> univers

Answer: 1, 3
Solution: Stemming cannot convert are->be as it can only convert or chop off word suffixes.
Also Porter Stemmer wouldn’t chop off if the final outcome is of length 1 as in saw -> s.
____________________________________________________________________________

Question 9:
What is natural language processing good for?
1. Summarize blocks of text
2. Automatically generate keywords
3. Identifying the type of entity extracted
4. All of the above

Answer: 4

Solution:
For all the above-mentioned task, NLP can be used
____________________________________________________________________________
Question 10:

What is the size of unique words in a document where total number of words =
12000. K = 3.71 Beta = 0.69?

1. 2421
2. 3367
3. 5123
4. 1529

Answer: 1

Solution: 3.71 x 12000^0.69 = 2421 unique words. Heap’s Law

____________________________________________________________________________
************END*******
 Natural Language Processing
Assignment- 2
TYPE OF QUESTION: MCQ
Number of questions: 10 Total mark: 10 X 1 = 10
______________________________________________________________________________

QUESTION 1:
According to Zipf’s law which statement(s) is/are correct?
(i) A small number of words occur with high frequency.
(ii) A large number of words occur with low frequency.
a. Both (i) and (ii) are correct
b. Only (ii) is correct
c. Only (i) is correct
d. Neither (i) nor (ii) is correct
Correct Answer: a
Solution:

____________________________________________________________________________
QUESTION 2:
Consider the following corpus C1 of 4 sentences. What is the total count of unique bi-grams for
which the likelihood will be estimated? Assume we do not perform any pre-processing.

tomorrow is Sachin’s birthday

He loves cream chocolates
he is also fond of sweet cake
we will celebrate his birthday with sweet chocolate cake

today is Sneha’s birthday

she likes ice cream
she is also fond of cream cake
we will celebrate her birthday with ice cream cake

a. 24
b. 28
c. 27
d. 23

Correct Answer: a

Detailed Solution:
Unique bi-grams are:
<s> tomorrow tomorrow is is Sachin’s Sachin’s birthday birthday <\s>
<s> he he loves loves cream cream chocolates chocolates <\s>
he is is also also fond fond of of sweet
cake <\s>
<s> we we will will celebrate celebrate his
his birthday birthday with with sweet chocolate cake
______________________________________________________________________________

QUESTION 3:
A 4-gram model is a ___________ order Markov Model.

a. Two
b. Five
c. Four
d. Three
Correct Answer: d

Detailed Solution:

______________________________________________________________________________

QUESTION 4:

Which of these is/are - valid Markov assumptions?

a. The probability of a word depends only on the current word.

b. The probability of a word depends only on the previous word.

c. The probability of a word depends only on the next word.

d. The probability of a word depends only on the current and the previous word.

Correct Answer: b

Solution:

______________________________________________________________________________

QUESTION 5:
For the string ‘mash’, identify which of the following set of strings has a Levenshtein distance of
1.

a. smash, mas, lash, mushy, hash

b. bash, stash, lush, flash, dash
c. smash, mas, lash, mush, ash
d. None of the above

Correct Answer: c

Detailed Solution:

______________________________________________________________________________
QUESTION 6:
Assume that we modify the costs incurred for operations in calculating Levenshtein distance,
such that both the insertion and deletion operations incur a cost of 1 each, while substitution
incurs a cost of 2. Now, for the string ‘clash’ which of the following set of strings will have an
edit distance of 1?

a. ash, slash, clash, flush

b. flash, stash, lush, blush,
c. slash, last, bash, ash
d. None of the above

Correct Answer: d

Detailed Solution:

____________________________________________________________________________

QUESTION 7:
Given a corpus C2, the Maximum Likelihood Estimation (MLE) for the bigram “dried berries” is
0.45 and the count of occurrence of the word “dried” is 720. For the same corpus C2, the likelihood
of “dried berries” after applying add-one smoothing is 0.05. What is the vocabulary size of C2?

a. 4780
b. 3795
c. 4955
d. 5780

Correct Answer: d

Detailed Solution:

0.45 = C(dried, berries) / 720

C(dried, berries) = 720*0.45 = 324

0.05 = (324+1) / (720+V)

V=5780
_____________________________________________________________________________
For Question 8 to 10, consider the following corpus C3 of 3 sentences.
there is a big garden
children play in a garden
they play inside beautiful garden

QUESTION 8:
Calculate P(they play in a big garden) assuming a bi-gram language model.
a. 1/8
b. 1/12
c. 1/24
d. None of the above

Correct Answer: b

Detailed Solution:

P(they | <s> ) = 1/3

P(play | they) = 1/1
P(in | play) = 1/2
P(a | in) = 1/1
P(big | a) = 1/2
P(garden | big) = 1/1
P(<\s>|garden) = 3/3
P(they play in a big garden) = 1/3 x 1/1 x 1/2 x 1/1 x 1/2 x 1/1 x 3/3 = 1/12
______________________________________________________________________________

QUESTION 9:
Considering the same model as in Question 7, calculate the perplexity of <s> they play in a big
garden <\s>.

a. 2.289
b. 1.426
c. 1.574
d. 2.178

Correct Answer: b

Detailed Solution:

______________________________________________________________________________
QUESTION 10:
Assume that you are using a bi-gram language model with add one smoothing. Calculate P(they
play in a beautiful garden).

a. 4.472 x 10^-6
b. 2.236 x 10^-6
c. 3.135 x 10^-6
d. None of the above

Correct Answer: b

Detailed Solution:

|V|=11
P(they | <s> ) = (1+1)/(3+11)
P(play | they) = (1+1)/(1+11)
P(in | play) = (1+1)/(2+11)
P(a | in) = (1+1)/(1+11)
P(beautiful | a) = (0+1)/(2+11)
P(garden | beautiful) = (1+1)/(1+11)
P(<\s>|garden) = (3+1)/(3+11)
P(they play in a beautiful garden) = 2/14 x 2/12 x 2/13 x 2/12 x 1/13 x 2/12 x 4/14
= 2.236 x 10^-6

____________________________________________________________________________

************END*******
 Natural Language Processing
Assignment- 3
TYPE OF QUESTION: MCQ
Number of questions: 7 Total mark: 10 (Q5, Q6, Q7 carries two marks each)

Question 1:

Which of the following words contains both derivational and inflectional suffixes?

1. happiness
2. quicker
3. enjoyment
4. responsibilities

Answer: 4

Solution:
Responsibilities = respons(e) (Root word) + ible (derivational suffix) + ity (derivational suffix) +
es (inflectional suffix).

Question 2:

Let's assume the probability of flipping heads two times in a row with a fair coin
is q. Consider a sentence consisting of M random binary digits (0s and 1s). A
model assigns probability to each digit in the sentence using the probability q.
What is the perplexity of the sentence?

1. 2
2. 4
3. 8
4. 16

Answer: 2

Solution: The probability of flipping heads two times in a row is q=1/2×1/2=¼

Then perplexity is ((1/4)^M)^-1/M = 4
Question 3:
Assume that “x” represents the input and “y” represents the tag/label. Which of the
following mappings are correct?

1. Generative Models - learn Joint Probability p(x, y)

2. Discriminative Models - learn Joint Probability p(x, y)
3. Generative Models - learn Posterior Probability p(y | x) directly
4. Discriminative Models - learn Posterior Probability p(y | x) directly

Answer: 1, 4
Solution: Generative classifiers learn a model of the joint probability p(x, y) and make their
predictions by using Bayes rules to calculate p(y | x). Discriminative classifiers model the
posterior p(y | x) directly, or learn a direct map from inputs x to the class labels y.

Question 4.

Natural language processing is essentially the study of the meaning of the words a
human says or writes. Natural language processing is all around us all the time, but it
also happens to be a way to improve the chatbot or product we interact with on a regular
basis. Natural language processing is all about mimicking our own language patterns.
Natural language processing can also improve the efficiency of business transactions
and customer care. Natural language processing is the application of computer
technology.

Suppose we want to check the probabilities of the final words that succeed the string language
processing in the above paragraph. Assume d= 0; it is also given that no of unigrams = 78, no of
bigrams = 122, no of trigrams = 130,, Question 6 and Question 7 are related to Question 5
corpus.

Solve the question with the help of Kneser-Ney backoff technique.

What is the continuation probability of “is” ?

1. 0.0078
2. 0.0076
3. 0.0307
4. 0.0081

Answer: 2

Solution: Refer week 3 lecture 12

Continuation probability of is = 1/130 = 0.0076

The numerator means the number of different string types preceding the final word, (here only 1

type– language processing is) and the denominator means the number of different possible n-

gram types , in this case trigram = 130

Question 5:
What will be the value of P(is| language processing) using Kneser-Ney backoff technique
and choose the correct answer below. . Please follow the paragraph in Question .

1. 0.5
2. 0.6
3. 0.8
4. 0.7

Answer: 3

Solution: Refer week 3 lecture 12

P(is| language processing) = ⅘ + 0*0.0076 = 0.8 [as d=0 so lambda = 0]

In this example is equal to the frequency of language processing *: the frequency of language

processing is (here it occurs 4 times) plus the frequency of language processing can (occurs

only once). Therefore, for word is, firstTerm(is) = 4/(4+1) = 0.8

Question 6.
What is the value of P(can| language processing)? Please follow the paragraph in
Question 5

1. 0.1
2. 0.02
3. 0.3
4. 0.2
Answer: 4

Solution: Refer week 3 lecture 12

Similarly P(can| language processing) = ⅕ + 0*Continuation probability = 0.2

Language processing * occurs 5 times, language processing can occur only once.

Question 7:
Consider the HMM given below to solve the sequence labeling problem of POS tagging.
With that HMM, calculate the probability that the sequence of words “free workers” will be
assigned the following parts of speech;

VB NNS

free workers

JJ 0.00158 0

NNS 0 0.000475

VB 0.00123 0

VBP 0.00081 0

VBZ 0 0.00005

The above table contains emission probability and the figure contains transition
probability

1. 4.80 * 10-8
2. 9.80 * 10-8
3. 3.96 * 10-7
4. 4.96 * 10-8
Answer: 4
Solution:

P(free workers, VB NNS)

= P(VB|start) * P(free|VB) * P(NNS|VB) * P(workers|NNS)

* P(end|NNS)

= 0.25 * 0.00123 * 0.85 * 0.000475 * 0.4

= 4.96 * 10-8
 Natural Language Processing
Assignment 4
Type of Question: MCQ
Number of Questions: 7 Total Marks:(4×1)+(3×2)=10

=====================================================

1.

Baum-Welch algorithm is an example of - [Marks 1]

A) Forward-backward algorithm
B) Not a case of the Expectation-maximisation algorithm
C) Both A and B
D) None

Answer: A

Solution: Theory.

=====================================================
2. Marks 2

Once a day (e.g. at noon), the weather is observed as one of state 1: rainy state 2:
cloudy state 3: sunny The state transition probabilities are :

Given that the weather on day 1 (t = 1) is sunny (state 3), what is the probability that
the weather for the next 7 days will be “sun-sun-rain-rain-sun-cloudy-sun”?

A) 1.54 * 10-4
B) 8.9 * 10-2
C) 7.1 * 10-7
D) 2.5 * 10-10
Answer: A

Solution:
O = {S3, S3, S3, S1, S1, S3, S2, S3}
P(O | Model)
= P(S3, S3, S3, S1, S1, S3, S2, S3 | Model)
= P(S3) P(S3|S3) P(S3|S3) P(S1|S3) P(S1|S1) P(S3|S1) P(S2| S3)
P(S3|S2) = Q3 · a33 · a33 · a31 · a11 · a13 · a32 · a23
= (1)(0.8)(0.8)(0.1)(0.4)(0.3)(0.1)(0.2)
= 1.536 × 10-4

=====================================================
3.

In the question 2, the expected number of consecutive days of sunny weather is:
A) 2
B) 3
C) 4
D) 5

[Marks 1]

Answer: D

Solution:
Exp(i) = 1/(1-pii) So for rainy, the expected no of days = 1/(1-0.8) = 5

=====================================================

4. [Marks 2]

You are building a model distribution for an infinite stream of word tokens. You know
that the source of this stream has a vocabulary of size 1200. Out of these 1200
words you know of 200 words to be stop words each of which has a probability of
0.001. With only this knowledge what is the maximum possible entropy of the
modelled distribution. (Use log base 10 for entropy calculation)

A) 2.079
B) 4.5084
C) 2.984
D) 3.0775

Answer: D

Solution: There are 200 stopwords with each having an occurrence probability
of 0.001. Hence,
P(Stopwords) = 200 ∗ 0.001 = 0.2
P(non − stopwords) = 1 − 0.2 = 0.8

For maximum entropy, the remaining probability should be uniformly distributed.

For every non-stopword w, P(w) = 0.8/(1200 − 200) = 0.8/1000 = 0.0008. Finally,
the value of the entropy would be,
H = E(log(1/p))
= −200(0.001 ∗ log(0.001)) − 1000(0.0008 log(0.0008))
= −200(0.001 ∗ (-3)) − 1000(0.0008 * (-3.0969))
= 0.6 + 2.4775
= 3.0775
=====================================================

5. [Marks 1]

Suppose you have the input sentence “Sachin is a great cricketer”.

And you know the possible tags each of the words in the sentence can take.
• Sachin: NN, NNS, NNP, NNPS
• is: VB
• a: DT
• great: ADJ
• cricketer: NN, NNS, NNP
How many possible hidden state sequences are possible for the
above sentence and States?

A) 4 × 3 × 3
B) 3 × 4
C) 24 × 23 × 23
D) 3 × 42

Answer: B

Solution: Each possible hidden sequence can take only one POS tag for each of the
words. Hence the total possibility will be a product of the number of candidates for
each word.

=====================================================

6.

[Marks 1]

What are the time and space complexity order of the Viterbi algorithm? K is the
number of states and N number of time steps.

A) KN, K2N
B) K2N, KN
C) K2N, K2N
D) KN, KN

Answer: B

Solution: The sum-product algorithm is polynomial. The time complexity is

O(K2N), the space complexity is O(KN), where K is the number of states and N
number of time steps.

=====================================================

7.

[Marks 2]

Mr. X is happy someday and angry on other days. We can only observe when he
smiles, frowns, laughs, or yells but not his actual emotional state. Let us start on
day 1 in a happy state. There can be only one state transition per day. It can be
either a happy state or an angry state. The HMM is shown below-
Assume that qt is the state on day t and ot is the observation on day t. Answer the
following questions;

What is P(o2 = frown)?

A) 0.56
B) 0.18
C) 0.03
D) 0.78

Answer: B
Solution: We need to find the probability of observation frown on day 2. But we don’t
know whether he is happy or not on day 2 (we know he was happy on day 1). Hence,
the probability of the observation is the sum of products of observation probabilities
and all possible hidden state transitions.

P(o2 = frown) = P(o2 = frown | q2 = Happy) + P(o2 = frown | q2 = Angry)

= P(Happy | Happy)* P(frown | Happy) + P(Angry | Happy)* P(frown | Angry)

= (0.8 * 0.1) + (0.2 * 0.5) = 0.08 + 0.1 = 0.18

 Natural Language Processing
Assignment 5
Type of Question: MCQ

Number of Questions: 8 Total Marks: (6×1)+(2×2)=10

================================================================

Question 1.
Which of the following are true?
A) Given a CFG and its corresponding CNF, they produce different languages.
B) It requires ‘2n-1’ productions or steps in CNF to generate a string w of length
‘n’.
C) For a given grammar, there can be one CNF.
D) All of the above
Answer: B
Solution: Given a CFG and its corresponding CNF, they produce the same
language.
Let n be the length of a string. We start with the (non-terminal) symbol S which has
length n=1. Using (n−1) rules of form NT→NT NT (where NT represents a
non−terminal) we can construct a string containing ‘n’ non-terminal symbols. Then on
each NT symbol of said string of length ‘n’ we apply a rule of form NT→T. i.e. we
apply n rules. In total we will have applied
(n−1) + n = 2n−1 rules.

================================================================

Question 2.
Consider the CFG given below:
S → xSy|V
V → Vz|ϵ
How many non-terminals should be added to convert the CFG into CNF?
A) 2
B) 4
C) 5
D) 3

Answer: C
Solution: The final CNF is:
S′ → AE|AB|VC|z
S → AE|AB|VC|z
E → SB
V → VC|z
A→x
B→y
C→z

===============================================================

Question 3:
the CFG to CNF converted form?​
In the above Q. 2) How many different numbers of Null productions in
A) 0
B) 1
C) 2
D) 3

A) 2
B) 4
C) 7
D) 10

Answer: C (7)

Please check the Q. 2. Solution

================================================================
For Question 5 to 7 consider the following PCFG fragment:

S → NN VP ​ 0.50​ S → VP NN ​ ​ 0.50
NP → NN PB ​ 0.40 P B → PP NN 0.30
V P → VB NN 0.30 V P → VB NP ​ 0.20
V P → NN VB 0.25 V P → NN PB ​ 0.15
P P → with ​​ 0.10 P P → without 0.10
V B → play ​​ 0.30 V B → enjoy/like 0.20
 V B → watch/enjoy ​ 0.25 NN → children/students ​ 0.15
NN → cricket/football 0.15 NN → friends ​ 0.20
NN → football/cricket​ 0.10 NN → music/painting​ 0.12

For a sentence S = w1w2w3w4, assume that the cells in the table are indexed as
follows:

Question 5:
Using CKY algorithm, find the probability score for the most probable tree for the
sentence S1 = “students play football with friends”.
A) 6.06 × 10−4
B) 1.62 × 10−6
C) 2.73 × 10−3
D) 4.33 × 10−6
Answer: B
Solution: Calculate the probability using the Bottom-Up method as explained in the
lecture. 2

================================================================\

Question 6:
Using CKY algorithm, find the number of parse trees for the sentence S2 = students
like painting and the probability score for “at least one of the probable trees”.

A) 1, 4.95 × 10−3
B) 3, 0.36 × 10−3
C) 2, 0.99 × 10−3
D) 2, 0.54 × 10−3

Answer: C
Solution:
There are two parse trees.
S → NN11 VP23 = 0.5 × 0.15 × (0.3 × 0.2 × 0.12) = 0.54 × 10−3
S → VP12 NN33 = 0.5 × (0.25 × 0.15 × 0.2) × 0.12 = 0.45 × 10−3

Total is sum of both of the above = 0.54 × 10−3 + 0.45 × 10−3 = 0.99 × 10−3

We get the above probabilities with the CKY algorithm.

================================================================

Question 7:
Consider the expression below:
P(“students enjoy cricket like painting”, N34|G) = Pj P(“students enjoy cricket like
painting” |Nj34, G)
What does the L.H.S. represent?

A) Probability of the sentence “students enjoy cricket like painting”, given a

grammar G.
B) Probability of the sentence “students enjoy cricket like painting”, given a
grammar G and that there is some consistent spanning of the segment
“cricket like”, i.e. from word 3 to 4.
C) Probability of the sentence “students enjoy cricket like painting”, given a
grammar G and some rule which derives the segment “cricket like”.
D) None of the above

Answer: B
Solution: Refer to Inside-Outside Probabilities.

================================================================

Question 8:
Which of the following grammars are valid CNF?

1. a) A → B 2. A → BCD 3. A → BC
b) B → CD B → b B → ϵ
c) C → c C → c C → c
d) A → BC A → a

2. a
3. b
4. c
5. D
6. None

Answer: d
Solution: Valid CNF form is as follows:
A → BC
A→a

A non-terminal generating a terminal or A non-terminal generating two non-terminals

================================================================
 Natural Language Processing
Assignment- 6
TYPE OF QUESTION: MCQ
Number of questions: 8 Total mark: 6*1 + 2*2 = 10 [Q7, Q8 Carries two marks each]

Question 1.
With respect to a Dependency Structure, which of the following is not a valid criterion for
a syntactic relation between a head H and a dependent D in a construction C?

1. H determines the syntactic category of C

2. The form of H depends on D.
3. H selects D and determines whether D is obligatory.
4. The linear position of D is specified with reference to H

Answer: 2
Solution: Explained in Lecture 27.

Solution: The size of the feature vector for any configuration always depends on no. of features
defined and no. of possible oracle transitions. Refer transition based parsing lecture

Question 2:
Which of the following is False about formal conditions of dependency graph?

1. Syntactic structure is hierarchical

2. Some word can have more than one syntactic head
3. There should not be any crossing of dependencies
4. Syntactic structure is complete

Answer: 2

Solution:

Refer lecture 27 of week 6

Question 3:
Which of the following condition is false about directed spanning tree?
A directed spanning tree of a (multi-) digraph G = (V, A) is a subgraph G’ = (V’, A’) such
that :
1. V’ = V
2. A’ is subset of A
3. |A’| = |V’| -1
4. G’ is cyclic

Answer: 4

Solution: G’ should be acyclic. Refer to lecture 30 of week 6

Question 4:

Consider the following graph with a root node and 3 other vertices. The edge weights
between all the pair of modes have been provided. Suppose you use Chu-Liu-Edmonds
algorithm to find the MST for this graph. Which pair of nodes will have to be contracted
to form a single vertex during the algorithm in the 1st iteration?

1. (V2, V3)
2. (V1, V3)
3. All these pairs will get contracted at different times in the algorithm
4. (V1, V2)

Answer: 4
Solution: Solve by applying Chu-Liu-Edmonds Algorithm
V1→V2 having maximum weights, so in the first iteration this pair of nodes will be contracted
Question 5:
Suppose you write down the sequence of actions that generate the parse tree of the
sentence “I prefer NLP 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, 3]
4. [1, 2, 0, 2]

Answer: 3
Solution: Solve by arc-eager parsing, Refer lecture 29

Question 6:
Correct sequence of actions that generates the parse tree of the sentence “I prefer NLP
course” using Arc-Eager Parsing is:
Note: Right Arc (RA), Left Arc(LA), Reduce(RE), Shift(SH)

1. SH->LA->SH->SH->LA->RA
2. SH->LA->SH->RE->LA->RA
3. SH->LA->SH->SH->RA->LA
4. SH->LA->RE-->SH->SH->LA

Answer: 1

Solution: Solve by arc-eager parsing, Refer lecture 29

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: [5,20,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. [6, 19, 14, 13]

2. [6, 19, 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 prefer NLP course’ is a gold-standard parse in your training data. You are
also given that NLP and ‘course’ are ‘Nouns’, ‘I’ is a ‘Pronoun’ while the POS tag of
‘prefer’ is ‘Verb’. Obtain the dependency graph for this sentence on your own. 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 | 2,3,2,1| 3,2,2,2 | 2,2,2,2]
4. [2,2,3,3 | 3,3,2,1| 3,2,2,2 | 2,2,2,2]

Answer: 3
Solution: Refer lecture 29 of week 6
 Natural Language Processing
Assignment 7
Type of Question: MCQ

Number of Questions: 7

===================================================

Question 1: [1 mark]

Suppose you have a raw text corpus and you compute word co-occurrence matrix
from there. Which of the following algorithm(s) can you utilize to learn word
representations? (Choose all that apply)

a. CBOW
b. SVD
c. PCA
d. GloVe

Answer: a, b, c, d
Solution:

===================================================

Question 2: [1 mark]

What is the method for solving word analogy questions like, given A, B and D, find C
such that A:B::C:D, using word vectors?

a. vc = va + (vb − vd), then use cosine similarity to find the closest word of vc.

b. vc = va + (vd − vb) then do dictionary lookup for vc

c. vc = vd + (va − vb) then use cosine similarity to find the closest word of vc.
d. vc = vd + (va − vb) then do dictionary lookup for vc.
e. None of the above

Answer: c
Solution: vd − vc = vb − va
vc = vd + va − vb then use cosine similarity to find the closest word of vc.
===================================================

Question 3: [1 mark]

What is the value of PMI(w1, w2) for C(w1) = 100, C(w2) = 2500, C(w1, w2) = 320, N =
50000? N: Total number of documents.
C(wi): Number of documents, wi has appeared in.
C(wi, wj ): Number of documents where both the words have appeared in.
Note: Use base 2 in logarithm.

a. 4
b. 5
c. 6
d. 5.64

Answer: c

Solution:

PMI = log2 [(320*50000) / (100*2500)] = log2(64) = 6

===================================================
Question 4: [2 marks]

Given two binary word vectors w1 and w2 as follows:

w1 = [1010011010]
w2 = [0011111100]
Compute the Dice and Jaccard similarity between them.

a. 6/11, 3/8
b. 10/11, 5/6
c. 4/9, 2/7
d. 5/9, 5/8
Answer: a
Solution:

===================================================

Question 5: [2 marks]

Consider two probability distributions for two words be p and q. Compute their
similarity scores with KL-divergence.
p = [0.20, 0.75, 0.50]
q = [0.90, 0.10, 0.25]
Note: Use base 2 in logarithm.

a. 4.704, 1,720
b. 1.692, 0.553
c. 2.246, 1.412
d. 3.213, 2.426

Answer: c
Solution:

===================================================
Question 6: [2 marks]

Consider the following word co-occurrence matrix given below. Compute the cosine
similarity between
(i) w1 and w2, and (ii) w1 and w3.

w4 w5 w6
w1 2 8 5
w2 4 9 7
w3 1 2 3

a. 0.773, 0.412
b. 0.881, 0.764
c. 0.987, 0.914
d. 0.897, 0.315

Answer: c
Solution:

Cosine-sim (w1, w2) = (2*4 + 8*9 + 5*7) / (√(2*2 + 8*8 + 5*5) * √(4*4 + 9*9 + 7*7)) =
0.987
Cosine-sim (w1, w3) = (2*1 + 8*2 + 5*3) / (√(2*2 + 8*8 + 5*5) * √(1*1 + 2*2 + 3*3)) =
0.914

===================================================

Question 7: [1 marks]

Which of the following types of relations can be captured by word2vec (CBOW or

Skipgram)?
 1. Analogy (A:B::C:?)
2. Antonymy
3. Polysemy
4. All of the above

Answer: 1
Solution: Word vectors learnt using CBOW or Skipgram models can’t
disambiguate between Antonyms or Polysemous words.

===================================================
 Natural Language Processing
Assignment- 8
TYPE OF QUESTION: MCQ

Number of Questions: 9 [Question 4 carries 2 marks] Total Marks: 10

Question 1:

Consider the following statements. Which of the following is/are True?

1. Car is a hyponym of vehicle.

2. Flower is a hypernym of rose.
3. Vehicle is a hyponym of car.
4. Tulip is a hypernym of flower.

Answer: 1, 2

Question 2:

Which of the following is False?

1. Hypernym: From concepts to superordinates

2. Hyponym: From concepts to subtypes
3. Troponym: From verbs to the verbs they entail
4. Part Meronym: From wholes to parts

Answer: 3

Solution: Refer to Week 8 Lecture 37

 Question 3:
Two concepts along with their glosses are given below. Find the similarity score
between concepts “book” and “novel” using the Extended Lesk’s algorithm. (Note:
Do not consider the stop words.)

book: a set of written or printed pages bound together

novel: a long written work of fiction bound in pages

1. 2
2. 3
3. 5
4. 8

Answer: 2
Solution:
Common words are: written, pages, bound
Score = 1^2 + 1^2 + 1^2 =3
 For Question 4 to 6, consider a hypothetical wordnet noun taxonomy with their
information content as shown in Figure 1. Question 4 carries 2 marks
Note: Use base 10 in logarithmic calculations

Question 4:
What is the Lin similarity between house and design?
a. 0.564
b. 0.433
c. 0.466
d. 0.473

Answer: d
Solution: (2×4.7)/(11.09+8.75) ≈ 0.473
 Question 5:
What is the Resnic similarity between building and door?
a. 11.09
b. 8.30
c. 9.23
d. 4.70

Answer: b
Solution:

Question 6:
What is the Leacock–Chodorow similarity between building and design?
a. 0.398
b. 0.699
c. 0.097
d. None of the above

Answer: a

Solution:
LC similarity = −log pathlen(c1,c2)/2d = −log 4/(2×5) ≈ 0.398
For Question 7 to 9 consider the network of words for disambiguation of the word “light”
as shown in Figure 3. The hubs are “colors” and “lamps”. Note: Take the distance between
two words as the path length between them.

Question 7:
Compute the scores for (i) the hub “colors” and the component “white” and (ii) the hub
“colors” and the component “fixtures”.
a. 0.2, 0.25
b. 1.0, 0.0
c. 0.5, 0.25
d. None of the above

Answer: d
Solution:
(i) 1/(1+1) = 0.5
(ii) 0 as “colors” is not an ancestor of “fixtures”
Question 8:
What are the scores of the hubs “colors” and “lamps” respectively?

a. 0.6, 0.4
b. 0.20, 0.33
c. 2.5, 1.5
d. None of the above

Answer: c
Solution: Each component’s score is 0.5
Question 9:
Which is the most appropriate sense for the word “light”?

a. colors
b. lamps
c. both colors and lamps are appropriate
d. Not enough data

Answer: a
Solution: “colors” has the highest score
 Natural Language Processing
Assignment- 9
TYPE OF QUESTION: MCQ
Number of questions: 7 Total mark: 10 [4*1 + 3*2] (Q5, Q6, Q7 carries two marks each )

Question 1.

Which of the following is false?

1. Dirchlet distribution is an exponential family distribution

2. LDA is a generative model
3. Dirchlet distribution is taken over the simplex i.e positive vectors that sum to one
4. A higher value of alpha will assign fewer topics to each document whereas a high value
of alpha will have the opposite effect.

Answer : 4
Solution : Refer to Lecture 43 of Week 9

Question 2:

In Topic modeling which hyperparameters tuning used to represent document-topic

Density?
1. Dirichlet hyperparameter Beta
2. Dirichlet hyperparameter alpha
3. Number of Topics (K)
4. None of them

Answer: 2

Solution:
alpha is used to represent document-topic intensity

Question 3:
You have a topic model with the parameters α = 0.8 and β = 0.03. Now, if you want to have
sparser distribution over words and denser distribution over topics, what should be the
values for α and β?
1. Both α and β values should be decreased
2. Both α and β values should be increased
3. α should be decreased, but β should be increased
4. α should be increased, but β should be decreased

Answer: 4

Solution:
α : topic distribution
β : word distribution

Question 4 :

In Gibbs sampling choose the correct option from below

1. It can not directly estimate the posterior distribution over z
2. It is a form of Markov chain Monte Carlo
3. Here sampling is done in parallel
4. Sampling is stopped before sampled values approximate the target distribution

Answer: 2

Solution:
In gibbs sampling, we do sequential sampling until the sampled values approximate the target
distribution. This also can directly estimate the posterior distribution over z

For question 5 , 6 and 7 use the following information.

Suppose you are using Gibbs sampling to estimate the distributions, θ and β for topic
models. The underlying corpus has 3 documents and 5 words, {machine, learning, language,
nature, vision} and the number of topics is 2. At certain point, the structure of the documents
looks like the following
Doc1: nature(1) language(1) vision(1) language(1) nature(1) nature(1) language(1) vision(1)
Doc2: nature(1) language(1) language(2) machine(2) vision(1) learning(2) language(1)
nature(1)
Doc3: machine(2) language(2) learning(2) language(2) machine(2) machine(2) learning(2)
language(2)

(number) –number inside the brackets denote the topic no. 1 and 2 denote whether the word is
currently assigned to topics t1 and t2 respectively. η = 0.3 and α = 0.3

For question 5,6,7 calculate the value upto 4 decimal points and choose your answer

Question 5 :
Using the above structure the estimated value of β(2)nature at this point is

1. 0.0240
2. 0.02459
3. 0.0260
4. 0.0234

Answer: 1

Solution:
t1 t2
machine 0 4
nature 5 0
language 5 4
vision 3 0
learning 0 3

β(2)nature = (0+0.3)/(11+5*0.3) = 0.3/12.5 = 0.024

Question 6 :
Using the above structure the estimated value of θt1doc2
 1. 0.6562
2. 0.6162
3. 0.6385
4. 0.50000

Answer: 2

Solution:

t1 t2
doc1 8 0
doc2 5 3
doc3 0 8

θt1doc2 = (5+0.3)/(8+2*0.3) = 5.3/ 8.6 = 0.6162

Question 7 :
doc2
Using the above structure the estimated value of θt2

1. 0.6562
2. 0.3975
3. 0.3837
4. 0.3707

Answer: 3

Solution:
Use the same formulae mentioned in Question 9 solution
 Natural Language Processing
Assignment 10
Type of Question: MCQ
Number of Questions: 10 Total Marks:(10×1)= 10

=====================================================

Question 1.

Different phases of entity linking are -

A) Candidate Selection -> Reference Disambiguation
B) Reference Disambiguation -> Candidate Selection -> Mention Identify
C) Mention Identify -> Candidate Selection -> Reference Disambiguation
D) All of the above
Answer: A, C

Solution: Theory. Slide 7; Lecture 1, Week 10 (Entity Linking 1).

===================================================

Question 2.

The text span s=“river” occurs in 700 different Wikipedia articles.

c1 223
c2 161
c3 78
c4 31
No Link 207

Calculate the keyphraseness of “Sea”.

A) 0.232
B) 0.886
C) 0.688
D) 0.704
Answer D
Solution: CF(si) / CF(s) = 223 +161+78+31 / 700 = 493 / 700 = 0.704

===================================================
Question 3.
What is the commonness of (s, c3) in the above question?
A) 0.765
B) 0.389
C) 0.158
D) 0.910

Answer C

Solution: 78/(223+161+78+31) = 78/493 = 0.158

===================================================

Question 4.

Relevant feature/s for a supervised model for predicting the topics to be linked
is/are:
A) Disambiguation Confidence
B) Relatedness
C) Link Probability
D) All of the above
Answer: D

Solution: Theory. Entity Linking Lecture II [Lecture Video 47]

===================================================

Question 5.

Which of the following problem exists in bootstrapping technique for Information

extraction are:

A) Sensitiveness towards the seed set

B) High precision
C) Less manual intervention
D) All of the above
Answer: A

Solution: Theory

===================================================
Question 6.

Which of the following is an advantage of unsupervised relation extraction:

A) Can work efficiently with small amount of hand-labeled data

B) Not easily generalizable to different relations
C) Need no training data.
D) Always perform better than supervised techniques.

Answer: C

Solution: Theory

===================================================

Question 7.

Which of the following is not a Hearst’s Lexico Syntactic Patterns for automatic
acquisition of hyponyms -
A) X or other Y
B) X and other Y
C) Y including X
D) X but not Y
Answer: D

Solution: Theory. Lecture Video 48 : Information Extraction - Introduction, Week

10, Lecture 3 - Slide 15/18.

===================================================

Question 8.

Advantage of Distant supervision over bootstrapping method

A) Need more data

B) Less human effort
C) Can handle noisy data better
D) No Advantage
Answer: C

Solution: Theory

===================================================
Question 9.

Consider a dataset with a very low number of relations - all of which are very
important. For a relation extraction task on that dataset, which of the following is the
most useful metric
A) Precision
B) Recall
C) Accuracy
D) F1-Score
Answer: B
Solution: Theory

===================================================

Question 10.

What is KeyPhraseness (wikipedia)?

A) Number of articles that mention a key phrase divided by the number of
wikipedia articles containing it.
B) Number of Wikipedia articles that use it as an anchor, divided by the
number of articles that mention it at all.
C) Number of articles that mention a key phrase times by the number of
wikipedia articles containing it.
D) Number of Wikipedia articles containing the key phrases times by number
of articles mentioning it.
Answer: B

Solution: Theory.

===================================================