Does arc eager choose the correct parse by itself?

No. It defines the state transitions; a scoring or decision procedure selects among them.

Why is REDUCE separate from RIGHT-ARC?

A right-dependent item can remain on the stack after receiving its head, allowing further processing before it is removed.

Can the standard system directly represent every nonprojective tree?

No. The standard projective system needs an extension or alternative method for those structures.

AI Glossary / Natural language and speech / Advanced

Arc eager

Definition

Arc eager is a transition-based method for building dependency parses: structures linking each word to its syntactic head. It processes an input sequence using a stack, a buffer, and a growing set of dependency arcs. Its characteristic behavior allows an arc to be created as soon as the relevant stack and buffer items are available, before all later dependents have necessarily been processed.

What it means

A dependency arc points from a head word to a dependent and may carry a grammatical label. In “Mia reads books,” reads can head both Mia and books, with labels identifying the subject and object relationships.

Arc eager specifies legal state changes, not which parse is linguistically correct. A learned scorer, oracle during training, or search procedure chooses among allowed transitions. Different implementations use different root placement and termination conventions, so a worked trace must state its convention rather than mixing rules from separate variants.

How it works

The basic system has four actions. SHIFT moves the first buffer item onto the stack. LEFT-ARC links the first buffer item as head of the stack top and removes that stack item, provided it does not already have a head. RIGHT-ARC links the stack top as head of the first buffer item and moves that buffer item onto the stack. REDUCE removes a stack item that already has a head.

These actions maintain structural restrictions, with additional root and terminal-state rules depending on the formalization. A good action policy must avoid discarding an item before needed dependencies have been built.

The standard system targets projective dependency structures. Handling nonprojective dependencies requires an extension or a different approach. The number of transitions is linear in sentence length under the usual setup, but complete runtime also depends on how scores, features, and search are computed.

Three practical examples

1. Sentence analysis: A parser can identify a verb's subject and object as part of a larger information-extraction pipeline, helping distinguish who performed an action from what received it.

2. Parser education: A step-by-step visualizer can expose how words move between the buffer and stack and when arcs are created, making parsing decisions inspectable.

3. Domain adaptation: A team maintaining a transition-based parser can study mistaken actions on domain-specific sentences and assess whether training data or constraints address the relevant structures.

Think of it this way

Think of an assembly line with an incoming queue and a small working stack. The operator connects items when the required pieces are available and removes pieces whose relevant work is complete. The analogy captures incremental state changes, but syntax is not physical assembly: several legal actions may exist, and a locally attractive choice can block the intended final structure.

Worked example

Use the invented sentence “Mia reads books,” ignoring punctuation. For this trace, follow a root-at-end convention: the initial stack is empty and the buffer is [Mia, reads, books, ROOT]. The target arcs are reads to Mia, reads to books, and ROOT to reads.

Step 1: SHIFT Mia. The stack is [Mia], and reads is first in the buffer. Step 2: LEFT-ARC adds reads to Mia and removes Mia. The stack becomes empty.

Step 3: SHIFT reads. Step 4: RIGHT-ARC adds reads to books and moves books onto the stack, which is now [reads, books]. ROOT remains in the buffer.

Step 5: REDUCE books, which already has a head. Step 6: LEFT-ARC adds ROOT to reads and removes reads. The stack is empty and the buffer contains only ROOT, the terminal configuration for this stated convention.

The trace uses six transitions and produces three arcs for three ordinary words. If books were reduced before receiving a head, that would violate the REDUCE precondition. An implementation with ROOT initially on the stack needs its own corresponding trace; the two conventions should not be combined. This is a hand-checked example, not output from a trained parser.

Illustrative case study

Fictional case: Alder Text builds a parser demonstration for analysts. Its diagram places ROOT initially on the stack, but its written termination rule assumes ROOT remains at the end of the buffer.

The team selects one formalization and checks every transition against it. It also labels the distinction between legal actions and the scorer's preferred action. The fictional case illustrates documentation consistency, not a claimed improvement in parsing accuracy or a recommendation of one root convention over another.

Common misconceptions and mistakes

Do not assume eager means “always take an arc whenever any arc is legal.” The name concerns when an arc can be constructed; selecting the correct action still requires a policy.

Do not equate the transition system with a neural architecture or a specific classifier. Different scorers can drive the same transitions. Also distinguish a valid dependency structure from a correct linguistic analysis. Structural guarantees cannot ensure that the subject was attached to the intended verb, and linear transition count does not erase the cost of a complex scoring model.

Business use

Arc-eager parsing is useful background for teams maintaining syntactic-analysis systems or interpreting transition-based parser output. It reveals where local decisions enter and why an early mistake can influence later attachments.

Evaluate the final dependencies and the downstream extraction task, rather than only the percentage of transition decisions matching one oracle sequence. Multiple action sequences can be relevant in some training settings. Document projectivity assumptions, labels, root handling, and search policy so results can be reproduced and compared meaningfully.

Check your understanding

In the stated system, may REDUCE remove a stack-top word that has no head yet?

Answer: No. Having a head is a precondition of REDUCE. The parser needs a different legal action that preserves the possibility of a valid final structure.

Related terms

Arc standard
Beam search
dependency parsing
transition system
stack
buffer
projectivity
parsing oracle

Learn next

Trace arc-eager and arc-standard parsing on the same dependency tree. Then examine how oracle choices, scoring errors, and root conventions affect the sequence of legal actions.

Sources

Source: Nivre, Goldberg, and McDonald, Constrained Arc-Eager Dependency Parsing, Section 2, read for the base transitions, root-at-end convention, preconditions, and complexity assumptions: https://aclanthology.org/J14-2001.pdf . The example uses that paper's base system, without its additional application constraints. The transition trace is original and manually checked.

Previous: ARAP (as-rigid-as-possible) deformation Next: Arc standard