This algorithm handles global structures, such as clause and coordination, better than shift-reduce or other bottom-up algorithms.

length, comparing with top-down, 2nd-MST and shift-reduce parsers (beam size: 8, pred size: 5)

We also implemented and experimented Huang and Sagae (2010)’s arc-standard shift-reduce parser.

We used an early update version of averaged perceptron algorithm (Collins and Roark, 2004) for training of shift-reduce and top-down parsers.

Transition-based parsing algorithms, such as shift-reduce algorithms (Nivre, 2004; Zhang and Clark, 2008), are widely used for dependency analysis because of the efficiency and comparatively good performance.

(2004) pointed out that the drawbacks of shift-reduce parser could be resolved by incorporating top-down information such as root finding.

This work presents an 0(n2) top-down head-driven transition-based parsing algorithm which can parse complex structures that are not trivial for shift-reduce parsers.

Yamada and Matsumoto (2003) applied a shift-reduce algorithm to dependency analysis, which is known as arc-standard transition-based algorithm (Nivre, 2004).

Table 2: Features for the shift-reduce parser (SRP) and the graph-based maximum spanning tree (MST) parser.

The Shift-Reduce parser (SRP; Section 4.1) and the graph-based, maximum spanning tree parser (MST; Section 4.2) are compared to these baselines.

In terms of labeled attachment score, both dependency parsing models outperformed the baseline models — the maximum spanning tree parser achieved 0.614 LAS, and the shift-reduce parser achieved 0.647 LAS.

The shift-reduce parser (SRP) trains a machine learning classifier as the oracle 0 E (C —> T) to predict a transition 75 from a parser configuration 0 2 (L1, L2, Q, E), using node features such as the heads of L1, L2 and Q, and edge features from the already predicted temporal relations in E. The graph-based maximum spanning tree (MST) parser trains a machine learning model to predict SCORE(e) for an edge e = (107;, rj, wk), using features of the nodes w, and wk.

Note that both models share features that look at the nodes, while only the shift-reduce parser has features for previously classified edges.

We consider two different approaches to learning a temporal dependency parser: a shift-reduce model (Nivre, 2008) and a graph-based model (McDonald et al., 2005).

4.1 Shift-Reduce Parsing Model

Shift-reduce dependency parsers start with an input queue of unlinked words, and link them into a tree by repeatedly choosing and performing actions like shifting a node to a stack, or popping two nodes from the stack and linking them.

A similar idea of equivalent states is used by Huang and Sagae (2010), except they use equivalence to facilitate dynamic programming for shift-reduce parsing, whereas we generalize it for improving the processing time of similar hypotheses in general models.

We use the best-first probabilistic shift-reduce dependency parser of Sagae and Tsujii (2007), a transition-based parser (Kubler et al., 2009) with a MaXEnt classifier.

Algorithm 1 Best—first shift-reduce dependency parsing

While Huang and Sagae (2010) use the notion of “equivalent states”, they do so for dynamic programming in a shift-reduce parser to broaden the search space.