Virtual Labs

POS Tagging - Viterbi Decoding

What is the primary purpose of the Viterbi algorithm in Natural Language Processing?

a: To find the most probable sequence of hidden states given observations Explanation

Explanation

b: To translate text from one language to another Explanation

Explanation

c: To count word frequencies in a corpus Explanation

Explanation

d: To generate random sentences Explanation

Explanation

In the context of POS tagging, what do the 'hidden states' represent in a Hidden Markov Model?

a: The POS tags (noun, verb, adjective, etc.) Explanation

Explanation

b: The words in the sentence Explanation

Explanation

c: The punctuation marks Explanation

Explanation

d: The sentence length Explanation

Explanation

What information does the emission matrix provide in HMM-based POS tagging?

a: P( word | POS tag ) - the probability of observing a word given a POS tag Explanation

Explanation

b: P( POS tag | word ) - the probability of a POS tag given a word Explanation

Explanation

c: The frequency of words in the training corpus Explanation

Explanation

d: The order of words in a sentence Explanation

Explanation

What does the transition matrix represent in the context of POS tagging?
Choose the best option:

a: P(tag_i | tag_{i-1}) - the probability of transitioning from one POS tag to another Explanation

Explanation

b: P(word_i | word_{i-1}) - the probability of one word following another Explanation

Explanation

c: The total number of tags in the tagset Explanation

Explanation

d: The length of the training sentences Explanation

Explanation

What is the key computational technique that makes the Viterbi algorithm efficient?
Choose the best option:

a: Dynamic programming Explanation

Explanation

b: Brute force search Explanation

Explanation

c: Random sampling Explanation

Explanation

d: Greedy search Explanation

Explanation

In the Viterbi algorithm, what does each cell V[i][j] in the Viterbi table represent?
Choose the best option:

a: The maximum probability of any tag sequence ending in tag i at word position j Explanation

Explanation

b: The emission probability of word j given tag i Explanation

Explanation

c: The transition probability from tag i to tag j Explanation

Explanation

d: The frequency of tag i at position j in the training data Explanation

Explanation

What is the time complexity of the Viterbi algorithm for a sentence of length N with T possible tags?

a: O(N × T²) Explanation

Explanation

b: O(T^N) Explanation

Explanation

c: O(N × T) Explanation

Explanation

d: O(N²) Explanation

Explanation

In the Viterbi algorithm, why is backtracking necessary after filling the table?

a: To reconstruct the optimal tag sequence by following the path of maximum probabilities Explanation

Explanation

b: To verify that all probabilities sum to 1 Explanation

Explanation

c: To calculate the emission and transition matrices Explanation

Explanation

d: To count the total number of possible tag sequences Explanation

Explanation

Consider a sentence 'Book a park' where 'Book' could be either a noun or verb. How does the Viterbi algorithm handle this ambiguity?

a: It considers both possibilities and chooses based on the combination of emission and transition probabilities throughout the sequence Explanation

Explanation

b: It always chooses the most frequent tag for the word Explanation

Explanation

c: It ignores the context and assigns tags randomly Explanation

Explanation

d: It only looks at the emission probability for that word Explanation

Explanation