Dependency Parsing

10.1 From Phrase Structure to Dependency Parsing

10.1.1 Why Parsing and Word Relations Matter

Parsing is a foundational step for almost every modern NLP application. Question answering needs to know which words the user's question binds together, conversational AI has to track what modifies what, and machine translation has to carry the relations across languages. Dependency parsing in particular shows up in agentic AI and in many current AI applications, so this is a practical, widely used technique, not just a classroom exercise.

The meaning of a sentence depends totally on how its words are connected to each other. There is a lot of ambiguity in natural language, and the relation among words decides which reading is meant. So the step that recovers those connections — parsing — is one of the most important pieces of any NLP pipeline.

Before this session we covered phrase structure parsing: chart parsing, CYK parsing, and probabilistic parsing, all built on context-free grammar rules that group words into phrases (a noun phrase goes to a noun phrase plus a word phrase, and so on). We also covered evaluation — precision, label precision, and label recall — with a worked example. In dependency parsing, the viewpoint changes: we do not look at phrases at all. We look at the individual words and ask how each word depends on the others. The output is a set of relations between words rather than a tree of phrase labels.

Phrase structure grammars run into real trouble with sentences like I saw the man on the hill in Texas with the telescope at noon on Monday: a standard context-free parser returns an astonishing 132 different valid trees for it, because each prepositional phrase can attach at several points in the tree. Free-word-order languages such as Hindi and Russian make the situation worse — their words can move around freely, which breaks the rigid "boxes" of phrase-structure rules altogether. Dependency grammar sidesteps both problems by ignoring phrase boundaries and working directly with word-to-word relations.

10.1.2 The Ambiguity Problem

The classic example is I saw a girl with a telescope. This sentence has two interpretations depending on whether the phrase with a telescope attaches to girl or to saw:

• If with a telescope attaches to girl, the girl is carrying the telescope.
• If it attaches to saw, the seeing was done through a telescope.

Both readings use the same words in the same order; only the dependencies differ. This is exactly why the relations among words are so important in NLP applications — the relations, not the word order alone, carry the meaning.

That single arrow makes the difference concrete for machines. A machine translator must know which reading is meant before it can choose whether the telescope travels as a possession of the girl or as an instrument of seeing; a question-answering system that misbinds with a telescope answers the wrong question. Dependency parsing exists to draw those arrows correctly, and the rest of this lecture builds the machinery that draws them: first by hand with transition rules, then with learned weights, then by searching for the best tree.

10.2 Head Words, Roots, and Dependency Graphs

10.2.1 Head Words and Roots

Every sentence — in English, in Indian languages, in any language — has a head word, also called the governor: the single most important word of the sentence. All the other words are dependent on it.

Take the sentence Bills on ports and immigration were submitted by Brownback, Senator, Republican of Kansas. The word submitted is the main word here. Look at the other words and you will find that they all connect to one another through submitted. This head word is also called the root — the point from which the dependency tree is plotted. The dependencies flow from the head word out to every other word in the sentence.

Phrases have their own head words too. In a noun phrase, the noun is the head: all words in the phrase relate through the noun. In a verb phrase like walked into the store, the verb walked is the head that connects the rest of the phrase. So head-word thinking applies at the sentence level and at the phrase level.

When dependency relations are drawn as arrows, the arrows always point from the head word to the dependent word. In the prepositional phrase with telescope, with is the head of the prepositional phrase, and telescope is the head of the noun phrase a telescope, so the arrow runs from telescope down to a. This arrow convention (head → dependent) is the standard way to read a dependency tree.

10.2.2 Dependency Graphs and Notation

A dependency parse is naturally a graph. Each word in the sentence is one node, and each relation between words is an arc (an edge). Every sentence can be represented by a set of nodes and a set of arcs:

$$G=(V,E)$$

where $V$ is the set of words and $E$ is the set of relations among them.

The mathematical notation for a relation is simply $i\to j$ — an arc from word $W_i$ to word $W_j$. When the type of the relation matters, it is written with a label $D$, but the label is optional: we are often interested only in whether two words are related, not in what kind of relation it is. Indirect relations (paths or dominance) are denoted by $i{\to }^{\ast }j$: if $i$ can reach $j$ through an intermediate node $k$, the connection passes through $k$:

$$i\to k\to j(\text{written compactly as }i{\to }^{\ast }j)$$

10.2.3 Conditions on Dependency Graphs

Not every graph of relations is a valid dependency parse. Four conditions are needed, of which the first three are mandatory everywhere:

1. Connected ($G$ is connected). All nodes must be connected to one another through at least one relation. A word that is an "island" — linked to nothing — is impossible in a grammatically correct sentence; if a word had no connection, it would serve no purpose.
2. Acyclic (no cycles). If saw is the head of I, then I cannot be the head of saw. A relation like $A\to B$ and $B\to A$ together forms a cycle, and cycles are not allowed.
3. Single head constraint. Every word has exactly one incoming arrow. A word cannot have multiple head words, so multiple incoming edges are impossible. Outgoing edges are fine — the head word connects to many dependents — but incoming is always exactly one.
4. Projectivity (not mandatory for every algorithm). Projectivity forbids crossing edges. It is important for English because English is written left to right, so the relations are left-to-right as well: if saw connects to girl over the words between them, you cannot also draw a relation that crosses over that span. This condition is used by the arc-eager parser; the graph-based algorithm we will see later does not require it. It is listed here for completeness.

Visual intuition. Picture the Bills on ports and immigration were submitted ... sentence as a row of words with curved arrows drawn above them. From submitted — the root — arrows fan out to every other word, and each word receives exactly one arrow tip. Because the arrows never cross each other, the picture looks like a tidy arch over the sentence: that non-crossing property is projectivity in visual form. The one-sentence takeaway: a valid parse is a single connected, acyclic arrow diagram in which every word has exactly one incoming arrow.

10.2.4 Relation Labels

The optional label $D$ on an arc names the type of relation: subject, direct object, determiner, and so on. In a labeled parse you can read, for example, that one word is the direct object of the verb, another is the direct subject of the verb, and a third is the determiner of the noun cup. Having gold-labeled data that says what kind of relation each arc is will always help an application, but if the labels are unavailable, you can still work with the unlabeled relations.

Standard label sets exist for this: the Universal Dependencies project provides a uniform annotation scheme used across many languages, with labels such as nsubj (nominal subject), dobj (direct object), det (determiner), prep (preposition), pobj (prepositional object), amod (adjectival modifier), and tmod (temporal modifier). Because the same labels are reused for many languages, models trained on one language's treebank can transfer grammatical knowledge to another.

Real-world & domain connection. Labeled dependency trees are the backbone of the Universal Dependencies treebanks, which are built from resources such as the Penn Treebank and annotated by human experts across dozens of languages. Production NLP pipelines — including the parsing components inside question-answering, machine translation, and conversational AI systems — first recover the unlabeled relations, then assign labels such as subject and object, because downstream systems act on both the structure and the roles.

10.3 Deterministic (Arc-Eager) Parsing: The Four Transitions

10.3.1 Parser Configuration

The first family of dependency parsing algorithms is deterministic parsing: we find the relations among the words using a fixed sequence of simple, deterministic steps — that is why it is called deterministic. At every step exactly one move is chosen by a fixed rule (or, as we will see in the next section, by a learned classifier) — there is no backtracking and no search over alternatives.

The state of the parser at any moment is a parser configuration, written as a triple:

$$C=(S,B,A)$$

• $S$ — the stack: the words currently being processed. The stack is LIFO — last in, first out.
• $B$ — the buffer: the words of the sentence that have not been parsed yet. The buffer is FIFO — first in, first out. Initially it holds every tokenized word of the sentence (including the full stop).
• $A$ — the arcs: the relations the parser has already discovered. Arcs may carry labels like the $D$ labels discussed above, or they may be unlabeled.

The initial configuration is

$$C_0=(\varnothing ,[w_1,w_2,\dots ,w_n],\varnothing )$$

with an empty stack, the whole sentence in the buffer, and no arcs. At every step the parser checks the last word in the stack against the first word in the buffer — LIFO and FIFO determine how words are taken out, which is why the parser compares those two positions. A transition moves the parser from one configuration to the next, and parsing proceeds as a sequence of transitions. The goal at the end: the buffer must be empty, and the arcs set $A$ then contains all the relations of the sentence. The stack may or may not be empty at termination — that is allowed. Some textbooks apply a few extra reduce operations to empty the stack too, but it is not required, because reduce never adds an arc.

10.3.2 The Four Transitions

Four operations are enough to parse a sentence with this algorithm. They are the malt parser's transitions, which we focus on; other parsing algorithms exist in Jurafsky and Martin but are not required for the exam.

LEFT-ARC. We compare the last word of the stack with the first word of the buffer. If there is a left-arc relation — the buffer word $W_j$ is the head of the stack word $W_i$ — we add the arc $W_j\to W_i$ to $A$ and remove the last word from the stack. The buffer is untouched: the buffer word may itself be a dependent of other words later. So the one-line rule to remember: left arc removes the last word in the stack.

$$A^{\prime }=A\cup \{j\to i\},S^{\prime }=S\setminus \{\text{top}(S)\}$$

RIGHT-ARC. If the relation runs the other way — the last word of the stack $W_i$ is the head of the first word of the buffer $W_j$ — we add the arc $W_i\to W_j$ to $A$, and then push the buffer word onto the stack, keeping it there. We cannot remove the stack word here: that word is a head, and it may be the head of other words still waiting in the buffer. So the one-line rule: right arc adds the first buffer word to the stack (and does not remove the head).

$$A^{\prime }=A\cup \{i\to j\},S^{\prime }=S\cup \{\text{front}(B)\},B^{\prime }=B\setminus \{\text{front}(B)\}$$

SHIFT. If no word in the stack is related to the first word of the buffer — which is always true at the start, when the stack is empty — we simply move the first buffer word onto the stack. It is always added at the last (top) position, so the LIFO order is preserved. Shift adds no arc.

$$S^{\prime }=S\cup \{\text{front}(B)\},B^{\prime }=B\setminus \{\text{front}(B)\}$$

REDUCE. Suppose the last word of the stack is not related to the first word of the buffer, but the second-last word of the stack is. Because the stack is LIFO, we cannot reach down and attach the buffer word directly — we cannot bypass the top word. So we reduce: we remove the last word from the stack, adding nothing to the arcs and changing nothing in the buffer, just to clear the way for the relation below. The one-line rule: reduce removes the last word in the stack, with no arc and no buffer change.

When generating the gold transitions (the oracle) from a labeled parse, the operations are checked in a fixed order: left arc first, then right arc, then reduce, then shift. This order is the standard arc-eager definition: at each configuration the parser tries LEFT-ARC (it applies only when the word on top of the stack does not yet have a head), then RIGHT-ARC (it applies when the stack and the buffer are both non-empty), then REDUCE (it applies only when the top word already has a head), and only if none of them matches the gold tree does it SHIFT the front word of the buffer onto the stack. Because the check order is fixed, every configuration has exactly one correct next operation — the sequence is deterministic. The preconditions are what make LEFT-ARC and REDUCE mutually exclusive: a word that has no head yet cannot be reduced, and a word that already has a head cannot receive a left arc, since that would give it a second head.

10.3.3 Worked Example: "He sent her a letter."

Cost. A single parse is linear in the length of the sentence: every transition either removes a word from the buffer or removes a word from the stack, and each word enters the stack once, so the number of steps is at most $2n$ for $n$ words — $O(n)$. The price of this speed is that the parser is greedy: it decides each step once and never revisits a decision, so an early mistake can cascade and distort everything that follows. That is exactly the weakness the graph-based family at the end of this lecture attacks with a global view.

10.3.4 Student Questions and Answers

The next question attacks the step where the trace seems to contradict itself: after the right arc the stack keeps its word, while after the left arc it does not.

A second student asked where new words land when they enter the stack.

Then came the deeper doubt: if the word is done being processed, why keep it at all?

Another student wanted the rule for shift stated simply.

A follow-up asked whether the head sent would still be kept if the rest of the sentence were shorter.

The last question of the session was about how many dependents one head may have.

Real-world & domain connection. The four arc-eager transitions are the blueprint of the malt parser and of the transition-based parsers embedded in production NLP toolchains; the later neural parsers keep these exact operations and replace only the scoring of the moves — which is where the next section heads.

10.4 Training the Deterministic Parser: Data Generation and Weight Learning

10.4.1 From Transitions to Training Data

The arc-eager transitions are not just a way to parse; they are the machinery for generating training data for a classifier. Human-labeled treebanks — the Penn Treebank is the standard example — give us sentences paired with gold dependency graphs. Running the arc-eager algorithm over those graphs produces, for every configuration, the correct next operation: left arc, right arc, reduce, or shift. Those gold operations are the oracle: the target labels for learning.

Why go through this conversion? Because machine learning and deep learning algorithms cannot consume a dependency graph directly. They need feature–label pairs. Each configuration gives a feature description (the stack, buffer, and arc contents), and the gold transition is its class. Since there are exactly four operations, this is a four-class multi-class problem, and the configurations become the training tuples.

At test time the roles are reversed. A new sentence arrives (for example, something like She sent him a letter), the buffer holds all its words, the stack and arcs start empty, and at every step the learned weights select the best operation — finding, say, a left arc between a and letter, a right arc between sent and him — until the buffer is empty. The operations are the relations: each left arc and right arc drawn at test time is a discovered dependency.

10.4.2 The Weight-Learning Algorithm

The weights are learned the same way as in any linear classifier. The configuration is encoded as a feature vector $\varphi$, and each of the four operations gets a score that is the dot product of the weight vector with the feature vector:

$$\text{score}(t)={\mathbf{w}}^{\top }{\varphi }_t,t\in \{\text{LEFT-ARC},\text{RIGHT-ARC},\text{REDUCE},\text{SHIFT}\}$$

The chosen operation at each step is the argmax — the highest-scoring class. During training, all weights start at zero, exactly like gradient descent initialization, and the update rule is:

$${\mathbf{w}}_{\text{new}}={\mathbf{w}}_{\text{old}}+\varphi (\text{gold})-\varphi (\text{predicted})$$

The feature vector of the gold operation is added, the feature vector of the predicted operation is subtracted, and the old weights are updated accordingly. This is a perceptron-style update: the update literally adds the features of the correct move and subtracts the features of the bad move. If the prediction was right, the two vectors are equal and the weights do not change at all; every mistake moves the weights so that the gold operation scores higher and the wrong operation scores lower next time.

Learning continues while the error is being minimized, or for a fixed number of iterations $K$ — the same stopping logic as batch or mini-batch gradient descent: process all training examples (one sentence per pass, or all of them), then repeat until a fixed iteration count or an accuracy criterion is reached.

Decoding for a test sentence $w_1\dots w_n$: start from the initial configuration, and while the buffer is not empty, compute the four scores with the learned weights, apply the argmax operation, advance the configuration, and repeat. That is the whole loop: pick the best operation, apply it, move on, until every word in the buffer has been processed.

10.4.3 Worked Example: "John saw Mary"

The condition wording deserves one caution. The third condition appears in one place in the source as "the top of the buffer is a verb" and in another as "the top of the stack is a verb". The lecture notes define the three features as the conjunctive pairs used above — stack noun and buffer verb, stack verb and buffer noun — and only those agree with the numbers in Part 3 ([0, 1, 0] after John is shifted: John is a noun, so the stack-top-verb condition is 0). Both wordings agree on the examinable first step at C0, where the stack is empty and every class block reads [1, 0, 0].

This weight-learning example was flagged in class as a little overwhelming — that is expected. Work through it again slowly, one step at a time, and raise any doubts at the start of the next session.

10.4.4 Student Questions and Answers

The next exchange was about the single word argmax, which carries the whole decision.

Another student wondered whether the feature vector always has exactly one 1.

A practical doubt followed: what do these conditions look like inside a real program?

The next doubt was about scale: one sentence seems like very little training.

An observation from a student linked the step-by-step nature of parsing to sequence models.

The following question unpicked the shape of the feature vector: 12 values but one dot product.

The oracle came up next — where the "correct answer" of the update comes from.

Finally, the class asked directly what to expect in the exam.

Real-world & domain connection. This pipeline — replay gold trees from a treebank into transition sequences, then learn a classifier that picks the next operation — is how production transition-based parsers (the malt parser and its descendants) are trained. The same feature–label pattern underlies statistical parsing generally, and the neural parsers of later sessions replace the hand-built conditions with learned representations while keeping this training loop intact.

10.5 Graph-Based Dependency Parsing

10.5.1 Sentences as Weighted Graphs

The second family of algorithms takes a different view: treat the sentence as a graph and search for the best tree. As before, the words are the vertices and the relations are the arcs. Since we need to know which word is the head, the graphs are directed — digraphs, where an arc points from the head to the dependent. The word multi-digraph appears here because at the start we do not know what relations exist: arcs could run in any direction between any pair of words, and multiple different relations can hold at once.

This idea of several simultaneous relations is the same intuition behind multi-head attention in transformers: different attention heads capture different kinds of relationships (one head might track part-of-speech-style relations, another verb–argument structure, another something like "capital of city"). We will see the transformer architecture properly in the next session on contextual word embeddings. For now, graph-based dependency parsing focuses on a single directed relation between two words.

Each sentence has a single root — the head word of the whole sentence. The root has only outgoing edges to all the other words; every other node may have edges to and from every other node. So with $N$ words there are $N-1$ candidate arcs leaving the root, plus candidate arcs between all the remaining pairs, and initially we do not know which ones are correct.

The search uses the idea of a weighted spanning tree from network theory. Every candidate edge has a weight learned from the training data. For any tree, we compute the sum of its edge weights:

$$\text{score}(T)=\sum _{(u\to v)\in T}w(u\to v)$$

where $w(u\to v)$ is the weight of the edge from word $u$ to word $v$, and $T$ is a spanning tree over the words. The tree with the maximum total weight — the argmax over all candidate trees — is taken to be the correct set of relations among the words.

A spanning tree touches every vertex, has no loops, and gives every word exactly one incoming arc (the root none) — so a spanning tree and a valid dependency tree are the same object. The maximum spanning tree (MST) is the one with the highest total weight, and it is the parse the algorithm returns.

10.5.2 Chu-Liu-Edmonds Algorithm

Finding the maximum spanning tree could be done by enumerating candidates, but the standard method is the Chu-Liu-Edmonds algorithm, named after the researchers (Chu, Liu, and Edmonds) who proposed it. It is a greedy maximum spanning tree algorithm, and it is simple — the only complication is what to do when the greedy choices produce a cycle.

The greedy rule: we know the single head constraint — exactly one incoming edge per word — so for every node we independently select the incoming edge with the maximum weight:

$$\text{keep}(v)=\arg \underset{u}{\max }w(u\to v)$$

If the resulting collection of best-incoming edges contains no cycle, we are done: that is the parse tree.

The algorithm runs in four steps: (1) greedy selection — for every word, keep the incoming arc with the highest weight; (2) check — if the kept arcs contain no cycle, they are already the maximum spanning tree, so stop; (3) contraction — if a cycle appears, collapse the words of the cycle into one temporary vertex and recompute the incoming weights as path sums through the cycle; (4) unpacking — repeat the selection on the contracted graph, then expand the temporary vertex back into the original words, keeping the winning path.

Cost. For a sentence of $n$ words the candidate graph is dense — every word may relate to every other word — and the Chu-Liu-Edmonds algorithm runs in $O(n^2)$ time on such a graph: one pass to pick the best incoming arc per vertex, plus one pass for each cycle contraction. That is slower than the linear transition-based run, but the search is global: the answer is the mathematically best tree, not the first tree reached.

10.5.3 Worked Example: "John saw Mary" — the Greedy Step

If the greedy step had produced a tree, the algorithm would end right there. For instance, if the weight of root → saw had been 35 instead of 10, then saw's best incoming edge would be root → saw (35) instead of John → saw (30), and the greedy result — root → saw (35), saw → John (30), saw → Mary (30) — would already be a valid tree with the verb as root. Cycles only trigger extra work, and with well-learned weights they should be rare, because it is the learned edge weights that determine whether a cycle forms at all.

One caution about the numbers in the source figure: the per-edge weights shift between the greedy phase and the cycle phase — for example saw → John appears as 20 here and as 30 during cycle removal — and the class acknowledged that the figure carries a typo from the book. The four path sums computed in the next step (40, 29, 31, 30) and the final tree follow the numbers exactly as presented in class, so those are the numbers to use and to expect on the exam.

10.5.4 Breaking Cycles: Contraction and Expansion

The four path sums 40, 29, 31, 30 and the final tree above follow the numbers exactly as stated in class. One caution: the source figure contains a typo in an edge weight, acknowledged in class as carried over from the book — saw → John appears as 20 in the greedy figure but as 30 in the path sums and the final tree. Keep the numbers as stated here; they are the ones used for the exam.

That is the entire algorithm: greedy maximum-incoming selection; if a cycle appears, contract the cycle words, recompute the incoming path sums, re-select greedily, and expand back. Multiple cycles would be handled the same way — treat each cycle as a single word and recompute — though multiple cycles are unlikely when the edge weights are learned properly.

10.5.5 Student Questions and Answers

A second student asked how the other incoming sums arise.

The next doubt was about why the two-edge paths must be taken together at all.

Another student asked what the final tree actually says about the sentence.

The last question was about whether cycles can pile up.

Visual intuition. Picture the contraction step of the example: the two-word cycle is a small ring — John points to saw, saw points back to John — which collapses into one bubble $W_{JS}$. From outside, four arrows reach the bubble: two from root (weight 40 via saw, 29 via John) and two from Mary (31 via saw, 30 via John). The heaviest, 40, wins; splitting the bubble open again reveals the path root → saw → John, and the ring's other arc (John → saw) is dropped. The takeaway: contraction turns a cycle problem into an ordinary single-incoming-arc choice, and expansion restores the original words.

Real-world & domain connection. Graph-based dependency parsing is the basis of the MST parser family, trained with global updates that compare the whole predicted tree against the gold tree. The maximum-spanning-tree idea comes from network theory, where it is used to lay out efficient telephone, power, and transport networks; the multi-digraph view — several relations between the same two words — is also the conceptual bridge to multi-head attention in transformers, where different attention heads capture different relation types at once.

10.6 Looking Ahead: Contextual Word Embeddings and Transformers

10.6.1 Why Transformers Matter

The multi-digraph idea — several different relations holding between words at the same time — is a natural bridge to the next topic: contextual word embeddings and the transformer architecture, including the key, query, and value matrices of the attention mechanism. The class check showed that key-query-value matrices have not been covered in depth yet (a brief mention appeared in the computer vision session on transformers), so they will be developed from scratch. The topic is flagged as a bit involved, but it matters everywhere: transformers are the basic building block of LLMs, generative AI, most modern NLP courses, and agentic AI. Multi-head attention will tie directly back to the idea that multiple relations among words can be captured simultaneously.

In dependency parsing, each arc label — subject, object, modifier — is one kind of relation between two words. Attention heads generalize this picture: instead of one labeled arc per pair of words, the model computes, for every pair, a soft strength for each of several relation types at the same time, and all of them coexist inside the network rather than competing for a single tree. That is the bridge: a dependency tree keeps one chosen relation per pair, the multi-digraph keeps several, and attention keeps several weighted ones.

This lecture's two parsing families are also a preview of two learning styles that return in transformer models: the step-by-step scoring of a classifier inside the transition-based parser, and the global optimization over a structure behind the maximum spanning tree. Both styles reappear when we study how attention is trained and used.

Exam Guidance Summary

Both numerical questions below come straight from the worked examples — reread the traces before the exam.

• Expect a numerical on arc-eager parsing. Given a sentence and its gold dependency picture, produce the sequence of transitions — left arc, right arc, reduce, shift — from the initial configuration to the end of the sentence (buffer empty). The full trace of He sent her a letter . above is the template: every operation, every stack and buffer update, every arc added.
• Expect a numerical on weight learning. Given the conditions (features) and the gold standard (oracle) values, define the feature vector and the initial weight vector, compute the per-class dot products, find the argmax, and apply the weight update ${\mathbf{w}}_{\text{new}}={\mathbf{w}}_{\text{old}}+\varphi (\text{gold})-\varphi (\text{predicted})$. Only the first iteration is asked; the follow-up iterations will not be on the exam.
• Scope: the malt parser (arc-eager) transitions only. Other parsing algorithms in Jurafsky and Martin are not required for the exam; the four operations covered here are the focus.
• The weight-learning example was flagged in class as dense — if it feels heavy, that is expected. Go back through the worked example slowly: feature vector → dot products → argmax → update, one step at a time.
• Review the material after the session; questions about the deterministic part are welcome at the start of the next session.

The graph-based worked example follows the same pattern as the deterministic one: greedy selection, cycle contraction with path sums, expansion. Practise writing the transition sequence and the weight update with a fresh sentence and a fresh gold picture — the mechanics are the same every time.

Key Industry Applications

• Agentic AI and modern NLP apps: dependency parsing is used across current AI applications, from question answering to conversational AI to machine translation. Agents that read instructions or queries need the same word relations to act on them, which makes this a practical, widely used technique.
• Question answering: you need to know which words the question binds together — which relations hold among them — before you can answer it. An attachment error changes which entity the question asks about.
• Conversational AI: tracking what modifies what in a user's utterance is part of understanding it; a wrong attachment produces the wrong intent.
• Machine translation: the dependency relations carry the sentence structure that has to survive translation; many MT systems parse the source into dependencies before generating the target sentence.
• Treebanks and training data: human-labeled resources like the Penn Treebank feed the arc-eager transition generation, which produces the feature–label pairs for the parsing classifier — the same pattern as training data generation in statistical parsing.
• Parsing classifiers: the deterministic parser is trained as a four-class classifier (logistic regression/SVM-style feature engineering for ML; learned features for deep learning), and the graph-based parser searches for the maximum-weight spanning tree, a network-theory idea applied to grammar.
• Transformers and multi-head attention: the multi-digraph view of many simultaneous word relations prefigures multi-head attention in transformers, the building block of LLMs, generative AI, and agentic AI — covered in the next session on contextual word embeddings.
• Named references: Jurafsky and Martin (Speech and Language Processing; the textbook and the Stanford NLP course material), the NPTEL course notes for the weight-learning example, the Penn Treebank, the malt parser (arc-eager) algorithm, and the Chu-Liu-Edmonds maximum spanning tree algorithm.