✔ Scroll down and test yourself — answers are hidden under the “View Answer” button.
Attempt all questions first.
✔️ Click SUBMIT at the end to unlock VIEW ANSWER buttons.
Top Graph-Based Dependency Parsing MCQs - Quiz Questions and Detailed Explanations
Graph-based dependency parsing is a powerful approach in Natural Language Processing (NLP) that models sentence structure as a graph and selects the highest-scoring dependency tree using global optimization techniques. Unlike transition-based methods, graph-based parsers evaluate relationships across the entire sentence, making them effective for handling complex linguistic structures and long-distance dependencies.
This MCQ set focuses on key concepts related to graph-based dependency parsing, including projectivity, non-projective structures, Maximum Spanning Tree (MST) algorithms, scoring mechanisms, and global inference strategies. Each question is accompanied by a clear explanation to support learning, exam preparation, and interview readiness.
These questions are especially useful for students, researchers, and professionals working in NLP, computational linguistics, and machine learning who want to strengthen their understanding of modern dependency parsing techniques.
Dependency parsing models syntactic structure using directed relations between a head word and its dependent.
A dependency relation shows how one word (dependent) is grammatically connected to another word (head). Each relation answers the questions (a) Which word depends on which? and (b) What is their grammatical role? (subject, object, modifier, etc.)
Example
Sentence:
“She drives a Mercedes-Benz C-Class.”
Dependency Relations:
- drives → root (main verb)
- She → dependent of drives (subject → nsubj)
- C-Class → dependent of drives (object → obj)
- a → determiner of C-Class (det)
- Mercedes-Benz → compound modifier of C-Class (compound)
So the structure is:
- drives → She (nsubj)
- drives → C-Class (obj)
- C-Class → a (det)
- C-Class → Mercedes-Benz (compound)
Each arrow represents a dependency relation between a head word and its dependent.
Why other options are INCORRECT?
Option A: Relationship between phrases. This is constituency parsing, not dependency parsing.
Option C: Relationship between sentences. Dependency parsing works within a sentence.
Option D: Relationship between characters. Parsing operates at the word level, not characters.
A dependency structure forms a tree: one root, no cycles, and every word has exactly one head except the root (root has no head).
Key Property: Single-Head Constraint
In a valid dependency tree:
- Every word must have exactly one head, except the root word, which has no head.
- This is called the single-head property.
- One word (usually the main verb) is the root.
- Every other word is connected to only one parent (head).
This constraint ensures that the structure forms a tree, not a graph with multiple parents.
Why other options are INCORRECT?
Option A: Multiple roots. A valid dependency tree must have exactly one root, not multiple.
Option B: Cycles allowed. Dependency trees must be acyclic. Cycles (A → B → A) are not allowed.
Option D: All dependencies must be projective. Projectivity is desirable but not required. Some valid trees are non-projective, especially in free-word-order languages.
In transition-based dependency parsing, a parser builds a dependency tree step-by-step using:
- a stack
- a buffer
- a set of dependency arcs
Each action changes these structures.
LEFT-ARC creates a dependency where the top stack element becomes dependent and is removed.
What does LEFT-ARC do?
The LEFT-ARC action:
- Creates a dependency.
- The word at the top of the stack becomes the dependent.
- The word at the front of the buffer becomes its head.
- Removes the dependent from the stack.
So the LEFT-ARC operation adds a dependency and removes the dependent from the stack.
Example application of LEFT-ARC operation:
Stack: [She]
Buffer: [drives, a, car]
Apply LEFT-ARC:
- Create: drives → She (nsubj)
- Remove She from the stack
New state:
Stack: []
Buffer: [drives, a, car]
Why other options are INCORRECT?
Option B: SHIFT. Moves a word from buffer to stack. No dependency created.
Option C: REDUCE without arc. Removes a word from the stack but does not create a dependency.
Option D: SWAP. Used for handling non-projective structures. Does not directly add a dependency.
Graph-based parsers score possible edges and select the highest-scoring tree globally, reducing greedy errors.
Main Advantage of Graph-Based Parsing
In graph-based dependency parsing:
- The sentence is viewed as a graph.
- Words are treated as nodes.
- Possible dependencies between words are treated as edges with scores.
The parser:
- Assigns a score to each possible dependency.
- Searches for the entire dependency tree with the highest total score.
This means:
The parser makes global decisions, considering the whole sentence at once.
This process is called global optimization.
Why this is an advantage
- Avoids errors caused by early local decisions.
- Finds the best overall tree for the sentence.
- Provides better accuracy for complex sentence structures.
Why other options are INCORRECT?
Option A: Linear-time parsing. Transition-based parsers are typically faster and closer to linear time.
Option C: No training required. Graph-based parsers are machine learning models and require training.
Option D: Works only for short sentences. They work for sentences of any length (though computation increases).
A projective dependency tree is one where the dependency structure can be drawn above the sentence without any crossing lines. If any dependency arcs cross each other, the tree is called non-projective.
What is Projectivity?
In a projective dependency tree:
- Dependencies follow the word order of the sentence.
- If a head is connected to a dependent, all words between them must also belong to that head’s subtree.
- No dependency arcs cross when the tree is drawn above the sentence.
When is a tree non-projective?
A dependency tree is non-projective when:
- At least two dependency arcs cross each other.
This usually happens in:
- Free word-order languages
- Long-distance dependencies
- Certain constructions such as topicalization or scrambling
Why other options are INCORRECT?
Option A and D are violating tree property. B is incorrect because labels are optional for the structure.
Graph-based parsers often use MST algorithms (e.g., Chu–Liu/Edmonds) to find the optimal dependency tree.
In graph-based dependency parsing, the goal is to find the best dependency tree for a sentence. This problem is naturally solved using a Maximum Spanning Tree (MST) algorithm.
Why Maximum Spanning Tree (MST) is suitable?
- Ensures a valid tree structure - MST guarantees one root, each word has exactly one headn, the structure is connected, and no cycles. These are the required properties of a dependency tree.
- Global optimization - Instead of making local decisions, MST considers all possible dependencies and finds the globally best tree with the highest total score
- Efficient algorithms exist (e.g., Chu–Liu/Edmonds)
Why other options are INCORRECT?
Option A Viterbi is used for sequence labeling problem, B (CKY algorithm) is used for constituency parsing and C (Beam search) approximates the best structure but does not guarantee the globally optimal tree.
Standard transition-based dependency parsing runs in O(n) time because it processes each word with a constant number of transitions (shift and arc operations), resulting in a linear number of steps relative to sentence length, hence linear-time complexity.
More explanation:Transition-based dependency parsing builds a dependency tree by processing a sentence word by word using a sequence of simple actions (called transitions). Common transitions are: SHIFT (move a word from buffer to stack), LEFT-ARC (create a dependency and remove one word), and RIGHT-ARC (create a dependency and remove one word)
Why the Complexity is O(n)
Let n be the number of words in the sentence.
- Each word is shifted once from the buffer to the stack → n operations.
Each word also participates in:
- At most one Left-Arc
- At most one Right-Arc
Therefore, the total number of transitions is proportional to the sentence length:
Total transitions ≤ 2n (or a small constant × n)
Since:
- Each transition takes constant time: O(1)
- Total number of transitions = O(n)
Therefore,
Total time complexity = O(n)
Unlabeled Attachment Score (UAS) measures the percentage of words that are assigned the correct head in the dependency tree, regardless of the dependency label.
More explanation:In dependency parsing, each word in a sentence is assigned a head (the word it depends on), and a dependency label (the type of relationship, e.g., subject, object, modifier). To evaluate a parser, we check how many of these predictions are correct.
What is Unlabeled Attachment Score (UAS)?
Unlabeled Attachment Score (UAS) measures the percentage of words for which a dependency parser predicts the correct head, while ignoring the dependency label.
It evaluates (equation below) only the correctness of the syntactic structure (i.e., who depends on whom).
UAS = (Number of words with correct head / Total number of words) × 100
Key Points:
- Only the head prediction is evaluated.
- The dependency relation type (label) is not considered.
- UAS measures how accurately the parser captures the sentence structure.
The SWAP operation allows reordering elements to handle crossing dependencies in non-projective parsing.
Traditional word embeddings (like Word2Vec or GloVe) assign one fixed vector per word, regardless of context. However, in real language, the meaning and syntactic role of a word often depend on the surrounding words.
Contextual embeddings like BERT improve dependency parsing by providing context-aware word representations that capture syntactic roles and relationships within a sentence.
What are Contextual Embeddings?
Contextual embeddings are word representations that change depending on the surrounding context. Models like BERT generate different vectors for the same word based on how it is used in a sentence.
Example:
- “She sat on the bank of the river.” (bank = river side)
- “He went to the bank to withdraw money.” (bank = financial institution)
BERT produces different representations for the word bank in each of the above sentences using the other words present in the context (sentence).
Why This Helps Dependency Parsing?
Dependency parsing requires understanding the grammatical roles (subject, object, modifier), long-distance relationships between words, and ambiguity resolution
Contextual embeddings help because they:
- Capture syntactic role based on context - “book” in “book a ticket” (verb). “book” in “read a book” (noun)
- Provide information about surrounding words - This helps the parser predict the correct head and dependency relation.
- Handle ambiguity and long-range dependencies, which is important for complex sentences.
Why other options are INCORRECT?
Option A: They eliminate the need for tree structures. Parsers still produce dependency trees.
Option B: They reduce sentence length. Embeddings don’t change input size.
Option C: They replace dependency labels. Labels are still predicted by the parser.
No comments:
Post a Comment