Keyphrases:
Dependency Parsing.
Dependency Grammar and Dependency Structure
Two main types of structures: constituency structures and dependency structures.
Dependency Parsing
Dependency parsing is the task of analyzing the syntactic dependency structure of a given input sentence S. The output of a dependency parser is a dependency tree where the words of the input sentence are connected by typed dependency relations
Two subproblems:
- Learning: Given a training set D of sentences annotated with dependency graphs, induce a parsing model M that can be used to parse new sentences.
- Parsing: Given a parsing model M and a sentence S, derive the optimal dependency graph D for S according to M.
Transition-Based Dependency Parsing
It relies on a state machine.Most transition-based systems do not make use of a formal grammar.
-
learning: induce a model which can predict the next transition in the state machine based on the transition history
-
parsing: construct the optimal sequence of transitions for the input sentence, given the previously induced model.
Greedy Deterministic Transition-Based Parsing
States:
For any sentence $S=w_0w_1…w_n$, a state can be described with a triple $c=(\sigma, \beta, A)$:
- a stack $\sigma$ of words $w_i$ from S
- a buffer $\beta$ of words $w_i$ from S
- a set of dependency arcs A of the form $(w_i, r, w_j)$, where $w_i$, $w_j$ are from S, and r describes a dependency relation.
initial state:$({[w_0]}{\sigma}, {[w_1,…,w_n]}{\beta}, \phi)$
terminal state:$(\sigma, []_{\beta}, A)$
Transitions:
- shift: $\sigma, w_i\mid\beta,A\rightarrow \sigma\mid w_i, \beta,A$
- left-arc: $\sigma\mid w_i\mid w_j, \beta,A\rightarrow \sigma\mid w_j, \beta,A\bigcup{r(w_j, w_i)}$
- right-arc: $\sigma\mid w_i\mid w_j, \beta,A\rightarrow \sigma\mid w_i, \beta,A\bigcup{r(w_i, w_j)}$
Neural Dependency Parsing
