Edit on 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 an intermediate parser state (or configuration), and oracles map confifurations to "gold" transitions.

The DependencyTrees.TransitionParsing module implements the following transition systems:

Arc-Standard

DependencyTrees.TransitionParsing.ArcStandard — Type
ArcStandard()

Transition system for for Arc-Standard dependency parsing.

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]

See Nivre 2004.

source

Oracle function for arc-standard parsing:

Arc-Eager

DependencyTrees.TransitionParsing.ArcEager — Type
ArcEager()

Arc-Eager transition system for dependency parsing.

Transitions

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

Preconditions

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

References

Nivre 2003, Nivre 2008.

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: –>

<!– @docs --> <!-- stacktoken --> <!-- buffertoken --> <!-- –>

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.

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

oracle_function is called on a paraser 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.

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