Evaluating Coverage for Large Symbolic NLG Grammars

1 Introduction

Like parsing, text generation offers enormous potential bene­ fits for more natural interaction with computers. Examples of applications which could be greatly improved include auto­ matic technical documentation, intelligent tutoring systems, and machine translation, among many others. Historically, natural language generation (NLG) has focused on the study of symbolic pipelined architectures which receive knowledge structures and goals from knowledge-based applications and which proceed to progressively add linguistic information.

In the last few years, the same paradigm shift which occurred in the parsing community, the use of statisti­ caVempirica:l methods, has begun to influence the NLG com­ munity as well. As with parsing, statistical generation promises benefits such as robustness in the face of bad data, wider coverage, domain and language independence, and less need for costly resources such as grammars. But unlike pars­ ing, which starts with a very flat representation (t~xt} which is easily accessible in large quantities to both statistical and symbolic methods, the semantic input for NLG is typically associated with large knowledge-based systems. The types of corresponding corpora which would be necessary for using statistical processes, pairs of subgraphs of knowledge bases and their texts, do not currently exist in large quantities.

Because of this representation problem, most statistical systems have concentrated on replacing existing individual components in the standard NLG pipelined architecture [Re­ iter, 1994] without changing the remaining original sym­ bolic modules. The most popular candidate has been the surface realization module [Elhadad, 1991; Bateman, 1995; Lavoie and Rambow, 1997; White and Caldwell, 1998], which is responsible for converting the syntactic representa­ tion of a sentence into the actual text seen by the user. Thus current statistical generators are still dependent on remaining architectural modules in a system to function and do not by themselves account for a large amount of linguistic phenom­ ena: pronominalization, revision, definiteness, etc.

However, statistical surface realizers [Langkilde and Knight, 1998; Bangalore and Rambow, 2000; Rarnaparkhi , 2000; Langkilde-Geary, 2002] have focused attention on a number of problems facing standard, pipelined NLG that have until now been generally considered future work: large­ scale data-robust and language- and domain-independent gene;ation. In addition, as Langkilde points out, empirical evaluation has not been standard practice in the NLG com­ munity, which has instead relied either on the software engi­ neering practice of regression testing with a suite of examples or theoretical evaluations [Robin and McKeown, 1995].

This paper presents the analogue of this recent statistical experiment using a well-known off-the-shelf symbolic sur­ face realizer, using an augmented generation grammar that includes support for dialogue and additional syntactic cov­ erage. We first describe in the following sect~on the re~re­ sentations and processes needed to understand Its evaluatiOn. We then detail our implemented system for converting sen­ tences from a large corpus into a systemic functional nota­ tion, present an evaluation of that system and the grammar itself using Section 23 of the Penn TreeBank [Marcus et.al., 1993], and finally discuss the implications of that evaluatiOn.

2 Sentence Representations

To undertake a large-scale evaluation of a symbolic surface realizer, we must first find a large quantity of sentence plans with which to produce text. However, most text planners can­ not generate either the requisite syntactic variation or quan­ tity of text, and we thus cannot turn to implemented gener-

((cat clause) (S (PP (IN Without) (NP (NNP GM))) (, ,) (circum {{accompaniment ((cat pp) {pos ition front) (accomp-polarity -) (np ((cat proper) (lex "GM"))))))) (NP-SBJ (process (( t ype ascriptive) (tense past))) (NP (JJ overall) (NNS sales)) (PP ( IN for) (NP (DT the) (JJ other) (participants {(carrier ((cat common) (lex "sale") (number plural) (describer ((cat adj) (lex ''overall 11 ))))) (qualifier ((cat pp) (prep ( (lex "for"))) (NNP u.s .) (NNS automakers) ) ) ) (VP (VBD were) (np {(cat common) {lex 11 automaker " ) (definite yes) (number plural) (status different) (classifier ((cat proper) (lex ''U.S."))))))))) (ADJP-PRD (RB roughly) (JJ flat) (PP (IN with ) (NP (CD 1989) (NNS results ")))))) (attribute ((cat ap) (lex "flat " ) (modif i er ((cat adv) (lex "roughly" ))) (qualifier ((cat pp) (prep ((lex "with"))) (np ((cat common) (lex "result") (number plural) (classifier ((cat date) (year 1989))))))))))))

ation systems as a source. To solve this problem, Langkilde trained a statistical algorithm [Langkilde-Geary, 2002] on a substitute set of sentence plans: the Penn TreeBank [Marcus et al., 1993], a collection of sentences from newspapers such as the Wall Street Journal, which have been hand-annotated for syntax by linguists. An example sentence is shown on the left side of Figure 1. Hierarchical syntactic/semantic bracket­ ing is provided along with the syntactic categories of lexemes and symbols in the newspaper texts.

Unfortunately, text planners currently in use do not gener­ ate representations of the form found in the Penn TreeBank, opting instead to use more fully-developed syntactic theories, such as HPSG [Pollard and Sag, 1994], from the linguis­ tics community. Because annotated texts do not exist in this form, Langkilde created a pre-processing system to translate from the TreeBank annotation into the language accepted by the HALOGEN statistical surface realizer [Langkilde-Geary, 2002]. HALOGEN uses these translations to create aforest lattice whose paths from start to finish represent many possi­ ble versions of a single sentence. Separately, a larger corpus is processed to obtain bigram or trigram frequencies, which are then used to rank the possible sentence versions based on word adjacency. The highest ranked sentence is then pre­ sented as the final output of the system.

In contrast, most deep surface realizers are symbolic rather than statistical, and consist of components that check gram­ matical constraints, appropriately linearize constituents, and adjust for morphology and formatting. One such system in wide use, FUF/SURGE [Elhadad, 1991], combines ideas from systemic functional grammars and head-driven phrase structure grammars. An example of the FUF representation, known as a functional description is shown on the right side of Figure 1. SURGE is the largest generation grammar for En­ glish, and has the largest regression test suite available. But as Langkilde pointed out, 500 test examples are insufficient to empirically demonstrate the coverage of a grammar.

To arrive at a set of sentence plans which is representa­ tive of English, as well as to evaluate the coverage of the FUF/SURGE surface realizer in a way which can be directly compared to the HALOGEN evaluation, we likewise used the Penn TreeBank as a sentence source. Because our represen­ tations are also different, we (as Langkilde) needed a pre­ processing system to convert from the TreeBank notation into the functional descriptions expected by the surface realizer.

Our pre-processor thus performs top-down structure traver­ sal of a sentence annotated in Penn TreeBank format and

( (S ( -LRB- -LRB-) (NP-SBJ-1 (NP (NNP Sony) ) (NP (PRP itself))) (VP (VBZ declines) (S (NP-SBJ (-NONE- *-l)) (VP (TO to) (VP (VB comment))) ( . . ) (-RRB- -RRB-))) (S (LRB LRB) (NP-SBJ-1 (NP (NNP "Sony"}) (NP ~ PRP "itself"))) (VP (VBZ "declines") (S (NP- SBJ (NONE STAR-l)) (VP (TO "to") (VP (VB "comment 11 ) )))) (RRB RRB)))

builds the corresponding functional description. The pre­ processor is organized as a context-sensitive, proceduralized rewriting grammar which matches input symbols to output symbols. The resulting functional descriptions can then be given to the FuF/SURGE surface realizer, and the sen.te_nce string it produces can be lexically compared to the ongmal sentence in various ways to determine how well the surface realizer performs at sentence generation.

3 Implementation

The implementation necessary for evaluating the coverage of FUF/SURGE comprised three processes: (1) normalizing the syntactic/semantic representations, (2) transforming the normalizations into functional descriptions, and (3) generat­ ing the sentence itself with a surface realizer. The normaliz­ ing phase is necessary to convert the original Penn TreeBank structures into a LISP-readable format (Figure 2), which was accomplished with a series of regular expression transforma­ tions on the original text file.

The most time-consuming aspect of the procedure was cre­ ating the transformation component, which was highly anal­ ogous to writing parsing rules by hand. The resulting com­ ponent contained 4000 lines of code and approximately 900 rules, although most of the actual computational effort was spent instead in surface realization. Most of the problems encountered were the result of differences in the underlying grammars themselves. For example, the Penn TreeBank has a more hierarchical noun phrase structure than the flatter rep­ resentation of SURGE's systemic functional grammar.

The final task involved changing the surface realization component (1) to add additional branches and surface forms to the grammar that were not originally present in order to produce surface forms not previously possible, (2) to add new punctuation and capitalization rules 1 , and (3) to update irregular morphology due to the vast number of words the system had not previously seen. The principal linguistic problems uncovered by this phase include:

1 The Penn TreeBank, because it is a newspaper corpus, contains many newspaper headlines and stock quotes with domain-specific

• Quotations: Newspaper text generally contains large amounts of complex quotations, such as splitting a quoted phrase to insert the speaker in the middle, or merging a quote into an unquoted part of the sentence: "I have this feeling that it's built on sand," she says, that the market rises "but there's no foundation to it."
• Punctuation scoping: Problems related to the use of punctuation with tree structures[Doran, I998]. For ex­ ample, SURGE has a flat representation for noun phrases, causing difficulties with phrases such as The major "cir­ cuit breakers" where SURGE cannot insert punctuation between the adjective and nominal classifier.
• Adverb and clause ordering: Because satellite clauses in SURGE are placed using semantic information, they sometime appear in different (though still grammatically acceptable) positions than were specified in the original sentence [Elhadad et al., 2001]. This can oftentimes cause a perfectly acceptable sentence to be produced, but highly skew automatic measurements of correctness such as tree edit distance (simple string accuracy). For example, contrast: "Exports fell 29% in the first few months" vs. "In the first few months, exports fell 29%."
• Semantic roles: SURGE has a hybrid syntactic/semantic representation, whereas the Penn TreeBank is purely syntactic. Thus some guessing must be done to fill in semantic roles in the corresponding functional descrip­ tion. Wrong guesses can lead to incorrect surface forms even when the remainder of the transformation was ac­ complished successfully.

While the normalization process is slow (I 0-12 hours each for WSJ23 and WSJ24), it occurs offline and only once. The transformation process is quite fast, requiring on average O.I2 seconds per sentence. Meanwhile, the FUF/SURGE system is relatively slow, as it requires the use of functional unification, a task of inherent complexity due to backtracking. Section 23 needed 8,397.2 seconds to generate 2372 sentences (with a longest exact match of 48 words), while section 24 needed 5,590.4 seconds to generate I ,326 sentences (with a longest exact match of 44), for a combined average of 3.72 seconds per sentence. 2 This contrasts with statistical approaches like Langkilde's, which require 27.I-55.5 seconds depending on algorithm parameters, and gets exponentially worse if it uses trigrams or larger models in an attempt to improve quality.

formatting not typically used in NLG systems, such as: "8 13/16% high, 8 1/2% low, 8 5/8% near closing bid, 8 3/4% offered."

2 Additionally, a compiled C version of FUF can produce sen­ tences using the same grammar on the order of 0.1 seconds.

4 Experiments and Results

In order to evaluate the coverage of the SURGE grammar, we used the standard train and test methodology. Unlike typi­ cal machine learning experiments, adjustments to the trans­ formation rule set were done by hand, although the evalua­ tion of the resulting sentences was performed automatically. Training took place over a period of several months, consist­ ing of multiple iterations over Penn TreeBank Sections 0-22 and 24 to both improve the number of sentences which could be generated and to match as closely as possible the origi­ nal sentences. These two goals were accomplished solely by adding rules to the transformation set and by updating SURGE grammar rules, notably aspects pertaining to the stock market domain, in addition to support for extended quotations which was added in previous work [Callaway and Lester, 2002].

We considered two types of string matches: exact matches that were identical character-by-character, and "close" matches which were two words or less longer or shorter than the original sentence. There were several motiva­ tions for this second choice: (I) many sentences were equiv­ alent except for a minor missing/extra punctuation mark or wrongly capitalized word (especially with newspaper head­ lines); (2) as mentioned previously, movable clauses (so­ called circumstantials in SURGE nomenclature) could be put in multiple acceptable locations; and (3) sentences with al­ most the exact number of words, especially sentences with more than I5 words, were much more likely to at least have all of the various phrases present when they were within two words or the original sentence's length. We utilized the NIST Simple String Accuracy (SSA) as an automatic eval­ uation score (the same as used in Langkilde's work), where the smallest number of Adds, Deletions, and Insertions were used to calculate accuracy: I - (A + D + T) I #Characters.

The only previous measure of generation coverage for Sec­ tion 23 of the Penn TreeBank is that of [Langkilde-Geary, 2002], who defined coverage as the number of sentences for which the surface realizer produced strings. As seen in Ta­ ble 1, our system achieved 87.8% on one of the training sets and 88.7% on the test set compared to between 76.2% and 83.3% for HALOGEN depending on its algorithm parameters.

A more detailed examination of the coverage and accuracy of the system is found in Table 2 for WSJ Section 24 and Table 3 for Section 23. Both tables are broken down by sen­ tence length, which shows that the results are highly skewed towards sentence of smaller length, as would be expected in a test for exact matches. It should be noted, however, that surface realizers are rarely called upon to generate sentences with the extended lengths and complexities found in highly educated newspaper text. Finally, the "valid FD" column in­ dicates that the transformation program is very good at pro­ ducing valid functional descriptions, even if they eventually are discarded by the grammar as being erroneous.

The test set had a slightly higher coverage than the train­ ing set shown above, as well as a higher number of perfect matches and a better score using the NIST SSA measure. Al­ though we trained on other sections of the Penn TreeBank, time constraints due to the large amount of time required to generate all test sentences prevented us from having a fuller comparison set. Additionally, Section 24 was the first sec­ tion we trained on, and it is likely that later sections were more similar to Section 23, or that the amount of domain­ specific stock market constructions were imbalanced. Finally, the "close matches" column shows how many candidate sen­ tences might be nearly exactly matching, and the sum of these two is reflected in the final category "combined."

One interesting observation is that this evaluation (and cor­ respondingly, the evaluation of HALOGEN) is not only an evaluation of the underlying surface realizer, but also of the accompanying transformation program that converts the Penn TreeBank notation into the specifications it expects. We thus set out to perform a minor, secondary evaluation to determine if it were possible to find a baseline metric for how many sen­ tences could still be generated by the surface realizer even if the corresponding FDs could not be produced for them by the transformation program.

We thus randomly selected 25 sentences from each of the two sections which were not either perfect matches or "close"

matches, i.e., they were not in the "combined" match cate­ gory. While these sets included some of the problems listed in Section 3, 41 of the 50 were capable of being rendered by hand as FDs which produced exact matches without changes to the grammar, 6 required minor changes to the grammar which were quickly performed, and the remaining 3 sen­ tences required major grammar changes which have still not yet been made. The latter were sentences that still do not have satisfactory linguistic analyses in the linguistic literature. We thus conclude that with better transformation rules, we could then obtain close to 95% coverage.

5 Discussion

Surface realization is probably the most understood and com­ petent task in NLG today. There is a high possibility that sur­ face realization can already be considered a solved problem, except with regard to problems introduced by new languages or highly specialized domains. However, there are two re­ lated unsolved problems inherent in the process described in this paper.

5.1 Automatic Evaluation of Output

Evaluation of NLG systems face the same problems as those that confront Machine Translation systems: Given a set of generated sentences, how do you tell how "good" they are in general, and how often you can produce good sen­ tences in a given context or application. Work in machine translation has shifted to large-scale evaluations which re­ quire automatic evaluation techniques [Papineni et al., 2001 ;

Doddington, 2002] because human graders cannot hope to examine all of the responses in a short enough period of time.

Yet current evaluation techniques are completely nu­ meric/statistical in nature and do not attempt to measure se­ mantic content (such as the well-known example of a missing "not" in a system's output). Furthermore, these techniques are ill-equipped to evaluate the types of sentences produced by symbolic NLG systems. For example, by changing a fea­ ture specifying that, say, a particularly lengthy purpose clause should go at the beginning rather than the end of a sentence, a string edit distance metric will report a very large error when in terms of the system's input, only one "error" has occurred.

As an example of this type of problem, consider that the string edit distance between the following original sen­ tence and that produced by the transformation program and FUF/SURGE with input from the Penn TreeBank would be 83, resulting in a NIST SSA 50.4% match:

Freddie Mac said the principal-only securities were priced at 58 1/4 to yield 8.45%, assuming an average life of eight years and a prepayment of 160% of the PSA model.

Freddie Mac said assuming an average life of eight years and a prepayment of 160% of the PSA model, the principal-only securities were priced at 58 1/4 to yield 8.45%.

Obviously 50.4% is a poor score for such sentences, but many such examples were found in our corpus and their low scores were factored into the NIST Simple String Accuracy ratios in Tables 2 and 3.

5.2 Symbolic vs. Statistical Approaches

Almost all fully-developed NLG systems to-date operate on data specified in a knowledge base from some other sys­ tem. The fact that this data has typically been represented as highly-structured data has been an impediment to tradi­ tional machine learning techniques which have previously op­ erated mostly on flat, unstructured text data. It is also gener­ ally stated that statistical methods are more robust than their symbolic counterparts and more easily adapted to new data sets. The data in the previous section seems to indicate that HALOGEN, a statistical system, performs substantially better on longer sentences, even if it has lower overall coverage. But there are several advantages in favor of symbolic techniques.

First, the transformation program presented above can be tweaked to an arbitrary level of perfection by progressively adding more rules. Most statistical and machine learning systems however have eventually reached a boundary where progress becomes seemingly exponentially more difficult. Second, errors which are encountered during processing can be examined and fixed because the grammars and other re­ sources are logically and semantically connected to the lan­ guage being generated, rather than being a set of numbers. If however a statistical generator must create new output forms not contained in the initial corpus or model, it must be re­ trained from scratch.

Finally, symbolic surface realizers allow a wide range of optional operations which statistical programs currently can't offer, for example, the capability of adding formatting state­ ments in HTML, modifying punctuation, generating dialect differences, adding prosody for TIS, etc. While this may be due to the multiple decades of history over which symbolic systems have been developed, it may also be due to the lack of annotated corpora that support statistical algorithms, or even potentially the impossibility of having a corpus at all, such as in large narratives [Callaway and Lester, 2002].

Additionally, there are some disadvantages to the current approaches undertaken in statistical NLG research. For in­ stance, symbolic NL generation systems are already consid­ ered slow, and FuF/SURGE is generally considered to be the slowest in the NLG community. And yet the data from Ta­ ble 3 shows that HALOGEN is anywhere from 6.5 to 16 times slower, and thus a I 0-sentence paragraph might need 4 min­ utes or longer to be generated. Moreover, these approaches use techniques such as n-gram models, where n must be in­ creased to improve quality, but results in even slower genera­ tion times and exponentially larger storage space.

5.3 Potential Applications

The transformation program presented here has additional side benefits besides helping calculate the coverage of a grammar. For example, in generation systems where non­ linguists must maintain old data and add new data, such a program allows them to write sample sentences in the syntax-only TreeBank notation, which is much easier for non-linguists, and then convert those sentences directly into a more linguistically-manageable form for generation (e.g., functional descriptions). Graphical editing tools for linguistic data such as GATE [Bontcheva et al., 2002] or similar author­ ing tools could quicken the process even more.

Additionally, the transformation program can be used as an error-checker for the well-formedness of sentences con­ tained in the TreeBank. Rules could be (and have been) added alongside the normal transformation rules that detect when er­ rors are encountered, categorize them, and make them avail­ able to the corpus creator for correction. This extends not only to annotation errors by the corpus creator detectable at the syntax tree level, but even morphology errors such as in­ correct verbs, typos, or British/ American English differences by the original author of the text. Both of these tasks are much more difficult for a statistical system to accomplish, requiring separate retraining in the first case and locating or creating a corpus of possible mistakes in the second, much like what is done with tutoring systems where databases of potential stu­ dent errors are painstakingly constructed.

6 Conclusions and Future Work

Recent years have seen the arrival of statistical approaches to the field of Natural Language Generation, much as was seen in parsing a decade ago. Of the many possible compo­ nents in the standard NLG pipelined architecture, almost all of these statistical systems have focused on the surface real­ ization component, offering the same robustness, wide cover­ age, and domain- and language-independence as for parsing.

Recent experiments with one statistically-based system, HALOGEN, showed that it could achieve respectable coverage without the typical development costs inherent in pro­ ducing grammars for symbolic NLG. By taking as input sen­ tences from the Penn TreeBank, HALOGEN was able to gen­ erate a substantial enough quantity of sentences to allow for an empirical analysis of grammatical coverage of English. This paper represents the analogous effort for a symbolic generation system using the FuF/SURGE systemic realization system, which includes the largest generation grammar.

We presented the results of a grammatical coverage eval­ uation experiment that showed the symbolic system had a higher level of coverage of English as represented by the Penn TreeBank. We also contrasted the statistical and symbolic methodologies and concluded with ideas for future applica­ tions for easier creation of NLG systems and automatic error­ checking for large-scale corpora. We also plan lo further de­ velop our Italian generation grammar developed at ITC-irst [Novello and Callaway, 2003] with a similarly annotated cor­ pus of Italian newspaper text.

7 Acknowledgements

This work was funded by the PEACH project, granted by the Autonomous Province of Trento in Italy.