1 Introduction
Since the mid-1980s, unification-based grammars have been studied by many researchers as a device for providing precise and in-depth analyses based on linguistic theories, such as head-driven phrase structure grammar (HPSG) (Pollard and Sag Reference Pollard and Sag1994), lexical functional grammar (LFG) (Bresnan and Kaplan Reference Bresnan, Kaplan and Bresnan1982) and combinatory categorial grammar (CCG) (Steedman Reference Steedman2000). As a numerical model for selecting the best parse tree, conditional random fields for a packed parse forest have been used for probabilistic unification-based grammars (Geman and Johnson Reference Geman and Johnson2002; Miyao and Tsujii Reference Miyao and Tsujii2002; Kaplan et al. Reference Kaplan, Riezler, King, Maxwell and Vasserman2004; Clark and Curran Reference Clark and Curran2004b), and its parsing is empirically known to be fast and accurate (Clark and Curran Reference Clark and Curran2004a; Miyao and Tsujii Reference Miyao and Tsujii2005; Ninomiya et al. Reference Ninomiya, Matsuzaki, Tsuruoka, Miyao and Tsujii2006; Ninomiya et al. Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007). Both estimation and parsing with the packed parse forest, however, have an inherent problem that derives from the restriction of locality. Feature functions can only be defined for local structures, which limit the parser's accuracy. This is because parsers segment parse trees into constituents and factor equivalent constituents into a single constituent (edge) in a chart. However, this problem has not been adequately studied in unification-based grammar parsing, where only a few studies exist, i.e., a method of sampling for estimating parameters (Malouf and van Noord Reference Malouf and van Noord2004), and selective n-best unpacking (Zhang, Oepen and Carroll Reference Zhang, Oepen and Carroll2007).
This paper discusses our investigations into a transition-based parsing approach to unification-based grammars without the mechanisms of the packed parse forest. The transition-based parsing for context-free grammar (CFG) trees or dependencies has recently been studied (Ratnaparkhi Reference Ratnaparkhi1997; Yamada and Matsumoto Reference Yamada and Matsumoto2003; Collins and Roark Reference Collins and Roark2004; Nivre and Scholz Reference Nivre and Scholz2004; Sagae and Lavie Reference Sagae and Lavie2005; Sagae and Lavie Reference Sagae and Lavie2006; Zhang and Clark Reference Zhang and Clark2009) through approaches that are essentially based on deterministic parsing, in which global features can be easily defined for the entire structures of partial parse trees that have been built thus far in the process of parsing. The main advantage of this approach is that it can achieve simple and fast parsing by accurately choosing a search path with a large number of local and global features. Its current accuracy is competitive with that of state-of-the-art CFG parsers, and it is one of the most promising methodologies thus far. These techniques, however, cannot simply be applied to unification-based grammar parsing because it can fail as a result of its hard constraints in the grammar. Therefore, we propose deterministic parsing for unification-based grammars by using default unification, which almost always succeeds in unification by overwriting inconsistent constraints in the grammars such that the amount of overwriting is minimized. Because parsing failure is caused by unification failure of grammar constraints, default unification enables us to almost always succeed in parsing an entire sentence. Deterministic shift-reduce parsing itself is simple without the mechanism of the packed parse forest. This enables us to write global feature functions flexibly. We further pursue the best-first shift-reduce parsing for unification-based grammars by introducing nondeterminism in the same way as Sagae and Lavie (Reference Sagae and Lavie2006). The experiments revealed that deterministic parsing with default unification achieved a high degree of accuracy of 87.6 per cent for the Penn Treebank with gold part-of-speech (POS) tags. The best-first parsing with a beam search achieved the best accuracy of 87.0 per cent in settings with normal unification. Default unification further increased accuracy from 87.0 to 88.4 per cent. The experimental results with a very wide beam indicate that our deterministic parsing has the potential to reach the accuracy of state-of-the-art parsers due to its deterministic mechanism that offers flexibility in its feature design.
Section 2 describes the background and related works on unification-based grammar parsing and transition-based parsing. Section 3 explains unification-based grammars and Section 4 explains default unification. Shift-reduce parsing for unification-based grammars is presented in Section 5. Section 6 discusses our experiments and Section 7 concludes the paper.
2 Background and related work
Developing a unification-based grammar parser for parsing real-world text has been difficult for a long time because of the difficulty of developing grammars and the absence of well-defined numerical models for selecting the best parse tree in unification-based grammars. The problem with grammar development was overcome by using a method of constraint ranking for manually tailored LFG grammars (Butt et al. Reference Butt, King, Niño and Segond1999; Frank et al. Reference Frank, King, Kuhn, Maxwell and Sells2001) and corpus-based methods, through which consistent and robust unification-based grammars could be acquired from a CFG-style annotated corpus (Hockenmaier and Steedman Reference Hockenmaier and Steedman2002; O'Donovan et al. Reference O'Donovan, Burke, Cahill, van Genabith and Way2004; Clark and Curran Reference Clark and Curran2004b; Miyao, Ninomiya and Tsujii Reference Miyao, Ninomiya, Tsujii, Su, , Lee and Kwong2005). The problem with numerical models was solved by using a probabilistic model for unification-based grammars. Previous studies (Abney Reference Abney1997; Johnson et al. Reference Johnson, Geman, Canon, Chi and Riezler1999; Riezler et al. Reference Riezler, Prescher, Kuhn and Johnson2000; Geman and Johnson Reference Geman and Johnson2002; Miyao and Tsujii Reference Miyao and Tsujii2002; Toutanova et al. Reference Toutanova, Manning, Shieber, Flickinger and Oepen2002; Kaplan et al. Reference Kaplan, Riezler, King, Maxwell and Vasserman2004; Malouf and van Noord Reference Malouf and van Noord2004; Clark and Curran Reference Clark and Curran2004b) defined a probabilistic model of unification-based grammars, including HPSG, LFG and CCG, as conditional random fields for parse trees, which provided the probabilities of discriminating a correct parse tree from candidate parse trees in a multi-class logistic regression (also known as, a log-linear or maximum entropy model) with many features for parse trees.
Conditional random fields for packed parse trees have been used successfully for probabilistic unification-based grammars (Geman and Johnson Reference Geman and Johnson2002; Miyao and Tsujii Reference Miyao and Tsujii2002; Kaplan et al. Reference Kaplan, Riezler, King, Maxwell and Vasserman2004; Clark and Curran Reference Clark and Curran2004b), and their parsing has empirically been known to be fast and accurate, especially with supertagging (Clark and Curran Reference Clark and Curran2004a; Ninomiya et al. Reference Ninomiya, Matsuzaki, Tsuruoka, Miyao and Tsujii2006, Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007). Both estimation and parsing with the packed parse forest, however, raise an inherent problem that derives from the restriction of locality. Feature functions can only be defined for local structures, which limit the parser's accuracy. This is because parsers segment parse trees into constituents and factor equivalent constituents into a single constituent (edge) in a chart. However, this problem has not been adequately studied in unification-based grammar parsing, where only a few studies exist, i.e., a method of sampling for estimating parameters (Malouf and van Noord Reference Malouf and van Noord2004), and selective n-best unpacking (Zhang et al. Reference Zhang, Oepen and Carroll2007).
In many studies on CFG parsing, several approaches, such as reranking (Collins Reference Collins2000; Charniak and Johnson Reference Charniak and Johnson2005; Huang Reference Huang2008), transition-based parsing (Ratnaparkhi Reference Ratnaparkhi1997; Yamada and Matsumoto Reference Yamada and Matsumoto2003; Collins and Roark Reference Collins and Roark2004; Nivre and Scholz Reference Nivre and Scholz2004; Sagae and Lavie Reference Sagae and Lavie2005, Reference Sagae and Lavie2006; Zhang and Clark Reference Zhang and Clark2009), learning as search optimization (Daumé and Marcu Reference Daumé and Marcu2005) and sampling methods (Nakagawa Reference Nakagawa2007) have been studied to solve the problem of locality. The reranking methods rerank the n-best unpacked parse trees obtained from a packed parse forest, but these kinds of methods inherently suffer from two drawbacks; first, the accuracy of reranking greatly depends on the precision of first-stage parsing, which only uses local features, and second, the correct answer can slip from the list of the n-best candidates; e.g., around 40 per cent of the correct parse trees did not exist in the 30-best candidates (Collins Reference Collins2000). Huang Huang (Reference Huang2008) proposed a fine-grained method of reranking, which tried to process the reranking and enumeration of n-best candidates simultaneously by extracting the n-best partial parse trees for each node in the packed parse forest. Huang's method enables approximate reranking of the packed parse forest with non-local features, but it is limited by the beam search and the enumeration of partial parse trees instead of locality restriction.
The transition-based parsing, including incremental parsing with a perceptron (Collins and Roark Reference Collins and Roark2004), shift-reduce parsing (Yamada and Matsumoto Reference Yamada and Matsumoto2003; Sagae and Lavie Reference Sagae and Lavie2005; Sagae and Lavie Reference Sagae and Lavie2006; Zhang and Clark Reference Zhang and Clark2009) and dependency parsing (Nivre and Scholz Reference Nivre and Scholz2004), has intensively been studied as an empirical method of parsing natural languages. It regards the parsing problem as a search problem of how to choose the parser's action in which the scores for choosing the parser's action are associated with the history of the parsing process, such as previous parsing actions and partial parse trees that have been built thus far. One advantage of this approach is that it can achieve simple and fast parsing by accurately choosing a search path. For example, Sagae and Lavie (Reference Sagae and Lavie2005) have shown that deterministic shift-reduce parsing can be highly efficient and accurate by using a large number of local and global features extracted from entire structures of unambiguous partial parse trees, which have been deterministically built during the parsing process. Likewise, parsing methods in recent studies on the transition-based parsing have assumed that each parsing state retains its own unambiguous partial parse trees to extract global features, and have not assumed a packed parse forest. They have introduced nondeterminism simply by processing parsing states in parallel (Sagae and Lavie Reference Sagae and Lavie2006). This means that its hypothesis space becomes exponentially larger because the intermediate results are not shared among parsing states. However, this approach enables us to extract global features that can greatly contribute to choosing a better search path. Collins and Roark's (Reference Collins and Roark2004) incremental parsing and Zhang and Clark's (Reference Zhang and Clark2009) shift-reduce parsing nondeterministically optimized their global discrimination models by using a perceptron. Their probabilistic models and search strategies were different from Sagae and Lavie's methods, but these were also based on ‘deterministic parsing,’ i.e., these did not use the packed parse forest, each parsing state retained its own parsing history and their parsing order was fixed from left to right. The transition-based parsing currently achieves competitive accuracy with state-of-the-art parsers in analyzing CFG trees or dependencies, and is one of the most promising methodologies thus far. These methods, however, cannot simply be applied to unification-based grammar parsing because it can fail as a result of its hard constraints in the grammar. Even though parsing failure can be recovered by nondeterministically exploring the search space, it is hard to find a search path that produces a parse tree that satisfies all grammar constraints because its hypothesis space is exponentially large.
There have been several studies related to our work. The nondeterministic shift-reduce parsing for unification-based grammars has been studied by Briscoe and Carroll (Reference Briscoe and Carroll1993b). However, their algorithm works nondeterministically with the mechanism of the packed parse forest, and hence it has the problem of locality in the packed parse forest. Bouma (Reference Bouma1990) exemplified the application of grammar rules by default unification, in which some constraints in grammar rules were specified as default information. Optimality theory in LFG (Frank et al. Reference Frank, King, Kuhn, Maxwell and Sells2001) is also a sort of default-rule application for developing wide-coverage grammars and giving preference to parsing results. Constraints in a grammar rule are ordered in optimality theory, and the grammar writer can provide robust and specific controls for each language phenomenon corresponding to a constraint. The difference between our study and others is that (i) we used shift-reduce parsing, (ii) preferences were determined by a machine learning classifier and (iii) non-head daughters were specified as default information instead of default information being specified for each constraint in the grammar rules. Zhang et al. (Reference Zhang, Oepen and Carroll2007) proposed selective n-best unpacking for unification-based grammars. Using the same approach as Huang Huang (Reference Huang2008), they tried to process the reranking and enumeration of n-best candidates simultaneously by extracting the n-best partial parse trees for each node in the packed parse forest. Their method provided precise reranking of the packed parse forest with non-local features, but it was limited by the types of non-local features. There is a trade-off between the decoding time and the types of non-local features. If further non-local features were used, exact decoding would be difficult within a reasonable time.
3 Unification-based grammars
A unification-based grammar is defined as a pair consisting of a set of lexical entries and a set of grammar rules. The lexical entries express word-specific characteristics, while the grammar rules describe constructions of constituents in parse trees. Both the grammar rules and the lexical entries are represented by feature structures (Carpenter Reference Carpenter1992), and constraints in the grammar are forced by unification. Of the grammar rules, a binary rule is a partial function: F × F → F, where F is the set of all possible feature structures. The binary rule takes two partial parse trees as daughters and returns a larger partial parse tree that consists of the daughters and their mother. A unary rule is a partial function: F → F, which corresponds to a unary branch.
In the experiments, we used an HPSG (Pollard and Sag Reference Pollard and Sag1994), which is one of the most sophisticated unification-based grammars in linguistics. An HPSG generally has a small number of grammar rules and a large number of lexical entries where a head daughter is determined for each binary rule. Let H be a partial parse tree corresponding to a head daughter and NH a partial parse tree corresponding to a non-head daughter. The binary rule and unary rule are defined as
where R is a feature structure corresponding to a binary/unary rule, and F ⊔ G returns the result of the unification of feature structures F and G. In what follows, we write ⊥ for the most general type, F ⊔ G for the unification of two feature structures, F ⊓ G for the generalization of two feature structures and F ⊑ G for subsumption relations, in which G is more specific than or equal to F (F is more general than or equal to G)Footnote 1.
Feature structures in an HPSG are strictly typed. Let type be a finite set of types that are partially ordered according to their specificity. We write σ ⊔ τ for the type unification of two types, and σ ⊑ τ for subsumption relations in which τ is more specific than or equal to σ. The type unification of two types, σ ∈ type and τ ∈ type, is defined as their least upper bound, i.e., the most general type γ ∈ type such that σ ⊑ γ and τ ⊑ γ. Figure 1 has an example of partially ordered types, in which the types in the upper positions are more specific than the types in the lower positions. The type unification of d and b returns h because d and b have in common more specific types (h and i) and h is the most general type. However, the type unification of c and b fails because c and b do not have in common more specific types. Each node in the typed feature structures is assigned a single type in type. In the process of unifying two feature structures, a pair of two nodes is unified one by one through type unification. If type unification fails at any point during the unification, the latter also returns unification failure as a result.
Example of partially ordered types.
Figure 2 shows an example of HPSG parsing of the sentence, ‘Spring has come’. The left side of the figure shows a partial parse tree for ‘has come’, which is obtained by unifying each of the lexical entries for ‘has’ and ‘come’ with a daughter feature structure of the head-complement rule. Larger partial parse trees are obtained by repeatedly applying phrase-structure rules to lexical/phrasal partial parse trees. Suppose the subject-head rule is
![\[
g(NH, H) = \fs{\feat{HEAD:}\reent{1}\\
\feat{SUBJ:}\reent{3}\\
\feat{COMPS:}\langle \rangle\\
\feat{DTRS:}\fs{\feat{H:}\fs{\feat{HEAD:}\reent{1}\\
\feat{SUBJ:}\langle\reent{2}|\reent{3}\rangle\\
\feat{COMPS:}\langle \rangle}\\
\feat{NH:}\reent{2}}} \sqcup \fs{\feat{DTRS:H:} H} \sqcup \fs{\feat{DTRS:NH:} NH}\!.
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU2.gif?pub-status=live)
By applying it to the partial parse trees on the left of the figure, a larger partial parse tree is obtained, as on the right. Finally, the parse results in output as a parse tree that dominates the sentence. We have written gR(H, NH) = R ⊔ H ⊔ NH for the binary rules in what follows for simplicity.
Example of HPSG parsing.
We used Enju, a treebank grammar of an HPSG for English (Miyao et al. Reference Miyao, Ninomiya, Tsujii, Su, , Lee and Kwong2005), in the experiments. Enju is a sort of treebank grammar; the lexicon of Enju is semiautomatically developed from a CFG-style treebank. Therefore, it is occasionally considered to be a data-driven parsing grammar, such as a probabilistic context-free grammar (PCFG), but Enju is more theoretically and linguistically developed than PCFGs or simple dependency grammars. Enju was developed by using a corpus-oriented method of grammar development (Miyao et al. Reference Miyao, Ninomiya, Tsujii, Su, , Lee and Kwong2005), in which the grammar rules were developed manually, and the lexicon was automatically developed from an HPSG treebank by harvesting leaves in the treebank. The crux of this method of grammar development was how to develop an HPSG treebank that satisfied the grammar constraints defined in the original HPSG. An HPSG treebank was developed as follows: an existing CFG-style treebank was first converted to a primitive HPSG treebank, and then the primitive HPSG treebank was specialized so that it satisfied the grammar constraints in the grammar rules by applying them to each branch. Nonterminal/terminal symbols in the CFG-style treebank were converted to phrasal/lexical feature structures in the primitive HPSG treebank so that they satisfied the constraints represented by symbols in the CFG-style treebank. Tree skeletons in the CFG-style treebank were also changed to tree skeletons that conformed with the HPSG theory. Other constraints that could be inferred from the primitive HPSG treebank were also added to the primitive HPSG treebank, such as wh-phrases and a grammar rule name for each branch. Finally, the primitive HPSG treebank was constrained by the grammar rules. Consequently, constraints derived from the nonterminal/terminal symbols were strictly checked in the derived HPSG treebank as to whether they conformed with the HPSG theory through constraints imposed by the grammar rules. For example, a noun phrase having a verb head word was strictly prohibited by the head feature principle, i.e., constraints had to have the same category between a mother and a head daughter in the grammar rules.
4 Default unification
Default unification was investigated in a series of studies that involved robust parsing by unification-based grammars and lexical semantics in order to deal with default inheritance in a lexicon (Bouma Reference Bouma1990; Briscoe Reference Briscoe, Briscoe, de Paiva and Copestake1993a; Ninomiya, Miyao and Tsujii Reference Miyao and Tsujii2002). This is advantageous to achieve robust processing, because (i) it almost always succeeds and (ii) a feature structure is relaxed such that the amount of information is maximized (Bouma Reference Bouma1990; Ninomiya et al. Reference Ninomiya, Miyao and Tsujii2002). We tested a simplified version of Copestake's (Reference Copestake, Briscoe, de Paiva and Copestake1993) default unification in our experiments. Before explaining this, let us first explain Carpenter's two definitions of default unification (Carpenter Reference Carpenter, Briscoe, de Paiva and Copestake1993).
4.1 Carpenter's default unification
Carpenter proposed the following two types of default unification (Carpenter Reference Carpenter, Briscoe, de Paiva and Copestake1993):
Credulous default unification
Skeptical default unification
F is called a strict feature structure, whose information must not be lost, and G is called a default feature structure, whose information can be lost, although this needs to be as limited as possible so that F and G can be unified.
Credulous default unification (1) is greedy, in that it tries to maximize the amount of information from the default feature structure, but it does result in a set of feature structures. Skeptical default unification (2) simply generalizes the set of feature structures resulting from credulous default unification. Skeptical default unification thus leads to a unique result so that there remains the default information that can be found in every result for credulous default unification. The following is an example of skeptical default unification:
4.2 Copestake's default unification
Copestake (Reference Copestake, Briscoe, de Paiva and Copestake1993) mentioned that the problem with Carpenter's default unification (1 and 2) is its time complexity. Carpenter's default unification takes exponential time to find the optimal answer because it requires the unifiability of the power set of constraints to be checked in a default feature structure. Copestake (Reference Copestake, Briscoe, de Paiva and Copestake1993) thus proposed the following definition of default unification. Let PV(G) be a function that returns a set of path values in G, and let PE(G) be a function that returns a set of path equations, i.e., information about structure-sharing in G.
Copestake's default unification
where H = F ⊔ ⨆ PE(G). It forces to first unify all path equations in the default feature structure, then all path values that are consistent with the strict feature structure and all other path values are unified. Copestake's default unification returns the following result for the example in (3):
![\[\fs{\feat{F:} \ftype{a}\\} \adu \fs{ \feat{F:} \reent{1}\ftype{b}\\
\feat{G:} \reent{1}\\
\feat{H:} \ftype{c}\\ }= \fs{ \feat{F:} \reent{1}\ftype{a}\\
\feat{G:} \reent{1}\\
\feat{H:} \ftype{c}\\ }
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU3.gif?pub-status=live)
Copestake's default unification can fail if one of the path equations in the default feature structure is not consistent with the strict feature structure. The following is an example for which Carpenter's default unification returns an answer but Copestake's default unification fails:
![\[
\begin{array}{lr}
\fs{ \feat{F:} \ftype{a}\\
\feat{G:} \ftype{b}\\ } \sdu \fs{ \feat{F:} \reent{1}\\
\feat{G:} \reent{1}\\
\feat{H:} \ftype{c}\\ } = \fs{ \feat{F:} \ftype{a}\\
\feat{G:} \ftype{b}\\
\feat{H:} \ftype{c}\\ } & \mbox{(Carpenter)}\\
\fs{ \feat{F:} \ftype{a}\\
\feat{G:} \ftype{b}\\ } \adu \fs{ \feat{F:} \reent{1}\\
\feat{G:} \reent{1}\\
\feat{H:} \ftype{c}\\ } \mbox{ not defined} & \mbox{(Copestake)}
\end{array}
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU4.gif?pub-status=live)
Copestake's default unification (4) works efficiently. All path equations in the default feature structure are unified with the strict feature structures, and then the unifiability of path values is checked one by one for each node in the result of unifying the path equations. The algorithm for Copestake's default unification runs as fast as normal unification, and can be executed even for feature structures that include cycles.
4.3 Typed version of Copestake's default unification
Copestake's default unification is well defined and works efficiently. When types are involved, however, it is not easy to find unifiable path values in the default feature structure. She introduced type decomposition function TypeDecomp(F, G) instead of path value function PV(F). Let F be 〈Q, q 0, δ, θ〉 and G be 〈Q′, q 0′, δ′, θ′〉, where Q is a set of feature structure nodes, q 0 is the root node, δ(f, q) is a partial function that returns a feature structure node reached by following f from q, and θ(q) is a type assignment function for q. TypeDecomp(F, G) is defined as
• If θ(q 0) ⊑ θ′(q 0′), then TypeDecomp(F, G) is the set of all feature structures, H = 〈Q″, q 0″, δ″, θ″〉 such that:
— θ″(q 0″) = θ(q 0).
— If F has features, i.e., δ(f, q 0) is defined for some f, then δ″(f, q 0″) for some f such that δ(f, q 0) is defined is a member of TypeDecomp(δ(f, q 0), δ′(f, q 0′)) and δ″(f′, q 0″) for all f′ ≠ f is not defined.
• If θ(q 0) ⋢ θ′(q 0′), then TypeDecomp(F, G) = {F}.
The typed version of Copestake's default unification is defined as
where H = F ⊔ ⨆ PE(G) and D is TypeDecomp(⊔ PV(G), F). In the typed version, TypeDecomp(⊔ PV(G), F) is used instead of PV(G), and it returns a set of feature structures. A feature structure returned by TypeDecomp(⊔ PV(G), F) is constructed by following and copying a path on ⊔ PV(G), and following the same path on F simultaneously. If type σ on a current node on ⊔ PV(G) is neither more general than nor equal to type τ on a current node on F, i.e., σ ⋢ τ, then the remaining feature structure on ⊔ PV(G) is attached to the end of the copied path. Intuitively, TypeDecomp(⊔ PV(G), F) returns a set of path values that are neither more general nor equal to the strict feature structure. The algorithm for this definition is more efficient than finding the optimal answer, and this definition is well suited to a grammar based on a type constraint system, in which each type is constrained with a bag of constraints. If a type in the default is not incorporated into the strict feature structure, then a bag of constraints defined with the type should also not be incorporated.
Suppose we have two feature structures as
where d ⊔ e is not defined and c ⊑ g. TypeDecomp(⊔ PV(G), F) is
![\[
\left\{
\fs{
\ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{e}}},
\fs{
\ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{G:}\ftype{f}}},
\fs{
\ftype{a}\\
\feat{G:}\fs{\ftype{g}\\
\feat{F:}\ftype{e}\\
\feat{G:}\ftype{f}}}
\right\}
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU5.gif?pub-status=live)
Thus, the result of the default unification of F and G becomes
![\[
F \adu G =
\fs{
\ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{d}\\
\feat{G:}\ftype{f}}\\
\feat{G:}\fs{\ftype{c}\\
\feat{F:}\ftype{d}\\
\feat{G:}\bot}}
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU6.gif?pub-status=live)
4.4 Simply typed version of Copestake's default unification
The typed version of Copestake's default unification (5) is suited to a type constraint system, but it assumes the acyclicity of feature structures, and still involves huge computational cost to find the compatible feature structures in TypeDecomp(⊔ PV(G), F). Therefore, we implemented a simply typed version of Copestake's default unification, which does not assume the acyclicity of feature structures, and runs as fast as normal unification.
Figure 3 has the algorithm by which we implemented the simply typed version. First, each node is marked ‘strict’, if it belongs to a strict feature structure, otherwise it is marked ‘default.’ The marked strict and default feature structures are unified by type-unconstrained unification. Type-unconstrained unification is a sort of unification but the types in the feature structure nodes are not unified but merged as a set of types, and hence type-unconstrained unification never fails. The following is an example of type-unconstrained unification of marked feature structures:
Then all types marked ‘strict’ are unified into one type for each node. If this fails, then default unification also returns unification failure as its result. Finally, each node is assigned a single type, which is the result of type unification for all types marked both “default' and ‘strict,’ if it succeeds, otherwise all types marked only ‘strict.’ otherwise Supposing that t ⊑ u, a ⊔ b = e and e ⊔ c is not defined, the result for the above example (7) becomes
![\[
\fs{\ftype{t}\\
\feat{F:} \ftype{a}\\
\feat{G:} \ftype{b}\\} \sadu \fs{ \ftype{u}\\
\feat{F:} \reent{1}\ftype{c}\\
\feat{G:} \reent{1}\\
\feat{H:} \ftype{d}\\ }= \fs{ \ftype{u}\\
\feat{F:} \reent{1}\ftype{e}\\
\feat{G:} \reent{1}\\
\feat{H:} \ftype{d}\\ }\!.
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU7.gif?pub-status=live)
Algorithm for the simply typed version of Copestake's default unification.
The following example illustrates the difference in behaviour between the typed version and the simply typed version for the two feature structures in (6):
![\[
\begin{array}{lr} \fs{ \ftype{a}\\
\feat{F:}\fs{\ftype{b}\\\feat{F:}\ftype{d}\\\feat{G:}\bot}\\
\feat{G:}\fs{\ftype{c}\\
\feat{F:}\ftype{d}\\
\feat{G:}\bot}} \adu \fs{ \ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{e}\\
\feat{G:}\ftype{f}}\\
\feat{G:}\fs{\ftype{g}\\
\feat{F:}\ftype{e}\\
\feat{G:}\ftype{f}}}= \fs{ \ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{d}\\
\feat{G:}\ftype{f}}\\
\feat{G:}\fs{\ftype{c}\\
\feat{F:}\ftype{d}\\
\feat{G:}\bot}} & \mbox{\small (Typed version, Copestake)}\\
\fs{ \ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{d}\\
\feat{G:}\bot}\\
\feat{G:}\fs{\ftype{c}\\
\feat{F:}\ftype{d}\\
\feat{G:}\bot}} \sadu \fs{ \ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{e}\\
\feat{G:}\ftype{f}}\\
\feat{G:}\fs{\ftype{g}\\
\feat{F:}\ftype{e}\\
\feat{G:}\ftype{f}}}= \fs{ \ftype{a}\\
\feat{F:}\fs{\ftype{b}\\
\feat{F:}\ftype{d}\\
\feat{G:}\ftype{f}}\\
\feat{G:}\fs{\ftype{g}\\
\feat{F:}\ftype{d}\\
\feat{G:}\ftype{f}}} & \mbox{\small (Simply typed version)}\\
\end{array}
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary-alt:20160626184246-59598-mediumThumb-S1351324910000240_eqnU8.jpg?pub-status=live)
where d ⊔ e is not defined and c ⊑ g. The simply typed version greedily tries to unify types for each node in the default feature structure, but the typed version tries to unify decomposed parts of the default feature structure. In the example above, the feature structure reached by following feature G: from the root node of the default feature structure is a decomposed part of the default feature structure. The typed version does not unify this decomposed part because the type e in the decomposed part is inconsistent with the type d in the strict feature structure. The simply typed version greedily unifies the type g and f in the decomposed part with the strict feature structure.
4.5 Ninomiya et al.'s default unification
Ninomiya et al. (Reference Ninomiya, Miyao and Tsujii2002) proposed another definition of default unification. It first unified the strict and default feature structures through type-unconstrained unification. Then, each node with inconsistent types was coerced to have the most general type, and was marked with ‘failpoint.’ All structure-sharings on the path that led to the fail points were unfolded. Finally, the strict feature structure was unified with it by normal unification. Ninomiya et al.'s (Reference Ninomiya, Miyao and Tsujii2002) default unification assumed two reasons for unification failure. The first involved the types on the failpoints, and the second involved the structure-sharings on the path that led to the failpoints. Their algorithm generalized the type on the failpoints and removed all structure-sharings on the path to the failpoints. Copestake's default unification forced all path equations to be unified with the strict feature structure, and hence default unification failed if a path equation in the default was inconsistent with the strict feature structure. However, Ninomiya et al.'s (Reference Ninomiya, Miyao and Tsujii2002) default unification always succeeds because it relaxes path equations. Suppose grammar rule R and daughters DTR are given as
![\[
R = \fs{\feat{HEAD:}\reent{1}\\
\feat{DTRS:}\fs{\feat{H:}\reent{2}\fs{\feat{HEAD:}\reent{1}\ftype{head}}\\
\feat{NH:SPR:}\reent{2}}}
\]
\[ DTR = \fs{\feat{DTRS:}\fs{\feat{H:HEAD:CASE:}\ftype{obj}\\
\feat{NH:SPR:HEAD:CASE:}\ftype{nom}}}.
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022070737819-0757:S1351324910000240_eqnU9.gif?pub-status=live)
Also Suppose the type head has PHON:, CASE:, and INV: as its features, and the type sign has HEAD: and VAL:. Copestake's default unification results in unification failure because all structure-sharings in R are forced to unify with DTR. Ninomiya et al.'s (Reference Ninomiya, Miyao and Tsujii2002) default unification returns much more informative results as follows:
![\[
DTR \ndu R = \fs{\feat{HEAD:}\fs{\ftype{head}\\
\feat{PHON:}\reent{3}\\
\feat{CASE:}\bot\\
\feat{INV:}\reent{4}}\\
\feat{DTRS:}\fs{\feat{H:}\fs{\ftype{sign}\\
\feat{HEAD:}\fs{\ftype{head}\\
\feat{PHON:}\reent{3}\\
\feat{CASE:}\ftype{obj}\\
\feat{INV:}\reent{4}}\\
\feat{VAL:}\reent{5}}\\
\feat{NH:SPR:}\fs{\ftype{sign}\\
\feat{HEAD:}\fs{\ftype{head}\\
\feat{PHON:}\reent{3}\\
\feat{CASE:}\ftype{nom}\\
\feat{INV:}\reent{4}}\\
\feat{VAL:}\reent{5}}}}
\]](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary-alt:20160626184243-35551-mediumThumb-S1351324910000240_eqnU10.jpg?pub-status=live)
The information on structure-sharings is preserved as much as possible. In the example, the structure-sharing tagged as 
in original grammar rule R is decomposed into the structure-sharing 
. However, Ninomiya et al.'s (Reference Ninomiya, Miyao and Tsujii2002) default unification cannot be applied to cyclic feature structures. In the preliminary experiments (Section 6.2), cyclic feature structures were coerced to be acyclic by eliminating feature pointers that form cycles.
5 Shift-reduce parsing for unification-based grammars
This section explains our shift-reduce parsing algorithms, which are based on deterministic shift-reduce CFG parsing (Sagae and Lavie Reference Sagae and Lavie2005) and best-first shift-reduce CFG parsing (Sagae and Lavie Reference Sagae and Lavie2006). Sagae and Lavie's parser selected the most probable shift/reduce actions and non-terminal symbols without assuming explicit CFG rules. Therefore, their parser could proceed deterministically without failure. However, a deterministic parser for unification-based grammars can fail as a result of its hard constraints in the grammar. We propose three new shift-reduce parsing approaches to unification-based grammars: deterministic shift-reduce parsing and shift-reduce parsing by backtracking and a best-first search. The major difference between our algorithm and Sagae and Lavie's algorithm is that we use default unification. First, let us explain the deterministic shift-reduce parsing algorithm and then shift-reduce parsing with backtracking and a best-first search.
5.1 Deterministic shift-reduce parsing for unification-based grammars
The deterministic shift-reduce parsing algorithm for unification-based grammars is mainly composed of two data structures: a stack, S, and a queue, W. Items in S are partial parse trees, including a lexical entry, and a parse tree that dominates the whole input sentence. Items in W are words and POS tags in the input sentence. The algorithm defines two types of parser actions, shift and reduce, which are as follows
Shift.. A shift action removes the first item (a word and a POS tag) from W. Then, one lexical entry is selected from the candidate lexical entries for the item. Finally, the selected lexical entry is placed on the top of the stack.
Binary Reduce. A binary reduce action removes two items from the top of the stack. Then, partial parse trees are derived by applying binary rules to the first removed item as a right daughter and a left daughter as the second removed item. Of the candidate partial parse trees, one is selected and placed on the top of the stack.
Unary Reduce. A unary reduce action removes one item from the top of the stack. Then, partial parse trees are derived by applying unary rules to the removed item. Of the candidate partial parse trees, one is selected and placed on the top of the stack.
Parsing fails if there are no candidates for selection (i.e., a dead end). Parsing is considered to have successfully finished when W is empty and S has only one item that satisfies the sentential condition: the category is verb and the subcategorization frame is empty. Parsing is considered to be a nonsentential success when W is empty and S has only one item that does not satisfy the sentential condition.
Figure 4 has an example of deterministic shift-reduce HPSG parsing of the sentence, ‘Spring has come.’ First, shift actions are selected thrice. A lexical entry is selected for each word and placed on the top of the stack. Then, the top two elements in the stack are reduced by unifying them with the head-complement rule. Finally, a parse tree is obtained on the top of the stack by applying a reduce action to the top two elements by unifying them with the head-subject rule.
Example of deterministic shift-reduce parsing for HPSG.
We used a multi-class logistic regression classifier (also known as a maximum entropy or log-linear model) in our experiments to choose the parser's action. Table 1 lists the feature templates for the classifier, and Table 2 lists the combinations of feature templates. The implemented classifier had sixty-two feature templates, 155 combinations of feature templates, and 1,806,069 features. Many of these features were taken from those used in Ninomiya et al.'s (Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007), Miyao and Tsujii's (Reference Miyao and Tsujii2005), and Sagae and Lavie's (Reference Sagae and Lavie2005) parsers, including global features defined over the information in the stack, which cannot be used in parsing with the packed parse forest. The global features are specifically those including feature templates Sw(i), Sp(i), Sl(i), Ssy(i), Shsy(i), Snsy(i), Shp(i), and Snp(i) such that i ≥ 1. The number of feature template combinations, including global features, is fifty-two of 155. The features for selecting shift actions are the features used in the supertagger (Ninomiya et al. Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007) and the features used in Sagae and Lavie's (Reference Sagae and Lavie2005) parser. Our shift-reduce parsers can be regarded as an extension of the supertagger.
Feature templates
Combinations of feature templates
Deterministic parsing can fail because of its grammar's hard constraints. For example, Figure 5 shows parsing failure in the deterministic parsing of the sentence, ‘Spring has come.’ Deterministic parsing for this sentence fails because an incorrect lexical entry has been selected for the verb, ‘has,’ and consequently parsing fails due to the disagreement in number between the subject, ‘spring’, and the verb, ‘has.’ Because no result is returned when unification failure occurs and the process is deterministic, we cannot continue deterministic parsing. Consequently, we use default unification, which almost always succeeds in unification. We assume that a head daughter (or, an important daughter) is determined for each binary rule in the unification-based grammar. Default unification is used in applying a binary rule, in which a binary rule unified with the head daughter is the strict feature structure and the non-head daughter is the default feature structure, i.e., (R ⊔ H) 
NH, where R is a binary rule, H is a head daughter, and NH is a non-head daughter. We used a simply typed version of Copestake's default unification in applying the binary rule application in the experiments. Note that default unification was always used instead of normal unification in both the training and the evaluation of parsers using default unification. Although the simply typed version of Copestake's default unification almost always succeeds, the binary rule application can fail if the binary rule cannot be unified with the head daughter, or inconsistency is caused by path equations in the default feature structures. If the application of rules fails for all binary rules, backtracking or a best-first search can be used for recovery, as explained in Section 5.2. We had no failures in applying the binary rules with default unification in the experiments.
Example of parsing failure.
We also evaluated deterministic parsing with normal unification to evaluate the effect of default unification, and compared it with deterministic parsing with default unification. Deterministic parsing with normal unification can easily fail, and hence recall will greatly decrease if a parser outputs nothing when it fails. Therefore, we evaluated it as follows. First, we evaluated partial parse trees that were analyzed until parsing failed. Second, we let the parser continue parsing after it failed parsing a sentence. Specifically, parsing involves the following seven steps:
(1) Let P: = ∅.
(2) Do deterministic parsing with normal unification.
(3) If a fully connected sentential parse tree is the output, then return it.
(4) If a partial parse tree is the output, add it to P.
(5) If the right-most partial parse tree in P reaches the end of the sentence, then return P.
(6) Clear the stack, and continue parsing from the next position in the right- most partial parse tree.
(7) Go to 2.
This simple mechanism greatly improves the recall of deterministic parsing with normal unification even though the output is not a fully connected parse trees but partial parse trees. Note that proper grammatical constraints are enforced when using normal unification.
5.2 Shift-reduce parsing by backtracking and best-first search
Backtracking is one possible solution for recovering from parsing failure. When parsing fails or ends with nonsentential success, the parser's state reverts to some previous state (backtracking), and it chooses the second-best action and tries parsing again. A parser's state consists of a tree stack, a word queue – the same stack and queue as explained in the shift-reduce parsing algorithm – and a probability, which are sufficient information to restart parsing from any point of deterministic shift-reduce parsing. There are several metrics to choose a previous state as a restarting point, e.g., the smallest probability for transition, the smallest difference or ratio of probabilities for the top-ranked and second-ranked transitions, or the largest entropy in the transition candidates. We used the difference in probability between the top-ranked and the second-ranked transition candidates as the metric in this study, and the previous state with the smallest difference in probability was selected. Let us define the maximum number of backtracking steps while parsing a sentence. Backtracking repeats until parsing finishes with sentential success or reaches the maximum number of backtracking steps. When parsing finishes with sentential success, a fully connected parse tree is output. However, when parsing finishes, because the maximum number of backtracking steps has been reached, a fully connected nonsentential parse tree or a partial parse tree is output. When a partial parse tree is output, recall will greatly decrease because words located at the right side of the partial parse tree remain unanalyzed. Therefore, we let the parser continue parsing from the right side of the partial parse tree until a partial parse tree is reached at the end of the sentence. If parsing fails to find a fully connected parse tree, then the best continuous partial parse trees are output for evaluation. Parsing involves the following five specific steps:
(1) Let P: = ∅.
(2) Do deterministic parsing with normal unification/default unification.
• If a fully connected sentential parse tree is output, then return it.
• Add the output to P.
• If the number of backtracking steps reaches its maximum number, then go to 3.
• Backtrack parsing state, and go to 2.
(3) If the right-most partial parse tree reaches the end of the sentence, then return the best continuous partial parse trees from P.
(4) Clear the stack, and continue parsing from the next position in the right- most partial parse tree.
(5) Go to 2.
Note that this algorithm can be used for both deterministic parsing with normal unification and default unification.
From the viewpoint of search algorithms, parsing with backtracking is a sort of depth-first search algorithm. Another possibility is to use the best-first search algorithm. The best-first parser has a state priority queue. Parsing continues by applying shift-reduce actions to the best state in the state queue. First, the best state is removed from the state queue, and then shift-reduce actions are applied to the state. The newly generated states as results of the shift-reduce actions are placed in the queue. This process repeats until it generates a state satisfying the sentential condition. We define the score of a parsing state as the product of the probabilities of selecting actions that have been taken to reach the state. We regard the state score as the objective function in the best-first search algorithm, i.e., the state with the highest score is always chosen in the algorithm. However, the best-first algorithm with this objective function searches as done by the breadth-first search; a shorter search path tends to have a higher score as it is the product of the probabilities, and therefore the best-first algorithm tends to choose a shorter search path as done by the breadth-first search. Consequently, parsing is very slow or cannot be processed within a reasonable time. Thus, we introduce beam thresholding to the best-first algorithm. The search space is pruned by only adding a new state to the state queue if its score is greater than 1/b of the score of the best state in the states that had the same number of shift-reduce actions. We also used the iterative parsing algorithm (Tsuruoka and Tsujii Reference Tsuruoka, Tsujii, Su, Tsujii, Lee and Kwong2005) for the best-first search algorithm. It first starts parsing with a narrow beam. If parsing fails, then the beam is widened, and parsing continues until the parser outputs results or the beam width reaches some limit.
We tested both backtracking and the best-first search with default unification or normal unification in the experiments. Note that the best-first search parsing for unification-based grammars was much slower than the shift-reduce CFG parsing with the best-first search. This was because we had to copy parse trees, which consisted of large feature structures, in every step of searching to retain many states in the state queue. Copying is not necessary in backtracking, and the original feature structures can be restored by rolling back (trailing) the operations applied to the feature structures.
5.3 Estimation of model parameters
We trained two models of multi-class logistic regression for selecting shift-reduce actions in the experiments. The first was trained using normal unification, and the second was trained using default unification. The probability of an action, y, given an input, x, in a multi-class logistic regression is defined as
where fu is a feature function, wu is a model parameter (a weight for fu), and Y(x) is a set of all possible candidates for x. Multi-class logistic regression is a kind of supervised learning; given a set of inputs and correct answers to these, the model parameters are estimated by using methods of numerical optimization (Malouf Reference Malouf2002) to maximize the log-likelihood of the training data. We used an HPSG treebank (Miyao et al. Reference Miyao, Ninomiya, Tsujii, Su, , Lee and Kwong2005) in the experiments to train the classifiers. The correct answer was provided by normal unification, but we needed two classifiers trained with normal and default unifications. This was because the sets of all possible candidates were different in using normal unification and default unification, i.e., the denominators in (8) were different. For example, suppose that we acquire ten candidates by using normal unification and forty candidates in default unification for some input x. |Y(x)| is 10 in normal unification and |Y(x)| is 40 in default unification. Consequently, the probabilities, p(y|x), are different, and hence the optimal points of the model parameters are different. The accuracy of deterministic shift-reduce parsing dropped by around 2 per cent points in our preliminary experiments, when we trained the model with normal unification, and used default unification in the test run, compared to deterministic shift-reduce parsing using default unification in both the training and test runs.
6 Experiments
We mainly carried out two sets of experiments; preliminary experiments to test different default unifications and different settings for default feature structures (Section 6.2), and main experiments to evaluate our new approach with different search strategies (Section 6.3). A simply typed version of Copestake's default unification with the default non-head daughter achieved the best accuracy in the preliminary experiments. After obtaining the results for the preliminary experiments, we only tested the simply typed version of Copestake's default unification with the default non-head daughter in the main experiments. Section 6.1 explains the settings and evaluation metrics for the experiments. Section 6.4 discusses the differences between our parsing scheme and Matsuzaki et al.'s parser (Matsuzaki, Miyao and Tsujii Reference Matsuzaki, Miyao and Tsujii2007). Section 6.5 provides analyses of our parsers, including the profiles of parsing, the path values overwritten by default unification, error analysis, and an evaluation of the effects of global features.
6.1 Settings
We evaluated the speed and accuracy of parsing with Enju 2.3β, an HPSG for English (Miyao et al. Reference Miyao, Ninomiya, Tsujii, Su, , Lee and Kwong2005). The lexicon for the grammar was extracted from Sections 02–21 of the Penn Treebank (39,832 sentences). The grammar consisted of twelve grammar rules and 2,302 lexical entries for 11,187 words. We used multi-class logistic regression (also known as the maximum entropy or log-linear model) as classifiers. Two probabilistic classifiers for selecting shift-reduce actions were trained using the same portion of the treebank. The first was trained using normal unification, and the second was trained using default unification. The model trained with normal unification was used for evaluating the test run with normal unification, and the model trained with default unification was used for evaluating the test run with default unification.
We measured the accuracy of output for the predicate–argument relations of the parser. A predicate–argument relation is defined as a tuple 〈σ,wh,a,wa〉, where σ is the predicate type (e.g., adjective, intransitive verb), wh is the head word of the predicate, a is the argument label (MODARG, ARG1, . . ., ARG4), and wa is the head word of the argument. Labeled precision (LP)/labeled recall (LR) is the ratio of tuples correctly identified by the parser, and the labeled F-score (LF) is the harmonic mean of the LP and LR. This evaluation scheme was the same as that used in previous evaluations of lexicalized grammars (Hockenmaier Reference Hockenmaier2003; Clark and Curran Reference Clark and Curran2004b; Miyao and Tsujii Reference Miyao and Tsujii2005). The experiments were conducted on an Intel Xeon 5160 server with 3.0 GHz CPUs. Section 22 of the Penn Treebank was used as the development set, and the accuracy was evaluated using sentences of ≤ 100 words in Section 23 of the Penn Treebank.
6.2 Preliminary experiments
We did preliminary experiments to evaluate parsing accuracy using Ninomiya et al.'s (Reference Ninomiya, Miyao and Tsujii2002) default unification and a simply typed version of Copestake's default unification with several ways of applying binary rules as (R ⊔ H) NH, (R ⊔ NH) H, and (H ⊔ NH) R, where R is a grammar rule, H is a head-daughter, and NH is a non-head daughter. We measured the accuracy of output for the predicate–argument relations of the deterministic parser with Enju 2.3β for the Penn Treebank Section 22 (development set) with gold POS tags.
Table 3 lists the results from these preliminary experiments. The ‘a′’ means a simply typed version of Copestake's default unification and ‘n’ means Ninomiya et al.'s (Reference Ninomiya, Miyao and Tsujii2002) default unifications. From the table, we can see that the accuracy of parsing with the default non-head daughters was better than that with the default head daughters and that with the default rules in both Ninomiya et al.'s and Copestake's default unification cases. The labeled F-score dropped by 2.8 points when the defaults were switched from non-head daughters to head daughters. Of these methods, the simply typed version of Copestake's default unification with the default non-head daughter, (R ⊔ H) a′ NH, achieved the best accuracy. We only tested (R ⊔ H) a′ NH in the main experiments.
Preliminary experiments with Ninomiya et al.'s and Copestake's default unification cases (Penn Treebank Section 22 with gold POS tags)
6.3 Evaluation
We evaluated the speed and accuracy of parsing Section 23 of the Penn Treebank, using Enju 2.3β and a simply typed version of Copestake's default unification with the default non-head daughter. Tables 4 and 5 list the results of parsing Section 23. ‘Time’ in the table is the average parsing time for the tested sentences. ‘Deterministic’ means the deterministic shift-reduce parsing proposed in this paper. ‘Backtrack’ means shift-reduce parsing with backtracking. ‘Best-first’ means the best-first shift-reduce parsing with beam thresholding. ‘Default unification’ indicates that default unification was used, and ‘normal unification’ means that default unification was not used. Table 4 lists the results obtained using gold POS tags, while Table 5 lists the results obtained using an automatic POS tagger. The maximum number of backtracking steps and the beam threshold were determined by observing the speed and accuracy for the development set (Section 22) such that the LF was maximized with a parsing time of less than 500 ms/sentence (except ‘best-first(wide)’). The maximum number of backtracks was forty for normal unification and twenty for default unification. The beam width, b, was 7.39 for normal unification, and 20.09 for default unification. The accuracy of ‘best-first(wide)’ was evaluated to find the limit of accuracy of the best-first parsing, and beam width b was set to 403.4.
Experimental results for section 23 (gold POS tags)
Experimental results for section 23 (automatic POS tags)
Deterministic parsing with normal unification achieved accuracy with an LF of around 79.1 per cent (Section 23, gold POS tags).Footnote 2 The LF increased to 83.3 per cent with backtracking. Figure 6 shows the relation between LF and parsing time for the development set (Section 22, gold POS tags). As seen in the figure, the LF increased with increase in the parsing time. The increase in LF for deterministic parsing with normal unification, however, seems to have saturated at around 83.5 per cent. Table 4 also indicates that deterministic parsing with default unification achieved greater accuracy, with an LF of around 87.6 per cent (Section 23, gold POS tags) without backtracking. Default unification was more effective; it ran faster and achieved better accuracy than deterministic parsing with normal unification. The best-first parsing without default unification achieved a high degree of accuracy, with an LF of around 87.0 per cent, but it was still worse than deterministic parsing with default unification. However, with default unification, it achieved the best accuracy, with an LF of around 88.4 per cent, in settings with parsing time of less than 500 ms/sentence for Section 22.
Relation between LF and the average parsing time (section 22, gold POS tags).
The speed and accuracy of Miyao and Tsujii's (Reference Miyao and Tsujii2005), Ninomiya et al.'s (Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007), Matsuzaki et al.'s (Reference Matsuzaki, Miyao and Tsujii2007), and Sagae et al.'s (Reference Sagae, Miyao and Tsujii2007) parsers have also been listed in Tables 4 and 5 for the purpose of cross referencing. Miyao and Tsujii's (Reference Miyao and Tsujii2005) parser is based on a probabilistic model only estimated with a feature forest. Ninomiya et al.'s (Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007) parser is a mixture of the feature forest and an HPSG supertagger. Sagae et al.'s (Reference Sagae, Miyao and Tsujii2007) parser is a hybrid parser with a shallow dependency parser. As seen in the table, our deterministic/best-first parser with default unification achieved an accuracy that was between Miyao and Tsujii's (Reference Miyao and Tsujii2005) and Ninomiya et al.'s (Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007) parsers. Note that these have been listed for the purpose of cross referencing and not to stress the superiority of the packed-forest-based parsing or the deterministic/best-first parsing. The main focus here has been to demonstrate to what extent simple deterministic/best-first parsing could reach state-of-the-art parsers, which have basically been developed with sophisticated parsing technologies based on the packed parse forest. The table also lists the average parsing time, and although our deterministic parser was competitive with Ninomiya et al.'s (Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007) parser, it was slower than Matsuzaki et al.'s (Reference Matsuzaki, Miyao and Tsujii2007) parser. Also note that these were for cross referencing. The difference in parsing speed was mainly due to the difference in implementation and technologies employed for speedups. Parsing time is particularly sensitive to implementation, but our implementation is currently not fully optimized for deterministic parsing with default unification. There is a detailed discussion on Matsuzaki et al.'s (Reference Matsuzaki, Miyao and Tsujii2007) parser in Section 6.4, and the profiles on parsing time are provided in Section 6.5.
Our method with the setting of the ‘best-first(wide)’ provided interesting results. The ‘best-first(wide)’ in Table 4 and the ‘best-first’ in Figure 6 indicate great possibilities for beam-search parsing. The ‘best-first(wide)’ was very slow, but its accuracy was higher than that of any of the other parsers except for Sagae et al.'s (Reference Sagae, Miyao and Tsujii2007) parser.
6.4 Discussion
Matsuzaki et al. (Reference Matsuzaki, Miyao and Tsujii2007) developed a quite efficient HPSG parser by using a technique called CFG-filtering. All possible lexical assignments (i.e., selection of lexical entries) were scored by a conditional probability model, and then a combination of highly scored lexical assignments, which satisfied most grammatical constraints, was selected by applying a dynamic-programming-based parsing algorithm to the scored lexical entries, with a CFG that approximated the original HPSG. As such, they could only use ‘local’ features in their lexical assignment model because the joint probability of a combination of lexical assignments was calculated in the dynamic-programming-based CFG parser as a product of the assignment probabilities for each word. This is in good contrast with our lexical assignment model, which is integrated in the shift-reduce parsing process, wherein we can virtually use all types of features taken from partial parse results that have been built up to the lexical-entry assignment step in shift operation. As the accuracy of lexical assignments largely determines the overall accuracy of parse disambiguation (Ninomiya et al. Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007), we consider the higher accuracy with our method in the ‘best-first (wide)’ setting than that with Matsuzaki et al.'s (Reference Matsuzaki, Miyao and Tsujii2007) approach is mainly due to our richer model of lexical assignment. Matsuzaki et al.'s parser mainly achieved its efficiency by replacing unification operations (or more precisely, their approximation) with CFG rules. They obtained the CFG rules by regarding a feature structure as an atomic symbol, ignoring several of its feature values to obtain a finite set of symbols. Default unification had a similar effect for CFG approximation, as some (conflicting) feature values were ignored to approximate the full search space of parsing to a smaller one. We expect to achieve a similar speedup for Matsuzaki et al.'s (Reference Matsuzaki, Miyao and Tsujii2007) method by introducing the technique of CFG approximation to our method, while still enjoying flexibility in feature design due to the truly deterministic nature of our method, even though we have left this for future work.
6.5 Analysis
Table 6 lists the profiles of the total number of backtracks, states, parsing failures, and parsing successes for Section 22. The ‘#backtrack’ is the total number of backtracking steps that occurred during parsing. The ‘#states’ is the total number of states for the sentences in Section 22. The ‘#failure’ is the number of sentences for which parsing failed. The ‘#non-sent’ is the number of sentences for which parsing succeeded but did not generate a parse tree that satisfied the sentential condition. The ‘#success’ is the number of sentences for which parsing succeeded in generating a parse tree that satisfied the sentential condition. ‘NU’ means that normal unification was used, and ‘DU’ means that default unification was used. The number of parsing failures reached zero and the number of sentences with sentential success increased, when default unification was used.
Profiles for section 22
Table 7 lists the behaviors of default unification for ‘deterministic’ with ‘default unification.’ The table has the twenty most frequent path values that were overwritten by default unification in Section 22. In most of these, the overwritten path values were in the selection features, i.e., subcategorization frames (COMPS:, SUBJ:, SPR:, and CONJ:) and the modifiee specification (MOD:). The column with ‘Default type’ indicates the default types that were overwritten by strict types in the ‘strict type’ column, and the last column is the frequency of overwriting. The ‘cons’ means a non-empty list, and ‘nil’ means an empty list. In most of these, modifiee and subcategorization frames were changed from empty to non-empty and vice versa. The table also indicates, head information was overwritten, e.g., a ‘noun’ was changed to a ‘verb.’
Path values overwritten by default unification in section 22
We analyzed the predicate and argument types that were incorrectly identified by the parsers. Table 8 has the mapping of predicates and arguments to categories. Tables 9, 10, 11, and 12 have the categories of predicates and arguments that were incorrectly identified by Ninomiya et al.'s (Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007) parser, the deterministic shift-reduce parser, the shift-reduce parser with backtracking, and the best-first shift-reduce parser, respectively (Section 22, gold POS tags). We first enumerated all predicate–argument pairs that were incorrectly identified by the parser, and then enumerated pairs of a gold argument and incorrectly identified argument for each predicate. In the tables, ‘pred’ means predicate types, ‘arg’ means argument types in the gold relations, ‘errarg’ means argument types output by the parser, and ‘pred-arg[errarg]’ means triples of a predicate, gold argument, and incorrectly identified argument. The numbers in brackets are the frequencies of each error. The tables indicate that the effect of default unification was the reduced number of undefined arguments (‘undef’ in the table), which means that normal unification failed to identify predicate–argument relations at many places due to hard constraints, and default unification outputs some analysis rather than ‘undef.’ Default unification, on the other hand, tended to output incorrect labels for each ‘errarg’ type. This implies that default unification outputs some analysis rather than ‘undef,’ but its analysis tended to be incorrect. However, in total, default unification outputs better analysis than normal unification.
Mapping of categories for predicates and arguments in error analysis
Incorrectly identified predicate and argument types (Ninomiya et al.'s parser, Section 22, gold POS tags)
Incorrectly identified predicate and argument types (deterministic, section 22, gold POS tags)
Incorrectly identified predicate and argument types (backtrack, section 22, gold POS tags)
Incorrectly identified predicate and argument types (best-first, section 22, gold POS tags)
Table 13 lists profiles of deterministic shift-reduce parsing for Section 22 with gold POS tags. The ‘calc. of prob.’ indicates the average time per sentence for calculating probabilities, including the time for extracting features from feature structures. ‘DU’ is the average time for processing default unification. The ‘parsing main’ is the total time excluding the time for calculating probabilities and processing default unification. The ‘parsing main’ mainly consists of the time for stack and queue operations, and lexical entry look-up and unification operation. As can be seen from the profile, most of the time was spent on calculating probabilities. This is because our parser has many features, i.e., sixty-two feature templates and 155 combinations of feature templates. If we could reduce the time for calculating probabilities, the time for parsing with normal unification would be closer to the that for Matsuzaki et al.'s (Reference Matsuzaki, Miyao and Tsujii2007) parser. In parsing with default unification, much of the time was spent on default unification. This is partly because default unification generated more candidates for classifiers than normal unification because default unification almost always succeeded. Consequently, more time needs to be spent on default unification than normal unification, as well as on calculating the probabilities.
Profiles of deterministic parsing (Section 22, gold POS tags)
We also evaluated the effectiveness of the global features. There were fifty-two feature template combinations, including global features (the total number of feature template combinations was 155). We extracted each global feature from the full set of features in deterministic shift-reduce parsing with default unification. Each feature contributed to an accuracy from 0.0003 per cent points to 0.14 per cent points, and 0.029 per cent points on average. When we removed all global features, the F-score dropped by 2.9 per cent points from 87.61 to 84.72 per cent.
7 Conclusion and future work
We presented a shift-reduce parsing approach to unification-based grammars, based on deterministic shift-reduce parsing. Deterministic parsing was difficult in the framework of unification-based grammar parsing, which often fails because of its hard constraints. We introduced default unification to avoid parsing failures. Our experimental results demonstrated the effectiveness of deterministic parsing with default unification. The experiments revealed that deterministic parsing with default unification achieved a high degree of accuracy, with a labeled LF of 87.6 per cent for Section 23 of the Penn Treebank with gold POS tags. We also presented the best-first parsing with a beam search for unification-based grammars. The best-first parsing with a beam search achieved the best accuracy, with an LF of 87.0 per cent, in settings with normal unification. Default unification further increased LF from 87.0 to 88.4 per cent.
We also tested the best-first parsing by normal unification with a very wide beam, ignoring its efficiency. The best-first parsing achieved the best LF of 89.9 per cent with an average parsing time of around 15 s. Even though this parser cannot be used in practice due to this efficiency, this indicates that our deterministic parsing has the potential to reach state-of-the-art parsers in terms of accuracy due to its truly deterministic nature and flexibility in feature design.
We have not yet exhaustively pursued the combinations of feature templates, although there are many possibilities for these, e.g., more words/POS tags in relative positions, more elements in the parser's stack, and exponentially more possibilities of combinations. Although at present these features are found manually, it is very difficult to find them manually in settings where global features are available like they are in deterministic parsing. Automatic feature construction/selection that has been studied in the field of machine learning, such as grafting (Perkins, Lacker, Theiler Reference Perkins, Lacker and Theiler2003) should solve this problem, but it is also known that it can easily overfit the training data. We have left the problem of efficiency in the best-first parsing with normal unification and the problem of feature construction/selection for future work.
