Automatic Error Detection for Natural Language Generation
Michael Wayne Goodman† Francis Bond‡†University of Washington‡NICT Language Infrastructure Group, MASTAR Project
goodmami@u.washington.edu, bond@ieee.org
1Introduction

One of the advantages of deep grammars, such as
those based on HPSG, is that they can be used forgeneration as well as parsing. However, typicallythey are tested more thoroughly for parsing. In
this paper we introduce a system that helps thegrammar engineer eﬃciently bring the generation
capabilities to the same level as the parsing. Thesystem can quickly and accurately determine thecharacteristics of parsed and generated sentencesfrom a deep grammar, and then ﬁnd the mostsalient grammar rules used in producing particular classes of sentences. For our purposes, we
generally look at sentences that cannot generate
or overgenerate, ﬁnd the problematic rules causing them to be that way, and attempt to ﬁx thoserules.
Consider (1), the grammar was able to parsethis sentence, but was unable to generate any new
sentences from its semantics (Section 4.2 elaborates on this particular issue).
(1) 彼女は 写真
写り が いいkanojyo wa shashin utsuri ga ii
she
top picture taking nom good
She is good at taking pictures
The system is tested both on Jacy, an implemented HPSG grammar for Japanese and theERG (English Resource Grammar). Often, by ﬁxing the problems we not only improve generation
results, but also parsing coverage and accuracy.
1.1

Motivation

Bond et al. (2008) showed that by producing paraphrases of the English side of an aligned corpus,
they could increase their corpus size and improve
the performance of a statistical machine translation system. We want to increase the size of theJapanese side of the corpus for the same reasons.
However, Jacy could not generate new sentences
nearly as well as the ERG, and was thus unusablefor the task. Table 1 shows the initial parsing andgeneration statistics for both the ERG and Jacy
(further explanation of the table is in Section 2.1).
Improving generation would also greatly beneﬁt
to-Japanese machine translation tasks using theJacy grammar. It has also been shown that by
improving generation, one can generally increase
parsing performance.
1.2

ResourcesWe use the Jacy (Siegel, 2000) Japanese grammar (hereafter “Jacy”) and the English Resource
Grammar (ERG) (Flickinger, 2000) within theDELPH-IN1 machinery (PET (Callmeier, 2000)
for parsing and LKB (Copestake, 2002) for generating). These are rule-based systems basedon the Head-driven Phrase Structure Grammar(HPSG) (Pollard and Sag, 1994) formalism forsyntax, and Minimal Recursion Semantics (MRS)(Copestake et al., 2005) for semantic representation. These grammars can process a corpus of input sentences and output parsing and generation
profiles, which include lists of processable items,
their derivation trees, MRS, and surface form. We
use the Tanaka Corpus (Tanaka, 2001) for both
our English and Japanese input sentences. In thispaper, we will refer to a corpus item as the collection of an input sentence, its parse information(parse trees, MRS), and its generation information (generated trees, MRS, surface forms).
Regarding the parsing and generation processes, we are paraphrasing sentences into thesame language. This entails ﬁrst parsing the input sentence and obtaining the semantics fromthe best ranked parse(s), then using those semantics as input to generate new sentences. Therefore, we can only generate new sentences fromsentences that could be parsed.
1

Deep Linguistic Processing with HPSG Initiative –see http://www.delph-in.net for background information, including the list of current participants and pointers
to available resources and documentation

Unparsable
Ungeneratable
No original
Only original

ERG
abs
rel
13%
4%
4%
12% 15%
34% 40%

Jacyabsrel
21%
35% 44%
34% 77%
1%
2%

Table 1: Initial general statistics

Lexemes diﬀer
Tree diﬀers
Rules diﬀer
String diﬀers
MRS diﬀer

ERG
50%
69%
64%
63%
5%

Jacy
90%
75%
56%
95%
10%

Table 2: Initial comparative statistics

2Data Collection

Our error detection routine is a two-step process.
First we analyze the parsing and generation proﬁles to determine the characteristics of each
item. Characteristics include things such as lexical, syntactic, semantic, and surface similarity tothe original parsed sentence. We will call a uniquesequence of characteristics a characteristic pattern, abbreviated as CP. The second step in ourerror detection routine is to ﬁnd the most salient
grammar rules for certain CPs. To do this step,
we ﬁrst train a classiﬁer with a simpliﬁed form ofeach sentence’s syntactic structure as features anda string representation of each respective CP aslabels. After training, we ﬁnd the rules that havethe highest association to certain characteristics.
In our tests, we found that the highest ranked
rules for a class of problematic sentences indeed
pointed to the most signiﬁcant problems in thosesentences.
2.1

Determining CharacteristicsIn Tables 1 and 2, we list nine diﬀerent characteristics. The characteristics listed in Table 1 aregeneral, process-related qualities, and those listed
in Table 2 are comparative qualities between theparsed and generated sentences.
“Unparsable” means the grammar was unable
to parse the input sentence, and “Ungenerable”
means that it could not generate from the semantics created by a successful parse. “No original”

means that the grammar could parse and generate from an input sentence, but could not generate the original parsed sentence. “Only original”
means that the grammar could parse and generate a sentence, but could only generate the original sentence. This might be expected for very
simple sentences.
Items where the “Lexemes diﬀer” in the parsed
and generated sentences will have a word inserted, deleted, or replaced with something different. “Rules diﬀer” means that the (unordered)
set of rules invoked when generating that sentence
is diﬀerent from the set invoked when parsing theoriginal sentence. “Tree diﬀers”, on the other
hand, occurs when the derivation tree (that is, therules and their structure) diﬀers from the parse’s
in some way. “String diﬀers” occurs when the surface form of the parsed and generated sentences
are diﬀerent (ignoring some punctuation). Lastly,“MRS diﬀer” means that the argument structurein the semantics are not equivalent. Because weare paraphrasing from the same semantic structure we should never have diﬀerent semantics inthe parsed and generated sentences.
2.2

Problematic Rule Ranking

Once we have created a matrix of characteristic
patterns for all input and output sentences, wetrain a maximum entropy-based classiﬁer over thederivation tree and CPs. For each item, we extract a set of n-grams of nonbranching paths fromthe parse trees, creating separate paths for eachbranch in the original tree. These sets of paths areused as the features in the classiﬁer. See Figure
1 for an example derivation tree and some paths
extracted from it. We call these rule paths, abbreviated as RP. A string representation of theCPs from each item are then used as labels.

3Results and Interpretation

While the ranking of problematic rules requires
the characteristic patterns to be determined inorder to run, both the ranked RPs and the CPs
are useful individually to a grammar developer.
We will describe how one can use each of theseresources for grammar error detection.
3.1

Interpreting Characteristic Patterns

While some characteristics in a CP are mutually
exclusive (e.g. “Unparsable” and “Ungenerable”)

quantify-n-lrule• quantify-n-lrule → compounds-rule → kikai-machinecompounds-rule• compounds-rule → kikai-machine → 機械• quantify-n-lrule → compounds-rule → vn2n-det-lrulekikai-machine
機械vn2n-det-lrule
honyaku 1
翻訳• compounds-rule → vn2n-det-lrule → honyaku 1• vn2n-det-lrule → honyaku 1 → 翻訳

Figure 1: Derivation tree for “機械翻訳” (“machine translation”) and paths with length of 3others often occur in parallel. Those that occur together are most likely not independent fromeach other. For instance, if a generated sentence
has diﬀerent lexemes from the original sentence,then it most likely will also have a diﬀerent surface form.
Sometimes it can be useful to look at characteristics in combination. For example, every time
an item has diﬀering sets of rules it will invariably
have diﬀering trees as well. If, instead, the setsof rules are the same, but the tree structures differ, then there is a strong reason to believe thatthe clauses in the sentence were simply reordered.
Similarly, if an item has identical sets of lexemes,
sets of rules, and derivation trees, but has diﬀering surface forms, then it is likely applying incorrect inﬂectional rules, since inﬂectional rules do
not appear in the derivation tree.
3.2

Interpreting Problematic Rules

Our list of ranked rule paths is sorted on the scoreeach RP received from the classiﬁer. This is useful information, but it is incomplete. For example, the RP vend-vend-rule → adj-te-t-lexeme-cstem-infl-rule → nai-notyetend → “なく” has ascore of 0.34, and the RP hf-complement-rule →head-specifier-rule → koto-pred → “こと” has a(lower) score of 0.25, but the former only has 9
occurrences in the corpus, compared to the latter’s 63. For the grammar developer looking toﬁx bugs, the latter RP oﬀers to yield more gain
than the former, despite its higher score. Therefore, along with the score from the classiﬁer, wealso output the raw count of the items using thatparticular RP.
For a given list of ranked RPs, not all areunique. Since the RPs are n-grams, there aremany overlapping or subset RPs, and often eachvariant will receive a similar score. To reduce theamount of cruft, we exclude RPs that are subsets
or supersets of a previously listed RP. We do notexclude RPs that are merely shifted (such as 1-2-3and 2-3-4) since there is less assurance that they
do not actually describe a diﬀerent problem.
For example, we saw that the highest ranking
RP was quantify-n-lrule → compounds-rule, andit also occured many times in the corpus. This
RP is a bigram that could be taken from thederivation tree in Figure 1. It turned out thatthe problem was indeed the interaction between
the quantify-n-lrule and the compounds-rule. See
Section 4.2 for more information on the solution
to this problem.

4Grammar FixesWith the information provided by our system,
we tried to ﬁx some of the most prevalent problems. The ﬁrst problem we ﬁxed was to restructure how the grammar treated commas and colons
as topic markers. The second was to change therule for noun quantiﬁcation so compound nouns
could generate. We modiﬁed the treatment of numeral classiﬁers so they compound (e.g. ５年契
約 go-nen keiyaku “5-year contract”), stand alone
as nouns they aﬀect (e.g. 三匹が吠える san-biki
ga hoeru “Three (animals) bark”), and generateproperly in certain constructions (e.g. ３匹の犬
san-biki no inu “three dogs”). We removed somelexemes that caused spurious ambiguity, such as
the hiragana versions of the verbs にる niru “toboil” and てる deru “to leave, to attend”, as theywould incorrectly be used in place of the ni andde case markers. From this (non-exhaustive) listof changes made to the grammar, we will describe
the ﬁrst two in more detail.
The changes we made improved generation cov-Unparsable
Ungeneratable
No original
Only original
Lexemes diﬀer
Tree diﬀers
Rules diﬀer
String diﬀers
MRS diﬀer

beforeabs
rel21%
35% 44%
34% 77%
1%2%
90%
75%
56%
95%
10%

after
abs
rel
17%
28% 34%
41% 74%
1%2%
88%
72%
50%
94%
0.2%

Table 3: Jacy statistics, before and aftererage (over those items that could be parsed) by
nearly 10% to 66%, while reducing overgeneration. See Table 3 for updated statistics from theimproved grammar.
We also found some errors in the English grammar: e.g. the morphology is wrong for somegerunds: for the input I showered before breakfast, we generate I showerred before breakfast.
4.1

Overgenerating Topic Markers

In the initial version of Jacy, punctuation suchas commas, colons, and equals could be treatedas topic markers, which were a subtype of thewa-topic marker. This worked for parsing, but
in generation we would overgenerate a comma,colon, or equals for every instance of a watopic marker as in (2). We solved this by making the topic-marker hierarchy more informative:
comma, colon, equals, and wa were specialized todaughter types of a “topic” parent type. By making this change, we improved generation accuracy
by eliminating many undesirable results. Parsing
and generation coverage were not aﬀected.
(2)

a. その 計画 は 具体 化 し て き た
The project is taking shapeb. その 計画 、 具体 化 し て き た
c. その 計画 ： 具体 化 し て き た
d. その 計画 ＝ 具体 化 し て き た

4.2

Ungenerable Compound Nouns

Compound nouns (like the one in Figure 1) caused
almost every sentence in which they occurred tobe ungenerable. The only sentences that could
generate were those with explicit quantiﬁers, suchas この kono “this”. The problem was in thequantiﬁcation of bare-nouns after compounding.
The quantiﬁcation rule was a lexical-rule and thegenerator could not apply it after a phrase-rule(such as the compounds-rule). Thus, we changed
the quantiﬁcation rule to be a phrase-rule, allowing compounds to generate. This resulted in alarge boost in generation coverage. Fixing thisbug led to changes in other areas, such as numeralclassiﬁers. The extra changes not only resulted
in greater generation coverage, but also increased
parsing coverage by about 1.5%.

5Conclusion

We have introduced a system that not only analyzes problems in an implemented HPSG grammar, but also ﬁnds and ranks the possible sourcesof those problems. This tool can greatly reduce
the amount of time a grammar developer would
spend ﬁnding bugs, and helps them make informed decisions about which bugs are best toﬁx. Using our system, we were able to improve
Jacy’s generation coverage by 10% with only twoweeks of grammar development.

References
Francis Bond, Eric Nichols, Darren Scott Appling, andMichael Paul. 2008. Improving statistical machine translation by paraphrasing the training data. In International Workshop on Spoken Language Translation, pages
150–157. Honolulu.
Ulrich Callmeier. 2000. PET - a platform for experimentation with eﬃcient HPSG processing techniques. NaturalLanguage Engineering, 6(1):99–108.
Ann Copestake. 2002. Implementing Typed Feature Structure Grammars. CSLI Publications.
Ann Copestake, Dan Flickinger, Carl Pollard, and Ivan A.
Sag. 2005. Minimal Recursion Semantics. An introduction. Research on Language and Computation, 3(4):281–332.
Dan Flickinger. 2000. On building a more eﬃcient grammar by exploiting types. Natural Language Engineering,6(1):15–28. (Special Issue on Eﬃcient Processing withHPSG).
Carl Pollard and Ivan A. Sag. 1994. Head Driven Phrase
Structure Grammar.
University of Chicago Press,Chicago.
Melanie Siegel. 2000. HPSG analysis of Japanese. In
Wolfgang Wahlster, editor, Verbmobil: Foundations of
Speech-to-Speech Translation, pages 265 – 280. Springer,
Berlin, Germany.
Yasuhito Tanaka. 2001. Compilation of a multilingual parallel corpus. In Proceedings of PACLING 2001, pages
265–268. Kyushu. (http://www.colips.org/afnlp/
archives/pacling2001/pdf/tanaka.pdf).