The system reuses standard techniques for building projective trees by combining adjacent nodes (representing subtrees with adjacent yields), but adds a simple mechanism for swapping the order of nodes on the stack, which gives a system that is sound and complete for the set of all dependency trees over a given label set but behaves exactly like the standard system for the subset of projective trees.

This is not the case for the tree in Figure l, where the subtrees rooted at node 2 (hearing) and node 4 (scheduled) both have discontinuous yields.

The fact that we can swap the order of nodes, implicitly representing subtrees , means that we can construct non-projective trees by applying

LEFT-ARC; or RIGHT-ARC; to subtrees whose yields are not adjacent according to the original word order.

This algorithm proceeds in top-down fashion by sampling individual split points using the marginal probabilities of all possible subtrees .

To do so directly would involve simultaneously marginalizing over all possible subtrees as well as all possible alignments between such subtrees when sampling upper-level split points.

For every pair of nodes n1 6 T1,n2 6 T2, a table stores the marginal probability of the subtrees rooted at m and 712, respectively.

From a binary bracketing instance, we derive a unary bracketing instance ((9,710,119)), ignoring the subtrees 7(cz-nj) and flog-+1.19).

These features are to capture the relationship between a source phrase 3 and 7(3) or 7(3)’s subtrees .

There are three different scenarios3: l) exact match, where 3 exactly matches the boundaries of 7(3) (figure 3(a)), 2) inside match, where 3 exactly spans a sequence of 7(3)’s subtrees (figure 3(b)), and 3) crossing, where 3 crosses the boundaries of one or two subtrees of 7(3) (figure 3(c)).

The source phrase 32 exactly spans two subtrees VV and AS of VP, therefore CBMF is “VP-I”.