4.3 Left-corner Dependency Parsing
4.3.3 Oracle and spurious ambiguity
However, our system is unsound for the class of projective dependency trees, meaning that a transition sequence on a sentence does not always generate a valid projective dependency tree. We can easily verify this claim with an example. Leta b cbe a sentence and consider the action sequence
“SHIFTLEFTPRED SHIFT LEFTPRED INSERT” with which we obtain the terminal configuration ofσ = [x(a), c];β= [];A={(b, c)}5, but this is not a valid tree. The arc-eager system also suffers from a similar restriction (Nivre and Fernández-González, 2014), which may lead to lower parse accuracy. Instead of fixing this problem, in our parsing experiment, which is described in Section 4.5, we implement simple post-processing heuristics to combine those fragmented trees that remain on the stack.
• RIGHTCOMP: Letc= (σ|hσ′2|i|x(λ)i|hσ11,· · · i, β, A).imay not exist. Then – ifiexists, the rightmost dependent ofσ11is inβand(i, σ11)∈Ag;
– otherwise, the rightmost dependent ofσ11is inβ and∃k∈λ,(σ11, k)∈Ag.
• RIGHTPRED: ifc= (σ|hσ11,· · · i, β, A)andσ11has a dependent inβ.
• LEFTPRED: otherwise.
Essentially, each condition ensures that we do not miss any gold arcs by performing the transition.
This is ensured at each step so we can recover the gold tree in the terminal configuration. We use this oracle in our experiments in Sections 4.4 and 4.5.
Spurious ambiguity Next, we observe that the developed oracle above is not a unique function to return the gold action. Consider sentenceaxbyc, which is a simplification of the sentence shown in Figure 4.1(c). If we apply the oracle presented above to this sentence, we obtain the following sequence:
SHIFT→LEFTPRED→ INSERT→RIGHTPRED→INSERT (4.1) Note, however, that the following transitions also recover the parse tree:
SHIFT→ LEFTPRED→SHIFT→ RIGHTCOMP→INSERT (4.2) This is a kind of spurious ambiguities that we mentioned several times in this thesis (Sections 2.1.4, 2.3.5, and 4.1). Although in the transition-based parsing literature some works exist to improve parser performances by utilizing this ambiguity (Goldberg and Nivre, 2013) or by eliminating it (Hayashi et al., 2013), here we do not discuss such practical problems and instead analyze the differences in the transitions leading to the same tree.
Here we show that the spurious ambiguity of the transition system introduced above is essen-tially due to the spurious ambiguity of transforming a dependency tree into a CFG parse (Section 2.1.4). We can see this by comparing the implicitly recognized CFG parses with the two action sequences above. In sequence (4.1), RIGHTPREDis performed at step four, meaning that the rec-ognized CFG parse has the form ((a b) c), while that of sequence (4.2) is (a (b c)) due to its RIGHTCOMPoperation. This result indicates an oracle for our left-corner transition system implic-itly binarizes a given gold dependency tree. The particular binarization mechanism associated with the oracle presented above is discussed next.
Implicit binarization We first note the property of the presented oracle that it follows the strat-egy of performing composition or insert operations when possible. As we saw in the given example, sometimes INSERTand SHIFT can both be valid for recovering the gold arcs, though here we al-ways select INSERT. Sometimes the same ambiguity exists between LEFTCOMPand LEFTPREDor RIGHTCOMPand RIGHTPRED; we always prefer composition.
Then, we can show the following theorem about the binarization mechanism of this oracle.
Theorem 4.1. The presented oracle above implicitly binarizes a dependency tree in the following manner:
a b c d e (a)
X[b]
X[d]
X[d]
X[e]
e X[d]
d X[c]
c X[b]
X[b]
b X[a]
a
(b)
Figure 4.7: Implicit binarization process of the oracle described in the body.
• Given a subtree rooted ath, if the parent of it is its right side, orhis the sentence root,h’s left children are constructed first.
• If the parent ofhis its left side,h’s right children are constructed first.
Figure 4.7 shows an example. For example, since the parent of dis b, which is in left, the constituentd eis constructed first.
An important observation for showing this is the following lemma about the condition for ap-plying RIGHTCOMP.
Lemma 4.1. Letc= (σ|σ2|σ1, β, A)andσ2be incomplete (next action is a reduce action). Then, in the above oracle,RIGHTCOMPnever occurs for a configuration on whichσ2is rooted at a dummy, i.e.,σ2 =hx(λ)i, orσ1has some left children, i.e.,∃k < σ11,(σ11, k).
Proof. The first constraint,σ2 6= hx(λ)i is shown by simulating how a tree after RIGHTCOMPis created in the presented oracle. Let us assumeλ={i}(i.e.,σ2looks likeixx),j=σ11, andσ1be a subtree spanning fromi+ 1tok(i.e.,i+ 1≤j≤k). After RIGHTCOMP, we get a subtree rooted atj, which looks likeixjyx′ wherex′is a new dummy node. The oracle instead builds the same structure by the following procedures: After buildingixxby LEFTPREDtoi, it first collect all left children ofxby consecutive LEFTCOMPactions, followed by INSERT, to obtain a treeixj(omitj’s left dependents betweeniandj). Then it collects the right children ofj(corresponding tox′) with RIGHTPREDs. This is because we prefer LEFTCOMPand INSERTover LEFTPREDand SHIFT, and suggests thatσ2 6=hx(λ)ibefore RIGHTCOMP. This simulation also implies the second constraint that∄k < σ11,(σ11, k), since it never occurs unless LEFTPREDis preferred over LEFTCOMP. Proof of Theorem 4.1. Let us examine the first case in which the parent ofhis in the right side. Let this parent index beh′, i.e.,h < h′. Note that this right-to-left arc (hxh′) are only created with LEFTCOMPor LEFTPREDand in both cases hmust finish collecting every child before reduced, meaning thath′does not affect the construction of a subtree rooted ath. This is also the case when his the sentence root. Now, ifhcollects its right children first, that meanshcollects left children via RIGHTCOMPwith subtree rooted at a dummy node (which is later identified toh) but this never occurs by Lemma 4.1.
In the second case, h′ < h. The arch′xh is established with RIGHTPRED or RIGHTCOMP
when the head of the top stack symbol ish′(instantiated dummy node is later filled withh). In both cases, ifhcollects its left children first, that means a subtree rooted ath(the top stack symbol) with left children is substituted to the dummy node with RIGHTCOMP (see Figure 4.5). However, this situation is prohibited by Lemma 4.1. The oracle instead collects left children ofhwith successive LEFTCOMPs. This occurs dues to the oracle’s preference for LEFTCOMPover LEFTPRED. Other notes
• The property of binarization above also indicates that the designed oracle is optimal in terms of stack depth, i.e., it always minimizes the maximum stack depth for a dependency tree, since it will minimize the number of turning points of the zig-zag path.
• If we construct another oracle algorithm, we would have different properties regarding im-plicit binarization, in which case Lemma 4.1 would not be satisfied.
• Combining the result in Section 4.3.2 about the transparency between the stack depth of the transiton system and the left-corner PDA, it is obvious that at each step of this oracle, the incurred stack depth to recognize a dependency tree equals to the stack depth incurred by the left-corner PDA during recognizing the CFG parse given by the presented binarization.
• In Section 4.4, we use this oracle to evaluate the ability of the left-corner parser to recognize natural language sentences within small stack depth bound. Note if our interest is just to examine rarity of center-embedded constructions, that is possible without running the oracle in entire sentences, by just counting the degree of center-embedding of the binarized CFG parses. The main reason why we do not employ such method is because our interests are not limited to rarity of center-embedded constructions but also lie in the relative performance of the left-corner parser to capture syntactic regularities among other transition-based parsers, such as the arc-eager parser. This comparison seems more meaningful when we run every transition system on the same sentences. To make this comparison clearer, we next give more detailed analysis on the stack depth behavior of our left-corner transition system.