2.1 Lexicalized grammar and parsing

Lexicalized grammars are ‘lexicalist’ syntax description frameworks in which syntactic and semantic specifications are directly associated with words. General grammatical rules are operated on these lexical entries to derive syntactic structures. Lexicalized grammars owe much to lexical entries for syntax description, whereas the general grammar rules are few. The key idea of lexicalized grammar can be described as more lexical entries and less grammar rules. It is a strict mathematical formalism to describe linguistic structures. The formal definition of lexicalized grammar is given as follows:

Definition 1: A lexicalized grammar is defined using a 2-tuple G = 〈L, R〉, where

• • L = {〈w, e〉|w ∈ , e ∈ }, where and , respectively, represent the sets of words and lexical entries;

• • R = {r|r is a partial function mapping: × → } is a set of grammar rules applied to lexical entries.Footnote ²

HPSG is a lexicalized grammar formalism proposed by Pollard and Sag (Reference Pollard and Sag1994). As a lexicalized grammar, an HPSG grammar consists of two components: lexical entries and rule schemata. Lexical entries are used to depict word-specific syntactic and semantic information, whereas rule schemata are used to represent general grammar constraints. The representation of HPSG is based on typed feature structures (TFS) (Carpenter Reference Carpenter1992) and a unification operation for syntax description. In HPSG, the lexical entries and rule schemata are represented as typed feature structures, which are called signs. Figure 1 portrays a sign defined by Pollard and Sag (Reference Pollard and Sag1994). Although various constraints are specified in a sign, for simplicity, we only present a sign in a simplified form when it is not confusing. The simplified form only shows features that are relevant to an explanation, following a previous work (Miyao Reference Miyao2006). The values of suppressed features can be readily inferred from contexts. A simplified form is not strict in mathematics or linguistics. Readability is prioritized when features are guessable from the context.

Fig. 1.

Sign defined in HPSG.

A Lexical entry is a sign directly associated with a word. In Figure 2, a simplified sign represents a lexical entry for the word ‘like’. Omitted features, such as NONLOC, are empty lists. A lexical entry describes that the basic category of the word is ‘verb’, and that it must be combined with an NP-headed (noun phrase headed) sign as its subject and another NP-headed sign as its object. Phrase structures in HPSG are also represented by signs and constructed by rule schemata. Rule schemata are construction rules that describe how child signs are combined into a parent sign under constraints. Figure 3 presents an example of a Subject-Head schema. In the figure, the head child is labeled with ‘H’ and irrelevant features are omitted. The constraints represented as the Subject-Head schema are summarized as follows:

• • HEAD of the head child is percolated to the parent sign.

• • SUBJ of the head child is a list of one-element.

• • The non-head child is expected to satisfy the constraints imposed by the value of SUBJ of the head child.

• • SUBJ of the parent sign has no subject element.

Fig. 2.

Lexical entry (supertag) of the word ‘like’ represented by a simplified sign.

Fig. 3.

Example of HPSG rule schema.

When the constraints in the schema are satisfied by the child signs, unification is applied to generate a corresponding parent sign. Based on the lexical entries and rule schemata, HPSG trees can be constructed.

Two major differences exist between HPSG and CFG. First, a CFG tree consists of nodes labeled with categories (e.g., NP, VP), whereas HPSG is based on typed feature structures, which include more information. The relations between entities in HPSG are formulated as constraints on typed feature structures, whereas the relation in CFG is simply described by production rules such as VP → VBP NP. For some special linguistic phenomena, HPSG has more expression power. The special linguistic phenomena can be represented in typed feature structures. Second, HPSG is regarded as non-derivational, which means that no transformation or destructive operation exists to derive one structure from another (Pollard and Sag Reference Pollard and Sag1994).

A common HPSG parsing process is depicted in Figure 4. Given a word and part-of-speech (POS) sequence (w, p) as the input, supertagging is the first step to resolve lexical ambiguity and to assign probable lexical entries to each word. Subsequently, the deep parser resolves combinational structure ambiguity based on supertagging outputs and constructs the most likely HPSG tree as a final output. In this pipeline parsing framework, a supertagger and a parser take different responsibilities for syntactic disambiguation. A supertagger is intended to resolve lexical ambiguity in the first stage to the greatest extent possible and to reduce predicting errors that might be propagated to the parser.

Fig. 4.

Two steps of HPSG parsing. In this pipeline process, supertagging is a pre-process preceding parsing.

For combinatorial ambiguity in the parsing stage, two approaches are widely used for structural disambiguation: chart-based and shift–reduce parsing. Chart-based approaches, such as the Cocke–Younger–Kasami (CYK) algorithm (Kasami Reference Kasami1965; Younger Reference Younger1967; Cocke and Schwartz Reference Cocke and Schwartz1970), use dynamic programming to search exactly all possible schemata applied for the current lexical/phrasal signs to construct a parse tree. Shift–reduce approaches transform the parsing process to a series of actions to construct a parse tree, such as shift of a sign and reduction of two signs with a schema. Compared with chart-based approaches, shift–reduce parsers usually apply a greedy search or beam search to find the highest scored action series, which can be implemented very efficiently. Generally, the chart-based parsing is more accurate but slower than the shift–reduce parsing. Different from the CFG parsing, unification of operations among large feature structures (signs) that represent phrases makes the HPSG parsing more computationally costly with time complexity of O(cn ³|G|), where n denotes the sentence length, c represents a factor related to the unification operations, and |G| is the size of grammar.

2.2 Supertagging

Supertagging is usually formalized as a sequence-labeling task. Here, we formulate supertagging in perceptron formalism. We follow the definition of Collins' structure-perceptron (Collins Reference Collins2002) to learn mapping from the input space x =(w, p) ∈ W × P to the supertag space s ∈ S, where W and P, respectively, denote a set of words and POS tags. We use function GEN(x) to indicate all possible supertag sequences-given input x. Feature function Φ maps a training sample (x, s) ∈ W × P × S to a point in feature space R^d. To get feature weights θ ∈ R^d of the feature function, we use the averaged perceptron training method presented in Algorithm 1. For decoding, given an input x and a vector of feature weights θ, we want to find an output s that satisfies the following equation:

The model structures commonly used for supertagging are portrayed in Figure 5. The point-wise models incorporate the assumption that the supertag predictions are independent and make predictions based on the input context for each token. Compared with point-wise models, sequential models incorporate the assumption that the current predicted supertag ŝi is also conditioned on previous supertag assignments. For example, in the first-order sequential model, ŝi is conditioned on the input context and previous supertag ŝi − 1. For sequential models, the Viterbi algorithm is commonly used for efficient decoding.

Fig. 5.

Two sequence-labeling approaches for supertagging.

Nevertheless, the current accuracy of a supertagger is insufficient to use it as a single-tagger for lexicalized grammar parsing. Multi-supertagging strategies, which assign more than one supertag to each word, have been widely used. A tradeoff arises between a supertagger and a parser (in other words, a tradeoff between speed and accuracy). The more the supertag candidates are reserved for a parser, the more accurate but slower the parser becomes because more than one supertag assignment can avoid possible parse error brought by the wrong supertag assignment. However, this also imposes a heavier workload on a parser, which increases parsing time compared with parsing with fewer supertag candidates. Clark and Curran (Reference Clark and Curran2004) proposed an adaptive beam search strategy to improve naive multi-supertagging. They start with a small supertag beam width for supertag assignments. If the initially provided supertag assignments make the parser fail, then more supertag sequence candidates are requested by the parser. The supertag beam width is then enlarged and the supertagger is re-run. The process continues until the parser finds a well-formed analysis or a pre-defined iteration number is reached. Matsuzaki, Miyao and Tsujii (2007) proposed an enumeration-based approach that filters out ungrammatical supertag assignments provided to the parser. The parsing speed is greatly improved by reducing unnecessary parse trials on the unlikely supertag sequences. These two methods favor speed over accuracy because the first returned parse tree is used as the output of the parser, but the returned parse tree is not guaranteed to be the highest scoring parse tree. The fundamental reason for this problem is that the supertaggers are still weak.

4.1 Dependency-informed supertagger

Since a supertag is a description of syntactic properties, e.g., the case-frame of a word, a correct choice of a supertag might be dependent on surface words that are distant from the word on which the choice is made. Simply considering the context feature in the whole sentence level presents a high computational cost, and it invariably includes many noisy features for supertagger modeling. In a discriminative sequence-labeling framework, either sequential or local classifier, you have to design features based on input sequence. Although some sequence-labeling models such as CRF can condition the global input sequence in theory, considering the computational cost, features are usually derived based on the limited scope of the input context in practice. We become motivated to use dependency formalism to describe word-to-word relations and use this information to guide the long-range feature extraction for supertagger models. Therefore, we can selectively choose related surface words and POS tags to generate context features in a whole sentence scope. In other words, the dependency information is used as guidance to select related features for a supertagger.

Following is the overall training process of the dependency-informed supertagger: Given the corpora, the first step is to acquire word-to-word dependencies for each given sentence. We can use a dependency parser to get word-to-word dependencies. In the second step, we use the acquired word-to-word dependencies to locate all related words for each word in the sentence. We extract the dependency-informed features based on the current predicted word and its related words. The dependency-informed features are combined with local context features extracted from the context window. We train weights for the features as model parameters.

Regarding the testing process of the dependency-informed supertagger, given a test sentence, we first generate word-to-word dependencies with the dependency parser used in the training process and then extract dependency-informed long-range features and local features. Based on model parameters and feature sets, we find the highest scoring supertag sequence as the supertagger output.

4.1.1 Acquisition of word-to-word dependencies

In order to extract context features from related words selectively, we first model word-to-word relations in dependency formalism. As introduced in the background section of this paper, the dependency grammar is a natural approach to describe relations between words. It is a simple shallow syntactic description compared with HPSG. For a given sentence, we use a dependency parser to parse word-to-word dependency structures of a sentence. The word-to-word dependencies are the high-scoring dependency edge set for a sentence:

We must re-train a dependency parser based on dependency trees derived from HPSG. From a parser's perspective, dependency grammar is used as an approximation to HPSG used for a supertagger. Compared with the CFG approximation (CFG filter), the dependency grammar approximation process is simpler. We use the ‘Head’ information defined in phrasal signs in each branch of HPSG trees. The lexical head of a non-head daughter of the branch is dependent on the lexical head of the head daughter. Then, the dependency arc is labeled with the name of the schema that was used at the branch. For example, as shown in Figure 7, we can extract word-to-word dependencies in the form of 〈like, coffee, Head-complement〉 and 〈like, They, Subject-Head〉 from an HPSG tree in corpora. The ‘ROOT’ tag is appended as the root of the dependency tree. Therefore, the dependency arc, such as 〈ROOT, like, Head-root〉, is also included in the dependency tree. The derived dependency trees are used as the training data for a dependency parser. Mainstream data-driven dependency parsing techniques, such as graph-based and transition-based methods, can be applied to model word-to-word dependencies.

Fig. 7.

Example of extracting dependency tree from an HPSG tree. The extracted dependency tree is used to train a dependency.

4.1.2 Transformation from word-to-word dependencies to guided features

After acquiring word-to-word dependencies, we use them to extract MODIN and MODOUT relations for each word in the sentence. MODIN and MODOUT relations can be acquired from dependency results, which are represented by the mappings of MODIN(x_i)={head of x_i} and MODOUT(x_i)={all dependents of x_i}. For example, for the word ‘like’, we can obtain MODIN(like) = {ROOT} and MODOUT(like) = {they, coffee}. Therefore, we can extract long-range features according to the MODIN and MODOUT mappings, which enable us to break through the limitation of the context window without bringing in too many context features, which can be noisy. We designate these extracted features as ‘dependency-informed features’. These dependency-informed features are described in Table 1. The relative locations and names of schema are included in the feature. The relative location is mainly represented as left or right located MODIN and MODOUT elements according to the current predicted word.

Table 1.

Feature templates used for the dependency-informed supertagger

Note: p, w, and sc, respectively, signify POS, word, and schema. Also, E represents a set of dependency edges. Direction (left/right) from MODIN/MODOUT word to the current word is also considered in feature templates.

4.1.3 Integrating guided features into a supertagger

We factorize the sequence input into separated words and use a point-wise classifier augmented with dependency-guided features. The model structure is depicted in Figure 8. The model structure (point-wise classifier plus global features) can be categorized as an approach of structure complication (Liang, Daumé III and Klein Reference Liang, Daumé and Klein2008), which replaces structure with features to reduce the computational cost.

Fig. 8.

Model structure for incorporating dependency information into supertagging. Dotted arrows describe the long-distance dependency information provided for supertag prediction. The rectangle represents a local context window.

In order to avoid overfitting, in our case, features consist of local features in the context window and dependency-guided features in a sentence scope. The model parameters can be trained using various optimization methods. As described in this paper, we use averaged perceptron to train the dependency-informed supertagger.

From the deep parser perspective, using dependency information in the supertagging stage can be treated as a combination of shallow parsing and deep parsing. Previous research (Sagae, Miyao and Tsujii Reference Sagae, Miyao and Tsujii2007) has shown that the surface of a dependency structure of a sentence provides valuable information for the HPSG parser. They used heuristic rules to extract dependency from partial HPSG trees and match it with predetermined dependency constraints. In our case, the dependency information is used as a soft constraint in the supertagger model; then it is propagated to the parser by supertag assignments.

4.2 Forest-guided supertagger training

4.2.5 Explanation in search-based learning framework

This training algorithm is also explainable in the search-based learning framework (Daumé III and Marcu Reference Daumé and Marcu2005). In this framework, the objective of learning is to optimize θ for the enqueue function to place good hypothesis high on the search queue. The rank score r consists of two components: path score g and heuristic score h, as defined in A* search (Hart et al. Reference Hart, Nilsson and Raphael1968). In the forest-guided training method, r can be rewritten as follows:

The heuristic part h checks whether the supertag candidate sequence satisfies grammar constraints: if no CFG tree can be constructed, −∞ penalty is imposed to the candidate sequence in the forest-guided training method.

If the current prediction supertag sequence is unable to form any CFG tree in the training process of the forest-guided supertagger, a new rank score of the prediction would be changed to −∞. Consequently, this supertag prediction sequence will be discarded and the algorithm will search for the next highest scoring during the grammar-satisfying sequence prediction. Just as we expected, supertagger is learned in the approximated grammar-satisfying space, and other possible sequences in grammar violating space are pruned away during the search of the highest scoring grammar-satisfying prediction sequence.

5.1 Data

We conducted experiments on the Enju HPSG treebank (version 2.3),Footnote ³ which was semi-automatically converted from the Wall Street Journal (WSJ) portion of the PennTreebank (Miyao Reference Miyao2006). In all, the grammar consists of 2,308 supertags. The training and test split of the data are the same as in the previous work (Ninomiya et al. Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007): section 02-21/22/23 are used as training/development/test data for the supertagger and the HPSG parser. The training data comprise 37,806 sentences, whereas the development and the test data, respectively, include 1,648 and 2,291 sentences.

Figure 9 shows the word-type quantity according to the number of label (supertag or POS tag) candidates for the words in the training data. As the figure shows, no word has more than six POS tag candidates, although there are 1,116 words with more than six supertag candidates in the training data. For example, the word ‘as’ has eighty-eight possible supertag candidates. In fact, this example illustrates the difficulty of supertagging compared with POS tagging: more label ambiguities must be resolved in the supertagging task (1.71 supertag/word vs. 1.16 POS tag/word on average).

Fig. 9.

Word statistics according to supertag and POS tag numbers on training data.

5.2 Evaluation metrics

The evaluation methods of a supertagger are based on the supertagging and HPSG parsing performance. A supertagger is evaluated by the token-labeling accuracy. For comparison with different supertagging models, we apply the McNemar's test to evaluate the significance of the difference between two supertaggers outputs.Footnote ⁴ The performance of an HPSG parser is evaluated using labeled precision (LP) and labeled recall (LR) of the predicate-argument relations generated by the parser as in previous works (Miyao Reference Miyao2005; Matsuzaki et al. Reference Matsuzaki, Miyao and Tsujii2007; Ninomiya et al. Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007). The F-score of evenly weighted LP and LR is also calculated. As for time information, all experiments were conducted on an AMD Opteron 2.4-GHz server and I/O time is not included in the supertagging and parsing time.

5.3 Model settings

Supertaggers: The baseline supertagger models followed the conventional sequence-labeling approach. We considered point-wise model (PW) and sequential labeling model (SEQ). The model parameters were optimized using the averaged perceptron. The training iterations for baseline models were set as five according to the development set. For ease of comparison, the supertagging features used in the baseline model were the same as those described in a previous report (Matsuzaki et al. Reference Matsuzaki, Miyao and Tsujii2007). The feature template details are presented in Table 1 of local feature rows. For the forest-guided supertagger, we used beam-search to find the highest scoring grammar-satisfying supertag sequence. The chart size of the CFG parser was used to control the beam, set as 20,000 edges. In other words, the CFG parser was only allowed to search parse trees when the chart edges are fewer than 20,000.

Parsers: Our experiments used parsers of three types: CFG parser, dependency parser, and HPSG parser. The CFG grammar was used as an approximation of Enju HPSG, which was identical to the CFG used in Matsuzaki et al. (Reference Matsuzaki, Miyao and Tsujii2007). The CFG was approximated to the original Enju HPSG extracted using Kiefer and Krieger's algorithm. Detailed statistics of the CFG grammar are presented in Table 2. The dependency parser was used to find word-to-word dependencies of a sentence. We used the MSTParser Ver. 0.4.3Footnote ⁵ and MaltParser Ver. 1.5.3.Footnote ⁶ For MaltParser, we used the ‘LIBLINEAR’ option for classifier.

Table 2.

Approximated CFG for the Enju HPSG grammar

The HPSG parser was used to evaluate the improvement of the final parser brought by supertagger refinement. We used a shift–reduce HPSG parserFootnote ⁷ (Matsuzaki et al. Reference Matsuzaki, Miyao and Tsujii2007) and evaluated the contribution of the improved supertagger for the final HPSG parsing. The parser crucially depends on a supertagger's performance in that it outputs the first well-formed tree constructed on the highest scoring supertag sequence. The HPSG tree construction on a supertag sequence uses a shift–reduce style parsing algorithm equipped with a classifier-based action selection mechanism. The CFG constraints are also used to guide the shift–reduce parsing process. In the default setting of HPSG parsing, we fed multiple supertag candidates for each token to the parser. It is noteworthy that for the baseline HPSG parser, a CFG filter already exists between the supertagging module and the parsing module. For brevity, in parsing with different supertaggers, we merely distinguish the parsers with different supertag modules. We used stratified shuffling for the significant test of parsing results with a sample size of 10,000. Moreover, we run a state-of-the-art chart-based HPSG parser (Enju parser 2.3) for comparison of the final HPSG parsing performance.

Others: For the supertagging task, POS tags are required as the input. In our experiments, POS tags were assigned automatically using a maximum entropy tagger with around 97% accuracy.

5.4 Analysis on baseline supertagger

We first present experiment results obtained using the baseline supertagger. Our baseline supertagger is a point-wise classifier training by averaged perceptron, which shows performance of 92.16% (gold POS) and 90.84% (auto POS) as shown in Table 3. When considering the first-order supertag edge features in the supertagger, we obtained further improvement of 0.38% and 0.46% from the baseline PW supertagger with P-values less than 0.0001 for given gold standard POS tags and automatically assigned POS tags, respectively.

Table 3.

Supertagging accuracy on section 22

Thereafter, we imposed grammar constraints on the supertagger's output with a CFG filter. The method of using a CFG filter in the post-process of a supertagger is identical to the learning scheme of learning plus inference. CFG filter is used to maintain structural consistency only after learning. We obtained large gains of 1.13% from PW to PW+CFG (P-value < 0.0001) for given gold standard POS tags. A similar case was found when POS tags were given automatically. The performance of a PW+CFG supertagger is better than a statistically significant degree of a SEQ supertagger.

Comparison of PW with PW+CFG shows a frequent type of correction by CFG filter for the word ‘and’, wherein a supertag for NP-coordination (‘NP and NP’) was corrected to one for VP-coordination (‘VP and VP’ or ‘S and S’). The salient meaning is that disambiguation between two coordination types is difficult for SEQ supertagger, presumably because they appear to be very similar with a limited length of context. For example, in an S–S coordination, the sequence of the NP-object of left conjunct, ‘and’, and the NP subject of right conjunct appear to be very similar to an NP coordination.

5.5 Analysis of dependency-informed supertagger

In a dependency-informed supertagger, either for training or testing, we must conduct dependency parsing beforehand. Therefore, the performance of a supertagger is expected to be affected by the accuracy of the dependency parser. In this section, we specifically examine analyses of the effect of dependency accuracy on supertagger and parser. Here, we used two state-of-the-art dependency parsers: MSTParser and MaltParser.

We first evaluated the upper bound of the dependency-informed supertagger for the gold standard first-order dependencies. As shown in Table 4, using gold standard dependency results, the supertagging accuracy can reach 97.30%. Compared with PW supertagger (92.48%), this absolute 4.82% gain shows that the derived non-local feature from the dependency information is very informative for supertagging task.

Table 4.

Oracle performance of dependency-informed supertagger on section 22

In a real case, MSTParser was more accurate on the labeled attachment score (LAS) than MaltParser. The LASs of MSTParser are, respectively, higher by 1.26% and 1.31% than those of MaltParser for given gold standard POS tags and automatically assigned POS tags. Accordingly, the supertagger using MSTParser was better to a statistically significant degree than the supertagger using MaltParser, as shown in Table 5.

Table 5.

Effects of dependency accuracy on dependency-informed supertaggers on section 22. The dependency results are evaluated using the labeled attachment score (LAS)

We then fed the single-best supertagging results of the baseline parser to investigate the dependency accuracy effect for HPSG parser. As presented in Table 6, affected by the supertaggers' accuracy, the F-score of the parser using the one-best PW-DEP_Malt supertagger is 1.19% lower than that of the parser using the one-best PW-DEP_MST supertagger. In the one-best supertag candidate case, lexical entries of the parse tree are already determined by the supertagger. Therefore, the parsing performance is also affected by the dependency accuracy. We conclude that the more accurate the dependency parser is, the more accurate dependency-informed supertagger and the corresponding HPSG parser are.

Table 6.

Comparison of HPSG parsers with dependency-informed supertaggers using a different dependency parser

Although the MSTParser is more accurate than the MaltParser, the parsing time in actuality is much slower. For example, on the test data, the MSTParser needed the parsing time of around 169 s, whereas the MaltParser parsed in only 6.7 s. As supertagger also contributes to the high speed of a deep parser, in applying the dependency-informed supertagger, we face a tradeoff problem on the speed and accuracy of a dependency parser.

Compared with the method of using CFG filter for a supertagger's output, the dependency-informed supertagger belongs to a different category of inference-based learning and the classifier is refined with the assistance of dependency information. However, the dependency-informed supertagger makes use of dependency information to derive long-range features as soft constraints, although CFG filter produces hard constraints for the supertagger's results. Both dependency information and CFG constraints are used as approximations for the same deep grammar. It is very interesting to see the effect of combining these two methods. We then applied CFG filter to the dependency-informed supertaggers. With the help of a CFG filter, the dependency-informed supertaggers can still make a statistically significant 0.42% (PW-DEP_MST) and 0.9% (PW-DEP_Malt) improvement, given the automatically assigned supertags. It is also the case in which gold standard POS tags are given. Furthermore, the accuracy gap separating the PW-DEP_MST supertagger and PW-DEP_Malt supertagger became smaller. The PW-DEP_MST+CFG supertagger was not significantly different statistically from PW-DEP_Malt+CFG supertagger as shown in Table 7. The dependency-informed supertaggers using CFG filter are also significantly better statistically than the PW+CFG supertagger, with token accuracies of 92.12% (auto POS) and 93.29% (gold POS). Since a deep parser itself can be treated as a refined CFG filter, if we feed the parser with all supertag candidates for each token, then we can obtain similar result as that obtained using the CFG filter in the post-process. Table 6 shows that no statistically significant difference was found between the F-scores of the parsers using different dependency-informed supertaggers. Therefore, we can use the PWDEP_Malt supertagger without too much loss of accuracy while maintaining the speed issue.

Table 7.

Performance of dependency-informed supertaggers with CFG filter on section 22

5.6 Analysis of forest-guided supertagger

Compared with the PW supertagger, the PW+CFG supertagger incorporates grammar constraints only in the test phase. However, with the forest-guided (FT) supertagger, the grammar constraints are incorporated both in training and testing stages. A comparison between PW+CFG supertagger and forest-guided supertagger is shown in Table 8, which shows that incorporating grammar constraints into the training stage gave additional statistically significant improvements of 0.38% (gold POS) and 0.29% (auto POS) over the PW+CFG supertagger. Therefore, considering grammar constraints in a supertagger's training process can further improve the accuracy of the supertagger. Similar to the training scheme of the dependency-informed supertagger, forest-guided supertagger training is an inference-based learning method and the local classifier is refined with CFG filter. The original motivation for supertagging is using simple models to resolve lexical ambiguity, which can efficiently reduce search space of the parser. A better supertagger can contribute to a more efficient and accurate deep parser. Actually, a supertagger itself can be treated as a coarse parser for the whole parsing process as long as the coarse parser is efficient.

Table 8.

Comparison of the forest-guided supertagger (FT) and point-wise supertagger with CFG filter in the post-process (PW+CFG) on section 22

5.6.1 Beam size effect

Beam size plays an important role for the forest-guided supertagger because a larger beam size reduces the possibility of search errors. In practice, we control beam size by quantitative limitation of edges in the chart in both the forest-guided supertagger training process and the parsing process.

Figure 10 presents the results obtained using different chart size limits for the forest-guided supertagger and the HPSG parser on development set. The x-axis represents the chart size for the final deep parser. ‘10k-train’ represents the chart size to be limited to 10k during the FT supertagger training phase. A similar representation is used for ‘20k-train’. No beam search is applied for baseline PW supertagger. We evaluated the F-score of parsers using different supertaggers. First, as shown in Figure 10, when the chart size of the parser was greater than 10k, the benefits of using the forest-guided supertaggers were statistically significant (around an absolute 0.55% improvement in the F-score compared to the parser using the baseline PW supertagger with the F-score of 88.34%). The performance of the parser using ‘10k-train’ FT supertagger was already approaching that of the parser using a ‘20k-train’ FT supertagger. Secondly, when the chart size of the parser was less than 2,000, the forest-guided supertaggers did not work well. The F-scores of parsers using 10k-train FT supertagger and 20k-train FT supertagger are lower than the F-score of the parser using the baseline PW supertagger.

Fig. 10.

F-score of HPSG parsers on section 22 using different settings for the chart size limit in supertagger training and parsing.

This interesting phenomenon is explainable as follows: In the forest-guide supertagger, the CFG filter and the point-wise model work collaboratively to train the supertagger. The CFG filter used in the supertagger training excludes unnecessary negative samples for the supertagger learner and makes the point-wise model to be learned in a smaller space. In the testing time of applying forest-guided supertagger, the CFG filter is also needed to exclude unlearned ungrammatical supertag sequences in the point-wise model. For this reason, smaller beam sizes used in the parsing time give lower performance of the parser. In addition, similar to the results described in earlier reports (Daumé III and Marcu Reference Daumé and Marcu2005), it is better to use the same chart size limit in the forest-guided supertagger training and the final parsing.

5.7 Overall results obtained for the test set

Finally, we make comparisons using the standard test set. As shown in Table 9, because of the difference of training algorithms, the accuracy of the PW supertagger trained using averaged perceptron is around 0.3% less than the PW supertagger trained using Maximum Entropy model (Matsuzaki et al. Reference Matsuzaki, Miyao and Tsujii2007) using the same local context features, which are statistically significant. The long-range information is extremely important for the supertagging task. By incorporating grammar constraints into the PW supertagger (PW+CFG, PW-DEP, and FT), we obtained significant improvements from PW supertagger. They are all better than SEQ supertagger to a statistically significant degree. For the dependency-informed supertagger, no statistically significant difference was found between the dependency-informed supertaggers using different dependency parsers on the dataset. Given the automatically assigned POS tags, the dependency-informed supertaggers were worse than both PW+CFG and FT supertaggers to a statistically significant degree. The reason underlying this result is that a certain amount of extra dependency-informed features used in PW-DEP are based on POS tags and the dependency accuracy is also affected by POS tags. However, the dependency-informed supertagger shows an approach to incorporate richer information for supertagger and the HPSG parser.

Table 9.

Supertagging accuracy on section 23

Note: *The result is significantly better statistically than that of the baseline PW supertagger.

^† The result is significantly different statistically from that of the PW-DEP supertagger.

Table 10 shows results of the baseline parser using different supertaggers. We first compared the baseline shift–reduce HPSG parsers using FT and PW supertaggers. The forest-guided supertagger improves the final parser's F-score by 0.68% (statistically significant) over the parser using PW supertagger, which did not consider grammar constraints in the supertagger's training process. The whole parsing time of FT parser closely approximates that of PW parser (108 s vs. 106 s). This result is explained as follows: In the forest-guided supertagger, the supertagger model is forced to learn the model parameters in the approximated grammar-satisfying space. The CFG filter takes the role of distinguishing the ungrammatical supertag sequences. Consequently, the supertagger becomes more discriminative for the gold supertag sequence and other grammar-satisfying supertag sequence candidates. This discriminative tendency constitutes a complement to the deep parser, which favors speed over accuracy, because the first-returned parse tree becomes more accurate in similar parsing time.

Table 10.

HPSG parser's performance on section 23 with automatically assigned POS tags

Note: *Result is significantly different statistically from the baseline parser's result.

We also compared our results with those obtained using a state-of-the-art HPSG parser. The Enju parser (Miyao Reference Miyao2005; Ninomiya et al. Reference Ninomiya, Matsuzaki, Miyao and Tsujii2007) is a chart-based parser with maximum entropy model on the feature forest representation for structural disambiguation. In contrast with our baseline shift–reduce HPSG parser, a dynamic programming algorithm is applied to search the space consisting of possible supertagging candidates for the highest probability HPSG parse tree of the sentence. Usually, the chart-based HPSG parser is more accurate but slower than the shift–reduce-based HPSG parser. In the experiments, the baseline parser using the PW supertagger was 0.23% below the Enju parser but around seven times faster. Using the dependency-informed supertagger and the forest-guided trained supertagger, we acquired competitive or even better parsing results while retaining the speed advantage. Our improved FT parser performed significantly better in the F-score by 0.45% than the Enju parser.