Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 63 ยท Sequences and Structure

Dependency Parsing and Semantic Role Labeling

Build an arc-standard transition parser from scratch, train a tiny scikit-learn action classifier, and map dependency trees to semantic role frames.

The parsing lesson showed dependency trees as head arrays and used CKY to explore constituency trees. This lesson goes one level deeper in two directions. First, you will see how a dependency parser actually builds a tree: a transition-based parser makes a short series of simple decisions, and a classifier chooses each decision. We implement that loop in plain Python and train its classifier with scikit-learn. Second, you will see how to move from syntax (who is the subject of the verb) to meaning (who is the writer, who is the recipient), a task called semantic role labeling (SRL).

Why bother? Because syntax and meaning do not line up. In "Maria wrote the report" and "The report was written by Maria" the subject is different, but Maria wrote it both times. Applications such as information extraction, question answering and coreference want the meaning layer. Dependency trees are the bridge: a rule or a model reads the roles off the tree.

Transition-based parsing

A transition-based parser keeps two data structures: a stack of words it is still working on, and a buffer of words it has not looked at yet. It starts with only ROOT on the stack and the whole sentence in the buffer, and it repeats one of three actions until the buffer is empty and only ROOT remains. This is the arc-standard system.

The three actions

SHIFT Move the next word from the buffer onto the stack.
LEFT-ARC The second word on the stack depends on the top word; remove it.
RIGHT-ARC The top word depends on the second word; remove the top.

Every arc has a relation label such as nsubj or obj.

1 / 2

Each word is shifted once and attached once, so a sentence with n words always takes exactly 2n actions. That is why transition-based parsers are so fast compared with chart parsers.

To train a parser we need to know the correct action at each step. For a sentence with a known tree, a simple oracle can provide it: if the second word on the stack depends on the top word, do LEFT-ARC; if the top word depends on the second and has already collected all its own dependents, do RIGHT-ARC; otherwise SHIFT. The "already collected all its dependents" rule matters: in arc-standard, a word disappears from the stack as soon as it is attached, so it must get all of its children first.

Python The oracle: a tree as a sequence of actions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace from top to bottom. She and gave are shifted, and then LEFT-nsubj says the second item (She) depends on the top item (gave), so She is removed from the stack. the is shifted and, once dog is on top, LEFT-det attaches it. dog is then attached to gave with RIGHT-iobj, and a bone is handled the same way. The last action, RIGHT-root, attaches gave to ROOT. Twelve actions for six words, exactly 2n. Because every action is either a stack move or an arc, the sequence of actions is the tree: you can rebuild the head array from it.

Training a parser with a classifier

At test time, the oracle is not available because we do not know the tree. Instead we train a classifier to predict the action from the current state. The features describe the state: the part-of-speech tags and words of the top two stack items and the first buffer item, and a few combinations such as "the two top tags together". This is the classical feature-based approach (see sequence labeling); neural parsers replace the hand-made features with contextual vectors but keep the same loop.

The example below turns seven tiny hand-annotated sentences into 66 training decisions, trains a logistic regression on them and parses two new sentences. At prediction time, the loop takes the most probable action that is legal (you cannot SHIFT from an empty buffer, or attach ROOT as a dependent).

Python A tiny transition-based dependency parser

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both new sentences are parsed with every head correct, so the unlabeled attachment score (UAS, see the parsing lesson) is 7 of 7 each time. Do not be too impressed. The test sentences only rearrange patterns the parser saw in training, such as determiner then noun, or verb then noun phrase, and all trees are projective with no prepositions, no clauses and no conjunctions. Real parsers train on tens of thousands of annotated sentences, such as the Universal Dependencies treebanks. What the example does show is the mechanism: a few features of the stack and buffer are enough to choose among seven actions, and a linear scan builds the tree.

Arc-standard can only build projective trees (no crossing arcs). Languages with free word order, or English sentences with extraposition, need extra actions such as SWAP, or a graph-based parser that scores every possible arc and finds the best tree. Greedy parsers can also be wrong without recovering; beam search over action sequences, as in decoding, mitigates that.

From syntax to meaning: semantic role labeling

A dependency tree answers grammatical questions: which word is the subject? Semantic role labeling answers meaning questions about an event: who did what, to whom, where and when? Each verb (a predicate) evokes a frame with numbered core roles, and every other phrase either fills one of them or is a modifier. In the PropBank scheme, which defines these frames for English verbs, roles look like this:

  • ARG0: the agent or doer (the writer, the giver).
  • ARG1: the patient or thing affected (the thing written, the thing given).
  • ARG2: often the recipient, beneficiary or instrument. What ARG2 and above mean depends on the verb, so every verb has its own frame entry.
  • ARGM-*: modifiers that any verb can have, such as ARGM-LOC (location), ARGM-TMP (time), ARGM-MNR (manner) and ARGM-CAU (cause).

The important property is that roles stay the same when the syntax changes. A rule-based labeler can show it from a dependency tree: nsubj becomes ARG0 in the active sentence, but in a passive sentence nsubj:pass becomes ARG1 and the by phrase (obl:agent) becomes ARG0.

Python Reading semantic roles from dependency trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first two sentences have different surface structure but the same frame: Maria is ARG0, the report is ARG1, Lisbon is the location and yesterday is the time. The third shows a three-argument verb, give, with a recipient in ARG2. The function subtree collects the whole phrase under a head, dropping the preposition (case), so ARG1 is the report, not just report.

Our rules are brittle. Real SRL has to cope with verbs that take their arguments in many patterns, with prepositions that mark different roles (in Lisbon is a place, in May a time), with nominal predicates (the destruction of the city) and with arguments that are far from the verb. Modern SRL systems are neural, usually a fine-tuned pretrained transformer that tags each word with BIO labels (as in sequence labeling) for each predicate, trained on PropBank and OntoNotes, with F1 in the high 80s on news text. Libraries such as AllenNLP once offered ready-made models; today a large language model with a JSON schema in its prompt is a common way to extract "who did what to whom" when you need a quick solution and can accept some inconsistency.

When you need relations from text, ask what you really need. If "subject, verb, object" triples from simple sentences are enough, a dependency parse and a few rules (as in the parsing lesson) are fast and free. If your data has passives, many clause types or nominal events, SRL or an LLM-based extractor is worth the cost.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the arc-standard system, what does LEFT-ARC do?

    LEFT-ARC draws the arc from the top word (the head) to the second word (the dependent), and the dependent leaves the stack because it has been attached.
  2. 2. A sentence has 8 words. How many actions does an arc-standard parser need to build its tree?

    Every word is shifted once and attached once, so the total is 2n, here 16. That is why transition-based parsing is linear in sentence length.
  3. 3. Why must RIGHT-ARC wait until the top word has all its own dependents?

    After RIGHT-ARC the dependent is removed from the stack. Any child it still needed would have no way to attach to it.
  4. 4. Which statement about semantic roles is correct?

    Semantic roles describe the part a participant plays in the event, not its grammatical position, so they are stable across active and passive voice.
  5. 5. Why is "7 of 7 heads correct" in our tiny parser experiment weak evidence about its quality?

    With so little training data and test sentences built from familiar patterns, the result says that the mechanism works, not that the parser handles real text.

Summary

  • A transition-based dependency parser uses a stack and a buffer; SHIFT, LEFT-ARC and RIGHT-ARC build the tree in exactly 2n actions for n words.
  • Training turns each treebank tree into oracle actions; a classifier learns to predict the next action from features of the stack and buffer, and legal-action checks keep the parse well formed.
  • Arc-standard builds only projective trees; other systems add actions or score all arcs; beam search reduces the cost of greedy mistakes.
  • Semantic role labeling assigns roles such as ARG0 (agent), ARG1 (patient), ARG2 and ARGM-LOC or ARGM-TMP to the phrases around a predicate, in the PropBank style.
  • Roles stay stable across active and passive sentences, which syntax alone does not give you; neural SRL models tag spans with BIO labels, and simple rules over a dependency tree can handle easy cases.

Next, learn how to build feature-based taggers in Sequence Labeling with CRFs and Features.