Hypertagging: Supertagging for Surface Realization with CCG
Espinosa, Dominic and White, Michael and Mehay, Dennis

Article Structure

Abstract

In lexicalized grammatical formalisms, it is possible to separate lexical category assignment from the combinatory processes that make use of such categories, such as parsing and realization.

Introduction

In lexicalized grammatical formalisms such as Lexicalized Tree Adjoining Grammar (Schabes et al., 1988, LTAG), Combinatory Categorial Grammar (Steedman, 2000, CCG) and Head-Driven Phrase-Structure Grammar (Pollard and Sag, 1994, HPSG), it is possible to separate lexical category assignment — the assignment of informative syntactic categories to linguistic objects such as words or lexical predicates — from the combinatory processes that make use of such categories — such as parsing and surface realization.

Background

2.1 Surface Realization with OpenCCG

The Approach

3.1 Lexical Smoothing and Search Errors

Results and Discussion

Several experiments were performed in training and applying the hypertagger.

Related Work

Our approach follows Langkilde-Geary (2002) and Callaway (2003) in aiming to leverage the Penn Treebank to develop a broad-coverage surface realizer for English.

Conclusion

We have introduced a novel type of supertagger, which we have dubbed a hypertagger, that assigns CCG category labels to elementary predications in a structured semantic representation with high accuracy at several levels of tagging ambiguity in a fashion reminiscent of (Bangalore and Rambow, 2000).

Topics

logical form

Appears in 13 sentences as: logical form (8) logical forms (6)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. We have adapted this multitagging approach to lexical category assignment for realization using the CCG-based natural language toolkit OpenCCG.1 Instead of basing category assignment on linear word and POS context, however, we predict lexical categories based on contexts within a directed graph structure representing the logical form (LP) of a proposition to be realized.
    Page 1, “Introduction”
  2. Edges are grouped into equivalence classes when they have the same syntactic category and cover the same parts of the input logical form .
    Page 2, “Background”
  3. Additionally, to realize a wide range of paraphrases, OpenCCG implements an algorithm for efficiently generating from disjunctive logical forms (White, 2006a).
    Page 2, “Background”
  4. the one that covers the most elementary predications in the input logical form , with ties broken according to the n-gram score.
    Page 3, “Background”
  5. In the second step, a grammar is extracted from the converted CCGbank and augmented with logical forms .
    Page 3, “Background”
  6. A separate transformation then uses around two dozen generalized templates to add logical forms to the categories, in a fashion reminiscent of (Bos, 2005).
    Page 3, “Background”
  7. After logical form insertion, the extracted and augmented grammar is loaded and used to parse the sentences in the CCGbank according to the gold-standard derivation.
    Page 3, “Background”
  8. If the derivation can be successfully followed, the parse yields a logical form which is saved along with the corpus sentence in order to later test the realizer.
    Page 3, “Background”
  9. Currently, the algorithm succeeds in creating logical forms for 97.7% of the sentences in the development section (Sect.
    Page 4, “Background”
  10. Of these, 76.6% of the development logical forms are semantic dependency graphs with a single root, while 76.7% of the test logical forms have a single root.
    Page 4, “Background”
  11. These missing dependencies usually reflect inadequacies in the current logical form templates.
    Page 4, “Background”

See all papers in Proc. ACL 2008 that mention logical form.

See all papers in Proc. ACL that mention logical form.

Back to top.

POS tags

Appears in 13 sentences as: POS tag (1) POS tagger (4) POS tagging (2) POS tags (9)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. The best performing model interpolates a word trigram model with a trigram model that chains a POS model with a supertag model, where the POS model conditions on the previous two POS tags, and the supertag model conditions on the previous two POS tags as well as the current one.
    Page 4, “Background”
  2. Clark (2002) notes in his parsing experiments that the POS tags of the surrounding words are highly informative.
    Page 5, “The Approach”
  3. As discussed below, a significant gain in hypertagging accuracy resulted from including features sensitive to the POS tags of a node’s parent, the node itself, and all of its arguments and modifiers.
    Page 5, “The Approach”
  4. Predicting these tags requires the use of a separate POS tagger , which operates in a manner similar to the hypertagger itself, though exploiting a slightly different set of features (e. g., including features corresponding to the four-character prefixes and suffixes of rare logical predication names).
    Page 5, “The Approach”
  5. Following the (word) supertagging experiments of (Curran et al., 2006) we assigned potentially multiple POS tags to each elementary predication.
    Page 5, “The Approach”
  6. The POS tags assigned are all those that are some factor 6 of the highest ranked tag,3 giving an average of 1.1 POS tags per elementary predication.
    Page 5, “The Approach”
  7. The values of the corresponding feature functions are the POS tag probabilities according to the POS tagger .
    Page 5, “The Approach”
  8. At this ambiguity level, the POS tagger is correct 2 92% of the time.
    Page 5, “The Approach”
  9. Using L—BFGS allowed us to include continuous feature function values where appropriate (e. g., the probabilities of automatically-assigned POS tags ).
    Page 5, “The Approach”
  10. We trained each hypertagging model to 275 iterations and our POS tagging model to 400 iterations.
    Page 5, “The Approach”
  11. We used no feature frequency cutoffs, but rather employed Gaussian priors with global variances of 100 and 75, respectively, for the hypertagging and POS tagging models.
    Page 5, “The Approach”

See all papers in Proc. ACL 2008 that mention POS tags.

See all papers in Proc. ACL that mention POS tags.

Back to top.

CCG

Appears in 11 sentences as: CCG (11)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. We adapt techniques from sapertagging — a relatively recent technique that performs complex lexical tagging before full parsing (Bangalore and Joshi, 1999; Clark, 2002) — for chart realization in OpenCCG, an open-source NLP toolkit for CCG .
    Page 1, “Abstract”
  2. In lexicalized grammatical formalisms such as Lexicalized Tree Adjoining Grammar (Schabes et al., 1988, LTAG), Combinatory Categorial Grammar (Steedman, 2000, CCG ) and Head-Driven Phrase-Structure Grammar (Pollard and Sag, 1994, HPSG), it is possible to separate lexical category assignment — the assignment of informative syntactic categories to linguistic objects such as words or lexical predicates — from the combinatory processes that make use of such categories — such as parsing and surface realization.
    Page 1, “Introduction”
  3. combination thereof, as in the CCG parser in (Hockenmaier, 2003) or the chart realizer in (Carroll and Oepen, 2005).
    Page 1, “Introduction”
  4. Supertagging has been more recently extended to a multitagging paradigm in CCG (Clark, 2002; Curran et al., 2006), leading to extremely efficient parsing with state-of-the-art dependency recovery (Clark and Curran, 2007).
    Page 1, “Introduction”
  5. we evaluate it as a tagger, where the hypertagger achieves high single-best (93.6%) and multitagging labelling accuracies (95.8—99.4% with category per lexical predication ratios ranging from 1.1 to 3.9).2 Second, we compare a hypertagger-augmented version of OpenCCG’s chart realizer with the preexisting chart realizer (White et al., 2007) that simply instantiates the chart with all possible CCG categories (subject to frequency cutoffs) for each input LF predicate.
    Page 2, “Introduction”
  6. The OpenCCG surface realizer is based on Steed-man’s (2000) version of CCG elaborated with Baldridge and Kruijff’s multi-modal extensions for lexically specified derivation control (Baldridge, 2002; Baldridge and Kruijff, 2003) and hybrid logic dependency semantics (Baldridge and Kruijff, 2002).
    Page 2, “Background”
  7. (2007) describe an ongoing effort to engineer a grammar from the CCGbank (Hockenmaier and Steedman, 2007) — a corpus of CCG derivations derived from the Penn Treebank — suitable for realization with OpenCCG.
    Page 3, “Background”
  8. Changes to the derivations are necessary to reflect the lexicalized treatment of coordination and punctuation assumed by the multi-modal version of CCG that is implemented in OpenCCG.
    Page 3, “Background”
  9. In the next section, we show that a supertagger for CCG realization, or hypertagger, can reduce the problem of search errors by focusing the search space on the most likely lexical categories.
    Page 4, “The Approach”
  10. We have introduced a novel type of supertagger, which we have dubbed a hypertagger, that assigns CCG category labels to elementary predications in a structured semantic representation with high accuracy at several levels of tagging ambiguity in a fashion reminiscent of (Bangalore and Rambow, 2000).
    Page 8, “Conclusion”
  11. We have also shown that, by integrating this hypertagger with a broad-coverage CCG chart realizer, considerably faster realization times are possible (approximately twice as fast as compared with a realizer that performs simple lexical lookups) with higher BLEU, METEOR and exact string match scores.
    Page 8, “Conclusion”

See all papers in Proc. ACL 2008 that mention CCG.

See all papers in Proc. ACL that mention CCG.

Back to top.

language model

Appears in 8 sentences as: language model (4) Language Models (1) language models (3)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. Assigned categories are instantiated in OpenCCG’s chart realizer where, together with a treebank-derived syntactic grammar (Hockenmaier and Steedman, 2007) and a factored language model (Bilmes and Kirchhoff, 2003), they constrain the English word-strings that are chosen to express the LF.
    Page 1, “Introduction”
  2. OpenCCG implements a symbolic-statistical chart realization algorithm (Kay, 1996; Carroll et al., 1999; White, 2006b) combining (l) a theoretically grounded approach to syntax and semantic composition with (2) factored language models (Bilmes and Kirchhoff, 2003) for making choices among the options left open by the grammar.
    Page 2, “Background”
  3. makes use of n-gram language models over words represented as vectors of factors, including surface form, part of speech, supertag and semantic class.
    Page 2, “Background”
  4. 2.3 Factored Language Models
    Page 4, “Background”
  5. The language models were created using the SRILM toolkit (Stolcke, 2002) on the standard training sections (2—21) of the CCGbank, with sentence-initial words (other than proper names) uncapitalized.
    Page 4, “Background”
  6. Note that the use of supertags in the factored language model to score possible realizations is distinct from the prediction of supertags for lexical category assignment: the former takes the words in the local context into account (as in supertagging for parsing), while the latter takes features of the logical form into account.
    Page 4, “Background”
  7. Table 1: Percentage of complete realizations using an oracle n-gram model versus the best performing factored language model .
    Page 4, “The Approach”
  8. As shown in Table l, with the large grammar derived from the training sections, many fewer complete realizations are found (before timing out) using the factored language model than are possible, as indicated by the results of using the oracle model.
    Page 4, “The Approach”

See all papers in Proc. ACL 2008 that mention language model.

See all papers in Proc. ACL that mention language model.

Back to top.

BLEU

Appears in 7 sentences as: BLEU (7)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. Moreover, the overall BLEU (Papineni et al., 2002) and METEOR (Lavie and Agarwal, 2007) scores, as well as numbers of exact string matches (as measured against to the original sentences in the CCGbank) are higher for the hypertagger-seeded realizer than for the preexisting realizer.
    Page 2, “Introduction”
  2. compared the percentage of complete realizations (versus fragmentary ones) with their top scoring model against an oracle model that uses a simplified BLEU score based on the target string, which is useful for regression testing as it guides the best-first search to the reference sentence.
    Page 4, “The Approach”
  3. Table 5 shows that increasing the number of complete realizations also yields improved BLEU and METEOR scores, as well as more exact matches.
    Page 7, “Results and Discussion”
  4. In particular, the hypertagger makes possible a more than 6-point improvement in the overall BLEU score on both the development and test sections, and a more than 12-point improvement on the sentences with complete realizations.
    Page 7, “Results and Discussion”
  5. Even with the current incomplete set of semantic templates, the hypertagger brings realizer performance roughly up to state-of-the-art levels, as our overall test set BLEU score (0.6701) slightly exceeds that of Cahill and van Genabith (2006), though at a coverage of 96% instead of 98%.
    Page 7, “Results and Discussion”
  6. We have also shown that, by integrating this hypertagger with a broad-coverage CCG chart realizer, considerably faster realization times are possible (approximately twice as fast as compared with a realizer that performs simple lexical lookups) with higher BLEU , METEOR and exact string match scores.
    Page 8, “Conclusion”
  7. Moreover, the hypertagger-augmented realizer finds more than twice the number of complete realizations, and further analysis revealed that the realization quality (as per modified BLEU and METEOR) is higher in the cases when the realizer finds a complete realization.
    Page 8, “Conclusion”

See all papers in Proc. ACL 2008 that mention BLEU.

See all papers in Proc. ACL that mention BLEU.

Back to top.

n-gram

Appears in 6 sentences as: n-gram (6)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. makes use of n-gram language models over words represented as vectors of factors, including surface form, part of speech, supertag and semantic class.
    Page 2, “Background”
  2. In the anytime mode, a best-first search is performed with a con-figurable time limit: the scores assigned by the n-gram model determine the order of the edges on the agenda, and thus have an impact on realization speed.
    Page 2, “Background”
  3. the one that covers the most elementary predications in the input logical form, with ties broken according to the n-gram score.
    Page 3, “Background”
  4. In the final step, these fragments are concatenated, again in a greedy fashion, this time according to the n-gram score of the concatenated edges: starting with the original best edge, the fragment whose concatenation on the left or right side yields the highest score is chosen as the one to concatenate next, until all the fragments have been concatenated into a single output.
    Page 3, “Background”
  5. While these models are considerably smaller than the ones used in (Langkilde-Geary, 2002; Velldal and Oepen, 2005), the training data does have the advantage of being in the same domain and genre (using larger n-gram models remains for future investigation).
    Page 4, “Background”
  6. Table 1: Percentage of complete realizations using an oracle n-gram model versus the best performing factored language model.
    Page 4, “The Approach”

See all papers in Proc. ACL 2008 that mention n-gram.

See all papers in Proc. ACL that mention n-gram.

Back to top.

maximum entropy

Appears in 5 sentences as: Maximum Entropy (1) Maximum entropy (1) maximum entropy (3)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. 3.2 Maximum Entropy Hypertagging
    Page 4, “The Approach”
  2. The resulting contextual features and gold-standard supertag for each predication were then used to train a maximum entropy classifier model.
    Page 5, “The Approach”
  3. Maximum entropy models describe a set of probability distributions of the form:
    Page 5, “The Approach”
  4. We used Zhang Le’s maximum entropy toolkit4 for training the hypertagging model, which uses an implementation of Limited-memory BFGS, an approximate quasi-Newton optimization method from the numerical optimization literature (Liu and No-cedal, 1989).
    Page 5, “The Approach”
  5. Additionally, as our tagger employs maximum entropy modeling, it is able to take into account a greater variety of contextual features, including those derived from parent nodes.
    Page 8, “Related Work”

See all papers in Proc. ACL 2008 that mention maximum entropy.

See all papers in Proc. ACL that mention maximum entropy.

Back to top.

semantic representations

Appears in 5 sentences as: semantic representation (1) semantic representations (4)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. We call this approach hypertagging, as it operates at a level “above” the syntax, tagging semantic representations with syntactic lexical categories.
    Page 1, “Abstract”
  2. We have dubbed this approach hypertagging, as it operates at a level “above” the syntax, moving from semantic representations to syntactic categories.
    Page 1, “Introduction”
  3. This process involves converting the corpus to reflect more precise analyses, Where feasible, and adding semantic representations to the lexical categories.
    Page 3, “Background”
  4. As the effort to engineer a grammar suitable for realization from the CCGbank proceeds in parallel to our work on hypertagging, we expect the hypertagger-seeded realizer to continue to improve, since a more complete and precise extracted grammar should enable more complete realizations to be found, and richer semantic representations should
    Page 7, “Results and Discussion”
  5. We have introduced a novel type of supertagger, which we have dubbed a hypertagger, that assigns CCG category labels to elementary predications in a structured semantic representation with high accuracy at several levels of tagging ambiguity in a fashion reminiscent of (Bangalore and Rambow, 2000).
    Page 8, “Conclusion”

See all papers in Proc. ACL 2008 that mention semantic representations.

See all papers in Proc. ACL that mention semantic representations.

Back to top.

feature set

Appears in 4 sentences as: feature set (3) feature sets (1)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. The the whole feature set was found in feature ablation testing on the development set to outperform all other feature subsets significantly (p < 2.2 - 10—16).
    Page 6, “Results and Discussion”
  2. The full feature set outperforms all others significantly (p < 2.2 - 10—16).
    Page 6, “Results and Discussion”
  3. The results for the full feature set on Sections ()0 and 23 are outlined in Table 2.
    Page 6, “Results and Discussion”
  4. Finally, further efforts to engineer a grammar suitable for realization from the CCGbank should provide richer feature sets , which, as our feature ablation study suggests, are useful for boosting hypertagging performance, hence for finding better and more complete realizations.
    Page 8, “Conclusion”

See all papers in Proc. ACL 2008 that mention feature set.

See all papers in Proc. ACL that mention feature set.

Back to top.

lexicalized

Appears in 4 sentences as: Lexicalized (1) lexicalized (4)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. In lexicalized grammatical formalisms, it is possible to separate lexical category assignment from the combinatory processes that make use of such categories, such as parsing and realization.
    Page 1, “Abstract”
  2. In lexicalized grammatical formalisms such as Lexicalized Tree Adjoining Grammar (Schabes et al., 1988, LTAG), Combinatory Categorial Grammar (Steedman, 2000, CCG) and Head-Driven Phrase-Structure Grammar (Pollard and Sag, 1994, HPSG), it is possible to separate lexical category assignment — the assignment of informative syntactic categories to linguistic objects such as words or lexical predicates — from the combinatory processes that make use of such categories — such as parsing and surface realization.
    Page 1, “Introduction”
  3. Changes to the derivations are necessary to reflect the lexicalized treatment of coordination and punctuation assumed by the multi-modal version of CCG that is implemented in OpenCCG.
    Page 3, “Background”
  4. Our implementation makes use of three general types of features: lexicalized features, which are simply the names of the parent and child elementary predication nodes, graph structural features, such as the total number of edges emanating from a node, the number of argument and non-argument dependents, and the names of the relations of the dependent nodes to the parent node, and syntactico-semantic attributes of nodes, such as the tense and number.
    Page 5, “The Approach”

See all papers in Proc. ACL 2008 that mention lexicalized.

See all papers in Proc. ACL that mention lexicalized.

Back to top.

BLEU score

Appears in 3 sentences as: BLEU score (3)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. compared the percentage of complete realizations (versus fragmentary ones) with their top scoring model against an oracle model that uses a simplified BLEU score based on the target string, which is useful for regression testing as it guides the best-first search to the reference sentence.
    Page 4, “The Approach”
  2. In particular, the hypertagger makes possible a more than 6-point improvement in the overall BLEU score on both the development and test sections, and a more than 12-point improvement on the sentences with complete realizations.
    Page 7, “Results and Discussion”
  3. Even with the current incomplete set of semantic templates, the hypertagger brings realizer performance roughly up to state-of-the-art levels, as our overall test set BLEU score (0.6701) slightly exceeds that of Cahill and van Genabith (2006), though at a coverage of 96% instead of 98%.
    Page 7, “Results and Discussion”

See all papers in Proc. ACL 2008 that mention BLEU score.

See all papers in Proc. ACL that mention BLEU score.

Back to top.

development set

Appears in 3 sentences as: development set (3)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. The the whole feature set was found in feature ablation testing on the development set to outperform all other feature subsets significantly (p < 2.2 - 10—16).
    Page 6, “Results and Discussion”
  2. The development set (00) was used to tune the 6 parameter to obtain reasonable hypertag ambiguity levels; the model was not otherwise tuned to it.
    Page 6, “Results and Discussion”
  3. limit; on the development set , this improvement eli-mates more than the number of known search errors (cf.
    Page 7, “Results and Discussion”

See all papers in Proc. ACL 2008 that mention development set.

See all papers in Proc. ACL that mention development set.

Back to top.

Treebank

Appears in 3 sentences as: Treebank (3)
In Hypertagging: Supertagging for Surface Realization with CCG
  1. (2007) describe an ongoing effort to engineer a grammar from the CCGbank (Hockenmaier and Steedman, 2007) — a corpus of CCG derivations derived from the Penn Treebank — suitable for realization with OpenCCG.
    Page 3, “Background”
  2. Our approach follows Langkilde-Geary (2002) and Callaway (2003) in aiming to leverage the Penn Treebank to develop a broad-coverage surface realizer for English.
    Page 7, “Related Work”
  3. However, while these earlier, generation-only approaches made use of converters for transforming the outputs of Treebank parsers to inputs for realization, our approach instead employs a shared bidirectional grammar, so that the input to realization is guaranteed to be the same logical form constructed by the parser.
    Page 7, “Related Work”

See all papers in Proc. ACL 2008 that mention Treebank.

See all papers in Proc. ACL that mention Treebank.

Back to top.

PDF available from www.aclweb.org.
Send us an email