Please enable JavaScript.
Coggle requires JavaScript to display documents.
Incrementality in Deterministic Dependency Parsing (most straightforward…
Incrementality in Deterministic
Dependency Parsing
Incrementality
at any point during the parsing process, there is a single connected structure representing the analysis of the input consumed so far
for graphs - the graph being built during parsing is connected at all times
Determinism - never undoing previously made decisions, deterministic parsers do not back up
2 reasons for it in parsing
practical - real-time applications (e.g. speech recognition) require a continually updated analysis of the in- put received so far
theoretical - human parsing is largely incremental (cognitive modelling and psycholinguistics)
avoiding re-parsing the whole input, only finding the part of the tree that needs to be modified by the new input
Not used in most state-of-the-art methods
Full parsers (attempt to disambiguate the input completely) normally have an algorithm that derives a packed parse forest, then selects the most probable analysis, are not deterministic -> no incrementality
Partial parsers (only partially disambiguate the input) are usually deterministic and construct the final analysis in one pass over the input. But the output sequences are not connected, so no incrementally either
Deterministic dependency parsing
compromise btw full and partial parsing
builds a complete syntactic analysis like full parsing (not just identifies the major constituents)
is robust, efficient, and deterministic like partial parsing
Dependency parsing
every word token is dependent on at most one other word token (head / regent)
the structure can be represented as a directed graph, with nodes representing word tokens and arcs representing dependency relations. Arcs may be labeled with specific dependency types.
Here, unlabelled and projective (2 ordered dependencies cannot cross each other) dependency graphs are used
Well-formedness conditions:
unique label
single head
acyclic
connected
projective
Parsing process
triples <S,I,A>, S- the stack represented as a list, I is the list of remaining input, A is the (current) arc relation for the dependency graph
With a string W, the parser initialises as <nil, W, 0> and terminates with <S, nil, A>
The input string is accepted if the dependency graph is well-formed at termination and rejected otherwise
buffer of input tokens and stack for storing the previously processed input
most straightforward parsing strategy - left-to-right bottom-up parsing
parser in form of a transition system
Transitions
:
Initialization
Left-Reduce
combines the two top tokens on the stack by a left-directed arc (head on the right) and reduces the dependent
Right-Reduce
combines the two top tokens on the stack by a right-directed arc (head on the left) and reduces the dependent
Shift
pushes the next input token onto the stack
Termination
to make the algorithm deterministic - parser is guaranteed to terminate after at most 2n transitions for an input string of length n
the size of the stack should never exceed 2 to make the graph connected at all times - every word to be at- tached somewhere in the dependency graph as soon as it has been shifted onto the stack
out of 7 possible projective dependency graphs, only 4 can be constructed incrementally with this approach to parsing
the remaining three require 3 tokens to be shifted onto the stack before the first reduction
in two cases the first two tokens are not connected by a single arc (the leftmost tokens are not linked directly - can never be parsed incrementally), in the third case a reduced dependent has its own dependent - can be parsed incrementally in a modified algorithm
Left-Reduce and Right- Reduce
are subject to conditions that ensure that the
Single head
condition is satisfied. For
Shift
, the only condition is that the input list is non-empty.
Arc-Eager Dependency Parsing
combine bottom-up and top-down processing: process left-dependents bottom-up and right-dependents top-down
arcs will be added to the dependency graph as soon as the respective head and depen- dent are available, even if the dependent is not complete with respect to its own dependents
Transitions:
Left-Arc
adds an arc from the next token to the token on the top of the stack and pops the stack (corresponds to Left-Reduce)
Right-Arc
adds an arc from the token on top of the stack to the next input token and pushes it onto the stack
Reduce
pops the stack
Shift
pushes the next input token onto the stack
Left-Arc and Right-Arc
should ensure that the
Single head
constraint is satisfied, while the
Reduce
transition can only be applied if the token on top of the stack already has a head. The
Shift
transition is the same as before and can be applied as long as the input list
Separation of Right-Arc and Reduce permits the incremental parsing of arbitrary long right-dependent chains
is optimal with respect to incrementality in dependency parsing even though two type of structures cannot be processed by it
top-down vs bottom-up in dependency parsing
top-down construction means that a head is attached to a dependent before the dependent is attached to (some of) its dependents
bottom- up construction means that a dependent is attached to its head before the head is attached to its head
Evaluation
incrementality is measured by the number of connected components at different stages during parsing
out of 16545 configurations in 613 sentences, 68,9% were processed incrementally, the majority of violations were mild (more than 90% of all configurations have no more than three connected components on the stack)
when the test data is restricted to the sentences for which he parser produces a well-formed dependency graph, 87,1% of configurations satisfy the constraints of incrementality
Conclusion: strict incrementality is not possible in deterministic dependency parsing, with the arc-eager algorithm being the closest approximation of it