GitHub

Transition Parsing

The TransitionParsing submodule provides implementations of transition-based parsing algorighms.

julia> using DependencyTrees.TransitionParsing

In transition-based dependency parsing, trees are built incrementally and greedily, one relation at a time. Transition systems define a parser state (or "configuration") while a tree is being built, and oracles map configurations to "gold" transitions that build the correct tree.

An appealing feature about transition parsing is that it is in principle quite fast (𝒪(n) for a sentence of n tokens). A drawback is that a parser greedily predicting one arc at a time can make a "garden-path"-like error, in which a wrongly predicted arc produces more errors for the rest of the parse.

The DependencyTrees.TransitionParsing module implements the following transition systems:

Arc-Standard

DependencyTrees.TransitionParsing.ArcStandard — Type
ArcStandard()

Transition system for for Arc-Standard dependency parsing.

State consists of a stack (σ), a buffer (β), and a list of tokens (A).

Transitions

TransitionDefinition
LeftArc(l)(σ|s1|s0, β, A) → (σ|s0, β, A ∪ (s0, l, s1))
RightArc(l)(σ|s, b|β, A) → (σ, b|β, A ∪ (b, l, s))
Shift(σ, b|β, A) → (σ|b, β, A)

Preconditions

TransitionCondition
LeftArc(l)¬[s1 = 0], ¬∃k∃l'[(k, l', s1) ϵ A]
RightArc(l)¬∃k∃l'[(k, l', s0) ϵ A]

References

source

Oracle function for arc-standard parsing:

Arc-Eager

DependencyTrees.TransitionParsing.ArcEager — Type
ArcEager()

Arc-Eager transition system for dependency parsing.

In Arc-Eager parsing, the parser state consists of:

  • A stack σ, with s at the top: σ|s
  • a buffer β, with b at the front: b|β
  • a list of tokens A, each (h, ℓ, i), indicating an arc from h to i with label ℓ

Arcs are drawn between the token at the top the stack, s, and and the leftmosttoken on the buffer, b.

Transitions

TransitionDefinition
LeftArc(ℓ)(σ|s, b|β, A) → (σ, b|β, A ∪ (s, ℓ, b))
RightArc(ℓ)(σ|s, b|β, A) → (σ, b|β, A ∪ (b, ℓ, s))
Reduce(σ|s, β, A) → (σ, β, A)
Shift(σ, b|β, A) → (σ|b, β, A)

Preconditions

TransitionCondition
LeftArc(ℓ)¬[s = 0], ¬∃k∃ℓ'[(k, ℓ', i) ϵ A]
RightArc(ℓ)¬∃k∃ℓ'[(k, ℓ', j) ϵ A]
Reduce∃k∃ℓ[(k, ℓ, i) ϵ A]

Further Reading

source

Oracle functions for arc-eager parsing:

Arc-Hybrid

Oracle functions for arc-hybrid parsing:

Arc-Swift

Oracle function for arc-swift parsing:

List-Based Non-Projective

Oracle function for list-based non-projective parsing:

Misc.

For stack-and-buffer transition systems (Arc-Eager, Arc-Standard, Arc-Hybrid, and Arc-Swift), DependencyTrees.jl implements functions for getting the tokens from the stack and buffer in a safe way:

Oracles

An Oracle maps a parser configuration to one more gold transitions, which can be used to train a dependency parser.

DependencyTrees.TransitionParsing.Oracle — Type
Oracle(system, oracle_function; label=untyped)

Create an oracle for predicting gold transitions in dependency parsing.

Arguments

  • system is a transition system, defining configurations and valid transitions.

  • oracle_function is called on a parser configuration and tree for gold predictions:

    oracle(cfg, tree, label)

  • label is a function that's called on the gold tokens for that parameters of arcs.

Examples

julia> using DependencyTrees.TransitionParsing

julia> oracle = Oracle(ArcEager(), static_oracle)
Oracle{ArcEager, typeof(static_oracle), typeof(untyped)}(ArcEager(), static_oracle, untyped)

julia> tree = DependencyTree([(2, "I"), (0, "saw"), (4, "a"), (2, "dog")])
┌──────── 0 ROOT
│     ┌─► 1 I
└─►┌──└── 2 saw
   │  ┌─► 3 a
   └─►└── 4 dog

julia> for (state, transition) in oracle(tree)
           @show transition
       end
transition = Shift()
transition = LeftArc()
transition = RightArc()
transition = Shift()
transition = LeftArc()
transition = RightArc()
source
DependencyTrees.TransitionParsing.Oracle — Method
Oracle(system, oracle_function; label=untyped)

Create an oracle for predicting gold transitions in dependency parsing.

Arguments

  • system is a transition system, defining configurations and valid transitions.

  • oracle_function is called on a parser configuration and tree for gold predictions:

    oracle(cfg, tree, label)

  • label is a function that's called on the gold tokens for that parameters of arcs.

Examples

julia> using DependencyTrees.TransitionParsing

julia> oracle = Oracle(ArcEager(), static_oracle)
Oracle{ArcEager, typeof(static_oracle), typeof(untyped)}(ArcEager(), static_oracle, untyped)

julia> tree = DependencyTree([(2, "I"), (0, "saw"), (4, "a"), (2, "dog")])
┌──────── 0 ROOT
│     ┌─► 1 I
└─►┌──└── 2 saw
   │  ┌─► 3 a
   └─►└── 4 dog

julia> for (state, transition) in oracle(tree)
           @show transition
       end
transition = Shift()
transition = LeftArc()
transition = RightArc()
transition = Shift()
transition = LeftArc()
transition = RightArc()
source

An oracle acts like a function when called on a DependencyTree, returning either an OracleSequence or an UnparsableTree in the case when a tree cannot be parsed.

DependencyTrees.TransitionParsing.OracleSequence — Type
OracleSequence(oracle, tree, policy=NeverExplore())

A "gold" sequence of parser configurations and transitions to build tree.

The sequence of transitions is performed according to

policy is a function that determines whether or not "incorrect" transitions are explored. It will be called like so: `policy(

source

An Oracle's third argument is a function called on a DependencyTrees.Token to parametrize a transition. This parameterization can be arbitrary, but DependencyTrees.TransitionParsing exports two function which yield labeled or unlabeled dependencies, respectively:

Exploration Policies

Training a parser on only optimal sequeces of transitions can result in poor decisions under suboptimal conditions (i.e., after a mistake has been made). To compensate for this, OracleSequences can be created with exploration policies to control when (if ever) a "wrong" transition that prevents the correct parse from being produced is allowed.

Exploration policies can wrap a model, which will be called to predict a transition (called like model(cfg, A, G) where cfg is the parser configuration, A is a vector of possible transitions, and G is the gold transition(s) according to the oracle function). The exploration policy then selects the next transition from A and G and the prediction, if available.

DependencyTrees.TransitionParsing.AlwaysExplore — Type
AlwaysExplore()

Policy for always exploring sub-optimal transitions.

If model predicts a legal transition, apply it. Otherwise, sample from the possible transitions (without regard to the oracle transitions) according to rng.

source
DependencyTrees.TransitionParsing.ExplorationPolicy — Type
ExplorationPolicy(k, p)

Simple exploration policy from Goldberg & Nivre, 2012. Explores at rate p.

With rate p, follow model's prediction if legal, or choose from the possible transitions according to rng if the prediction can't be followed. With probability 1 -p, choose from gold transitions according to rng.

source